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

Question

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

" AB 500 "
"Автобус AB 500 "
" Новости CA "
" Новости CA BLAH"

Мой план был
а. Поместите их в слова.
б. Создать глобальный массив токенов
с. Сравните эти строки с общими токенами.

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

Answer 1

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

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

пример кода:

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

Если повторение слов не является важной особенностью для вашего случая использования, я предлагаю наборы. I.e.:

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 3

Вы имеете в виду что-то подобное?

>>> 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 4

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

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

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