编程之美–最短摘要生成

题目:

Alibaba笔试题:给定一段产品的英文描述,包含M个英文字母,每个英文单词以空格分隔,无其他标点符号;
再给定N个英文单词关键 字,请说明思路并编程实现方法String extractSummary(String description,String[] key words),
目标是找出此产品描述中包含N个关键字(每个关键词至少出现一次)的长度最短的子串,作为产品简介输出。(不限编程语言)20分。

先来看看这些序列:

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

分析

当初看这道题时,看了好了几遍都没看懂。后来总算弄明白:给出的字符串是用其它程序分好词的,关键字符串也是用其它程序分好词的,而不是按用户直接输入的字符串。比如书上给的例子:“微软亚洲研究院 使命”,不是按空格分成两个关键词,“微软亚洲研究院”和“使命”,而是按其它程序分成:“微软”、“亚洲”、“研究院”和“使命”四个关键词。

“最短摘要”应该是指:包含所有关键字(关键字不要求按用户输入的顺序排列)的长度最短的摘要。书上的解法,把“最短摘要”理解成包含所有关键字且词个数最少的摘要。

 

这个过程要记录最短文摘的信息。
这个时间复杂度是 O(N ^ 2 * M)
N 是文档的长度
M 是关键词数组的大小

总结的滑动窗口法是:

——————————————————

使用滑动窗口的办法,找出最短摘要。我们把这个滑动窗口叫做摘要滑动窗口
摘要滑动窗口左边界L,右边界R。

窗口中应该维护的信息:

  1.   窗口中已经遍历过的关键字序列—-可使用队列才存储;
  2.   窗口中各个关键字出现的个数—-可使用hashtable来表示或者数组也行。

[while]

右边界R向右移动的原则:
  当前窗口中不包含所有种类的关键字,R向右移动寻找更新的关键字。

左边界L向右移动的原则:
  当前窗口中已经包含了所有种类的关键字,计算当前摘要长度,并从队列中拿出一个关键字,即L向右移动一个关键字;

L与R一直移动下去,一直到R不能往右移动时候,循环结束。

[end while]

来源:http://www.cnblogs.com/jack204/archive/2012/09/03/2668667.html

About 智足者富

http://chenpeng.info

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>