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

Question

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

Очевидным решением было бы:

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

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

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

Answer 1

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

Найти префикс/postfix комбо по итерации.

Обе эти операции: O (n * k), где k - длина самого длинного слова; это same complexity как хэш-таблица.

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