Levenshtein 거리

AI
qwen-3-235b-a22b-instruct-2507
작성자
익명
작성일
2025.09.06
조회수
10
버전
v2
기술 → 자연어처리 → 편집 거리
Levenshtein 거리 편집 거리 동적 프로그래밍 자연어처리 철자 교정

📋 문서 버전

이 문서는 2개의 버전이 있습니다. 현재 최신 버전을 보고 있습니다.

Levenshtein리

Levenshtein 거리(venshtein Distance)는 두열 간의 유사도를 측정하는 데 사용되는 편집 거리(Edit Distance)의 한 형태로, 1965년 러시아 수학자 블라디미르 레벤슈타인(Vladimir Levenshtein)에 의해 제안되었습니다. 이 거리는 하나의 문자열을 다른 문자열로 변환하기 위해 필요한 최소 편집 횟수를 계산하며, 자연어처리(NLP), 철자 교정, 유전자 서열 분석, 음성 인식 등 다양한 분야에서 널리 활용됩니다.

개요

Levenshtein 거리는 두 문자열이 얼마나 "비슷한지"를 정량적으로 평가하는 지표입니다. 이 거리가 작을수록 두 문자열은 유사하며, 0일 경우 완전히 동일한 문자열입니다. 허용되는 편집 연산은 다음 세 가지입니다:

  1. 삽입(Insertion): 문자 하나를 추가
  2. 삭제(Deletion): 문자 하나를 제거
  3. 치환(Substitution): 문자 하나를 다른 문자로 변경

예를 들어, 문자열 kitten을 sitting으로 바꾸기 위해 다음과 같은 3단계가 필요합니다:

  1. k → s (치환): sitten
  2. e → i (치환): sittin
  3. g 삽입: sittin → sitting

따라서 kitten과 sitting의 Levenshtein 거리는 3입니다.

알고리즘 원리

Levenshtein 거리는 동적 프로그래밍(Dynamic Programming) 기법을 사용하여 효율적으로 계산됩니다. 두 문자열 A와 B의 길이를 각각 m과 n이라고 할 때, m×n 크기의 2차원 배열 dp[i][j]를 생성하여 부분 문제의 최적해를 저장합니다.

점화식 (Recurrence Relation)

배열 dp[i][j]는 문자열 A[0..i-1]과 B[0..j-1] 사이의 Levenshtein 거리를 의미합니다. 점화식은 다음과 같습니다:

dp[i][j] = 
  if i == 0: j
  if j == 0: i
  else:
    min(
      dp[i-1][j] + 1,           // 삭제
      dp[i][j-1] + 1,           // 삽입
      dp[i-1][j-1] + cost       // 치환 (cost = 0 if A[i-1]==B[j-1], else 1)
    )

초기 조건: - dp[0][j] = j: 빈 문자열에서 B의 j번째 문자까지 만들기 위해 j번 삽입 필요 - dp[i][0] = i: A의 i번째 문자까지를 빈 문자열로 만들기 위해 i번 삭제 필요

예시 계산

A = "cat", B = "car"일 경우:

c a t
0 1 2 3
c 1 0 1 2
a 2 1 0 1
r 3 2 1 1
  • t → r 치환: 1회 연산
  • 최종 거리: 1

응용 분야

1. 철자 교정 (Spelling Correction)

사용자가 입력한 단어가 사전에 없을 경우, 사전 내 단어들과의 Levenshtein 거리를 계산하여 가장 가까운 단어를 제안합니다. 예: recieve → receive (거리: 1)

2. 자연어처리 (NLP)

3. 생물정보학 (Bioinformatics)

DNA 또는 단백질 서열 간 유사도 분석에 활용. 삽입, 삭제, 치환은 유전자 변이를 모델링할 수 있음.

4. 데이터 정제 및 중복 제거

데이터베이스 내 유사한 이름, 주소 등을 비교하여 중복 레코드를 식별하고 병합.

변형 및 관련 개념

  • Damerau-Levenshtein 거리: Levenshtein 거리에 문자 교환(Transposition) 연산을 추가. 예: hte → the (1회 교환)
  • Jaro-Winkler 거리: 주로 이름 매칭에 사용되며, 문자 순서와 일치 여부에 가중치를 둠.
  • Hamming 거리: 길이가 같은 두 문자열에서 서로 다른 위치의 문자 수. 삽입/삭제 불가.
  • 확률 기반 편집 거리: 각 편집 연산에 비용(확률)을 부여하여 더 현실적인 모델링.

구현 예시 (Python)

def levenshtein_distance(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - ]:
                cost = 0
            else:
                cost = 1
            dp[i][j] = min(
                dp[i - 1][j] + 1,      # 삭제
                dp[i][j - 1] + 1,      # 삽입
                dp[i - 1][j - 1] + cost  # 치환
            )
    
    return dp[m][n]

# 사용 예
print(levenshtein_distance("kitten", "sitting"))  # 출력: 3

참고 자료 및 관련 문서

Levenshtein 거리는 단순하면서도 강력한 개념으로, 문자열 비교의 기본 도구로 자리 잡고 있습니다. 특히 자연어처리 분야에서는 오류 정정, 유사 문장 탐지, 정보 검색 등에서 핵심적인 역할을 수행합니다.

AI 생성 콘텐츠 안내

이 문서는 AI 모델(qwen-3-235b-a22b-instruct-2507)에 의해 생성된 콘텐츠입니다.

주의사항: AI가 생성한 내용은 부정확하거나 편향된 정보를 포함할 수 있습니다. 중요한 결정을 내리기 전에 반드시 신뢰할 수 있는 출처를 통해 정보를 확인하시기 바랍니다.

이 AI 생성 콘텐츠가 도움이 되었나요?