바그너-피셔 알고리즘

Wagner–Fischer algorithm

컴퓨터 과학에서 바그너-피셔 알고리즘은 두 문자 문자열 사이의 편집 거리를 계산하는 동적 프로그래밍 알고리즘이다.

역사

바그너-피셔 알고리즘은 다발명의 역사를 가지고 있다.나바로는 그것의 다음과 같은 발명가들을 출판 날짜와 함께 나열하고, 그 목록이 불완전하다는 것을 인정한다.[1]: 43

계산 거리

바그너-Fischer 알고리즘은 첫 번째 문자열의 모든 접두사와 두 번째 문자열의 모든 접두사 사이의 편집 거리를 보유하기 위해 매트릭스를 예약하면 매트릭스를 채움으로써 매트릭스의 값을 계산할 수 있으며, 따라서 마지막 val로서 두 전체 문자열 사이의 거리를 찾을 수 있다는 관찰을 바탕으로 편집 거리를 계산한다.연산된 ue.

길이 m과 길이 n의 두 개의 문자열을 사용하고 그들 사이의 레벤슈테인 거리를 반환하는 Distance 함수에 대한 유사점으로서, 직접적인 구현은 다음과 같이 보인다.입력 문자열은 1-색인 반면 매트릭스 d는 0-색인 및[i..k]폐쇄된 범위야 

기능을 하다 거리(마를 뜨다 s[1..m], 마를 뜨다 t[1..n]):   // 모든 i와 j에 대해 d[i,j]는 사이의 거리를 유지한다.   // s의 첫 번째 i 문자 및 t의 첫 번째 j 문자   // d에는 (m+1)*(n+1) 값이 있음   선언하다 인트로 d[0..m, 0..n]     세트 각각 요소 에 d 로 영     // 소스 접두사는 다음에 의해 빈 문자열로 변환할 수 있음   // 모든 문자 삭제   을 위해 i 로부터 1 로 m:       d[i, 0] := i     // 빈 소스 접두사에서 대상 접두사에 도달할 수 있음   // 모든 문자를 삽입하여   을 위해 j 로부터 1 로 n:       d[0, j] := j     을 위해 j 로부터 1 로 n:       을 위해 i 로부터 1 로 m:           만일 s[i] = t[j]:             대체비용 := 0           다른:             대체비용 := 1            d[i, j] := 최소의(d[i-1, j] + 1,                   // 삭제                              d[i, j-1] + 1,                   // 삽입                              d[i-1, j-1] + 대체비용)  // 대체     돌아오다 d[m, n]

결과 매트릭스의 두 가지 예(밑줄이 그어진 숫자 위에 표시하면 해당 숫자를 얻기 위해 수행된 작업이 표시됨):

k i t t e n
0 1 2 3 4 5 6
s 1 1 2 3 4 5 6
i 2 2 1 2 3 4 5
t 3 3 2 1 2 3 4
t 4 4 3 2 1 2 3
i 5 5 4 3 2 2 3
n 6 6 5 4 3 3 2
g 7 7 6 5 4 4 3
S a t u r d a y
0 1 2 3 4 5 6 7 8
S 1 0 1 2 3 4 5 6 7
u 2 1 1 2 2 3 4 5 6
n 3 2 2 2 3 3 4 5 6
d 4 3 3 3 3 4 3 4 5
a 5 4 3 4 4 4 4 3 4
y 6 5 4 4 5 5 5 4 3

알고리즘 전체에서 유지되는 불변성은 초기 세그먼트를 변환할 수 있다는 것이다.s[1..i]로t[1..j]을 최소한으로 하여d[i,j]작전마지막에 배열의 오른쪽 하단 요소에는 답이 들어 있다.

정확성 증명

앞서 언급했듯이, 불변성은 초기 세그먼트를 변형할 수 있다는 것이다.s[1..i]로t[1..j]을 최소한으로 하여d[i,j]작전이 불변성은 다음 이후 유지된다.

  • 이 값은 다음과 같은 이유로 행과 열 0에 처음에는 참이다.s[1..i]빈 문자열로 변환할 수 있음t[1..0]간단히 모든 것을 취하함으로써.i성격.비슷하게, 우리는 변환할 수 있다.s[1..0]로t[1..j]간단히 모두 합쳐서j성격.
  • 만약s[i] = t[j]그리고 우리는 변신을 할 수 있다.s[1..i-1]로t[1..j-1]에k그럼 우리도 똑같이 할 수 있을거야s[1..i]마지막 등장인물은 그냥 놔두고,k작전
  • 그렇지 않으면 거리는 변환을 수행할 수 있는 세 가지 방법 중 최소값이다.
    • 우리가 변화시킬 수 있다면s[1..i]로t[1..j-1]에k운영, 그러면 간단히 추가할 수 있다.t[j]을 얻기 위해 나중에t[1..j]에k+1작업(실제)
    • 우리가 변화시킬 수 있다면s[1..i-1]로t[1..j]에k수술 후 제거하면s[i]그리고 나서 같은 변환을 행한다, 총체적으로k+1작업(실제)
    • 우리가 변화시킬 수 있다면s[1..i-1]로t[1..j-1]에k그럼 우리도 똑같이 할 수 있을거야s[1..i], 그리고 원본을 교환하다.s[i]을 위해t[j]그 후에, 총계적으로k+1작업(실제)
  • 변환에 필요한 작업s[1..n]로t[1..m]물론 모든 것을 변환하는 데 필요한 수입니다.s의 모든 부분에 있어서.t등등d[n,m]우리의 결과를 유지한다.

이 증명은 에 배치된 번호가d[i,j]사실 최소다; 이것은 보여주기 더 어렵고, 우리가 추측하는 모순에 의한 논쟁을 포함한다.d[i,j]최소 3개보다 작으며, 3개 중 1개가 최소가 아니라는 것을 보여주기 위해 이것을 사용한다.

수정 가능

이 알고리즘에 대한 가능한 수정사항은 다음과 같다.

  • 알고리즘은 이전 행과 현재 행을 한 번에 저장하기만 하면 되기 때문에 O(mn) 대신 O(m)를 적게 사용하도록 조정할 수 있다.
  • 삽입 횟수와 삭제, 대체 횟수를 따로 보관하거나, 발생 위치까지 항상 보관할 수 있다.j.
  • 간격까지의 거리를 정상화시킬 수 있다.[0,1].
  • 만약 우리가 그것이 임계값 k보다 작을 경우에만 거리에만 관심이 있다면, 그것은 매트릭스에서 폭 2k+1의 대각선 스트라이프를 계산하기에 충분하다.이런 식으로 알고리즘은 O(kl) 시간에 실행할 수 있는데 여기서 l는 최단 문자열의 길이다.[2]
  • 우리는 삽입, 삭제, 대체에 다른 벌칙 비용을 줄 수 있다.삽입, 삭제, 대체 문자에 따라 위약금도 줄 수 있다.
  • 이 알고리즘은 데이터 의존도가 높기 때문에 병렬화가 잘 안 된다.그러나, 모든 것은cost값을 병렬로 계산할 수 있으며 알고리즘을 적용하여minimum의존성을 제거하기 위해 단계적으로 기능한다.
  • 행 대신 대각선을 검사하고, 게으른 평가를 사용함으로써 Rebenshtein 거리를 O(1 + d) 시간(여기서는 d가 Levenshtein 거리)으로 찾을 수 있는데, 거리가 작을 경우 일반 동적 프로그래밍 알고리즘보다 훨씬 빠르다.[3]

문자열 검색용 판매자 변종

0으로 매트릭스의 첫 번째 행을 초기화함으로써, 우리는 텍스트의 문자열의 퍼지 문자열 검색에 사용할 수 있는 Wagner-Fischer 알고리즘의 변형을 얻는다.[1]이 수정은 텍스트의 일치하는 하위 문자열의 끝 위치를 제공한다.일치하는 서브스트링의 시작 위치를 결정하기 위해 삽입과 삭제 횟수를 따로 저장하여 끝 위치로부터 시작 위치를 계산하는 데 사용할 수 있다.[4]

결과 알고리즘은 결코 효율적이지 않지만, 대략적인 검색을 수행한 최초의 알고리즘 중 하나로서 발행 시점(1980년)에 있었다.[1]

참조

  1. ^ a b c Navarro, Gonzalo (2001). "A guided tour to approximate string matching" (PDF). ACM Computing Surveys. 33 (1): 31–88. CiteSeerX 10.1.1.452.6317. doi:10.1145/375360.375365. S2CID 207551224.
  2. ^ Gusfield, Dan (1997). Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge, UK: Cambridge University Press. ISBN 978-0-521-58519-4.
  3. ^ Allison L (September 1992). "Lazy Dynamic-Programming can be Eager". Inf. Proc. Letters. 43 (4): 207–12. doi:10.1016/0020-0190(92)90202-7.
  4. ^ 브루노 울첸로겔 팔레오.레벤슈테인 거리를 기준으로 한 GATE의 대략적인 가제트.논리, 언어 및 정보 분야의 유럽 여름 학교 학생 부문, 2007.