CYK 알고리즘

3. 알고리즘

CYK 알고리즘은 주어진 문자열의 모든 부분 문자열에 대해, 해당 부분 문자열이 문법의 각 비단말 기호로부터 생성될 수 있는지 여부를 저장하는 테이블을 작성한다. 이 테이블은 동적 계획법을 사용하여 채워진다.

CYK 알고리즘은 상향식 알고리즘이며, 문맥 자유 언어의 멤버십 문제가 결정 가능함을 구성적으로 증명할 수 있다는 점에서 이론적으로도 중요하다.

간단히 말하면, CYK 알고리즘은 입력 문자열의 모든 가능한 부분 문자열을 고려하여 각 부분 문자열이 특정 비단말 기호에서 생성될 수 있는지 여부를 테이블에 저장한다. 구체적인 알고리즘의 동작 방식은 다음과 같다.

• 입력: ''n''개의 문자 ''a''₁ ... ''a''_''n''으로 구성된 문자열.
• 문법: ''r''개의 비단말 기호 ''R''₁ ... ''R''_''r'' (시작 기호 ''R''_s 포함).
• P\[n,n,r]: 불리언 배열. 모든 요소를 false로 초기화.
• i = 1부터 n까지:
• 각 생성 규칙 R_j → a_i에 대해, P\[i,1,j] = true로 설정.
• i = 2부터 n까지 (범위의 길이):
• j = 1부터 n-i+1까지 (범위의 시작 위치):
• k = 1부터 i-1까지 (범위의 구분):
• 각 생성 규칙 R_A → R_B R_C에 대해:
• 만약 P\[j,k,B]와 P\[j+k,i-k,C]가 모두 true이면, P\[j,i,A] = true로 설정.
• P\[1,n,x] 중 하나라도 true이면 (x는 R_s의 모든 인덱스 s에 대해 반복), 입력 문자열은 해당 언어에 속한다. 그렇지 않으면 속하지 않는다.

3. 1. 의사 코드

3. 2. 확률적 CYK

4. 예시

다음은 주어진 문법이다.

:$\backslash begin\{align\}$

\ce{S} & \ \ce{-> NP\ VP}\\

\ce{VP} & \ \ce{-> VP\ PP}\\

\ce{VP} & \ \ce{-> V\ NP}\\

\ce{VP} & \ \ce{-> eats}\\

\ce{PP} & \ \ce{-> P\ NP}\\

\ce{NP} & \ \ce{-> Det\ N}\\

\ce{NP} & \ \ce{-> she}\\

\ce{V} & \ \ce{-> eats}\\

\ce{P} & \ \ce{-> with}\\

\ce{N} & \ \ce{-> fish}\\

\ce{N} & \ \ce{-> fork}\\

\ce{Det} & \ \ce{-> a}

\end{align}

이제 "she eats a fish with a fork" 문장을 CYK 알고리즘으로 분석한다. 아래 표에서 P[i,j,k]는 i번째 행(아래에서부터 1로 시작), j번째 열(왼쪽에서부터 1로 시작)을 의미한다.

위 표에서 시작 기호 S가 P[7,1]에 있으므로, 이 문장은 주어진 문법으로 생성될 수 있다.

간단히 설명하면, CYK 알고리즘은 단어 배열에서 가능한 모든 조합을 고려한다. 먼저 길이 1의 배열을 검토하고, 그다음 길이 2의 배열을 검토하는 식으로 진행한다. 길이 2 이상의 배열은 두 부분으로 나누어, P → Q R 생성 규칙으로 Q와 R이 각각 배열의 전반부와 후반부에 일치하는지 확인한다. 일치하면 P를 해당 배열 전체와 일치하는 것으로 기록한다. 이 과정이 끝나면, 입력 문자열 전체가 시작 기호에서 생성되는지 알 수 있다.

5. 확장

CYK 알고리즘은 주어진 문장이 특정 문맥 자유 문법에 속하는지 판별하는 것 외에도, 다양한 방식으로 확장될 수 있다.

• 구문 분석 트리 생성: CYK 알고리즘은 단순한 인식기를 넘어, 구문 분석 트리를 생성하는 파서로 확장될 수 있다. 배열 P의 각 요소에 부울 값 대신 파스 트리의 노드를 저장하고, 이 노드들을 연결하여 트리 구조를 만들 수 있다. 모호한 문장의 경우, 모든 가능한 파스 트리를 보존하기 위해 추가적인 테이블 B를 사용하여 파싱 과정에서 해당 노드를 얻는 모든 방법을 저장할 수 있다. 이렇게 생성된 공유 포레스트는 모호한 문법으로 읽을 수 있다.

• 가중 문맥 자유 문법 파싱: CYK 알고리즘은 가중 문맥 자유 문법이나 확률 문맥 자유 문법을 처리하도록 확장될 수 있다. 이 경우, 테이블 P에 가중치나 확률을 저장하여 P[i, j, A]가 i부터 j까지의 부분 문자열이 A로부터 생성될 수 있는 최소 가중치(최대 확률)를 나타내도록 한다. 더 나아가, 모든 가능한 구문 분석을 가중치(확률) 순으로 열거할 수도 있다.^[1]

• 비 촘스키 정규 형식 문법 파싱: CYK 알고리즘은 촘스키 정규 형식으로 변환하지 않고도 임의의 문맥 자유 문법을 처리하도록 일반화될 수 있다. Lange와 Leiß는 알고리즘의 효율성, 명확성, 단순성을 유지하면서 CYK 알고리즘을 일반화하는 방법을 제안했다.

• 수치 안정성: 확률적 CYK 알고리즘을 긴 문자열에 적용할 때 발생할 수 있는 수치적 불안정성 문제는 로그 확률을 사용하여 해결할 수 있다. 확률 값 대신 로그 확률을 사용하면 곱셈이 덧셈으로 바뀌어 계산이 안정적으로 이루어진다.^[1]

5. 1. 구문 분석 트리 생성

6. Valiant의 알고리즘

밸리언트는 CYK 알고리즘의 확장을 제시했다. 그의 알고리즘은 CYK 알고리즘과 동일한 파싱 테이블을 계산하지만, 효율적인 곱셈을 위한 알고리즘인 0-1 엔트리를 가진 행렬을 사용하여 이 계산을 수행할 수 있음을 보였다.^[4]

이러한 행렬의 곱셈에 Coppersmith–Winograd 알고리즘을 사용하면 점근적 최악의 경우 실행 시간은 $O(n^\{2.38\}\; \backslash cdot\; |G|)$가 된다. 그러나 빅 오 표기법에 의해 숨겨진 상수항이 너무 커서 Coppersmith–Winograd 알고리즘은 현재 컴퓨터에서 처리하기에는 너무 큰 행렬에만 가치가 있다. 효율적인 행렬 곱셈에 대한 의존성을 완전히 피할 수는 없다. 리는 $O(n^\{3-\backslash varepsilon\}\; \backslash cdot\; |G|)$ 시간에 작동하는 문맥 자유 문법에 대한 모든 파서가 $O(n^\{3\; -\; \backslash varepsilon/3\})$ 시간에 0-1 엔트리를 가진 $(n\; \backslash times\; n)$ 행렬의 곱을 계산하는 알고리즘으로 효과적으로 변환될 수 있음을 증명했으며, 이는 Abboud et al.에 의해 상수 크기 문법에 적용되도록 확장되었다.^[4]

참조

_[1] 서적 Parsing techniques : a practical guide Springer 2008
_[2] 간행물 "Syntax in universal translation" Her Majesty’s Stationery Office, London 1962
_[3] 서적 Introduction to the theory of computation https://www.worldcat[...] Thomson Course Technology 2006
_[4] 논문 If the Current Clique Algorithms are Optimal, so is Valiant's Parser 2015-11-05