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

我试图在我正在构build的网站上实现像Googlebuild议的内容,并且很好奇如何去处理一个非常大的数据集。 当然,如果你有1000个物品,你caching的项目,只是循环通过它们。 但是当你有一百万件物品时,你怎么去做呢? 此外,假设这些项目不是一个单词。 具体来说,我对Pandora.com印象深刻。 例如,如果您search“湿”,它带回“湿砂”,但它也带回蟾蜍湿链轮。 而他们的自动完成是FAST。 我的第一个想法是按照前两个字母对项目进行分组,所以您可能会有这样的内容:

Dictionary<string,List<string>> 

关键是前两个字母。 没关系,但是如果我想要做类似潘多拉的事情,并允许用户查看匹配string中间的结果呢? 与我的想法:湿将永远不会匹配蟾蜍湿链轮,因为它将在“到”桶而不是“我们”桶。 那么也许你可以把琴弦分开,“Toad the Wet Sprocket”进入“TO”,“WE”和“SP”桶(去掉“THE”这个词),但是当你说的是一百万每个可能有几个单词的条目,似乎你会很快开始使用大量的内存。 好吧,这是一个很长的问题。 思考?

正如我在“ 如何在列表中实现增量search”中指出的那样,应该使用像Trie或Patricia trie这样的结构来search大型文本中的模式。

而在一些文本中间发现模式有一个简单的解决scheme。 我不知道这是否是最有效的解决scheme,但我通常按如下方式进行。

当我向Trie插入一些新的文本时,我只是插入它,然后删除第一个字符,再次插入,删除第二个字符,再次插入…等等,直到整个文本被消耗。 然后,您可以通过从根目录search来发现每个插入文本的每个子string。 由此产生的结构被称为后缀树,并有很多可用的优化。

这真的太快了。 要查找包含n个字符的给定序列的所有文本,您必须检查至多n个节点,并对每个节点的子节点列表执行search。 根据子节点集合的实现(数组,列表,二叉树,跳过列表),您可以使用less至5个search步骤来识别所需的子节点,只要不区分大小写拉丁字母。 插值sorting可能对大字母和具有许多孩子的节点有帮助,这些孩子通常位于根部附近。

不要试图自己实现(除非你只是好奇)。 使用像Lucene或Endeca的东西 – 它会节省你的时间和头发。

不是algorithm上与你要求的相关,但要确保在kaypress()之后你有200ms或更多的延迟(滞后),所以你要确保用户在发出asynchronous请求之前已经停止了input。 这样你将减less多余的http请求到服务器。

我会沿着一个trie的行来使用一些东西,并且每个叶节点的值都是包含由叶节点表示的单词的可能性的列表。 你可以按照可能的顺序对它们进行sorting,或者根据用户在search框中input的其他词语来dynamic地对它们进行sorting/过滤等等。它将以非常快的速度和合理数量的RAM执行。

您将这些项目保留在服务器端(如果数据集非常大且复杂,可能在数据库中),并且从客户端浏览器发送AJAX调用,并使用json / xml返回结果。 您可以通过用户input或定时器来做到这一点。

如果你不想要一个trie,而你想要从string中间的东西,你通常想运行某种编辑距离函数(levenshtein距离),这将给你一个数字,表明两个string匹配。 这不是一个特别有效的algorithm,但是对于诸如单词之类的东西来说并不重要,因为它们相对较短。 如果您正在比较8000个字符的string,则可能需要几秒钟的时间。 我知道大多数语言有一个实现,或者你可以很容易地在互联网上find代码/伪代码。

我已经完全为这种情况构build了AutoCompleteAPI 。

注册以获取私人索引,然后上传您的文档。

在“New York”文件上使用curl进行上传的示例:

 curl -X PUT -H "Content-Type: application/json" -H "Authorization: [YourSecretKey]" -d '{ "key": "New York", "input": "New York" }' "http://suggest.autocompleteapi.com/[YourAccountKey]/[FieldName]" 

索引所有文档后,要获得自动填充build议,请使用:

 http://suggest.autocompleteapi.com/[YourAccountKey]/[FieldName]?prefix=new 

您可以使用任何客户端自动完成库将这些结果显示给用户。