Lucene에서 Edit Distance를 이용해 쿼리를 날려서 검색 결과를 받는 기능이 있다.
그때 막연하게 시간이 많이 걸린다고 책에서 나와 있는 관계로 왜 많이 걸릴까 고민을 하지 않던 찰라 기회가 생겨서 Edit Distance를 구하는 알고리즘을 공부하고 구현해 봤다.
결과적으로 Dynamic Programming 문제이긴 한데, 이것과 배낭문제 그리고 어제 학교에서 공부했던 Routing Algorithm(최단 라우팅 거리 측정 알고리즘)을 비교해서 보니 조금이나마 정확한 이해를 하게 된거 같다.
동적 프로그래밍을 적용할때 가장 중요한것은 이 문제가 동적 프로그래밍으로 가능한지 판단하는것이다.
“한 문제에 대한 해가 최적이면 그 문제를 이루는 부분 문제들의 해도 최적이다”
위의 명제에 해당하는 문제면 일단 분석에 들어 가야 한다.
1. 해당 문제가 최적화의 원리가 적용되는 문제인가?
2. 큰 문제와 작은 문제는 어떻게 정의할 것인가?
3. 큰 문제와 작은 문제 사이의 점화식은 어떻게 설정할 것인가?
4. 점화식을 통해서 작은 문제로부터 큰 문제를 해결하는 순서를 정한다.
1. 부분의 최적해가 전체의 해를 구하는데 도움이 된다.
math -> art 로 변환시 math -> ar, mat -> art, mat -> ar 의 변환까지의 최적 편집거리가 math -> art로의 편집거리를 구하는데 도움이 된다.
2,3,4. 아래 점화식이 나온다.
<환경 설명>
1. 먼저 입력된 문자열에 대한 길이를 획득하고
2. 길이에 맞춰서 이차원 배열을 선언한다.
이때 문자열이 없는 경우도 포함해서 “길이 + 1” 만큼의 크기로 선언한다.
<부연설명>
행렬의 행이 의미하는것은 원본 문자열이고 열이 의미하는것은 목적 문자열이다.
그러니 행의 값이 오르는것은 문자열의 삭제에 대한 cost가 증가하는것을 의미하고
열이 오르는것은 문자열의 추가에 대한 코스트가 증가함을 의미한다.
그리고 갱신의 cost는 실제로의 상황에서는 추가, 삭제가 한꺼번에 일어나는 것이지만 1로 본다.
그래서 문자열의 추가, 삭제, 갱신은 cost가 모두 1이다.
<수행 in geteditdistance>
1. 각 행에 대한 수행
matrix[i][j] = Getmin(matrix[i-1][j] + 1, matrix[i][j-1] + 1, matrix[i-1][j-1] + isreplace);
위의 문장이 점화식이다.
isreplace는 현재 검사하는 문자가 같을 경우에는 0이고 다를 경우에는 갱신 코스트 1을 추가한다.
인자가 의미하는것은 삭제, 삽입, 갱신에 대한 코스트이다.
그러니까 현재 상태에 오기 직전까지의 모든 최적의 삽입, 삭제, 갱신중에서 가장 작은 값을 현재의 가장 최적해로 지정하는것이다.
이렇게 해서 제일 마지막에 전체 문자열에 대한 cost를 계산한 값이 matrix의 마지막에 구해지는데 그것이 바로 최적 Edit Distance가 된다.
2^n의 복잡도를 가지는것이 단지 for문 두개를 돌리는 n^2의 문제로 바뀌는 순간이다.
루씬에서는 FuzzyQuery라는 기능을 구현하기 위해 아래와 같은 스코어링 룰을 사용한다.
1 – (편집거리 / min(본문 글자수, 질의 글자수))
하지만 실제 상용 검색엔진에서 이런것을 제공한다면(Lucene처럼) 역시나 n^2의 지수승 이상의 부하가 많이 걸리는 연산이 될거 같다는 생각이 든다. 그래서 Lucene에서도 그리 권장하지 않는 기능이기도 하고…쩝.
그리고 이런 편집거리 쿼리를 쓸데가 있을지도 의문이기도 하다. ㅎㅎ
위의 코드는 알고리즘 이해를 위해 간단하게 C로 만들어본 Edit Distance 산출 프로그램 소스코드이다.
Dynamic Programming : Edit Distance (and Lucene FuzzyQuery) by from __future__ import dream is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.