algorithm - 使用什么算法来匹配字符串的开头

Question

我有很多字符串要与搜索词匹配。

例子：

folks
fort
garage
grabbed
grandmother
habit
happily
harry
heading
hunter

我想搜索字符串“ha”和返回列表开头的算法，其中字符串以“ha”开头，在本例中为“habit”。

当然，我不会一一列出，因为列表很大。我可以做一些预处理来对列表进行排序或将其放入使这种搜索快速的结构中。

有什么建议么？

score 3 · Accepted Answer

那么你想要某种类型的排序结构。您可以使用 TreeMap 或 Radix Tree（Radix 将为您节省一些空间）。这样做的开销将是排序操作或插入排序数据结构的开销。然而，一旦排序，二分搜索会给你logN+1最坏的情况查找性能。

值得注意的是Lucene使用 Radix Trees afaik

score 1 · Accepted Answer

你的帖子留下了太多没有答案的问题。我的解释是你想从一个无序列的单词列表中创建一个字典。但是，当您搜索时ha，您真正想要的是什么？

你想要

如果你想要1和/或3，那么说trie的人是正确的。（我给你的链接有一个易于阅读的实现）。

如果2是你想要的，那么你能谈谈一个用例吗？如果没有，那么您正在考虑使用字符串搜索算法。没有更多细节，很难给出更准确的建议。

score 1 · Accepted Answer

1

您可以随时查看Patricia Trees。它们几乎非常适合这种事情。

于 2013-01-10T22:08:56.943 回答

score 1 · Accepted Answer

1

Trie是您正在寻找的。

于 2013-01-10T22:09:10.773 回答

score 0 · Accepted Answer

你的问题有很多模糊的地方。根据您的具体要求，您可能会发现Rabin-Karp字符串搜索方法对您有用。

5 回答 5