String Algorithm(KMP,Boyer-Moore)

1. String Algorithm Outline

: 웹 브라우저나 문서 상에서 단어를 하나 찾고 싶다면 CTRL+F로 찾을 수 있다. 이처럼 문자열 내에서 원하는 단어를 빠르게 찾는 알고리즘은 상당히 많은 곳에서 사용되고 있다. 특히 검색엔진과 같은 경우는 사용자의 검색어를 수 초 안에 빠르게 검색할 수 있어야 하므로, String Algorithm에선 "시간"이 생명이다! 이를 원본 문자열에서 pattern과 매칭되는 부분을 찾는다고 하여 Pattern Matching problem이라고 한다.

 

그렇다면 Pattern Matching Problem과 관련된 여러 가지 방법 중에 많이 쓰이는 세 가지는 무엇이 있을까?

1) Brute-force Algorithm

2) KMP Algorithm

3) Boyer-Moore Heuristic

순으로 빠르게 검색이 가능하며, 이번 포스팅에서는 세 가지 알고리즘에 대해 모두 알아보도록 하자.

 

2. Strings

P가 size m을 갖는 문자열이라고 할때, 

-> 만약 String안에서 연속된 문자열을 추출하면 P[i..j], Substring이라고 하고, String에서 문자를 뽑아서 추출한 것(순서 X)을 Subsequence라고 한다.

: 즉, 이 용어를 사용해 말하면 String algorithm(Pattern Matching Problem)은 Text와 Pattern 문자열이 주어졌을때, T의 Substring중 P와 일치하는 것을 찾는다고 할 수 있다.

 

- Suffix : 접두사, P[0...i] (맨 앞에서 시작한 substring)

- Prefix: 접미사, P[i....m-1] (맨 끝에서 끝나는 substring)

 

 

3. Brute-Force Algorithm

: 가장 간단하고 쉽게 생각할 수 있는 알고리즘으로, 원본 문자열과 패턴을 일일히 모두 비교하는 방법이다.

원본 문자열의 맨 앞 문자부터 탐색을 시작하여, 패턴과 다른 문자가 나오면 두번째 문자열에 다시 패턴을 두고 일일히 비교하는 방식이다.

-> 이는 시간 복잡도가 원본 문자열이 N, 패턴이 M일때 O(NM)의 시간 복잡도를 갖는데, 이는 다른 알고리즘에 비해 현저히 느린 속도이다. 패턴이 10글자라면, 최악의 경우에 원본 문자열에서 고작 10글자를 읽는데 100번의 비교를 해야 한다. 검색 알고리즘에선 시간이 생명이라고 앞서 언급했던 것을 잊지 말자.

 

-Pseudocode

i는 문자열, j는 패턴과 관련된 인덱스이다. i는 멈춰두고, j를 늘려가며 차근차근 비교해 불일치가 발생하면 i인덱스를 1늘려 패턴을 처음부터 다시 비교하는 프로세스라고 할 수 있다.

4. KMP Algorithm

앞서 끔찍하게 느린 Brute-force 알고리즘은 잊고, 좀더 개선된 KMP 알고리즘의 기본 아이디어에 대해서 살펴보자.

KMP 알고리즘은 brute-force알고리즘처럼 모든 문자열을 일일히 비교하는게 아니라, 비교가 따로 필요없는 일정 부분은 건너뛸수 없을까? 하는 아이디어에서 착안한 알고리즘이다.

 

- 아래 예시를 살펴보자.

-> 패턴과의 많은 match가 발생했는데 마지막 부분에서 불일치가 발생했다. 이럴 때는 분명히 어느 정도는 비교할 필요가 없이 뛰어넘을 수 있는 구간이 존재할 것이다.  그렇다면, 이 구간은 어떤 기준으로 계산할수 있을까?

 

A) 패턴의 prefix(P[0..j]와 suffix(P[1...j])가 일치하는 최대 길이이다.

 

-> 이 조건이 성립하는 이유는 문자열 탐색을 일정부분 건너 뛸수 있으려면 패턴 내에서 새로운 시작점을 찾는 것이 핵심이기 때문이다. 어차피 중간쯤에서 불일치가 발생했으니 원본 문자열에서 그 부분은 다시 비교할 필요가 없다.

 

따라서, 패턴을 움직임을 통해 얻을 수 있는 효과는

1) 그 원본 문자열의 불일치가 발생한 부분을 건너뜀과 동시에 

2) 패턴에서도 당연히 일치하는 일부분은 건너뛰고 다시 비교를 시작한다는 것이다.

여기서 이전에 match된 부분만큼의 패턴에서 prefix(P[0..j]와 suffix(P[1...j])가 일치하는 최대 길이만큼 패턴을 움직임을 통해 1+2의 두마리 토끼(비교할 필요가 없는 부분, 비교를 시작할 필요가 없는 부분을 다 뛰어넘음)를 다 잡을수 있게 되는 것이다.

 

-> 자세한 예시를 통한 설명은 아래 블로그 참조..

https://m.blog.naver.com/kks227/220917078260

KMP 알고리즘(Knuth–Morris–Pratt Algorithm) (수정: 2019-09-01)

 

-> 다시 아까의 그림을 살펴보자.

: 아까 얻은 아이디어를 통해서 어느 정도 몇칸을 건너뛸수 있는지, 또 패턴의 비교는 어디서부터 시작할 수 있는지를 알 수 있음을 깨달았다. 불일치가 발생한 이전까지의 패턴에 대해서 prefix와 suffix가 일치하는 최대 길이를 구함으로써 일정 부분의 비교를 건너 뛸수 있게 된다.

즉, 이 모든 프로세스를 패턴의 모든 경우에 대해 prefix와 suffix가 일치하는 최대 길이를 미리 계산해두면 빠르게 구할 수 있음을 알 수 있다. 그래서 이를 미리 계산해 놓는데, 이 함수를 실패함수, Failure Function 라고 한다.

 

 

-> abaaba에 대해서 pattern의 모든 substring에 대해 미리 failure function을 구해놓았다. 

(시작점은 제외한다)

 

-> Substring은 무조건 이전의 function값을 기준으로 한다. 따라서 값이 매번 최대 1개씩 늘 수 있다.

 

 

: 패턴을 움직일 때 j에서 불일치가 발생하면, F(j-1)을 참조해 비교할 필요가 없는 부분은 건너뛰고 F(j-1)+1 에서 비교를 시작한다.

-> Pseudocode를 통해 자세한 것은 살펴보자.

 

 

 

 

 

 

 

-Pseudocode

 

-> KMP 알고리즘은 O(m+n)만큼의 시간 복잡도를 갖고 있다.

 

# 실패 함수의 수도코드 또한 완전히 동일한 형태를 갖고 있다. T가 P로 바뀌었을 뿐.

: 약간 다른 점이라면 매번 match가 발생할때 failure function값을 저장하는 것이다.

 

 

-Example

 

 

 

5. Boyer-Moore Heuristic

Boyer-Moore 알고리즘은 KMP 알고리즘과 다르게 텍스트에 대해 패턴의 오른쪽(끝) 부터 일치여부를 탐색한다.  과연 이것은 어떤 의미를 갖고 있을까?

 

-> 패턴을 뒤에서부터 비교하기 시작해서, 불일치가 발생하면 그 지점에서 원본 문자열의 character와 패턴에서 가장 가깝게 있는 동일한 character가 같은 자리로 오게끔 패턴을 옮긴다.

예를 들어 위에선 a,b에서 불일치가 발생했으므로 패턴에서 가장 가깝게 a가 있는 앞자리로 패턴을 옮겨놓고 뒤에서부터 다시 비교를 시작한다. 이를 bad character heuristic이라고 한다.

-> 즉 어떤 문자에서 불일치가 발생하든 그 문자가 패턴에서 어디에서 가장 마지막으로 등장하는지 (last occurence)를 미리 기록해 놓아야 이 작업을 빨리 할 수 있다. 이 작업을 last occurrence function이라고 한다.

 

 

-> 만약 abacab라는 패턴이 있을때, 원본 문자열에서 발생하는 모든 문자를 ∑로 표현하고, 이 문자들이 패턴의 어느 index에서 마지막으로 발생하는지를 저장해둔다. 오른쪽->왼쪽, 끝->처음으로 비교하기때문에 pattern의 점프를 최소화하기 위해서는 마지막 발생위치로 패턴을 옮기게 되기 때문이다.

 

- 만약 bad character가 pattern에 존재하지 않는 경우도 있다. 이 경우에는 어떤 패턴의 문자에도 mismatch가 일어나기 때문에 패턴의 길이만큼 뛰어 넘게 된다.

 

 

-Pseudocode

1) 만약 bad character의 마지막 발생 위치가 pattern의 현재 위치의 뒷부분에 존재하면, 그냥 pattern을 한칸 옮기고 다시 비교를 끝에서부터 시작한다.

2) 만약 bad character가 앞에 위치하면 그 위치로 패턴을 옮기고 뒤에서부터 다시 비교를 시작한다.

3) 만약 bad character가 패턴에 존재하지 않으면 bad character의 다음 칸에 패턴의 시작점을 두고 패턴의 길이만큼 패턴을 옮긴다.

 

- Example

시간 복잡도 : O(nm+s)만큼의 시간이 걸린다. 최악의 경우에 brute force와 비슷할 수도 있지만 영어 text에서 이 알고리즘은 상당히 좋은 속도를 보여준다.

 

Bruteforce: O(nm) , KMP: O(m+n), Boyer-Moore: O(mn+s)