对半亿个字符串进行前缀搜索

Question

我有一个包含500百万个字符串的列表。这些字符串由ASCII字符组成，长度各不相同（通常在2-30个字符之间），并且它们是单词（或没有空格的多个单词的组合，例如'helloiamastring'）。

我需要快速检查目标字符串，例如“hi”，结果应该是从这500百万个字符串中以“hi”开头的所有字符串（例如'hithere'，'hihowareyou'等）。这个过程需要很快，因为每次用户输入时都会进行新的查询，所以如果他键入“hi”，将显示500百万个列表中所有以“hi”开头的字符串，如果他键入“hey”，则显示以“hey”开头的所有字符串等等。

我尝试了Tries算法，但是存储300百万个字符串的内存占用量非常巨大。需要超过100GB的内存。而且我相信这个列表将增长到十亿。

有没有适用于此用例的快速算法？

注：如果没有快速选项，则最好的替代方案是限制输入至少为4个字符，然后再显示结果。那么有没有一种快速检索结果的方法呢？

- anemaria20

---

为什么不使用数据库（如果您绝对想要将数据保存在内存中，Sqlite 可以在内存中运行）？ - xzoert

[Trie] 存储 3 亿个字符串的内存占用量非常巨大 [100GB+]。你是如何实现 Trie 的？使用了哪种语言/运行环境？现代语言通常支持 16 位 Unicode。（我支持 J. Coleman 的想法，即对前两个字符使用 O(1) 查找）。Stemming 可以减少常规字典的内存占用；但在你的情况下，我预计优势会更小。 - greybeard

@老程序员 这只是一个粗略的估计，但即使使用最有效率的算法，我猜也不会少于30GB。考虑到这些长字符串将会增长的问题性质，任何类型的内存结构都不是一个好主意（除非有一些我不知道的极其高效的前缀匹配算法）。 - anemaria20

我看到的最大障碍几乎与表示和搜索“字符串集”完全无关：你将如何“表示和使用结果”？即使有大小写区分，我们也在谈论几千个可能的二元组，平均约有100,000个命中，其中流行的命中（如辅音后跟元音）要高得多。 - greybeard

@老程序员 是的，但仍然是数亿人口并且还在增长，你懂的。 - anemaria20

Answer 1

如果字符串已排序，则可以采用二分搜索的方式。为了加速搜索，您可以维护一个所有可能的二元组（“aa”，“ab”等）的字典，其中相应的值是以该二元组开头的第一个和最后一个索引（如果有）。这样，就可以在O(1)时间内缩小包含要查找的字符串的子列表。一旦找到匹配项，请进行线性搜索以获取所有其他匹配项。

- John Coleman

---

这些字符串没有排序。考虑到列表每天都在变化，我不知道对 3 亿条记录进行排序是否是可行的解决方案。 - anemaria20

@anemaria20 我猜“内存中”排序/分类时间不是问题，重建以及更新也不是问题。 - greybeard

如果你追求速度，排序将大大改善你的情况。进行一次初始排序可能需要时间，但随着列表的增长，只需将物品插入到它们应该在的位置（假设你使用正确的数据结构），这应该是相当简单的。@anemaria20 - Jason Cemra

Answer 2

你需要一个有向无环词图或DAWG。这是对@graybeard建议使用词干处理的一般化。例如，可以参考this第3.2节中的讨论。

- JimD.

---

有没有任何编程语言中的库可以用于这个？ - anemaria20

有一个Python包实现了DAWG。如果这个包无法处理您的数据集大小，那么该包的作者声称marisa-trie适用于更大的数据集，尽管速度较慢。 - JimD.

我知道，如果Ruby也有相应的工具就太好了。我见过一个C#版本。 - anemaria20

Answer 3

如果你想强制用户至少输入4个字母，可以使用键值对映射、内存或磁盘来保留数据。其中，键是所有四个字母的组合（如果不区分大小写，则数量不会太多；否则可以限制为三个），值是以该组合开头的所有字符串的位置列表。

当用户输入了三（或四）个字母后，就可以得到所有可能的字符串。从这一点开始，您只需在此子集上循环即可。

平均而言，此子集足够小，例如500M除以26^4……实际上会更大，因为可能并非所有的四字母组合都是您字符串的前缀。

还有一点：当您向大列表中添加新字符串时，还要更新映射中相应键的索引列表。

- emilio

Answer 4

如果您不想使用某些数据库，您应该创建一些与所有数据库引擎预先存在的数据相关例程：

1. 不要尝试将所有数据加载到内存中。
2. 对于所有字符串使用固定长度。这会增加存储器消耗，但显著减少寻址时间（第i个字符串可以在文件中的L * i字节位置找到，其中L是固定长度）。创建额外的机制来处理极长的字符串：将其存储在不同的位置并使用特殊指针。
3. 对所有字符串进行排序。您可以使用归并排序来完成此操作，而无需一次性将所有字符串加载到内存中。
4. 创建索引（以“a”，“b”等开头的第一行的地址），也可以为2-gram、3-gram等创建索引。索引可以放置在内存中以增加搜索速度。
5. 使用高级策略避免在数据更新时进行完整的索引重建：通过首字母将数据拆分为多个文件，并仅更新受影响的索引，在数据中创建空白空间以减少读取-修改-写入过程的影响，在主存储之前为新行创建缓存并在此缓存中搜索。
6. 使用查询缓存快速处理常见请求。

- Stanislav Ivanov

Answer 5

在这个假设中，被索引的字符串没有与任何其他信息相关联（例如同一行中的其他列），完整索引和一开始就保持字符串排序之间的差异相对较小（有一些差异，但不如你所希望的那么大）。考虑到列表的不断增长和更新成本，也许采用相反的方法会更好地实现您寻求的性能权衡。

对于字符串中的任何给定位置上的任何字符，您的基本情况是不存在包含该字母的字符串。例如，一旦输入了“hello”，如果接下来输入的字母是“t”，那么您的基本情况就是没有以“hellot”开头的字符串。在位置5处，可能会跟随“hello”的字符数量是有限的（比如说26个）。您需要26个固定长度的空间来存储关于跟随位置5处的“hello”的字符的信息。每个空间要么为零，表示不存在一个字符串，在该字符串中，“t”跟随“hello”，要么包含一些数据存储地址，通过这些地址可以找到涉及该字符的一个或多个字符串的字符列表，这些字符串中的一个或多个字符跟随位置6的“hellot”（或使用绝对数据存储地址，尽管只有相对地址才能使我提出的算法支持无限数量的无限长度的字符串，而不需要修改以允许更大的指针随着列表的增长而增加）。

算法可以通过存储在磁盘上的数据向前移动，同时在内存中构建字符串开头的树，并避免由随机访问读取引起的延迟。对于内存索引，只需将最靠近根部的树部分存储在内存中。当用户键入“hello”并且算法已经跟踪到关于一个或多个以“hellot”开头的字符串存在于数据存储地址X时，算法会在位置X找到两种类型的列表之一。它要么是另一个序列，例如26个固定长度的空格，其中包含有关位于位置6处的“hellot”后面的字符的信息，要么是预先分配的空间块，列出了所有跟随“hellot”的后缀，具体取决于存在多少这样的后缀。一旦有足够的后缀，使用一些传统的搜索和/或排序算法来更新和搜索后缀列表无法提供所需的性能优势，它就会被分割并替换为一系列，例如26个固定长度的空格。

这涉及到预先分配相对大量的磁盘存储空间，以换取您的树可以在大多数更新时保持排序形式而无需移动任何内容，并且您的搜索可以在单个顺序读取中进行。 它还提供了更大的灵活性，可能需要比基于将字符串本身存储为固定长度字符串的解决方案少得多的存储空间。

- RichardB

Answer 6

首先，我应该说你应该为你的问题添加的标签是“信息检索”。

我认为使用Apache Lucene的PrefixQuery是处理通配符查询的最佳方法。如果你熟悉Python，那么Apache有一个Python版本。但是要使用Apache lucent解决你的问题，你首先需要了解索引你的数据（这部分是将你的数据压缩并以更有效的方式保存的部分）。

此外，查看IR书籍中的索引和通配符查询部分会给你更好的视野。

- Alikbar

---

这与以下链接是否类似：https://www.elastic.co/guide/en/elasticsearch/guide/current/_query_time_search_as_you_type.html - anemaria20

Elasticsearch和Apache Solr是基于Apache Lucene的搜索引擎。 - Alikbar