CYK Algorithm

상위 문서: Context-Free Languages

개요

CNF으로 변환된 문법을 기반으로, 주어진 문자열이 언어 [math]\displaystyle{ L }[/math]에 속하는지를 결정론적으로(deterministic) 판단할 수 있다. 이때 recognizer라는 개념이 등장하는데, recognizer는 문자열 [math]\displaystyle{ w }[/math]를 입력받아, 그 문자열이 언어 [math]\displaystyle{ L }[/math]에 속하는지 여부를 판별하는 알고리즘이다. 이때 아래와 같이 수식이 정의된다:

• [math]\displaystyle{ L = L(G) }[/math]
• [math]\displaystyle{ w = w_1w_2\cdots w_n }[/math]
• [math]\displaystyle{ D(i, l, A) = true \leftrightarrow A \Rightarrow* w_iw_{i+1}\cdots w_{i+l-1} }[/math]

즉, 위에서 [math]\displaystyle{ D(i, l, A) }[/math]은 "비단말 [math]\displaystyle{ A }[/math]가 [math]\displaystyle{ w }[/math]의 특정 구간을 유도할 수 있는가?"를 기록하는 boolean 테이블이다. 아래는 [math]\displaystyle{ D(i, l, A) }[/math]가 true가 되는 두가지 경우이다:

1. 문법에 규칙 [math]\displaystyle{ A \rightarrow a }[/math]가 존재하는 경우
   • 입력 문자열의 i번째 문자가 [math]\displaystyle{ a }[/math]이며 [math]\displaystyle{ l = 1 }[/math]
2. 문법에 규칙 [math]\displaystyle{ A \rightarrow BC }[/math]이 존재하는 경우, 어떤 분할점 [math]\displaystyle{ k\,\, (1 \le k \lt l) }[/math]에 아래 두 조건이 모두 참
   • [math]\displaystyle{ D(i,k,B) }[/math]
   • [math]\displaystyle{ D(i+k, l-k, C) }[/math]

즉, A가 길이 l의 부분문자열을 만들 수 있으려면 좌측 비단말 B가 앞쪽 부분, 우측 비단말 C가 뒷부분을 생성할 수 있어야 한다. 이때 아래와 같은 명제가 성립한다:

[math]\displaystyle{ w \in L \Leftrightarrow (w = \epsilon \land S \rightarrow \epsilon) \lor D(1, |w|, S) }[/math]

CYK(Cocke–Younger–Kasami) 알고리즘은 위 명제를 바탕으로 CFL(Context-Free Language)를 인식하기 위한 동적 프로그래밍 기반의 알고리즘이다.

Implementation of CYK Algorithm

Initialization Step

CYK 알고리즘을 수행하기 위해서는 먼저 모든 D(i,l,A)를 false로 초기화해야 한다. 또한 각 w의 각 문자 위치 [math]\displaystyle{ i = 1sim n }[/math]에 대해 문법의 모든 규칙 [math]\displaystyle{ A \rightarrow a }[/math]를 확인하여 만약 [math]\displaystyle{ w_i = a }[/math]이면 [math]\displaystyle{ D(i,1,A)=true }[/math]로 설정한다.

Main Loop

CYK 알고리즘의 main loop에서는 문자열 길이 2 이상인 구간을 처리한다. 아래는 이를 수행하는 코드이다:

for l from 2 to n:             // 부분문자열의 길이
  for i from 1 to n - (l - 1): // 시작 위치
    for k from 1 to l - 1:     // 분할 위치
      for each rule A → BC:
        if D(i, k, B) and D(i+k, l-k, C) are true:
            set D(i, l, A) = true

즉, 모든 가능한 부분 문자열 구간과 그 분할점을 고려하면서 어떤 비단말 A가 그 구간을 생성할 수 있는지를 동적 프로그래밍으로 확인하는 것이다. 이를 실행한 뒤, [math]\displaystyle{ D(1,n,S)=true }[/math]이면 입력 문자열 [math]\displaystyle{ w }[/math]는 시작 단말 [math]\displaystyle{ S }[/math]로부터 유도 가능한 것이다. 즉, 이 경우 주어진 [math]\displaystyle{ w }[/math]는 [math]\displaystyle{ w \in L }[/math]을 만족한다.

Time Complexity of the CYK Algorithm

CYK 알고리즘의 시간 복잡도는 [math]\displaystyle{ O(n^3\cdot |G|) }[/math]이다. 이때 n은 입력 문자열의 길이이고, |G|는 문법의 규칙 수이다. 이는 다른 일반적인 CFL 판별 알고리즘(Earley 등)과 비슷한 수준이다.