Какой алгоритм я могу использовать, чтобы определить, появляется ли какая-либо последовательность из n слов в двух документах?

Question

Дано два документа:

Сейчас зима нашего недовольства Сделано славное лето этим солнцем Йорка; И все облака, которые гремят на наш дом В глубине океана похоронен. Теперь наши брови связаны победными венками; Наши ушибленные руки повешены для памятников; Наши строгие аварийные сигналы изменились на веселые встречи, Наши ужасные походы на восхитительные мероприятия.

(Ричард III)

Ричард (герцог Йоркский): [трижды стучит по бокалу по столу] Тишина! Молчать! Для короля!

Король (Ричард III): [встает, сгорбившись, говорит неловко] Сейчас лето нашего сладкого содержания , [Сделано?] [Ошибаться?] - отбрасывать зиму этими тудорскими облаками.

(BlackAdder, сезон 1, эпизод 1)

Какой алгоритм кто-то может использовать, чтобы выяснить, какие последовательности из трех слов существуют в обоих документах? Если таковые имеются, конечно - это не гарантировано.

В этом примере « now is the » - единственная последовательность из трех слов, встречающаяся в обоих документах.

Answer 1

Если не считать грубой силы, простейшим решением было бы создать хеш-карту с записями для каждого кортежа слов для одного текста, а затем проверить, присутствует ли каждый кортеж в другом тексте в хеш-карте.Это было бы линейно, учитывая постоянное окно (3 слова), но мы можем сделать это за линейное время, не зависящее от размера окна.

Чтобы сделать это эффективно, мы используем скользящий хеш .Вводимые символы в скользящий хэш будут хешами слов.Этот метод известен как алгоритм Рабина-Карпа .

Answer 2

Похоже, вы ищете общие подстроки длиной 3, за исключением того, что "символы", из которых состоят ваши "строки", на самом деле являются словами, а не одиночными символами. Итак, «У меня есть хитрый план» - это строка длиной 5.

Суффиксные деревья обычно упоминаются в этой точке: http://en.wikipedia.org/wiki/Generalised_suffix_tree,, но от того, сколько вам нужно, зависит, сколько у вас текстов. Пара вложенных циклов для сравнения, начиная с каждой пары границ слов (по одному в каждой строке), в конце концов завершит работу.