Пометка похожих предложений с меньшей временной сложностью, чем n ^ 2

Question

Это мой первый пост, который долгое время был скрытным, поэтому постараюсь изо всех сил объясниться здесь.

Я использовал метод наименьшей общей подстроки наряду с базовым сопоставлением слов и сопоставлением подстрок(regexp) для объединения подобных историй в сети.Но проблема в том, что его временная сложность равна n ^ 2 (я сравниваю каждый заголовок со всеми остальными).Я выполнил очень простые оптимизации, такие как хранение и пропуск всех совпадающих заголовков.

Что мне нужно, так это какая-то предварительная обработка фрагмента текста, чтобы на каждой итерации я уменьшал количество постов, которым нужно соответствовать.Любая дальнейшая оптимизация также приветствуется.

Вот функции, которые я использую для того же.основная функция, которая вызывает их, сначала вызывает word_match, если более 70% слова совпадает, я далее иду вниз и вызываю 'substring_match' и LCSubstr_len.Код написан на Python, я также могу использовать C

import re

def substring_match(a,b):
    try:
        c = re.match(a,b) 
        return c if c else True if re.match(b,a) else False
    except:
        return False

def LCSubstr_len(S, T):
    m = len(S); n = len(T)
    L = [[0] * (n+1) for i in xrange(m+1)]
    lcs = 0
    for i in xrange(m):
     for j in xrange(n):
         if S[i] == T[j]:
             L[i+1][j+1] = L[i][j] + 1
             lcs = max(lcs, L[i+1][j+1])
         else:
             L[i+1][j+1] = max(L[i+1][j], L[i][j+1])
    return lcs/((float(m+n)/2))

def word_match(str1,str2):
    matched = 0
    try:
        str1,str2 = str(str1),str(str2)
        assert isinstance(str1,str)
    except:
        return 0.0
    words1 = str1.split(None)
    words2 = str2.split(None)
    for i in words1:
        for j in words2:
            if i.strip() ==j.strip():
                matched +=1
    len1 = len(words1)
    len2 = len(words2)
    perc_match = float(matched)/float((len1+len2)/2)
    return perc_match

Answer 1

Использовать инвертированный индекс: для каждого слова сохраните список пар (docId, numOccurences).Затем, чтобы найти все строки, которые могут быть похожи на данную строку, просмотрите ее слова и найдите строки, содержащие это слово в инвертированном индексе.Таким образом, вы получите таблицу "(docId, wordMatchScore)", которая автоматически содержит только записи, где wordMatchScore не равен нулю.

Существует огромное количество возможных оптимизаций;Кроме того, ваш код крайне неоптимальный, но если мы говорим об уменьшении количества пар строк для сравнения, то это все.

Answer 2

Ускорение word_match легко с наборами:

def word_match(str1,str2):
    # .split() splits on all whitespace, you dont needs .strip() after
    words1 = set(str1.split())
    words2 = set(str2.split())
    common_words = words1 & words2
    return 2.0*len(common_words)/(len(words1)+len(words2))

Это также показывает, что «A A A» и «A» имеют 100% общего по этой мере ...