KMP 알고리즘 (Knuth-Morris-Pratt Algorithm)
쉽게 풀면
긴 문서에서 특정 단어를 찾는다고 해봅시다. 가장 단순한 방법은 문서의 첫 글자부터 한 칸씩 밀어가며 단어와 일일이 대조하는 것인데, 이러면 비교했던 내용을 매번 처음부터 다시 확인하게 되어 느립니다.
KMP 알고리즘은 "패턴 자기 자신"을 미리 분석해서 "일치하다가 틀렸을 때, 몇 칸을 건너뛰어도 안전한지"를 나타내는 표(실패 함수, failure function)를 만들어 둡니다.
이 표 덕분에 불일치가 나와도 이미 확인한 부분을 다시 훑지 않고 필요한 만큼만 건너뛸 수 있어서, 문서 길이와 패턴 길이의 합에 비례하는 시간(선형 시간)만으로 검색을 끝낼 수 있습니다.
왜 중요한가
문자열에서 패턴을 찾는 작업은 텍스트 검색, 네트워크 침입 탐지, 생물정보학의 서열 분석 등 다양한 분야에서 반복적으로 등장하는 기본 연산이며, 데이터 규모가 커질수록 선형 시간 보장이 중요해집니다. KMP는 이런 패턴 매칭 문제의 시간복잡도를 이론적으로 최적에 가깝게 낮춘 대표 알고리즘이라, 문자열 처리 성능을 논하는 논문에서 비교 기준이나 하위 모듈로 자주 인용됩니다.
어떤 절차인가
KMP(Knuth-Morris-Pratt)는 길이 n의 텍스트 T에서 길이 m의 패턴 P가 나타나는 위치를 찾습니다(Knuth 외, 1977). 두 단계입니다.
- 전처리: 패턴의 각 위치 i에 대해 π[i] = “P[0..i]의 접두사이면서 접미사이기도 한 가장 긴 진부분 문자열의 길이”를 구합니다(실패 함수).
- 탐색: 텍스트를 한 번만 왼쪽에서 오른쪽으로 읽으며, 일치하면 패턴 위치 k를 하나 늘리고, 불일치하면 텍스트 위치는 그대로 둔 채 k를 π[k−1]로 줄여 비교를 이어 갑니다.
예를 들어 패턴 ABABCABAB의 실패 함수는 (코드로 계산) 다음과 같습니다.
| 위치 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| 패턴 문자 | A | B | A | B | C | A | B | A | B |
| π | 0 | 0 | 1 | 2 | 0 | 1 | 2 | 3 | 4 |
위치 8의 값 4는 “ABAB”가 패턴의 앞과 끝에서 겹친다는 뜻입니다. 예를 들어 패턴 앞 8글자 ABABCABA가 일치한 뒤 다음 글자가 B가 아니면, 비교 위치는 8에서 π[7] = 3으로 줄어 “ABA”가 이미 맞은 상태로 이어 비교합니다. 이 방식으로 텍스트 위치는 뒤로 되돌아가지 않으며, 최악의 경우에도 시간은 O(n + m), 추가 공간은 O(m)입니다.
언제 쓰고 무엇을 얻나
단순한 방법(텍스트의 모든 시작 위치에서 패턴을 처음부터 비교)은 최악의 경우 O(nm)입니다. A가 100개 이어진 뒤 B가 붙은 텍스트(길이 101)에서 A 20개와 B로 된 패턴을 찾는 가상의 실험(코드로 계산)에서는 문자 비교 횟수가 단순한 방법 1,701회, KMP 181회였습니다(위치 80에서 발견). 이 차이는 같은 문자를 여러 번 되풀이해 비교하는 최악 상황에서 두드러지고, 일반적인 텍스트에서는 단순한 방법도 빠릅니다.
- 언제 쓰나: 한 패턴을 긴 텍스트에서 찾을 때, 텍스트를 한 번만 읽을 수 있는 스트림에서 찾을 때(되돌아가지 않으므로).
- 대안: 평균적으로 건너뛰며 더 빠른 Boyer-Moore, 해시를 쓰는 Rabin-Karp, 여러 패턴을 동시에 찾는 Aho-Corasick, 같은 텍스트에서 질의가 반복되면 접미사 배열 같은 인덱스 구조가 쓰입니다(Cormen 외, 2009; Gusfield, 1997). 알파벳 크기와 패턴 길이에 따라 실제 속도는 다릅니다.
논문에는 이렇게 적는다
논문에서는 알고리즘의 시간·공간 복잡도(최악과 평균을 구분), 입력의 크기와 패턴 길이, 비교한 알고리즘, 구현 언어와 실험 환경, 측정 지표(문자 비교 횟수 또는 실행 시간), 데이터 종류(자연어, 알파벳이 작은 DNA 서열 등)를 적습니다. 이론상 O(n + m)인 알고리즘이 실제 실행 시간에서 항상 가장 빠른 것은 아니므로 실험 조건을 함께 보고해야 합니다.
예시 문장(예시): “패턴 매칭에는 최악 시간 복잡도가 O(n + m)인 KMP 알고리즘을 사용하였고, 문자 비교 횟수를 기준으로 단순 탐색과 비교하였다.”
논문에서는 이렇게 쓰입니다
실제 논문에서
이 용어를 직접 쓴 국내 논문 문장을 아직 수집하지 못했습니다. 수집되는 대로 출처와 함께 싣겠습니다.
예시 문장
아래는 용어의 쓰임을 보여 주려고 만든 예시로, 실제 논문에서 가져온 문장이 아닙니다.
이 문장은 "많은 양의 텍스트 데이터 안에서 원하는 문자열 패턴을 KMP 방식으로 빠르게 찾아냈다"는 뜻입니다. 침입 탐지, 유전자 서열 분석, 텍스트 검색 엔진 등에서 자주 쓰입니다.
생물정보학 연구에서 유전자 서열 내 특정 패턴(모티프)의 위치를 빠르게 찾을 때 활용되는 예시이다.
보안 분야에서 실시간 트래픽 검사 속도를 높이기 위해 패턴 매칭 알고리즘을 적용한 예시이다.
조금 더 깊게 보면
KMP 알고리즘의 핵심은 패턴 자체의 접두사와 접미사가 겹치는 최대 길이를 미리 계산해 둔 실패 함수(부분 일치 표)입니다. 이 표 덕분에 불일치가 발생해도 패턴 포인터만 적절히 이동시키고 텍스트 포인터는 뒤로 되돌리지 않아도 되므로, 전체 탐색이 텍스트 길이와 패턴 길이의 합에 비례하는 선형 시간에 끝납니다.
여러 패턴을 동시에 찾아야 하는 경우에는 이 아이디어를 확장한 아호-코라식(Aho-Corasick) 알고리즘이 흔히 쓰이며, 대규모 텍스트에서 반복 검색이 많다면 접미사 배열이나 접미사 트리 같은 인덱싱 구조가 대안으로 논의되기도 합니다.
주의할 점
KMP 알고리즘은 패턴 하나를 문자열 하나에서 찾는 데는 효율적이지만, 여러 패턴을 동시에 찾거나 문자열 전체의 반복 구조를 폭넓게 분석하려면 접미사 배열과 같은 다른 자료구조가 더 적합할 수 있습니다.
헷갈리기 쉬운 용어
문자열 검색 알고리즘은 최악 시간과 용도로 구별합니다.
| 알고리즘 | 최악 시간(요지) | 특징 |
|---|---|---|
| 단순 탐색 | O(nm) | 구현이 간단, 일반 텍스트에서는 충분히 빠르기도 함 |
| KMP | O(n + m) | 텍스트를 되돌아가지 않음, 실패 함수 사용 |
| Boyer-Moore | 변형에 따라 다름 | 평균적으로 건너뛰며 빠른 경우가 많음 |
| Rabin-Karp | 평균 O(n + m), 최악 O(nm) | 해시 비교, 여러 패턴에 확장 용이 |
| Aho-Corasick | 텍스트 길이에 선형(패턴 집합 전처리 필요) | 여러 패턴을 동시에 찾음 |
| 접미사 배열 | 전처리 후 질의가 빠름 | 같은 텍스트에서 반복 검색 시 유리 |
참고 문헌
- Knuth, D. E., Morris, J. H., Jr., & Pratt, V. R. (1977). Fast pattern matching in strings. SIAM Journal on Computing, 6(2), 323–350.
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
- Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press.
- Navarro, G., & Raffinot, M. (2002). Flexible Pattern Matching in Strings. Cambridge University Press.
표의 기준값은 위 문헌에 근거한 관례이며, 분야·학술지마다 다른 기준을 쓸 수 있습니다.