python - 使用字符串作为 python 字典(内存管理)

Question

我需要在一组文本中找到相同的字符序列。将其视为寻找相同/剽窃的句子。天真的方法是这样的:

ht = defaultdict(int)
for s in sentences:
    ht[s]+=1

我通常使用 python，但我开始认为 python 不是完成此任务的最佳选择。我错了吗？有没有合理的方法用 python 做到这一点？

如果我理解正确的话，python 字典使用开放式寻址，这意味着键本身也保存在数组中。如果确实如此，则意味着 python 字典允许高效查找但在内存使用方面非常糟糕，因此如果我有数百万个句子，它们都会保存在字典中，这很糟糕，因为它超出了可用内存 - 制作python 字典是一个不切实际的解决方案。

有人可以批准前一段吗？

想到的一个解决方案是显式使用哈希函数(使用内置哈希函数，实现一个或使用 hashlib 模块)而不是插入 ht[s]+=1，插入:ht[哈希(s)]+=1

这样存储在数组中的键是一个 int(将再次被散列)而不是完整的句子。

那行得通吗？我应该期待碰撞吗？还有其他 Pythonic 解决方案吗？

谢谢!

Answer 1

1. 是的，字典将 key 存储在内存中。如果您的数据适合内存，这是最简单的方法。

2. 哈希应该有效。试试MD5。它是 16 字节 int，因此不太可能发生冲突。

3. 尝试使用 BerkeleyDB 基于磁盘的方法。