算法：子字符串聚合，以确定相关信息

Question

我想要做一个聚合算法，将获得基于用户亮点的文本中最重要的元素。

假设你有具有，你必须选择从文本k连拍字作为“有关突出显示”，其中1 < = K < = N。（k为n的子串）

的能力n个字文本

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

请考虑许多亮点会重叠，我们需要考虑这一点。我最好还是在javascript中寻找解决方案，因为它是用于Chrome扩展的。

这不适用于一个班级，这是针对基于人群的摘要的个人项目。

Answer 1

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

您可以使用动态编程来完成此操作，在文本中从左向右工作。对于文本中的每个点以及每个可能允许的组合（＃突出显示，＃突出显示的总字数，当前单词是否突出显示），您可以计算出满足这些限制条件的最佳答案的分数。通过使用前一个单词的最佳答案，您可以在每个时间点找出最佳答案 - 考虑如果您采用现有最佳答案中的任何一个，并延长当前突出显示，如果突出显示最后一个单词，或开始新的亮点。最后，您从右向左追溯整个文本的最佳答案。

这给你一个总结k伸展的最佳部分的形式来突出显示，使用最多N个单词来提取尽可能多的用户突出显示的单词。毫无疑问，对于不同的分数或不同的突出显示约束条件，会有不同的变化 - 计算k个区段的最佳组合可能会更容易，其中每个区段最多包含M个字符。