chapter10 문자열탐색

10.1 문자열 탐색 알고리즘의 개요

Ctrl+F : 탐색단축키

• 본문 : 탐색 대상 문자열
• 패턴 : 탐색어
• 이동 : 탐색 위치 옮기기

10.2 고지식한 탐색 알고리즘

• 본문 길이가 n이고 패턴 길이가 k이면 인덱스 0~n-k까지 패턴단위로 한 칸 한 칸 옮겨서 탐색 해보는 것

• 최악의 경우 NxM번의 비교 수행

10.3 카프-라빈 알고리즘

알고리즘의 핵심 : 해싱

10.3.1 카프-라빈 알고리즘의 동작 방식

• 문자열 탐색을 위해 해시 함수를 이용한다.
• 패턴의 해시값과 본문 내의 하위 문자열의 해시값을 비교하는 방식
• 연산 비용은 더 커보이는데 천재적인 영감은? 해시함수의 비용을 획기적으로 줄이는 방법

패턴의 길이 m = 4
본문 = S[0…3]인 해시값 H = S[0]x2^3 + S[1]x2^2 + S[2]x2^1 + S[3]x2^0
본문 = S[1…4]인 해시값 H2 = S[1]x2^3 + S[2]x2^2 + S[3]x2^1 + S[4]x2^0

원래의 해시함수로는 비교할 때마다 매번 패턴길이 m만큼 문자에 접근해야 하지만, 새 해시 함수를 이용하면 2개의 문자에만 접근하면 된다.

• 새로운 해시함수(앞 단계에서 계산해놓은 H(i-1)에서 S[i-1] 부분의 해시값을 빼고 S[i+m-1]부분의 해시값을 더해서 다음 해시값을 구할 수 있도록 식을 간추림)

Hn =2(H(i-1) - S[i-1]x2^(m-1)) + S[i+m-1]x2^0
= 2(H(i-1) -S[i-1]x2^(m-1)) + S[i+m-1]

패턴 길이와 상관없이 본문 길이에만  영향을 받으므로 탐색 성능이 향상된다.
다만 H(0), 최초의 해시값을 미리 구하기 위해서는 기존의 해시함수를 사용해야 한다.

1. 그리고 본문을 한칸 한칸 옮겨가면서 패턴의 해시값과 일치하는지 확인한다.
2. 패턴의 해시값과 일치하는 부분을 찾으면 찾아낸 문자열이 패턴과 일치하는지 증명한다 (서로 다른 문자열에서 얻어낸 해시값이 동일한 경우(충돌)도 생길 수 있다)

10.4 KMP 알고리즘

KMP알고리즘은 ‘고지식한 탐색’과 비슷하다
그러나 KMP알고리즘은 비교할 필요 없는 부분은 지나치고, 비교가 필요한 부분만 비교를 수행하는 똑똑한 알고리즘이다.

How? 본문 내 문자열을 한차례비교하고 나면, 다음단계 탐색에서 사용할 수 있는 ‘어떤 정보’가 남으며, 이 정보를 이용하면 불필요한비교를 피할 수 있다는 사실을 알아냈다.

Then? 이’ 어떤 정보’가 무엇인지, 이 정보를 ‘어떻게 활용하는가’에 대한 것

10.4.1 KMP 알고리즘의 동작 방식

접두부와 접미부를 나눈다.
경계 : 접두부와 접미부 쌍을 가리킨다
KMP알고리즘은 이 경계를 활용해서 불필요한 문자 비교를 피한다.

1. 본문에서 패턴과 일치하는 부분이 생긴다.
2. 패턴에서 경계값이 있다? 그렇다면 본문의 경계값도 똑같다. (일치하는 부분이니까)
3. 그러면 나머지는 뛰어넘어서 경계값으로 JUMP!!
4. 이때 패턴의 탐색 위치 이동거리는 일치하는 부분의 문자열 길이에서 경계의 길이를 뺀 값과 같다. (당연하겠지머,,)

따라서 KMP알고리즘은 본문의 길이가 n일 때 최대 n번 만큼만 비교를 수행하면 본문에서 패턴과 일치하는 문자열의 위치를 알아낼 수 있다.

10.4.2 경계 정보 사전 계산 방법

“경계를 찾는 데 소요되는 비용은 공짜가 아닐텐데?”
탐색 중간에 매번 경계를 찾는다면 비용이 만만치 않다.
따라서 미리 패턴으로 부터 경계의 정보를 가진 테이블을 만든다.

10.5 보이어 - 무어 알고리즘

문자열을 오른쪽에서 왼쪽으로 비교해 나간다.
하지만 ‘이동’만큼은 왼쪽에서 오른쪽으로 이루어진다. 우리가 사용하는 대부분의 프로그램이 이 알고리즘을 사용하고 있다.
끝문자가 패턴 안에서 발견되지 않으면 패턴의 길이만큼 탐색 위치를 이동해서 비교를 재개한다.
크게 두종류의 이동

• 나쁜 문자 이동
• 착한 접미부 이동

불일치가 발생하면 나쁜문자 이동과 착한 접미부 이동 모두를 검토해서 더 멀리 옮겨 가는 이동방법을 선택한다

10.5.1 나쁜 문자 이동

나쁜 문자를 이동시킨다는 뜻
나쁜 문자 : 본문과 패턴사이를 이간질하는 ‘본문의 문자’를 의미한다

• 본문과 패턴의 불일치가 발생하면 본문의 불일치한 문자와 같은 불일치 문자를 패턴에서 찾는다
• 찾아낸 패턴의 불일치 문자 위치가 본문의 불일치 문자 위치와 일치하도록 패턴을 이동시킨다
• 불일치문자와 동일한 문자가 패턴 내에서 2개 이상 나오는 경우, 발견된 문자중 가장 오른쪽에 있는 것을 본문의 불일치 문자에 맞추면 된다.
• 만약 마이너스가 나온다면 착한 접미부 이동!

10.5.2 착한 접미부 이동

착한 접미부 : 패턴에는 본문과 일치하는 접미부가 나타나는데, 이렇게 일치하는 접미부를 착한 접미부라고 부른다.

첫 번째 경우

불일치가 발생하기 전까지 일치했던 접미부 부분과, 일치하는 패턴의 문자열에 존재할 때, 찾아낸 패턴의 부분이 본문의 착한 접미부 위치와 일치하도록 패턴을 이동시킨다

두 번째 경우

첫 번째 부분을 만족하지 않는다면, 착한 접미부의 접미부가 패턴의 접두부와 일치하는지 따져봐야 한다.