java - 自动完成服务器端实现

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 索引之类的方法来查找您想要的术语，并设置一个计时器任务，该任务在每次击键后重置，延迟为 0.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
}

那里有一些伪代码，但就是这样。此外，如果设置了查询词，则可以预先创建和优化 Lucene 索引。