javascript - 算法：聚合子串以确定相关信息

Question

我正在尝试做一个聚合算法，它将根据用户突出显示文本中最重要的元素。

想象一下，您有一个包含 n 个单词的文本，您可以从文本中选择 k 个连续单词作为“相关突出显示”，其中 1<=k<=n.(k 是 n 的子字符串)

假设我们从这 k 个亮点中选择 10 到 10000 个，是否有任何算法可以确定最重要的信息？

考虑到许多亮点会重叠，我们需要考虑到这一点。我也最好在 javascript 中寻找解决方案，因为它是针对 chrome 扩展的。

这不是针对课程的，而是针对基于人群的总结的个人项目。

Answer 1

假设每个用户都突出显示了一些文本片段，并且您知道这些突出显示是什么。你可以总结出，对于文本中的每个单词，有多少人突出显示了它。您可以计算出的一件事是，对于某些固定的 k 和 N，总共使用最多 N 个单词的 k 个拉伸，这样 N 个单词被突出显示的次数的总和是最大值。

您可以使用动态编程来做到这一点，在文本中从左到右工作。对于文本中的每个点和每个可能的允许组合（# 突出显示，# 总单词突出显示，当前单词是否被突出显示），您计算出在满足这些约束的那个点处终止的最佳答案的分数。您可以通过使用前一个单词的最佳答案来计算每个点的最佳答案 - 考虑如果您采用任何现有的最佳答案并扩展当前突出显示（如果最后一个单词被突出显示），您可能获得的分数，或开始一个新的亮点。最后，您从右到左跟踪整个文本的最佳答案。

这为您提供了 k 段要突出显示的最佳部分的摘要，最多使用 N 个单词来提取尽可能多的用户突出显示的单词。毫无疑问，对于不同的分数或不同的突出显示约束，这会有所不同——计算 k 段的最佳组合可能更容易，其中每个段最多包含 M 个字符。