레벤슈타인 거리

1 개요

Levenshtein distance, edit distance

레벤슈타인 거리, Levenshtein 거리, 편집거리

• 두 문자열이 얼마나 다른지를 나타내는 거리 중 하나
• 문자를 삽입, 삭제, 치환하여 다른 문자열로 변형하는데 필요한 최소 횟수
• 철자검사기 등에서 두 문자열이 어느 정도 유사한지 값으로 나타내는 방법의 하나
• 1965년 러시아의 브라디미르 레벤슈타인이 고안함
• 같으면 0, 다르면 1 이상

2 예시

• lev( "kitten", "kitten" ) == 0
• lev( "kitten", "sitten" ) == 1
• lev( "kitten", "sittin" ) == 2
• lev( "kitten", "sitting" ) == 3

3 같이 보기

• agrep
• bitap 알고리즘
• 해밍 거리 - 길이가 같은 문자열 대상
• 편집 거리(edit distance)
• PHP levenshtein()

4 참고

• https://en.wikipedia.org/wiki/Levenshtein_distance