如何在Java中创建一个简单的前缀索引？

Question

我有一组大量的网址，希望能实现自动完成功能。但我不喜欢简单粗暴的方法，因为它需要遍历整个网址集合，时间复杂度为线性：

for(String url: urls) if(url.startsWith(input) {doSomething();}

现在我知道在哈希集中，函数“contains()”的时间复杂度为“O(1)”，但是没有“containsPrefix()”。是否有简单的方法可以不使用像Lucene这样的大型库或自己编写代码来解决这个问题？我不介意这样做，但对于这样一个简单的问题来说，似乎有点过头了，所以我想知道是否存在现有的简单解决方案 :-)

从我的计算机科学课程中，我记得有一棵由字符串片段组成的树，但我忘记它叫什么了。它的工作原理是这样的：

[car, care, carrot,carrotville]->

car
|
-/
-e
-rrot
  |
  ----ville

附言：我该如何调用返回一个字符串是另一个字符串前缀的所有字符串的方法？例如如果a是b的前缀，那么b对于a是什么？

- Konrad Höffner

---

你想做什么？自动在每个字符串的开头添加一些文本吗？ - Android Killer

我想知道我的字符串是哪些字符串的前缀，以便我可以将它们作为自动完成建议。 - Konrad Höffner

Answer 1

如果您需要高效地查找字符串的前缀，请使用Trie，这是一种专门设计用于此目的的数据结构：

Trie（字典树或前缀树）是一种有序树数据结构，用于存储关联数组，其中键通常为字符串。与二叉搜索树不同，树中没有任何节点存储与该节点关联的键；相反，它在树中的位置定义了它所关联的键。所有节点的后代都具有与该节点关联的字符串的公共前缀，而根与空字符串相关联。

这里有两个链接，包含示例和实现。

- Óscar López

---

太好了！我使用了来自https://forums.oracle.com/forums/thread.jspa?messageID=8787521的代码，第一次尝试就成功了！ - Konrad Höffner

Answer 2

一个很好的替代算法是三叉搜索树（更节省内存）https://github.com/varunpant/TernaryTree/tree/master/TernaryTree 这里有一个Java实现的trie http://algs4.cs.princeton.edu/52trie/TrieST.java.html

- varun

Answer 3

很久以前，我在这里放了一个简单的Trie实现：

http://code.google.com/p/triebag/source/browse/trunk/src/triebag/tries/SimpleTrie.java

然而，这不是一个紧凑的Trie，因此它为每个字符创建一个节点，创建一个紧凑的Trie有点棘手。

- mdakin

---

太好了！如果每个字符只有一个节点，我也不介意，但为了防止有人有多个节点的问题，我会保持问题开放。 - Konrad Höffner

紧凑版本使用的节点数量约为原版的50％（至少对于字典中的土耳其单词而言）。这是测试代码，所以您可以看到它在运行中，希望没有错误 :) http://code.google.com/p/triebag/source/browse/trunk/test/triebag/tries/SimpleTrieTest.java - mdakin

我尝试了一下你的SimpleTrie，但它似乎对我不起作用。首先构造函数不是公共的，之后我改变了它，以下测试没有返回任何内容：SimpleTrie<String> trie = new SimpleTrie<>(); trie.add("x","x"); trie.add("xy","xy"); Iterator it = trie.getItemsWithPrefix("x"); while(it.hasNext()) System.out.println(it.next()); - Konrad Höffner

Answer 4

java.util.regex.Pattern 正则表达式实现可以有效地处理前缀：

StringBuilder buffer = new StringBuilder();
for (String prefix : prefixes) {
    if (buffer.length() > 0)
        buffer.append("|");
    buffer.append(prefix);
}
Pattern prefixPattern = Pattern.compile("^(" + buffer + ")");

您可以测试所有前缀：

boolean containsPrefix = prefixPattern.matcher(stringToTest).find();

注意：为简单起见，前缀字符串未经过转义。正则表达式字符 [, ]，\，*，？，$，^，（），{ } 和 | 必须以 \ 为前缀。

- Tires