TrieとRadixツリーとPatricia trieとの比較

私は（hereからも）理解しているように、これらのDSのメモリの複雑さは、Trie> Radix> Patriciaのように並べることができます。しかし、時間の複雑さはどうですか？私は彼らがほぼ同じだと思う。TrieとRadixツリーとPatricia trieとの比較

私の問題について言えば、事前に構築された辞書からプレフィックス検索クエリをたくさん使いたいと思います。メモリは私にとって大きな懸念事項ではありません。私は最も速いDSを使いたいです。

HAT-trieが最適ですが、実装するには複雑すぎます。上記のDSの代わりにTernary Search Treesを使用する必要がありますか？

ありがとうございます！

出典

2016-03-29 Eziz Durdyyev

https://www.youtube.com/watch?v=jXAHLqQthKw 時間の尺度はまたPatriciaTrieはトライよりも少ないメモリを消費し –

http://stackoverflow.com/questions/14708134をチェックしてください/ trie-and-the-the-the-difference-between-trie-and-radix-trie-data-structuresを使用しています。 – KGhatak

ハットトライはそれほど難しくないかもしれません。有限状態マシンとaho-corasickアルゴリズムを見てください。基本的にトライの幅優先探索です。トライとPatriciaTrie のための最後のスライドに

出典

2016-03-29 12:10:16 Bytemain

あなたの注意と努力に感謝しますが、あなたは私の質問にも答えませんでした。 –

TrieとRadixツリーとPatricia trieとの比較

答えて

関連する問題