在巨大的文字上找到最重复的短语

Question

我有大量的文本数据.我的整个数据库都是UTF-8的文本格式

我需要在我的整个文本数据上列出最重复的短语.

例如,我的愿望输出如下:

{
  'a': 423412341,
  'this': 423412341,
  'is': 322472341,
  'this is': 222472341,
  'this is a': 122472341,
  'this is a my': 5235634
}

处理和存储每个短语占用巨大的数据库.例如存储在MySQL或MongoDB中.问题是有没有更有效的数据库或算法来找到这个结果？Solr,Elasticsearch等......

我想我每个短语最多10个单词对我有好处.

Answer 1

我建议结合两个领域的想法：流算法和来自市场篮子分析的 Apriori 算法。

1. 让我们从在不将整个语料库加载到内存的情况下找到k 个最常见的单个单词的问题开始。一个非常简单的算法，即采样（请参阅在数据流中查找频繁项），可以非常轻松地做到这一点。此外，它非常适合并行实现（如下所述）。关于 top-k 查询有大量的工作，包括一些关于分布式版本的工作（例如，参见分布式网络中的高效 Top-K 查询计算）。

2. 现在讨论k 个最常见短语（可能有多个短语）的问题。显然，长度为l + 1的最频繁的短语必须包含长度为l的最频繁的短语作为前缀，因为向短语添加单词并不能增加其流行度。因此，一旦你有了k 个最频繁的单个单词，你就可以只扫描语料库（这更快）来构建长度为 2 的最频繁的短语。使用它，你可以构建长度为 3 的最频繁的短语，并且很快。停止条件是长度为l + 1的短语不驱逐任何长度为l的短语。

采样算法的简短描述

这是一个非常简单的算法，它将以高概率从频率至少为f的项目中找到前k个项目个项目。它分两个阶段运行：第一个阶段查找候选元素，第二个阶段对它们进行计数。

在第一阶段，从语料库中随机选择~ log(n) / f 个单词（注意，这远小于n）。您想要的所有单词很有可能出现在这些单词的集合中。

在第二阶段，维护这些候选元素的计数的字典；扫描语料库并计算出现次数。

输出前k个个项目。

请注意，第二阶段非常适合并行实施。如果将文本分成不同的段，并计算每个段中的出现次数，则可以轻松地在最后合并词典。