如何在海量数据集上实现自动完成

我正在尝试在我正在建立的网站上实施Google建议的内容,并且很好奇如何在非常大的数据集上进行操作.当然,如果您有1000个项目,则缓存项目并循环浏览它们.但是当你有一百万件商品时,你怎么做呢？此外,假设项目不是一个单词.具体来说,我对Pandora.com印象非常深刻.例如,如果您搜索"湿",它会带回"湿沙",但它也会带回Toad The Wet Sprocket.他们的自动完成功能很快.我的第一个想法是按前两个字母对项目进行分组,所以你会有类似的东西:

Dictionary>

其中键是前两个字母.那没关系,但是如果我想做类似Pandora的事情并允许用户看到与字符串中间匹配的结果呢？根据我的想法:Wet永远不会匹配Toad the Wet Sprocket,因为它将在"TO"桶而不是"WE"桶中.那么也许你可以把弦分开,"Toad the Wet Sprocket"进入"TO","WE"和"SP"桶(去掉"THE"这个词),但当你谈到一百万可能不得不说几句话的条目,似乎你很快就开始耗费大量的记忆.好的,这是一个很长的问题.思考？

1> Daniel Brück..：

---

正如我在如何在列表上实现增量搜索所指出的那样,你应该使用像Trie或Patricia trie这样的结构来搜索大文本中的模式.

而对于在某些文本中间发现模式,有一个简单的解决方案.我不确定它是否是最有效的解决方案,但我通常按如下方式进行.

当我在Trie中插入一些新文本时,我只是插入它,然后删除第一个字符,再次插入,删除第二个字符,再次插入......依此类推,直到整个文本被消耗.然后,您只需从根中搜索一次,即可发现每个插入文本的每个子字符串.生成的结构称为后缀树,并且有许多可用的优化.

这真是令人难以置信的快速.要查找包含给定n个字符序列的所有文本,您必须检查最多n个节点,并对每个节点的子列表执行搜索.根据子节点集合的实现(数组,列表,二叉树,跳过列表),您可能能够识别所需的子节点,只需5个搜索步骤,仅假设不区分大小写的拉丁字母.插值排序可能对大型字母表和具有许多子节点的节点有用,因为这些子节点通常位于根目录附近.

---

Trie非常适合在字符串的开头找到匹配项.但是,使用我当前的数据集,删除第一个字符然后插入的过程并没有最终工作得很好,只是开始使用太多的内存:> 1 gig之前用数据集完成了一半.

2> Jim Arnold..：

---

不要试图自己实现这个(除非你只是好奇).使用像Lucene或Endeca这样的东西 - 它可以节省你的时间和头发.

3> cherouvim..：

---

在算法上与您要查询的内容无关，但请确保在kaypress之后有200毫秒或更长时间的延迟（滞后），以确保在发出异步请求之前用户已停止键入。这样，您将减少对服务器的多余http请求。