[Java] 편집거리를 활용한 한국어 단어 교정 프로그램

회사에서 오탈자를 교정하기 위한 시스템을 개발해야 하는데, 여러가지 방법중 하나인 편집거리 알고리즘을 생각해 보았다.

이미 많은 분들이 편집 거리를 구하기 위한 프로그램을 많이 공유해 주었고, 아래 사이트에서 알고리즘을 참고하여 자바 프로그램으로 만들게 되었다.

참고한 알고리즘은 Levenshtein Distance 이며, 한국어는 영어와 달리 한 글자가 다차원으로 이루어져 있기 때문에 자소 분리라는 선행 과정에 대한 프로세스를 추가하였다.

Levenshtein Distance : https://en.wikipedia.org/wiki/Levenshtein_distance

클래스 파일은 다음과 같이 두개로 나뉜다.

 - JasoTokenizer : 자소 분리를 위한 클래스

 - EditDistance : 편집 거리를 구하기 위한 클래스

JasoTokenizer.java

/**
 * 한글 단어의 자소 분리를 위한 클래스입니다.
 */
public class JasoTokenizer {
 
 private static final char [] CHO_SUNG = {'ㄱ', 'ㄲ', 'ㄴ', 'ㄷ', 'ㄸ', 'ㄹ', 'ㅁ', 'ㅂ', 'ㅃ', 'ㅅ', 'ㅆ', 'ㅇ', 'ㅈ', 'ㅉ', 'ㅊ', 'ㅋ', 'ㅌ', 'ㅍ', 'ㅎ'};
 private static final char [] JWUNG_SUNG = {'ㅏ', 'ㅐ', 'ㅑ', 'ㅒ', 'ㅓ', 'ㅔ', 'ㅕ', 'ㅖ', 'ㅗ', 'ㅘ', 'ㅙ', 'ㅚ', 'ㅛ', 'ㅜ', 'ㅝ', 'ㅞ', 'ㅟ', 'ㅠ', 'ㅡ', 'ㅢ', 'ㅣ'};
 private static final char [] JONG_SUNG = {'\0', 'ㄱ', 'ㄲ', 'ㄳ', 'ㄴ', 'ㄵ', 'ㄶ', 'ㄷ', 'ㄹ', 'ㄺ', 'ㄻ', 'ㄼ', 'ㄽ', 'ㄾ', 'ㄿ', 'ㅀ', 'ㅁ', 'ㅂ', 'ㅄ', 'ㅅ', 'ㅆ', 'ㅇ', 'ㅈ', 'ㅊ', 'ㅋ', 'ㅌ', 'ㅍ', 'ㅎ'};
 
 public static String split(String word) {
  
  StringBuilder sb = new StringBuilder();
  
  char [] charArr = word.toCharArray();
  int a, b, c;
  
  for (char ch : charArr) {
   
   if ('가' <= ch && ch <= '힣') {
    
    int temp = ch - '가';
    a = temp / (21 * 28); // 초성
    c = temp % (21 * 28);
    b = c / 28; // 중성
    c = c % 28; // 조성
    
    sb.append(CHO_SUNG[a]).append(JWUNG_SUNG[b]);
    
    if (c != 0) {
     sb.append(JONG_SUNG[c]);
    }
   } else {
    sb.append(ch);
   }
  }
  
  return sb.toString();
 }
}

EditDistance.java

/**
 * 편집거리를 구하기 위한 클래스입니다.
 *  - JasoTokenizer 클래스가 필요합니다.
 */
public class EditDistance {
 
 /**
  * 편집거리를 구하기 위한 알고리즘으로 levenshtein distance 알고리즘을 사용합니다.
  *  - 한글의 다차원 특성상 자소분리를 통해 거리를 측정합니다.
  * 
  * @param word1
  * @param word2
  * @return
  */
 public int levenshteinDistance(String word1, String word2) {
  
  System.out.print(word1 +" | "+ word2 + " = ");
  
  word1 = JasoTokenizer.split(word1);
  word2 = JasoTokenizer.split(word2);
  
  int word1_len = word1.length() + 1;
  int word2_len = word2.length() + 1;
  int cost = 0;
  
  if (word1.equals(word2)) {
   return 0;
  }
  
  int [][] costMatrix = initCostMatrix(word1_len, word2_len);
  
  for (int j = 1; j < word2_len; j++) {
   for (int i = 1; i < word1_len; i++) {
    if (word1.charAt(i-1) == word2.charAt(j-1)) {
     cost = 0;
    } else {
     cost = 1;
    }
    costMatrix[i][j] = minimum(costMatrix[i - 1][j] + 1,
           costMatrix[i][j - 1] + 1,
           costMatrix[i - 1][j - 1] + cost);
   }
  }
  
  // displayCostMatrix(costMatrix);
  
  return costMatrix[word1_len - 1][word2_len - 1];
 }
 
 private void displayCostMatrix(int [][] costMatrix) {
  
  for (int i = 0; i < costMatrix.length; i++) {
   for (int j = 0; j < costMatrix[i].length; j++) {
    System.out.print(costMatrix[i][j] + "\t");
   }
   System.out.println();
  }
 }
 
 private int [][] initCostMatrix(int word1_len, int word2_len) {
  
  int [][] costMatrix = new int [word1_len][word2_len];
  
  for (int i = 1; i < word1_len; i++) {
   costMatrix[i][0] = i;
  }
  
  for (int i = 1; i < word2_len; i++) {
   costMatrix[0][i] = i;
  }
  
  return costMatrix;
 }
 
 private int minimum(int arg1, int arg2, int arg3) {
  
  int minimum = 100000;
  
  if (arg1 == arg2 && arg2 == arg3) {
   minimum = arg1;
  }
  
  if (arg1 < arg2 || arg1 < arg3) {
   minimum = arg1;
  }
  
  if (arg2 < arg1 || arg2 < arg3) {
   minimum = arg2;
  }
  
  if (arg3 < arg1 || arg3 < arg2) {
   minimum = arg3;
  }
  
  return minimum;
 }
}