Простой алгоритм для поиска всех совпадающих под-текстов в двух текстах

По долгу службы мне часто нужно находить все пересечения между текстами (например, все цитаты из одного текста в другом). Я достаточно долго искал стандартное решение, которое бы позволило бы это делать, но найти его мне так и не удалось — обычно решается какая-то совсем или немного другая задача. Например, класс SequenceMatcher из difflib в стандартной библиотеке Питона находит самую длинную общую подпоследовательность в двух последовательностях hashable элементов, а потом рекурсивно повторяет поиск слева и справа от нее. Если в одном из текстов будет более короткая подпоследовательность, которая содержится внутри уже найденной (например, если кусок длинной цитаты где-то был повторен еще раз), он ее пропустит. Кроме того, когда я загнал в него «Войну и мир» и «Анну Каренину» в виде списков слов и попросил для начала найти самую длинную подпоследовательность, он задумался на семь минут; когда я попросил все совпадающие блоки, он ушел и не вернулся (в документации обещают среднее линейное время, но что-то в прозе Льва Толстого, по-видимому, вызывает к жизни worst-case квадратичное).

В конечном итоге я придумал свой алгоритм, тем самым наверняка изобретя велосипед, который надеюсь увидеть в комментариях. Алгоритм делает ровно то, что мне нужно: находит все совпадающие последовательности слов в двух текстах (за исключением тех, что в обоих текстах входят в состав более крупных совпадающих последовательностей) и сравнивает «Войну и мир» с «Анной Карениной» за минуту.



Принцип следующий: сначала из каждого текста извлекаются все биграммы и создается хэш-таблица, где для каждой биграммы указан ее порядковый номер. Затем берется более короткий текст, его биграммы перебираются в любом порядке, и если какая-то из них есть в словаре для второго текста, то в отдельно созданный массив добавляются все пары вида (№ биграммы из первого словаря, № биграммы из второго словаря). Например, если в тексте 1 биграмма «А Б» встречается на позициях 1, 2 и 3, а во втором тексте она же встречается на позициях 17, 24 и 56, в массив попадут пары (1, 17), (1, 24), (1, 56), (2, 17)… Это самое слабое место алгоритма: если оба текста состоят из одинаковых слов, то в массив попадет n на m пар цифр. Такие тексты, однако, нам вряд ли попадутся (алгоритм ориентирован на тексты на естественном языке), а чтобы снизить количество бессмысленных совпадений, можно заменить биграммы на любые n-граммы (в зависимости того, какие минимальные совпадения нужны) или выкинуть частотные слова.

Каждая пара цифр в массиве — это совпадение на уровне биграммы. Теперь нам надо получить оттуда совпадающие последовательности, причем если у нас есть совпадение вида «А Б Б В», то тот факт, что ровно эти же фрагменты текста совпадают по «А Б», «Б Б» и «Б В» т. д. надо проигнорировать. Все это очень легко сделать за линейное время при помощи умеренно нетривиальной структуры данных — упорядоченного множества. Оно должно уметь помещать в себя и выкидывать из себя элементы за константное время и помнить, в каком порядке элементы в него добавлялись. Имплементация такого множества для Питона есть здесь: code.activestate.com/recipes/576694-orderedset Для наших нужд оно должно уметь выплевывать из себя элементы не только из конца, но и из начала. Добавляем туда сделанный на скорую руку метод popFirst:

def popFirst(self):
        if not self:
            raise KeyError('set is empty')
        for item in self:
            i = item
            break
        self.discard(i)
        return i

Остальное совсем просто: вынимаем из множества первый элемент, кладем во временный массив и, пока можем, добавляем к нему такие элементы из множества, что у каждого следующего и первый и второй индексы на один больше, чем у предыдущего. Когда таких больше не оказывается, отправляем найденную параллельную последовательность в итоговый массив и повторяем заново. Все добавленные элементы тоже выкидываются из множества. Таким образом мы одновременно получаем макисмальные по длине параллельные последовательности, игнорируем совпадения подпоследовательностей в длинных последовательностях и не теряем связи между найденными последовательностями и другими местами в тексте (такие совпадения будут отличаться на первый или второй индекс). В конечном итоге на выходе имеем массив массивов, где каждый подмассив — совпадающая последовательность слов. Можно отсортировать эти подмассивы по длине или по индексу начала (чтобы узнать все параллельные места к тому или иному фрагменту) или отфильтровать по минимальной длине.

Код на Питоне без OrderedSet и с биграммами. compareTwoTexts сразу возвращает результат. Чтобы по номерам биграмм понять, какие именно фрагменты текста совпадают, нужно отдельно сделать словарь биграмм и из него обратный словарь (extractNGrams, getReverseDic) или просто взять список слов (extractWords): каждая биграмма начинается со слова, стоящего в той же позиции, что и она сама.

from OrderedSet import OrderedSet

russianAlphabet = {'й', 'ф', 'я', 'ц', 'ы', 'ч', 'у', 'в', 'с', 'к', 'а', 'м', 'е', 'п', 'и', 'н', 'р', 'т', 'г', 'о', 'ь', 'ш', 'л', 'б', 'щ', 'д', 'ю', 'з', 'ж', 'х', 'э', 'ъ', 'ё'}

def compareTwoTexts(txt1, txt2, alphabet = russianAlphabet):
    # txt1 should be the shorter one
    ngramd1 = extractNGrams(txt1, alphabet)
    ngramd2 = extractNGrams(txt2, alphabet)
    return extractCommonPassages(getCommonNGrams(ngramd1, ngramd2))

def extractNGrams(txt, alphabet):
    words = extractWords(txt, alphabet)
    ngrams = []
    for i in range(len(words)-1):
        ngrams.append(
            (words[i] + ' ' + words[i+1], i)
            )
    ngramDic = {}
    for ngram in ngrams:
        try:
            ngramDic[ngram[0]].append(ngram[1])
        except KeyError:
            ngramDic[ngram[0]] = [ngram[1]]
    return ngramDic

def extractWords(s, alphabet):
    arr = []
    temp = []
    for char in s.lower():
        if char in alphabet or char == '-' and len(temp) > 0:
            temp.append(char)
        else:
            if len(temp) > 0:
                arr.append(''.join(temp))
                temp = []
    if len(temp) > 0:
        arr.append(''.join(temp))
    return arr

def getReverseDic(ngramDic):
    reverseDic = {}
    for key in ngramDic:
        for index in ngramDic[key]:
            reverseDic[index] = key
    return reverseDic

def getCommonNGrams(ngramDic1, ngramDic2):
    # ngramDic1 should be for the shorter text
    allCommonNGrams = []
    for nGram in ngramDic1:
        if nGram in ngramDic2:
            for i in ngramDic1[nGram]:
                for j in ngramDic2[nGram]:
                    allCommonNGrams.append((nGram, i, j))
    allCommonNGrams.sort(key = lambda x: x[1])
    commonNGramSet = OrderedSet((item[1], item[2]) for item in allCommonNGrams)
    return commonNGramSet

def extractCommonPassages(commonNGrams):
    if not commonNGrams:
        raise ValueError('no common ngrams')
    commonPassages = []
    temp = []
    while commonNGrams:
        if not temp:
            temp = [commonNGrams.popFirst()]
            if not commonNGrams:
                break
        if (temp[-1][0]+1, temp[-1][1]+1) in commonNGrams:
            temp.append((temp[-1][0]+1, temp[-1][1]+1))
            commonNGrams.discard((temp[-1][0], temp[-1][1]))
        else:
            commonPassages.append(temp)
            temp = []
    if temp:
        commonPassages.append(temp)
    return commonPassages