最短摘要的生成

    图2 谷歌中搜索关键字“结构之法”

    在上面所示的图2中，搜索结果“结构之法算法之道-博客频道-CSDN.NET”下有一段说明性的文字：“程序员面试、算法研究、编程艺术、红黑树4大经典原创系列集锦与总结 作者：July—结构之法算法…”，我们把这段文字称为那个搜索结果的摘要，亦即最短摘要。我们的问题是，请问，这个最短摘要是怎么生成的呢?

    分析与解法

    这个问题比较完整正规的说明是：

    给定一段产品的英文描述，包含M个英文字母，每个英文单词以空格分隔，无其他标点符号；再给定N个英文单词关键字，请说明思路并编程实现方法

    目标是找出此产品描述中包含N个关键字（每个关键词至少出现一次）的长度最短的子串，作为产品简介输出（不限编程语言。

    简单分析如下：

    2. 1.试图右移动left，停止条件为再移动将导致无法包含所有关键字。
    3. 2.比较当前range's length和best length，更新最优值。
    4. 3.右移right，停止条件为使任意一个关键字的计数+1。
    5. 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之博主…..”中包含了关键字——“结构之法”。

    那么，我们该怎么做呢？

    在分析问题之前，先通过一个实际的例子来探讨。比如在本博客第一篇置顶文章的开头，有这么一段话：

    1. “程序员面试、算法研究、编程艺术、红黑树4大经典原创系列集锦与总结
    2. 作者：July--结构之法算法之道blog之博主。
    3. 时间：2010年10月-2011年6月。
    4. 出处：http://blog.csdn.net/v_JULY_v。
    5. 声明：版权所有，侵犯必究。”

    那么，我们可以猜想一下可能的分词结果：

    1. ”程序员/面试/、/算法/研究/、/编程/艺术/、/红黑树/4/大/经典/原创/系列/集锦/与/总结/ /作者/：/July/
    2. --/结构/之/法/算法/之/道/blog/之/博主/....“（网页的分词效果W数组）

    这也就是我们期望的W数组序列。

    之前的Q数组序列为：

    1. “结构之法”（用户输入的关键字Q数组）

    再看下下面这个W-Q序列：

    上述序列上面的是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个关键字不一定只会出现一遍，它可能会在这篇文章中出现多次，就如上面的W-Q序列一般。咱们可以假想出下面的结果（结构之法便出现了两次）：

    1. “程序员/面试/、/算法/研究/、/编程/艺术/、/红黑树/4/大/经典/原创/系列/集锦/与/总结/ /作者/：/July/
    2. --/结构/之/法/算法/之/道/blog/之/博主/././././转载/请/注明/出处/：/结构/之/法/算法/之/道/CSDN/博客/./././.”

    由此，我们可以得出解决此问题的思路，如下：

    1.从W数组的第一个位置开始查找出一段包含所有关键词数组Q的序列（第一个位置”程“开始：程序员/面试/、/算法/研究/、/编程/艺术/、/红黑树/4/大/经典/原创/系列/集锦/与/总结/ /作者/：/July/—/结构/之/法/查找包含关键字“结构之法”所有关键词的序列）。计算当前的最短长度，并更新Seq数组。

    2.对目标数组W进行遍历，从第二个位置开始，重新查找包含所有关键词数组Q的序列（第二个位置”序“处开始：程序员/面试/、/算法/研究/、/编程/艺术/、/红黑树/4/大/经典/原创/系列/集锦/与/总结/ /作者/：/July/—/结构/之/法/查找包含关键字”结构之法“所有关键词的序列），同样计算出其最短长度，以及更新包含所有关键词的序列Seq，然后求出最短距离。

    3.依次操作下去，一直到遍历至目标数组W的最后一个位置为止。

    最终，通过比较，咱们确定如下分词序列作为最短摘要，即搜索引擎给出的分词效果：

    1. “程序员面试、算法研究、编程艺术、红黑树4大经典原创系列集锦与总结 作者：July--结构之法算法之道blog之博主。
    2. 时间：2010年10月-2011年6月。出处：http://...”

    那么，这个算法的时间复杂度如何呢？

    要遍历所有其他的关键词（M），对于每个关键词，要遍历整个网页的词（N），而每个关键词在整个网页中的每一次出现，要遍历所有的Seq，以更新这个关键词与所有其他关键词的最小距离。所以算法复杂度为：O（N^2 * M）。

    我们试着降低此问题的复杂度。因为上述思路一再进行查找的时候，总是重复地循环，效率不高。那么怎么简化呢？先来看看这些序列：

      问题在于，如何一次把所有的关键词都扫描到，并且不遗漏。扫描肯定是无法避免的，但是如何把两次扫描的结果联系起来呢？这是一个值得考虑的问题。

      沿用前面的扫描方法，再来看看。第一次扫描的时候，假设需要包含所有的关键词，从第一个位置w0处将扫描到w6处：

      1. w0,w1,w2,w3,q0,w4,w5,q1,w6,w7,w8,q0,w9,q1

      那么，下次扫描应该怎么办呢？先把第一个被扫描的位置挪到q0处。

      然后把第一个被扫描的位置继续往后面移动一格，这样包含的序列中将减少了关键词q0。那么，我们便可以把第二个扫描位置往后移，这样就可以找到下一个包含所有关键词的序列。即从w4扫描到w9处，便包含了q1，q0：

      1. w0,w1,w2,w3,q0,w4,w5,q1,w6,w7,w8,q0,w9,q1

      这样，问题就和第一次扫描时碰到的情况一样了。依次扫描下去，在w中找出所有包含q的序列，并且找出其中的最小值，就可得到最终的结果。编程之美上给出了如下参考代码：

      1. //July、updated，2011.10.21
      3. int pBegin = 0;                     // 初始指针  
      4. int pEnd = 0;                       // 结束指针  
      5. int nLen = N;                       // 目标数组的长度为N  
      6. int nAbstractBegin = 0;           // 目标摘要的起始地址  
      7. int nAbstractEnd = 0;           // 目标摘要的结束地址  
      9. while(true)  
      10. {  
      11.     // 假设未包含所有的关键词，并且后面的指针没有越界，往后移动指针  
      12.     while(!isAllExisted() && pEnd < nLen)  
      13.     {  
      14.         pEnd++;  
      15.     }  
      17.     // 假设找到一段包含所有关键词信息的字符串  
      18.     while(isAllExisted())  
      19.     {  
      20.         if(pEnd – pBegin < nTargetLen)  
      21.             nTargetLen = pEnd – pBegin;  
      23.             nAbstractEnd = pEnd – 1;   
      24.         }  
      25.         pBegin++;  
      26.     }  
      27.     if(pEnd >= N)  
      28.         Break;  
      29. }

      小结：上述思路二相比于思路一，很明显提高了不小效率。我们在匹配的过程中利用了可以省去其中某些死板的步骤，这让我想到了KMP算法的匹配过程。同样是经过观察，比较，最后总结归纳出的高效算法。我想，一定还有更好的办法，只是我们目前还没有看到，想到，待我们去发现，创造。

      以下是读者jiaotao1983回复于本文评论下的反馈，非常感谢。

      关于最短摘要的生成，我觉得July的处理有些简单，我以July的想法为基础，提出了自己的一些想法，这个问题分以下几步解决：

      1.将传入的key words[]生成哈希表，便于以后的字符串比较。结构为KeyHash，如下：

      1. struct KeyHash
      2. {
      3.   int cnt;
      4.   char key[];
      5.   int hash;
      6. }

      结构体中的hash代表了关键字的哈希值，key代表了关键字，cnt代表了在当前的扫描过程中，扫描到的该关键字的个数。

      当然，作为哈希表结构，该结构体中还会有其它值，这里不赘述。

      2.建立一个KeyWord结构，结构体如下：

      1. struct KeyWord
      2. {
      3.   int start;
      4.   KeyHash* key;
      5.   KeyWord* next;
      6.   KeyWord* prev;
      7. }

      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，结构体如下：

      扫描到的多个句子结构组成一个链表。增加两个全局变量，分别指向了Sentence链表的头和尾。

      扫描时，建立关键字链表时，也要建立Sentence链表。当扫描到包含了所有的关键字时，必须要扫描到一个完整句子的结束。开始做Sentence头节点优化。做法是：查看Sentence结构中的全部key结构，如果全部的key对应的KeyHash结构的cnt属性全部大于1，表明该句子是多余的，去掉它，去掉它的时候更新对应的HashKey结构的关键字，因为减去了很多的关键字。然后对下一个Sentence结构做同样的操作，直至某个Sentence结构是必不可少的，就是说它包含了当前的摘要中只出现过一次的关键字！

      扫描到了一个摘要后，在开始新的扫描。更新Sentence链表的头结点为下一个节点，同时更新对应的KeyHash结构中的cnt关键字，当某个cnt变成0时，就递增needKeycnt变量。再次扫描时仍然是从当前的结束位置开始扫描。

      初步估计时间也是O(M+N)。