メモリ効果的な検索が

Question

例えば、サフィックスの リストについては、辞書のいくつかの並べ替えを構築する作業があります：例えば、

[., .com., a.com., a.b.com., org., some.org., ...] 

と各着信文字列の「test.some .org "構築された辞書の中で最長の接尾辞を見つける。いくつかのメモリ制限があります。このケースで最も適切なアルゴリズム/データ構造は何ですか？

私にとって最も明白な選択肢は、逆の文字列のトライですが、メモリを消費するようです。私はサフィックス配列を使用しようとしましたが、それはタスクに合っていないように見えます。

辞書は変更できません。一度構築する必要があります。不変の試行のよりメモリ効率のよい表現ですか？

Answer 1

不変の文字列の場合、compressed trieはうまく機能します。主な考え方は、トライの1つのブランチを1つのノードとして表現することです。この方法の多くの有用な説明/論文がウェブにあります。