隨筆檔案

最短摘要的生成

這個問題在《編程之美》中提到過。前幾天百度三面的時候也問到了這個問題，當時沒有答上來。從新翻閱了一下《編程之美》。
直觀的解決方案是：
從文檔第一個詞開始遍歷，尋找后面的詞是否與關鍵詞數組匹配
然后從文檔第二個、第三個 ... 一直到最后一個詞遍歷

這個過程要記錄最短文摘的信息。
這個時間復雜度是 O(N ^ 2 * M)
N 是文檔的長度
M 是關鍵詞數組的大小

改進的方法是：
對于求的的一個文摘，記錄第一次出現關鍵詞的位置，然后直接移動到該關鍵詞，然后右邊的邊界再向后移動。
這個時間復雜度是 O(N)
這種方法也就是說維持了一個摘要滑動窗口，一遍掃描文檔即可得到相應的最短摘要。
摘要中的關鍵詞可以用一個隊列來存儲，因為摘要滑動窗口的左邊界和右邊界都是要從左到右移動的。所以隊列正好適用。另外還應該維持一個對應文摘滑動窗口中的關鍵詞出現的次數表。在做左右邊界移動時需要考量這個次數表所提供的信息。