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

Question

我有一个有序列表（一个包含100K个单词的字典），需要经常在该列表上搜索许多单词。因此，性能是关键问题。我知道HashSet.contains(theWord)或Collections.binarySearch(sortedList, theWord)非常快。但实际上，我并不是要查找整个单词。

我想要的是，例如搜索“se”，并获取所有以“se”开头的单词。那么，Java或任何库中是否存在现成的解决方案呢？

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

List.subList (String beginIndex, String endIndex) // 返回区间

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

注意：这里有一个非常类似的问题，但被接受的答案并不令人满意。 Overriding HashSet's Contains Method

- hrzafer

Answer 1

您在寻找的是一种常被称作'trie'的数据结构：

它将字符串按前缀存储在树形结构中，其中树的第一层包含字符串的第一个字符，第二层包含第二个字符，依此类推。因此，它能够快速地通过前缀提取非常大的字符串集合的子集。请参考以下链接：http://en.wikipedia.org/wiki/Trie

- David Given

---

有没有任何流行库提供的实现？ - Rajat Gupta

这个？声称已经被贡献给Apache Commons Collections和Google Collections，但是快速查看ACC没有在Javadoc中显示。http://code.google.com/p/patricia-trie/ - David Given

是的，完全正确。我也无法弄清楚，所以才问你。 - Rajat Gupta

Answer 2

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

- mdma

---

我已经检查过了，看起来没问题。但是我无法编译代码。它依赖于其他一些包，这使得事情变得更加复杂。我将只修改一个字符串的二分搜索实现。 - hrzafer

我无法理解Guava库或Apache commons collections中Trie实现的具体细节。它是否有其他名称？ - Rajat Gupta

Answer 3

其实并不需要新的数据结构：可以通过对列表进行二分查找来解决问题。特别地，你可以修改二分查找算法以返回匹配的第一个元素（具有指定前缀的第一个元素）。

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

- Nikita Rybak

---

我只是想用已知的方法，比如List.subList（int beginIndex，int endIndex），来解释这个问题。 - hrzafer

@hrzafer 那些参数是什么意思？它们是字符串的前缀和后缀吗？ - Nikita Rybak

Answer 4

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

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

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

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

此方法基于两个假设：

• 字符串比较将“b”视为大于“az”
• “z”是单词列表中最高的字符值

我已经在JavaScript数据操作库（jOrder.net）中实现了此算法。

- Dan Stocker

---

你真的应该使用Character.MAX_VALUE而不是"z"，但除此之外，这篇文章基本上总结了它。根据你具体在做什么，当我遇到这样的问题时，我通常会在前缀上进行二进制搜索，然后使用"while (value.get(x).startsWith(prefix))"进行处理，而不是尝试返回一个范围。 - Jay

我完全同意你关于Character.MAX_VALUE的观点，但考虑到100k数量级，是不是更好考虑执行log(N)（N为字典长度）个额外的字符串比较，而不是K（K为结果集长度）呢？ - Dan Stocker