Levenshtein Distance   레벤슈타인 거리, 르벤슈타인 거리

(2025-10-04)

편집 거리


1. 레벤슈타인 거리 (Levenshtein distance), 편집 거리 (Edit Distance)

  ㅇ 두 단어(문자열) 사이의 유사성측정하는 방법으로써,
     - 서로다른 두 단어가 같아지려면 편집해야하는 연산 횟수

  ㅇ 창안자 : 1965년 블라디미르 레벤슈타인이 고안

  ㅇ 용도 (활용)  :  단어 유사도 측정, 철자 오타 교정, DNA 서열 비교 등

  ㅇ 편집 연산의 종류 및 거리 
     - 삽입 (Insertion) : 한 문자를 삽입
     - 삭제 (Deletion) : 한 문자를 삭제
     - 대치 (Substitution) : 한 문자를 다른 문자로 치환
     * 레벤슈타인 거리 : 두 단어가 같아지기 위한 세 연산의 최소 수행 횟수

  ㅇ 例) "kitten" → "sitting"
     - kitten → sitten (k→s 치환) (1회)
     - sitten → sittin (e→i 치환) (2회)
     - sittin → sitting (g 삽입) (3회)
     * 따라서, 레벤슈타인 거리 = 3

  ㅇ 거리값 의미
     - 값이 0 이면, 두 문자열이 완전히 같음
     - 값이 클수록, 문자열 차이가 큼

유사도
1. 닮음 (유사도)   2. 거리 (유사도 척도)   3. k 최근접 이웃   4. 레벤슈타인 거리  
용어해설 종합 (단일 페이지 형태)

"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"
     [정보통신기술용어해설]