[Algorithm]Boyer-Moore

 

대상 문자열 : text

찾을 패턴 문자열 : pattern

 

brute force 알고리즘은 

http://ir.bagesoft.com/37

 

굉장히 비효율적이다. (하지만 구현이 빠르고 추가 연산이 필요 없다.)

그래서 사람들이 생각한 게, '어떻게 하면 적게 비교해서 pattern을 찾을까... 였다.  

Boyer-Moore알고리즘을 알아보려고 한다.

 

(http://xenostudy.tistory.com/72  다른 자료도 많겠지만 여기보고 이 알고리즘을 이해했습니다. 

제가 이해한걸 적어보려고 합니다. )

 

 

먼저 접미사, 접두사에 대해 알아야 한다. 앞에 붙어있는 게 접두사, 뒤에 붙어있는 게 접미사

(조사하면서 영어공부도 같이했네요 ㅋㅋ  http://jujubong.tistory.com/70)

 

Boyer-Moore의 가장 큰 특징은 다른 알고리즘은 왼쪽에서 오른쪽으로 비교하는데 

반대로 오른쪽에서 왼쪽으로 비교를 한다. 

뭔가 있기 때문에 오른쪽부터 비교하지 않았을까?  그렇다. 접두사 접미사를 여기서 사용한다.

 

적게 비교하기위해 3가지 비교 방법을 사용한다. (bad-case 1개, good-case 2개)

 

 

먼저 bad-case

pattern내에 접미사와 동일한 게 없는 경우다. 그렇다고 한 칸 이동하자니 억울하니 동일한 문자가 있는 곳으로 이동한다.

 

bad-case에서 i가 여러개 있는 경우는, 가장 오른쪽에 위치한 것만 사용한다. 

 왜???? good-case까지 알고나면 이해가 된다.

 

 

good-case (1)

 

 

good-case (2)

 

 

오른쪽에서 왼쪽으로 비교 잘~~하다가 틀렸을 때

매칭 된 접미사가 있는 곳으로 이동할 것인가?(good-case)

 

 

틀린 문자가 있는곳으로 이동할 것인가? (bad-case)이다.

 

 

 

 

 

궁금한 점

* bad-case에서 왜 가장 오른쪽에 위치한 idx를 저장할까?

* 접미사와 동일한 게 pattern에서 여러 개 있으면 어떻게 하나?  

 (제가 궁금했던 점이었습니다. 생각해보니 너무 당연한 거였지만...)

두 질문이 원리는 같으니, good-case를 예로 들겠다.

 

잠시 키보드에 손을 놓고 생각해보자.

 

지금 상태는 c까지 매칭이 된 상태고 그다음 문자에서 틀렸다.

그럼 a로 이동하는 게 좋을까? b로 이동하는게 좋을까?    당연히 좋은건 a로 이동하는게 많이 이동하니까 좋다.

하지만~!!!!!!!!         이 알고리즘의 목적은 많이 이동하는게 주목적이 아니라 문자열 매칭이 주목적이다;;

(저만 이렇게 생각했나요? ;; ㅎ)

그래서 b로 이동한다.   결국 good-case, bad-case 가장 오른쪽에 있는 걸 저장한다.

 

 

 

 

 

https://github.com/kgcrom/algorithms/blob/master/c/searching/string_matching.c

 

이미 짜인 소스 참고하면서 짜 봤다.

(이해한 걸 했다고는 하지만 똑같은 거죠.......... 변수명만 다르고... 뭐 그런 거죠....;;  ,

구현하면서 숨이 턱턱 막혔던 게 배열 index 구하는 거..... 종이에 수십 번 그린 것 같아요 ㅋㅋ)

 

 

소스에 나온 good_case, bad_case는 매칭이 안된 그 자리에서 얼마큼 움직일까?라는 정보를 담았고

j += MAX(good_case[i], bad_case[text[j + i]] - (len_pattern - i) - 1 );

둘 중에 값이 큰 곳으로 이동한다.

 

kmp algorithm같이 틀렸을 경우 최대한 이동할 거리를 미리 구해놓는다는 게 핵심~!!!

 

------------------------------------

 

이것을 학습하게 된 이유는 log를 모니터링하는 일이 많은데, grep을 하게 되면 엄~!!! 청 빠르게 찾아내는 게

신기해서 grep을 조사하다가 하게 되었다.

 

grep이 왜 빠른가??

http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html

http://www.quora.com/Why-is-GNU-grep-so-fast-What-features-give-it-speed-as-compared-to-other-algorithms-and-implementations

* line별로 읽는 것이 아님 (뭉탱이로 읽음)

* read() 대신 mmap() 사용

* Boyer-Moore알고리즘을 사용

 

good-case부분 이해하는데 시간이 많이 걸렸네요.  

이해하는데 조금이나마 도움되고자, 그림 그려봅니다. 근데 글씨 정말 못쓰네요 ㅋㅋㅋㅋ

 

 

 

무작정 좋은 기술 있다고, 좋은 오픈소스 있다고 까 보는 게 아니라 필요에 의해, 목적이 생겼을 때 학습하는 게 

나한테는 맞는 것 같다 : )

 

지문상 존댓말을 생략했는데.... 건방져 보이네요... 이것도 자주 하면 괜찮겠죠? ㅎㅎ (응??? )

틀린 점이나 설명이 애매한 부분이 있으면 알려주세요.~

 

참조 url : 

http://www.cs.utexas.edu/users/moore/best-ideas/string-searching/fstrpos-example.html

http://xenostudy.tistory.com/72