Levenshtein Distance
今日は混合分布のところが理解できずに永遠に詰んでました。大学1年に戻らないといけないかもですね…orz
というわけでネタがないので、ちょっと前のやつを投下!
Levenshtein Distanceを求めるプログラムです。
詳しい内容はそこらじゅうにたくさんあるので、ここで説明する必要はなさそうです。
核は、i行j列の行列を用意して、既知の距離情報から再帰的に距離を求めていくということです。
LD(i,j)はLD(i,j-1)+1,LD(i+1,j)+1, LD(i-1,j-1)+α ※(i=j) α=0, otherwise α=1
の情報のみで求めることができます。
入力:文章を数値リスト化したもの
例:appleとplayのLevenshtein Distanceを求める
2 5 #文字数 #異なり文字数 5 1 2 2 3 4 #文字の総数 #文字ID・・・ 4 2 3 1 5 リスト 1 a 2 p 3 l 4 e 5 y
#include <iostream> #include <fstream> #include <cstdlib> #include <cmath> #include <iomanip> #include <vector> #include <algorithm> #include<sys/times.h> using namespace std; int Dm, Dn, *VecA, **MatA, **MatB; void readValue(char *fn1){ ifstream fin; int i, j, l, v; fin.open(fn1); if(!fin){ cerr << "ERROR: Failed to open file" << endl; exit(1); } fin >> Dm >> Dn; VecA = new int [Dm]; //文字数 MatA = new int *[Dm]; //文字ID MatB = new int *[Dn+1]; //距離計算 for(i = 0; i < Dm; i++){ fin >> VecA[i]; MatA[i] = new int [VecA[i]]; for(j=0;j<VecA[i];j++){ fin >> v; MatA[i][j] = v-1; } VecA[i] += 1; } fin.close(); for(i=0;i<Dn+1;i++) MatB[i] = new int [Dn+1]; for(j=0;j<Dn+1;j++) MatB[0][j] = MatB[j][0] = j; } int calLD(int x, int y) { int i, j, n, m, v, min; n = VecA[x]; m = VecA[y]; if(n <= 1 || m <= 1) return(-1); for(i = 1; i < n; i++){ for(j = 1; j < m; j++){ v = (MatA[x][i-1] == MatA[y][j-1]) ? 0: 1; min = MatB[i-1][j-1] + v; if((v = MatB[i-1][j]+1) < min) min = v; if((v = MatB[i][j-1]+1) < min) min = v; MatB[i][j] = min; } } return(min); } void printValue(char *fn1) { ofstream fout; int i,j; double k; fout.open(fn1); fout << Dm << " " << Dm*(Dm-1)/2 << endl; for(i=0; i<Dm; i++){ for(j=i+1; j<Dm; j++){ k = calLD(i,j); k = 1.0-(k/(VecA[i]+VecA[j]-2)); //類似度に変換するため、文字数で割り正規化 fout << i+1 << " " << j+1 << " " << scientific << k << endl; } } fout.close(); }
出力
2 1 1 2 5.555556e-01 #No1と2の類似度
大規模なデータに使う時はうまく分散処理させないといけませんね。