[Java] 문자열의 유사도 구하기 : 거리 알고리즘

Levenshtein Distance Algorithm

 

실전 프로젝트 중, 유튜브 영상을 검색해 관련성 있는 영상을 가져오는 기능을 구현하던 중 문제가 발생했다.

유튜브 영상의 검색결과가 생각보다 그렇게 관련성이 높은 결과가 잘 나오지 않는다는 점이었다.

키워드와 거의 정확히 관련이 있는 영상만 가져와야 하는 상황이었기 때문에 이것은 꽤나 심각한 문제였다. 그래서 대책을 강구하기 시작했다.

그렇게 생각하던 중, 제목이 유사한 영상을 채택한다면 일반적으로 꽤나 높은 신뢰도의 영상을 서치할 수 있게 될 것이라고 생각했다. 그래서 찾은 것이 문자열의 유사도를 구하는 알고리즘이었다.

 

내가 채택한 알고리즘은 레벤슈타인 거리 알고리즘(Levenshtein distance algorithm) 이었다. 이 알고리즘은 문장의 유사도를 0~1 사이의 실수로 표시해주는 알고리즘이다. 이 알고리즘을 선택한 이유는 구현 방식이 단순해서였다. 시간상의 이유로 코드는 복붙으로 사용하겠지만, 그 로직은 이해해야 하지 않겠는가. 그래서 가져다 쓸 수 있는 것 중 이해가 가장 쉽다고 생각되는 것을 선택했다.

 

코드는 아래의 블로그를 참조했다.

[Java] 두 문자열간의 유사도 구하기 – GIS Developer

 

private double similarity(String s1, String s2) {
        String longer = s1, shorter = s2;

        if (s1.length() < s2.length()) {
            longer = s2;
            shorter = s1;
        }

        int longerLength = longer.length();
        if (longerLength == 0) return 1.0;
        return (longerLength - editDistance(longer, shorter)) / (double) longerLength;
    }

    private int editDistance(String s1, String s2) {
        s1 = s1.toLowerCase();
        s2 = s2.toLowerCase();
        int[] costs = new int[s2.length() + 1];

        for (int i = 0; i <= s1.length(); i++) {
            int lastValue = i;
            for (int j = 0; j <= s2.length(); j++) {
                if (i == 0) {
                    costs[j] = j;
                } else {
                    if (j > 0) {
                        int newValue = costs[j - 1];

                        if (s1.charAt(i - 1) != s2.charAt(j - 1)) {
                            newValue = Math.min(Math.min(newValue, lastValue), costs[j]) + 1;
                        }

                        costs[j - 1] = lastValue;
                        lastValue = newValue;
                    }
                }
            }

            if (i > 0) costs[s2.length()] = lastValue;
        }

        return costs[s2.length()];
    }

원리는 간단하다. 두 개의 문자열을 입력받아 둘의 유사도에 따른 가중치를 계산해 출력해주는 알고리즘이다. 이것을 이용해 연관성 있는 영상 중 더 연관성 있는 내용을 출력해낼 수 있을 것이다.

 

내가 이 알고리즘을 활용한 방식은 다음과 같다.

 

1. Youtube Data API v3을 활용해 영상 검색 결과를 받아온다.

2. 그 중 제목이 내가 입력한 키워드와 일치하도록 한 번 더 필터링한다.

 

이게 끝이다.

하지만 끝은 아니다. 왜냐면 이 알고리즘은 문자열의 길이의 차이도 인식하기 때문이었다. 그렇기 때문에 검색어와 영상의 제목을 매칭시키기 위해 추가로 필요 없는 문자열을 제거하고 비교에 필요한 문자열끼리만 비교하기 위한 코드도 필요할 것이다. 이 코드는 여백이 부족해 적지 않겠다. 내가 적은 코드가 너무 부끄러워서 안 적는거 맞으니까 나보다 머리가 좋은 독자들은 더 지혜롭게 이 문제를 풀어나갈 수 있길 바라겠다. 그름 이만. 국그릇핑크퐁~