한글 Levenshtein Distance 구현

'Levenshtein Distance 알고리즘'과 '한글 초성, 중성, 종성 분리'에 대해서 다뤘었는데요.

 

이 두 내용을 결합해서 Levenshtein Distance 알고리즘에서 한글을 사용할 수 있게 변경해보려해요.

 

우선 Levenshtein Distance 에서 한글을 썼을 때 문제가 되는 부분은 '수정(modify)' 연산인데요.

 

영어 알파벳과 달리 한글은 초성, 중성, 종성으로 이루어져있기 때문이예요.

 

'햇볕' -> '해변' 으로 수정하는 비용과 '태양' -> '기차' 로 수정하는 비용을 서로 다르게 보는거죠.

 

그래서 기존 Levenshtein Distance 알고리즘의 수정연산에서 한글 글자를 초성, 중성, 종성으로 분리해서 얼만큼 바꿔야하는지 비용을 계산하는 부분이 새로 추가된다고 보시면 되요.

 

 

public double analyze() {
        double[][] editDistance = new double[s1.length() + 1][s2.length() + 1];

        for(int row=1;row<s1.length() + 1;row++) {
            editDistance[row][0] = row;
        }

        for(int col=1;col<s2.length() + 1;col++) {
            editDistance[0][col] = col;
        }

        for(int row = 1; row < s1.length() + 1; row++) {
            for (int col = 1; col < s2.length() + 1; col++) {
                // Skip
                if(s1.charAt(row-1) == s2.charAt(col-1)) {
                    editDistance[row][col] = editDistance[row-1][col-1];
                }
                // Modify
                else {
                    editDistance[row][col] = cutting(editDistance[row-1][col-1] + customModifyCost(s1.charAt(row-1), s2.charAt(col-1)));
                }
                // Insert
                if(editDistance[row][col-1] + 1 < editDistance[row][col]) {
                    editDistance[row][col] = editDistance[row][col-1] + 1;
                }
                // Delete
                if(editDistance[row - 1][col] + 1 < editDistance[row][col]) {
                    editDistance[row][col] = editDistance[row - 1][col] + 1;
                }
            }
        }

        return cutting(editDistance[s1.length()][s2.length()] / s2.length());
    }

 

 

Levenshtein Distance 글에서 구현했던 코드인데요. 크게 두 부분이 바뀌었어요.

 

하나는 수정(Modify) 연산 부분이고

editDistance[row][col] = cutting(editDistance[row-1][col-1] + customModifyCost(s1.charAt(row-1), s2.charAt(col-1)));

 

다른 하나는 리턴해주는 값의 소수점을 잘라주는 처리부분이예요.

return cutting(editDistance[s1.length()][s2.length()] / s2.length());

 

 

customModifyCost 함수는 사용자정의 수정비용계산 함수예요.

private double customModifyCost(char s1, char s2) {
        int s1Base = s1 - 44032;
        char s1Chosung = (char)(s1Base / 28 / 21);
        char s1Jungsung = (char)(s1Base / 28 % 21);
        char s1Jongsung = (char)(s1Base % 28);

        int s2Base = s2 - 44032;
        char s2Chosung = (char)(s2Base / 28 / 21);
        char s2Jungsung = (char)(s2Base / 28 % 21);
        char s2Jongsung = (char)(s2Base % 28);

        double cost = 0;
        if(s1Chosung != s2Chosung) cost += 0.4;
        if(s1Jungsung != s2Jungsung) cost += 0.3;
        if(s1Jongsung != s2Jongsung) cost += 0.3;

        return cutting(cost);
    }

 

코드를 보시면 s1 과 s2 의 한글을 분해하고 초성, 중성, 종성을 각각 비교해서 불일치할 경우 제가 정의한 비용만큼 합산되어서 최종 수정 연산의 비용을 리턴하게 되요.

 

 

그리고 최종적으로 얻은 결과값에서 s2 문자열의 길이만큼 나눠주게 되는데요.

 

그 이유는 s1, s2 를 세팅해줄 때 s1 의 문자열 길이보다 s2 의 문자열의 길이가 크거나 같도록 세팅해주었기 때문이예요.

public WordShapeSimilarityAnalyzer setBase(String s1, String s2) {
        String refinedS1 = s1.trim().replaceAll(" ", "");
        String refinedS2 = s2.trim().replaceAll(" ", "");

        if(refinedS1.length() <= refinedS2.length()) {
            this.s1 = refinedS1;
            this.s2 = refinedS2;
        } else {
            this.s1 = refinedS2;
            this.s2 = refinedS1;
        }

        return this;
    }

이렇게 세팅을 해주면 s1에서 s2로 바꾸는 연산의 횟수는 최대 s2의 문자열 길이만큼으로 제한되게 되요.

 

그래서 ' Levenshtein Distance / s2.length() ' 를 일반화된 유사도 비율값으로 쓸 수 있게되는 거예요.

 

그리고 추가적으로 Levenshtein Distance 결과값에 대해서 소수점 둘째자리에서 자르도록 처리했어요.

 

private double cutting(double value) {
        return Double.parseDouble(String.format("%.2f", value));
    }

 

 

이렇게 구현해주고 프로그램을 돌리면 아래와 같은 결과를 얻을 수 있어요.

public class Main {
    public static void main(String[] args) {
        WordShapeSimilarityAnalyzer analyzer = new WordShapeSimilarityAnalyzer();
        System.out.println(analyzer.setBase("따뜻한", "따스운").analyze());
    }
}

 

한글 단어간의 형태적 유사도 측정값으로 참고할 수 있을 것 같아요.

 

아래는 전체 코드 내용입니다.

 

public class Main {
    public static void main(String[] args) {
        WordShapeSimilarityAnalyzer analyzer = new WordShapeSimilarityAnalyzer();
        System.out.println(analyzer.setBase("따뜻한", "따스운").analyze());
        System.out.println(analyzer.setBase("사람은", "사랑은").analyze());
        System.out.println(analyzer.setBase("바다 보고싶다", "떠나고 싶다").analyze());
        System.out.println(analyzer.setBase(" 동일한 클래스 내의 다른 생성자에서 ", " 키워드를 사용하는 표현식은 생성자의 ").analyze());
        System.out.println(analyzer.setBase("힙한 건 뭘까", "힙합은 뭘까").analyze());
    }
}

public class WordShapeSimilarityAnalyzer {
    public String s1;
    public String s2;
    public final String[] chosungs;
    public final String[] jungsungs;
    public final String[] jongsungs;
    public final String[] jaums;
    public final String[] moums;

    public WordShapeSimilarityAnalyzer() {
        this.chosungs = new String[]{"ㄱ", "ㄲ", "ㄴ", "ㄷ", "ㄸ", "ㄹ", "ㅁ", "ㅂ", "ㅃ", "ㅅ", "ㅆ", "ㅇ" , "ㅈ", "ㅉ", "ㅊ", "ㅋ", "ㅌ", "ㅍ", "ㅎ"};
        this.jungsungs = new String[]{"ㅏ", "ㅐ", "ㅑ", "ㅒ", "ㅓ", "ㅔ", "ㅕ", "ㅖ", "ㅗ", "ㅘ", "ㅙ", "ㅚ", "ㅛ", "ㅜ", "ㅝ", "ㅞ", "ㅟ", "ㅠ", "ㅡ", "ㅢ", "ㅣ"};
        this.jongsungs = new String[]{"", "ㄱ", "ㄲ", "ㄳ", "ㄴ", "ㄵ", "ㄶ", "ㄷ", "ㄹ", "ㄺ", "ㄻ", "ㄼ", "ㄽ", "ㄾ", "ㄿ", "ㅀ", "ㅁ", "ㅂ", "ㅄ", "ㅅ", "ㅆ", "ㅇ", "ㅈ", "ㅊ", "ㅋ", "ㅌ", "ㅍ", "ㅎ"};
        this.jaums = new String[]{"ㄱ", "ㄲ", "ㄳ", "ㄴ", "ㄵ", "ㄶ", "ㄷ", "ㄸ", "ㄹ", "ㄺ", "ㄻ", "ㄼ", "ㄽ", "ㄾ", "ㄿ", "ㅀ", "ㅁ", "ㅂ", "ㅃ", "ㅄ", "ㅅ", "ㅆ", "ㅇ", "ㅈ", "ㅉ", "ㅊ", "ㅋ", "ㅌ", "ㅍ", "ㅎ"};
        this.moums = new String[]{"ㅏ", "ㅐ", "ㅑ", "ㅒ", "ㅓ", "ㅔ", "ㅕ", "ㅖ", "ㅗ", "ㅘ", "ㅙ", "ㅚ", "ㅛ", "ㅜ", "ㅝ", "ㅞ", "ㅟ", "ㅠ", "ㅡ", "ㅢ", "ㅣ"};
    }

    public WordShapeSimilarityAnalyzer setBase(String s1, String s2) {
        String refinedS1 = s1.trim().replaceAll(" ", "");
        String refinedS2 = s2.trim().replaceAll(" ", "");

        if(refinedS1.length() <= refinedS2.length()) {
            this.s1 = refinedS1;
            this.s2 = refinedS2;
        } else {
            this.s1 = refinedS2;
            this.s2 = refinedS1;
        }

        return this;
    }

    public double analyze() {
        double[][] editDistance = new double[s1.length() + 1][s2.length() + 1];

        for(int row=1;row<s1.length() + 1;row++) {
            editDistance[row][0] = row;
        }

        for(int col=1;col<s2.length() + 1;col++) {
            editDistance[0][col] = col;
        }

        for(int row = 1; row < s1.length() + 1; row++) {
            for (int col = 1; col < s2.length() + 1; col++) {
                // Skip
                if(s1.charAt(row-1) == s2.charAt(col-1)) {
                    editDistance[row][col] = editDistance[row-1][col-1];
                }
                // Modify
                else {
                    editDistance[row][col] = cutting(editDistance[row-1][col-1] + customModifyCost(s1.charAt(row-1), s2.charAt(col-1)));
                }
                // Insert
                if(editDistance[row][col-1] + 1 < editDistance[row][col]) {
                    editDistance[row][col] = editDistance[row][col-1] + 1;
                }
                // Delete
                if(editDistance[row - 1][col] + 1 < editDistance[row][col]) {
                    editDistance[row][col] = editDistance[row - 1][col] + 1;
                }
            }
        }

        print(editDistance, s1, s2);
        return cutting(editDistance[s1.length()][s2.length()] / s2.length());
    }

    private double customModifyCost(char s1, char s2) {
        int s1Base = s1 - 44032;
        char s1Chosung = (char)(s1Base / 28 / 21);
        char s1Jungsung = (char)(s1Base / 28 % 21);
        char s1Jongsung = (char)(s1Base % 28);

        int s2Base = s2 - 44032;
        char s2Chosung = (char)(s2Base / 28 / 21);
        char s2Jungsung = (char)(s2Base / 28 % 21);
        char s2Jongsung = (char)(s2Base % 28);

        double cost = 0;
        if(s1Chosung != s2Chosung) cost += 0.4;
        if(s1Jungsung != s2Jungsung) cost += 0.3;
        if(s1Jongsung != s2Jongsung) cost += 0.3;

        return cutting(cost);
    }

    private double cutting(double value) {
        return Double.parseDouble(String.format("%.2f", value));
    }

    private void print(double[][] editDistance, String s1, String s2) {
        for(int row=0;row<s1.length()+1;row++) {
            for (int col = 0; col < s2.length() + 1; col++) {
                System.out.print(editDistance[row][col] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
}

 

끝까지 읽어주셔서 감사합니다 :)

 

 

 

 

참고)

https://lovit.github.io/nlp/2018/08/28/levenshtein_hangle/

Levenshtein (edit) distance 를 이용한 한국어 단어의 형태적 유사성