50万个街道名称 - 使用什么数据结构实现快速搜索？

Question

我们有许多街道名称，这些名称存储在一个文件中。在生产环境中，我可能会在服务器启动时缓存它们。搜索应该是自动完成的，例如，当您输入“lang”时，您可能会得到8个匹配项：langstr、langestr等。

- Toskan

---

请考虑一个 https://en.wikipedia.org/wiki/Trie。 - Steve Kuo

你可能想看看Apache Solr，它提供了开箱即用的自动完成功能，无需从头开始。 - Mikos

Answer 1

你需要的是某种压缩字典树表示。建议从succinct tries或DAWG开始研究，它们具有出色的效率和非常好的空间利用率。 希望这能帮到你！

- templatetypedef

---

@tq- 我不熟悉mongodb，所以我不能发表评论。抱歉！ - templatetypedef

Answer 2

自动完成通常使用以下一种或多种方式实现：

• 树结构。通过将可搜索文本索引化为树形结构（前缀树、后缀树、dawg等），可以在牺牲存储空间的代价下执行非常快速的搜索。树遍历可以适应近似匹配。
• 模式分割。通过将文本分割成标记（ngrams），可以使用简单的哈希方案执行模式出现的搜索。
• 过滤。找到一组潜在的匹配项，然后应用顺序算法来检查每个候选项。

看看completely，这是一个Java自动完成库，实现了一些后面的概念。

- Filipe Miguel Fonseca