《編程之美》讀書筆記24： 3.5 最短摘要的生成
當初看這道題時，看了好了幾遍都沒看懂。后來總算弄明白：給出的字符串是用其它程序分好詞的，關鍵字符串也是用其它程序分好詞的，而不是按用戶直接輸入的字符串。比如書上給的例子：“微軟亞洲研究院 使命”，不是按空格分成兩個關鍵詞，“微軟亞洲研究院”和“使命”，而是按其它程序分成：“微軟”、“亞洲”、“研究院”和“使命”四個關鍵詞。
“最短摘要”應該是指：包含所有關鍵字（關鍵字不要求按用戶輸入的順序排列）的長度最短的摘要。書上的解法，把“最短摘要”理解成包含所有關鍵字且詞個數最少的摘要。
弄清了問題，解決起來就很簡單：
1 反復讀入字符串，直到碰到關鍵字（可以用set或unordered_set）。
2 更新該關鍵字字符串最近出現的位置。
3 若已經找到所有的關鍵字，根據這些關鍵字的位置最小/最大值，計算摘要長度
可以用set來維護這些位置值。
（實際上，只要求維護位置的最小值，還可以自行實現一個堆結構，節省空間。）
根據位置值計算長度，需要先計算出分詞后的字符串，在未分詞的字符串的位置。
4 記錄長度最短的摘要
若有m個關鍵字，待查詢字符串有n個，時間復雜度大概為：O(n*log m)
（關鍵字一般都很短，可以認為對關鍵字間的比較、計算哈希值時間復雜度為O(1)）
另外，將關鍵字映射到數字，減少字符串比較，能進一步提高效率。
最短摘要
#include<iostream>
#include<vector>
#include<string>
#include<set>
#define USE_CPLUSPLUS0x 1
#if USE_CPLUSPLUS0x
#include<unordered_map>
#else
#include<map>
#endif
#include<cassert>
using std::string;
using std::vector;
using std::cout;
/**//* //----
#if USE_CPLUSPLUS0x
struct Cmp{
bool operator()(const string* a, const string* b) const { return *a == *b; }
} ;
struct Hash{
size_t operator()(const string* a) const { return std::hash<string>()(*a);}
} ;
typedef std::unordered_map<const string*, size_t, Hash, Cmp> Dict;
#else
struct Cmp{
bool operator()(const string* sa, const string * sb) const { return *sa < *sb; }
} ;
typedef std::map<const string*, size_t, Cmp> Dict;
#endif
*/
#if USE_CPLUSPLUS0x
typedef std::unordered_map<string, size_t> Dict;
#else
typedef std::map<string, size_t> Dict;
#endif
template<typename T>
void output(T beg, T end, const char str[] = "", const char sep[] = "")
{
cout << str;
while (beg != end) cout << *beg++ << sep;
cout << "\n";
}
void solve(const string str[], const size_t str_sz,
const string keyword[], const size_t keyword_sz)
{
if (str_sz == 0 || keyword_sz == 0) return;
Dict key_idx; //關鍵字映射為數字，以減少字符串比較
for (size_t i = 0; i < keyword_sz; ++i) {
//key_idx.insert(Dict::value_type(&keyword[i], i)); //----
key_idx.insert(Dict::value_type(keyword[i], i));
}
const size_t Pos_init = -1;
vector<size_t> prev_pos(keyword_sz, Pos_init); //上次碰到的關鍵字符串的位置
std::set<size_t> pos; //對關鍵字符串的位置進行升序排列
vector<size_t> old_pos; //分詞后的字符串，在原字符串中的位置
old_pos.reserve(str_sz + 1);
old_pos.push_back(0);
for (size_t i = 0, sum = 0; i < str_sz; ++i) {
sum += str[i].size();
old_pos.push_back(sum);
}
size_t beg = 0, end = 0, len = -1, count = 0; //記錄結果
for (size_t i = 0; i < str_sz; ++i) {
//Dict::iterator it = key_idx.find(&str[i]); //----
Dict::iterator it = key_idx.find(str[i]);
if (it == key_idx.end()) continue;
assert(it->second < prev_pos.size());
size_t& last_pos = prev_pos[it->second];
if (last_pos != Pos_init) pos.erase(last_pos); //更新前要先刪除舊的
else ++count; //已匹配關鍵字 數加1
last_pos = i;
pos.insert(pos.end(), i);
assert(count <= keyword_sz);
if (count == keyword_sz) { //包含所有關鍵字
size_t pbeg = *pos.begin();
//std::set<size_t>::iterator it = pos.end();
//size_t pend = *--it + 1;
size_t pend = i + 1;
assert(pbeg < old_pos.size());
assert(pend < old_pos.size());
size_t plen = old_pos[pend] - old_pos[pbeg];
if (plen < len) {
len = plen;
beg = pbeg;
end = pend;
}
}
}
output(&str[0], &str[str_sz], "words: ");
output(&keyword[0], &keyword[keyword_sz], "keywords: ", " ");
if (beg == end && !pos.empty()) { //沒找到所有關鍵字
cout << "(" << pos.size() << "/" << keyword_sz << " Matched) ";
beg = *pos.begin();
std::set<size_t>::iterator it = pos.end();
end = *--it + 1;
}
output(&str[beg], &str[end], "result: ");
cout << "\n";
}
template<typename T, size_t sz>
inline size_t getsz(T (&)[sz]) { return sz; }
int main()
{
string keyword[] = { "微軟", "計算機", "亞洲", "中國"};
string str[] = {
"微軟","亞洲","研究院","成立","于","1998","年","，","我們","的","使命",
"是","使","未來","的","計算機","能夠","看","、","聽","、","學","，",
"能","用","自然語言","與","人類","進行","交流","。","在","此","基礎","上",
"，","微軟","亞洲","研究院","還","將","促進","計算機","在","亞太","地區",
"的","普及","，","改善","亞太","用戶","的","計算","體驗","。","”"
};
solve(str, getsz(str), keyword, getsz(keyword));
}
作者：
flyinghearts 出處：
http://www.cnblogs.com/flyinghearts/ 本文采用
知識共享署名-非商業性使用-相同方式共享 2.5 中國大陸許可協議進行許可，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接，否則保留追究法律責任的權利。