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

먼저 새로운 다짐을 하고 새해 처음 쓰는 글이다. 이미 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, 보이어 무어 알고리즘중 이게 제일 맘에 든다. )








Posted by 차출발 차출발

댓글을 달아 주세요

  1. BlogIcon . . 2010.04.21 10:58 신고  댓글주소  수정/삭제  댓글쓰기

    라빈-카프..
    덕분에 이해를 조금이라도 한 것 같아요.

    블로그에 좋은 글이 참 많은 것 같습니다^^

    하시는 일 모두 잘 되시길 기원합니다^^

  2. 2010.06.10 05:35  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다

  3. BlogIcon 코알라라랑 2010.06.29 16:38 신고  댓글주소  수정/삭제  댓글쓰기

    우와!!!!!! 정말감사합니다!! 정말쉽게이해되는군요 ^^

  4. 전성모 2010.11.13 10:42  댓글주소  수정/삭제  댓글쓰기

    카프라빈.. 재미있게 잘 읽었습니다. C로 구현해보니 좀 지저분해지더군요.. ㅡ.ㅜ
    다시 한번 깔끔하게 만들어보겠습니다 .. ^^

  5. 2011.09.30 14:19  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다

  6. 작은이리 2012.01.27 14:29  댓글주소  수정/삭제  댓글쓰기

    KMP에 이어 카프라빈도 도움이 많이 되었습니다. KMP보단 구현이 쉽겠네요 ㅎ 감사합니다. ㅎ

  7. heeju 2012.02.03 15:25  댓글주소  수정/삭제  댓글쓰기

    책으로 봤을때는 이해가 안됬는데 이 글을 읽으니까 이해가 매우 잘되네요
    감사합니다 ㅎㅎ

  8. BlogIcon Flaskl 2012.02.09 14:05  댓글주소  수정/삭제  댓글쓰기

    감사합니다.

  9. joono 2012.04.07 10:25  댓글주소  수정/삭제  댓글쓰기

    쉽게 설명을 잘해주시네요~! (제가 쉽게 구현할 수 있을지는 미지수지만;;;)

    좋은글 감사합니다 ~~~/

  10. 질문있습네다 2013.05.31 16:02  댓글주소  수정/삭제  댓글쓰기

    덕분에 잘 이해했습니다.

    다만 궁금한점은 "알파벳 * 2^자리수"를 더하는 형식으로 하셨는데
    2보다는 27이 더 적절하지 않을까... 싶네요 ㅋ 책을 봤을때는 총 표현가능한 문자 갯수가 들어가야한다는데...
    굳이 안그래도 잘 나오긴 하네요 ㅋㅋ

    그리고 하나 더 궁금한점은 한글도 응용이 가능할까요?ㅋㅋ 한글은 갯수가 음청 많은데... ㄷㄷ

  11. 현수 2013.06.08 16:19  댓글주소  수정/삭제  댓글쓰기

    와 책으로 너무 어려웠는데, 쉽게 설명해주셔서 감사합니당~~~~~~!!!! 짱이에요

  12. 양자리 2013.09.26 20:57  댓글주소  수정/삭제  댓글쓰기

    아 정말 이렇게 이해가 쉽게 될 줄이야 ! 정말 감사드립니다 ~ 보는내내 소름이 ㅎ
    참, 혹시 단어를 분류할때 사용하는 좋은 알고리즘에 관해 알고 계신거 있으신가요 ?

  13. 아루레이 2014.01.14 14:47  댓글주소  수정/삭제  댓글쓰기

    감사합니다. 도움이 많이 되었습니다. ㅎㅎㅎ

  14. Juno 2014.04.06 17:39  댓글주소  수정/삭제  댓글쓰기

    쉬운 설명 감사드립니다ㅎㅎ

  15. kangsk0226 2014.04.20 02:45  댓글주소  수정/삭제  댓글쓰기

    책보다 낫네요. 설명이 엄청 자세하고, 구성이 깔끔합니다.
    정말 많은 도움이 되었습니다.

  16. 감사합니다. 2015.05.20 16:20  댓글주소  수정/삭제  댓글쓰기

    정말 빠르게 이해하기 쉽게 설명해 주셨네요 감사합니다. :)
    그런데 해쉬값을 계산하려면 나머지 연산을 하기 전의 값으로 해주어야 하는것 같은데요.
    그러면 굳이 나머지 법을 사용하는 이유가 있나요? 제가 뭘 잘못 이해한 걸까요? ㅠㅠ
    C로 구현하고 보니 나머지 연산을 왜 해주어야 하는지 잘 모르겠어서 질문 드려요.

  17. 2015.06.12 15:58  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다

  18. 감사합니다 2015.08.23 10:59  댓글주소  수정/삭제  댓글쓰기

    쉬운 설명과 동영상 첨부 감사합니다 ㅎㅎ

  19. 도레미축구 2015.10.22 23:18  댓글주소  수정/삭제  댓글쓰기

    감사합니다 ^^
    이해하기 쉽게 글을 잘 쓰시네요~