在大文本中查找重复次数最多的短语
Find most repeated phrase on huge text
我有大量的文本数据。我的整个数据库都是 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 个单词对我来说是好的。
我建议结合两个领域的想法，在这里：Streaming Algorithms, and the Apriori Algorithm From Market-Basket Analysis。
让我们从寻找 k 个最频繁出现的单词开始，而不用将整个语料库加载到内存中。一个很简单的算法，Sampling（见Finding Frequent Items in Data Streams]), can do so very easily. Moreover, it is very amenable to parallel implementation (described below). There is a plethora of work on top-k queries, including some on distributed versions (see, e.g., Efficient Top-K Query Calculation in Distributed Networks）。
现在讨论 k 个最常见的短语（可能是多个短语）的问题。显然，长度为 l + 1 的最频繁短语必须包含长度为 l 的最频繁短语作为前缀，就像将单词附加到短语不能增加其流行度。因此，一旦你有了 k 个最常见的单词，你就可以只扫描语料库中的它们（这样更快）来构建长度为 2 的最常见的短语。使用这个，你可以构建长度为 3 的最频繁的短语，依此类推。停止条件是当长度为 l + 1 的短语不驱逐任何长度为 l.
[=50= 的短语时]
采样算法的简短描述
这是一个非常简单的算法，它将很有可能从频率至少为 f[=48= 的项目中找到前 k 个项目].它分两个阶段运行：第一个阶段找到候选元素，第二个阶段计算它们。
第一阶段，从语料库中随机select ~log(n) / f个词（注意这比少很多n).很有可能，所有你想要的词都出现在这些词的集合中。
第二阶段，维护这些候选元素的计数字典；扫描语料库，统计出现次数。
输出第二阶段产生的前 k 项。
请注意，第二阶段非常适合并行实施。如果将文本分成不同的段，并计算每个段中出现的次数，则可以轻松地在最后合并字典。
这可以大大简化。你根本不需要数据库。只需将全文存储在一个文件中。然后写一个PHP脚本打开并读取文件内容。使用 PHP 正则表达式函数提取匹配项。将总数保存在全局变量中。将结果写入另一个文件。而已。
如果可以将数据存储在 Apache Solr, then the Luke Request Handler 中，可以用来找到最常见的短语。示例查询：
http://127.0.0.1:8983/solr/admin/luke?fl=fulltext&numTerms=100
此外，Terms Component may help find the most common individual words. Here is an article about Self Updating Solr Stopwords 使用术语组件查找 100 个最常见的索引词并将它们添加到停用词文件。示例查询：
http://127.0.0.1:8983/solr/terms?terms.fl=fulltext&terms.limit=100
您是否考虑过使用 MapReduce？
假设您可以访问适当的基础架构，这似乎非常适合它。您将需要一个分词器，它可以将行拆分为最多 10 个单词的多词标记。我认为这没什么大不了的。 MR 作业的结果将是 token -> frequency 对，您可以将其传递给另一个作业以按频率对它们进行排序（一个选项）。我建议在考虑其他解决方案之前阅读 Hadoop/MapReduce。您还可以使用 HBase 来存储任何中间输出。
MapReduce 上的原始 paper Google。
将其标记为 1 到 10 个单词 并按标记长度插入 10 SQL tables。确保在带有字符串标记的列上使用散列索引。然后只需在每个 table 上调用 SELECT token,COUNT(*) FROM tablename GROUP BY token 并将结果转储到某处并等待。
编辑：这对于大型数据集是不可行的，只是对于每个 N-gram 将计数更新 +1 或将新行插入 table（在 MYSQL 中将是有用的查询 INSERT...ON DUPLICATE KEY UPDATE).不过，您绝对应该仍然使用哈希索引。
之后只需按出现次数排序并合并来自这 10 table 的数据（您可以一步完成，但这会给内存带来更多压力）。
警惕像 Ami Tavory 建议的启发式方法，如果你 select 错误的参数，你可能会得到错误的结果（采样算法的缺陷可以在一些经典术语或短语中看到 - 例如 "habeas corpus" - 人身保护令和语料库本身都不会 select 被频繁编辑，但作为一个 2 个单词的短语，它的排名很可能比你通过 appending/prepending 得到的一些短语更高。肯定没有必要将它们用于更短长度的标记，只有在经典方法失败时（占用太多时间或内存）才可以使用它们。
Amy Tavori 的最佳答案是：
Clearly, the most frequent phrases of length l + 1 must contain the most frequent phrases of length l as a prefix, as appending a word to a phrase cannot increase its popularity.
虽然将单词附加到短语确实不能增加其流行度，但没有理由假设 2-gram 的频率受 1-gram 频率的限制。为了说明这一点，请考虑以下语料库（专门为说明这一点而构建）：
Here, a tricksy corpus will exist; a very strange, a sometimes cryptic corpus will dumbfound you maybe, perhaps a bit; in particular since my tricksy corpus will not match the pattern you expect from it; nor will it look like a fish, a boat, a sunflower, or a very handsome kitten. The tricksy corpus will surprise a user named Ami Tavory; this tricksy corpus will be fun to follow a year or a month or a minute from now.
查看最频繁出现的单词，我们得到：
1-Gram Frequency
------ ---------
a 12
will 6
corpus 5
tricksy 4
or 3
from 2
it 2
the 2
very 2
you 2
Ami Tavori 建议的方法将识别前 1-gram，'a'，并将搜索范围缩小到带有前缀 'a' 的 2-gram。但是查看之前的语料库，前 2-grams 是：
2-Gram Frequency
------ ---------
corpus will 5
tricksy corpus 4
or a 3
a very 2
然后继续进行 3-gram，整个语料库中只有一个重复的 3-gram，即：
3-Gram Frequency
------ ---------
tricksy corpus will 4
概括地说：您不能使用最高的 m-grams 直接外推到最高的 (m+1)-grams。您可以做的是扔掉最底层的 m-gram，特别是那些根本不重复的，然后查看所有重复的 m-gram。这会稍微缩小范围。
我有大量的文本数据。我的整个数据库都是 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 个单词对我来说是好的。
我建议结合两个领域的想法，在这里：Streaming Algorithms, and the Apriori Algorithm From Market-Basket Analysis。
让我们从寻找 k 个最频繁出现的单词开始，而不用将整个语料库加载到内存中。一个很简单的算法，Sampling（见Finding Frequent Items in Data Streams]), can do so very easily. Moreover, it is very amenable to parallel implementation (described below). There is a plethora of work on top-k queries, including some on distributed versions (see, e.g., Efficient Top-K Query Calculation in Distributed Networks）。
现在讨论 k 个最常见的短语（可能是多个短语）的问题。显然，长度为 l + 1 的最频繁短语必须包含长度为 l 的最频繁短语作为前缀，就像将单词附加到短语不能增加其流行度。因此，一旦你有了 k 个最常见的单词，你就可以只扫描语料库中的它们（这样更快）来构建长度为 2 的最常见的短语。使用这个，你可以构建长度为 3 的最频繁的短语，依此类推。停止条件是当长度为 l + 1 的短语不驱逐任何长度为 l.
[=50= 的短语时]
采样算法的简短描述
这是一个非常简单的算法，它将很有可能从频率至少为 f[=48= 的项目中找到前 k 个项目].它分两个阶段运行：第一个阶段找到候选元素，第二个阶段计算它们。
第一阶段，从语料库中随机select ~log(n) / f个词（注意这比少很多n).很有可能，所有你想要的词都出现在这些词的集合中。
第二阶段，维护这些候选元素的计数字典；扫描语料库，统计出现次数。
输出第二阶段产生的前 k 项。
请注意，第二阶段非常适合并行实施。如果将文本分成不同的段，并计算每个段中出现的次数，则可以轻松地在最后合并字典。
这可以大大简化。你根本不需要数据库。只需将全文存储在一个文件中。然后写一个PHP脚本打开并读取文件内容。使用 PHP 正则表达式函数提取匹配项。将总数保存在全局变量中。将结果写入另一个文件。而已。
如果可以将数据存储在 Apache Solr, then the Luke Request Handler 中，可以用来找到最常见的短语。示例查询：
http://127.0.0.1:8983/solr/admin/luke?fl=fulltext&numTerms=100
此外，Terms Component may help find the most common individual words. Here is an article about Self Updating Solr Stopwords 使用术语组件查找 100 个最常见的索引词并将它们添加到停用词文件。示例查询：
http://127.0.0.1:8983/solr/terms?terms.fl=fulltext&terms.limit=100
您是否考虑过使用 MapReduce？
假设您可以访问适当的基础架构，这似乎非常适合它。您将需要一个分词器，它可以将行拆分为最多 10 个单词的多词标记。我认为这没什么大不了的。 MR 作业的结果将是 token -> frequency 对，您可以将其传递给另一个作业以按频率对它们进行排序（一个选项）。我建议在考虑其他解决方案之前阅读 Hadoop/MapReduce。您还可以使用 HBase 来存储任何中间输出。
MapReduce 上的原始 paper Google。
将其标记为 1 到 10 个单词 并按标记长度插入 10 SQL tables。确保在带有字符串标记的列上使用散列索引。然后只需在每个 table 上调用 SELECT token,COUNT(*) FROM tablename GROUP BY token 并将结果转储到某处并等待。
编辑：这对于大型数据集是不可行的，只是对于每个 N-gram 将计数更新 +1 或将新行插入 table（在 MYSQL 中将是有用的查询 INSERT...ON DUPLICATE KEY UPDATE).不过，您绝对应该仍然使用哈希索引。
之后只需按出现次数排序并合并来自这 10 table 的数据（您可以一步完成，但这会给内存带来更多压力）。
警惕像 Ami Tavory 建议的启发式方法，如果你 select 错误的参数，你可能会得到错误的结果（采样算法的缺陷可以在一些经典术语或短语中看到 - 例如 "habeas corpus" - 人身保护令和语料库本身都不会 select 被频繁编辑，但作为一个 2 个单词的短语，它的排名很可能比你通过 appending/prepending 得到的一些短语更高。肯定没有必要将它们用于更短长度的标记，只有在经典方法失败时（占用太多时间或内存）才可以使用它们。
Amy Tavori 的最佳答案是：
Clearly, the most frequent phrases of length l + 1 must contain the most frequent phrases of length l as a prefix, as appending a word to a phrase cannot increase its popularity.
虽然将单词附加到短语确实不能增加其流行度，但没有理由假设 2-gram 的频率受 1-gram 频率的限制。为了说明这一点，请考虑以下语料库（专门为说明这一点而构建）：
Here, a tricksy corpus will exist; a very strange, a sometimes cryptic corpus will dumbfound you maybe, perhaps a bit; in particular since my tricksy corpus will not match the pattern you expect from it; nor will it look like a fish, a boat, a sunflower, or a very handsome kitten. The tricksy corpus will surprise a user named Ami Tavory; this tricksy corpus will be fun to follow a year or a month or a minute from now.
查看最频繁出现的单词，我们得到：
1-Gram Frequency
------ ---------
a 12
will 6
corpus 5
tricksy 4
or 3
from 2
it 2
the 2
very 2
you 2
Ami Tavori 建议的方法将识别前 1-gram，'a'，并将搜索范围缩小到带有前缀 'a' 的 2-gram。但是查看之前的语料库，前 2-grams 是：
2-Gram Frequency
------ ---------
corpus will 5
tricksy corpus 4
or a 3
a very 2
然后继续进行 3-gram，整个语料库中只有一个重复的 3-gram，即：
3-Gram Frequency
------ ---------
tricksy corpus will 4
概括地说：您不能使用最高的 m-grams 直接外推到最高的 (m+1)-grams。您可以做的是扔掉最底层的 m-gram，特别是那些根本不重复的，然后查看所有重复的 m-gram。这会稍微缩小范围。