algorithm - 在一组单词中找到匹配的短语

Question

我创建了一个程序来解析一些文本文件并计算单词的数量，然后将它们降序排列。这很好用，但我想把它提升到另一个层次。

我希望能够找出文本中重复的任何词组，但我不确定该怎么做。

我目前的算法是首先将文本拆分成单词，然后用单词创建一个哈希表并像这样计算值:键

hash:
    "word":3,
    "test":12,
     .....

然后我只根据键和输出对 has 进行排序，我就完成了。

假设我有一首生日快乐歌:

Happy Birthday to You
Happy Birthday to You
Happy Birthday Dear (name)
Happy Birthday to You.

From good friends and true,
From old friends and new,
May good luck go with you,
And happiness too.

Alternative ending:
How old are you?
How old are you?
How old, How old
How old are you?

我可以很好地统计字数，但如果我想匹配所有短语怎么办？

例如这个 6 词的短语可以说匹配了两次:

happy birthday to you happy birthday

一对 5 词短语匹配:

birthday to you happy birthday
happy birthday to you happy

一些 4 个单词短语匹配

how old are you
happy birthday to you
to you happy birthday
how old how old
birthday to you happy

以此类推直到两个匹配的单词短语。

我更关心匹配整个短语，甚至是跨行匹配，因为无论如何我都必须查看输出以进行进一步处理。

什么类型的算法可以让我实现这个目标？

Answer 1

首先，您可能希望使用快速正则表达式对段落进行分词，以便更轻松地迭代单词，例如对所有空白/换行符使用您的语言的 String.split 方法。这应该为您留下一个字符串数组，如下所示:["Happy", "birthday", "to", "you", "happy", ...]。如果您稍后使用正则表达式，则不需要对字符串进行小写，我在此答案中建议这样做。

接下来，您需要从段落中提取短语，这可以通过创建一个 start 和 end 指针并像这样迭代来实现:

for (var start = 0; start < tokens.length; start+=1) {
    for (var end = start; end < tokens.length; end+=1) {
        var phrase = tokens.slice(start, end)
        // Count occurrences of phrase ...
    }
}

以上将使用每个单词作为提取的起点，并将每个后续单词作为提取的终点，这允许在 phrase 中提取单个单词和整个短语。请注意，有(如果我的数学是正确的)(n + n^2)/2 个这些短语，所以这个东西呈指数增长。如果您主动存储所有短语直到最后，对于大数据，内存使用量可能会非常大。

正则表达式匹配本身可以找到给定短语的出现次数，因此您不局限于使用哈希表来存储您的工作结果。您可以通过仅存储那些在文章中多次出现的短语来节省内存。