Можете подсказать алгоритм поиска наиболее часто встречающихся подстрок в тексте?

Question

[knott]

Есть текст. Необходимо найти наиболее встречающиеся подстроки в нем.

Например:

Карл у Клары украл кораллы, а Клара у Карла украла кларнет.


Здесь например должно выдать:

• к (Карл, Клары, уКрал, Кораллы, Клара, Карла, уКрала, Кларнет)
  
• а (кАрл, укрАл, корАллы, клАра, кАрла, укрАла, клАрнет),
  
• ...
  
• клар (Клары, Клара, кларнет),
  
• карл (Карл, Карла),
  
• крал (украл, украла),
  
• украл (Украл, Украла)
  

С алгоритмами на Вы, но предполагаю что решение O(n²) нежелательно.


Очень уж не хочется придумывать свой велосипед.

Буду очень благодарен за помощь!

Comments

[knott]

Да, по сути так и есть. Самыми частыми будут однобуквенные строки.
В примере выше, они находятся в списке первыми, символизируя свою высокочастотность.

Answer 1

[MikhailEdoshin]

Суффиксное дерево (также на английском). Строится за линейное время, время поиска пропроционально длине искомой строки, памяти, правда, много занимает. (Забавно, что в Дискретном анализе (2003) И. В. Романовского в главе «Суффиксное дерево» дается пример как раз с этой же фразой о Карле и Кларе.)

Comments

[MikhailEdoshin]

Упс, простите, не до конца понял вопрос, хотя все равно суффиксное дерево поможет, только нужно будет к нему счетчики добавить.

[leventov]

Проще не счетчики добавлять, а по построенному дереву в глубину пройтись 1 раз.
И это точно верный путь:
«Functionality:… Find the most frequently occurring substrings of a minimum length (ex. 1) in O(n) time.» — со странички в английской википедии.

[MikhailEdoshin]

leventov: да, вы совершенно правы — мне почему-то показалось спросонья, что он схлопнет одинаковые строки и не будет возможности их сосчитать, хотя это вовсе не так.

[knott]

Все совпадения случайны. )
Памяти не жалко, самое главное — это время за которое отработает алгоритм.

Answer 2

[Алексей Фирсов]

Тоже интересно, если кто знает желательно с помощью регулярок.

Answer 3

[agmt]

Я не гуру, но сдаётся мне, что O(n2) — вполне достойно, по-крайней мере в той формулировке, что я понял. Ведь результатом должен быть отсортированный массив строк размером от n (исходная строка «аа… а») до (1+n)*n/2 (исходная строка «abcd..»). С введением ограничения на размер подстроки, быть может, получится и улучшить эффективность алгоритма.
А вообще, как говорил Пайк:

Правило 3: Изощрённые алгоритмы являются медленными, если n мало, а n обычно мало. В изощрённых алгоритмах присутствуют большие константы. До тех пор, пока вы не убедитесь, что n часто становится большим, избегайте изощрённости. (Даже если n становится большим, вначале используйте правило 2).

Answer 4

[Fahrenheit]

«Обычно» при постановке подобной задачи ставится вопрос о достаточно больших значениях n, а также о нахождении не всех, а m наиболее часто встречающихся последовательностей (в примере результата ведь нету подстроки «Карл у Клары украл кораллы, а Клара у Карла украла кларне» (исходная минус один символ), которая встречается один раз).
Соотвественно, алгоритм с n^2 плохо себя поведет.

Comments

[Fahrenheit]

Написал в ответ на комментарий от agmt

Answer 5

[Mrrl]

Я решал подобную задачу, заменяя самую часто встречающуюся пару символов новым символом (если она встречалась более трех раз) — правда, роль «символов» у меня играли слова. Самой длинной «часто встречающейся» подстрокой в «Мертвых Душах» оказалась «дама приятная во всех отношениях».

Answer 6

[motl]

Попробуйте структуру данных trie
en.wikipedia.org/wiki/Trie