편집 거리 (Levenshtein Distance)

한 문자열을 다른 문자열로 바꾸는 데 필요한 삽입·삭제·교체의 최소 횟수 — 맞춤법 검사, 자동완성, diff, DNA 정렬의 핵심

휴대폰에 recieve라고 치면 receive로 고쳐 주고, Git이 git stauts 대신 status를 제안하는 이유는 무엇일까? 컴퓨터는 두 단어가 "얼마나 비슷한지"를 편집 거리라는 숫자로 잰다. 편집 거리는 글자 하나 삽입 / 글자 하나 삭제 / 글자 하나 교체 세 가지 연산만 써서 단어 A를 단어 B로 만들 때 필요한 최소 연산 횟수다. 예를 들어 kitten → sitting 은 3 (k→s 교체, e→i 교체, 끝에 g 삽입).

직접 계산해 보기

단어 A (출발)

단어 B (도착)

kitten / sitting recieve / receive sunday / saturday intention / execution AGCTA / AGTCA (DNA) 가나다라 / 가마다바

DP 표 (동적 계획법 행렬)

칸 D[i][j] = "A의 앞 i글자"를 "B의 앞 j글자"로 바꾸는 최소 편집 거리. 각 칸은 왼쪽·위·왼쪽위 세 이웃에서만 계산된다.

지금 채우는 칸 역추적 경로(최적 선택) 정답 = 오른쪽 아래 칸

점화식 — 세 이웃 중 최솟값

D[i][0] = i  # A의 i글자를 빈 문자열로 → i번 삭제
D[0][j] = j  # 빈 문자열에서 B의 j글자 → j번 삽입

D[i][j] = min(
  D[i-1][j]   + 1,    # 위칸: A[i] 삭제
  D[i][j-1]   + 1,    # 왼칸: B[j] 삽입
  D[i-1][j-1] + (A[i] == B[j] ? 0 : 1)  # 대각선: 교체 또는 그대로
)

표를 왼쪽 위에서 오른쪽 아래로 한 칸씩 채우면, 이미 계산해 둔 이웃 값만 재활용하므로 각 칸은 O(1)에 정해진다. 표 크기가 (m+1) × (n+1) 이므로 전체 시간·공간은 O(m·n). 완성된 표의 오른쪽 아래 칸이 답이고, 거기서 "어느 이웃을 골랐는지" 거꾸로 따라가면 실제 연산 순서(정렬)를 복원할 수 있다.

세 가지 연산

연산	표에서의 이동	예시
교체(substitute)	대각선 ↖ (글자 다르면 +1)	`cat → cut`
일치(match)	대각선 ↖ (글자 같으면 +0)	`cat → cat`
삽입(insert)	왼쪽 ← (B의 글자 추가, +1)	`cat → cart`
삭제(delete)	위 ↑ (A의 글자 제거, +1)	`cart → cat`

어디에 쓰일까

맞춤법 검사·자동완성 — 사전 단어들과 편집 거리를 재서 가장 가까운 후보를 추천
diff / git — 두 파일(줄 단위)의 최소 편집 스크립트를 구해 변경 부분만 표시
DNA·단백질 서열 정렬 — 생물정보학의 Needleman–Wunsch가 편집 거리의 일반화(가중치 버전)
검색어 오타 보정 — "이거 찾으셨나요?" 추천
OCR·음성 인식 정확도 평가 — 정답 대비 WER(단어 오류율) = 편집 거리 ÷ 단어 수

파이썬 구현

# O(m*n) 시간, O(n) 공간 (한 줄만 유지)
def edit_distance(a, b):
    m, n = len(a), len(b)
    prev = list(range(n + 1))          # D[0][j] = j
    for i in range(1, m + 1):
        cur = [i] + [0] * n            # D[i][0] = i
        for j in range(1, n + 1):
            cost = 0 if a[i-1] == b[j-1] else 1
            cur[j] = min(
                prev[j] + 1,           # 삭제
                cur[j-1] + 1,          # 삽입
                prev[j-1] + cost,      # 교체/일치
            )
        prev = cur
    return prev[n]

print(edit_distance("kitten", "sitting"))  # 3

※ 위 데모는 전체 표를 저장해 역추적(정렬)까지 보여주므로 O(m·n) 공간을 쓴다. 거리 값만 필요하면 코드처럼 두 줄만 있으면 된다.

한양과학기술고등학교