ナップサック問題として複数文書要約を解くを試す
はじめに
複数文書要約をナップサック問題として解く、という話を聴いて、簡単に試せそうなのでやってみる。
手法
西川ら「冗長性制約付きナップサック問題に基づく複数文書要約モデル」
https://www.jstage.jst.go.jp/article/jnlp/20/4/20_585/_pdf
上記の論文中で紹介されている「動的計画ナップサックアルゴリズム」を参考に。
(論文で提案されている手法ではないことに注意)
コード
#include <iostream> #include <vector> #include <map> #include <sstream> class KPSummary { // T[i][k] := 文iまでで最大要約長がkのときの最適解値 // U[i][k] := 経路復元用(文iを利用したかどうか) std::vector< std::vector<int> > T, U; int maxN, maxK; public: KPSummary(int maxN, int maxK): maxN(maxN), maxK(maxK), T(maxN+1, std::vector<int>(maxK+1, 0)), U(maxN+1, std::vector<int>(maxK+1, 0)) { } std::vector<std::string> summary( const std::vector<std::string>& text, //文 const std::vector<int>& s, //文の重要度 int K //要約後のテキスト長 ) { //DPtableのサイズで足りない場合は結果なし if(text.size() > maxN || K > maxK) return std::vector<std::string>(); int n = text.size(); for(int k=0; k<=K; k++) T[0][k] = 0; for(int i=1; i<=n; i++){ for(int k=0; k<=K; k++){ T[i][k] = T[i-1][k]; U[i][k] = 0; } int li = text[i-1].length() + 1; //改行文字含み int si = s[i-1]; for(int k=li; k<=K; k++){ if(k-li<0) continue; if(T[i-1][k-li] + si >= T[i][k]){ T[i][k] = T[i-1][k-li] + si; U[i][k] = 1; } } } std::vector<std::string> ret; { int k = K; for(int i=n; i>=1; i--){ int li = text[i-1].length() + 1; //改行文字含み if(U[i][k] == 1){ ret.push_back(text[i-1]); k = k - li; } } } std::reverse(ret.begin(), ret.end()); return ret; } }; std::pair<int, std::string> split(const std::string& str){ std::pair<int, std::string> ret; size_t spi = 0; for(int i=0; i<str.length(); i++) if(str[i] == '\t'){ spi = i; break; } std::stringstream ss(str.substr(0, spi)); ss >> ret.first; ret.second = str.substr(spi+1); return ret; } int main(){ KPSummary summary(1000, 1000); //1000文書以下、1000byte以下 std::vector<std::string> text; std::vector<int> s; std::string str; int weight; while(std::getline(std::cin, str)){ std::pair<int, std::string> sp = split(str); s.push_back(sp.first); text.push_back(sp.second); } //500byte以下に要約 std::vector<std::string> res = summary.summary(text, s, 500); for(int i=0; i<res.size(); i++){ std::cout << res[i] << std::endl; } return 0; }
入力
子安さんがプリキュアに出てたのでtwitterで「子安」の検索結果をいくつかピックアップ。
タブ区切りで「RT数\tツイート」形式。
0 寝ぼけながらプリキュア見たらテラ子安だったしそのあと二度寝したしおはようござまし 0 子安 0 子安声でグリだもんね…。(白目)あれ、子安ボイチェン使ってたけど中身はラビのｶｰﾁｬﾝでした！って今思うと結構な力業よな(笑) 0 いきなりファンレターは云々とか言い出して噴いた////オレスキー子安面白すぎ/// 0 敵キャラですwwwwwwww 子安は来週も出演しますよー 井上和彦は敵キャラのラスボスに情報を提供する鏡のキャラなので不定期ですがwwwwwww 0 ノリノリやん子安 0 オレスキー子安か…… 0 うちの地元に子安ってとこあるな 地名で 0 子安さんまた変な役やってたね(´｀) 0 テラ子安wwwwwwやばいwww 0 プリキュア子安すぎかwwwwwwwwwwwwwww 0 オレスキー子安は改心しそうなキャラだなあ 0 敵幹部に子安ｗｗｗ 0 では、私ももう一個。子安さんはどうです？？ 0 プリキュアの敵キャラに子安出てたけどプリキュアに出るのこれで何度目だｗ 0 敵に子安きたああ□︎ほんと子安は良い声だよぉ… 0 子安の塔wwwwwwwwwwwwwwwwwwwww 0 子安の声でなぎさってこの妹の声確実に本名陽子さんだわ 0 子安ボイスの幹部強そう 0 森久保さんの声は、森久保さんって認識すると全てが森久保さんってキャラになる。子安さんの声が子安ってキャラになるのと同じ。 0 子安がイケメン 0 今季のプリキュア、あまり興味もてなかったんだが、なんか変なテンション高い敵がでてきて（cv.子安）少し興味がでてきた（≧∇≦） 0 花粉の予感！てかハピネスに子安さんだって！！やべぇ 276 あなたの子安武人、どこから？ 1 子安かわええ 0 今日プリキュア見たら子安出ててわろちw 0 テラ子安ｗｗｗ 0 ＿人人 人人＿ ＞ 子安 ＜ ￣Y^Y^Y^Y￣ 0 プリキュアに子安さんが出てたと聞いて…軍服…か……えっ軍服！！！？ 0 子安オン・ステージ 0 子安ｗｗｗｗ 0 子安のじてんでふぁん！ 0 声は子安です 0 音だけ聞いてたらプリキュアにディオ出てきたかと思った…焦った…子安さん…？ 0 子安いいキャラしてんな 0 プリキュアのレギュラーで出てきそうな敵キャラがテラ子安で、ファンクラブの年会費800円らしいっすよww＼(^o^)／ 0 オレスキーさんは子安ｗｗ 0 子安が出てましたwwwwwwww 井上和彦も出演してて 簡単にまとめるとカーズ様の部下がDIOです 0 テラ子安 0 子安！テラ子安！ 0 今話題の子安
結果
#ツイートの順番を入れ替えて9個要約を作成
$ for i in {1..9};do cat test.txt| perl -MList::Util=shuffle -e 'print shuffle(<>)'| ./a.out > res.${i}.txt; done
$ wc res*
15 21 497 res.1.txt
11 16 498 res.2.txt
10 13 498 res.3.txt
12 17 499 res.4.txt
8 11 499 res.5.txt
12 15 498 res.6.txt
10 12 494 res.7.txt
13 15 500 res.8.txt
12 15 496 res.9.txt
103 135 4479 total
$ cat res.1.txt
子安かわええ
テラ子安
あなたの子安武人、どこから？
子安ｗｗｗｗ
子安がイケメン
子安！テラ子安！
いきなりファンレターは云々とか言い出して噴いた////オレスキー子安面白すぎ///
子安ボイスの幹部強そう
テラ子安ｗｗｗ
子安
今話題の子安
子安オン・ステージ
子安さんまた変な役やってたね(´｀)
＿人人 人人＿ ＞ 子安 ＜ ￣Y^Y^Y^Y￣
テラ子安wwwwwwやばいwww
$ cat res.2.txt
子安
あなたの子安武人、どこから？
テラ子安
森久保さんの声は、森久保さんって認識すると全てが森久保さんってキャラになる。子安さんの声が子安ってキャラになるのと同じ。
子安かわええ
子安オン・ステージ
今日プリキュア見たら子安出ててわろちw
オレスキー子安は改心しそうなキャラだなあ
子安いいキャラしてんな
子安がイケメン
子安の塔wwwwwwwwwwwwwwwwwwwww
$ cat res.3.txt
あなたの子安武人、どこから？
子安のじてんでふぁん！
今話題の子安
子安いいキャラしてんな
オレスキーさんは子安ｗｗ
声は子安です
子安かわええ
寝ぼけながらプリキュア見たらテラ子安だったしそのあと二度寝したしおはようござまし
子安さんまた変な役やってたね(´｀)
子安が出てましたwwwwwwww 井上和彦も出演してて 簡単にまとめるとカーズ様の部下がDIOです500byte以下に収まってて、RT数が多いものはちゃんと入ってる。
ただ、重要度sにRT数しかいれていないので、そのツイートがどの程度中身のあることを言っているかは考慮していない。
(ツイートだったら考慮する必要ないかもしれないけど)
