Простой алгоритм для поиска всех совпадающих под-текстов в двух текстах
По долгу службы мне часто нужно находить все пересечения между текстами (например, все цитаты из одного текста в другом). Я достаточно долго искал стандартное решение, которое бы позволило бы это делать, но найти его мне так и не удалось — обычно решается какая-то совсем или немного другая задача. Например, класс 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
