RAM 高效的 10 亿短字符串集和快速查找

Question

我希望能够尽快测试给定字符串是否属于包含 10 亿个字符串的集合S：

每个字符串的平均长度为 10，因此整个数据约为 10 GB，最大长度为 100
99% 的字符串仅使用 a-z A-Z 0-9 + 一些特殊字符 (.!-;\/)，在极少数情况下还有其他字符
如有必要，可对数据进行排序：
```
aaaaa
...
helloworld
hellu
help
...
zzzzz
```
我们也许可以使用前缀树/特里树，但我不确定这是否是最佳解决方案。

问题：有没有一种方法可以使用 Python 处理内存压缩集，可能使用标准库，快速查找？

目标是尽快测试 'hello' in S。

我知道如何使用 10 GB 的 RAM 执行此操作，但出于好奇，我想知道这是否可能仅使用 1 或 2 GB 的 RAM:

S = set()
with open('db.txt', 'r') as f:
   for l in f:
       S.add(l)
print('hello' in S)

Answer 1

您应该能够压缩字符串并使用压缩版本。但是，您节省多少内存将取决于您的数据集的可压缩性。

我会建议一个自定义压缩系统：基于整个字符串语料库构建一个压缩字典，优化以最小化字典 + 压缩字符串存储的总大小。

我会使用散列 table 来查找压缩字符串，而不是树。每个哈希桶可以只是一堆压缩数据，从头开始按顺序扫描。对于恰好有很多长字符串的桶，提供一个指向其余数据的溢出指针； in-table 存储桶大小是一个性能参数——或者您可以将该大小一直滑动到 0 以获得完全间接的 table。

从性能的角度来看，顺序扫描听起来有问题，但初始哈希查找和顺序扫描在当前硬件上都很快。哈希桶的数量是（统计上）限制顺序扫描长度的；这是另一个性能参数。

为了在 Python 中实现这一点，我将手动进行散列索引，并将散列 table 存储为字节串数组。我认为这实际上是上面提到的间接 table，它可能不是尽可能快，但应该相当不错。

# Python-like pseudocode for building the table
compression_dict = compressor.train(strings)
hash_table = [BytesIO() for i in range(table_size)]
for s in strings:
    hash_table[hash(s) % table_size].write(compression_dict.compress(s))

Answer 2

没有

除非您没有告诉我们的数据中存在大量冗余，否则您可以预期将 10 GB 压缩到 6 或 7 GB，甚至排序。像您建议的数据结构会使它变得更大，而不是更小。

正如另一个答案中所建议的，您可以使用散列方法使其更快。但不会将存储空间减少五到十倍。

RAM 高效的 10 亿短字符串集和快速查找

RAM-efficient set of 1 billion of short strings, and fast lookup

python

memory

compression

set

trie