10장 문자열 검색

책정리/뇌를 자극하는 알고리즘

10장 문자열 검색

GONII 2015. 3. 31. 15:52

고지식한 검색

본문(Text) : 탐색 대상이 되는 문자열

패턴(Pattern) : 검색어(검색해야할 문자열)

이동(Shift) : 본문에서의 탐색 위치를 옮기는 것

고지식하거나 미련하거나

본문이 'ABCABACDC'라고 하고, 패턴은 'BA'라고 할 때 간단하게 생각해본다면 대부분 순차 검색을 통해 첫 번째 글자를 먼저 같은지를 검색하고 같은 것을 찾았을 때 뒤에 있는 2번째 글자를 검색할 것이다.

이 알고리즘은 마치 요령부지 않고 그저 우직하게 일하는 일꾼처럼 동작할 것이다. 이러한 알고리즘을 가리켜 고지식한 검색(Native Search), 또는 무식한 검색(Brute Force Search)라고 한다. 본문의 길이를 N, 패턴의 길이를 M이라고 했을 때, 본문 속에 존재하는 패턴을 찾기 위해 최악의 경우 N*M번의 비교를 수행해야 한다.

고지식한 검색의 구현
- 예제 BruteForce.h

#ifndef _BRUTEFORCE_H__

#define _BRUTEFORCE_H__

int bruteForce(char* text, int textSize, int start, char* pattern, int patternSize);

#endif

예제 BruteForce.c

#include "BruteForce.h"

int bruteForce(char* text, int textSize, int start, char* pattern, int patternSize)

{

int i = 0;

int j = 0;

for( i = start ; i <= textSize - patternSize ; i++ )

{

for( j = 0 ; j < patternSize ; j++ )

{

if( text[i+j] != pattern[j] )

break;

}

if( j >= patternSize )

return i;

}

return -1;

}

예제 main.c

#include <stdio.h>

#include <string.h>

#include "BruteForce.h"

#define MAX_BUFFER 512

int main(int argc, char** argv)

{

char* filePath;

FILE* fp;

char text[MAX_BUFFER];

char* pattern;

int patternSize = 0;

int line = 0;

if( argc < 3 )

{

printf("usage: %s<FilePath> <Pattern>\n", argv[0]);

return 1;

}

// argv[1]은 본문이 들어 있는 파일 경로

// argv[2]는 패턴 문자열

filePath = argv[1];

pattern = argv[2];

patternSize = strlen(pattern);

if( (fp = fopen(filePath, "r")) == NULL )

{

printf("cannot openfile:%s\n", filePath);

return 1;

}

// 파일을 처음부터 끝까지 한줄씩 읽으며 bruteForce() 함수 호출

while( fgets(text, MAX_BUFFER, fp) != NULL )

{

int position = bruteForce(text, strlen(text), 0, pattern, patternSize);

line++;

if( position >= 0 )

{

printf("line:%d, column:%d : %s", line, position, text);

}

fclose(fp);

return 0;

}

카프-라빈 알고리즘

해시 값을 활용한 문자열 검색

카프-라빈(Karp-Rabin) 알고리즘은 문자열 검색을 위해 해시 함수를 이용한다. 패턴 내의 문자들을 일일이 비교하는 대신에 패턴의 해시 값과 본문 안에 있는 하위 문자열의 해시 값만 비교하는 것이다. 해시 함수를 다음과 같이 정의하겠다. S는 문자열이고, S[n]은 문자열의 n번째 문자, m은 문자열의 길이이다.

카프와 라빈은 해시 함수의 비용을 줄이는 방법을 찾아냈다. 패턴의 길이m이 4일 때, S[0...3]의 해시 값 H₀는 다음과 같다

S[1...4]의 해시 값 H₁은 다음과 같다

그리고 H₁은 다음과 같이 H₀을 이용하여 나타낼 수 있다

원래의 해시 함수로는 비교할 때마다 매번 패턴의 길이 m만큼 문자에 접근해야 하지만, 새 해시 함수를 이용하면 항상 2개의 문자에만 접근하면 된다. S[i...i+m-1]의 새로운 해시 함수는 다음과 같이 정의할 수 있다.

이 해시 함수라면 총 탐색 시간이 패턴의 길이와 상관없이 본문의 길이에만 영향을 받게 되어 탐색 성능이 향상된다. 하지만 새 해시 함수는 i가 0일 때, 즉 이전 해시 값이 미리 구해지지 않은 경우에느느 사용할 수 없으므로 최초의 해시 값을 구할 때는 기존의 해시 함수를 사용해야 한다.

최초의 해시 함수나 새 해시 함수 모두 문자열의 길이가 늘어나면 해시 값도 따라 커진다는 문제가 있다. 따라서 해시 값을 일정 범위 안에 가둘 필요가 있는데, 이를 위해 해시 함수의 결과를 어느 값으로 나눈 나머지를 해시 값으로 사용한다. 여기에서 '어느 값'을 q라고 한다. q가 들어간 해시 함수는 다음과 같다

이 해시 함수를 이용해서 문자열 검사를 해보겠다. q의 값은 214748364(int의 최대값), 본문과 패턴은 다음과 같다

본문 : ABACCEFABADD

패턴 : CCEFA

패턴 길이 m은 5이다. 먼저 패턴의 해시 값과 본문[0...4]의 해시 값을 구해본다. 패턴이나 보문 [0...4] 모두 '이전 해시 값'이 없으니 다음의 해시 함수를 이용해서 해시 값을 계산해야 한다.

패턴은 2089, 본문은 2029가 나온다. 서로 일치하지 않는다. 검색을 계속 하기 위해 본문의 검색 위치를 오른쪽으로 한 칸 이동시킨다.

앞 단계에서와는 다르게 지금 본문[0...4]의 해시 값을 갖고 있다. 따라서 이 단계부터는 다음의 해시 함수를 사용하 ㄹ수 있다.

본문 [1...5]의 해시 값을 본문[0...4]의 해시 값과 새 해시 함수를 이용하여 계산하면, 결과는 2047로 패턴의 해시 값 2089와 일치하지 않는다. 따라서 검색 위치를 본문에서 오른쪽으로 한 칸 더 이동한다.

이번에도 마찬가지로 앞 단계(본문[1..5])의 해시 값을 이용해서 본문[2...6]의 해시 값을 계산한다. 찾는 값이 아니므로 본문에서 오른쪽으로 한 칸 이동한다.

본문[3...7]의 해시 값은 패턴의 해시 값과 같은 2089이다.

찾아낸 문자열이 실제로 패턴과 일치하는지는 아직 증명되지 않았다. 카프-라빈 알고리즘이 해시 함수에 기반하고 있기 때문에 서로 다른 문자열에서 얻어낸 해시 값이 동일한 경우도 생길 수 있다.

그래서 카프-라빈 알고리즘에서는 패턴의 해시 값과 일치하는 해시 값을 가지는 문자열을 본문에서 찾아낸 다음, 실제로 각 문자가 패턴의 것과 일치하는 지를 일일이 확인한다.

카프-라빈 알고리즘의 구현

패턴과 본문[0...m-1]의 해시 값을 구하는 hash()함수, 본문[i...i+m-1]의 해시 값을 구하는 rehash()함수, 카프-라빈 알고리즘 자체를 구현하는 karpRabin()함수를 만들 것이다.
- KarpRabin.h

#ifndef _KARPRABIN_H_

#define _KARPRABIN_H_

int karpRabin(char* text, int textSize, int start, char* pattern, int patternSize);

int hash(char* str, int size);

int rehash(char* str, int start, int size, int hashPrev, int coefficient);

#endif

KarpRabin.c

#include <stdio.h>

#include <math.h>

#include "KarpRabin.h"

int karpRabin(char* text, int textSize, int start, char* pattern, int patternSize)

{

int i = 0;

int j = 0;

// 2의(m-1)제곱

int coefficient = pow((double)2, patternSize-1);

// 본문[0...m-1] 해시 값 구하기

int hashText = hash(text, patternSize);

// 패턴의 해시 값 구하기

int hashPattern = hash(pattern, patternSize);

for( i = start ; i <= textSize - patternSize ; i++ )

{

hashText = rehash(text, i, patternSize-1, hashText, coefficient);

if( hashPattern == hashText )

{

for( j = 0 ; j < patternSize ; j++ )

{

if( text[i+j] != pattern[j] )

break;

}

if( j >= patternSize )

return i;

}

return -1;

}

int hash(char* str, int size)

{

int i = 0;

int hashValue = 0;

for( i = 0 ; i < size ; i++ )

{

hashValue = str[i] + (hashValue*2);

}

return hashValue;

}

int rehash(char* str, int start, int size, int hashPrev, int coefficient)

{

if( start == 0 )

return hashPrev;

return str[start + size-1] +

((hashPrev - coefficient*str[start-1]) *2);

}

main.c

#include <stdio.h>

#include <string.h>

#include <math.h>

#include "KarpRabin.h"

#define MAX_BUFFER 512

int main(int argc, char** argv)

{

/*char text[MAX_BUFFER] = "My Name is pattern";

char* pattern = "pattern";

int patternSize = 4;

int h0, h1, rh1;

int result = karpRabin(text, strlen(text), 0, pattern, strlen(pattern));

printf("%d\n", result);

h0 = hash(pattern, patternSize);

h1 = hash(pattern+1, patternSize);

rh1 = rehash(pattern, 1, patternSize, h0, pow((double)2, patternSize-1));

printf("h0:%d\n", h0);

printf("h1:%d\n", h1);

printf("rh1:%d\n", rh1);*/

char* filePath;

FILE* fp;

char text[MAX_BUFFER];

char* pattern;

int patternSize = 0;

int line = 0;

if( argc < 3 )

{

printf("usage:%s<filePath> <pattern>\n", argv[0]);

return 1;

}

filePath = argv[1];

pattern = argv[2];

patternSize = strlen(pattern);

if( (fp = fopen(filePath, "r")) == NULL )

{

printf("cannot open file:%s\n", filePath);

return 1;

}

while( fgets(text, MAX_BUFFER, fp) != NULL )

{

int position = karpRabin(text, strlen(text), 0, pattern, patternSize);

line++;

if( position >= 0 )

{

printf("line:%d, column:%d : %s", line, position+1, text);

}

fclose(fp);

return 0;

}

KMP 알고리즘

KMP(Knuth-Morris-Pratt)알고리즘은 '고지식한 알고리즘'처럼 검색 위치를 본문의 왼쪽부터 시작해서 오른쪽으로 옮겨가며 문자를 직접 비교하는 방식으로 동작한다. 하지만 고지식한 알고리즘과는 달리, KMP알고리즘은 비교할 필요가 없는 부분은 지나치고, 비교가 필요한 부분만 비교를 수행하는 알고리즘이다.

패턴과 본문 내의 문자열을 한 차례 비교하고 나면, 다음 단계의 검색에서 사용할 수 있는 '어떤 정보'가 남으며 이 정보를 이용하면 불필요한 비교를 피할 수 있음을 알아냈다. KMP알고리즘은 이 '어떤 정보'가 무엇인지와 이 정보를 '어떻게 활용하는가'에 대한 것이다.

접두부, 접미부, 그리고 경계

어느 문자열이든 접두부(Prefix)와 접미부(Suffix)를 갖고 있다. 접두부는 문자열의 머리 부분을 뜻하고, 접미부는 문자열의 꼬리 부분을 뜻한다.

KMP알고리즘에서는 빈 문자열이나 BBA처럼 문자열에서 일치하는 접두부와 접미부 쌍을 가리켜 경계(Border)라고 한다.

KMP알고리즘은 이 경계를 활용해서 불필요한 문자 비교를 피해나간다. 예를 들어 아래와 같은 본문과 패턴으로 검색을 한다고 해보자.

본문 : BAABAABAB

패턴 : BAABAB

검색을 시작해보면 본문과 패턴의 0~4번 문자열까지는 일치하고 5번 문자에서 불일치가 일어난다.

불일치가 일어나기 전까지 본문과 일치했던 패턴의 0~4번 문자열을 보자. BAABA는 빈 문자열과 BA, 두 개의 경계를 갖고 있다. 경계는 '서로 일치하는 접두부와 접미부'이다.

본문[0...4]와 패턴[0...4]는 서로 일차한다. 이것은 곧 두 문자열의 경계가 서로 같다는 뜻인데, 이는 본문[0...4]의 접미부는 패턴[0...4]의 접두부와 동일하다는 이야기가 된다. 따라서 패턴 전체를 오른쪽으로 쭉 밀어서 패턴의 접두부와 본문[0...4]의 접미부를 일치하게 만들어 놓으면 곧바로 5번부터 비교를 재개하 수 있게 된다. 이때 패턴의 검색 위치 이동 거리는 일치하는 부분 문자열(BAABA)의 길이(5)에서 경계(BA)의 길이(2)를 뺀 것과 같다.

KMP알고리즘은 본문의 길이가 n일 때 최대 n번만큼만 비교를 수행하면 본문 내에서 패턴과 일치하는 문자열의 위치를 알아낼 수 있다.

경계 정보를 미리 계산하기

KMP알고리즘은 검색을 수행하기 전에 미리 패턴으로부터 경계의 정보를 갖는 테이블을 만든다. 예를 들어 BAABABAA라는 패턴이 있다고 하고 이 패턴으로 검색을 시도 했을 때 첫 번째 문자부터 불일치가 일어난다고 생각해보자. KMP알고리즘에서는 불일치가 일어난 위치 이전의 일치 접두부에서 최대 경계를 찾고, 이 경계의 너비를 이용해서 검색 위치를 뛰어 넘는다. 그런데 첫 번째 문자는 일치 접두부가 아예 존재하지 않는다. 그래서 첫 번째 문자의 경계의 너비는 항상-1이다.

이번엔 두번째 문자에서 불일치가 일어난다고 해보자. 2번째 문자의 일치 접두부라고 해봐야 B하나이다. 따라서 경계가 존재하지 않는다. 이전 접두부의 최대 경계 너비는 0이다. 3번째 역시 경계가 존재하지 않으므로 0이다. 4번째 문자도 마찬가지이다 5번째 문자에서 불일치가 일어나는 경우, 일치 접두부는 BAAB이므로 최대 경계가 B로써 너비는 1이다. 6번째 문자의 일치 접두부 BAABA는 최대 경계가 BA로 너비가 2이다. 이런식으로 테이브을 완성해 나가면 다음과 같은 결과를 얻을 수 있다.

테이블의 마지막칸은 본문 내의 문자열이 패턴과 일치하지만 이어서 탐색을 하고자 할 때 사용한다. 일치 접두부는 BAABABAA이고 최대 경계는 BAA로 길이는 3이다. 이 값을 기입하면 테이블이 완성된다

불일치가 발생했을 때 검색 위치의 이동거리는 다음과 같다

이동 거리 = 일치 접두부 길이 + 최대 경계 너비

KMP 알고리즘의 구현
- 예제 KruthMorrisPratt.h

#ifndef _KNUTHMORISSPRATT_H__

#define _KNUTHMORISSPRATT_H__

#include <stdio.h>

int knuthMorrisPratt(char* text, int textSize, int start, char* pattern, int patternSize);

void preprocess(char* pattern, int patternSize, int* border);

#endif

예제 KruthMorrisPratt.c

#include <stdlib.h>

#include "KnuthMorrisPratt.h"

int knuthMorrisPratt(char* text, int textSize, int start, char* pattern, int patternSize)

{

int i = start;

int j = 0;

int position = -1;

int* border = (int*)calloc(patternSize+1, sizeof(int));

preprocess(pattern, patternSize, border);

while( i < textSize )

{

while( j >= 0 && text[i] != pattern[j] )

j = border[j];

i++;

j++;

if( j == patternSize )

{

position = i - j;

break;

}

free(border);

return position;

}

void preprocess(char* pattern, int patternSize, int* border)

{

int i = 0;

int j = -1;

border[0] = -1;

while( i < patternSize )

{

while( j > -1 && pattern[i] != pattern[j] )

j = border[j];

i++;

j++;

border[i] = j;

}

예제 main.c

#include "KnuthMorrisPratt.h"

#include <string.h>

#define MAX_BUFFER 512

int main(int argc, char** argv)

{

char* filePath;

FILE* fp;

char text[MAX_BUFFER];

char* pattern;

int patternSize = 0;

int line = 0;

if( argc < 3 )

{

printf("usage:%s<filePath> <pattern>\n", argv[0]);

return 1;

}

filePath = argv[1];

pattern = argv[2];

patternSize = strlen(pattern);

if( (fp = fopen(filePath, "r")) == NULL )

{

printf("cannot open file:%s\n", filePath);

return 1;

}

while( fgets(text, MAX_BUFFER, fp) != NULL )

{

int position = knuthMorrisPratt(text, strlen(text), 0, pattern, patternSize);

line++;

if( position >= 0 )

{

printf("line:%d, column:%d : %s", line, position+1, text);

}

fclose(fp);

return 0;

}

보이어-무어 알고리즘

보이어-무어(Boyer-Moore)알고리즘은 '이동'만큼은 왼쪽에서 오른쪽으로 하지만 문자열을 오른쪽에서 왼쪽으로 비교해 나간다.

보이어-무어 알고리즘은 패턴에 오른쪽 끝에 있는 문자가 불일치하고 이 문자가 패턴 내에 존재하지 않는 경우, 이동 거리는 무려 패턴의 길이만큼이 된다.

보이어-무어 알고리즘에는 크게 두 가지 종류의 이동이 있다. 나쁜 문자 이동(Bad Character Shift)과 착한 접미부 이동(Good Suffix Shift)이 있다.

나쁜 문자 이동

나쁜 문자 이동(Bad Character Shift)는 본문과 패턴 사이를 이간질시키는(불일치시키는) '본문의 문자'이다.

나쁜 문자 이동은 다음 두 단계를 거친다.
- 패턴에서 나쁜 문자를 찾는다.
- 찾아낸 패턴의 나쁜 문자의 위치가 본문의 나쁜 문자 위치와 일치하게 패턴을 이동시킨다.
나쁜 문자와 같은 문자가 패턴 내에서 두 개 이상 나오는 경우, 발견된 문자 중 가장 오른쪽에 있는 것을 본문의 나쁜 문자에 맞추면 된다. 본문의 3번 문자는 B, 패턴의 3번 문자는 C이기 때문에 서로 일치 하지 않는다. 여기서 나쁜 문자는 B이므로 이것을 패턴에서 찾는다. B가 패턴에서 0, 1번에서 각각 발견되었다. 발견된 문자 중 1이 가장 오른쪽에 있으므로 패턴의 1번에 있는 B를 본문의 나쁜 문자의 위치에 일치하도록 패턴을 이동 시킨다.

한편 나쁜 문자 이동은 실패하는 경우도 있다. 아래 그림의 경우를 보면 나쁜 문자는 A인데, 패턴에서 나쁜 문자를 찾으면 0, 2에서 나타난다. 그런데 2가 가장 오른쪽에 있으므로 이것을 본문의 나쁜 문자에 맞추기 위해 패턴을 이동하면 패턴은 오른쪽이 아니라 왼쪽으로 나간다. 마이너스 방향으로 이동하는 셈이다.

이런 경우 사용할 수 있는 방법이 '착한 접미부 이동'이다

착한 접미부 이동

보이어-무어 알고리즘은 패턴을 오른쪽에서부터 비교하기 때문에 패턴에는 본문과 일치하는 접미부가 나타나게 된다. 이렇게 일치하는 접미부를 가리켜 착한 접미부(Good Suffix)라고 부른다.

착한 접미부 이동(Good Suffix Shift)을 상황은 두 가지로 나뉜다.
- 첫 번째 경우
  
  쳣 번째 경우는 불일치가 일어났을 때 착한 접미부와 동일한 문자열이 패턴의 착한 접미부 왼쪽에 존재하는 경우이다. 아래 그림을 보면 2번 문자에서 본문의 A와 패턴의 B가 불일치 한다. 그래서 착한 접미부 AB를 패턴에서 찾고 이 위치를 본문의 착한 접미부의 위치에 일치하도록 이동시켰다.
  
  그런데 일치 하는 부분이 없으면 두 번째 경우와 같은지 확인한다. 그리고 두번째 경우에도 해당하지 않는다면 패턴의 길이만큼 검색 위치를 오른쪽으로 이동시키면 된다.
- 두 번째 경우
  
  다음의 경우는 착한 접미부가 패턴 안에 존재하지 않지만, 착한 접미부의 접미부가 패턴의 접두부와 일치하는 때이다. 이 경우에는 착한 접미부 전체가 아닌, '착한 접미부의 접미부'와 일치하는 패턴의 접두부를 이동시키면 된다.
  
  다음 그림을 보면 착한 접미부가 AABB인데, 패턴에서는 이 같은 문자열이 없다.
  
  그런데 착한 접미부의 AB는 패턴의 접두부와 일치한다. 패턴의 접두부가 착한 접미부의 접미부에 일치하도록 다음과 같이 이동시킨다.
보이어-무어 알고리즘의 전처리 과정
- 나쁜 문자 이동 테이블 만들기
  
  먼저 테이블을 하나 준비하고, 패턴을 왼쪽에서 오른쪽으로 읽어나가면서 패턴에 있는 각 문자의 위치를 이 테이블에 기록해두면 된다. 중복되는 문자들이 있어도 가장 오른쪽에 있는 문자의 위치만 테이블에 남게 된다.
  
  아래 그림에서 패턴 ABAAB에서 A는 0, 2, 3번에 위치하지만 테이블에는 가장 오른쪽에 있는 3을 입력하고 B 역시 1, 4에 위치하지만 가장 오른쪽인 4를 테이블에 입력했다. 패턴 내에 존재하지 않는 문자들은 모두 -1로 입력한다.
  
  테이블에 입력된 위치는 곧 불일치가 일어났을 때의 이동거리가 된다.
- 착한 접미부 이동 테이블 만들기
  
  착한 접미부 이동에는 두 가지 경우가 있기 때문에 테이블 역시 두 가지 경우를 고려해서 만들어야 한다. 하지만 테이블은 하나만 있으면 된다.
  
  우리가 원하는 것은 착한 접미부의 존재 여부를 검색하기 전에 확인하고 존재한다면 이동 거리를 테이블 안에 넣어둠으로써, 불일치가 일어났을 때 착한 접미부를 확인하자마자 바로 이동 거리를 얻을 수 있도록 하는 것이다. 한마디로 이 테이블은 '착한 접미부의 이동거리'를 보관하는 것이다.
  
  착한 접미부 이동의 첫 번째 경우는 불일치가 일어났을 때 착한 접미부가 패턴 안에 존재할 때이다.
  
  첫 번째 경우에 대해 착한 접미부 이동 테이블을 만드는 과정은 이렇다. 우선 패턴의 길이+1 크기의 테이블을 준비한다. 그 다음에는 패턴을 오른쪽에서부터 왼쪽으로 읽으면서 나타나는 접미부 X에 대해, 이 접미부를 경계로 가지는 패턴 내의 가장 큰 접미부 Y를 찾는다. 가장 큰 접미부를 찾았으면 "X의 시작 위치 - Y의 시작 위치"를 이동 거리로 입력한다.
  
  그런데 만약 접미부 X가 다른 접미부의 경계가 되지 않거나, 경계라 하더라도 이 경계가 왼쪽 방향으로 더 큰 경계로 확장될 수 있다면 이동 거리를 0으로 비워둬야 한다. 이렇게 비워둔 이동 거리는 두 번째 경우를 처리할 때 채우게 된다.
  
  예를 들어 AABABA라는 패턴이 있다고 하고, 이 패턴으로부터 착한 접미부 이동 테이블을 만들어 보겠다. 먼저, 빈 접미부는 경계가 없으므로 이동 거리는 패턴의 길이(6)+1 = 7이 된다. 그리고 착한 접미부가 문자열이라는 것은, 일치하는 부분이 전혀 없다는 뜻이므로 이동 거리는 1이 된다.
  
  문자열의 5번에 있는 A를 보면 A를 경계로 가지는 다른 접미부는 ABA, ABABA, AABABA 세가지 이다. AABABA는 패턴의 시작부터 포함하고 있어서 선택 대상에서 제외된다. 패턴의 시작 부분을 다루는 것은 두 번째 경우에 해당되기 때문이다. 남은 것은 ABA와 ABABA인데, ABABA가 더 크므로 이것을 선택한다. ABABA의 시작 위치는 1, A의 시작 위치는 5이므로 이동 거리는 5-1=4이다. 이동 거리 테이블의 5번에 이 값을 입력한다.
  
  이제 한 더 왼쪽으로 이동해서 4에서 시작하는 접미부 BA를 볼 차례이다. BA를 경계로 갖는 다른 접미부는 BABA인데, 불행히도 BABA는 왼쪽 방향으로 확장이 가능하다. BABA에서 왼쪽으로 한칸 더 이동하면 ABABA가 나온다. ABABA는 BA를 왼쪽으로 한칸 확장한 ABA가 경계이디 때문이다. 따라서 BA의 이동 거리는 0으로 해둔다.
  
  한 칸 더 이동해보겠다. 이번에는 ABA인데, 우리가 조금 전에 이야기한 것처럼 ABA를 경계로 갖는 최대의 접미부는 ABABA이다. ABABA와 ABA는 왼쪽으로 확장할 수도 없기 때문에 이동에 활용할 수 있다. 현재 위치 3에서 ABABA의 시작 위치를 뺀 2를 테이블에 입력한다.
  
  나머지 접미부들(BABA, ABABA, AABABA)은 길이가 원래 문자열 길이의 1/2보다 크기 때문에 경계가 될 수 없다. 이들의 이동 거리는 모두 0으로 채운다.
  
  이제 두번째 경우이다. 두번째 경우는 착한 접미부의 접미부와 패턴의 접두부 사이의 거리가 이동 거리다 된다. 즉, 패턴의 양쪽 경계의 거리가 곧 이동 거리가 되는 것이다. 첫 번째 경우에 대한 이동 거리는 이미 처리를 했으므로 이제 우리는 테이블 내에서 이동 거리가 0인 항목에 대해서만 처리를 하면 된다.
  
  패턴의 왼쪽부터 읽으면서 경계를 이룰 수 있는 가장 너비가 큰 접두부를 찾는다. 접두부 A는 접미부 A와 경계를 이루므로 이동거리는 5가 된다.
  
  그런데 접두부 AA는 경계를 이룰 수 있는 접미부가 패턴에 존재하지 않는다. 대신에 접두부 AA의 접두부 중에 접미부와 경계를 이룰 수 있는 '접두부의 접두부' A를 선택하고, A끼리의 거리 5를 이동 거리로 입력한다. 이동 거리가 0으로 남아 있는 AAB, AABAB 모두 A 외에는 경계를 이룰 수 있는 접두부를 갖고 있지 않다. 따라서 테이블[2], 테이블[4]의 이동거리는 모두 5가 된다.
- 예제 BoyerMore.h

#ifndef _BOYERMOORE_H__

#define _BOYERMOORE_H__

int boyerMoore(char* text, int textSize, int start, char* pattern, int patternSize);

void buildGST(char* pattern, int patternSize, int* suffix, int* GST);

void buildBCT(char* pattern, int patternSize, int* BCT);

int max(int a, int b);

#endif

예제 BoyerMore.h

#include <stdio.h>

#include <stdlib.h>

#include "BoyerMoore.h"

int boyerMoore(char* text, int textSize, int start, char* pattern, int patternSize)

{

int BCT[128];

int* suffix = (int*)calloc(patternSize+1, sizeof(int));

int* GST = (int*)calloc(patternSize+1, sizeof(int));

int i = start;

int j = 0;

int position = -1;

buildBCT(pattern, patternSize, BCT);

buildGST(pattern, patternSize, suffix, GST);

while( i <= textSize - patternSize )

{

j = patternSize - 1;

while( j >= 0 && pattern[j] == text[i+j] )

j--;

if( j < 0 )

{

position = i;

break;

}

else

{

i += max(GST[j+1], j-BCT[text[i+j]]);

}

free(suffix);

free(GST);

return position;

}

void buildGST(char* pattern, int patternSize, int* suffix, int* GST)

{

// case1

int i = patternSize;

int j = patternSize + 1;

suffix[i] = j;

while( i > 0 )

{

while( j <= patternSize && pattern[i-1] != pattern[j-1] )

{

if( GST[j] == 0 )

GST[j] = j-i;

j = suffix[j];

}

j--;

i--;

suffix[i] = j;

}

// case2

j = suffix[0];

for( i = 0 ; i <= patternSize ; i++ )

{

if( GST[i] == 0 )

GST[i] = j;

if( i == j )

j = suffix[j];

}

void buildBCT(char* pattern, int patternSize, int* BCT)

{

int i;

int j;

for( i = 0 ; i < 128 ; i++ )

BCT[i] = -1;

for( j = 0 ; j < patternSize ; j++ )

BCT[pattern[j]] = j;

}

int max(int a, int b)

{

if( a > b )

return a;

else

return b;

}

예제 BoyerMore.h

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include "BoyerMoore.h"

#define MAX_BUFFER 512

int main(int argc, char** argv)

{

char* filePath;

FILE* fp;

char text[MAX_BUFFER];

char* pattern;

int patternSize = 0;

int line = 0;

if ( argc < 3 )

{

printf("Usage: %s <filePath> <pattern>\n", argv[0]);

return 1;

}

filePath = argv[1];

pattern = argv[2];

patternSize = strlen(pattern);

if( (fp = fopen(filePath, "r")) == NULL )

{

printf("Cannot open file:%s\n", filePath);

return 1;

}

while( fgets(text, MAX_BUFFER, fp) != NULL )

{

int position = boyerMoore(text, strlen(text), 0, pattern, patternSize);

line++;

if( position >= 0 )

{

printf("line:%d, column:%d : %s", line, position+1, text);

}

fclose(fp);

return 0;

}

'책정리 > 뇌를 자극하는 알고리즘' 카테고리의 다른 글

9장 그래프 (0)	2015.03.29
8장 해시 테이블 (2)	2015.03.28
7장 우선순위 큐와 힙 (0)	2015.03.25
6장 탐색 (0)	2015.03.25
5장 정렬 (0)	2015.03.23

현재글10장 문자열 검색

GONI