Python 中的概率计数

Question

我有一个50gb的随机字符串txt文件，想要计算在这个文件中某个子字符串出现的次数......多次，对于不同的未预定义的随机子字符串。我在想是否还有其他方法来解决这个问题。 概率方法 类似布隆过滤器的东西，但是不是用于概率成员检查，而是用于概率计数。这种数据结构将用于计数估计。 其他统计方法（？） 有没有可以用来估计文本文件中字符串出现次数的简单方法？欢迎尝试其他方法。

如果能够在＜=对数时间内完成该任务将会很好。

- RetroCode

---

@jonrsharpe，你说得没错，但我忘了补充一点，我没有50GB的内存。 - RetroCode

一个计数器不会占用50GB的空间，而且你不需要一次性将整个文件保存在内存中。你可以逐步读取。完全可以对每个字符进行计数。 - Carcigenicate

你为什么认为需要50GB的内存？文件的大小根本不重要，重要的是不同单词的数量，如果先应用词干处理，那么可能只有几千个不同的单词。 - tobias_k

嗯，我假设你说的是“文字”是因为你提到了“文本文件”，但如果实际上是50GB的连续基因组序列之类的数据，那么你应该在问题中明确说明。 - tobias_k

即使是连续的数据，你仍然可以分块或惰性地读取它。 - Carcigenicate

Answer 1

一些流算法听起来与这个问题相关，可以单独使用或结合使用。

1. 对文件进行初始处理可以近似得到重要数据项。根据您的问题，可能仅需要重要数据项的分布情况就足够了，而这个集合又足够小，可以保存在内存中。如果是这种情况，您可以进行第二次处理，仅计算第一次处理中的重要数据项。

2. 计数最小化草图数据结构可以进行近似计数。您可以单独使用此数据结构，也可以用它来计算重要数据项的出现次数。

由于标记为Python:

• StreamLib（流式处理库）

• PyPI上的count-min-sketch库

- Ami Tavory

Answer 2

你可以为文件计算后缀数组。

该数组按排序顺序包含后缀的起始位置。对于50GB的文本，您可以分配每个位置5个字节，最终得到一个250 GBytes的后缀数组。如果太大，那么您可以尝试压缩后缀数组。

计算此数组可以在O(n)时间内完成（使用适当的算法可能需要几个小时，主要受限于磁盘读/写速度）。

一旦您有了数组，就可以以对数时间计算任何子字符串的出现次数。实际上，时间会被磁盘不同部分的搜索时间所主导，因此如果您将文件存储在固态硬盘上，则这部分速度会快得多。

- Peter de Rivaz