Auto complete/prefix matching like google :: Trie/Dwag/sphinx/lucene

Question

您好，聽說Trie最適合自動建議/自動完成。 但dwag使用較少的空間，所以我想dwag應該會更好。

此外，如果Sphinx/Lucene可以做前綴匹配，那麼爲什麼我們不應該使用它。

另外Trie/dwag適合小桌子？

Answer 1

我看到的問題與DAWGs; DAWG相對複雜。您可以通過所有單詞獲得唯一路徑（以便將某些數據與您通常需要的鍵相關聯），但是比使用只有前綴壓縮並且將具有唯一終端節點的trie更困難。使用DAWG獲得的後綴壓縮僅僅是值得的，如果你是非常有限內存有限（就像在嵌入式設備上一樣），你可能並沒有提到Lucene。

爲此任務設計了一個前綴樹。這是完美的。如果你需要自己寫，那就是你要去的地方。當然，如果你沒有特殊需求，也可以使用許多庫，非常適合。