如何在海量数据集上实现自动完成
我试图在我正在构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
您可以使用任何客户端自动完成库将这些结果显示给用户。
