算法：子字符串聚合，以確定相關信息

Question

我想要做一個聚合算法，將獲得基於用戶亮點的文本中最重要的元素。

假設你有具有，你必須選擇從文本k連拍字作爲「有關突出顯示」，其中1 < = K < = N。（k爲n的子串）

的能力n個字文本

假設我們從這些k個高光中的10到10000的任意位置選擇，是否有任何算法可以確定最重要的信息？

請考慮許多亮點會重疊，我們需要考慮這一點。我最好還是在javascript中尋找解決方案，因爲它是用於Chrome擴展的。

這不適用於一個班級，這是針對基於人羣的摘要的個人項目。

Answer 1

假設每個用戶都會突出顯示一段文字，並且您知道這些突出顯示的內容。對於文本中的每個單詞，您可以總結出有多少人突出顯示它。你可以計算的一件事是，對於某些固定的k和N，總共使用最多N個單詞的k個拉伸，例如N個單詞被突出顯示的次數之和是最大的。

您可以使用動態編程來完成此操作，在文本中從左向右工作。對於文本中的每個點以及每個可能允許的組合（＃突出顯示，＃突出顯示的總字數，當前單詞是否突出顯示），您可以計算出滿足這些限制條件的最佳答案的分數。通過使用前一個單詞的最佳答案，您可以在每個時間點找出最佳答案 - 考慮如果您採用現有最佳答案中的任何一個，並延長當前突出顯示，如果突出顯示最後一個單詞，或開始新的亮點。最後，您從右向左追溯整個文本的最佳答案。

這給你一個總結k伸展的最佳部分的形式來突出顯示，使用最多N個單詞來提取儘可能多的用戶突出顯示的單詞。毫無疑問，對於不同的分數或不同的突出顯示約束條件，會有不同的變化 - 計算k個區段的最佳組合可能會更容易，其中每個區段最多包含M個字符。