快速字符串搜索，如startsWith()而不是equals()

Question

我有一个有序列表（一本字典 - 100K 单词）和许多需要经常在此列表中搜索的单词。所以性能是一个问题。我知道

HashSet.contains(theWord)

或

Collections.binarySearch(sortedList, theWord)

速度非常快。但我实际上并不是在寻找整个词。

我想要的是，假设搜索

"se"

并获取所有以

"se"

开头的单词。那么 Java 或任何库中有现成的解决方案吗？

更好的示例：在排序列表上执行以下操作的快速解决方案

List.subList (String beginIndex, String endIndex) // returns the interval 

myWordList.subList(“ab”, “bc”);

注意：这是一个非常相似的问题，但接受的答案并不令人满意。 重写HashSet的Contains方法

Answer 1

您在这里寻找的是一种通常称为“trie”的数据结构：

http://en.wikipedia.org/wiki/Trie

它将字符串存储在按前缀索引的树中，其中树的第一层包含字符串的第一个字符，第二层包含第二个字符，依此类推。结果是它允许您提取非常大的集合的子集非常快地按前缀字符串。

Answer 2

Trie结构非常适合字典和查找具有共同前缀的单词。 Google Collections/Guava 中贡献了 Trie 实现。

Answer 3

确实不需要新的结构：问题可以通过列表上的二分搜索来解决。特别是，您可以修改二分搜索以返回

first 匹配元素（具有指定前缀的第一个元素）。

List.subList(String beginIndex, String endIndex) // 返回区间 我可能很蠢，但是什么样的索引是字符串类型呢？你能澄清一下这部分吗？

Answer 4

您的搜索结果将是您的有序单词列表中的一个范围。为此，您需要该范围的第一个和最后一个元素的索引。

要获得第一个，请使用原始搜索字符串（“se”）运行二分搜索，将其与每次迭代中的当前位置进行比较。当当前位置的单词大于搜索字符串，但当前第 1 个单词小于搜索字符串时停止。

要获取最后一个索引，请对搜索项+“z”（“sez”）运行另一个二分搜索，但现在仅当当前索引处的单词小于“sez”但当前+1更大时才停止。

最终通过编程语言中可用的任何方式返回由第一个和最后一个索引标记的范围。

该方法建立在两个假设之上：

字符串比较发现“b”大于“az”
“z”是单词列表中最高的字符值

我在 JavaScript 数据操作库 (jOrder.net) 中实现了此算法。