search - 查找大文本中重复次数最多的短语

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

我建议结合两个领域的想法，在这里:Streaming Algorithms ，以及 Apriori Algorithm From Market-Basket Analysis .

1. 让我们首先解决在不将整个语料库加载到内存的情况下查找 k 个最常见的单个单词的问题。一个非常简单的算法，采样(参见Finding Frequent Items in Data Streams])，可以很容易地做到这一点。此外，它非常适合并行实现(如下所述)。关于 top-k 查询有大量的工作，包括一些关于分布式版本的工作(例如，参见 Efficient Top-K Query Calculation in Distributed Networks )。

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

<小时/>

采样算法的简短描述

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

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

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

输出第二阶段产生的前k个项目。

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