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。

为此任务设计了一个前缀树。这是完美的。如果你需要自己写，那就是你要去的地方。当然，如果你没有特殊需求，也可以使用许多库，非常适合。