なんとなく生きてます

雑記帳備忘録チラシの裏

編集距離(レーベンシュタイン距離)を求めるプログラムをJavaScriptで


両者の2単語の編集距離(レーベンシュタイン距離)を計算します。

と思ったら,なんか,jsがはてぶの上で動かないので,コードを貼るw.

  function onButtonClick() {
    target1 = document.getElementById("input1");
    target1.innerText = document.forms.id_form1.id_textBox1.value;
    target2 = document.getElementById("input2");
    target2.innerText = document.forms.id_form1.id_textBox2.value;
    var arr1 = (target1.innerText).split('');
    arr1leng = arr1.length;
    var arr2 = (target2.innerText).split('');
    arr2leng = arr2.length;

    //編集距離を計算するためのマップを作成
    //map[i][j]の値はtext1のi文字目、text2のj文字目に対応する.
    //mapの各要素は[値、フラグ]
    //フラグは最後にマップを右隅からたどるために必要となるため後述
    var map = new Array(arr1leng+1);
    for (i = 0; i < arr1leng+1; i++){
      map[i] = new Array(arr2leng+1);
    }
    //0行目を初期化
    for (j = 0; j < arr2leng+1; j++){
      map[0][j] = new Array(j, 0);
    }
    //0列目を初期化
    for (i = 0; i < arr1leng+1; i++){
      map[i][0] = new Array(i, 1)
    }
    //======================================================
    //マップを埋めていく
    for (i = 1; i < arr1leng+1; i++){
      for (j = 1; j < arr2leng+1; j++){
        //左の値はmap[i][j-1](フラグ0)
        //上の値はmap[i-1][j](フラグ1)
        //左上の値はmap[i-1][j-1](フラグ2)
        //これらの中から最小のものを選んでmap[i][j]の値としてフラグも定める.
        //map[i][j]の値は[値、フラグ]という配列になる
        temp0 = map[i][j-1][0] + 1;
        temp1 = map[i-1][j][0] + 1;
        var temp2;
        if(arr1[i] == arr2[j]){
          temp2 = map[i-1][j-1][0] + 1;
        }
        else {
          temp2 = map[i-1][j-1][0] + 3;
        }
        //=======================================
        if(temp0 <= temp1){
          if(temp0 <= temp2){//temp0が最小
            map[i][j] = new Array(temp0, 0);
          }
          if(temp0 > temp2){//temp2が最小
            map[i][j] = new Array(temp2, 2);
          }
        }
        if(temp0 > temp1){
          if(temp1 <= temp2){//temp1が最小
            map[i][j] = new Array(temp1, 1);
          }
          if(temp1 > temp2){//temp2が最小
            map[i][j] = new Array(temp2, 2);
          }
        }
      }
    }
    //マップの作成が完了
    //======================================================

    //======================================================
    //マップを右下隅から辿っていく
    var dist = 0;
    //フラグmap[i][j][1]を見て
    //0ならmap[i][j-1]に
    //1ならmap[i-1][j]に
    //2ならmap[i-1][j-1]に移動してdistを1増やし、
    //map[0][0]にたどり着くまで繰り返す.
    i_current = arr1leng;
    j_current = arr2leng;
    while (i_current != 0 && j_current != 0) {
      if(map[i_current][j_current][1] == 0){
        j_current--;
        dist++;
      }
      if(map[i_current][j_current][1] == 1){
        i_current--;
        dist++;
      }
      if(map[i_current][j_current][1] == 2){
        i_current--;
        j_current--;
        dist++;
      }
    }
    //======================================================
    alert("2語の編集距離は " + dist + " です!");
  }