http://alones.byus.net/tt/726
아무런 알고리즘을 사용하지 않고 어떤 text에서 특정 문자열 "abcde"을 찾는다고 가정한다면, 아주 많은 비교 (comparison) 때문에 큰 문자열 (characterset)에서 찾는 경우 수행 속도가 느릴 것이다.
아무런 알고리즘을 사용하지 않고 어떤 text에서 특정 문자열 "abcde"을 찾는다고 가정한다면, 아주 많은 비교 (comparison) 때문에 큰 문자열 (characterset)에서 찾는 경우 수행 속도가 느릴 것이다.
Boyer-Moore 알고리즘 아주 빠른 text matching (searching) 알고리즘으로 1975년 경에 고안되었으며 현재 많은 에디터 프로그램들에서 문자 검색에 사용되어지고 있다.
프로젝트에서 만들어서 사용하고 있던 에디터의 문자열 검색 속도 향상을 위해서 Boyer-Moore 알고리즘을 적용했는데 결과는 대 만족이다.
아래 위키에서 최신 내용을 볼 수 있을 것이다..png)
in my wiki: http://alones.byus.net/moniwiki/wiki.php/boyer_moore?action=show
브라우저를 늘리면 가로가 늘어나지만 그래도 아래 위키가 코드를 보기에는 편할 것입니다.
- initial version: 2007.07.29
1 들어가기 전에 #
알고리즘의 이론적 접근 보다는 잘 용하기 위한 접근을 문서를 작성했다. "잘 사용하기 위한" 이라는 것은
- 알고리즘을 정말 잘 이해하고 다른 사람들이 쉽고 실수 하지 않게 사용할 수 있게
- 알고리즘을 일단 구체화 시켜 (알고리즘이든 pseudo 코드든) 생각 없이 바로 쓸 수 있게
2 Terminology #
혼선을 줄이기 위해서 이 문서에서 사용하고 있는 용어는 다음과 같다.
- 대상 text (source text): 검색의 대상이 되는 문자열 (characterset)로 특정 pattern text를 이 속에서 찾을 것이다.
- 패턴 text (pattern text): 찾을 문자열 (characterset)을 의미한다.
- occurrenc: 대상 text에서 패턴 text의 문자가 같을 때
- index: 문자열의 array index를 의미
3 Boyer-Moore algorithm #
Boyer-Moore 알고리즘 아주 빠른 text matching (searching) 알고리즘으로 1975년 경에 고안되었으며 현재 많은 에디터 프로그램들에서 문자 검색에 사용되어지고 있다. 알고리즘을 별도로 생각하지 않고 특정 문자열을 검색한다면 아주 많은 비교 (comparison)을 수행해야 할 것이다.
아무런 알고리즘을 사용하지 않고 어떤 text에서 특정 문자열 "abcde"을 찾는다고 가정한다면,
source text ...a b c d k... pattern text a b c d e index 0 1 2 3 4
위와 같은 경우 index 0을 검색할 차례라고 했을 때 0부터 3까지 match된다고 하더라도index 4가 틀리기 때문에 불일치 할 것이고 다음 차례를 검색해야 할 것이다. 문제는 다음 차례가 index 1이라는 것이다. index 1에서 다시 "abcde"가 나타나는지 확인해야 할 것이다.
text의 문자 개수가 n 개이고, 찾을 문자열의 개수가 m 개인 경우 cpu에서 많은 시간을 소비하는 비교 연산이 최악의 경우는 n*m 번 일어나야한다.
Boyer-Moore algorithm은 위의 비교 연산을 줄이기 위해서,
문자열이 불일치 할 때 대상 text에서 다음 비교를 위해서 이동할 위치를 최대화한 알고리즘이다.
문자열이 불일치 할 때 대상 text에서 다음 비교를 위해서 이동할 위치를 최대화한 알고리즘이다.
이동 위치의 최적화를 위해서 Boyer-Moore algorithm은 다음과 같은 방법을 사용했다.
- 패턴 text를 전처리 (pre-processing) 해서 가능한 최대 이동 거리를 미리 계산한다.
- 휴리스틱 (heuristic)으로 best case와 worst case를 계산해 둔다.
- 비교 시 best case와 worst case 중 가장 큰 이동 거리를 선택한다. ※ 연산 시간이 많이 걸리는 비교 (comparison) 연산을 최소화 하기 위한 것이다.
- 대상 text에서 index는 왼쪽에서 오른쪽으로 이동시키지만 비교는 패턴 text를 기준으로 오른쪽에서 왼쪽으로 수행한다.
4 원리 #
Boyer-Moore 알고리즘에서 사용하는 이동 방법에 대해서 설명하겠다. 패턴 text로 대상 text에서 비교를 수행하다 일치하지 않는 문자가 나왔을 때 이동하는 방법은 good-suffix shift와 bad-character shit의 두 가지 방법이 있다.
4.1 good-suffix shift #
good-suffix shift이동을 하기 위해 우리는 이 알고리즘은 패턴 text를 대상 text에서 비교할 때 오른쪽에서 왼쪽으로 한다는 것을 상기해야 한다. suffix의 의미는 패턴 text 내에 반복되는 문자열이 있으니 이동할 때 첫 번째 반복되는 문자열은 이미 확인했으니 다시 확인하지 않게 두 번째 반복되는 문자열의 위치를 고려해서 이동하는 것이다.
source text ... Y Y Y Y a b Y Y
pattern text a b X X a b
index 0 1 2 3 4 5 6 7 8 9
current check: 3
Y는 확인되지 않는 대상 text의 문자이다. X는 패턴 text에서 'a'나 'b'가 아니고 서로 다른 문자이다. 위와 같이 index 5와 4는 같은데 index 3에서 틀린 문자가 나온다면 pattern text를 이동시켜야 하는데 "ab"가 이미 같은 것을 확인했고 패턴 text 내에 "ab"가 반복되기 때문에 아래와 같이 이동할 수 있다는 것이다.
source text ... Y Y Y Y a b Y Y Y Y
pattern text a b X X a b
after shift a b X X a b
index 0 1 2 3 4 5 6 7 8 9
current from 9 to 0
그리고 비교는 패턴 text의 가장 오른쪽인 index 9부터 수행한다는 것이다.
이와 같은 good-suffix shift는 다음과 같이 두 가지 경우가 있을 것이다.
전처리에서 패턴 text 내에 동일한 부분이 있는지 찾고 이동 위치를 계산하는 과정이다.
4.2 good-suffix shift: case 1 #
아래 그림에서 u가 이미 비교한 문자열이고 패턴 text의 'a'가 나와서 틀린 부분이 나왔고, 패턴 text내에 u가 반복되는 부분이 있으면 (물론 반복되는 u의 왼쪽 바깥쪽 문자인 'c'가 'a'와는 틀릴 것이다.) 다음과 같이 이동할 것이다. 그리고 이동 후 다시 패턴 text의 제일 오른쪽 부터 비교해 갈 것이다.
4.3 good-suffix shift: case 2 #
case 1과 같이 전체 u가 반복되는 것이 아니고 u의 일부분이 패턴 text에서 반복된다면 아래와 같이 이동할 것이다. 이 것은 good-suffix shift 개념에대한 설명에서 예로 든 것과 유사할 것이다.
[edit]
4.4 bad-character shift #
bad-character shift는 good-suffix shift와는 다르게 패턴 text 내에 반복되는 문자열이 없는 경우이다. 이 경우는 비교 도중 틀린 문자가 나올 경우 패턴 text 내의 다른 부분에 문자열이 있다면 그 문자열로 이동시키면 될 것이고 (최소한 한 문자는 같으니) 틀린 문자가 패턴 text에 없다면 패턴 text만큼 이동 시키면 될 것이다. 여기서 관건은 틀린 문자가 패턴 text에 있는지 없는지 확인하는 과정일 것이다. 비교 도중 틀린 문자열이 패턴 text의 다른 부분에 있는지 일일이 비교 (comparison)해서 찾는 다면 수많은 비교 연산이 일어날 것이다. 그래서 전처리 과정에서 다음과 같이 비교가 아닌 array access로 이 문제를 처리한다.
- ascii code 만큼의 array를 만들고 값을 모두 패턴 text의 크기 만큼 잡는다
- 이 경우는 비교 도중 틀린 대상 text의 문자가 패턴 text의 나머지 부분에도 없다는 것을 의미
- 패턴 text의 문자의 ascii code 값을 index로 해서 해당 index의 값을 패턴 text 길이에서 패턴 text의 문자 위치를 뺀 값을 넣는다.
- 비교 도중 틀린 대상 text의 문자가 패턴 text의 나머지 부분에 나타날 경우 (occurrence) 이동할 거리를 계산해서 넣는 것이다.
- 비교 도중 틀린 대상 text의 문자가 패턴 text의 나머지 부분에 나타날 경우 (occurrence) 이동할 거리를 계산해서 넣는 것이다.
bad-character shift의 코드를 잠시 보면 아래와 같다.
// bad-character shift array를 만드는 함수 void preBmBc(char *x, int m, int bmBc[]) { int i; // ASIZE는 ascii code 크기인 256이다. // m은 패턴 text의 크기이다. for (i = 0; i < ASIZE; ++i) bmBc[i] = m; // 패턴 text 문자의 ascii code에 해당하는 index에 // 패턴 text 전체 길이에서 문자의 위치를 뺀 값을 // 넣는다. for (i = 0; i < m - 1; ++i) bmBc[x[i]] = m - i - 1; }
//
검색할 패턴 text 내에 동일하게 반복되는 문자열이 없다면 bad-character shift가 사용될 것이다.
4.5 bad-character shift case 1 #
bad-character shift의 첫 번째 경우는 비교 도중 틀린 대상 text의 문자가 패턴 text에 있는 경우로 아래와 같이 패턴 text를 이동한다.
패턴 text에서 'a'까지 비교했는데 대상 text의 'b'와 일치하지 않았고, 'b'는 패턴 text에 존재해서 'b'를 현재 index에 이동 시킨 것이다.
4.6 bad-character shift case 2 #
bad-character shift의 두 번째 경우는 틀린 문자가 패턴 text에 없는 경우로 이 경우는 패턴 text의 길이 만큼 이동하면 된다.
5 Code #
첨부한 class는 멀티 바이트 처리를 위해서 원본 pseudo 코드를 조금 수정하고 원본 c code를 class로 만들었다. 멀티 바이트에 대해서는 검색을 할 수 있게 bad-character shift array와 search 부분을 수정했지만 멀티 바이트의 한 바이트 값이 음수인 경우 때문에 Boyer-Moore 알고리즘을 그대로 발휘하게 고치지는 못했다. (즉 멀티 바이트의 경우는 틀린 부분이 있는 경우 한 글자씩 이동한다)
※ 멀티 바이트에 대해서도 Boyer-Moore 알고리즘을 그대로 반영할 수 있게 수정할 계획이다.
5.1 CAloBM.h #
/** * @file AloBM.h * @brief CAloBM class * @author alones * @date initial version: 2007.07.29 * @brief * http://alones.byus.net/moniwiki/wiki.php/boyer_moore?action=show */ #ifndef __ALO_BM_H__ #define __ALO_BM_H__ //#include "string.h" /** * @class CAloBM * @brief Boyer Moore text matching algorithm */ class CAloBM { protected: /** * @brief make bad-character shift * @param[in] x (char*) pattern text * @param[in] m (int) length of x * @param[out] bmBc (int[]) bad-character shift array * @return */ static void preBmBc(char *x, int m, int bmBc[]); /** * @brief make suffix for good-suffix shift array * @param[in] x (char*) pattern text * @param[in] m (int) length of x * @param[out] suff (int*) suffix array * @return */ static void suffixes(char *x, int m, int *suff); /** * @brief make good-suffix shift * @param[in] x (char*) pattern text * @param[in] m (int) length of x * @param[out] bmGs (int[]) good-suffix shift array * @return */ static void preBmGs(char *x, int m, int bmGs[]); public: /** * @brief search x string in y string * @param[in] x (char*) pattern text * @param[in] y (char*) source text * @return int index of x in y */ static int BM(char *x, char *y); }; #endif //__ALO_BM_H__
//
5.2 CAloBM.cpp #
/** * @file AloBM.cpp * @brief CAloBM class impl. * @author alones * @date initial version: 2007.07.29 * @brief * http://alones.byus.net/moniwiki/wiki.php/boyer_moore?action=show */ #include "AloBM.h" #include "string.h" #define ASIZE 256 #define BM_MAX(a,b) a >= b ? a : b; void CAloBM::preBmBc(char *x, int m, int bmBc[]) { int i; for (i = 0; i < ASIZE; ++i) bmBc[i] = m; for (i = 0; i < m - 1; ++i) { // ascii code 내에 있는 것만 처리 // multi byte 등은 x size 그대로 둠 if( x[i] >= 0 && x[i] <= 255) bmBc[x[i]] = m - i - 1; } } void CAloBM::suffixes(char *x, int m, int *suff) { int f, g, i; suff[m - 1] = m; g = m - 1; for (i = m - 2; i >= 0; --i) { if (i > g && suff[i + m - 1 - f] < i - g) suff[i] = suff[i + m - 1 - f]; else { if (i < g) g = i; f = i; while (g >= 0 && x[g] == x[g + m - 1 - f]) --g; suff[i] = f - g; } } } void CAloBM::preBmGs(char *x, int m, int bmGs[]) { int i, j; int* suff = new int[ strlen(x)+1]; // make suffix suffixes(x, m, suff); for (i = 0; i < m; ++i) bmGs[i] = m; j = 0; for (i = m - 1; i >= 0; --i) if (suff[i] == i + 1) for (; j < m - 1 - i; ++j) if (bmGs[j] == m) bmGs[j] = m - 1 - i; for (i = 0; i <= m - 2; ++i) bmGs[m - 1 - suff[i]] = m - 1 - i; if( suff ) { delete [] suff; suff = NULL; } } int CAloBM::BM(char *x, char *y) { int i, j, m, n, bmBc[ASIZE]; int* bmGs; int tempBmBCVal; int nFind = 0; if( x == NULL || y == NULL) return -1; m = strlen(x); n = strlen(y); bmGs = new int[ m + 1 ]; /* Preprocessing */ // make good-suffix shift array preBmGs(x, m, bmGs); // make bad-character shift preBmBc(x, m, bmBc); /* Searching */ j = 0; while (j <= n - m) { for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i); if (i < 0) { nFind = 1; goto _BM_RET; // j += bmGs[0]; } else { if( y[i+j] >= 0 && y[i+j] <= 255) tempBmBCVal = bmBc[ y[i+j] ]; else tempBmBCVal = 1; j += BM_MAX(bmGs[i], tempBmBCVal - m + 1 + i); } } _BM_RET: if( bmGs ) { delete [] bmGs; bmGs = NULL; } if( nFind ) return j; else return -1; }
5.3 Usage #
#include "AloBM.h" #include <string> #include <iostream> void main() { // source text std::string strSource = "this is a test text. 멀티바이트 테스트"; // 10 25 std::string strPattern = "test"; std::cout<<"source text: "
<<strSource.c_str()<<std::endl; // find "test" int nIndex = CAloBM::BM(
(char*)strPattern.c_str(),
(char*)strSource.c_str()); std::cout<<"pattern: "
<<strPattern<<" index: "<<nIndex<<std::endl; strPattern = "바이트"; // find "바이트" nIndex = CAloBM::BM(
(char*)strPattern.c_str(),
(char*)strSource.c_str()); std::cout<<"pattern: "
<<strPattern<<" index: "<<nIndex<<std::endl; }
![[http]](http://alones.byus.net/moniwiki/imgs/http.png)
