編輯距離（Edit Distance | Levenshtein距離）

1.問題定義

編輯距離又稱為Levenshtein距離，是指兩個字元串之間，從一個字元串變成另一個字元串所需要的最小編輯操作次數。可以采用的編輯操作包括：插入操作、替換操作和删除操作。例如：字元串“a“ 與字元串 ”b“的編輯距離為1，隻有一個替換操作。 将”kitten一字轉成“sitting”的編輯距離為3： sitten （k→s）：替換操作 sittin （e→i）：替換操作 sitting （→g）：插入操作

2.問題分析

編輯距離問題可以采用動态規劃的方式來解決。假設dp[i][j]表示字元串的長度為i的字元串strA[0...i-1]和字元串長度為j的字元串strB[0...j-1]的編輯距離。接下來就要分析dp[i][j]與dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]之間的關系。 假設strA的最後一個字元為‘x’，strB的最後一個字元為‘y’，則通過‘x’與‘y’的關系得到如下： 1）如果x==y，則dp[i][j]=dp[i-1][j-1]； 2)如果x！=y，将x替換為y，則dp[i][j]=dp[i-1][j-1]+1； 3）如果x！=y，将y插入到x後面，則dp[i][j]=dp[i][j-1]+1； 4）如果x！=y，将x從strA中删除，則dp[i][j]=dp[i-1][j]+1; 在x！=y的情況下，dp[i][i]的值為2）3）4）中的最小值。 初始條件： dp[i][0]=i，dp[0][j]=j.

3.程式實作

public class EditDistance {

	/**
	 * @author Qunzer
	 * @since 2013/12/16
	 */

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String strA = "hello";
		String strB = "helli1";
		System.out.println("Edit distance is :" + getEditDistance(strA, strB));

	}

	// 求解編輯距離的靜态方法
	public static int getEditDistance(String strA, String strB) {
		int lenA = strA.length();
		int lenB = strB.length();
		int[][] dp = new int[lenA + 1][lenB + 1];
		int i, j;
		for (i = 0; i < lenA; i++) {
			dp[i][0] = i;
		}
		for (j = 0; j < lenB; ++j) {
			dp[0][j] = j;
		}
		for (i = 0; i < lenA; ++i) {
			char c1 = strA.charAt(i);
			for (j = 0; j < lenB; ++j) {
				char c2 = strB.charAt(j);
				if (c1 == c2)
					dp[i + 1][j + 1] = dp[i][j];
				else {
					int replaceTemp = dp[i][j] + 1;
					int insertTemp = dp[i + 1][j] + 1;
					int deleteTemp = dp[i][j + 1] + 1;
					dp[i + 1][j + 1] = getMin(replaceTemp, insertTemp,
							deleteTemp);
				}
			}
		}
		return dp[lenA][lenB];
	}

	// 得到三個中的最小值
	public static int getMin(int a, int b, int c) {
		int min = a > b ? b : a;
		return (c > min ? min : c);
	}

}
      

4.輯距離的應用

編輯距離可以用到以下場景： DNA分析 拼字檢查 語音辨識 抄襲偵測 相似度計算