KMP·Rabin-Karp·Boyer-Moore: 문자열 검색 알고리즘 선택 기준

검색 경로가 달라지면 알고리즘 선택도 달라진다

대규모 텍스트 처리, 로그 분석, 보안 탐지에서는 같은 문자열을 찾더라도 입력이 스트리밍인지, 패턴이 얼마나 긴지, 여러 패턴을 동시에 검사하는지가 성능을 좌우한다. KMP, Rabin-Karp, Boyer-Moore는 모두 문자열 검색에 쓰이지만 전처리 방식과 불일치 처리 전략이 서로 다르다.

KMP는 패턴의 접두사와 접미사가 일치하는 길이를 미리 계산해 둔다. LPS 또는 Failure function이라 부르는 이 정보를 이용하면 텍스트 인덱스를 뒤로 되돌리지 않고 좌에서 우로 진행할 수 있다. 시간 복잡도는 O(n+m), 공간 복잡도는 O(m)이며 입력 특성과 무관하게 지연 시간이 일정하다.

Rabin-Karp는 롤링 해시를 사용한다. 윈도우가 이동할 때 해시값을 O(1)로 갱신하고, 해시가 일치한 후보에서만 실제 문자열을 비교한다. 평균 시간은 O(n+m)이지만 해시 충돌이 발생하면 최악 O(nm)까지 갈 수 있다. 다중 패턴, 스트리밍, 슬라이딩 윈도우에 맞추기 쉽다는 점이 특징이다.

Boyer-Moore는 패턴을 우에서 좌로 비교하며, 불일치가 나면 Bad-character와 Good-suffix 휴리스틱으로 비교 위치를 크게 이동한다. 평균적으로 서브선형 성능을 보이며 긴 패턴과 영문처럼 큰 알파벳에서 특히 빠르다. 반면 최악 시간은 O(nm)이고, Horspool이나 Sunday 같은 경량 변종도 널리 사용된다.

전처리 비용과 입력 분포를 함께 본다

KMP는 길이 O(m)의 LPS 배열만 구성하면 된다. 구조와 메모리 사용이 단순하며, 좌에서 우로 진행하는 비교 방식은 분기 예측과 캐시 지역성 측면에서도 유리하다.

Boyer-Moore는 Bad-character에 O(σ), Good-suffix에 O(m) 전처리를 사용한다. Horspool 같은 변종은 전처리와 메모리 부담을 줄이는 대신 전략을 단순화한다. 불일치가 잦고 건너뛸 수 있는 거리가 큰 입력이라면 평균 비교 횟수를 크게 줄일 수 있지만, 텍스트와 패턴의 분포, 알파벳 크기에 성능이 민감하다.

Rabin-Karp의 성능은 해시 설계에 좌우된다. 모듈러와 베이스를 어떻게 선택하는지, 충돌을 어떻게 검증하는지에 따라 실제 비용이 달라진다.

스트리밍과 다중 패턴의 경계

순차 스트리밍에서는 Boyer-Moore의 점프 이점이 줄어든다. 반대로 Rabin-Karp는 슬라이딩 윈도우를 자연스럽게 처리할 수 있어 필터 단계에 넣기 쉽다.

단일 패턴을 선형 시간에 처리해야 한다면 KMP가 적합하다. 여러 패턴을 동시에 찾는 문제에서는 Aho-Corasick을 검토할 수 있으며, Rabin-Karp를 사전 필터로 조합할 수도 있다.

⤢✕

알고리즘별 운영 특성

항목	KMP	Rabin-Karp	Boyer-Moore(변종 포함)
성능	일관된 선형 시간, 안정적 처리량	평균 선형, 충돌 시 급감 가능	평균 서브선형, 긴 패턴·큰 σ에서 최고 성능
확장성	단일 패턴에 최적	다중 패턴·스트리밍 적합	긴 패턴·랜덤 액세스 텍스트에 적합
일관성	최고	해시 품질 의존	입력 분포 의존, 최악 케이스 존재
안정성	전처리·메모리 단순	모듈러/베이스 선택·충돌 검증 필요	전처리 테이블 2종, 구현 복잡도 중간
운영 편의	파인튜닝 불필요	파라미터/충돌 모니터링 필요	변종 선택·테이블 캐싱·SIMD 최적화 여지

검색 대상에 따른 적용 방식

로그와 보안 탐지에서는 스트리밍 로그의 시그니처를 Rabin-Karp 해시로 먼저 거른 뒤 후보 매치를 직접 비교할 수 있다. 수천 개 패턴을 함께 탐지해야 한다면 Aho-Corasick을 본선으로 두고 Rabin-Karp를 사전 필터로 결합하는 방식도 가능하다.

텍스트 편집기나 IDE에서는 긴 검색어와 소스 코드 파일을 대상으로 Boyer-Moore 또는 Horspool을 사용해 체감 속도를 높일 수 있다. 짧은 검색어에 즉각적인 반응이 필요할 때는 KMP가 일정한 지연 시간을 제공한다.

데이터베이스나 검색엔진에서 인덱스가 적용되지 않는 구간을 스캔할 때는 Boyer-Moore 변종으로 I/O 대비 CPU 사용을 최적화할 수 있다. 트랜잭션 로그 검증처럼 재현성이 필요한 작업에는 KMP가 맞는다.

DNA처럼 알파벳 크기가 매우 작은 환경에서는 BM의 이점이 제한된다. DNA 4 환경에서는 KMP 또는 Rabin-Karp(64-bit 롤링 해시, 낮은 충돌률)를 고려할 수 있고, 대량 슬라이딩 윈도우 k-mer 검사에는 Rabin-Karp의 O(1) 롤링 갱신을 활용할 수 있다.

처리량과 지연 시간에 미치는 영향

동일 하드웨어 기준으로 Boyer-Moore 변종은 1.53배, KMP는 1.22배, 충돌 저감 설계를 적용한 Rabin-Karp는 1.2~2배 가속을 기대할 수 있으며 환경에 따라 달라진다.

KMP를 채택하면 P99와 평균 지연 시간의 차이를 최소화할 수 있다. KMP와 BM의 전처리는 O(m)이며, Rabin-Karp는 해시를 O(1)로 갱신한다. 충돌 검증을 조건부로 제한하면 CPU 캐시 친화적으로 동작하고 분기 비용을 줄일 수 있다.

구현에서 놓치기 쉬운 조건

Rabin-Karp는 64-bit 모듈러(예: 2^61-1) 또는 다중 해시로 충돌 확률을 낮출 수 있다. 해시가 일치하면 반드시 직접 비교해야 한다. Boyer-Moore의 Bad-character 테이블은 바이트 기준인지 코드포인트 기준인지 정해야 하며, 긴 패턴에서는 Good-suffix를 포함했을 때 효율이 높아진다.

유니코드 텍스트는 NFC/NFKC 정규화 뒤에 매칭한다. 복합 문자를 다룰 때는 grapheme cluster 단위 토크나이즈를 고려한다. 바이너리 데이터는 바이트 스트림으로 검색하면서 σ=256을 가정할 수 있고, 이 경우 BM 변종의 이점이 커진다.

짧은 패턴은 단순 비교와 SIMD(memmem/AVX2/Neon)를 먼저 검토하고, 일정 길이 이상에서 BM 또는 KMP로 전환한다. 자주 쓰는 패턴과 테이블은 핫 캐싱하며, 대용량 입력은 블록 처리와 NUMA 인식을 적용한다.