# 最短摘要的生成 ## 題目描述 你我在百度或谷歌搜索框中敲入本博客名稱的前4個字“結構之法”，便能在第一個選項看到本博客的鏈接，如下圖2所示：  圖2 谷歌中搜索關鍵字“結構之法” 在上面所示的圖2中，搜索結果“結構之法算法之道-博客頻道-CSDN.NET”下有一段說明性的文字：“程序員面試、算法研究、編程藝術、紅黑樹4大經典原創系列集錦與總結 作者：July--結構之法算法...”，我們把這段文字稱為那個搜索結果的摘要，亦即最短摘要。我們的問題是，請問，這個最短摘要是怎么生成的呢? ## 分析與解法 這個問題比較完整正規的說明是： 給定一段產品的英文描述，包含M個英文字母，每個英文單詞以空格分隔，無其他標點符號；再給定N個英文單詞關鍵字，請說明思路并編程實現方法 String extractSummary(String description,String[] key words) 目標是找出此產品描述中包含N個關鍵字（每個關鍵詞至少出現一次）的長度最短的子串，作為產品簡介輸出（不限編程語言。 簡單分析如下： @owen：掃描過程始終保持一個[left,right]的range,初始化確保[left,right]的range里包含所有關鍵字則停止。然后每次迭代： 1.試圖右移動left，停止條件為再移動將導致無法包含所有關鍵字。 2.比較當前range's length和best length，更新最優值。 3.右移right，停止條件為使任意一個關鍵字的計數+1。 4.重復迭代。 更進一步，我們可以對問題進行如下的簡化： **1.**假設給定的已經是經過網頁分詞之后的結果，詞語序列數組為W。其中W[0], W[1],…, W[N]為一些已經分好的詞語。 **2.**假設用戶輸入的搜索關鍵詞為數組Q。其中Q[0], Q[1],…, Q[m]為所有輸入的搜索關鍵詞。 這樣，生成的最短摘要實際上就是一串相互聯系的分詞序列。比如從W[i]到W[j]，其中，0 < i < j<= N。例如上圖所示的摘要“程序員面試、算法研究、編程藝術、紅黑樹4大經典原創吸了集錦與總結 作者：July--結構之法算法之道blog之博主.....”中包含了關鍵字——“結構之法”。 那么，我們該怎么做呢？ ### 解法一 在分析問題之前，先通過一個實際的例子來探討。比如在本博客第一篇置頂文章的開頭，有這么一段話： “程序員面試、算法研究、編程藝術、紅黑樹4大經典原創系列集錦與總結 作者：July--結構之法算法之道blog之博主。 時間：2010年10月-2011年6月。 出處：http://blog.csdn.net/v_JULY_v。 聲明：版權所有，侵犯必究。” 那么，我們可以猜想一下可能的分詞結果： ”程序員/面試/、/算法/研究/、/編程/藝術/、/紅黑樹/4/大/經典/原創/系列/集錦/與/總結/ /作者/：/July/ --/結構/之/法/算法/之/道/blog/之/博主/....“（網頁的分詞效果W數組） 這也就是我們期望的W數組序列。 之前的Q數組序列為： “結構之法”（用戶輸入的關鍵字Q數組） 再看下下面這個W-Q序列： w0,w1,w2,w3,q0,w4,w5,q1,w6,w7,w8,q0,w9,q1 上述序列上面的是W數組（經過網頁分詞之后的結果），W[0], W[1],…, W[N]為一些已經分好的詞語，上述序列下面的是Q數組（用戶輸入的搜索關鍵詞）。其中Q[0], Q[1],…, Q[m]為所有輸入的搜索關鍵詞。 ok，如果你不甚明白，我說的通俗點：如上W-Q序列中，我們可以把,q0,w4,w5,q1作為摘要，q0,w9,q1的也可以作為摘要，同樣都包括了所有的關鍵詞q0，q1，那么選取哪個是最短摘要呢？答案很明顯，后一個更短，選取q0,w9,q1的作為最短摘要，這便是最短摘要的生成。 我們可以進一步可以想象，如下： 從用戶的角度看：當我們在百度的搜索框中輸入“結構之法”4個字時，搜索引擎將在索引數據庫中（關于搜索引擎原理的大致介紹，可參考本博客中這篇文章：搜索引擎技術之概要預覽）查找和匹配這4個字的網頁，最終第一個找到了本博客的置頂的第一篇文章：[置頂]程序員面試、算法研究、編程藝術、紅黑樹4大系列集錦與總結； 從搜索引擎的角度看：搜索引擎經過把上述網頁分詞后，便得到了上述的分詞效果，然后在這些分詞中查找“結構之法”4個關鍵字，但這4個關鍵字不一定只會出現一遍，它可能會在這篇文章中出現多次，就如上面的W-Q序列一般。咱們可以假想出下面的結果（結構之法便出現了兩次）： “程序員/面試/、/算法/研究/、/編程/藝術/、/紅黑樹/4/大/經典/原創/系列/集錦/與/總結/ /作者/：/July/ --/結構/之/法/算法/之/道/blog/之/博主/././././轉載/請/注明/出處/：/結構/之/法/算法/之/道/CSDN/博客/./././.” 由此，我們可以得出解決此問題的思路，如下： **1.**從W數組的第一個位置開始查找出一段包含所有關鍵詞數組Q的序列（第一個位置”程“開始：程序員/面試/、/算法/研究/、/編程/藝術/、/紅黑樹/4/大/經典/原創/系列/集錦/與/總結/ /作者/：/July/--/結構/之/法/查找包含關鍵字“結構之法”所有關鍵詞的序列）。計算當前的最短長度，并更新Seq數組。 **2.**對目標數組W進行遍歷，從第二個位置開始，重新查找包含所有關鍵詞數組Q的序列（第二個位置”序“處開始：程序員/面試/、/算法/研究/、/編程/藝術/、/紅黑樹/4/大/經典/原創/系列/集錦/與/總結/ /作者/：/July/--/結構/之/法/查找包含關鍵字”結構之法“所有關鍵詞的序列），同樣計算出其最短長度，以及更新包含所有關鍵詞的序列Seq，然后求出最短距離。 **3.**依次操作下去，一直到遍歷至目標數組W的最后一個位置為止。 最終，通過比較，咱們確定如下分詞序列作為最短摘要，即搜索引擎給出的分詞效果： “程序員面試、算法研究、編程藝術、紅黑樹4大經典原創系列集錦與總結 作者：July--結構之法算法之道blog之博主。 時間：2010年10月-2011年6月。出處：http://...” 那么，這個算法的時間復雜度如何呢？ 要遍歷所有其他的關鍵詞（M），對于每個關鍵詞，要遍歷整個網頁的詞（N），而每個關鍵詞在整個網頁中的每一次出現，要遍歷所有的Seq，以更新這個關鍵詞與所有其他關鍵詞的最小距離。所以算法復雜度為：O（N^2 * M）。 ### 解法二 我們試著降低此問題的復雜度。因為上述思路一再進行查找的時候，總是重復地循環，效率不高。那么怎么簡化呢？先來看看這些序列： w0,w1,w2,w3,q0,w4,w5,q1,w6,w7,w8,q0,w9,q1 問題在于，如何一次把所有的關鍵詞都掃描到，并且不遺漏。掃描肯定是無法避免的，但是如何把兩次掃描的結果聯系起來呢？這是一個值得考慮的問題。 沿用前面的掃描方法，再來看看。第一次掃描的時候，假設需要包含所有的關鍵詞，從第一個位置w0處將掃描到w6處： w0,w1,w2,w3,q0,w4,w5,q1,w6,w7,w8,q0,w9,q1 那么，下次掃描應該怎么辦呢？先把第一個被掃描的位置挪到q0處。 w0,w1,w2,w3,q0,w4,w5,q1,w6,w7,w8,q0,w9,q1 然后把第一個被掃描的位置繼續往后面移動一格，這樣包含的序列中將減少了關鍵詞q0。那么，我們便可以把第二個掃描位置往后移，這樣就可以找到下一個包含所有關鍵詞的序列。即從w4掃描到w9處，便包含了q1，q0： w0,w1,w2,w3,q0,w4,w5,q1,w6,w7,w8,q0,w9,q1 這樣，問題就和第一次掃描時碰到的情況一樣了。依次掃描下去，在w中找出所有包含q的序列，并且找出其中的最小值，就可得到最終的結果。編程之美上給出了如下參考代碼： ```c //July、updated，2011.10.21 int nTargetLen = N + 1; // 設置目標長度為總長度+1 int pBegin = 0; // 初始指針 int pEnd = 0; // 結束指針 int nLen = N; // 目標數組的長度為N int nAbstractBegin = 0; // 目標摘要的起始地址 int nAbstractEnd = 0; // 目標摘要的結束地址 while(true) { // 假設未包含所有的關鍵詞，并且后面的指針沒有越界，往后移動指針 while(!isAllExisted() && pEnd < nLen) { pEnd++; } // 假設找到一段包含所有關鍵詞信息的字符串 while(isAllExisted()) { if(pEnd – pBegin < nTargetLen) { nTargetLen = pEnd – pBegin; nAbstractBegin = pBegin; nAbstractEnd = pEnd – 1; } pBegin++; } if(pEnd >= N) Break; } ``` 小結：上述思路二相比于思路一，很明顯提高了不小效率。我們在匹配的過程中利用了可以省去其中某些死板的步驟，這讓我想到了KMP算法的匹配過程。同樣是經過觀察，比較，最后總結歸納出的高效算法。我想，一定還有更好的辦法，只是我們目前還沒有看到，想到，待我們去發現，創造。 ### 解法三 以下是讀者jiaotao1983回復于本文評論下的反饋，非常感謝。 關于最短摘要的生成，我覺得July的處理有些簡單，我以July的想法為基礎，提出了自己的一些想法，這個問題分以下幾步解決： **1.**將傳入的key words[]生成哈希表，便于以后的字符串比較。結構為KeyHash，如下： ```c struct KeyHash { int cnt; char key[]; int hash; } ``` 結構體中的hash代表了關鍵字的哈希值，key代表了關鍵字，cnt代表了在當前的掃描過程中，掃描到的該關鍵字的個數。 當然，作為哈希表結構，該結構體中還會有其它值，這里不贅述。 初始狀態下，所有哈希結構的cnt字段為0。 **2.**建立一個KeyWord結構，結構體如下： ```c struct KeyWord { int start; KeyHash* key; KeyWord* next; KeyWord* prev; } ``` key字段指向了建立的一個KeyWord代表了當前掃描到的一個關鍵字，掃描到的多個關鍵字組成一個雙向鏈表。 start字段指向了關鍵字在文章中的起始位置。 **3.**建立幾個全局變量: KeyWord* head，指向了雙向鏈表的頭，初始為NULL。 KeyWord* tail，指向了雙向鏈表的尾，初始為NULL。 int minLen，當前掃描到的最短的摘要的長度，初始為0。 int minStartPos，當前掃描到的最短摘要的起始位置。 int needKeyCnt，還需要幾個關鍵字才能夠包括全部的關鍵字，初始為關鍵字的個數。 **4.**開始對文章進行掃描。每掃描到一個關鍵字時，就建立一個KeyWord的結構并且將其連入到掃描到的雙向鏈表中，更新head和tail結構，同時將對應的KeyHash結構中的cnt加1，表示掃描到了關鍵字。如果cnt由0變成了1，表示掃描到一個新的關鍵字，因此needKeyCnt減1。 **5.**當needKeyCnt變成0時，表示掃描到了全部的關鍵字了。此時要進行一個操作：鏈表頭優化。鏈表頭指向的word是摘要的起始點，可是如果對應的KeyHash結構中的cnt大于1，表示掃描到的摘要中還有該關鍵字，因此可以跳過該關鍵字。因此，此時將鏈表頭更新為下一個關鍵字，同時，將對應的KeyHash中的結構中的cnt減1，重復這樣的檢查，直至某個鏈表頭對應的KeyHash結構中的cnt為1，此時該結構不能夠少了。 **6.**如果找到更短的minLength，則更新minLength和minStartPos。 **7.**開始新一輪的搜索。此時摘除鏈表的第一個節點，將needKeyCnt加1，將下一個節點作為鏈表頭，同樣的開始鏈表頭優化措施。搜索從上一次的搜索結束處開始，不用回溯。就是所，搜索在整個算法的過程中是一直沿著文章向下的，不會回溯，直至文章搜索完畢。 這樣的算法的復雜度初步估計是O(M+N)。 **8.**另外，我覺得該問題不具備實際意義，要具備實際意義，摘要應該包含完整的句子，所以摘要的起始和結束點應該以句號作為分隔。 這里，新建立一個結構：Sentence，結構體如下： ```c struct Sentence { int start; //句子的起始位置 int end; //句子的結束位置 KeyWord* startKey; //句子包含的起始關鍵字 KeyWord* endKey; //句子包含的結束關鍵字 Sentence* prev; //下一個句子結構 Sentence* next; //前一個句子結構 } ``` 掃描到的多個句子結構組成一個鏈表。增加兩個全局變量，分別指向了Sentence鏈表的頭和尾。 掃描時，建立關鍵字鏈表時，也要建立Sentence鏈表。當掃描到包含了所有的關鍵字時，必須要掃描到一個完整句子的結束。開始做Sentence頭節點優化。做法是：查看Sentence結構中的全部key結構，如果全部的key對應的KeyHash結構的cnt屬性全部大于1，表明該句子是多余的，去掉它，去掉它的時候更新對應的HashKey結構的關鍵字，因為減去了很多的關鍵字。然后對下一個Sentence結構做同樣的操作，直至某個Sentence結構是必不可少的，就是說它包含了當前的摘要中只出現過一次的關鍵字！ 掃描到了一個摘要后，在開始新的掃描。更新Sentence鏈表的頭結點為下一個節點，同時更新對應的KeyHash結構中的cnt關鍵字，當某個cnt變成0時，就遞增needKeycnt變量。再次掃描時仍然是從當前的結束位置開始掃描。 初步估計時間也是O(M+N)。 ok，留下一個編程之美一書上的擴展問題：當搜索一個詞語后，有許多的相似頁面出現，如何判斷兩個頁面相似，從而在搜索結果中隱去這類結果？