如何在一个大的文本组中计算每一个二字组出现的次数

Question

我有大量的文本，包括维基百科的文章，新闻文章等。大约15亿字的总数，约300万个独特的字。你知道吗

我想做的是决定什么时候把连续的单词作为一个单词来计算，例如“橙汁”应该作为一个单词来处理。为了决定一对单词是否应该被视为一个单词，我需要知道二元结构出现了多少次，以及二元结构中每个单词出现了多少次。 bigramCount/(word1Count*word2Count) > threshold 问题是，一个包含我的文本的所有bigram计数的变量将占用比我的计算机ram大小更多的内存。你知道吗

我试着做的是：

1. Count single words
2. For every single word:
    1. Count every ocurrence of a bigram that starts with that word
    2. Decide, applying the formula, which of those bigrams should be treated as a single word.

这样的话，它的内存更容易，但它需要太长的时间去做。 我目前正在做，但它已经运行了至少一天了，所以我正在努力想出一个更好的方法来做到这一点。你知道吗

你知道吗？你知道吗

Answer 1

将数据分成大小均匀的100-200个MiB块。运行你的算法。在一个文件（1.csv）中存储前85%（最常见的组合）的bigram。按第一个单词对文件排序。你知道吗

重复不同的文件（2，3，4…），直到没有更多的数据。你知道吗

将文件1和2的相关（合并相同的值计数）放入一个新的CSV文件1a中。 将文件3和4关联到新的CSV文件2a中。 对其余的文件重复上述步骤。 如果有奇数个文件，则将最后一个文件与随机文件关联（1..n） 然后关联1a，2a。。文件夹。你知道吗

继续，直到有一个包含结果的文件。你知道吗

此过程表示一个二叉树解决方案。就运行时间而言，它是最优的解决方案，但它引入了空间偏差。在所有样品中，成对出现的频率越近或间隔越均匀，最终产品的重量就越大。你知道吗

最完整的解决方案是将所有级别的扩展完全聚合起来。例如，（比较1和3=>；1b，1和4=>；1c。。。2和1=>；2b，2和3=>；2c，2和4=>；2d。。。然后在下一步中结合1a和1b…，2a和2b。。。这是指数解（慢）。你知道吗

为了平衡性能和降低复杂性并减少偏差，您可以在较低级别上随机配对：

例如：随机化的顺序，因为他们是在每个层次上分析的块。确保算法每次只输出一对。你知道吗

如果将树底部的选择随机化多次（约为上述完全展开的1/2），同时从所有以前的迭代中消除重复对，则在上述层中得到的精度将大大提高。你知道吗

如果你在第二和第三个层次上重复这种随机化（如果完全分析仍然不可能）超过第三个层次，由于收益递减规律，显著的绩效提升是不可能的。你知道吗

我建议使用预先构建的bigram数据库，或者至少在顶层限制bigram候选者为（名词|形容词，名词）。否则，您可能会得到最常用的名词/动词组合（在大多数其他现代美式英语数据集中，将是“我是”或“我有”）。你知道吗

Answer 2

而不是试图把它都留在内存中，这样做在多个过程。你知道吗

首先，创建两个文件，一个用于单个单词，另一个用于bigrams。你知道吗

现在，按顺序看完你的课文。阅读每个单词时，将其输出到单个单词文件。将它与前面的单词组合起来，并将这对单词写入bigrams文件。例如，给定一句话“重点是没有意义，使整个对话毫无意义”，那么单字文件每行将包含一个字。bigrams文件将包含：

the point
point is
is that
that there
there is
...

现在，使用操作系统提供的排序实用程序，对每个文件进行排序。把相同的词组合在一起。你知道吗

然后，编写一个程序，逐行读取文件，计算相同的行数。当您得到每个单词的总数时，编写一个包含word,count的相应文件。如果你有：

apple
apple
banana
cherry
cherry
cherry

那么您的输出将是：

apple,2
banana,1
cherry,3

对bigrams文件执行相同的操作。你知道吗

最后，将单个单词文件加载到地图或字典中，按单词索引，值为计数。三百万个独特的单词应该合适。如果没有，你可以把它们放进数据库。像SQLite这样的东西会非常有效。你知道吗

然后开始读取bigrams文件。每一行都包含二元图及其计数。您可以进行计算并做出决定，然后您是否要将它作为一个单词来处理，或者您可以将带有计数和分数的二元图输出到一个单独的文件中，然后再做出决定。你知道吗

您可以通过在内存中保留一些内容来减小第一次创建的中间文件的大小。与其将每个单词和bigram立即写入中间文件，不如在内存中保留两个字典，并限制它们的大小。当字典满了，把单词和计数写进磁盘，然后清空字典。这样，文件中就不会有成千上万个“the”字，而只会有少数几个“the，100000”条目。你知道吗

减小中间文件的大小将提高排序速度。在第二步中，删除重复项时，要为每个条目添加计数，而不是只为每个条目添加一个计数。你知道吗

在多个过程中这样做会使事情变得更容易，因为它减少了所需的内存，而且每一步都非常简单。当然，它没有单一程序解决方案那么快。但如果这是一件不常发生的事情，那么谁会在乎它是否需要一点额外的时间呢？你知道吗

另一个好处是该解决方案具有很强的可扩展性。我在笔记本电脑（8gb内存）上也做过类似的事情，在下载整个英文维基百科的时候做单词和双字符统计。花了一段时间（几个小时），但效果很好。你知道吗