編集距離で遊ぶ
はじめに
簡単な例としてよく出てくる「編集距離」を使って、英単語の修正を試してみる。(編集距離が小さいものを列挙するまで)
dpができなすぎるので、「dpやるだけ」って言えるようになりたい。
編集距離とは
- ある文字列sからある文字列tへ、文字の削除、挿入、置換などの操作をするとき、最小の操作回数(または最小操作コスト)
- dp[i][j] := s[0..i-1]からt[0..j-1]にするのにかかる最小操作回数(または最小操作コスト)
- さまざまな変形や拡張が研究されてる
- 近似文字列照合
許可する操作による違い
- 編集距離(Levenshtein distance)
- 挿入、削除、置換
- Damerau distance
- 挿入、削除、置換、隣接文字同士の入替
- Longest common subsequence distance
- 挿入、削除
- ハミング距離(Hamming distance)
- 置換のみ
コード
高速化は何もしてない。いつものごとく適当なコード。
#include <iostream> #include <fstream> #include <vector> #include <climits> #include <algorithm> class EditDistance { bool ins, del, rep, twi; //許可する操作(挿入、削除、置換、隣接文字同士の入替) public: EditDistance(bool ins, bool del, bool rep, bool twi): ins(ins), del(del), rep(rep), twi(twi) {} int solve(const std::string& src, const std::string& tgt){ std::vector< std::vector<int> > D(src.length()+1, std::vector<int>(tgt.length()+1, INT_MAX)); for(int i=0; i<src.length()+1; i++) D[i][0] = i; //srcからすべて削除していけばtgt(=NULL)にできる for(int i=0; i<tgt.length()+1; i++) D[0][i] = i; //src(=NULL)にすべて追加していけばtgtにできる for(int i=1; i<=src.length(); i++){ for(int j=1; j<=tgt.length(); j++){ int op_nop = INT_MAX; if(src[i-1] == tgt[j-1]){ op_nop = D[i-1][j-1]; } int op_ins = INT_MAX; if(ins && D[i][j-1] != INT_MAX){ op_ins = D[i][j-1] + 1; //srcに1文字足す事でtgtと同じにした } int op_del = INT_MAX; if(del && D[i-1][j] != INT_MAX){ op_del = D[i-1][j] + 1; //srcから1文字消すことでtgtと同じにした } int op_rep = INT_MAX; if(rep && D[i-1][j-1] != INT_MAX){ op_rep = D[i-1][j-1] + 1; //srcの1文字を置換することでtgtと同じにした } int op_twi = INT_MAX; if(twi && i>1 && j>1 && D[i-2][j-2] != INT_MAX){ if(src[i-1]==tgt[j-2] && src[i-2]==tgt[j-1]){ op_twi = D[i-2][j-2] + 1; //srcの連続した2文字を入れ替える事でtgtに同じにできる場合、それをしてtgtと同じにした } } D[i][j] = std::min(D[i][j], op_nop); D[i][j] = std::min(D[i][j], op_ins); D[i][j] = std::min(D[i][j], op_del); D[i][j] = std::min(D[i][j], op_rep); D[i][j] = std::min(D[i][j], op_twi); } } return D[src.length()][tgt.length()]; } }; int main(int argc, char** argv){ if(argc != 2){ std::cerr << "Usage : " << argv[0] << " dictionary_file" << std::endl; return 1; } std::ifstream dic_ifs(argv[1]); std::vector<std::string> dic; std::string word; while(dic_ifs >> word) dic.push_back(word); //編集距離で近い単語を見つける EditDistance ed(true, true, true, true); //すべての編集操作を有効 while(std::cin >> word){ for(size_t i=0; i<dic.size(); i++){ int dist = ed.solve(word, dic[i]); if(dist <= 2){ std::cout << "\t" << dist << " " << dic[i] << std::endl; } } } return 0; }
英単語(名詞)リストの準備
- WordNet-3.0のdict/index.nounから1列目を取り出す
- http://wordnet.princeton.edu/
- 「cut -f1 -d" " index.noun |tail -n +30 > noun.dict 」
試す
$ g++ edit_distance.cc -O2
$ ./a.out noun.dict
doctar
2 cottar
2 docker
1 doctor
2 dollar
2 donar
2 dotard
2 kotar
2 lontar
2 mortar
2 nectar
2 octad
2 ottar
programing
0 programing
1 programming
colour
2 cloud
2 clout
2 coleus
2 collar
2 colobus
2 colon
2 colony
1 color
2 colors
0 colour
1 colours
2 colter
2 contour
2 cooler
2 copout
2 dolor
1 dolour
2 flour
2 honour
2 odour
2 valour
2 velour
disatnce
1 distance候補多すぎ。実用的には、さらに生起確率や前後文脈とか考慮すれば使えそうかも？
キーボードの打ち間違えであれば、ホームポジションからずれて入力した場合とかも考慮したら面白そう。
