KMP 알고리즘 (Knuth-Morris-Pratt Algorithm)
쉽게 풀면
긴 문서에서 특정 단어를 찾는다고 해봅시다. 가장 단순한 방법은 문서의 첫 글자부터 한 칸씩 밀어가며 단어와 일일이 대조하는 것인데, 이러면 비교했던 내용을 매번 처음부터 다시 확인하게 되어 느립니다. KMP 알고리즘은 "패턴 자기 자신"을 미리 분석해서 "일치하다가 틀렸을 때, 몇 칸을 건너뛰어도 안전한지"를 나타내는 표(실패 함수, failure function)를 만들어 둡니다. 이 표 덕분에 불일치가 나와도 이미 확인한 부분을 다시 훑지 않고 필요한 만큼만 건너뛸 수 있어서, 문서 길이와 패턴 길이의 합에 비례하는 시간(선형 시간)만으로 검색을 끝낼 수 있습니다.
왜 중요한가
문자열에서 패턴을 찾는 작업은 텍스트 검색, 네트워크 침입 탐지, 생물정보학의 서열 분석 등 다양한 분야에서 반복적으로 등장하는 기본 연산이며, 데이터 규모가 커질수록 선형 시간 보장이 중요해집니다. KMP는 이런 패턴 매칭 문제의 시간복잡도를 이론적으로 최적에 가깝게 낮춘 대표 알고리즘이라, 문자열 처리 성능을 논하는 논문에서 비교 기준이나 하위 모듈로 자주 인용됩니다.
논문에서는 이렇게 쓰입니다
이 문장은 "많은 양의 텍스트 데이터 안에서 원하는 문자열 패턴을 KMP 방식으로 빠르게 찾아냈다"는 뜻입니다. 침입 탐지, 유전자 서열 분석, 텍스트 검색 엔진 등에서 자주 쓰입니다.
생물정보학 연구에서 유전자 서열 내 특정 패턴(모티프)의 위치를 빠르게 찾을 때 활용되는 예시이다.
보안 분야에서 실시간 트래픽 검사 속도를 높이기 위해 패턴 매칭 알고리즘을 적용한 예시이다.
조금 더 깊게 보면
KMP 알고리즘의 핵심은 패턴 자체의 접두사와 접미사가 겹치는 최대 길이를 미리 계산해 둔 실패 함수(부분 일치 표)입니다. 이 표 덕분에 불일치가 발생해도 패턴 포인터만 적절히 이동시키고 텍스트 포인터는 뒤로 되돌리지 않아도 되므로, 전체 탐색이 텍스트 길이와 패턴 길이의 합에 비례하는 선형 시간에 끝납니다. 여러 패턴을 동시에 찾아야 하는 경우에는 이 아이디어를 확장한 아호-코라식(Aho-Corasick) 알고리즘이 흔히 쓰이며, 대규모 텍스트에서 반복 검색이 많다면 접미사 배열이나 접미사 트리 같은 인덱싱 구조가 대안으로 논의되기도 합니다.
주의할 점
KMP 알고리즘은 패턴 하나를 문자열 하나에서 찾는 데는 효율적이지만, 여러 패턴을 동시에 찾거나 문자열 전체의 반복 구조를 폭넓게 분석하려면 접미사 배열과 같은 다른 자료구조가 더 적합할 수 있습니다.