В конечном итоге я придумал свой алгоритм, тем самым наверняка изобретя велосипед, который надеюсь увидеть в комментариях. Алгоритм делает ровно то, что мне нужно: находит все совпадающие последовательности слов в двух текстах (за исключением тех, что в обоих текстах входят в состав более крупных совпадающих последовательностей) и сравнивает «Войну и мир» с «Анной Карениной» за минуту.
Принцип следующий: сначала из каждого текста извлекаются все биграммы и создается хэш-таблица, где для каждой биграммы указан ее порядковый номер. Затем берется более короткий текст, его биграммы перебираются в любом порядке, и если какая-то из них есть в словаре для второго текста, то в отдельно созданный массив добавляются все пары вида (№ биграммы из первого словаря, № биграммы из второго словаря). Например, если в тексте 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
Комментарии (39)
lair
25.06.2015 01:58+2Какова в итоге вычислительная сложность вашего алгоритма?
Потому что мне задача интуитивно напоминает классический sequence alignment, вопрос только в том, как ее разумно свести.
macleginn Автор
25.06.2015 02:13Я был бы рад узнать, как это разумно свести. В моем алгоритме и время, и память зависят от того, сколько элементов оказывается в массиве совпадений. Пока там получается линейная зависимость от более длинного инпута, причем с хорошими коэффициентами:
Герой нашего времени: 41527 слов
Анна Каренина: 268515 слов
Война и мир: 442152 слов
Герой нашего времени vs Анна Каренина: 461201 пар в массиве общих биграмм (Анна Каренина * 1,7)
Анна Каренина vs Война и мир: 6536013 пар в массиве общих биграмм (Война и мир * 14,8)
Герой нашего времени vs Война и мир: 578580 пар в массиве общих биграмм (Война и мир * 1,3)
Но и это все только потому, что я не пытался отсеять частотные слова и/или взять более крупные n-граммы, иначе зависимость не была бы так привязана к более крупному тексту. Так считаются все биграммы вида «и он», «и тут» и т.д., которые никому не нужны, конечно.
andreich
25.06.2015 10:55+3пробовали сравнить Войну и мир с самим собой? Очень интересно узнать, что выйдет.
macleginn Автор
25.06.2015 11:23+1Будет один огромный общий фрагмент (весь текст) плюс невыравненные совпадения разных мелких биграмм и рядов биграмм по тексту (причем, поскольку это один и тот же текст, эти вещи посчитаются дважды, несмотря на то, что проходим только по одному тексту). Самый большой по величине совпадающий фрагмент, не считая всего текста, это «которые под его предводительством направятся к редуту и войдут в линию с прочими войсками» (там в описании военной неразберихи повторяется текст депеши).
Что касается затрат по памяти/времени, то массив совпадений в данном случае все так же имеет терпимую длину 10884179 — 24,6 * длина инпута.
lair
25.06.2015 12:24Ну, начнем с того, что стоимость формирования массива —
n + m. Как именно вычислительная сложность зависит от этого массива?macleginn Автор
25.06.2015 12:49Стоимость формирования массива зависит от того, сколько в двух массивах есть совпадающих биграмм. Например, если и последовательность A и последовательность B имеют вид «aaa, aaa, aaa, aaa», в массив совпадений попадут все пары номеров: (1, 1), (1, 2), (1, 3), (2, 1)… Это квадратичное, а не линейное время.
Что касается вычислительной сложности, то она раскладывается на следующие составляющие:
1. Препроцессинг последовательностей — линейное время, каждая биграмма добавляется в соответствующий хэш за О(1).
2. Формирование массива совпадений — зависит от содержания исходных последовательностей, линейное время на моей небольшой практике, в идеальном случае — сублинейное (текст А раскладывается на небольшое количество биграмм, и многих из них нет в тексте В), в маловероятном худшем случае — квадратичное время.
3. Процеживание массива совпадений — каждый элемент массива будет обработан один раз и включен в последовательность или сам сформирует последовательность из одного элемента. Соответственно, время здесь такое же, как в пункте 2.lair
25.06.2015 12:55У вас для каждого элемента из массива совпадений выполняется
O(1)работы?macleginn Автор
25.06.2015 13:00Да. Первый элемент последовательности выкидывается через popFirst, упорядоченное множество помнит порядок добавления элементов, так что это O(1). Когда мы ищем следующие, мы увеличиваем оба индекса в последнем найденном элементе, смотрим, есть ли такой в множестве, и если есть, то достаем его, добавляем во временный массив и удаляем из множества — это тоже все амортизированное О(1) (худший случай зависит от имплементации хэш-таблицы в Питоне, надо смотреть документацию).
lair
25.06.2015 13:21Пойдем по вашему коду, а вы меня поправляйте, если я неправильно понял:
for nGram in ngramDic1: if nGram in ngramDic2: for i in ngramDic1[nGram]: for j in ngramDic2[nGram]: allCommonNGrams.append((nGram, i, j))
O(n*m), и это же — длина массива совпадений.
Дальше сортировка:
allCommonNGrams.sort(key = lambda x: x[1])
Если я ничего не путаю, сортировок (на сравнениях) лучше O(n log n) не бывает. Это означает, что ваш рантайм увеличился до O((n*m)log(n*m)).macleginn Автор
25.06.2015 13:49Посмотрите внимательнее на цикл: мы один раз смотрим на каждую биграмму из первого словаря, и если она есть во втором словаре, делаем все пары из их номеров. Это даст квадратичное время только в том случае, если многие биграммы текста А много раз повторяются в тексте В. Иначе время будет линейным или даже сублинейным, и в случае с текстами на естественном языке так и происходит, потому что чем частотнее биграммы, тем таких биграмм меньше, и большинство биграмм встречаются только в одном тексте.
Согласен насчет сортировки, я это упустил, спасибо. Впрочем, этого logN-множителя можно избежать, если сразу использовать упорядоченный словарь: он будет помнить, в каком порядке туда добавлялись биграммы, потом в таком же порядке будут выявляться совпадения и добавляться в массив.lair
25.06.2015 14:01Что касается «время только в том случае» — я оцениваю сложность на произвольных входных данных, делать предположения об их структуре мне сейчас не хочется.
macleginn Автор
25.06.2015 14:06Я же написал в основном тексте, что это не алгоритм общего назначения, а заточенный под конкретный — хотя и весьма широкий — вид данных, и описал случай, когда время будет квадратичным.
macleginn Автор
25.06.2015 14:02То есть не совсем так со временем: чтобы оно было квадратичным, надо, чтобы существенная часть текста B состояла из небольшого количества биграмм и эти же биграммы встречались в существенном количестве в тексте А — тогда будет много перекрестных совпадений. Тексты на естественном языке достаточно разнообразны на уровне биграмм, поэтому такого быть не должно.
les_sosna
25.06.2015 06:35+2Можно решить с помощью суффиксного дерева
en.wikipedia.org/wiki/Longest_common_substring_problem#Suffix_treemacleginn Автор
25.06.2015 10:46В общем случае суффиксное дерево решает проблемы поиска k общих подстрок за время Theta(n*k), что слишком долго. Я знаю, что есть оптимизация суффиксного дерева, которая переводит эту задачу в линейное время, но я пока не видел / не сделал подходящей имплементации.
macleginn Автор
26.06.2015 01:34UPD: Нашлась хорошая имплементация при помощи суффиксного массива (см. комментарий ниже). Там не выводятся очевидным образом все нужные перекрестные совпадения, но вообще получается более или менее то, что надо.
klirichek
25.06.2015 07:24+3Т.е. по сути получилось что-то вроде сжатия LZW, только вместо байт в него летят хэши биграмм, и на выходе пользу имеет не «сжатый» текст, а полученный словарь.
Ildarovich
25.06.2015 14:39+1Решал такую-же задачу. Начинал примерно с того же: найти хэшированием би-грам, триграмм «якорные» точки, связывающие два текста и искать затем минимальные покрытия. Но посмотрев на известные алгоритмы на строках понял, что там уже все топтано-перетоптано и ничего уже не изобретешь.
В итоге использовал суффиксный массив, который строил алгоритмом Манбера-Майерса (есть и быстрее), затем наибольшие фрагменты искал алгоритмом Касаи.
Мне нужно было найти повторяющиеся фрагменты в текстах модулей конфигураций 1С. При том, что алгоритмы реализованы непосредственно на 1С (!!!) работает все достаточно шустро. Притом обнаруживает и самосовпадения (повторы внутри одного файла).
На Вашей задаче (Война и мир и Анна Каренина) отработало примерно за две минуты. Тексты брал на royallib. В Войне и мире там сноски повторяются по два раза. То есть сначала перевод записан сразу после французского текста, а затем еще раз в конце. Самый длинный такой фрагмент состоит из 384 слов. В Анне Карениной самосовпадений меньше, но тоже встречаются.
Описание моего «копипастомера» и код приведены здесь: infostart.ru/public/294285.macleginn Автор
25.06.2015 14:42Спасибо! Я взял тексты романов без сносок.
А с какой скоростью Ваш код находит не наибольшие, а все общие подстроки?
macleginn Автор
25.06.2015 14:53+1Или алгоритм Касаи на самом деле выдает все повторы, а не только самые длинные?
Ildarovich
25.06.2015 15:04+2Касаи выводит LCP. А затем я уже сам выбираю из него «зубцы» за один проход по массиву.
macleginn Автор
26.06.2015 01:23О, при помощи небольшой проверки можно включать в LCP-массив только те ненулевые значения, которые связывают разные тексты, а не отмечают самоповторы, прекрасно.
macleginn Автор
26.06.2015 00:38Имплементировал ровно эти алгоритмы, работает неплохо спасибо! Только я пока не могу понять, как избавиться от параллельных совпадающих подпоследовательностей: в массиве суффиксов в одном месте будет рядом «ABQWERTY» и «ABQWER...», а где-то в другом — «BQWERTY» и «BQWER...», и это будет засчитано как второе по длине совпадение, что мне не нужно. Есть какой-то способ с этим справиться?
Stas911
25.06.2015 18:18А есть ли такой алгоритм с нечетким сравнением фрагментов (типа cosine similarity with threshold — не знаю как правильно такое назвается, но идея думаю, понятна)
macleginn Автор
25.06.2015 21:45Очень схожие методы точно есть: они используются в биоинформатике для выравнивания белковых последовательностей с учетом локальных мутаций/ошибок в сканировании. С их помощью можно найти самую большую общую fuzzy подпоследовательность, а потом посмотреть по отдельности отрывки слева и справа от нее в обеих заданных последовательностях. Не знаю, к сожалению, какие там стандарты по времени выполнения: классический подход с дистанцией Левенштейна квадратичный.
PastorGL
А вывод-то где? Эффективно получилось? Сколько памяти кушает при работе?
И где пример работы алгоритма? Статистика прогонов на разных типах текстов? Если задача была сравнить «Анну Каренину» с «Войной и миром», весьма интересно было бы посмотреть на результат. А то статья хорошая, но есть ощущение, что обрывается на самом интересном месте.
macleginn Автор
Статистику буду собирать постепенно.
Результат с «Войной и миром» неинтересный, потому что это тексты без нетривиальных совпадений. Самый большие общие фрагменты — «и тебе славу воссылаем, отцу и сыну и святому духу» и «Нет, это не может быть думала она. Он».
DimonSmart
Очень даже любопытные совпадения.
Полную статистику «В студию»!
dyadyaSerezha
Советую или отдать алгоритм в Диссернет (или сравнить их алгоритм с вашим) или попросить у них примеры текстов диссертаций для сравнения. Там у них очень много попадается кусков, совпадающих от параграфов до десятков страниц. Правда, к сожалению, в большинстве случаев укравшие диссертации люди выходят сухими из воды — большие начальники.
www.dissernet.org
macleginn Автор
Я был бы очень рад посмотреть на их алгоритм, но он, кажется, закрытый.
mifki
Хм, неужели они так в лоб только точные совпадения ищут.
macleginn Автор
См. еще мой ответ в следующем комментарии. Мне потребуется некоторое время на сбор данных, но я практически уверен, что при минимальной подгонке и нормальных текстах можно выйти на линейную память и время.
Zibx
На линейную точно нельзя. Слово «хэш» подразумевает под собой логарифм.
jcmvbkbc
Ммм? Логарифм подразумевается деревом. Тупой хэш подразумевает константную память, умный может дорасти до линейной.