1. 소개

이 기사에서는 편집 거리라고도하는 Levenshtein 거리를 설명합니다. 여기에 설명 된 알고리즘은 1965 년 러시아 과학자 Vladimir Levenshtein이 고안했습니다.

우리는이 알고리즘의 반복적이고 재귀적인 자바 구현을 제공 할 것입니다.

2. Levenshtein 거리는 얼마입니까?

Levenshtein 거리 둘 사이의 유사성의 측정은 현악기. 수학적으로 두 개의 문자열 x 및 y가 주어지면 거리는 x 를 y 로 변환하는 데 필요한 최소 문자 편집 수를 측정합니다 .

일반적으로 세 가지 유형의 편집이 허용됩니다.

  1. 문자 c 삽입
  2. 문자 c 삭제
  3. 문자 c 를 c '로 대체

예 : 만약 X = '샷' 및 Y = '지점' 때문에 둘 사이의 편집 거리가 1 "샷이 ' 로 변환 할 수 '스폿 ' '로 치환함으로써 H '에서' P를 '.

문제의 특정 하위 클래스에서는 각 편집 유형과 관련된 비용이 다를 수 있습니다.

예를 들어 키보드 근처에있는 문자로 대체하는 데 드는 비용이 적고 그렇지 않으면 더 많은 비용이 듭니다. 간단하게하기 위해이 기사에서는 모든 비용이 동일하다고 간주합니다.

편집 거리의 일부 응용 프로그램은 다음과 같습니다.

  1. 맞춤법 검사기 – 텍스트에서 맞춤법 오류를 감지하고 사전에서 가장 가까운 올바른 맞춤법을 찾습니다.
  2. 표절 탐지 (참조 – IEEE 논문 )
  3. DNA 분석 – 두 서열 간의 유사성 찾기
  4. 음성 인식 (참조 – Microsoft Research )

3. 알고리즘 공식화

각각 길이가 m 과 n 인 두 개의 문자열 x 와 y 를 봅시다 . 각 문자열 을 x [1 : m] 및 y [1 : n]으로 표시 할 수 있습니다.

변환이 끝날 때 두 문자열 의 길이가 같고 각 위치에 일치하는 문자가 있음을 알고 있습니다. 따라서 각 문자열 의 첫 번째 문자를 고려하면 세 가지 옵션이 있습니다.

  1. 치환:
    1. x [1] 을 y [1] 로 대체 하는 비용 ( D1 )을 결정합니다 . 두 문자가 같으면이 단계의 비용은 0이됩니다. 그렇지 않은 경우 비용은 1이됩니다.
    2. 1.1 단계 이후에는 두 문자열 이 동일한 문자로 시작 한다는 것을 알고 있습니다. 따라서 총 비용은 이제 1.1 단계의 비용과 나머지 문자열 x [2 : m] 을 y [2 : n] 으로 변환하는 비용의 합계가 됩니다 .
  2. 삽입:
    1. y 의 첫 번째 문자와 일치하도록 x 에 문자를 삽입합니다. 이 단계의 비용은 1입니다.
    2. 2.1 이후, 우리는 y 에서 하나의 문자를 처리했습니다 . 따라서 총 비용은 이제 2.1 단계의 비용 (즉, 1)과 전체 x [1 : m] 을 나머지 y (y [2 : n]) 로 변환하는 비용의 합계가됩니다.
  3. 삭제:
    1. x 에서 첫 번째 문자를 삭제하면 이 단계의 비용은 1이됩니다.
    2. 3.1 이후에는 x 에서 하나의 문자를 처리 했지만 전체 y 는 처리해야합니다. 총 비용은 3.1 비용 (즉, 1)과 나머지 x 를 전체 y 로 변환하는 비용의 합계입니다.

솔루션의 다음 부분은이 세 가지 중에서 선택할 옵션을 파악하는 것입니다. 어떤 옵션이 결국 최소 비용으로 이어질지 모르기 때문에 모든 옵션을 시도하고 가장 좋은 옵션을 선택해야합니다.

4. 순진한 재귀 구현

섹션 # 3의 각 옵션의 두 번째 단계는 거의 동일한 편집 거리 문제이지만 원래 문자열의 하위 문자열에 있음을 알 수 있습니다. 이것은 각 반복 후에 동일한 문제가 발생하지만 더 작은 문자열로 끝남을 의미 합니다.

이 관찰은 재귀 알고리즘을 공식화하는 열쇠입니다. 되풀이 관계는 다음과 같이 정의 할 수 있습니다.

D (x [1 : m], y [1 : n]) = min {

D (x [2 : m], y [2 : n]) + x [1]을 y [1]로 대체하는 비용,

D (x [1 : m], y [2 : n]) + 1,

D (x [2 : m], y [1 : n]) + 1

}

또한 재귀 알고리즘에 대한 기본 케이스를 정의해야합니다.이 경우에는 하나 또는 두 개의 문자열 이 모두 비어있는 경우입니다.

  1. 두 문자열 이 모두 비어 있으면 두 문자열 사이의 거리가 0입니다.
  2. 문자열 중 하나 가 비어있는 경우 하나를 다른 문자열 로 변환하려면 많은 수의 삽입 / 삭제가 필요하므로 문자열 간의 편집 거리는 다른 문자열 의 길이입니다 .
    • 예 : 하나가 문자열 인 "개" 등의 문자열 입니다 "" (빈), 우리가 하나 비어있는 세 가지 삽입 필요 문자열 을 만들기 위해 개 "" , 또는 우리가 세 가지 삭제해야합니다 ""개를 비어 있도록. 따라서 그들 사이의 편집 거리는 3입니다.

이 알고리즘의 순진한 재귀 구현 :

public class EditDistanceRecursive {

   static int calculate(String x, String y) {
        if (x.isEmpty()) {
            return y.length();
        }

        if (y.isEmpty()) {
            return x.length();
        } 

        int substitution = calculate(x.substring(1), y.substring(1)) 
         + costOfSubstitution(x.charAt(0), y.charAt(0));
        int insertion = calculate(x, y.substring(1)) + 1;
        int deletion = calculate(x.substring(1), y) + 1;

        return min(substitution, insertion, deletion);
    }

    public static int costOfSubstitution(char a, char b) {
        return a == b ? 0 : 1;
    }

    public static int min(int... numbers) {
        return Arrays.stream(numbers)
          .min().orElse(Integer.MAX_VALUE);
    }
}

이 알고리즘은 기하 급수적으로 복잡합니다. 각 단계에서 우리는 3 개의 재귀 호출로 분기하여 O (3 ^ n) 복잡성을 구축합니다.

다음 섹션에서는이를 개선하는 방법을 살펴 보겠습니다.

5. 동적 프로그래밍 접근법

재귀 호출을 분석 할 때 하위 문제에 대한 인수가 원래 문자열의 접미사임을 관찰합니다 . 이는 m * n 개의 고유 한 재귀 호출 만있을 수 있음을 의미 합니다 (여기서 m 및 n 은 x 및 y 의 접미사 수 ). 따라서 최적 솔루션의 복잡성은 2 차 O (m * n) 이어야합니다 .

몇 가지 하위 문제를 살펴 보겠습니다 (섹션 # 4에 정의 된 반복 관계에 따라).

  1. D (x [1 : m], y [1 : n]) 의 하위 문제 는 D (x [2 : m], y [2 : n]), D (x [1 : m], y [2 : n]) 및 D (x [2 : m], y [1 : n])
  2. D (x [1 : m], y [2 : n]) 의 하위 문제 는 D (x [2 : m], y [3 : n]), D (x [1 : m], y [3 : n]) 및 D (x [2 : m], y [2 : n])
  3. D (x [2 : m], y [1 : n]) 의 하위 문제 는 D (x [3 : m], y [2 : n]), D (x [2 : m], y [2 : n]) 및 D (x [3 : m], y [1 : n])

세 가지 경우 모두 하위 문제 중 하나는 D (x [2 : m], y [2 : n])입니다. 순진한 구현 에서처럼 이것을 세 번 계산하는 대신 한 번 계산하고 다시 필요할 때마다 결과를 재사용 할 수 있습니다.

이 문제는 중복되는 하위 문제가 많지만 하위 문제에 대한 해결책을 안다면 원래 문제에 대한 답을 쉽게 찾을 수 있습니다. 따라서 우리는 동적 프로그래밍 솔루션을 공식화하는 데 필요한 두 가지 속성, 즉 Overlapping Sub-Problems 및 Optimal Substructure를 모두 가지고 있습니다.

메모 화 를 도입하여 순진한 구현을 최적화 할 수 있습니다 . 즉, 하위 문제의 결과를 배열에 저장하고 캐시 된 결과를 재사용 할 수 있습니다.

또는 테이블 기반 접근 방식을 사용하여 반복적으로 구현할 수도 있습니다.

static int calculate(String x, String y) {
    int[][] dp = new int[x.length() + 1][y.length() + 1];

    for (int i = 0; i <= x.length(); i++) {
        for (int j = 0; j <= y.length(); j++) {
            if (i == 0) {
                dp[i][j] = j;
            }
            else if (j == 0) {
                dp[i][j] = i;
            }
            else {
                dp[i][j] = min(dp[i - 1][j - 1] 
                 + costOfSubstitution(x.charAt(i - 1), y.charAt(j - 1)), 
                  dp[i - 1][j] + 1, 
                  dp[i][j - 1] + 1);
            }
        }
    }

    return dp[x.length()][y.length()];
}

이 알고리즘은 재귀 구현보다 훨씬 더 잘 수행됩니다. 그러나 상당한 메모리 소비가 수반됩니다.

이것은 현재 셀의 값을 찾기 위해 테이블에서 세 개의 인접한 셀의 값만 필요하다는 것을 관찰함으로써 더욱 최적화 할 수 있습니다.

6. 결론

이 기사에서는 Levenshtein 거리가 무엇이며 재귀 및 동적 프로그래밍 기반 접근 방식을 사용하여 계산할 수있는 방법을 설명했습니다.

Levenshtein 거리는 문자열 유사성의 척도 중 하나 일 뿐이며, 다른 메트릭 중 일부는 코사인 유사성 (토큰 기반 접근 방식을 사용하고 문자열을 벡터로 간주), 주사위 계수 등입니다.

항상 그렇듯이 전체 예제 구현은 GitHub 에서 찾을 수 있습니다 .