32. String Matching

문자열 매칭 알고리즘을 알아보자. 텍스트 T 내에서 T[s+1, \cdots, s+m] = P[1, \cdots, m]이면 패턴 P가 이동 s로 발생(위치 s+1부터 발생)한다고 한다. P가 T 내에서 변화 s로 발생하면 s를 올바른 이동, 아니면 틀린 이동이라 한다. 문자열 매칭 문제는 패턴 P가 텍스트 T 내에서 발생할 수 있는 모든 올바른 이동을 찾는 문제이다. 이를 알아보자.

Notation and terminology

\Sigma^{\ast}는 알파벳 집합 \Sigma로부터 만들 수 있는 모든 유한 길이 문자열의 집합이다. 길이 0의 빈 문자열도 포함된다. 두 문자열 x, y을 이어붙인 것을 접합이라 하며 xy로 표기한다. 문자열 w에 대해 어떤 문자열 x = wy면 w를 x의 접두사라 하며 x = yw면 w를 x의 접미사라 한다. 다음이 성립한다.

Lemma. (Overlapping-suffix lemma) x \sqsupset z, y \sqsupset z일 때 \lvert x \rvert \leq \lvert y \rvert이면 x \sqsupset y, \lvert x \rvert \geq \lvert y \rvert이면 y \sqsupset x, \lvert x \rvert = \lvert y \rvert이면 x = y이다.

32.1. The naive string-matching algorithm

단순 문자열 매칭 알고리즘은 다음과 같다.

NAIVE-STRING-MATCHER(T, P)
n = T.length
m = P.length
for s = 0 to n - m
    if P[1..m] == T[s + 1..s + m]
        print "Pattern occurs with shift" s

이는 O((n-m+1)m)이 걸린다. 물론 이것보다는 더 좋은 방법이 있다.

32.2. The Rabin-Karp algorithm

Rabin-Karp 알고리즘은 최악 수행 시간 O((n-m+1)m), 전처리 시간 O(m)이 든다. 어떤 조건 하에서는 평균 수행 시간은 이것보다 낫다. 이는 모듈러 동치의 아이디어를 사용한다. 그러나 모듈러 동치라고 문자열이 꼭 같다는 법은 없기 때문에 거짓 명중인지 아닌지를 검사해야 한다. 코드로 쓰면 다음과 같다.

RABIN-KARP-MATCHER(T, P, d, q)
n = T.length
m = P.length
h = d^(m-1) mod q
p = 0
t_0 = 0
for i = 1 to m // preprocessing
    p = (dp + P[i]) mod q
    t_0 = (dt_0 + T[i]) mod q
for s = 0 to n - m // matching
    if p == t_s
        if P[1..m] == T[s + 1..s + m]
            print "Pattern occurs with shift" s
    if s < n - m
        t_(s+1) = (d(t_s - T[s + 1]h) + T[s + m + 1]) mod q

평균 기대 수행 시간은 O(n) + O(m(v+ \frac{n}{q}))이며, q를 패턴 길이보다 큰 소수로 잡을 때 이는 O(n + m) = O(n)이 된다.

32.3. String matching with finite automata

많은 문자열 매칭 알고리즘은 유한 오토마톤(정보를 처리하는 간단한 기기)를 사용한다.

Finite automata

유한 오토마톤 M은 다음의 5-튜플이다.

  • 상태의 유한집합 Q
  • 시작 상태 q_{0} \in Q
  • 허용 상태 A \subseteq Q
  • 유한 입력 알파벳 \Sigma
  • M의 전이 함수 \delta : Q \times \Sigma \to Q

오토마톤이 상태 q에서 문자 a를 읽으면 q에서 상태 \delta(q, a)로 이동한다. 현재 상태 q가 A의 원소이면 기기 M은 현재까지 읽은 문자열을 허용한다. 허용되지 않은 입력은 기각된다. 유한 오토마톤 M은 최종 상태 함수 \phi : \Sigma^{\ast} \to Q를 유도하는데 이는 M이 문자열 w를 허용하는 것과 \phi(w) \in A가 동치가 되는 함수이다.

String-matching automata

패턴 P에 대해 이를 매칭하기 위해서는 전처리 과정에서 문자열 매칭 오토마톤을 만든다. 이 때 P에 대응하는 접미사 함수 \sigma(x) = \max \{ k : P_{k} \sqsupset x \}를 정의한다. 즉, 문자열 x에 대해 패턴 P의 접두사들 중 x의 접미사이기도 한 부분 문자열 중 가장 긴 것의 길이를 찾는다. 패턴에 대한 문자열 매칭 오토마톤은 다음과 같이 정의된다.

  • 상태 집합 Q = \{ 0, \cdots, m\}. 시작 상태 q_{0}은 상태 0이고, 허용 상태는 m뿐이다.
  • \delta(q, a) = \sigma(P_{q} a)로 정의된 전이 함수.

이를 정리하면 다음과 같다.

FINITE-AUTOMATON-MATCHER(T, δ, m)
n = T.length
q = 0
for i = 1 to n
    q = δ(q, T[i])
    if q == m
        print "Pattern occurs with shift" i - m

전이 함수를 만드는 전처리 시간을 제외한다면 길이 n 텍스트에 대한 매칭 시간은 \Theta(n)이다. 먼저 이 알고리즘의 정당성을 증명해 보자.

Lemma. (Suffix-function inequality) 문자열 x와 문자 a에 대해 \delta(xa) \leq \delta(x) + 1이다.

Lemma. (Suffix-function recursion lemma) 문자열 x와 문자 a에 대해 \delta(xa) = \delta(P_{q} a)이다.

Theorem. 패턴 P의 문자열 매칭 오토마톤의 최종 상태 함수를 phi라 할 때 T[1..n]을 오토마톤의 입력 텍스트라 하면 i = 0, 1, …, n에 대해 \phi(T_{i}) = \sigma(T_{i})이다.

Computing the transition function

패턴 P에 대한 전이 함수는 다음과 같이 만든다.

COMPUTE-TRANSITION-FUNCTION(P, Σ)
m = P.length
for q = 0 to m
    for each character a ∈ Σ
        k = min(m + 1, q + 2)
        repeat
            k = k - 1
        until P_k ⊃ P_q a
        δ(q, a) = k
return δ

수행 시간은 O(m^{3} \lvert \Sigma \rvert)이지만, O(m \lvert \Sigma \rvert)으로 발전시킬 수 있다.

32.4. The Knuth-Morris-Pratt algorithm

Knuth, Morris, Pratt의 알고리즘은 선형 시간에 계산할 수 있는 보조 함수로 선형 시간에 매칭을 한다. 이를 알아보자.

The prefix function for a pattern

패턴의 전치사 함수 \pi는 패턴이 그 자신 또는 그 자신의 이동과 얼마나 매칭되는지에 대한 정보를 담는다. 이는 다음 질문을 푸는 것과 관계가 있다: 패턴 P[1..q]가 텍스트 T[s+1..s+q]와 매칭된다면 어떤 k < q에 대해 s' + k = s + q면서 P[1..k] = T[s'+1..s'+k]가 되는 최소 이동 s' > s는 어떻게 되는가? 이로부터 정의되는 전치사 함수 \pi : \{1, \cdots, m \} \to \{0, \cdots, m - 1\}는 다음과 같다: \pi[q] = \max \{k : k < q, P_{k} \sqsupset P_{q}\}

이로 유도되는 KMP 알고리즘은 다음과 같다.

KMP-MATCHER(T, P)
n = T.length
m = P.length
π = COMPUTE-PREFIX-FUNCTION(P)
q = 0 // number of characters matched
for i = 1 to n // scan the text from left to right
    while q > 0 and P[q + 1] ≠ T[i]
        q = π[q]  // next character does not match
    if P[q + 1] == T[i]
        q = q + 1 // next character matches
    if q == m // is all of P matched?
        print "Pattern occurs with shift" i - m
        q = π[q] // look for the next match
COMPUTE-PREFIX-FUNCTION(P)
m = P.length
let π[1..m] be a new array
π[1] = 0
k = 0
for q = 2 to m
    while k > 0 and P[k + 1] ≠ P[q]
        k = π[k]
    if P[k + 1] == P[q]
        k = k + 1
    π[q] = k
return π

Running-time analysis

COMPUTE-PREFIX-FUNCTION의 수행 시간은 \Theta(m)이다. KMP-MATCHER의 수행 시간은 \Theta(n)이다. FINITE-AUTOMATON-MATCHER와 비교하면 전처리 시간이 더 짧아졌다.

Correctness of the prefix-function computation

전치사 함수 생성 과정의 정당성을 증명해 보자.

Lemma. (Prefix-function iteration lemma) 길이 m의 패턴 P가 전치사 함수 π를 가졌다 하자. q = 1, \cdots, m에 대해 \pi^{\ast}[q] = \{k : k < q, P_{k} \sqsupset P_{q} \}이다.

Lemma. 길이 m의 패턴 P의 전치사 함수 π에 대해 q = 1, \cdots, m에 대해 \pi[q] > 0이면 \pi[q] - 1 \in \pi^{\ast}[q - 1]이다.

Corollary. 길이 m의 패턴 P의 전치사 함수 π에 대해 q = 2, \cdots, m에 대해 \pi[q] = 0 if E_{q-1} = \emptyset, \pi[q] = 1 + \max \{ k \in E_{q-1} \} if E_{q-1} \neq \emptyset이다.

Correctness of the Knuth-Morris-Pratt algorithm

KMP-MATCHER는 FINITE-AUTOMATON-MATCHER를 전치사 함수를 이용해 재구현한 버전으로 생각할 수 있다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중