java - java中的Typeahead/增量搜索

Question

我们有一个搜索结果映射列表，例如一个简单的 url 映射可能看起来像

"stackoverflow"-> "www.stackoverflow.com" “乔尔”->“www.joelonsoftware.com”

所以搜索确切的短语工作正常。

现在我们正在寻找增量搜索/提前输入，例如“stackover”也会返回“www.stackoverflow.com”。我们当然可以相应地填充我们的 map ，例如将所有可能的字符串放入映射中，从给定最小大小的所有变体开始

-> 映射键:

堆栈 -> 计算器 ... stackoverf -> 计算器溢出 stackoverfl -> 计算器溢出 stackoverflo -> stackoverflow 计算器 -> 计算器

然而，这意味着需要更高的内存占用(我猜)。

有什么建议吗？

Answer 1

最简单的解决方案:在列表中搜索<​​/strong>

您也可以即时搜索，例如:

List<String> urls = Arrays.asList("this", "is", "a", "test");

// search for "is"
List<String> reduced = new ArrayList<String>();
String searchWord = "is";
for (String s : urls) {
    if (s.contains(searchWord)) {
         reduced.add(s);
    }
}

// when the user types more, search again using the already reduced list.

第一个搜索将是最慢的，但之后您可以使用已经减少的列表，这应该会快得多。

更复杂:使用 Trie

如果性能是个问题，并且您只允许匹配字符串开头的搜索(例如，“stack”代表“stackoverflow”，而不是“overflow”作为搜索词)，您应该考虑将数据表示为Trie .这为您提供了 O(c) 搜索性能，其中 c 是字符数。所以搜索性能与搜索词的数量无关，这非常棒。

高级解决方案:使用 Suffix Tree

A Suffix tree或多或少是一个高级的Trie，在这里你也可以在O(c)中搜索任何子串，对于Trie。我会说这是最高级的选项。