Эффективный самый распространенный суффиксный алгоритм?

Question

У меня есть несколько строк в ГБ, и для каждого префикса я хочу найти 10 наиболее распространенных суффиксов. Есть ли эффективный алгоритм для этого?

Очевидное решение будет:

• Сохранение отсортированного списка <string, count> пар.
• Идентификация по бинарному экстенту для префикса, который мы ищем.
• Найдите 10 самых высоких count с в этой степени.
• Возможно, предварительно вычислить его для всех коротких префиксов, поэтому ему не нужно будет просматривать большую часть данных.

Я не уверен, будет ли это вообще эффективно. Есть ли лучший способ, который я упустил из виду?

Ответы должны быть в режиме реального времени, но это может потребовать столько предварительной обработки, сколько необходимо.

Answer 1

Поместите слова в дерево, например, trie или radix , поместив счетчик «количество вхождений» для каждого полного слова, чтобы вы знали, какие узлы являются окончаниями и как часто ониare.

Найти комбинации префикса / постфикса с помощью итерации.

Обе эти операции O (n * k), где k - длина самого длинного слова;это такая же сложность , что и у хеш-таблицы.

HAT-trie - это версия с поддержкой кэша, обещающая высокую производительность.