모든 부분 문자열에 대한 편집 거리를 찾는 알고리즘

Question

두 문자열 s 및 t이 주어졌습니다. s에있는 각 부분 문자열을 찾을 필요가 있습니다. t까지 거리 (Levenshtein distance). 사실 각각 i의 위치는 s에 있어야합니다. 위치는 i에서 시작된 모든 부분 문자열의 최소 편집 거리입니다.

예를 들어

:

t = "ab"  
s = "sdabcb" 

그리고 내가 좋아하는 뭔가를 얻을 필요가 :

{2,1,0,2,2}

설명 : 등등

1st position: 
distance("ab", "sd") = 4 (2*subst) 
distance("ab", "sda") = 3(2*delete + insert) 
distance("ab", "sdab") = 2 (2 * delete) 
distance("ab", "sdabc") = 3 (3 * delete) 
distance("ab", "sdabcb") = 4 (4 * delete) 
So, minimum is 2 

2nd position: 
distance("ab", "da") = 2 (delete + insert) 
distance("ab", "dab") = 1 (delete) 
distance("ab", "dabc") = 2 (2*delete) 
.... 
So, minimum is 1 

3th position: 
distance("ab", "ab") = 0 
... 
minimum is 0 

하고 있습니다.

나는이 작업을 해결하기 위해 무차별 대입 알고리즘을 사용할 수 있습니다. 하지만 더 빠른 알고리즘이 있습니까?

도움 주셔서 감사합니다.

Answer 1

Wagner-Fischer 알고리즘은 모든 프리픽스에 대한 답을 "무료"로 제공합니다.

http://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm

바그너 - 피셔 행렬의 마지막 행은 t-s 각 프리픽스 편집 거리를 포함한다.

문제가 발생한 첫 번째 균열로 각 i에 대해 Wagner-Fischer를 실행하고 마지막 행에서 가장 작은 요소를 선택하십시오.

다른 사람이 더 나은 접근 방법을 알고 있는지 (또는 알 수 있는지) 궁금 할 것입니다.

Answer 2

주어진 문자열에서 부분 문자열을 찾는 것은 매우 쉽습니다. 일반적인 Levenshtein 알고리즘을 사용하고 약간 수정하십시오. FIRST

: 대신 0,1,2,3,4,5과 행렬의 첫 번째 행을 채우는 ... 당신은 제로에 완전히 채운다. (녹색 직사각형)

초 : 그런 다음 알고리즘을 실행합니다.

THIRD : 마지막 행의 마지막 셀을 반환하는 대신 마지막 행에서 가장 작은 값을 검색하여 반환합니다. (적색 사각형)

예 : 바늘 "ABA"덤 "C의 아바 C"-> 결과 = 1 (변환 아바 -> ABA)

I 발견 여기에서 : http://ginstrom.com/scribbles/2007/12/01/fuzzy-substring-matching-with-levenshtein-distance-in-python/

나는 그것을 시험하고 작동한다.

질문에서와 같이 문자열을 통해 문자 단위로 문자를 이동하는 것이 훨씬 빠릅니다. 한 번만 행렬을 만듭니다.