A Fast StringSearching Algorithm 리뷰

해당 논문은 boyer–moore 알고리즘 이라고 불리는 kmp와 비슷한 알고리즘에 대하여 설명하고 있습니다.

 

보이어무어 알고리즘은 불필요한 것은 건너뛰고, 검색을 빠르게 하자는 것에서 KMP와 유사합니다.

 

단, 뒷부분에서 불일치가 일어날 확률이 높다는 성질을 활용하여 오른쪽 끝부터 비교하여 문자열 매칭을 진행합니다.

 

다음과 같이 "EAT A APPLE"의 문장에 "APPLE"이라는 단어가 있는지 체크하는 과정을 거친다고 가정해보겠습니다.

APPLE의 맨 뒤 단어인 E와 같은 위치에 있는 단어는 A로 서로 다르다는 것을 인식하였습니다.

이후, A라는 단어가 찾고자 하는 APPLE 이라는 단어에 포함되어 있는지 확인하고, 포함되어 있다면 해당 위치로 이동을 시킵니다.

위치로 이동결과, APPLE이라는 단어를 찾을 수 있었습니다.

 

"EAT A GRAPE"의 문장에 "GRAPE"라는 단어가 매칭되는지 확인하는 과정에 대하여 설명해보겠습니다.

GRAPE의 마지막 단어 E의 위치에 A라는 단어가 있습니다.

GRAPE에도 A라는 단어가 있어 해당 위치로 이동합니다.

이후에 다시 한번 E의 위치에 R이라는 단어가 있고, GRAPE라는 단어에 R이 있어, 해당 위치로 이동시킵니다.

그러면 다음과 같이 GRAPE라는 단어가 있다는 것을 확인할 수 있습니다.

 

PS에서는 보이어-무어 보다는 kmp를 주로 사용하고 있습니다.

kmp알고리즘의 시간복잡도는 O(n + m)이지만, 보이어-무어의 최악의 시간 복잡도는 O(nm)으로 kmp보다 시간이 더 많이 소요됩니다.

그럼에도 kmp보다 보이어-무어를 사용하는 이유는 평균적인 시간복잡도는 O(n/m)으로 kmp보다 빠른 소요시간을 보여줍니다.

JAVA의 내부 코드 중에도 보이어-무어를 사용하는 class가 존재합니다.

https://github.com/openjdk/jdk/blob/master/src/java.xml/share/classes/com/sun/org/apache/xerces/internal/impl/xpath/regex/BMPattern.java

jdk/src/java.xml/share/classes/com/sun/org/apache/xerces/internal/impl/xpath/regex/BMPattern.java at master · openjdk/jdk