String Matching 알고리즘을 요즘 좀 보고 있어서 정리했본다.

먼저 Naive String Matching 알고리즘이다.

일반적인 String Matching 알고리즘 이다. 누구든지 C로 구현을 한다고 하면, 처음엔 이런식으로 구현을 할것이다.
하지만 이 알고리즘은 상당한 단점을 가지고 있다. 무식하게 처음부터 1씩 증가하면서 모든 경우를 타진하는 알고리즘이기때문이다. 이를 보완한 알고리즘이 Boyer-Moore String Matching 알고리즘이다.

위의 알고리즘에서 x 는 Keyword가 되겠고, text는 우리가 Search할 문장이라고 한다. 그리고 F(x), G(x) 함수를 설명해보자.

먼저 F(x)함수는 last-occurance함수로서 말 그대로 알파벳에서 가장 나중에 나온 알파벳의 인덱스를 리턴한다. “gogamza” 라는 텍스트로 이 함수를 적용하자면, g:3, o:2, a:7 등이 되겠고 나오지 않은 “b, c”같은 것들은 0값이 된다.

또한 G(x)함수는 good-suffix 함수로서 특정 접미사의 인덱스가 입력이되면, 그 접미사가 다시 나타나는 인덱스를 리턴하게된다.

이 알고리즘의 백미는 12번째 줄에 있다. bad-charactor heuristic 방법과 good-suffix heuristic 방법을 이용해 두 shift 증가분 중의 큰 값으로 shift 값을 증가시켜 나가는것이다. 이렇게 함으로써 String Matching 속도자체가 Naive 방법보다 훨씬 빨라지는것이다.

아마도 여러 라이브러리에서 제공하는 find 계열의 함수들이 이 방법을 쓰지 않을까 감히 짐작해보면서 이에 관한 문서를 소개하고 글을 마치겠다.

Boyer-Moore String Matching
위 링크에서 그림으로 설명이 되어 있으니 쉽게 접근할수 있으리라 믿는다. 다행히 C 코드와 Example 프로그램도 제공이 된다.

String Matching 알고리즘 by from __future__ import dream is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.