Sun Wu라는 분과 Uni manber라는 분이 논문의 공동 저자라서
아마도 알고리즘 이름을 Wu-manber라고 한것 같다.
기본적인 방법론은 boyer-moore 알고리즘에 기반한다.
일반적인 문자열 방법과 다르게 패턴의 뒤에서 부터 매칭하는 부분과
문자열 비교가 실패했을때 비교한 문자열 길이만큼 jump하는 것이 특징이다.
bm 알고리즘을 char 기반인데 반해 wm알고리즘은 block 단위이다.
음절단위로 생각하면 2음절이나 3음절 정도를 권장한다고 한다.
멀티패턴이기 때문에 bm에서와는 다르게 가정이 존재하는데
패턴중 가장 짧은 패턴을 기준으로 다른 패턴들도 앞에서 부터 패턴을 절단하여 가장 짧은 패턴과 동일한 상태에서 초기화를 실행한다.
패턴의 길이는 BM에서 jump 거리를 좌우하기 때문에
wm에서도 동일하게 짧은 패턴이 하나라도 있다면 속도가 느려질수 있다.
고정길이 다중 패턴 매칭에 적합한 알고리즘이다.
간단히 SHIFT값 설정하는 법을 살펴보면 다음과 같다
SHIFT값은 보수적으로 설정한다. 가능한한 안전하게 즉 점프간격이 짧은 것과 긴것이 있을 경우 짧은 것을 선택한다. 놓치는 패턴이 없게 하기 위해
SHIFT값은 min(current value, m-j) 구한다. 보수적이기 때문에 min 값으로
SHIFT의 초기값 : m-B+1
X = 음절 바이그램으로 짤랐을때 값을 X라고 한다.
예를 들면
test = te, es, st 를 X
이X가 다른 패턴에는 나타나지 않을 경우 m-B+1으로 SHIFT를 계산하고
X가 다른 패턴에도 나타났을 경우 m-j
j는 만약 A라는 패턴에서는 2번째에 있고 B라는 패턴에는 3의 위치에 있으면
안정적으로 점프를 하기 위해서 큰 값(3)을 선택하게 된다.
결가적으로 m - j형태이기 때문에 점프거리가 줄어들게 된다.
SHIFT값으로 이동하고 HASH를 통해 얻은 것으로 패턴을 확인한다.
Fast exact string matching.pdf
A_Fast_Algorithm_for_Multi-Pattern_Searching.ppt
http://webglimpse.net/pubs/TR94-17.pdf
'알고리즘' 카테고리의 다른 글
| LCS( longest common subsequence ) 엑셀에서 (0) | 2014.12.01 |
|---|---|
| max(min) sort 보다 빠른quick select (0) | 2014.07.21 |
| udi manber (0) | 2013.09.26 |
| smoothing of NGRAM (0) | 2013.08.29 |
| norvig spell checker (0) | 2013.08.28 |