[알고리즘] Levenshtein Distance이란 무엇인가?

[gromit]

Levenshtein Distance이란 무엇인가?

Levenshtein Distance(이하 LD)는 두 문자열의 비슷한 정도를 측정하기위해 고안되었습니다.
여기서 원문자열을 (s)로, 대상문자열을 (t) 라고 나타낸다고 하겠습니다. distance란 s를
t로 변형시키기 위해 삭제, 추가, 또는 수정이 필요한 횟수를 뜻합니다. 예를든다면,

* s가 "test"이고 t도 "test"라면, LD(s,t) = 0 이 됩니다. 왜냐하면 문자열들이 이미 동일하여 변환이 필요하지 않기 때문입니다.

* s가 "test"이고 t가 "tent"라면, LD(s,t) = 1 이 됩니다. 왜냐하면 s를 t로 만들기 위해서는 "s"를 "n"으로 한번 수정이 필요하기 때문입니다.

Levenshtein distance는 string 간의 차이가 클수록 위대함을 느낄 수 있습니다.

Levenshtein distance는 러시아 과학자인 Vladimir Levenshtein가 1965년에 고안하여 그렇게 이름지어졌습니다.
Levenshtein 이란 단어가 쓰거나 읽기 힘들기 때문에 종종 edit distance라고도 불립니다.

Levenshtein distance 알고리즘은 다음과 같은 분야에 쓰여집니다:

* 철자 검사
* 음성 인식
* DNA 분석
* 표절여부 검사

데모

아래의 간단한 자바 애플릿으로 두 문자열의 Levenshtein distance를 알아보세요.

원래 문자열
대상 문자열


알고리즘

알고리즘 작동 단계
단계 설명
1
s의 문자열 길이를 n에 넣는다.
t의 문자열의 길이를 m에 넣는다.
만약 n = 0 이라면, m 을 리턴하고 종료한다.
만약 m = 0 이라면, n 을 리턴하고 종료한다.
0..m 행과, 0..n 열로 이루어진 행열을 만든다.
2
첫번째 행인 0..n을 초기화 한다.
첫번째 열인 0..m을 초기화 한다.
3
s의 각 문자(i는 1부터 n까지)를 검사한다.
4
t의 각 문자(j는 1부터 m까지)를 검사한다.
5
s[i]와 t[j]가 같다면, 변경하기 위한 비용은 0이 된다.
s[i]와 t[j]가 같지 않다면, 비용은 1이 된다.
6
행열의 셀 d[i,j]에 다음의 것들 중 가장 작은 값을 넣는다.
a. 바로 위의 셀이 더하기 1이 되는 경우: d[i-1, j] + 1
b. 바로 왼쪽 셀이 더하기 일이 되는 경우: d[i,j-1] + 1
c. 대각선으로 연속적인, 바로 왼,위쪽 셀의 비용: d[i-1,j-1] + cost
7
(3, 4, 5, 6) 단계를 반복하여 완료되면, d[n, m]셀에 있는 것이 distance가 된다.

예제

이 예제절에서는 원래 문자열이 "GUMBO"이고 대상 문자열이 "GAMBOL"이라 할 때
어떻게 Levenshtein distance가 계산되는지에 대해서 다룬다.

1 과 2 단계

i가 1일 때 3에서 6 단계

i가 2일 때 3에서 6 단계

i가 3일 때 3에서 6 단계

i가 4일 때 3에서 6 단계

i가 5일 때 3에서 6 단계

7단계
행열의 가장 오른쪽 아래에 있는 값이 distance가 된다.(여기서는 2)
이 결과는 "GUMBO"가 "GAMBOL"이 되기 위해서 "U"를 "A"로 바꾸고
"L"을 추가해야한다는, 직관적으로 알 수 있는 결과와 일치합니다.
( 1번의 수정과 1번의 추가 = 2 번의 변경 )

세가지 언어로 구현된 소스코드

프로그래밍 언어들간에 차이에 대해서 토론하는 엔지니어들 사이에서는 종교 전쟁이 일어나기도합니다.
이러한 예로, 전형적인 주장은 JavaWorld article에서 일어난(July 1999) Allen Holub의 주장입니다.:
"예를들자면, 비주얼 베이식은 전혀 객체지향이라고 말할 수 없다. Microsoft Foundation Classes(MFC)
또는 대부분의 다른 마이크로소프트의 테크놀러지는 어느것도 객체지향이라 주장할 수 없다."

Salon에 계제된(Jan. 8, 2001) Simson Garfinkels의 글에서 다른 진영의 반박이 이루어졌습니다.
이 글은 "Java: 느리고, 꼴사납고, 부적절한 언어"라는 제목으로 알려져 있는데, 명료하게
표현하자면 "나는 자바를 증오해"라고 나타낼 수 있습니다.

우리는 이러한 종교 전쟁들 속에서 자연스럽고 조심스런 입장을 취하로 했습니다. 배우기 위한 교재로써,
하나의 프로그래밍 언어에서만 해결할 수 있는 문제라면 대개 다른 언어에서도 마찬가지로 해결할 수
있을 것입니다. 우수한 프로그래머는 완전히 새로운 언어를 배우면서 한다고 하더라도 하나의 언어에서
다른 언어로 비교적 쉽게, 큰 어려움에 당면하지 않고 옮길 수 있습니다. 프로그래밍 언어라는 것은
목적을 이루기 위한 것이지, 그 자체가 목적은 아닌 것입니다.

이러한 중도의 입장에서, 우리는 Levenshtein distance 알고리즘을 아래에 있는 프로그래밍 언어들로
구현하여 소스코드를 보였습니다.

* Java
* C++
* Visual Basic

소스코드들 (블라블라)

참고문헌

Levenshtein distance에 관련된 다릍 토의를 다음 링크들에서 발견하실 수 있습니다.

* http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit.html (Lloyd Allison)
* http://www.cut-the-knot.com/do_you_know/Strings.html (Alex Bogomolny)
* http://www-igm.univ-mlv.fr/~lecroq/seqcomp/node2.html (Thierry Lecroq)

다른 언어로 구현

아래 있는 분들은 그들 각자가 다양한 언어로 Levenshtein Distance 알고리즘을 구현한 것을
여기서 사용할 수 있게 친절히 승낙해 주셨습니다.

* Eli Bendersky 은 펄로 구현해주셨습니다.
* Barbara Boehmer 은 Oracle PL/SQL 로 구현해주셨습니다.
* Rick Bourner Objective-C 로 구현해주셨습니다.
* Joseph Gama 는 TSQL로 Planet Source Code 에 있는 TSQL 함수 패키지의 한 파트로 구현해주셨습니다.
* Anders Sewerin Johansen 는 C++로 제가 만든 것보다 C++의 정신에 가깝게, 더 최적화되고 세련되게 구현해주셨습니다.
* Lasse Johansen 는 C#으로 구현해 주셨습니다.
* Alvaro Jeria Madariaga는 Delphi로 구현해 주셨습니다.
* Lorenzo Seidenari 는 C로 구현해 주셨습니다.
* Steve Southwell는 Progress 4gl로 구현해 주셨습니다.

이 페이지 밖에 있는 다른 구현들:

* Art Taylor의 Emacs Lisp로의구현.
* Magnus Lie Hetland의 Python로의 구현.
* Richard Suchenwirth의 Tcl로의 구현