Bitap: 내가 가장 좋아하는 문자열 매칭 알고리즘
Bitap: My favorite string matching algorithm
Bitap(또는 shift-and) 알고리즘은 패턴이 기계어 크기보다 짧을 때 효율적으로 동작하는 문자열 매칭 기법이다. 저자는 naive 알고리즘에서 출발해 스트리밍 방식으로, 다시 비트셋과 비트 연산을 활용하는 방식으로 점진적으로 유도하며, 단 한 번의 시프트와 AND 연산으로 모든 활성 상태를 갱신하는 우아함을 보여준다. Boyer-Moore나 KMP보다 직관적으로 이해되고 구현하기 쉬우며, 짧은 패턴에 한해 실용적이다.
비록 Boyer-Moore와 KMP도 자세히 공부했지만, 그것들을 처음부터 유도하는 데는 꽤 시간이 걸린다. 반면 bitap은 매우 쉽게 유도되는데, 내게는 그저 naive 알고리즘을 다르게 포장한 것에 불과하기 때문이다.