最短摘要的生成

這個(gè)問(wèn)題在《編程之美》中提到過(guò)。前幾天百度三面的時(shí)候也問(wèn)到了這個(gè)問(wèn)題，當(dāng)時(shí)沒(méi)有答上來(lái)。從新翻閱了一下《編程之美》。
直觀的解決方案是：
從文檔第一個(gè)詞開(kāi)始遍歷，尋找后面的詞是否與關(guān)鍵詞數(shù)組匹配
然后從文檔第二個(gè)、第三個(gè) ... 一直到最后一個(gè)詞遍歷

這個(gè)過(guò)程要記錄最短文摘的信息。
這個(gè)時(shí)間復(fù)雜度是 O(N ^ 2 * M)
N 是文檔的長(zhǎng)度
M 是關(guān)鍵詞數(shù)組的大小

改進(jìn)的方法是：
對(duì)于求的的一個(gè)文摘，記錄第一次出現(xiàn)關(guān)鍵詞的位置，然后直接移動(dòng)到該關(guān)鍵詞，然后右邊的邊界再向后移動(dòng)。
這個(gè)時(shí)間復(fù)雜度是 O(N)
這種方法也就是說(shuō)維持了一個(gè)摘要滑動(dòng)窗口，一遍掃描文檔即可得到相應(yīng)的最短摘要。
摘要中的關(guān)鍵詞可以用一個(gè)隊(duì)列來(lái)存儲(chǔ)，因?yàn)檎瑒?dòng)窗口的左邊界和右邊界都是要從左到右移動(dòng)的。所以隊(duì)列正好適用。另外還應(yīng)該維持一個(gè)對(duì)應(yīng)文摘滑動(dòng)窗口中的關(guān)鍵詞出現(xiàn)的次數(shù)表。在做左右邊界移動(dòng)時(shí)需要考量這個(gè)次數(shù)表所提供的信息。