[알고리즘]최소편집거리 알고리즘

코드

 

public class Main { public int M[][] = new int[100][100]; public int getMin(int a, int b, int c) { int min = a; if (min > b) min = b; if (min > c) min = c; return min; } public int getDistance(String a, String b) { for (int i = 0; i < a.length(); i++) { M[i][0] = i; } for (int j = 0; j < b.length(); j++) { M[0][j] = j; } for (int i = 1; i < a.length(); i++) { for (int j = 1; j < b.length(); j++) { if (a.charAt(i) == b.charAt(j)) { M[i][j] = M[i - 1][j - 1]; } else { M[i][j] = getMin(M[i - 1][j], M[i - 1][j - 1], M[i][j - 1]) + 1; } } } //System.out.println(a + "와(과) " + b + "의 최소 편집 거리는 " + M[a.length() - 1][b.length() - 1] + "입니다."); return M[a.length() - 1][b.length() - 1]; } /* public void getTrace(int M[][], String a, String b) { System.out.println("[ " + b + "을(를) " + a + "로 바꾸는 과정 추적 ]"); int i = a.length() - 1; int j = b.length() - 1; while (!(i == 0 && j == 0)) { int s = getMin(M[i - 1][j], M[i - 1][j - 1], M[i][j - 1]); if (s == M[i][j]) { i -= 1; j -= 1; } else { if (s == M[i][j - 1]) { System.out.println(b.charAt(j) + "을(를) 삭제합니다."); j -= 1; } else if (s == M[i - 1][j - 1]) { System.out.println(b.charAt(j) + "을(를) " + a.charAt(i) + "(으)로 변경합니다."); i -= 1; j -= 1; } else { System.out.println(a.charAt(i) + "을(를) 추가합니다."); i -= 1; } } } } */ public static void main(String[] args) { String a = "abcdef"; String b = "azced"; Main m = new Main(); // m.getDistance(a, b); // m.getTrace(m.M, a, b); // for(int i=0;i<a.length();i++){ System.out.print("\t"+a.charAt(i)); } System.out.println(); for(int i=0;i<b.length();i++){ System.out.print(b.charAt(i)+"\t"); for(int j=0;j<a.length();j++){ System.out.print(m.getDistance(b.substring(0, i+1), a.substring(0,j+1))+"\t"); } System.out.println(); } } }

 

코드 실행 화면

 

 

코드 실행 화면을 만들기 위해 필요 없어 보이는 부분은 주석처리하고 getDistance 메소드 반환값을 void → int 형으로 만들었습니다.

 

<출처 : http://blog.naver.com/PostView.nhnblogId=ndb796&logNo=220870218783&parentCategoryNo=23&categoryNo=&viewDate=&isShowPopularPosts=true&from=search

>