CYK 알고리즘

위키백과 ― 우리 모두의 백과사전.

 

CYK 알고리즘(CYK Algorithm)은 주어진 문맥자유문법이 특정한 문자열을 만들어내는지, 만약 그렇다면 어떻게 만들어내는지 판단하는 알고리즘이다. 이 문제는구문분석(파싱)이라고 불린다. 이 알고리즘은 동적 계획법의 한 예이다.

CYK 알고리즘은 기본적으로 촘스키 정규형식(CNF)으로 표현된 문맥자유문법에 의해 정의된 언어를 판단하는데 사용한다. 하지만 모든 문맥자유문법은 CNF로 표현이 가능하므로 CYK 알고리즘은 모든 문맥자유문법에 대해 사용할 수 있다. 또한, CYK 알고리즘은 CNF로 표현되지 않은 문맥자유문법을 처리하도록 확장할 수 있는데 일반적으로 성능을 높이기 위해 확장하지만 알고리즘을 이해하기는 더 어려워진다.

CYK 알고리즘의 최악의 경우 시간복잡도는 Θ(n³)이고 여기서 n은 파싱할 문자열의 길이이다. 따라서 CYK는 문맥자유문법을 처리하는 알고리즘들 중에서 가장 효율적인 알고리즘 중 하나이다. 하지만 문맥자유문법의 특정한 부분집합을 위해서 고안된 더 나은 알고리즘들도 있다.

[편집]알고리즘

CYK 알고리즘은 상향식(bottom-up) 파싱 알고리즘으로써 문맥자유언어의 membership 문제가 판정문제인지 증명하는데 사용될 수 있으므로 이론적으로 중요하다.

membership 문제를 푸는 CYK 알고리즘은 아래와 같다:

Let the input string consist of n letters, a1 ... an.
Let the grammar contain r terminal and nonterminal symbols R1 ... Rr.
This grammar contains the subset Rs which is the set of start symbols.
Let P[n,n,r] be an array of booleans. Initialize all elements of P to false.
For each i = 1 to n
  For each unit production Rj -> ai, set P[i,1,j] = true.
For each i = 2 to n -- Length of span
  For each j = 1 to n-i+1 -- Start of span
    For each k = 1 to i-1 -- Partition of span
      For each production RA -> RB RC
        If P[j,k,B] and P[j+k,i-k,C] then set P[j,i,A] = true
If any of P[1,n,x] is true (x is iterated over the set s, where s are all the indices for Rs)
  Then string is member of language
  Else string is not member of language

이 글은 스프링노트에서 작성되었습니다.