Edit distance

Edit distance 를 구하기 위해 java 로 짜보았다.

class EditDistance {

	// ㄱ ㄲ ㄴ ㄷ ㄸ ㄹ ㅁ ㅂ ㅃ ㅅ ㅆ ㅇ ㅈ ㅉ ㅊ ㅋ ㅌ ㅍ ㅎ
	final static char[] ChoSung = { 0x3131, 0x3132, 0x3134, 0x3137, 0x3138, 0x3139, 0x3141, 0x3142, 0x3143, 0x3145,
			0x3146, 0x3147, 0x3148, 0x3149, 0x314a, 0x314b, 0x314c, 0x314d, 0x314e };
	// ㅏ ㅐ ㅑ ㅒ ㅓ ㅔ ㅕ ㅖ ㅗ ㅘ ㅙ ㅚ ㅛ ㅜ ㅝ ㅞ ㅟ ㅠ ㅡ ㅢ ㅣ
	final static char[] JwungSung = { 0x314f, 0x3150, 0x3151, 0x3152, 0x3153, 0x3154, 0x3155, 0x3156, 0x3157, 0x3158,
			0x3159, 0x315a, 0x315b, 0x315c, 0x315d, 0x315e, 0x315f, 0x3160, 0x3161, 0x3162, 0x3163 };
	// ㄱ ㄲ ㄳ ㄴ ㄵ ㄶ ㄷ ㄹ ㄺ ㄻ ㄼ ㄽ ㄾ ㄿ ㅀ ㅁ ㅂ ㅄ ㅅ ㅆ ㅇ ㅈ ㅊ ㅋ ㅌ ㅍ ㅎ
	final static char[] JongSung = { 0, 0x3131, 0x3132, 0x3133, 0x3134, 0x3135, 0x3136, 0x3137, 0x3139, 0x313a, 0x313b,
			0x313c, 0x313d, 0x313e, 0x313f, 0x3140, 0x3141, 0x3142, 0x3144, 0x3145, 0x3146, 0x3147, 0x3148, 0x314a,
			0x314b, 0x314c, 0x314d, 0x314e };

	public static void main(String[] args) {

		if (args.length < 2) {
			System.err.println("자소 분리할 단어를 2개 입력하세요.");
			System.exit(1); 
		}

		try {
			String Jaso1 = hangulToJaso(args[0]);
			String Jaso2 = hangulToJaso(args[1]);

			System.out.println("Jaso1 : " + Jaso1 + ", Jaso2 : " + Jaso2);
			System.out.println("distance : " + Integer.toString(minDistance(Jaso1, Jaso2)));
		} catch (Exception e) {
			System.err.println(e); 
			System.exit(1);
		}

	} 
	
	public static String hangulToJaso(String s) { // 유니코드 한글 문자열을 입력 받음
		int a, b, c; // 자소 버퍼: 초성/중성/종성 순
		String result = "";

		for (int i = 0; i < s.length(); i++) {
			char ch = s.charAt(i);

			if (ch >= 0xAC00 && ch <= 0xD7A3) { // "AC00:가" ~ "D7A3:힣" 에 속한 글자면
												// 분해

				c = ch - 0xAC00;
				a = c / (21 * 28);
				c = c % (21 * 28);
				b = c / 28;
				c = c % 28;

				result = result + ChoSung[a] + JwungSung[b];
				if (c != 0)
					result = result + JongSung[c]; // c가 0이 아니면, 즉 받침이 있으면
			} else {
				result = result + ch;
			}
		}
		return result;
	}

	public static int minDistance(String word1, String word2) {
		int len1 = word1.length();
		int len2 = word2.length();

		int[][] dp = new int[len1 + 1][len2 + 1];

		for (int i = 0; i <= len1; i++) {
			dp[i][0] = i;
		}

		for (int j = 0; j <= len2; j++) {
			dp[0][j] = j;
		}

		// iterate though, and check last char
		for (int i = 0; i < len1; i++) {
			char c1 = word1.charAt(i);
			for (int j = 0; j < len2; j++) {
				char c2 = word2.charAt(j);

				if (c1 == c2) {
					dp[i + 1][j + 1] = dp[i][j];
				} else {
					int replace = dp[i][j] + 2;
					int insert = dp[i][j + 1] + 1;
					int delete = dp[i + 1][j] + 1;

					int min = replace > insert ? insert : replace;
					min = delete > min ? min : delete;
					dp[i + 1][j + 1] = min;
				}
			}
		}

		return dp[len1][len2];
	}

}

파라미터로 감나무, 밤나무를 넘기면

감나무 잣나무를 넘기면!

자소 또는 음소( phonemes ) 단위로 쪼개는 코드를 삽입했다. 

음절 단위로 쪼갠 경우 감나무 : 밤나무  의 Edit distance 와 감나무 : 잣나무  의 Edit distance 는 각각 1글자의 substitution. 즉, 2로 같았겠지만 이를 자소 단위로 쪼개어 비교하는 경우 감나무 : 밤나무는 1개의 substitution, 감나무 : 잣나무는 2개의 substitution 이 이뤄져야 하므로 값이 각각 2, 4 로 다르게 나타난다.