java - 500,000 个街道名称 - 使用什么数据结构来实现快速搜索？

Question

So we have many street names. They come in a file. Id probably cache them when booting the server up in production. The search should be auto complete like - e.g. you type 'lang ' and you would get maybe 8 hits : langstr, langestr. Etc

Answer 1

您正在寻找的是某种压缩的特里树表示。您可能希望以简洁的尝试或DAWG作为起点，因为它们提供了出色的效率和非常好的空间使用率。

希望这可以帮助！

Answer 2

自动完成通常使用以下方法之一实现：

• 树木。通过在树结构（前缀树、后缀树、dawg 等）中对可搜索文本进行索引，可以执行非常快速的搜索，但会占用内存存储空间。树遍历可以适应近似匹配。
• 模式分区。通过将文本划分为标记（ngram），可以使用简单的散列方案执行模式出现的搜索。
• 过滤。找到一组潜在的匹配，然后应用顺序算法来检查每个候选。

看一下完全，一个实现后面一些概念的 Java 自动完成库。