8

我正在考虑编写一个程序来为我收集大量文本中最常见的短语。如果将问题简化为仅查找单词，那么就像将每个新单词存储在哈希图中然后增加每次出现的计数一样简单。但是对于短语，将句子的每个排列存储为键似乎是不可行的。

基本上，问题被缩小到弄清楚如何从足够大的文本中提取每个可能的短语。计算短语然后按出现次数排序变得微不足道。

4

1 回答 1

9

我假设您正在搜索以相同顺序出现的连续单词的常见模式（例如，“世界之巅”不会被视为与“世界之巅”或“世界之巅”相同的短语）。

如果是这样，那么我会推荐以下线性时间方法：

  1. 将您的文本拆分为单词并删除您认为不重要的内容（即删除大写、标点、断字等）
  2. 将您的文本转换为整数数组（每个唯一单词一个整数）（例如，“cat”的每个实例变为 1，每个“dog”变为 2）这可以通过使用基于散列的字典来存储从单词到数字的转换。如果该词不在字典中，则分配一个新的 id。
  3. 为整数数组构造一个后缀数组（这是数组所有后缀的排序列表，可以按线性时间构造 - 例如使用算法和 C 代码here）
  4. 为您的后缀数组构造最长的公共前缀数组。（这也可以在线性时间内完成，例如使用这个C 代码）这个 LCP 数组给出了后缀数组中连续对之间每个后缀开头的常用词的数量。

您现在可以收集常用短语了。

目前还不太清楚您希望如何确定短语的结尾。一种可能性是简单地收集所有重复的 4 个单词的序列。
这可以通过查看最长公共前缀数组 >= 4 的位置的后缀数组来在线性时间内完成。索引 x 在 [start+1...start+len] 范围内的每次运行，其中 LCP[ x] >= 4（除 x 的最后一个值之外的所有值）对应于重复 len 次的短语。短语本身由前 4 个单词给出，例如后缀 start+1。

请注意，这种方法可能会发现跨句子结尾的短语。您可能更愿意将一些标点符号（例如句号）转换为唯一的整数来防止这种情况。

于 2013-10-27T19:55:04.943 回答