'Levenshtein'에 해당되는 글 1건

  1. 2013.04.10 [algorithm] elasticsearch multimatchquery 옵션 테스트 중 .maxExpansions(..)

[algorithm] elasticsearch multimatchquery 옵션 테스트 중 .maxExpansions(..)

Elastic/Elasticsearch 2013. 4. 10. 17:40

maxExpansions() 옵션 설정 후 어떻게 동작 하는지 확인 하려다 이넘이 동작하는 원리가 궁금해 졌습니다.

그래서 찾아 보니 Levenshtein distance 라는 알고리즘을 사용하고 있더군요.

설명은 아래를 참고해 주세요.

(similarity 할때 사용하는 줄 알았는데 multiMatchQuery 에서도 사용하내요)


원문 : http://progh2.tistory.com/195


URL: http://www.merriampark.com/ld.htm


자주쓰이는 3개의 언어로 구현한 Levenshtein Distance


작성자: Michael Gilleland, Merriam Park Software


이 짧은 에세이를 쓰게 된 것은 Levenshtein distance 알고리즘에 대해서

설명하고 또 그것이 각각의 세가지 프로그래밍 언어에서 어떻게 구현되는가를

보이기 위해서입니다.


Levenshtein Distance이란 무엇인가?

데모

알고리즘

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

레퍼런스

다른 언어로 구현


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를 알아보세요.


원래 문자열

대상 문자열



알고리즘


알고리즘 작동 단계

단계 설명

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로의 구현(링크가 깨진 것을 알려주신 Stefan Seidler님 감사합니다).


: