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の類似度

大規模なデータに使う時はうまく分散処理させないといけませんね。