在大量句子中查找n元频率

Question

我有一组文本消息，我们称之为 m1，m2，....。最大消息数量不超过1,000,000。每个消息的长度都不超过1024个字符，并且全部小写。我们还选择了一个n-gram s1。

我需要找到所有可能子字符串在所有这些消息中出现的频率。例如，假设我们只有两条消息：

m1 = a cat in a cage
m2 = a bird in a cage

这两条信息中某些n-gram的频率：

'a' = 4
'in a cage' = 2
'a bird' = 1
'a cat' = 1
...

请注意，由于 in = 2、in a = 2 和 a cage = 2 是 in a cage = 2 的子集，并且具有相同的频率，因此不应列出它们。只需取最长的具有最高频率的一个；遵循以下条件：最长的 sn-gram 应由至多 8 个单词组成，字符总数不超过 30。如果 n-gram 超出此限制，则可以将其分为两个或多个 n-gram 并分别列出。

我需要找到所有这些文本消息的这种 n-grams，并按其出现次数降序排序。

我该如何解决这个问题？我需要用 JavaScript 编写解决方案。

引用： PS：我需要帮助，但不知道去哪里寻求帮助。如果这个问题不适合这个网站，那么我应该在哪里发布？请指导一下这个新手。

- Jason

---

基本上在SO上，你应该寻求帮助来解决你的代码问题。但出于好奇，让我问一下..你需要完成这个任务的目的是什么？ - Redu

嗨。我完全没有任何代码。我甚至不知道从哪里开始。我需要从一系列消息中找到最常用的句子部分。这是我正在开发的文本分析程序所需的。 - Jason

你可能想先在网上搜索一下：维基百科和其他一些资源可以从概念到“这是实际可用的代码”解释“拓扑排序”，这些资源是我从谷歌搜索该术语的前20个结果中得到的。你可能还想搜索其他人如何使用略有不同的术语来实现它：在文本搜索中，你要寻找“n-gram频率计数”，因为n-gram是文本中的单词，而子字符串是字符串中的字母。这应该能让你找到很多提示和实现方法。 - Mike 'Pomax' Kamermans

一个问题是，“为什么要自己实现？”如果这不是一项作业练习。如果您正在处理的是真实的事情，请安装全文索引器，如Elastic Search，并使用它来为您完成工作？（或者，设置数据库以构建ngram索引，然后查看它已经跟踪的频率信息？） - Mike 'Pomax' Kamermans

你可以使用后缀自动机来解决这个问题。请查看此链接以了解更多信息：https://cp-algorithms.com/string/suffix-automaton.html - Dipu

Answer 1

也许你可以采取以下方式。我会尽快编辑以添加解释。

var subSentences = (w,...ws) => ws.length ? ws.reduce((r,s) => (r.push(r[r.length-1] + ` ${s}`), r),[w])
                                              .concat(subSentences(...ws))
                                          : [w],
    frequencyMap = sss => sss.reduce((map,ss) => subSentences(...ss.split(/\s+/)).reduce((m,s) => m.set(s, m.get(s) + 1 || 1), map), new Map());

    frequencies  = frequencyMap(["this is a test string",
                                 "this is another one",
                                 "yet another one is here"]);

console.log(...frequencies.entries()); // logging map object seems not possible hence entries

.as-console-wrapper { max-height : 100% !important
                    }

- Redu

---

这段代码几乎可以工作了，除了它应该将 ["this", 2], ["this is", 2] 合并成一个：["this is", 2]。不过还是非常感谢您的发布，我自己想不出如何解决这个问题。 - Jason