高效算法,可在大量文本中查找最常用的短语

Question

我正在考虑编写一个程序来收集大量文本中最常用的短语.如果问题被简化为仅仅找到单词而不是将每个新单词存储在散列映射中然后在每次出现时增加计数那么简单.但是对于短语,将句子的每个排列存储为关键似乎是不可行的.

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

Answer 1

我假设您正在搜索以相同顺序出现的连续单词的常见模式(例如,"世界之巅"不会被视为与"世界之巅"或"顶级世界"相同的短语).

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

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

您现在可以收集常用短语.

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

请注意,这种方法可能会发现跨越句子结尾的短语.您可能更喜欢将一些标点符号(例如句号)转换为唯一的整数以防止这种情况发生.