焼きなまし法で単語分割
アプローチ
- 「出現単語数」+「のべ出現単語数」+「入力文の文字数(固定)」=目的関数を最小化
- 単語の区切り位置を温度によって変化させる(近傍探索)
- 温度をどんどん冷やしていき、それに伴い、変化させる区切り位置の数を減らす
コード
#include <iostream> #include <vector> #include <set> #include <cmath> //xorshift // 注意: longではなくint(32bit)にすべき unsigned long xor128(){ static unsigned long x=123456789, y=362436069, z=521288629, w=88675123; unsigned long t; t=(x^(x<<11)); x=y; y=z; z=w; return w=(w^(w>>19))^(t^(t>>8)); } class word_segment_by_sa { //目的関数 : この値が最小となる区切りを探す int evaluate(std::string& text, std::string& segs){ std::vector<std::string> word = segment(text, segs); std::set<std::string> dic; for(size_t i=0; i<word.size(); i++){ dic.insert(word[i]); } int text_size = word.size(); //出現単語数 int lexicon_size = 0; //出現単語(uniq)の文字数の和(のべ出現単語数を含む) std::set<std::string>::iterator itr = dic.begin(); while(itr != dic.end()){ lexicon_size += (*itr).length() + 1; ++itr; } return text_size + lexicon_size; } //区切りフラグをランダムにn回入れ替える std::string flip_n(std::string segs, int n){ for(int i=0; i<n; i++){ size_t r = xor128()%(segs.length()); if(segs[r] == '0') segs[r] = '1'; else segs[r] = '0'; } return segs; } public: word_segment_by_sa(){} //単語に分割 std::vector<std::string> segment(const std::string& text, std::string& segs){ std::vector<std::string> ret; size_t last = 0; for(size_t i=0; i<segs.length(); i++){ if(segs[i] == '1'){ ret.push_back(text.substr(last,i+1-last)); last = i+1; } } ret.push_back(text.substr(last)); return ret; } //目的関数が最小化する区切りを焼きなましで探索 std::string simulated_annealing(std::string& text, std::string& init_segs, int iter, double cooling_rate){ double temp = init_segs.size(); std::string segs = init_segs; while(temp > 0.5){ std::string best_segs = segs; int best_score = evaluate(text, segs); for(size_t i=0; i<iter; i++){ std::string guess = flip_n(segs, round(temp)); int score = evaluate(text, guess); if(score < best_score){ best_score = score; best_segs = guess; } } segs = best_segs; temp = temp / cooling_rate; //デバッグ用 std::cerr << temp << " : " << best_score << std::endl; std::vector<std::string> ret = segment(text, segs); for(size_t i=0; i<ret.size(); i++){ std::cerr << " " << ret[i] << std::endl; } } return segs; } }; int main(){ word_segment_by_sa ws; std::string text = "doyouseethekittyseethedoggydoyoulikethekittylikethedoggy"; //元のテキスト std::string segs = "0000000000000001000000000010000000000000000100000000000"; //テキストの区切り情報 //最適解の探索 std::string best_segs = ws.simulated_annealing(text, segs, 10000, 1.2); std::vector<std::string> words = ws.segment(text, best_segs); //結果の表示 std::cout << "Best Result ==================" << std::endl; for(size_t i=0; i<words.size(); i++){ std::cout << words[i] << std::endl; } return 0; }
イテレーションを本に書いてある5000回の2倍まわして、十分な回数をまわす。
結果
45.8333 : 64 doyouseethekitty seethedoggy doyoulikethekitty likethedoggy ... 0.480452 : 43 doyou see thekitty see thedoggy doyou like thekitty like thedoggy Best Result ================== doyou see thekitty see thedoggy doyou like thekitty like thedoggy
いい感じにわかれた。