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

Question

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

我希望能够找出文本中重复的词组，但我不确定如何去做。

我目前的算法是首先将文本拆分成单词，然后用单词创建哈希 [=40=] 并像这样计数 value:key

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

您可以对单词组合使用相同的算法。如果您使用最大大小为 n 的队列，您可以连接检查的最后 n 个单词（例如通过迭代器）并将它们添加到您的哈希表中。对 n=2 重复此操作，直到 n > ( your #words / 2 ) 或未找到重复项

例子 “W1 w2 w3， W3 w1 w2.“

应该给出一个散列表... 哈希2： “w1 w2“：2 “w2 w3“：1 “w3 w3“：1 “w3 w1“：1 ..for n=2（忽略大写字母和逗号）对于 n=3，您的最高计数为 1，您可以打破

清理单词列表中的换行符并在可能需要连接时使用额外的空格

Answer 2

首先，您可能希望使用快速正则表达式对段落进行标记，以便更轻松地迭代单词，例如对所有 whitespace/newline 个字符使用您的语言的 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 个这些短语，所以这个东西呈指数增长。如果您主动将所有短语存储到最后，对于大数据，内存使用量可能会非常大。

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

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

Find matching phrases in a group of words

algorithm

word-frequency