레벤슈타인 거리(Levenshtein distance) 알고리즘: 텍스트 유사도 측정

레벤슈타인 거리 알고리즘은 두 문자열 사이의 편집 거리를 측정해 문자열 간의 유사도를 계산하는 비트윈 스캔 방법입니다. 주로 텍스트 편집기, 자동 완성 기능, 검색 엔진 등에서 널리 사용됩니다. 이 글에서는 레벤슈타인 거리 알고리즘의 원리와 이를 활용하는 방법, 그리고 파이썬을 이용한 구현 방법을 알아보겠습니다.

레벤슈타인 거리의 원리

레벤슈타인 거리란 두 문자열 사이에서 하나의 문자열을 다른 문자열로 변환하기 위해 필요한 최소한의 편집 작업 수를 말합니다. 여기서 편집 작업은 삽입, 삭제, 교체 세 가지로 정의됩니다. 예를 들어 문자열 "kitten"을 "sitting"으로 변환하려면 다음과 같은 작업이 필요합니다:

1. "kitten"에서 "sitten"으로 (k를 s로 교체)
2. "sitten"에서 "sittin"으로 (e를 i로 교체)
3. "sittin"에서 "sitting"으로 (n을 추가)

따라서 이 경우 레벤슈타인 거리는 3입니다.

레벤슈타인 거리의 계산 방법

레벤슈타인 거리를 계산하기 위해 동적 프로그래밍(Dynamic Programming) 기법을 사용합니다. 이를 위해 2차원 배열을 활용하며, 각 셀 [i][j]는 첫 번째 문자열의 처음 i 문자와 두 번째 문자열의 처음 j 문자 사이의 편집 거리를 나타냅니다. 배열은 다음과 같은 방식으로 채워집니다:

1. 첫 번째 행과 첫 번째 열은 인덱스를 따라 채워집니다. 즉, distance[i][0] = i 그리고 distance[0][j] = j입니다.
2. 나머지 셀 [i][j]는 다음 중 가장 작은 값으로 채워집니다:
   • distance[i-1][j] + 1 (삭제 연산)
   • distance[i][j-1] + 1 (삽입 연산)
   • distance[i-1][j-1] + cost, 여기서 cost는 문자가 같으면 0, 다르면 1입니다 (교체 연산).

파이썬을 이용한 구현 사례

레벤슈타인 거리를 파이썬으로 구현하는 예제를 살펴보겠습니다.

python
def levenshtein_distance(str1, str2):
    n, m = len(str1), len(str2)
    if n == 0: return m
    if m == 0: return n

    # Create a matrix to store the distances
    dist = [[0 for _ in range(m + 1)] for _ in range(n + 1)]

    # Initialize the matrix
    for i in range(n + 1):
        dist[i][0] = i
    for j in range(m + 1):
        dist[0][j] = j

    # Calculate distances
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if str1[i - 1] == str2[j - 1]:
                cost = 0
            else:
                cost = 1

            dist[i][j] = min(dist[i - 1][j] + 1,    # Deletion
                             dist[i][j - 1] + 1,    # Insertion
                             dist[i - 1][j - 1] + cost) # Substitution

    return dist[n][m]

# Test the function
str1 = "kitten"
str2 = "sitting"
print(f"Levenshtein distance between '{str1}' and '{str2}' is {levenshtein_distance(str1, str2)}")

위 코드에서 levenshtein_distance 함수는 두 문자열을 입력으로 받아 최소 편집 거리를 반환합니다. 동적 프로그래밍을 통해 각 위치까지의 거리를 계산하고, 최종적으로 가장 오른쪽 아래 셀의 값을 반환합니다.

레벤슈타인 거리의 적용 사례

텍스트 편집기

텍스트 편집기에서는 철자 검사, 자동 완성 기능, 텍스트 비교 등을 위해 레벤슈타인 거리를 활용할 수 있습니다. 예를 들어, 사용자가 잘못된 철자를 입력했을 때 가장 유사한 대안을 제시할 수 있습니다.

검색 엔진

검색 엔진은 사용자가 입력한 검색 쿼리와 데이터베이스의 저장된 문서 간의 유사도를 측정하는 데 레벤슈타인 거리를 사용할 수 있습니다. 이를 통해 사용자가 오타를 입력했을 때에도 관련된 검색 결과를 반환할 수 있습니다.

생물정보학

서열 분석에 활용됩니다. DNA, RNA, 단백질 서열 간의 차이를 분석하여 생물학적 유사성을 평가하는 데 레벤슈타인 거리 알고리즘이 사용됩니다.

결론

레벤슈타인 거리 알고리즘은 텍스트 유사도 계산에 있어 매우 유용한 도구입니다. 삽입, 삭제, 교체와 같은 편집 작업을 통해 두 문자열 간의 유사도를 정량적으로 평가할 수 있으며, 이를 근거로 다양한 응용 분야에서 활용할 수 있습니다. 동적 프로그래밍을 기반으로 한 알고리즘 구현 방법도 비교적 간단하므로, 다양한 프로그래밍 언어에서 쉽게 적용할 수 있습니다.