Классифицировать массив строк на основе общих черт

Question

У меня есть огромный список (200000) строк (из нескольких слов).Я хочу сгруппировать эти строки на основе общего массива совпадений слов среди этих строк.Я не могу придумать алгоритм с низким временем вычисления для этого

"AB 500"
"Автобус AB 500"
"Новости Калифорнии"
"Новости Калифорнии БЛА-БЛА"

Мой план состоял в следующем
a.Обозначьте их словами.
b.Создайте глобальный массив токенов
c.Сравните эти строки с обычными токенами.

Как вы уже догадались, это не помогает.Можете ли вы предложить алгоритм для этого?Я пишу это на python..

Answer 1

200000 - это не так уж много, вы можете сделать это

1. Разделите каждую строку, чтобы получить токены например"Новости, БЛА-БЛА" -> ["Бла-бла", "CA", "News"]
2. создайте запись dict для каждой длины списка, напримерв случае ["Бла", "CA", "News"] все комбинации по порядку
3. Теперь просто просмотрите dict и посмотрите группы

пример кода:

data="""AB 500
Bus AB 500
News CA
News CA BLAH"""

def getCombinations(tokens):
    count = len(tokens)
    for L in range(1,count+1):
        for i in range(count-L+1):
            yield tuple(tokens[i:i+L])

groupDict = {}
for s in data.split("\n"):
    tokens = s.split()
    for groupKey in getCombinations(tokens):
        if groupKey not in groupDict:
            groupDict[groupKey] = [s]
        else:
            groupDict[groupKey].append(s)

for group, values in groupDict.iteritems():
    if len(values) > 1:
        print group, "->", values

он выводит:

('News', 'CA') -> ['News CA', 'News CA BLAH']
('AB',) -> ['AB 500', 'Bus AB 500']
('500',) -> ['AB 500', 'Bus AB 500']
('CA',) -> ['News CA', 'News CA BLAH']
('AB', '500') -> ['AB 500', 'Bus AB 500']
('News',) -> ['News CA', 'News CA BLAH']

Answer 2

Вы имеете в виду что-то вроде этого?

>>> from collections import defaultdict
>>> L=["AB 500",
... "Bus AB 500",
... "News CA",
... "News CA BLAH"]
>>> d=defaultdict(list)
>>> for s in L:
...     for w in s.split():
...         d[w].append(s)
... 
>>> print d["News"]
['News CA', 'News CA BLAH']
>>> print d["CA"]
['News CA', 'News CA BLAH']
>>> print d["500"]
['AB 500', 'Bus AB 500']

Answer 3

Если повторение слов не является важной функцией для вашего варианта использования, я предлагаю наборы.То есть.:

thestrings = [
"AB 500",
"Bus AB 500",
"News CA",
"News CA BLAH",
]

thesets = dict((s, set(s.split())) for s in thestrings)

similarities = dict()
for s in thestrings:
  for o in thestrings:
    if s>=o: continue
    sims = len(thesets[s] & thesets[o])
    if not sims: continue
    similarities[s, o] = sims

for s, o in sorted(similarities, similarities.get, reverse=True):
  print "%-16r %-16r %2d" % (s, o, similarities[s, o])

Это близко к тому, что вы ищете?Он классифицирует 4 строки, которые вы указываете, так, как вы хотите, но это, конечно, очень слабый образец, поэтому я перепроверяю;-).

Answer 4

Что произойдет, если строка "AB 500 News CA" будет добавлена в ваш список?Должны ли две группы строк объединяться?Если нет, то как разделить список строк и почему?

Очень общий рабочий процесс для подобных проблем (если я правильно понял) выглядит следующим образом:

1. Получите список пар-кандидатов с помощью инвертированного индекса/Поиск сходства всех пар/Симхэшинг
2. Рассчитайте некоторые функции расстояния для каждой пары и объедините их в один вес
3. Каждая взвешенная пара ((a, b), вес) теперь представляет ребро в графике, которое вы можете сгруппировать в "группы совпадений слов" с помощью иерархической кластеризации / степенной итерации