[Levenshtein] 편집거리 알고리즘

신조어..

물고기 아님 먹는거 아님  우리회사에서 불사의 프로젝트로 영생을 누리고 있는 프로젝트

 

상품명에서 키워드를 조회해서 신조어로 등록될 만한 단어들을 선별해야 하는데 ngram 으로 Mysql DB 조회를 하려고 했으나 DBA 이방지의 반대가 심해서 다른방법을 찾는 중..

 

배치시간 12시간에서 1시간 내 실행으로 변경해야지만 운영환경에 올라갈 수 있다. 

어뷰징 키워드 제거, 중복제거를 했으나.. 3시간 이상 소요되는 배치

 

데이터를 살펴보니 

 

고구마맛 200ml, 고구마맛 300ml, 고구마맛 500ml 이런식으로 옵션상품들이 많이 있는데 이것들을 모두 조회하는 것은 리소스 낭비이고 배치시간이 길어지는 이유이다. 그래서 이것들은 한번만 조회 하는 방법으로 변경하려고 한다. 

 

근데 이것을 어떻게 구분한담...

 

완벽한 필터링은 아니지만 편집거리 알고리즘을 사용해서 모수를 줄여보자. 

 

편집 거리(Levenshtein distance) 알고리즘은 두 개의 문자열 사이의 유사도를 측정하는 방법 중 하나입니다. 이 알고리즘은 두 문자열 사이의 최소 편집 연산 횟수를 계산하여 이를 거리로 표현합니다. 여기서 편집 연산은 문자열에 적용되는 다음 세 가지 연산 중 하나입니다:

1. 삽입: 한 문자를 다른 문자열에 삽입합니다.
2. 삭제: 한 문자를 문자열에서 삭제합니다.
3. 대체: 한 문자를 다른 문자로 대체합니다.

이 알고리즘은 다이내믹 프로그래밍 기법을 사용하여 구현됩니다. 문자열 A와 문자열 B의 길이가 각각 m과 n일 때, 시간 복잡도는 O(m*n)입니다.

 

 

char[] stringA = "고구마맛 200ml".toCharArray();
char[] stringB = "고구마맛 300ml".toCharArray();

 

편집거리 : 1

 

이런식으로 두 단어의 차이를 편집거리로 판단 할 수 있는데 기준을 잡아서 필터링 하는 방법으로 진행 

package com.doo.aqqle.algorithm;

public class Levenshtein {
    public int getMinimum(int val1, int val2, int val3) {
        int minNumber = val1;
        if(minNumber > val2) minNumber = val2;
        if(minNumber > val3) minNumber = val3;
        return minNumber;
    }

    public int levenshteinDistance(char[] s, char[] t) {
        int m = s.length;
        int n = t.length;

        int[][] d = new int[m + 1][n + 1];

        for (int i = 1; i < m; i++) {
            d[i][0] = i;
        }

        for (int j = 1; j < n; j++) {
            d[0][j] = j;
        }

        for (int j = 1; j < n; j++) {
            for (int i = 1; i < m; i++) {
                if (s[i] == t[j]) {
                    d[i][j] = d[i - 1][j - 1];
                } else {
                    d[i][j] = getMinimum(d[i - 1][j], d[i][j - 1], d[i - 1][j - 1]) + 1;
                }
            }
        }
        return d[m - 1][n - 1];
    }

    public void runAlgorithm() {

        char[] stringA = "고구마맛 200ml".toCharArray();
        char[] stringB = "고구마맛 300ml".toCharArray();

        int result = levenshteinDistance(stringA, stringB);
        System.out.println(result);
    }

    public static void main(String[] args) {
        new Levenshtein().runAlgorithm();
    }
}