문자열 탐색 알고리즘들 살펴보기

주먹구구 알고리즘(brute force 알고리즘)

패턴의 제일 앞부분을 먼저 비교하고 틀리면 다음 문자로 넘어가며 맞으면 패턴의 다음 부분과 문자의 다음 부분을 비교하는 식이다. 복잡도는 o(mn)이지만 마지막 부분에 존재하는 최악의 경우는 거의 발생하지 않으므로 실질적으로 o(n)이다. 이 알고리즘도 충분히 빠르다고 할 수 있다.

kmp 알고리즘

주먹구구 알고리즘의 경우 패턴의 중간에서 불일치가 일어나더라도 한 칸만을 이동하여 다시 처음부터 비교를 한다. 반면 kmp알고리즘은 예를 들어 패턴의 3번째에서 불일치가 발생하였다면 2칸을 이동하고 다시 패턴을 비교하게 된다. kmp법은 최악의 경우라도 복잡도가 o(n)이 된다. 하지만 실제적으로는 kmp법이 주먹구구 보다 속도 측면에서의 이점은 거의 없다. 다만 최악의 경우에도 o(n)이라는 것이 중요하다. 하지만 텍스트를 가리키는 포인터가 뒤로 돌아가지 않는다라는 특징 때문에 이점이 있다. 주먹구구 식의 경우 텍스트를 버퍼링해야 하지만 kmp는 현재 처리 중인 한 문자만 기억하면 된다.

boyer-moore 알고리즘

kmp법은 이론적으로는 뛰어나지만 실용적 가치는 없다. bm법은 둘 다 만족시키는 알고리즘이며 가장 빠른 알고리즘이다. 만약 패턴이 abc고 텍스트가 abdefgh 라면 패턴의 끝부터 비교를 시작하면 d에서 불일치가 발생한다. 그러면 한 칸을 이동해도 b에서 불일치가 발생함을 알 수 있다. 두 칸을 이동해도 a와 불일치가 발생한다 따라서 3칸을 이동시키는 것이다. 즉 비교를 패턴의 끝부터 시작하며 불일치가 발생한 지점의 문자를 패턴의 문자와 다시 비교해 이동할 칸을 결정한다.