Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 39
А вывод-то где? Эффективно получилось? Сколько памяти кушает при работе?
И где пример работы алгоритма? Статистика прогонов на разных типах текстов? Если задача была сравнить «Анну Каренину» с «Войной и миром», весьма интересно было бы посмотреть на результат. А то статья хорошая, но есть ощущение, что обрывается на самом интересном месте.
И где пример работы алгоритма? Статистика прогонов на разных типах текстов? Если задача была сравнить «Анну Каренину» с «Войной и миром», весьма интересно было бы посмотреть на результат. А то статья хорошая, но есть ощущение, что обрывается на самом интересном месте.
Статистику буду собирать постепенно.
Результат с «Войной и миром» неинтересный, потому что это тексты без нетривиальных совпадений. Самый большие общие фрагменты — «и тебе славу воссылаем, отцу и сыну и святому духу» и «Нет, это не может быть думала она. Он».
Результат с «Войной и миром» неинтересный, потому что это тексты без нетривиальных совпадений. Самый большие общие фрагменты — «и тебе славу воссылаем, отцу и сыну и святому духу» и «Нет, это не может быть думала она. Он».
Очень даже любопытные совпадения.
Полную статистику «В студию»!
Полную статистику «В студию»!
Советую или отдать алгоритм в Диссернет (или сравнить их алгоритм с вашим) или попросить у них примеры текстов диссертаций для сравнения. Там у них очень много попадается кусков, совпадающих от параграфов до десятков страниц. Правда, к сожалению, в большинстве случаев укравшие диссертации люди выходят сухими из воды — большие начальники.
www.dissernet.org
www.dissernet.org
См. еще мой ответ в следующем комментарии. Мне потребуется некоторое время на сбор данных, но я практически уверен, что при минимальной подгонке и нормальных текстах можно выйти на линейную память и время.
Какова в итоге вычислительная сложность вашего алгоритма?
Потому что мне задача интуитивно напоминает классический sequence alignment, вопрос только в том, как ее разумно свести.
Потому что мне задача интуитивно напоминает классический sequence alignment, вопрос только в том, как ее разумно свести.
Я был бы рад узнать, как это разумно свести. В моем алгоритме и время, и память зависят от того, сколько элементов оказывается в массиве совпадений. Пока там получается линейная зависимость от более длинного инпута, причем с хорошими коэффициентами:
Герой нашего времени: 41527 слов
Анна Каренина: 268515 слов
Война и мир: 442152 слов
Герой нашего времени vs Анна Каренина: 461201 пар в массиве общих биграмм (Анна Каренина * 1,7)
Анна Каренина vs Война и мир: 6536013 пар в массиве общих биграмм (Война и мир * 14,8)
Герой нашего времени vs Война и мир: 578580 пар в массиве общих биграмм (Война и мир * 1,3)
Но и это все только потому, что я не пытался отсеять частотные слова и/или взять более крупные n-граммы, иначе зависимость не была бы так привязана к более крупному тексту. Так считаются все биграммы вида «и он», «и тут» и т.д., которые никому не нужны, конечно.
Герой нашего времени: 41527 слов
Анна Каренина: 268515 слов
Война и мир: 442152 слов
Герой нашего времени vs Анна Каренина: 461201 пар в массиве общих биграмм (Анна Каренина * 1,7)
Анна Каренина vs Война и мир: 6536013 пар в массиве общих биграмм (Война и мир * 14,8)
Герой нашего времени vs Война и мир: 578580 пар в массиве общих биграмм (Война и мир * 1,3)
Но и это все только потому, что я не пытался отсеять частотные слова и/или взять более крупные n-граммы, иначе зависимость не была бы так привязана к более крупному тексту. Так считаются все биграммы вида «и он», «и тут» и т.д., которые никому не нужны, конечно.
пробовали сравнить Войну и мир с самим собой? Очень интересно узнать, что выйдет.
Русские мужики засунули лом в японскую пилу…
Им тоже было интересно.
Им тоже было интересно.
Будет один огромный общий фрагмент (весь текст) плюс невыравненные совпадения разных мелких биграмм и рядов биграмм по тексту (причем, поскольку это один и тот же текст, эти вещи посчитаются дважды, несмотря на то, что проходим только по одному тексту). Самый большой по величине совпадающий фрагмент, не считая всего текста, это «которые под его предводительством направятся к редуту и войдут в линию с прочими войсками» (там в описании военной неразберихи повторяется текст депеши).
Что касается затрат по памяти/времени, то массив совпадений в данном случае все так же имеет терпимую длину 10884179 — 24,6 * длина инпута.
Что касается затрат по памяти/времени, то массив совпадений в данном случае все так же имеет терпимую длину 10884179 — 24,6 * длина инпута.
Ну, начнем с того, что стоимость формирования массива —
n + m. Как именно вычислительная сложность зависит от этого массива?Стоимость формирования массива зависит от того, сколько в двух массивах есть совпадающих биграмм. Например, если и последовательность A и последовательность B имеют вид «aaa, aaa, aaa, aaa», в массив совпадений попадут все пары номеров: (1, 1), (1, 2), (1, 3), (2, 1)… Это квадратичное, а не линейное время.
Что касается вычислительной сложности, то она раскладывается на следующие составляющие:
1. Препроцессинг последовательностей — линейное время, каждая биграмма добавляется в соответствующий хэш за О(1).
2. Формирование массива совпадений — зависит от содержания исходных последовательностей, линейное время на моей небольшой практике, в идеальном случае — сублинейное (текст А раскладывается на небольшое количество биграмм, и многих из них нет в тексте В), в маловероятном худшем случае — квадратичное время.
3. Процеживание массива совпадений — каждый элемент массива будет обработан один раз и включен в последовательность или сам сформирует последовательность из одного элемента. Соответственно, время здесь такое же, как в пункте 2.
Что касается вычислительной сложности, то она раскладывается на следующие составляющие:
1. Препроцессинг последовательностей — линейное время, каждая биграмма добавляется в соответствующий хэш за О(1).
2. Формирование массива совпадений — зависит от содержания исходных последовательностей, линейное время на моей небольшой практике, в идеальном случае — сублинейное (текст А раскладывается на небольшое количество биграмм, и многих из них нет в тексте В), в маловероятном худшем случае — квадратичное время.
3. Процеживание массива совпадений — каждый элемент массива будет обработан один раз и включен в последовательность или сам сформирует последовательность из одного элемента. Соответственно, время здесь такое же, как в пункте 2.
У вас для каждого элемента из массива совпадений выполняется
O(1) работы?Да. Первый элемент последовательности выкидывается через popFirst, упорядоченное множество помнит порядок добавления элементов, так что это O(1). Когда мы ищем следующие, мы увеличиваем оба индекса в последнем найденном элементе, смотрим, есть ли такой в множестве, и если есть, то достаем его, добавляем во временный массив и удаляем из множества — это тоже все амортизированное О(1) (худший случай зависит от имплементации хэш-таблицы в Питоне, надо смотреть документацию).
Пойдем по вашему коду, а вы меня поправляйте, если я неправильно понял:
O(n*m), и это же — длина массива совпадений.
Дальше сортировка:
Если я ничего не путаю, сортировок (на сравнениях) лучше O(n log n) не бывает. Это означает, что ваш рантайм увеличился до O((n*m)log(n*m)).
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)).
Посмотрите внимательнее на цикл: мы один раз смотрим на каждую биграмму из первого словаря, и если она есть во втором словаре, делаем все пары из их номеров. Это даст квадратичное время только в том случае, если многие биграммы текста А много раз повторяются в тексте В. Иначе время будет линейным или даже сублинейным, и в случае с текстами на естественном языке так и происходит, потому что чем частотнее биграммы, тем таких биграмм меньше, и большинство биграмм встречаются только в одном тексте.
Согласен насчет сортировки, я это упустил, спасибо. Впрочем, этого logN-множителя можно избежать, если сразу использовать упорядоченный словарь: он будет помнить, в каком порядке туда добавлялись биграммы, потом в таком же порядке будут выявляться совпадения и добавляться в массив.
Согласен насчет сортировки, я это упустил, спасибо. Впрочем, этого logN-множителя можно избежать, если сразу использовать упорядоченный словарь: он будет помнить, в каком порядке туда добавлялись биграммы, потом в таком же порядке будут выявляться совпадения и добавляться в массив.
Что касается «время только в том случае» — я оцениваю сложность на произвольных входных данных, делать предположения об их структуре мне сейчас не хочется.
То есть не совсем так со временем: чтобы оно было квадратичным, надо, чтобы существенная часть текста B состояла из небольшого количества биграмм и эти же биграммы встречались в существенном количестве в тексте А — тогда будет много перекрестных совпадений. Тексты на естественном языке достаточно разнообразны на уровне биграмм, поэтому такого быть не должно.
Можно решить с помощью суффиксного дерева
en.wikipedia.org/wiki/Longest_common_substring_problem#Suffix_tree
en.wikipedia.org/wiki/Longest_common_substring_problem#Suffix_tree
В общем случае суффиксное дерево решает проблемы поиска k общих подстрок за время Theta(n*k), что слишком долго. Я знаю, что есть оптимизация суффиксного дерева, которая переводит эту задачу в линейное время, но я пока не видел / не сделал подходящей имплементации.
UPD: Нашлась хорошая имплементация при помощи суффиксного массива (см. комментарий ниже). Там не выводятся очевидным образом все нужные перекрестные совпадения, но вообще получается более или менее то, что надо.
Т.е. по сути получилось что-то вроде сжатия LZW, только вместо байт в него летят хэши биграмм, и на выходе пользу имеет не «сжатый» текст, а полученный словарь.
Решал такую-же задачу. Начинал примерно с того же: найти хэшированием би-грам, триграмм «якорные» точки, связывающие два текста и искать затем минимальные покрытия. Но посмотрев на известные алгоритмы на строках понял, что там уже все топтано-перетоптано и ничего уже не изобретешь.
В итоге использовал суффиксный массив, который строил алгоритмом Манбера-Майерса (есть и быстрее), затем наибольшие фрагменты искал алгоритмом Касаи.
Мне нужно было найти повторяющиеся фрагменты в текстах модулей конфигураций 1С. При том, что алгоритмы реализованы непосредственно на 1С (!!!) работает все достаточно шустро. Притом обнаруживает и самосовпадения (повторы внутри одного файла).
На Вашей задаче (Война и мир и Анна Каренина) отработало примерно за две минуты. Тексты брал на royallib. В Войне и мире там сноски повторяются по два раза. То есть сначала перевод записан сразу после французского текста, а затем еще раз в конце. Самый длинный такой фрагмент состоит из 384 слов. В Анне Карениной самосовпадений меньше, но тоже встречаются.
Описание моего «копипастомера» и код приведены здесь: infostart.ru/public/294285.
В итоге использовал суффиксный массив, который строил алгоритмом Манбера-Майерса (есть и быстрее), затем наибольшие фрагменты искал алгоритмом Касаи.
Мне нужно было найти повторяющиеся фрагменты в текстах модулей конфигураций 1С. При том, что алгоритмы реализованы непосредственно на 1С (!!!) работает все достаточно шустро. Притом обнаруживает и самосовпадения (повторы внутри одного файла).
На Вашей задаче (Война и мир и Анна Каренина) отработало примерно за две минуты. Тексты брал на royallib. В Войне и мире там сноски повторяются по два раза. То есть сначала перевод записан сразу после французского текста, а затем еще раз в конце. Самый длинный такой фрагмент состоит из 384 слов. В Анне Карениной самосовпадений меньше, но тоже встречаются.
Описание моего «копипастомера» и код приведены здесь: infostart.ru/public/294285.
Спасибо! Я взял тексты романов без сносок.
А с какой скоростью Ваш код находит не наибольшие, а все общие подстроки?
А с какой скоростью Ваш код находит не наибольшие, а все общие подстроки?
Или алгоритм Касаи на самом деле выдает все повторы, а не только самые длинные?
Касаи выводит LCP. А затем я уже сам выбираю из него «зубцы» за один проход по массиву.
Имплементировал ровно эти алгоритмы, работает неплохо спасибо! Только я пока не могу понять, как избавиться от параллельных совпадающих подпоследовательностей: в массиве суффиксов в одном месте будет рядом «ABQWERTY» и «ABQWER...», а где-то в другом — «BQWERTY» и «BQWER...», и это будет засчитано как второе по длине совпадение, что мне не нужно. Есть какой-то способ с этим справиться?
А, я не совсем понял, как работает LCP, теперь ясно.
А есть ли такой алгоритм с нечетким сравнением фрагментов (типа cosine similarity with threshold — не знаю как правильно такое назвается, но идея думаю, понятна)
Очень схожие методы точно есть: они используются в биоинформатике для выравнивания белковых последовательностей с учетом локальных мутаций/ошибок в сканировании. С их помощью можно найти самую большую общую fuzzy подпоследовательность, а потом посмотреть по отдельности отрывки слева и справа от нее в обеих заданных последовательностях. Не знаю, к сожалению, какие там стандарты по времени выполнения: классический подход с дистанцией Левенштейна квадратичный.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Простой алгоритм для поиска всех совпадающих под-текстов в двух текстах