[알고리즘] 카프-라빈 알고리즘 (문자열 검색 #1)

카프-라빈 알고리즘에 대해서 설명해보려고 한다.

먼저 새로운 다짐을 하고 새해 처음 쓰는 글이다. 이미 20일이지만.. ㅋㅋ

내글을 한방에 읽고 카프-라빈 알고리즘이 머리에 꽉 박히면 좋겟다.

박혔으면 리플은 남겨주는 센스... ㅎㅎㅎ

리플을 남겨주면 이 글을 써놓은 보람이 생겨서 재미를 느끼고 글을 쓰게 되는거 같다.

말이 길었다.

카프 라빈 알고리즘에 대해 알아보자

오늘 나는 읽고 싶은 책이 생겨서 학교 도서관을 갔다. 

읽고 싶은 책은 "카프-라빈 이 들려주는 이야기 " 어라 이 책이 어디 있을가? 

앞에 컴퓨터가 있다. 음 여기서 찾으면 되겠군 ㅋㅋㅋ

검색란을 사용해야 겠다.

카프-라빈  검색 클릭! 

짠 A열 135번에 있단다. 

자 여기서 우리는 한번 짚어 보자

검색하는 과정을 보자 

우리는 여기서 카프-라빈 이라는 문자를 검색했다.

문자열을 검색하는데 도서관이면 엄청난 량의 책 제목이 있을 건데 

제목이 바로 뜬다.... 와 쩔군

의문이 생긴다. 이걸 일일이 다 검색하면 이 속도가 안나올텐데.. ㅋㅋㅋㅋ

(이런 의문이 생기는게 비정상이다. ㅋㅋㅋ)

그렇다  이걸 일일이 다 검색하는 것은 멍청하다

그런 방식이 직선적 알고리즘이다. 고지식한 검색(naive Search),  무식한 검색(Brute Force Search)이라 불린다.

이방식은 글자 크기 만큼 지속적으로 한칸식 이동하는 시간이 먼저 걸린다.

거기에 글자 크기안에서 글짜끼리 맞는지도 확인하는 시간이 걸린다. 

이를 보안하는 알고리즘으로 다양한 방법이 있는데 (카프라빈, KMP, 보이어무어)등이 있다.

카프-라빈 사람인지는 몰라도

이런 방법을 제안하였다.

이것을 해시값으로 접근해서 찾는다면 글자 크기안에서 글짜 끼리 확인하는 시간을 줄일수 있다. 

여기서 해시에 대해서 모른다면 해시를 먼저 배우고 이 글을 보기 바란다. 

.......................

본문에서 문자열을 검색하는 간단한 예를 들어서 설명 하겠다.

설명하기 전에 다음과 같이 정의 하겟다.

S  < 본문>

S[n]  <본문에서 n번째 문자>

m  <찾을려는 문자열 길이>

H  <문자열에 대한 해시함수 값>

예를 들어 크기가4인 문자열을 찾는다.

해시 함수는 다음과 같이 정의 한다고 했을때  

문자열의 크기가 4이기 때문에 처음 문자열의 해시값은 다음과 같을 것이다.  

한칸 전진한 문자열의 해시값은 다음과 같다.

아 이렇게 한칸식 이동해서 해시값을 구하고 값이 나오면 같은것만 찾으면 되구나 ... 

근데 이렇게 계산하는 비용이 더들겠다 차라히 비교하고 말지 

카프-라빈은 갑자기 문득 생각이 났다.

위의 식 H1 을 보자

H1 의 식에서 2^n 이기에 2가 공통으로 들어 감을 알수 있다.

그렇다 먼저 [1][2][3] 만 2로 묶어보자 

해보면 다음 식을 얻을 수 있다.

그리고 이식 가로 안에다 S[0]을 더해주고 빼어 보자

어차피 더해주고 빼주면 0이므로 같은 식이다.  (H = H +S[0] -S[0])

그러면 다음과 같은 식을 얻을 수 있다. 파랑색이 더해준거고 빨강색이 빼준거다 

자 여기서 우리는 한가지를 발견 할수 있다. 앗 H0가 안에 들어 있네

그 식을 H0 로 표현하자

그러면 다음과 같은 식을 얻게 된다.

오우 H1도 해보고 H2를 계속 해보면 다음과 같은 규칙을 발견 할 수 있다.

앗 이말은 항상 찾을려는 문자의 길이와는 상관없이 항상 2개의 문자에만 접근하면 해시값을 쉽게 구하네

그렇다 항상 2개문자에만 접근 하고 이전 데이터만 알면 해시값을 다 구할 필요가 없다.

이전데이터만 알아야한다. 여기서 문제는 첫항

아 어쩔수 없이 첫항은 해시값을 다 구해줘야한다. 

이제 첫항을 알았으니 다른 항들은 항상 2개 문자만 더 알면 접근 할 수 있다.

그럼 결론은 이거네

첫항 즉 i=0일때는 해시 값을 다구해주고

두번째 항부터 즉 i>0 일때는 이전데이터에다 2개 문자만 접근

이게 카프-라빈 알고리즘이다.

말로 설명하니 잘 이해가 안갈것이다.

실습을 해보자

카프라빈 동영상을 보자

예를 들어 본문은 ABACCEFABADD 가 있다.

여기서 우리는 CCEFA라는 패턴을 찾을려고 한다.

그림으로 보면 이해하기 쉽다.

먼저 찾을려는 패턴의 해시값을 구한다. 빨강색이다.  2089값이 나왔다 (해시함수의 나머지법을 사용)

이제 문자열에서 찾기 시작한다.

먼저 첫번째 라인이다.

아까도 말했드시 문자열의 초기 값은 해시값 그대로 구해줘야한다.

구한 결과 2029가 나왔다 찾을려는 문자열 값은 2089이기에 맞지 않다.

다음 한칸 전진

첫항 이후 부터는 두개의 문자열에 접근하면 모두 구할 수 있다

ABACC 에서 한칸 전진하면  BACCE 이다.

그림을 보면 첫 H0 ABACC 에서 노랑색으로 표시된 A가 빠지고 뒤에 빨강색 E가 붙음을 알수 있다.

그렇다  H0  - 노랑A + 빨E 가 붙으면 바로 해시값  2047 이 나오는 거다.

이것도 일치 안하므로 

계속 진행한다

2052 이번에도 일치 안한다.

다음 2089 가 나왔다.

드디어 일치한다.

하지만 이것을 다시 검증하는 방법이 필요하다.

이유는 해시값은 동일한 다른 문자열이 존재 할수 있기 때문이다.

그래서 이렇게 해시값만 가지고 일치 한 문자열을 다시 무식한 방법으로 일일이 비교 해서 그거 마저 일치하면

문자열에서 검색이 되는 것이다.

이제 카프-라빈 알고리즘의 이해는 마스터를 했을 것이다.

위의 내용을 다 알았다면 당신은 이제 카프-라빈 알고리즘을 직접 구현해보아라

그럼 진정한 카프-라빈 알고리즘을 진정으로 마스터 한것이다.

(개인적으로 카프-라빈, KMP, 보이어 무어 알고리즘중 이게 제일 맘에 든다. )