针对5亿个字符串的前缀搜索

Question

我有一张500密耳线的清单。字符串是字母数字、ASCII字符，大小不一（通常为2-30个字符）。而且，它们是单个单词（或者没有空格的单词组合，比如'helloiamastring'）。在

我需要的是一个快速的方法来检查目标，说“嗨”。结果应该是500mil列表中以“hi”开头的所有字符串（例如“heree”、“hihowareyou”等）。这需要很快，因为每次用户输入内容时都会有一个新的查询，所以如果他输入“hi”，500密耳列表中所有以“hi”开头的字符串都会显示出来，如果他键入“hey”，所有以“hey”开头的字符串都会显示出来，以此类推

我尝试过使用Tries算法，但是存储300 mil字符串的内存占用非常大。它应该需要我的100GB+内存。我很肯定这个名单会增长到10亿。在

这个用例的快速算法是什么？在

注：如果没有快速选项，最好的选择是在结果显示之前限制人们输入至少4个字符。有没有一种快速检索结果的方法？在

Answer 1

例如，如果您想强制用户使用至少4个字母的数字，您可以保留一个键值映射、内存或磁盘，其中的键都是4个字母的组合（如果不区分大小写，则不太多，否则可以限制为3个），值是以组合开头的所有字符串的位置列表。在

在用户键入三个（或四个）字母后，您将立即获得所有可能的字符串。从这一点开始，你就在这个子集上循环。在

平均来说，这个子集足够小，即500米除以26^4…就像例子一样。实际上更大，因为可能不是所有的4个字母都可以作为字符串的前缀。在

忘了说：当您向大列表添加一个新字符串时，您还更新了与映射中的键对应的索引列表。在

Answer 2

如果字符串被排序，那么二进制搜索是合理的。作为一个加速，您可以维护一个包含所有可能的双元组（“aa”、“ab”等）的字典，其中对应的值是第一个和最后一个索引，以该bigram（如果有的话）开始，在O(1)时间零点进入一个小得多的子列表，该子列表包含您要查找的字符串。找到匹配项后，对左右两侧进行线性搜索，以获得所有其他匹配项。在

Answer 3

你想要一个Directed Acyclic Word Graph或DAWG。这概括了@greybeard使用词干分析的建议。在

例如，请参见this第3.2节中的讨论。在