距離のダイナミックプランニングアルゴリズムの編集

自然言語処理では,空間ベクトルモデル,距離編集法が広く用いられている段落文間の類似度を比較することがしばしば必要である.ここでは、距離アルゴリズムの編集に重点を置き、Levenshtein距離とも呼ばれます.編集距離の基本思想:文字列Aに対して、少なくとも数回の増加、削除、変更操作を経て文字列Bに変えることができ、その中で操作の回数はAとBの間の編集距離である.
次のようになります.
A:  aaabbb
B: aacb
Bのcをaに変更し、後に2つのbを加える必要があるので、編集距離は3になります.
上の操作は英語の文字列に対して行われ、漢字からなる文については、最小編集単位を単一の字に決定する必要があります.
編集の距離を求めて動的な計画の思想を使うことができます.
文字列A(0...i)、B(0...j)があります.i+2行、j+2列のマトリクスを構築し、第1行に0...j、第1列に0...iの順に割り当てます.
文字列Aの0...iとBの0...jは比較を行い、行列に埋め込まれ、その計算式は以下の通りである.
M[i][j] = Min(M[i-1][j]+1, M[i][j-1]+1, A[i]==B[j]?M[i-1][j-1]:M[i-1][j-1]+1)
この繰返し式は、1つの文字を追加したり、1つの文字を修正したりすることによって、最も現在の問題を解く最小の解を見つけることができることを理解するのは難しくありません.これにより,サブ問題を一歩一歩解き,最終的に問題の解を導くことができる.
アルゴリズムJavaプログラムは以下の通りです.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
 * @author shao
 *
 */
public class Levenshtein {

	/**
	 * @param str1       1
	 * @param str2       2
	 * @return     
	 * @description       
	 */
	public static int getDistance(String str1, String str2){
		int len1 = str1.length();
		int len2 = str2.length();
		if(len1==0)
			return len2;
		else if(len2==0)
			return len1;
		
		int[][] disM = new int[len1+1][len2+1];
		for(int i=0;i<=len2;++i)
			disM[0][i] = i;
		for(int j=0;j<=len1;++j)
			disM[j][0] = j;
		for(int i=1;i<=len1;++i)
			for(int j=1;j<=len2;++j)
			{
				int top = disM[i-1][j]+1;
				int left = disM[i][j-1]+1;
				int lt = str1.charAt(i-1)==str2.charAt(j-1)?disM[i-1][j-1]:disM[i-1][j-1]+1;
				
				disM[i][j] = top