自动完成服务器端实现

Question

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

我正在我们的Web界面的主搜索框中写一个自动完成用户查询的服务，并且完成显示在ajax-powered下拉菜单中。我们正在运行查询的数据只是一个我们系统知道的大概念表，它大致与维基百科页面标题集相匹配。对于这项服务，显然速度是最重要的，因为网页的响应对用户体验很重要。

当前实现只是将所有概念加载到有序集合的内存中，并对用户按键执行简单的log（n）查找。然后用尾部组合提供超出最接近匹配的附加匹配。这个解决方案的问题是它不能缩放。它目前正在满足VM堆空间限制（我已经设置了-Xmx2g，这是我们可以在32位机器上推动的最多的），并且这妨碍了我们扩展概念表或增加更多功能。切换到具有更多内存的计算机上的64位虚拟机不是直接选项。

我一直在犹豫是否开始使用基于磁盘的解决方案，因为我担心磁盘寻道时间会导致性能下降。有没有可能的解决方案可以让我更好地扩展，无论是内存还是一些快速的磁盘备份实现？

编辑：

@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索引。

Answer 2

如果您无法将所有数据物理加载到RAM中，那么您将不得不处理在磁盘上存在一些数据。

你在使用什么数据库？

例如，Oracle有一个选项，您可以将整个表保存在内存中，并针对该表执行查询。

MySQL还声称有一些内存中的功能，但我对MySQL不太了解。

然后，您可以废除基于Java的缓存，也可以将缓存用于最常用/最近的搜索。

很明显，当你用完RAM时，有些数据将在磁盘上查询时发现，但根据系统的负载情况，这只会是第一次按键的问题，而不是后续的问题，因为在那之后该行将在内存中。

如果磁盘寻道使您放慢速度，那么您可以使用SSD驱动器进行调查以加快读取速度。

Answer 3

我有类似的要求。

我将关系数据库与单索引良好的合成表（避免连接和视图加速查找）以及内存中缓存（Ehcache）存储最常用的条目。

通过使用MRU缓存，您可以对大多数查找具有即时响应时间，并且在访问存储在磁盘上的大表中的索引列时，可能没有任何事情可以击败关系数据库。

这是您不能存储在客户端上的大数据集的解决方案，它工作得非常快（在我的情况下，总是在0.5秒内检索非缓存查找）。它也可以横向扩展 - 您可以随时添加额外的服务器和数据库服务器。

你也可以使用客户端上最常用的结果进行缓存，特别是如果你已经实现了它。就我而言，服务器端解决方案足够快，并且客户端加载时间足够慢，因此不保证。

P.S.只有当用户暂停一段时间才能进行客户端查询以避免重复查找，这是一个很好的解决方案。在我的客户端上，只有在输入了前三个字符后，我才查询数据库，因为在所有实例中返回的结果都不足以返回太多结果。

Answer 4

也许我误解了你的问题，但难道你不能使用JQuery插件Ajax的信息到你的应用程序？

Ajax Auto Suggest v2

Answer 5

我做这个了使用Ternary search tree小数据集：

我以前使用过这一个。 DDJ代码不难转换为Java，但是它假定整个数据集都可以放入内存。有三元搜索树的磁盘实现（here是python中的一个），但当然它们的性能会降低。由于三元搜索树擅长于部分匹配，但性能可能适合您的需求。

Answer 6

是否有可行的解决方案，这将 让我变得更好

是，甲骨文。这就是数据库的目的。只需索引相关列。如果您正在运行内存解决方案，那么磁盘寻道时间或网络延迟的折衷可能是没有意义的。特别是如果你在两者之间插入一个缓存层。

另外，如果稍微调整客户端代码，则可能会减少点击次数。如在查询运行之前设置最小数量的类型字符，或者在用户停止键入之后设置延迟的一小部分。如果您已经在使用这些设置，请将它们设置得更高一些。

Answer 7

我最终通过Lucene解决了这个问题;初始性能测试对我们的用例来说似乎已经足够了。为了使前缀查询能够正常工作，我需要进行一些黑客行为，因为我在扩展诸如“Jeff At *”之类的查询时遇到了TooManyClauses异常。我最终用一个FilterIndexReader封装了我的IndexReader，并设置了在前缀字词调用上返回的术语数量的上限。这里是我的代码：

Directory directory = FSDirectory.getDirectory(indexDir); 
IndexReader reader = IndexReader.open(directory); 
FilterIndexReader filteredReader = new FilterIndexReader(reader) { 
    @Override public TermEnum terms(Term t) throws IOException { 
    final TermEnum origEnum = super.terms(t); 

    return new TermEnum() { 
     protected int count = 0; 
     @Override public boolean next() throws IOException { 
     if (count++ < (BooleanQuery.getMaxClauseCount() - 10)) 
      return origEnum.next(); 
     else return false; 
     } 

     @Override public Term term() { 
     return origEnum.term(); 
     } 

     @Override public int docFreq() { 
     return origEnum.docFreq(); 
     } 

     @Override public void close() throws IOException { 
     origEnum.close(); 
     } 
    }; 
    } 
}; 

IndexSearcher searcher = new IndexSearcher(filteredReader); 

Answer 8

对于那些在这个问题谁绊倒......

我刚刚发布了server-side autocomplete implementation在谷歌代码。该项目包括一个可以集成到现有应用程序中的Java库和一个独立的HTTP AJAX自动完成服务器。

我希望能让人们将高效的自动完成功能整合到他们的应用程序中。踢轮胎！

Answer 9

我用哈希表和mmap（） 和10,000,000+记录术语列表是没有问题的。 观看演示在这里：http://olegh.ath.cx/autocomplete.html

Answer 10

利用特里数据结构在这里是 http://en.wikipedia.org/wiki/Trie