自动完成服务器端实现

Question

在html输入框中为自动完成功能实现服务器端组件的快速有效方法是什么？

我正在编写一个服务,在我们的Web界面的主搜索框中自动完成用户查询,完成显示在ajax驱动的下拉列表中.我们运行查询的数据只是我们系统知道的大型概念表,大致与维基百科页面标题集相匹配.对于该服务,显然速度是最重要的,因为网页的响应性对于用户体验是重要的.

当前实现只是将所有概念加载到有序集合中的内存中,并对用户击键执行简单的log(n)查找.然后使用尾部提供超出最接近匹配的附加匹配.该解决方案的问题在于它无法扩展.它目前正在运行VM堆空间限制(我设置-Xmx2g,这是我们可以在32位计算机上推送的最多),这阻止我们扩展我们的概念表或添加更多功能.在具有更多内存的计算机上切换到64位VM不是一个直接的选择.

我一直犹豫是否开始研究基于磁盘的解决方案,因为我担心磁盘搜索时间会影响性能.是否存在可以让我更好地扩展的解决方案,无论是完全在内存中还是在一些快速磁盘支持的实现中？

编辑:

@Gandalf:对于我们的用例,重要的是自动完成是全面的,而不仅仅是对用户的额外帮助.至于我们正在完成的内容,它是概念类型对的列表.例如,可能的条目是[("Microsoft","Software Company"),("Jeff Atwood","Programmer"),("StackOverflow.com","Website")].一旦用户从自动完成列表中选择一个项目,我们就会使用Lucene进行完整搜索,但我还不确定Lucene是否可以自动完成自动完成.

@Glen:这里没有使用数据库.当我在谈论表时,我只是指数据的结构化表示.

@Jason Day:我对这个问题的原始实现是使用Trie,但由于需要大量的对象引用,因此内存膨胀实际上比排序集更差.我将阅读三元搜索树,看它是否有用.

Answer 1

使用一个大的集合,我会尝试像Lucene索引一样找到你想要的术语,并设置一个在每次击键后重置的计时器任务,延迟为.5秒.这样,如果用户快速键入多个字符,则只有当用户暂停一秒时,才会在每个笔划中查询索引.可用性测试将让您知道该暂停应该有多长.

Timer findQuery = new Timer();
...
public void keyStrokeDetected(..) {
   findQuery.cancel();
   findQuery = new Timer();
   String text = widget.getEnteredText();
   final TimerTask task = new TimerTask() {
      public void run() {
         ...query Lucene Index for matches
      }
   };
   findQuery.schedule(task, 350); //350 ms delay
}

一些pseduocode那里,但这是主意.此外,如果设置了查询术语,则可以预先创建和优化Lucene索引.