UPD: Нашлась хорошая имплементация при помощи суффиксного массива (см. комментарий ниже). Там не выводятся очевидным образом все нужные перекрестные совпадения, но вообще получается более или менее то, что надо.
О, при помощи небольшой проверки можно включать в LCP-массив только те ненулевые значения, которые связывают разные тексты, а не отмечают самоповторы, прекрасно.
Имплементировал ровно эти алгоритмы, работает неплохо спасибо! Только я пока не могу понять, как избавиться от параллельных совпадающих подпоследовательностей: в массиве суффиксов в одном месте будет рядом «ABQWERTY» и «ABQWER...», а где-то в другом — «BQWERTY» и «BQWER...», и это будет засчитано как второе по длине совпадение, что мне не нужно. Есть какой-то способ с этим справиться?
Очень схожие методы точно есть: они используются в биоинформатике для выравнивания белковых последовательностей с учетом локальных мутаций/ошибок в сканировании. С их помощью можно найти самую большую общую fuzzy подпоследовательность, а потом посмотреть по отдельности отрывки слева и справа от нее в обеих заданных последовательностях. Не знаю, к сожалению, какие там стандарты по времени выполнения: классический подход с дистанцией Левенштейна квадратичный.
Я же написал в основном тексте, что это не алгоритм общего назначения, а заточенный под конкретный — хотя и весьма широкий — вид данных, и описал случай, когда время будет квадратичным.
То есть не совсем так со временем: чтобы оно было квадратичным, надо, чтобы существенная часть текста B состояла из небольшого количества биграмм и эти же биграммы встречались в существенном количестве в тексте А — тогда будет много перекрестных совпадений. Тексты на естественном языке достаточно разнообразны на уровне биграмм, поэтому такого быть не должно.
Посмотрите внимательнее на цикл: мы один раз смотрим на каждую биграмму из первого словаря, и если она есть во втором словаре, делаем все пары из их номеров. Это даст квадратичное время только в том случае, если многие биграммы текста А много раз повторяются в тексте В. Иначе время будет линейным или даже сублинейным, и в случае с текстами на естественном языке так и происходит, потому что чем частотнее биграммы, тем таких биграмм меньше, и большинство биграмм встречаются только в одном тексте.
Согласен насчет сортировки, я это упустил, спасибо. Впрочем, этого logN-множителя можно избежать, если сразу использовать упорядоченный словарь: он будет помнить, в каком порядке туда добавлялись биграммы, потом в таком же порядке будут выявляться совпадения и добавляться в массив.
Да. Первый элемент последовательности выкидывается через popFirst, упорядоченное множество помнит порядок добавления элементов, так что это O(1). Когда мы ищем следующие, мы увеличиваем оба индекса в последнем найденном элементе, смотрим, есть ли такой в множестве, и если есть, то достаем его, добавляем во временный массив и удаляем из множества — это тоже все амортизированное О(1) (худший случай зависит от имплементации хэш-таблицы в Питоне, надо смотреть документацию).
Стоимость формирования массива зависит от того, сколько в двух массивах есть совпадающих биграмм. Например, если и последовательность A и последовательность B имеют вид «aaa, aaa, aaa, aaa», в массив совпадений попадут все пары номеров: (1, 1), (1, 2), (1, 3), (2, 1)… Это квадратичное, а не линейное время.
Что касается вычислительной сложности, то она раскладывается на следующие составляющие:
1. Препроцессинг последовательностей — линейное время, каждая биграмма добавляется в соответствующий хэш за О(1).
2. Формирование массива совпадений — зависит от содержания исходных последовательностей, линейное время на моей небольшой практике, в идеальном случае — сублинейное (текст А раскладывается на небольшое количество биграмм, и многих из них нет в тексте В), в маловероятном худшем случае — квадратичное время.
3. Процеживание массива совпадений — каждый элемент массива будет обработан один раз и включен в последовательность или сам сформирует последовательность из одного элемента. Соответственно, время здесь такое же, как в пункте 2.
Будет один огромный общий фрагмент (весь текст) плюс невыравненные совпадения разных мелких биграмм и рядов биграмм по тексту (причем, поскольку это один и тот же текст, эти вещи посчитаются дважды, несмотря на то, что проходим только по одному тексту). Самый большой по величине совпадающий фрагмент, не считая всего текста, это «которые под его предводительством направятся к редуту и войдут в линию с прочими войсками» (там в описании военной неразберихи повторяется текст депеши).
Что касается затрат по памяти/времени, то массив совпадений в данном случае все так же имеет терпимую длину 10884179 — 24,6 * длина инпута.
В общем случае суффиксное дерево решает проблемы поиска k общих подстрок за время Theta(n*k), что слишком долго. Я знаю, что есть оптимизация суффиксного дерева, которая переводит эту задачу в линейное время, но я пока не видел / не сделал подходящей имплементации.
См. еще мой ответ в следующем комментарии. Мне потребуется некоторое время на сбор данных, но я практически уверен, что при минимальной подгонке и нормальных текстах можно выйти на линейную память и время.
Я был бы рад узнать, как это разумно свести. В моем алгоритме и время, и память зависят от того, сколько элементов оказывается в массиве совпадений. Пока там получается линейная зависимость от более длинного инпута, причем с хорошими коэффициентами:
Герой нашего времени: 41527 слов
Анна Каренина: 268515 слов
Война и мир: 442152 слов
Герой нашего времени vs Анна Каренина: 461201 пар в массиве общих биграмм (Анна Каренина * 1,7)
Анна Каренина vs Война и мир: 6536013 пар в массиве общих биграмм (Война и мир * 14,8)
Герой нашего времени vs Война и мир: 578580 пар в массиве общих биграмм (Война и мир * 1,3)
Но и это все только потому, что я не пытался отсеять частотные слова и/или взять более крупные n-граммы, иначе зависимость не была бы так привязана к более крупному тексту. Так считаются все биграммы вида «и он», «и тут» и т.д., которые никому не нужны, конечно.
А с какой скоростью Ваш код находит не наибольшие, а все общие подстроки?
Согласен насчет сортировки, я это упустил, спасибо. Впрочем, этого logN-множителя можно избежать, если сразу использовать упорядоченный словарь: он будет помнить, в каком порядке туда добавлялись биграммы, потом в таком же порядке будут выявляться совпадения и добавляться в массив.
Что касается вычислительной сложности, то она раскладывается на следующие составляющие:
1. Препроцессинг последовательностей — линейное время, каждая биграмма добавляется в соответствующий хэш за О(1).
2. Формирование массива совпадений — зависит от содержания исходных последовательностей, линейное время на моей небольшой практике, в идеальном случае — сублинейное (текст А раскладывается на небольшое количество биграмм, и многих из них нет в тексте В), в маловероятном худшем случае — квадратичное время.
3. Процеживание массива совпадений — каждый элемент массива будет обработан один раз и включен в последовательность или сам сформирует последовательность из одного элемента. Соответственно, время здесь такое же, как в пункте 2.
Что касается затрат по памяти/времени, то массив совпадений в данном случае все так же имеет терпимую длину 10884179 — 24,6 * длина инпута.
Герой нашего времени: 41527 слов
Анна Каренина: 268515 слов
Война и мир: 442152 слов
Герой нашего времени vs Анна Каренина: 461201 пар в массиве общих биграмм (Анна Каренина * 1,7)
Анна Каренина vs Война и мир: 6536013 пар в массиве общих биграмм (Война и мир * 14,8)
Герой нашего времени vs Война и мир: 578580 пар в массиве общих биграмм (Война и мир * 1,3)
Но и это все только потому, что я не пытался отсеять частотные слова и/или взять более крупные n-граммы, иначе зависимость не была бы так привязана к более крупному тексту. Так считаются все биграммы вида «и он», «и тут» и т.д., которые никому не нужны, конечно.