在html输入框中实现自动完成功能的服务器端组件的快速有效的方法是什么?
我正在编写一个在web界面的主搜索框中自动完成用户查询的服务,完成的内容显示在ajax支持的下拉列表中。我们正在运行查询的数据只是我们系统所知道的概念的一个大表,它与维基百科的页面标题集大致匹配。对于这项服务来说,速度显然是最重要的,因为网页的响应性对用户体验很重要。
当前的实现只是将所有概念加载到内存中的有序集合中,并对用户击键执行简单的log(n)查找。然后,尾集用于提供最接近匹配之外的其他匹配。这个解决方案的问题是它不能扩展。它目前遇到了VM堆空间限制(我已经设置了-Xmx2g,这是我们在32位机器上所能推送的最大值),这阻止了我们扩展概念表或添加更多功能。在内存更大的机器上切换到64位虚拟机并不是一个直接的选择。
我一直在犹豫是否开始研究基于磁盘的解决方案,因为我担心磁盘寻道时间会扼杀性能。有没有可能的解决方案可以让我更好地扩展,要么完全在内存中,要么通过一些快速的磁盘备份实现?
编辑:
@Gandalf:对于我们的用例来说,重要的是自动完成是全面的,而不仅仅是对用户的额外帮助。至于我们正在完成的内容,它是一个概念类型对的列表。例如,可能的条目是(“微软”,“软件公司”),(“杰夫·阿特伍德”,“程序员”),("StackOverflow.com",“网站”)。一旦用户从自动完成列表中选择一项,我们就使用Lucene进行完整搜索,但我还不确定Lucene是否能很好地用于自动完成本身。
@Glen:这里没有使用数据库。当我谈论表时,我只是指我的数据的结构化表示。
@Jason Day:我对这个问题的最初实现是使用Trie,但由于需要大量的对象引用,因此内存膨胀实际上比排序集更糟糕。我将阅读三元搜索树,看看它是否有用。
发布于 2009-06-09 16:31:15
对于这么大的集合,我会尝试像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
}
这里有一些伪代码,但这就是我们的想法。此外,如果设置了查询条件,则可以预先创建和优化Lucene索引。
发布于 2009-06-09 16:50:45
我也有类似的要求。
我使用具有单个索引良好的合成表的关系数据库(避免连接和视图以加快查找速度),并使用内存缓存(Ehcache)来存储最常用的条目。
通过使用MRU缓存,您将能够获得大多数查找的即时响应时间,并且在访问存储在磁盘上的大表中的索引列方面,可能没有什么比关系数据库更好了。
这是不能存储在客户端的大数据集的解决方案,而且它的工作速度非常快(在我的例子中,非缓存的查找总是在0.5秒内检索到)。它也是水平可扩展的--你可以随时添加额外的服务器和数据库服务器。
您还可以尝试只缓存客户端上最常用的结果,特别是如果您已经实现了它。在我的例子中,服务器端解决方案足够快,客户端加载时间也足够慢,所以没有必要这样做。
附注:只有当用户暂停一定时间以避免重复查找时,才使用客户端查询,这是一个很好的解决方案。在我的客户机上,我只在输入前三个字符之后查询数据库,因为在所有情况下,少于前三个字符都会返回太多的结果。
发布于 2009-06-11 22:29:05
我最终通过Lucene解决了这个问题;对于我们的用例,最初的性能测试似乎足够了。为了使前缀查询正常工作,需要进行一些黑客操作,因为我在扩展查询时遇到了TooManyClauses异常,比如"Jeff At*“。我最终用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);
https://stackoverflow.com/questions/971052
复制相似问题