Java/C++のLevenshtein distance - なぜか数学者にはワイン好きが多い

レーベンシュタイン距離を実装するには，Wikipediaを見れば十分です．

ここのサンプルに忠実に，例えばJavaで実装してみると，次のようになります．
以下，日本語コードはUTF-8だけに統一します．

import java.io.*;
import java.util.*;

class LevenshteinDistance
{
  int edit(String px, String py) throws UnsupportedEncodingException
  {
    int len1=px.length(),len2=py.length();
    int[][] row = new int[len1+1][len2+1];
    int i,j;
    int result;

    for(i=0;i<len1+1;i++) row[i][0] = i;
    for(i=0;i<len2+1;i++) row[0][i] = i;
    for(i=1;i<=len1;++i)
    {
      for(j=1;j<=len2;++j)
      {
        row[i][j] = Math.min(Math.min(
           (Integer)(row[i-1][j-1])
           + ((px.substring(i-1,i).equals(py.substring(j-1,j)))?0:1) , // replace
                      (Integer)(row[i][j-1]) + 1),     // delete
                      (Integer)(row[i-1][j]) + 1);  // insert
      }
    }
    result=(Integer)(row[len1][len2]);

    return result;
  }

  public static void main(String[] args) throws UnsupportedEncodingException
  {
    LevenshteinDistance ld = new LevenshteinDistance() ;
    System.out.println(ld.edit("あい","あいう"));
  }
}

このプログラムをedit0.javaというファイル名で保存して実行すると．．．

> javac -encoding UTF-8 edit0.java ; java -Dfile.encoding=UTF8 LevenshteinDistance
1

要するに「う」だけ違うので，距離は1となります．

同じプログラムをC++で作ると．．．

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
class LevenshteinDistance
{
public:
  static int edit(const string &px, const string &py)
  {
    int len1=px.size(),len2=py.size();
    vector<vector<int> > row(len1+1, vector<int>(len2+1));
    int i,j;
    int result;
    for(i=0;i<len1+1;i++) row[i][0]=i;
    for(i=0;i<len2+1;i++) row[0][i]=i;
    for(i=1;i<=len1;++i)
    {
      for(j=1;j<=len2;++j)
      {
        row[i][j] = min(min(
                      row[i-1][j-1] + ((px[i-1]==py[j-1])?0:1) , // replace
                      row[i][j-1] + 1),     // delete
                       row[i-1][j] + 1  );  // insert
      }
    }
    result=row[i-1][j-1];
    return result;
  }
};

int main()
{
  cout<<LevenshteinDistance::edit("あい","あいう")<<endl;
  return(0);
}

結果は，

> c++ -o LevenshteinDistance edit0.cc ; ./LevenshteinDistance
3

当然，UTF-8の全角一文字分違うので，3バイト分ということで距離が3になってしまいます．
c++にもw_charとか多言語を意識した予約がありますが．．．今のところ，互換性等，信用できない．．．

というわけで，自前で．

#include <iostream>
#include <vector>
using namespace std;
class LevenshteinDistance
{
public:
  static int isutf8(const string &c)
  {
    int ret;
    if((c[0]&0x80) == 0x00) ret = 1;
    else if((c[0]&0xe0) == 0xc0 && (c[1]&0xc0) == 0x80) ret = 2;
    else if((c[0]&0xf0) == 0xe0 && (c[1]&0xc0) == 0x80
                               && (c[2]&0xc0) == 0x80 ) ret = 3;
    return(ret);
  }
  static bool equal(const string &s1, const string &s2)
  {
    bool ret = false;
    if(isutf8(s1)==isutf8(s2))
    {
      int f=0;
      for(int i=0;i<isutf8(s1);++i)
      {
        if(s1[i]==s2[i]) ++f;
      }
      if(f==isutf8(s1)) ret = true;
    }
    return(ret);
  }
  static int edit(const string &px, const string &py)
  {
    int len1=0,len2=0;
    int i,j;
    int result;
    for(i=0;i<px.size();)
    {
      i += isutf8(&px[i]);
      ++len1;
    }
    for(i=0;i<py.size();)
    {
      i += isutf8(&py[i]);
      ++len2;
    }
    vector<vector<int> > row(len1+1, vector<int>(len2+1));

    for(i=0;i<len1+1;i++) row[i][0]=i;
    for(i=0;i<len2+1;i++) row[0][i]=i;
    int k=0,l=0;
    for(i=1;i<=len1;++i)
    {
      l = 0;
      for(j=1;j<=len2;++j)
      {
        row[i][j] = min(min(
                      row[i-1][j-1] + (equal(&px[k],&py[l])?0:1) , // replace
                      row[i][j-1] + 1),     // delete
                       row[i-1][j] + 1  );  // insert
        l += isutf8(&py[l]);
      }
      k += isutf8(&px[k]);
    }
    result=row[i-1][j-1];

    return result;
  }
};
int main()
{
  cout<<LevenshteinDistance::edit("あい","あいう")<<endl;
  return(0);
}

はい，実行すると

> c++ -o LevenshteinDistance edit.cc ; ./LevenshteinDistance
1

距離は1に．

せっかくなので，Javaのマルチバイト機能を信用しないバージョンを，C++から移植する形で書いてみました．

import java.io.*;
import java.util.*;

class LevenshteinDistance
{
  static int isutf8(String args) throws UnsupportedEncodingException
  {
    int ret = -1;
    byte[] c = args.getBytes("UTF-8");
    if((c[0]&0x80) == 0x00) ret = 1;
    else if((c[0]&0xe0) == 0xc0 && (c[1]&0xc0) == 0x80) ret = 2;
    else if((c[0]&0xf0) == 0xe0 && (c[1]&0xc0) == 0x80
                                && (c[2]&0xc0) == 0x80 ) ret = 3;
    return(ret);
  }
  static Boolean equal(String s1, String s2) throws UnsupportedEncodingException
  {
    Boolean ret = false;
    if(isutf8(s1)==isutf8(s2))
    {
      int f=0;
      for(int i=0;i<isutf8(s1);++i)
      {
        byte[] c1 = s1.getBytes("UTF-8");
        byte[] c2 = s2.getBytes("UTF-8");
        if(c1[i]==c2[i]) ++f;
      }
      if(f==isutf8(s1)) ret = true;
    }
    return(ret);
  }
  static int edit(String px, String py) throws UnsupportedEncodingException
  {
    Vector<Vector> row = new Vector<Vector>();
    int len1=0,len2=0;
    int i,j;
    int result;
    len1 = px.length();
    len2 = py.length();
    for(i=0; i<len1+1; ++i)
    {
      row.add(new Vector());
      for(j=0; j<len2+1; ++j)
      {
        row.get(i).add(0);
      }
    }

    for(i=0;i<len1+1;i++) row.get(i).set(0,i);
    for(i=0;i<len2+1;i++) row.get(0).set(i,i);
    for(i=1;i<=len1;++i)
    {
      for(j=1;j<=len2;++j)
      {
        row.get(i).set(j,Math.min(Math.min(
                      (Integer)(row.get(i-1).get(j-1))
          + (equal(px.substring(i-1),py.substring(j-1))?0:1) , // replace
                      (Integer)(row.get(i).get(j-1)) + 1),     // delete
                      (Integer)(row.get(i-1).get(j)) + 1  ));  // insert
      }
    }
    result=(Integer)(row.get(len1).get(len2));

    return result;
  }

  public static void main(String[] args) throws UnsupportedEncodingException
  {
    System.out.println(LevenshteinDistance.edit("あい","あいう"));
  }
}

実行しますと，

> javac -encoding UTF-8 edit.java ; java -Dfile.encoding=UTF8 LevenshteinDistance
Note: edit.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
1

一応，距離は1に．