在数组中搜索特定字符串

Question

我想知道在一个String数组中检查单词是否存在的最快方法/算法。例如，如果我有一个包含10,000个元素的字符串数组，我想知道它是否有单词"Human"。我可以对数组进行排序，没有问题。

然而，二分搜索（Arrays.binarySearch()）不被允许。其他集合类型，如HashSet、HashMap和ArrayList也不被允许。

有没有证明过的算法或其他方法？搜索的方式应该非常非常快。

- PeakGen

---

禁止使用二分搜索算法，还是仅禁止使用库中的二分搜索实现？同样地，是否允许自己编写哈希数据结构？ - Patricia Shanahan

@PatriciaShanahan：你是指HashMap吗？ - PeakGen

@PatriciaShanahan：我的单词已经被哈希了。这意味着，我将它们保存在三个字符的格式中。例如，“astronaut”这个单词将会是“!2#”。 - PeakGen

不，我的意思是自己实现一个哈希数据结构，而不依赖于现有的库实现。 - Patricia Shanahan

Answer 1

最快的排序方法将导致O(nLogn)的复杂度。因此，如果你想在无序数据中查找特定的单词，只需使用单个for循环扫描数组即可，这将花费O(n)。

- Vilen

---

对于每个单词，它将花费O（n * 单词长度）...非常昂贵。 - Aseem Goyal

length_of_word本质上不是一个变量，因此从渐近符号表示法来看，O(n)=O(100000000000*n)。 - Vilen

@VilenMelkumyan 当然是一个变量。我可以轻松地想象出具有无限词汇大小的字典。 - Niklas B.

是的，但我想这取决于您的数据以及您如何看待它。总的来说，如果您有一个字符串数组，那么肯定有一个字符串具有最大长度，因此单词长度是有限的。 如果字符串数组不同，则您是正确的。 - Vilen

Answer 2

为了达到最快的性能，您需要使用哈希。您可以使用滚动哈希。它确保了更少的碰撞。

hash = [0]*base^(n-1) + [1]*base^(n-2) + ... + [n-1]   

其中base是一个质数，比如说31。

你需要进行模运算，以确保整数范围不会超出一个质数。

时间复杂度：考虑乘法和模运算O(number of characters)，操作O(1)。

这里有一个非常好的解释：Rolling hash快速实现

- Aseem Goyal

Answer 3

将数组构建成trie。它可以在线性时间内构建（假设字母表大小是常数）。然后您也可以在线性时间内进行查询（时间与查询单词长度成正比）。预处理和查询时间都是渐近最优的。

- Niklas B.

---

+1 对于提出这个问题。创建 Trie 时，这将是一次性费用吗？比如说，如果我想要向已经创建的 Trie 添加一组单词，它会再次搜索那个特定的节点并添加到它，还是完全创建一个新的 Trie？ - bgth

@bgth 是的，你可以通过该算法直接向Trie中插入和删除数据。运行时间也是线性的（最优），因此如果你最初使用空Trie并逐个添加单词，则总体上仍然可以获得线性时间。 - Niklas B.

但是它是否是寻找整个字符串的正确工具，而不是最接近匹配的工具呢？另外，它是否会为所有在其上方的节点抛出匹配项？比如，如果你正在搜索" Hum"，它是否会为"Hum"、"Huma"、"Human"和"Humanitarian"都抛出匹配项呢？ - bgth

@bgth：你走到代表字符串“Human”的节点旁边。然后你检查它是否有一个布尔标记，表示“这个节点代表输入词语之一”。老实说，我并没有看出问题在哪里。从算法的角度来看，它绝对是正确的工具，因为它具有最优的运行时限制。而且它在实践中也非常快（但由于缓存未命中，可能不如基于哈希的方法那么快）。 - Niklas B.

请问您能否指点我一本详细介绍此类及其他读取算法的书籍？ - bgth

@bgth 我通常不从书本上学习，所以我只能告诉你别人说什么。Knuth的书据说很好，Cormen（算法导论）是一部经典之作。虽然我不太喜欢Cormen。 - Niklas B.