随笔档案

最短摘要的生成

这个问题在《编程之美》中提到过。前几天百度三面的时候也问到了这个问题，当时没有答上来。从新翻阅了一下《编程之美》。
直观的解决方案是：
从文档第一个词开始遍历，寻找后面的词是否与关键词数组匹配
然后从文档第二个、第三个 ... 一直到最后一个词遍历

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

改进的方法是：
对于求的的一个文摘，记录第一次出现关键词的位置，然后直接移动到该关键词，然后右边的边界再向后移动。
这个时间复杂度是 O(N)
这种方法也就是说维持了一个摘要滑动窗口，一遍扫描文档即可得到相应的最短摘要。
摘要中的关键词可以用一个队列来存储，因为摘要滑动窗口的左边界和右边界都是要从左到右移动的。所以队列正好适用。另外还应该维持一个对应文摘滑动窗口中的关键词出现的次数表。在做左右边界移动时需要考量这个次数表所提供的信息。