Java中的开头/增量搜索 [英] Typeahead / Incremental Search in java

问题描述

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

we've got a list of search-result mappings, e.g. a simple url mapping might look like

stackoverflow - >www.stackoverflow.com
joel - >www.joelonsoftware.com

"stackoverflow" -> "www.stackoverflow.com" "joel" -> "www.joelonsoftware.com"

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

so searching for the exact phrases is working fine.

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

Now we're looking for an incremental search / typeahead, e.g. "stackover" would also return "www.stackoverflow.com". We could of course populate our maps accordingly, e.g. put every possible string into the map, starting with all variations of a given min size

- >地图键：

stack - > stackoverflow
...
stackoverf - > stackoverflow
stackoverfl - > stackoverflow
stackoverflo - > stackoverflow
stackoverflow - > stackoverflow

stack -> stackoverflow ... stackoverf -> stackoverflow stackoverfl -> stackoverflow stackoverflo -> stackoverflow stackoverflow -> stackoverflow

但是这意味着需要更高的内存空间（我猜）。

However that would mean a higher memory footprint that necessary (I guess).

任何建议？

推荐答案

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

Simplest solution: Search in a List

搜索，例如：

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.

第一个serach将是最慢的，但是可以使用已经减少的列表，应该是更快。

The first serach will be the slowest, but then you can use the already reduced list which should be a lot faster.

更复杂：使用 Trie

More sophisticated: use a Trie

如果性能是一个问题，并且只允许与strign开始匹配的搜索（例如stackoverflow ，但不是溢出作为搜索词），您应该将数据表示为 Trie 。这给你O（c）搜索性能，其中c是字符数。所以搜索性能与搜索字词数量无关，这是非常棒的。

If performance is an issue and you only allow searches that match the start of the strign (e.g. "stack" for "stackoverflow", but not "overflow" as the search term), you should look into representing the data as a Trie. This gives you O(c) search performance, where c is the number of characters. So the search performance is independent of the number of search terms, which is quite awesome.

高级解决方案：使用后缀树

Advanced Solution: Use a Suffix Tree

A 后缀树或多或少是一个高级的Trie，在这里您还可以搜索O（c）中的任何子字符串，对于Trie。我会说这是最先进的选择。

A Suffix tree is more or less an advanced Trie, here you can also search for any substrings in O(c), as for the Trie. I'd say this is the most advanced option.

这篇关于Java中的开头/增量搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！