맨위로가기

커누스-모리스-프랫 알고리즘

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

커누스-모리스-프랫(KMP) 알고리즘은 1970년대 초 도널드 커누스, 본 프랫, 제임스 H. 모리스에 의해 개발된 효율적인 문자열 검색 알고리즘이다. 이 알고리즘은 텍스트 편집기에서 특정 패턴을 검색하는 문제를 해결하기 위해 고안되었으며, 단순 문자열 검색 알고리즘보다 향상된 최악의 경우 성능을 제공한다. KMP 알고리즘은 패턴의 구조를 미리 분석하여 불필요한 비교를 줄이는 방식으로 동작하며, 부분 일치 테이블(실패 함수)을 활용하여 텍스트의 각 문자를 여러 번 비교하는 것을 방지한다. 알고리즘의 검색 부분은 O(n)의 시간 복잡도를 가지며, 테이블 생성은 O(k)의 시간 복잡도를 가져 전체 알고리즘의 복잡성은 O(n + k)이다. KMP 알고리즘은 실시간 시스템 및 사전식 최소 문자열 회전 문제 해결에도 활용될 수 있으며, 보이어-무어 알고리즘, 단순 문자열 검색 알고리즘과 비교된다.

더 읽어볼만한 페이지

  • 문자열 검색 알고리즘 - 아호 코라식 알고리즘
    아호-코라식 알고리즘은 1975년에 개발된 알고리즘으로 트라이 자료구조, 실패 링크, 출력 링크를 활용하여 텍스트 내에서 여러 문자열 패턴을 효율적으로 검색하며 스팸 필터링, 침입 탐지 시스템 등 다양한 분야에 활용된다.
  • 1970년 컴퓨팅 - 표시적 의미론
    표시적 의미론은 프로그램의 의미를 수학적 객체로 표현하는 방법론으로, 프로그램의 의미를 입출력 매핑 함수로 제공하며, 병행 컴퓨팅 및 예외 처리와 같은 현대 프로그래밍 언어 기능을 지원하기 위한 연구가 활발히 진행되고 있다.
  • 도널드 커누스 - 컴퓨터 프로그래밍의 예술
    도널드 커누스가 집필한 컴퓨터 과학 분야의 대표 저서인 컴퓨터 프로그래밍의 예술은 자료 구조, 알고리즘, 준수치적 알고리즘, 정렬 및 검색, 조합론적 알고리즘 등 프로그래밍 핵심 주제를 깊이 있게 다루고 문제 해결 능력 향상에 기여하며, MIX/MMIX 어셈블리 언어 분석을 통해 튜링상 수상 및 "세기의 과학을 형성한 100여 권의 책"으로 선정되는 등 높은 평가를 받았다.
  • 도널드 커누스 - TeX
    TeX는 도널드 커누스가 개발한 수학, 과학, 공학 분야의 고품질 문서 출력을 위한 조판 시스템이며, 수학 수식 조판에 특화된 매크로 시스템과 높은 확장성을 제공한다.
커누스-모리스-프랫 알고리즘
알고리즘 정보
이름커누스-모리스-프랫 알고리즘
영문명Knuth–Morris–Pratt algorithm
분류문자열 검색 알고리즘
자료 구조문자열
시간 복잡도Θ(m) 전처리 + Θ(n) 매칭
공간 복잡도Θ(m)

2. 역사적 배경

문자열 검색 알고리즘은 주어진 텍스트에서 특정 패턴(문자열)을 찾는 컴퓨터 과학의 기본적인 문제이다. 가장 직관적인 방법은 무차별 대입 검색으로, 텍스트의 모든 가능한 시작 위치에서 패턴과 일치하는지 순차적으로 확인한다. 하지만 이 방식은 텍스트와 패턴의 특성에 따라 매우 비효율적으로 동작할 수 있으며, 특히 특정 문자가 반복되는 최악의 경우 검색 시간이 급격히 증가하는 단점이 있다. 이러한 단순 검색 방식의 한계를 극복하고 검색 효율성을 높이기 위한 연구 과정에서 KMP 알고리즘과 같은 진보된 알고리즘들이 개발되었다. KMP 알고리즘은 패턴 비교 과정에서 얻은 정보를 활용하여 불필요한 비교를 건너뛰는 방식으로 검색 속도를 개선했다.

2. 1. 알고리즘 개발 배경

문자열 검색 알고리즘은 주어진 텍스트(''S'') 안에서 특정 검색어(패턴, ''W'')가 나타나는 시작 위치(''m'')를 찾는 것을 목표로 한다.

가장 기본적인 방법은 '무차별 대입 검색' 또는 '단순 알고리즘'이라 불리는 방식이다. 이 방법은 텍스트의 모든 가능한 시작 위치 ''m''에서 패턴의 첫 문자(''W''[0])와 텍스트의 해당 위치 문자(''S''[''m''])를 비교하는 방식으로 작동한다. 만약 첫 문자가 일치하면, 패턴의 다음 문자(''W''[1])와 텍스트의 다음 문자(''S''[''m''+1])를 비교하는 식으로 패턴의 끝까지 일치하는지 확인한다. 패턴의 모든 문자가 텍스트의 해당 부분과 일치하면 검색 성공이다. 만약 중간에 문자가 다르거나, 패턴 끝까지 확인하기 전에 텍스트 끝에 도달하면 현재 위치 ''m''에서는 실패한 것으로 보고, 시작 위치를 한 칸 뒤(''m''+1)로 옮겨 다시 처음부터 비교를 시작한다.

일반적으로 텍스트의 문자들이 무작위로 분포되어 있다면, 대부분의 비교는 패턴의 첫 몇 글자에서 불일치가 발견되어 빠르게 다음 위치로 넘어간다. 이런 경우 단순 알고리즘은 평균적으로 텍스트 전체 길이(''n'')에 비례하는 비교 횟수만으로 검색을 마칠 수 있어 비교적 효율적이다. 예를 들어, 100만 자 텍스트에서 1000자 패턴을 찾는다면 약 104만 번의 문자 비교로 끝날 수 있다.

하지만 이 성능은 최악의 경우 보장되지 않는다. 텍스트와 패턴에 특정 문자가 반복되는 등 무작위적이지 않은 경우에는 매우 비효율적으로 동작할 수 있다. 예를 들어, 텍스트가 'A' 100만 개로 이루어져 있고(''S'' = "AAAA...A"), 패턴이 'A' 999개 뒤에 'B'가 붙은 형태(''W'' = "AAAA...AB")라고 가정해 보자. 단순 알고리즘은 각 시작 위치 ''m''마다 패턴의 길이(''k''=1000)만큼 문자를 비교한 후에야 마지막 문자 'B'에서 불일치를 발견하고 다음 위치로 넘어간다. 결국, 100만 번의 시작 위치마다 1000번 가까운 비교를 반복하게 되어, 총 비교 횟수는 패턴 길이(''k'')와 텍스트 길이(''n'')의 곱에 비례하여 약 10억 번에 달하게 된다.

이처럼 단순 알고리즘이 특정 상황에서 극도로 비효율적이라는 문제점 때문에, 더 빠른 문자열 검색 알고리즘의 필요성이 대두되었다. KMP 알고리즘은 바로 이러한 배경에서 개발되었다. KMP 알고리즘은 단순 알고리즘과 달리, 비교 과정에서 얻은 '어디까지 일치했었다'는 정보를 버리지 않는다. 패턴 자체의 구조를 미리 분석하여 테이블(부분 일치 테이블 또는 실패 함수 테이블)을 만들어 두고, 비교 중 불일치가 발생했을 때 이 테이블을 참조하여 다음 비교를 시작할 최적의 위치를 찾아낸다. 이를 통해 이미 일치했던 부분을 다시 비교하는 불필요한 작업을 생략하여, 최악의 경우에도 텍스트 길이(''n'')에 비례하는 비교 횟수만으로 검색을 완료할 수 있도록 성능을 개선했다. 즉, KMP는 약간의 사전 계산 시간을 투자하여 전체 검색 시간을 획기적으로 단축시킨다.

3. KMP 알고리즘

KMP 알고리즘은 주어진 텍스트(S) 안에서 특정 패턴(W)을 찾는 문자열 검색 알고리즘이다. 이 알고리즘의 가장 큰 특징은 검색 과정에서 불필요한 비교를 건너뛰어 효율성을 높인다는 점이다.

알고리즘의 핵심은 "부분 일치 테이블"(또는 실패 함수)이라고 불리는 테이블 T를 미리 계산하는 것이다. 이 테이블은 패턴 W 자체의 구조를 분석하여 만들어지며, 검색 중 텍스트 S와 패턴 W의 문자가 일치하지 않을 경우, 다음 비교를 어디서부터 시작해야 할지에 대한 정보를 제공한다.

구체적으로, 텍스트 Sj번째 문자와 패턴 Wk번째 문자를 비교하다가 불일치(S[j] ≠ W[k])가 발생하면, 테이블 Tk번째 값(T[k])을 참조한다. 이 값은 얼마나 뒤로 돌아가야 하는지(백트래킹)를 알려준다. 다음 비교는 패턴 WT[k]번째 문자부터 다시 시작하게 되며, 텍스트 S 내의 비교 위치 j는 뒤로 이동하지 않는다. 이를 통해 이미 일치했던 부분에 대한 중복 비교를 피할 수 있다.

예를 들어, S[m + i]W[i]를 비교하다 실패하면, 다음 가능한 일치는 텍스트 Sm + i - T[i] 위치에서 시작하게 된다. 즉, T[i]는 불일치 후 건너뛸 문자의 수를 나타낸다. 특히, T[0] = -1로 정의하여 패턴의 첫 문자(W[0])에서 불일치가 발생하면 백트래킹 없이 텍스트의 다음 문자로 이동하여 비교를 계속하도록 한다.

이러한 테이블 T를 활용함으로써, KMP 알고리즘은 텍스트 S의 각 문자를 여러 번 비교하는 것을 방지하고 선형 시간 복잡도(O(n+k))로 검색을 수행할 수 있다. 테이블 T의 생성 방법과 구체적인 검색 과정, 의사 코드는 하위 섹션에서 더 자세히 설명된다.

3. 1. 부분 일치 테이블 (실패 함수)

부분 일치 테이블(흔히 실패 함수라고도 불림)은 KMP 알고리즘이 검색 대상 문자열 ''S''의 각 문자를 여러 번 비교하는 것을 피하도록 돕는 핵심 요소이다. 이 테이블은 검색할 패턴 ''W'' 자체를 미리 분석하여 만들어진다. 테이블의 각 항목 ''T[i]''는 패턴의 ''i''번째 위치에서 문자가 불일치했을 때, 다음 비교를 시작하기 위해 패턴을 얼마나 이동해야 하는지에 대한 정보를 담고 있다.

구체적으로, ''T[i]''는 패턴 ''W''의 처음부터 ''i-1''번째 문자까지의 부분 문자열(''W[0...i-1]'')에서, 그 부분 문자열의 접두사이면서 동시에 접미사가 되는 진정한(proper) 부분 문자열 중 가장 긴 것의 길이를 나타낸다. 여기서 '진정한' 부분 문자열이란 원래 문자열 자신을 제외한 부분 문자열을 의미한다. 빈 문자열의 길이는 0으로 간주한다. 패턴의 가장 첫 문자(''W[0]'')에서 불일치가 발생하는 경우는 특별히 처리하는데, 이때는 더 이상 뒤로 돌아갈 곳이 없으므로 ''T[0] = -1''로 설정한다.

예를 들어, 패턴 ''W = "ABCDABD"''에 대한 부분 일치 테이블 ''T''를 만들어 보자. (원본 소스의 두 번째 설명 방식 기준)

  • ''' ''T[0] = -1'' ''': 정의에 따라 설정한다.
  • ''' ''T[1] = 0'' ''': ''W[0]'' = "A"에는 진정한 접두사/접미사가 없다.
  • ''' ''T[2] = 0'' ''': ''W[0...1]'' = "AB". 진정한 접미사는 "B"이고, 진정한 접두사는 "A"이다. 일치하는 것이 없으므로 0이다.
  • ''' ''T[3] = 0'' ''': ''W[0...2]'' = "ABC". 진정한 접미사는 "C", "BC"이고, 진정한 접두사는 "A", "AB"이다. 일치하는 것이 없으므로 0이다.
  • ''' ''T[4] = 0'' ''': ''W[0...3]'' = "ABCD". 진정한 접미사는 "D", "CD", "BCD"이고, 진정한 접두사는 "A", "AB", "ABC"이다. 일치하는 것이 없으므로 0이다.
  • ''' ''T[5] = 1'' ''': ''W[0...4]'' = "ABCDA". 진정한 접미사 중 "A"가 진정한 접두사 "A"와 일치한다. 가장 긴 길이는 1이다.
  • ''' ''T[6] = 2'' ''': ''W[0...5]'' = "ABCDAB". 진정한 접미사 중 "AB"가 진정한 접두사 "AB"와 일치한다. 가장 긴 길이는 2이다.


따라서 패턴 ''W = "ABCDABD"''에 대한 부분 일치 테이블은 다음과 같다. (원본 소스 두 번째 테이블)

`i`0123456
`W[i]`ABCDABD
`T[i]`-1000012



다른 패턴에 대한 부분 일치 테이블의 예시는 다음과 같다. (원본 소스 제공 테이블)

'''패턴 ''W = "ABACABABC"''''' (원본 소스 두 번째 예시 테이블, 패턴 유추)

`i`0123456789
`W[i]`ABACABABC
`T[i]`-10-11-10-1320



'''패턴 ''W = "ABACABAB"''''' (원본 소스 세 번째 예시 테이블, 패턴 유추)

`i`0123456789
`W[i]`ABACABABA
`T[i]`-10-11-10-13-13



'''패턴 ''W = "PARTICIPATE IN PARACHUTE"''''' (공백 문자 포함, 원본 소스 네 번째 예시 테이블)

`i`00010203040506070809101112131415161718192021222324
`W[i]`PARTICIPATEINPARACHUTE
`T[i]`-1000000-10200000-1003000000



이 테이블을 생성하는 과정은 패턴 자체 내에서 검색을 수행하는 것과 유사하며, 효율적으로 계산될 수 있다. 각 단계에서 이전 단계의 계산 결과를 활용하여 불필요한 비교를 건너뛰는 방식으로 최적화된다.

3. 2. 검색 알고리즘

문자열 검색 알고리즘은 주어진 텍스트(S)에서 특정 패턴(W)이 처음 나타나는 시작 위치(m)를 찾는 것을 목표로 한다.

가장 간단한 방식인 무차별 대입 검색 방법은 텍스트의 모든 가능한 시작 위치 m에서 패턴 W의 첫 문자(W[0])와 텍스트의 해당 위치 문자(S[m])를 비교하는 것부터 시작한다. 일치하면 패턴의 다음 문자(W[1])와 텍스트의 다음 문자(S[m+1])를 비교하는 식으로 패턴의 끝까지 비교를 계속한다. 만약 패턴의 모든 문자가 텍스트의 해당 부분과 일치하면, 위치 m에서 패턴을 찾은 것이다. 하지만 문자가 하나라도 일치하지 않으면, 다음 시작 위치(m+1)로 이동하여 비교를 처음부터 다시 시작한다.

이 방식은 평균적으로는 효율적일 수 있지만, 최악의 경우에는 매우 비효율적일 수 있다. 예를 들어, 텍스트 S가 'A' 100만 개로 이루어져 있고 패턴 W가 'A' 999개 뒤에 'B'가 오는 형태라면, 각 시작 위치 m마다 1000번의 비교를 수행해야만 불일치를 확인할 수 있다. 이 경우 패턴의 길이를 k, 텍스트의 길이를 n이라 할 때, 전체 비교 횟수는 O(kn)에 달할 수 있다.

커누스-모리스-프랫(KMP) 알고리즘은 이러한 최악의 경우 성능을 개선한다. KMP 알고리즘은 "부분 일치 테이블"(T)이라는 추가 정보를 미리 계산해두고(이 과정은 O(k) 시간이 걸린다), 이를 활용하여 텍스트 검색을 O(n) 시간에 수행한다. 핵심 아이디어는, 비교 중 불일치가 발생했을 때, 이전에 일치했던 부분의 정보를 활용하여 불필요한 비교를 건너뛰고 다음 비교 위치를 효율적으로 결정하는 것이다.

KMP 알고리즘은 두 개의 주요 상태 변수를 사용하여 검색을 진행한다:

  • m: 텍스트 S 내에서 현재 패턴 W와의 일치를 시도하는 시작 위치.
  • i: 패턴 W 내에서 현재 비교하고 있는 문자의 인덱스.


알고리즘의 동작 과정을 예시를 통해 살펴보자. 텍스트 S = "ABC ABCDAB ABCDABCDABDE" 에서 패턴 W = "ABCDABD" 를 찾는 경우이다. 부분 일치 테이블 T는 미리 계산되어 있다고 가정한다.

1. 검색 시작: m = 0, i = 0.

  • S[0..2] ("ABC")와 W[0..2]가 일치. i는 3이 된다.
  • S[3] (' ') 와 W[3] ('D') 비교. 불일치 발생.
  • 부분 일치 테이블 T (예: T[3] 값)에 따라 다음 위치 결정. W의 "ABC"에는 반복되는 접두사/접미사가 없으므로, 테이블 값(T[3]=0 가정)에 따라 mm + i - T[i] 즉, 0 + 3 - 0 = 3이 되고, iT[i] 즉, 0이 된다.
  • m = 3, i = 0 에서 S[3] (' ')와 W[0] ('A') 비교. 즉시 불일치. 테이블 값(T[0]=-1)에 따라 mm + i - T[i] 즉, 3 + 0 - (-1) = 4가 되고, i는 0이 된다.


2. m = 4 에서의 시도:

  • S[4..9] ("ABCDAB")와 W[0..5]가 일치. i는 6이 된다.
  • S[10] (' ') 와 W[6] ('D') 비교. 불일치 발생.
  • 이전에 일치했던 "ABCDAB"의 끝부분 "AB"는 패턴 W의 시작 부분 "AB"와 동일하다. 부분 일치 테이블(예: T[6]=2)을 참조하여, 다음 비교 위치는 m = 4 + 6 - 2 = 8이 되고, 비교는 i = T[6] = 2부터 시작한다.


3. m = 8 에서의 시도:

  • i = 2 부터 비교 시작. S[8+2] = S[10] (' ') 와 W[2] ('C') 비교. 즉시 불일치 발생.
  • 부분 일치 테이블(예: T[2]=0)을 참조하여, m = 8 + 2 - 0 = 10, i = T[2] = 0으로 설정한다.


4. m = 10 에서의 시도:

  • S[10] (' ') 와 W[0] ('A') 비교. 즉시 불일치 발생.
  • 부분 일치 테이블(T[0]=-1) 참조. m = 10 + 0 - (-1) = 11, i = 0으로 설정한다.


5. m = 11 에서의 시도:

  • S[11..16] ("ABCDAB")와 W[0..5]가 일치. i는 6이 된다.
  • S[17] ('C') 와 W[6] ('D') 비교. 불일치 발생.
  • 부분 일치 테이블(T[6]=2)을 참조하여, m = 11 + 6 - 2 = 15, i = T[6] = 2로 설정한다.


6. m = 15 에서의 시도:

  • i = 2 부터 비교 시작. S[15+2..15+6] ("CDABD")와 W[2..6]가 모두 일치. i는 7이 된다.
  • i가 패턴 W의 길이(7)와 같아졌으므로, 패턴 W를 텍스트 Sm = 15 위치에서 발견했다.


이 예시에서 보듯이, KMP 알고리즘은 "부분 일치 테이블" T를 사용하여 불일치가 발생했을 때 다음 검색 시작 위치(m)와 패턴 내 비교 시작 인덱스(i)를 효율적으로 결정한다. T[i] 값은 W[0...i-1] 에서 일치하는 가장 긴 접두사이면서 동시에 접미사인 문자열의 길이를 나타낸다. (T[0]은 보통 -1로 정의된다).

다음은 KMP 검색 알고리즘의 의사 코드 구현 예시이다.

'''algorithm''' ''kmp_search'':

'''input''':

  • 문자 배열, S (검색 대상 텍스트)
  • 문자 배열, W (찾을 패턴)
  • 정수 배열, T (미리 계산된 부분 일치 테이블)

'''output''':

  • 정수 (패턴 W가 처음 발견된 S 내의 시작 인덱스. 발견되지 않으면 S의 길이 반환)


'''define variables''':

  • 정수, m ← 0 (S 내의 현재 일치 시도 시작 위치)
  • 정수, i ← 0 (W 내의 현재 비교 위치)


'''while''' m + i < 길이(S) '''do''':

'''if''' W[i] == S[m + i] '''then''':

'''let''' i ← i + 1

'''if''' i == 길이(W) '''then''':

'''return''' m // 패턴 발견, 시작 위치 m 반환

'''else''': // 불일치 발생

'''let''' m ← m + i - T[i]

'''if''' i > 0 '''then''':

'''let''' i ← T[i] // i를 테이블 값으로 업데이트 (0 이상)

'''else''': // i가 0일 때 불일치 (T[0] = -1 사용)

'''let''' m ← m + 1 // m을 1 증가시키고 i는 0 유지

(루프 종료 후)

'''return''' 길이(S) // 패턴을 찾지 못함

3. 3. 알고리즘 의사 코드

KMP 알고리즘은 문자열 검색 시 불필요한 비교를 건너뛰기 위해, 찾고자 하는 패턴 문자열 W에 대한 정보를 미리 계산하여 테이블 T에 저장한다. 이 테이블은 흔히 "부분 일치 테이블" 또는 실패 함수라고 불리며, 검색 과정에서 문자가 일치하지 않을 경우, 패턴 문자열을 얼마나 이동시켜 다음 비교를 시작해야 하는지에 대한 정보를 제공한다.

테이블 T의 각 항목 T[i]는 일반적으로 패턴 W의 처음 i개 문자 (W[0...i-1])로 이루어진 부분 문자열에서, 접두사(prefix)이면서 동시에 접미사(suffix)인 가장 긴 문자열의 길이를 나타낸다. 검색 중 텍스트 Sj번째 문자와 패턴 Wk번째 문자에서 불일치(S[j] ≠ W[k])가 발생하면, 테이블 값 T[k]를 참조하여 패턴 내 다음 비교 위치를 T[k]로 설정하고 (즉, k ← T[k]), 텍스트 내 위치 j는 변경하지 않고 비교를 계속한다. 이는 T[k]개의 문자는 이미 일치함이 보장된다는 원리를 이용하는 것이다. 특별히 T[0]-1로 설정하여, 패턴의 첫 문자(W[0])에서 불일치가 발생하면 텍스트의 다음 문자(j ← j + 1)와 패턴의 첫 문자(k ← 0)부터 다시 비교하도록 한다.

다음은 KMP 알고리즘의 검색 단계와 부분 일치 테이블 생성 단계에 대한 의사 코드 예시이다.

=== 검색 알고리즘 (kmp_search) ===

이 알고리즘은 텍스트 S에서 패턴 W가 나타나는 모든 위치를 찾는다.

'''알고리즘''' ''kmp_search'':

'''입력''':

  • S: 문자 배열, 검색 대상 텍스트
  • W: 문자 배열, 찾을 패턴

'''출력''':

  • P: 정수 배열, W가 발견된 S 내 시작 위치(인덱스 0부터)들의 목록
  • nP: 정수, 발견된 총 횟수


'''변수 정의''':

  • j ← 0: S 내 현재 비교 위치
  • k ← 0: W 내 현재 비교 위치
  • T: 정수 배열, 미리 계산된 부분 일치 테이블


'''nP''' ← 0

'''while''' j < 길이(S) '''do'''

'''if''' W[k] = S[j] '''then'''

''// 문자가 일치하면 다음 문자를 비교''

j ← j + 1

k ← k + 1

'''if''' k = 길이(W) '''then'''

''// 패턴 W 전체가 일치하는 것을 발견''

P[nP] ← j - k ''// 일치 시작 위치를 P에 저장''

nP ← nP + 1

''// 다음 가능한 일치를 찾기 위해 테이블 T를 사용하여 k를 업데이트''

''// T[길이(W)] 값은 테이블 생성 시 계산되어 있어야 함''

k ← T[k]

'''else'''

''// 문자가 불일치하는 경우''

''// 테이블 T를 사용하여 다음 비교할 W의 위치 k를 업데이트''

k ← T[k]

'''if''' k < 0 '''then'''

''// T[0] = -1 이었던 경우, S의 다음 위치에서 W의 처음부터 다시 비교 시작''

j ← j + 1

k ← k + 1

=== 부분 일치 테이블 생성 알고리즘 (kmp_table) ===

이 알고리즘은 패턴 W에 대한 부분 일치 테이블 T를 생성한다. 아래는 한 가지 구현 예시이다.

'''알고리즘''' ''kmp_table'':

'''입력''':

  • W: 문자 배열, 분석할 패턴

'''출력''':

  • T: 정수 배열, 계산된 부분 일치 테이블


'''변수 정의''':

  • pos ← 1: T에서 현재 계산 중인 위치 (T[1]부터 계산 시작)
  • cnd ← 0: 현재 후보 부분 문자열(접두사)의 다음 문자에 대한 W 내 인덱스 (0부터 시작)


'''T[0]''' ← -1 ''// T[0]은 항상 -1''

'''while''' pos < 길이(W) '''do'''

'''if''' W[pos] = W[cnd] '''then'''

''// W[pos]와 W[cnd]가 일치하는 경우''

''// W[pos]에서 불일치가 발생하면 W[cnd]에서 불일치가 발생한 것과 동일하게 처리 가능''

''// 따라서 T[pos]에 T[cnd] 값을 저장하여 점프 위치를 최적화할 수 있음''

T[pos] ← T[cnd]

pos ← pos + 1

cnd ← cnd + 1

'''else'''

''// W[pos]와 W[cnd]가 불일치하는 경우''

''// T[pos]는 현재까지 일치했던 접두사의 길이(cnd)로 설정''

T[pos] ← cnd

''// 다음 비교를 위해 cnd를 이전 실패 위치로 이동 (T 테이블을 이용)''

'''while''' cnd ≥ 0 '''and''' W[pos] ≠ W[cnd] '''do'''

cnd ← T[cnd]

''// while 루프 후, pos와 cnd를 다음 위치로 이동하여 계속 진행''

pos ← pos + 1

cnd ← cnd + 1

''// 테이블의 마지막 항목 T[길이(W)] 설정''

''// 검색 알고리즘에서 패턴 전체가 일치했을 때 다음 위치를 찾기 위해 사용됨''

'''T[pos]''' ← cnd

3. 4. 알고리즘 효율성

KMP 알고리즘의 전체 시간 복잡도는 O(n + k)이다. 여기서 n은 검색 대상 텍스트(S)의 길이, k는 찾으려는 패턴(W)의 길이를 의미한다. 이 복잡도는 알고리즘을 구성하는 두 주요 단계, 즉 '검색 단계'와 '부분 일치 테이블 생성 단계'의 복잡도를 합한 결과이다.

KMP 알고리즘의 검색 단계는 O(n)의 시간 복잡도를 가진다. 이는 텍스트 S의 길이에 선형적으로 비례하는 시간 안에 검색이 완료됨을 의미한다. 검색 과정에서 문자가 일치하지 않을 경우, 미리 계산된 '부분 일치 테이블' T를 참조하여 다음 검색 시작 위치를 효율적으로 결정한다. 핵심은 T 테이블의 값(T[i])이 항상 현재 인덱스(i)보다 작다는 성질(T[i] < i)을 이용하여, 검색 시작 위치 m이 절대 뒤로 물러서지 않고 항상 앞으로 나아가거나(m ← m + i - T[i] 에서 i - T[i] > 0 이므로), 비교 중인 텍스트 내 위치(m + i)가 계속 증가한다는 점이다. 이 때문에 전체 검색 과정에서 텍스트의 각 문자는 최대 두 번 정도만 비교되며, 전체 루프는 최대 2n번 실행되는 것으로 분석된다. 따라서 텍스트 전체를 효율적으로 탐색할 수 있다.

패턴 W에 대한 '부분 일치 테이블' T를 생성하는 단계는 O(k)의 시간 복잡도를 가진다. 즉, 테이블 생성 시간은 패턴 W의 길이에 선형적으로 비례한다. 테이블 생성 알고리즘의 루프 역시 분석 결과 최대 2k번 정도 실행되는 것으로 나타나, 패턴 길이에 비례하는 시간 안에 완료된다.

결론적으로, 검색 단계(O(n))와 테이블 생성 단계(O(k))를 합쳐 KMP 알고리즘의 전체 시간 복잡도는 O(n + k)가 된다. 이 효율성은 텍스트나 패턴 내에 반복되는 부분이 얼마나 많은지와 관계없이 일정하게 유지된다는 장점이 있다. 이는 단순하게 모든 위치에서 패턴을 비교하는 방식보다 훨씬 효율적인 성능을 제공한다. 예를 들어, W = "AAAAAAA"와 같이 반복이 많은 패턴의 경우 테이블 T는 [-1, 0, 1, 2, 3, 4, 5]와 같이 구성되는데, 이러한 경우에도 KMP 알고리즘은 선형 시간을 보장한다. 다만, 특정 패턴(예: 반복이 많은 패턴)에서는 보이어-무어 알고리즘이 더 나은 성능을 보일 수도 있지만, 보이어-무어 알고리즘은 최선과 최악의 경우 성능 차이가 큰 반면, KMP는 일관된 선형 시간 성능을 제공한다.

4. KMP 알고리즘 변형

KMP 알고리즘은 기본적인 형태 외에도 특정 요구사항이나 응용 분야에 맞춰 다양하게 변형되어 사용될 수 있다. 이러한 변형 알고리즘들은 KMP의 핵심 원리를 유지하면서도 성능을 개선하거나 특정 문제 해결에 더 적합하도록 수정된 형태를 가진다.

4. 1. 실시간 KMP 알고리즘

KMP의 실시간 컴퓨팅 버전은 알파벳의 각 문자에 대해 별도의 실패 함수 테이블을 사용하여 구현할 수 있다. 텍스트에서 문자 x에서 불일치가 발생하면, 패턴에서 불일치가 발생한 인덱스 i에 대해 문자 x에 대한 실패 함수 테이블을 참조한다. 이로 인해 패턴의 접두사와 일치하는 i에서 끝나는 가장 긴 부분 문자열의 길이가 반환되며, 접두사 뒤의 문자가 x라는 조건이 추가된다. 이러한 제한으로 인해 텍스트의 문자 x는 다음 단계에서 다시 검사할 필요가 없으므로 텍스트의 각 인덱스를 처리하는 사이에 상수 개의 연산만 실행된다. 이는 실시간 컴퓨팅 제한 사항을 충족한다.

부스 알고리즘은 KMP 전처리 함수의 수정된 버전을 사용하여 사전식 최소 문자열 회전을 찾는다. 실패 함수는 문자열이 회전됨에 따라 점진적으로 계산된다.

5. 다른 알고리즘과의 비교

KMP 알고리즘은 문자열 검색 분야에서 중요한 위치를 차지하며, 다른 여러 알고리즘과 비교하여 그 특징과 효율성을 이해할 수 있다.

가장 기본적인 접근 방식인 단순 문자열 검색은 구현이 간단하지만, 텍스트와 패턴의 특정 조합(예: 반복되는 문자가 많은 경우)에서는 매우 비효율적인 성능을 보일 수 있다. 단순 검색은 최악의 경우 텍스트 길이(n)와 패턴 길이(k)의 곱에 비례하는 시간(O(nk))이 걸릴 수 있다. 반면, KMP 알고리즘은 패턴의 내부 구조 정보를 미리 분석하여 불필요한 비교를 건너뛰므로, 최악의 경우에도 선형 시간(O(n+k))의 안정적인 성능을 보장한다.

또 다른 고성능 알고리즘인 보이어-무어 알고리즘과 비교하면, KMP 알고리즘은 어떤 입력에 대해서도 일관된 선형 시간 성능을 제공한다는 장점이 있다. 보이어-무어 알고리즘은 평균적으로 KMP보다 더 빠른 성능을 보이는 경우가 많지만, 입력 데이터에 따라 성능 편차가 있을 수 있다. 각 알고리즘의 구체적인 작동 방식과 성능 특성에 대한 자세한 비교는 아래 하위 섹션에서 확인할 수 있다.

5. 1. 보이어-무어 알고리즘

KMP 알고리즘W = "AAAAAAA"와 같은 경우 최악의 성능을 보이지만, 이러한 문자열 검색에서는 보이어-무어 알고리즘이 최고의 성능을 보인다. KMP 알고리즘은 최선과 최악의 경우 모두 선형 시간에 검색이 완료되지만, 보이어-무어 알고리즘은 최선과 최악의 경우 소요 시간이 크게 다르다.

5. 2. 단순 문자열 검색 (무차별 대입)

문자열 검색은 주어진 텍스트 `S[]` 안에서 특정 검색어(패턴) `W[]`와 일치하는 부분의 시작 위치 `m`을 찾는 과정이다.

가장 기본적인 방법은 단순 문자열 검색 또는 무차별 대입(brute-force) 방식으로 알려진 알고리즘이다. 이 방식은 텍스트 `S[]`의 모든 가능한 시작 위치 `m`에서 패턴 `W[]`와의 일치 여부를 순서대로 확인한다.

구체적인 작동 방식은 다음과 같다.

# 텍스트의 현재 위치 `m`에서 패턴의 첫 번째 문자와 비교한다 (`S[m] == W[0]`).

# 만약 첫 문자가 일치하면, 패턴의 다음 문자(`W[1]`, `W[2]`, ...)와 텍스트의 다음 문자(`S[m+1]`, `S[m+2]`, ...)를 순서대로 계속 비교한다 (`S[m+i] == W[i]`).

# 패턴 `W[]`의 모든 문자가 텍스트의 해당 부분과 완전히 일치하면, 위치 `m`에서 일치하는 부분을 찾은 것으로 간주하고 검색을 성공적으로 마칠 수 있다.

# 비교 도중 문자가 일치하지 않거나, 패턴 전체를 비교하기 전에 텍스트의 끝에 도달하면 현재 위치 `m`에서의 비교는 실패한 것이다.

# 비교에 실패하면, 텍스트의 다음 시작 위치(`m+1`)로 이동하여 1단계부터 다시 비교를 시작한다.

# 텍스트의 끝까지 모든 위치를 확인했는데도 패턴을 찾지 못하면 최종적으로 검색은 실패한다.

일반적으로 텍스트 내 문자들이 무작위로 분포되어 있다면, 대부분의 위치에서는 패턴의 첫 몇 글자만 비교해도 불일치가 발생하여 빠르게 다음 위치로 넘어갈 수 있다. 예를 들어 알파벳 26개 문자가 균등하게 분포되어 있다면, 첫 문자가 일치할 확률은 1/26, 두 문자가 연속으로 일치할 확률은 1/262로 급격히 낮아진다. 따라서 평균적인 경우, 텍스트 `S[]`의 길이가 `n`일 때 단순 검색의 시간 복잡도는 O(n)으로 매우 효율적인 편이다. 예를 들어, 100만 자 길이의 텍스트에서 1000자 길이의 패턴을 찾는다면, 평균적으로 약 104만 번의 문자 비교만으로 검색이 완료될 수 있다.

하지만 이는 평균적인 경우의 성능이며, 최악의 경우에는 성능이 크게 저하될 수 있다. 예를 들어, 텍스트 `S[]`가 'A' 100만 개로 이루어져 있고("AAAAAAAA..."), 패턴 `W[]`가 'A' 999개 뒤에 'B'가 붙은 형태("AAAA...AAB")라고 가정해 보자. 이 경우, 텍스트의 거의 모든 시작 위치 `m`에서 패턴의 마지막 문자인 'B'와 비교할 때까지 999번의 'A' 비교가 성공하게 된다. 즉, 각 위치 `m`마다 패턴의 길이(`k` = 1000)만큼 비교를 수행해야만 불일치를 확인할 수 있다. 텍스트의 길이가 `n`이고 패턴의 길이가 `k`일 때, 이러한 최악의 경우 시간 복잡도는 O(nk)가 된다. 앞선 예시에서는 약 100만(위치 수) * 1000(패턴 길이) = 10억 번의 문자 비교가 필요하게 되어 매우 비효율적이다.

이러한 단순 검색의 비효율성을 개선한 알고리즘으로 KMP 알고리즘 등이 있다. KMP 알고리즘은 패턴 내부에 대한 정보를 미리 분석하여 테이블을 만들고(O(k) 시간 소요), 이를 활용해 불필요한 비교를 건너뛰어 최악의 경우에도 O(n)의 시간 복잡도로 검색을 수행한다. 단순 검색은 이전 비교에서 얻은 정보를 활용하지 않지만, KMP 알고리즘은 이 정보를 효과적으로 사용하여 성능을 향상시킨다.

참조

[1] 문서 m is the length of the pattern, which is the string we are searching for in the text which is of length n
[2] 간행물 Fast pattern matching in strings 1977
[3] 간행물 The Dangers of Computer-Science Theory
[4] 간행물 A linear pattern-matching algorithm
[5] 간행물 Real-time recognition of the inclusion relation http://logic.pdmi.ra[...] 2017-07-04
[6] 문서 Knuth mentions this fact in the errata of his book ''Selected Papers on Design of Algorithms '' : {{quotation|I learned in 2012 that Yuri Matiyasevich had anticipated the linear-time pattern matching and pattern preprocessing algorithms of this paper, in the special case of a binary alphabet, already in 1969. He presented them as constructions for a Turing machine with a two-dimensional working memory.}}
[7] 간행물 Dynamic text and static pattern matching



본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com