[알고리즘]문자열 검색(고지식한 검색, 라빈-카프, KMP, 보이어-무어)

문자열 검색이란

찾고자 하는 패턴의 문자를 본문 내용에서 어디에 있는지 확인 하는 검색

패턴과 일치하는 방식으로 찾는 방법은 같으나 효율적으로 찾는 알고리즘들을 학습

고지식한 검색 알고리즘

패턴과 본문의 내용을 하나씩 하나씩 맞는지를 처음부터 끝까지 확인하는 방식

패턴의 첫번째는 맞지만 

두번째가 맞지 않으면 

세번째 패턴은 비교하지 않고 본문 다음 글자로 이동

패턴이 일치 하지 않는 경우/ 패턴 중 하나는 일치하지만 다른 하나가 일치 하지 않는 경우 다음으로 이동

패턴이 일치하지 않는 경우 / 패턴이 일치 하는 경우

라빈-카프 알고리즘

해시를 활용한 문자열 검색 

수식에 의한 해시 값을 한칸씩 이동하면서 구하고 본문 해시 값과 패턴 해시 값이 같은지 여부를 확인

해시 충돌 시 이는 무시해도 되며 본문 해시와 패턴 해시 값이 같다면 실제 본분 값과 실제 패턴 값을 비교 확인

라빈-카프 수식

H[i] : 해시값

S[i] : 문자

M : 찾으려는 문자열(패턴) 길이

라빈-카프 검색 방법

패턴의 해시 값

본문에서 패턴의 길이만큼 해시 값을 구하고 해시값이 같지 않다면 한칸씩 이동하며 비교

KMP 알고리즘

KMP(Knuth-Morris-Pratt)은 비교 하지 않도 되는 부분은 무시하고 비교가 필요한 부분만 비교를 수행

왼쪽부터 오른쪽으로 비교하면서 접두부와 접미부로 경계를 통해 비교

문자열에서 일치하는 접두부와 접미부에 해당하는 구간은 경계라고 칭함

경계 정보 테이블 

이동거리 = (에러가 발생한)접두부 길이 + (에러 발생이 이전에 접두부 길이의)최대 경계 너비 

패턴 문자열

경계를 계산한 테이블

접두부의 0에서는 너비가 없으므로 -1로 함

문자열 검색 방법

본문 문자열

문자를 비교 C에서 일치 하지 않음

0~2까지 일치하므로 접두부 길이는 1이고  3에서 일치 하지 않으므로 접두부 길이 3-1= 2

2칸 이동

동일하게 적용하여 1칸 이동

동일하게 적용하여 1칸 이동

일치하는 문자 찾음

보이어-무어 알고리즘

오른쪽에서 왼쪽으로 비교하고 이동은 왼쪽으로 오른쪽으로 하는 방식

대부분의 프로그램이 채택하고 있는 문자열 검색 알고리즘

오른쪽 끝에 문자가 일치 하지 않고 해당 본문 문자가 패턴에 존재하지 않으면 패턴 길이만큼 이동

보이어-무어 이동 방법

불일치가 발생하면 최대의 효율을 내는 방법을 두가지 방법 중 채택

- 나쁜 문자 이동

본문 문자 중 패턴과 일치 하지 않는 문자를 나쁜 문자라고 하며 패턴에서 나쁜 문자와 일치하는 문자를 나쁜 문자의 위치로 이동 

2번째 인덱스 A 불일치 / 1번째 인덱스 B로 이동

- 착한 접미부 이동

본문 문자 중 패턴의 접미부와 일치하는 문자를 착한 접미부라고 하며 2가지의 경우에 따라 이동

첫 번째 경우 : 착한 접미부와 동일한 문자가 왼쪽 문자열중에 존재 하는 경우

두 번째 경우 : 패턴에 착한 접미부가 없지만 접두부와 이리하는 경우/ KMP의 경계

사전 테이블 만들기

나쁜 문자 이동 테이블

방법1

아스키 코드에 해당하는 256개 테이블을 만들고

패턴을 왼쪽에서 오른쪽으로 이동하면서 같은 문자열이면 패턴의 인덱스를 테이블에 저장 다르면 -1 저장

ex) A B A C B 

0 1 2 3 4

-> A : 2, B : 4, C : 3 D : -1, E : -1  ...

이동 거리 구하기 위한 공식 : value = patternLength - index -1 

마지막 문자가 패턴에 이미 있는 경우 = 1

마지막 문자가 패턴에 없는 경우 = 패턴의 길이

패턴에 없는 문자인 경우 : 패턴의 길이

참고

착한 접미부 이동 테이블

착한 접미부를 확인 하자마자 이동 거리를 얻을 수 있도록 착한 접미부의 이동 거리를 사전에 저장

소스는 깃허브에 올렸습니다.