[algorithm] KMP, BM string matching algorithm demo
- animation
- KMP algorithm
text : abcabcabcabda
pattern : abcabd
shift abcabd
compare |
1) 'c'에서 mismatch
2) 'c'를 제외하고, substring 'abcab'에서 prefix == suffix 조건을 만족하는 것을 찾으면 'ab'
3) suffix의 해당 'ab' position으로 shift
4) 'c' 포지션에서 다시 comparison 진행
핵심 아이디어는,
"mismatch 앞 부분 문자열의 prefix와 suffix가 같은 경우, suffix의 앞쪽에서는 절대로 pattern matching이 발생할 수 없다"
당연하겠지만, pattern이 매칭되려면 가장 앞 문자부터 매칭되어야한다.
따라서, mismatch되기 전까지의 substring에서 가장 앞 문자로 시작되는 것이 있으면 거기서 다시
pattern 매칭을 시작할수 있을 것이다.
그런데, 가장 앞 문자 하나만 고려하지 않고, 가장 앞 두문자를 고려한다면 어떨까?
가장 앞 세문자를 고려한다면?
이런 컨셉은 mismatch 앞 부분 문자열의 prefix와 suffix가 같은 최장 길이를 통해서 구현되는 것이다.
animation을 보면 알겠지만, 패턴 'abcabd'에 대해서 미리 'fail value'를 계산해둔다.
fail value 혹은 failure function을 계산하는 방법은 아래 그림에 있는 알고리즘에 잘 설명되어 있다.
두개의 i, j index를 가지고 시작
pattern P : abcabd
i=1, j=0, F[i=0]=0
i=1, j=0, 'ab'에 대해서 체크하면 같은 char가 없기 때문에 F[i=1]=0
i=2, j=0, 'abc'에 대해서도 마찬가지로 F[i=2]=0
i=3, j=0, 'abca'에 대해서 P[i=3] == P[j=0] == 'a', F[i=3] = j + 1 = 1
i=4, j=1, 'abcab'에 대해서 P[i=4] == P[j=1] == 'b', F[i=3] = j + 1 = 2
i=5, j=2, 'abcabd'에 대해서 P[i=5] != P[j=2], j > 0, j=F[j-1]=F[1]=0 (다시 처음으로)
i=5, j=0, 'abcabd'에 대해서 P[i=5] != P[j=0], F[i=5]=0
i=6, break
i P F
0 a 0
1 b 0
2 c 0
3 a 1
4 b 2
5 d 0
다시 처음 예로 돌아가서 설명하면
text : abcabcabcabda
pattern : abcabd
shift abcabd
compare |
text position i, pattern position j라고 하자.
i=5, j=5, 'd'에서 mismatch가 발생한다.
그러면 'd' 바로 앞 문자에 대해서(j=4)
F[j=4]=2
j - F[j=4] = 5 - 2 = 3
즉, 3만큼 pattern으로 shift(jump)시킨다.
(pattern을 shift시킨다는 것은 결국 text position i를 옮긴다는 것과 같다.
설명의 편의를 위해서 pattern을 shift시킨다고 표현.
i=3)
그리고나서 pattern position j를 F[j=4]=2로 잡는다. j=2
즉, 앞에 'ab'는 다시 비교할 필요가 없으니 'c'부터 비교하라는 의미이다.
time complexity : O(n + m)
worst case : O(2n), prefix/suffix 매칭되는 것이 없는 pattern인 경우
* KMP를 multi pattern으로 확장한 버전이 Aho-Corasick 알고리즘
- BM algorithm
kmp 알고리즘과 자주 비교되는 string matching 알고리즘이다.
기본 아이디어는 두가지
1. 패턴을 뒤에서부터 비교한다
2. last occurrence table을 사용한다
text : abcabcabcabda
pattern : abcabd
현재 text[5]=c에서 mismatch
'c'의 pattern에서 last occurrence는
pattern[2]이므로 text와 align을 하면
text : abcabcabcabda
pattern : abcabd
다시 pattern의 끝부터 비교시작
text[8]=c에서 mismatch
다시 align
text : abcabcabcabda
pattern : abcabd
다시 뒤에서부터 비교하면
match found
time complexity : O(n+m)
worst case : O(nm), text/pattern 둘다 동일한 문자가 반복되는 경우
Galil rule : O(n+m) for worst case
- references