레벤슈타인 거리(Levenshtein Distance)란? AI에서 삽입·삭제·대체로 문자열의 차이를 재는 방법

TL;DR

레벤슈타인 거리는 한 문자열을 다른 문자열로 바꾸는 데 필요한 삽입·삭제·대체의 최소 편집 횟수입니다. 기본 비용이 모두 1이면 같을 때 0이고 다른 부분이 많을수록 커집니다. AI가 읽은 짧은 텍스트나 오탈자 후보를 비교하는 데 쓰지만 의미의 유사도나 정답 확률은 아닙니다. 문자 단위·정규화·비용과 임계값의 반환 규칙을 함께 확인합니다.[1][2]

핵심 3줄 요약

• 핵심 1
  최소 편집 비용을 셉니다. 글자를 넣고 빼고 바꾸는 여러 경로 중 합계가 가장 작은 값을 구합니다.
• 핵심 2
  문자의 단위를 먼저 맞춥니다. 음절·자모·단어와 유니코드 표현이 달라지면 같은 화면의 글도 다른 입력이 됩니다.
• 핵심 3
  가까운 표기와 같은 뜻은 다릅니다. 적은 편집으로 부정 표현이나 금액이 달라질 수 있어 원문 검수가 필요합니다.

이 글에서 다룰 내용

레벤슈타인 거리를 한 문장으로 정의하면 무엇인가요?

레벤슈타인 거리는 두 문자 시퀀스 사이에서 삽입·삭제·대체 연산의 비용 합계를 최소화한 편집 거리입니다.

영문명은 Levenshtein Distance이며 문자열 편집 거리라고도 부릅니다. 이 글의 기본 설명은 세 연산의 비용이 각각 1인 경우입니다. 글자가 같아 그대로 두면 비용은 0입니다. 인접한 글자의 자리를 한 번에 맞바꾸는 연산은 기본 정의에 넣지 않습니다.[1][2][4]

입력은 문장의 의미를 담은 벡터가 아니라 순서가 있는 문자 목록입니다. 같은 글자가 몇 번 나왔는지와 어디에 놓였는지가 계산에 남습니다. 결과가 정수 1이라면 정해진 단위에서 최소 비용이 1이라는 뜻이며, 두 문서가 같은 사실을 말한다는 판정은 아닙니다.

한 줄 정리: 편집 거리는 두 표기를 바꾸는 비용입니다. 기본 레벤슈타인은 삽입·삭제·대체를 세고, 의미 판단과 오류의 업무상 중요도는 따로 다룹니다.

쉬운 예시로 이해해 볼까요?

감자나라ai님이 OCR 결과의 짧은 이름을 비교한다고 가정해 보겠습니다. 감자 를 감사 로 바꾸려면 마지막 음절 하나를 대체합니다. 비용 1의 대체 한 번이면 끝나므로 거리는 1입니다. 실제 OCR 모델을 평가한 자료가 아닌 계산 설명용 문자열입니다.

감자 를 왕감자 로 바꿀 때는 맨 앞에 왕을 삽입합니다. 뒤의 감자 두 글자는 그대로 두므로 거리는 1입니다. 두 문자열의 같은 위치만 비교하면 뒤쪽까지 달라 보이지만, 편집 거리는 앞에서 생긴 삽입을 반영해 나머지 글자를 다시 맞춥니다.

반대로 감자 를 감 으로 바꾸려면 자를 삭제해 거리가 1입니다. 감자 와 빈 문자열의 거리는 두 음절을 모두 삭제하는 2입니다. 같은 문자열 두 개의 거리는 아무것도 고칠 필요가 없어 0입니다.

자리 맞바꿈은 구분해야 합니다. ab 를 ba 로 바꾸는 기본 레벤슈타인 거리는 2입니다. 두 번 대체하거나 하나를 삭제한 뒤 다른 위치에 삽입합니다. 맞바꿈을 한 번의 연산으로 허용하는 변형에서는 다른 값이 나옵니다.[2][4]

위 거리와 뒤의 한글 정규화·비용 예시는 Python 표준 라이브러리와 직접 작성한 동적 계획법으로 검산했습니다. RapidFuzz·NLTK 함수를 설치해 실행한 결과나 Snowflake SQL의 실제 조회 결과로 제시하지 않습니다. 문서에 적힌 API 동작과 설명용 계산을 구분합니다.

쉬운 예시: 거리가 1인 두 문자열도 길이는 다를 수 있습니다. 같은 위치의 글자만 세는 비교와 달리, 레벤슈타인은 앞뒤 삽입과 삭제를 포함한 전체 최소 경로를 찾습니다.

왜 AI에서 레벤슈타인 거리가 중요한가요?

짧은 텍스트의 표기 차이를 비교합니다

OCR이 읽은 제품명, AI가 추출한 코드, 사용자가 입력한 검색어와 후보 표기를 비교하는 기준으로 검토합니다. 학습 모델 없이도 정해진 규칙으로 값을 계산합니다. 다만 어느 후보를 정답으로 승인할지와 어떤 정보를 고치면 안 되는지는 별도 판단입니다.

전체 값과 실제 수정 위치를 나누어 봅니다

두 결과의 거리가 같아도 틀린 위치는 다를 수 있습니다. 제품명 한 글자와 수량 한 자리의 오류는 같은 비용으로 잡혀도 영향이 다릅니다. 거리와 함께 원문·수정 위치를 보관하면 사람이 검토할 대상을 찾기 쉽습니다. 최소값 하나가 오류의 피해까지 요약하지는 않습니다.

핵심 인사이트: 비슷한 표기를 찾았다는 사실은 같은 대상이라는 증거가 아닙니다. 추천 후보를 좁히는 단계와 정답을 확정하는 단계를 분리합니다.

레벤슈타인 거리는 어떤 순서로 계산하나요?

1. 빈 문자열과 접두 부분의 비용을 만듭니다

두 입력의 앞부분끼리 바꾸는 최소 비용을 표에 적습니다. D[i,j] 는 첫 입력의 앞 i개 단위를 둘째 입력의 앞 j개 단위로 바꾸는 비용입니다. 기본 비용에서는 D[i,0]=i 와 D[0,j]=j 로 시작합니다. 한쪽이 비면 남은 글자를 모두 삭제하거나 삽입하기 때문입니다.[3]

2. 삭제·삽입·대체 후보 중 가장 작은 값을 고릅니다

각 칸에서 위쪽 칸의 비용에 삭제 1, 왼쪽 칸의 비용에 삽입 1, 대각선 칸의 비용에 대체 비용을 더한 값을 비교합니다. 현재 두 글자가 같으면 대각선에 더할 비용은 0이고 다르면 1입니다. 이 후보 중 최솟값이 해당 접두 부분의 답입니다.[3]

감자와 왕감자를 비교하는 표에서 빈 접두 부분의 첫 행은 [0,1,2,3] 입니다. 감까지 처리한 행은 [1,1,1,2] 이고 감자까지 처리한 행은 [2,2,2,1] 입니다. 마지막 칸의 1이 두 전체 입력의 거리입니다. 각 행의 최소값을 더하는 계산은 아닙니다.

3. 마지막 값과 편집 경로를 구분합니다

맨 끝 칸은 최소 비용이고, 어떤 글자를 고쳤는지 알려면 경로를 되짚는 별도 결과가 필요합니다. RapidFuzz의 editops 는 편집 연산을, opcodes 는 구간별 대응을 반환하는 도구입니다.[1] 최소 비용을 만드는 경로가 여럿일 수 있어 합계가 같아도 보고된 정렬은 달라질 수 있습니다.[3]

실전 팁: 처음에는 짧은 입력으로 표를 직접 확인하세요. 한쪽 앞에 글자를 하나 붙인 사례를 넣으면 위치별 단순 비교와 다른 점을 빠르게 확인합니다.

주요 설정과 반환값은 어떻게 읽나요?

weights는 세 편집 연산의 비용입니다

RapidFuzz의 weights=(1,1,1) 은 삽입·삭제·대체 순서입니다. weights=(1,1,2) 이면 대체 비용이 2로 바뀝니다.[1] 감자와 감사의 기본 거리는 1이지만 이 설정의 최소 비용은 2입니다. 점수의 단위가 달라졌으므로 다른 비용 설정의 숫자를 그대로 비교하지 않습니다.

NLTK의 substitution_cost 는 대체 비용을 바꾸는 옵션이며 transpositions=False 가 기본입니다.[2] 세 연산의 비용을 한 튜플로 받는 RapidFuzz와 계약이 다릅니다. 맞바꿈 옵션을 켠 결과를 기본 레벤슈타인이라고만 보고하면 계산의 차이를 숨기게 됩니다.

정규화 거리와 유사도는 방향이 반대입니다

기본 비용에서 비어 있지 않은 두 입력의 RapidFuzz 정규화 거리는 거리를 두 길이 중 큰 값으로 나눈 값입니다. 정규화 유사도는 1 - normalized_distance 입니다. 감자와 감사는 거리가 1, 최대 길이가 2이므로 각각 0.5와 0.5입니다. 같은 입력에서는 거리가 0이고 유사도가 1입니다.[1]

사용자 지정 비용에서는 분모도 길이와 비용에 따른 최대 가능 거리로 달라집니다. 무조건 최대 글자 수로 나누지 않습니다. 또 정규화 유사도 0.5를 정답일 확률 50%로 읽지 않습니다. 어떤 정규화식을 사용했는지와 빈 입력의 반환 규칙을 함수별로 확인합니다.[1]

임계값으로 잘린 결과는 정확한 거리가 아닐 수 있습니다

RapidFuzz의 원시 distance 에서 실제 거리가 score_cutoff 보다 크면 score_cutoff + 1 을 반환합니다. Snowflake의 EDITDISTANCE 는 max_distance 를 넘으면 그 상한값을 반환합니다.[1][4] 같은 이름의 제한 옵션도 반환 규칙이 다릅니다.

예를 들어 실제 거리가 4이고 제한값이 1이면 문서상 RapidFuzz의 반환은 2, Snowflake의 반환은 1입니다. 이들은 실제 거리가 각각 2와 1이라는 증거가 아닙니다. 특히 Snowflake의 잘린 값이 1이라는 이유만으로 실제 거리가 1 이하라고 승인하면 먼 후보까지 통과할 수 있습니다.[1][4]

전처리와 문자열 단위는 자동으로 같아지지 않습니다

RapidFuzz의 기본 processor=None 은 별도 전처리를 끕니다.[1] 대소문자·공백·기호를 통일하려면 그 규칙을 따로 적용합니다. Python 문자열로 코드 포인트를 순회하는 계산과 글자처럼 보이는 묶음을 세는 계산도 구별합니다. 정규화 함수의 지원과 실제 호출 여부는 별개입니다.[6]

레벤슈타인 거리와 헷갈리는 용어는 무엇이 다른가요?

해밍 비교·자카드 유사도와의 차이

같은 길이의 문자열에서 같은 위치가 다른지 세는 해밍 비교는 삽입으로 뒤쪽 위치가 밀린 상황을 직접 정렬하지 않습니다. 기존 해밍 손실 글은 고정된 라벨 칸의 오류 비율을 다룹니다. 여기서는 길이가 다른 문자열까지 최소 편집으로 맞추는 문제가 중심입니다.

자카드 유사도는 집합의 겹침 비율입니다. ab 와 ba 를 문자 집합으로 바꾸면 같은 원소를 담지만 기본 편집 거리는 2입니다. 순서와 반복 횟수를 지운 집합 표현을 문자열 편집과 같은 입력으로 보지 않습니다.

WER·CER와의 차이

단어 오류율(WER)은 정답 전사와 인식 결과의 단어 편집 오류를 정답 단어 수로 나누는 평가입니다. CER은 문자 단위를 씁니다. 레벤슈타인 원시 거리는 편집 비용 자체이며, 그 값만으로 WER처럼 정답 길이에 대한 오류율이 되지는 않습니다. 입력 단위와 분모를 따로 정합니다.

의미 유사도·맞바꿈 변형과의 차이

임베딩을 사용한 의미 비교와 달리, 기본 편집 거리는 문맥과 동의어를 해석하지 않습니다. 허용 과 불허용 의 거리가 1이어도 뜻은 크게 달라집니다. 낮은 거리를 근거로 안전 문구를 같은 답변으로 합치지 않습니다.

다메라우–레벤슈타인처럼 맞바꿈을 포함하는 정의와 기본 레벤슈타인을 구분합니다. NLTK는 맞바꿈 허용을 별도 옵션으로 제공하고 Snowflake EDITDISTANCE는 이를 세지 않는다고 명시합니다.[2][4] 비슷한 함수 이름만 보고 오타 유형별 비용도 같다고 가정하지 않습니다.

비교 정리: 편집 거리는 시퀀스를 바꾸는 비용, 자카드는 집합 겹침, WER·CER은 정답 길이에 대한 편집 오류율입니다. 의미가 같은지와 동일 대상인지는 별도 기준으로 확인합니다.

실전에서는 어디에 쓰이나요?

오탈자 후보를 검토할 순서로 좁힙니다

입력 검색어를 허용된 제품명 목록과 비교해 거리가 작은 후보를 먼저 보여 주는 응용을 검토합니다. 제품 코드·버전·금액처럼 한 글자가 다른 대상을 뜻하는 항목은 자동 치환에서 제외합니다. 후보 추천 이후 사람이나 별도 식별 규칙으로 확정하는 예시이며 검색 품질 향상을 보장하는 실험 결과는 아닙니다.

OCR·정보 추출의 수정 부담을 살핍니다

검수한 정답과 AI가 읽은 표기를 비교해 수정이 많이 필요한 사례를 찾습니다. 원시 거리만 모으면 긴 항목의 영향이 커질 수 있으므로 길이 구간과 오류 위치도 함께 남깁니다. 글자 수가 적게 바뀐 결과라도 날짜나 수량을 틀렸는지는 원문 이미지에서 따로 확인합니다.

레벤슈타인 거리를 적용할 때 어떤 순서로 확인하나요?

1. 비교 단위와 정규화 규칙을 고정합니다

비교할 항목 ID를 맞추고 문자·자모·단어 중 단위를 정합니다. 공백·대소문자·문장 부호 처리, 유니코드 정규화, 편집 비용과 함수 버전을 기록합니다. 원문은 별도로 남기고 비교용 사본에만 전처리를 적용합니다. 숫자나 기호 삭제가 업무상 차이를 지우지 않는지 검토합니다.

2. 작은 예시로 함수의 계약을 확인합니다

완전 일치, 앞쪽 삽입, 뒤쪽 삭제, 대체, 자리 맞바꿈, 빈 문자열을 각각 시험합니다. 한글의 조합 표현도 추가합니다. 제한값을 썼다면 한계보다 가까운 경우와 먼 경우를 모두 넣어 잘린 반환값을 실제 거리로 오해하지 않는지 확인합니다. 누락 데이터와 빈 문자열은 별도 상태로 남깁니다.

3. 임계값은 검증 자료에서 정합니다

거리 1이면 모두 같은 대상이라는 보편 규칙은 없습니다. 검수한 후보 쌍에서 잘못 합친 사례와 놓친 일치를 살핀 뒤 기준을 고정하고 별도 평가 자료에 적용합니다. 최종 테스트 결과에 맞춰 공백 삭제나 기준값을 바꾸지 않습니다. 평균 거리뿐 아니라 중요한 필드의 오인식 원문을 보관합니다.

사용할 때 무엇을 주의해야 하나요?

첫째, 한글의 화면 모양만 믿지 않습니다. 완성형 가와 결합 자모 두 코드 포인트로 적은 가는 화면에서 같아 보여도 원시 비교에서는 다를 수 있습니다. 이 글의 Python 코드 포인트 계산에서 정규화 전 거리는 2이고 양쪽을 NFC로 맞춘 뒤에는 0입니다. Unicode 표준은 이런 정준 동등성을 설명합니다.[5][6]

둘째, NFKC를 모든 원문에 강제하지 않습니다. 호환 정규화는 원문에서 구별하던 표기를 합칠 수 있습니다. 예시에서 원문 ① 과 1 의 거리는 1이지만 NFKC 뒤에는 0입니다. 검색용 비교에는 유용할 수 있어도 수식·식별자 등에서 중요한 차이를 없애는지 먼저 확인합니다.[5][6]

셋째, 긴 입력의 비용을 과소평가하지 않습니다. 기본적인 전체 동적 계획 표는 두 길이의 곱에 비례하는 칸을 채웁니다. 다만 모든 구현이 같은 방식은 아니며 RapidFuzz는 조건별 최적화를 설명합니다.[1][3] Snowflake도 길이가 긴 입력의 성능과 상한 옵션을 안내합니다.[4] 긴 문서 전체를 모든 후보와 무작정 비교하지 않습니다.

넷째, 동일인·동일 상품을 자동 확정하지 않습니다. 이름 한 글자나 코드 한 자리의 차이가 실제 다른 대상을 뜻할 수 있습니다. 후보 거리만으로 고객 기록을 합치거나 정답 데이터를 덮어쓰지 않습니다. 민감정보가 포함된 원문과 편집 로그의 접근·보관 범위도 함께 정합니다.

주의: 적은 편집 횟수는 의미·사실·안전성의 보증이 아닙니다. 비교용 정규화 결과, 원본과 편집 위치를 함께 남겨 사람이 잘못된 합침을 되돌릴 수 있게 합니다.

자주 묻는 질문

Q1. 레벤슈타인 거리는 낮을수록 비슷한가요?

같은 입력 단위와 편집 비용에서는 낮을수록 적은 비용으로 한 표기를 다른 표기로 바꿉니다. 0은 그 비교 규칙에서 같은 입력이라는 뜻입니다. 의미나 정답 확률까지 같은 것은 아닙니다.

Q2. 두 문자열의 길이가 달라도 계산하나요?

삽입과 삭제를 허용하므로 계산합니다. 감자와 왕감자는 길이가 달라도 삽입 한 번으로 맞춥니다. 길이 차이만으로 거리를 결정하지는 않으며 실제 글자와 순서도 함께 봅니다.

Q3. ab와 ba는 왜 거리 1이 아닌가요?

기본 레벤슈타인에는 맞바꿈 한 번이라는 연산이 없습니다. 두 번 대체하거나 삭제·삽입해야 해서 거리는 2입니다. 맞바꿈을 허용한 함수나 옵션을 썼다면 그 변형을 명시합니다.[2][4]

Q4. 한글이 같아 보이는데 거리가 왜 다르나요?

코드 포인트의 조합 방식이나 공백이 다를 수 있습니다. 원문을 보존하고 유니코드 표현과 정규화 전후를 확인합니다. NFC는 정준 동등성을 맞추는 도구이며 임의의 오탈자를 교정하는 기능은 아닙니다.[5][6]

Q5. 제한값을 넣어 반환된 거리를 그대로 저장해도 되나요?

반환값이 정확한 거리인지 상한·초과 표시인지 함께 저장합니다. RapidFuzz 원시 distance와 Snowflake EDITDISTANCE는 제한을 넘었을 때의 값이 다릅니다. 정확한 값이 필요하면 제한 없는 계산 경로로 확인합니다.[1][4]

Q6. 거리가 작으면 같은 고객이나 같은 뜻인가요?

그렇게 확정하지 않습니다. 표기가 가까워도 다른 사람·상품일 수 있고 부정 표현 하나로 뜻이 달라집니다. 편집 거리는 검토 후보를 고르는 단서로 사용하고 확정에 필요한 식별 근거는 별도로 확인합니다.

출처

마무리

레벤슈타인 거리는 삽입·삭제·대체의 최소 편집 비용으로 두 문자열의 차이를 재는 방법입니다. 길이가 다른 입력도 비교하지만 글자의 단위와 정규화, 연산 비용에 따라 숫자가 달라집니다. 원시 거리·정규화 유사도·상한으로 잘린 값을 구분하면 API 결과를 더 정확히 읽을 수 있습니다.

감자나라ai님이 AI의 추출 결과를 비교한다면 작은 문자열부터 검산해 보세요. 원본과 비교용 사본을 나누고, 같은 화면 모양의 한글과 자리 맞바꿈·빈 입력을 시험합니다. 그다음 실제 오류 쌍에서 기준을 정하고 중요한 글자의 차이는 사람이 확인합니다.