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