java中的Typeahead/Incremental Search

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

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

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

现在我们正在寻找增量搜索/预先输入,例如"stackover"也将返回"www.stackoverflow.com".我们当然可以相应地填充我们的地图,例如将每个可能的字符串放入地图中,从给定最小尺寸的所有变化开始

- >地图键:

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

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

有什么建议？

最简单的解决方案:在列表中搜索

您也可以动态搜索,例如:

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

// search for "is"
List reduced = new ArrayList();
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将是最慢的,但是你可以使用已经减少的列表,这应该快得多.

更复杂:使用Trie

如果性能是一个问题,并且您只允许匹配strign开头的搜索(例如"stackoverflow"的"stack",而不是搜索项的"overflow"),则应该考虑将数据表示为Trie.这为您提供了O(c)搜索性能,其中c是字符数.因此搜索性能与搜索项的数量无关,这非常棒.

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

一个后缀树或多或少是一种先进的特里,在这里你还可以搜索任何子在O(c)中,作为特里.我想这是最先进的选择.