CKY 파싱(또한 CYK, Cocke-Younger-Kasami라고도 불림)은 문맥 자유 문법을 위한 파싱 알고리즘으로, 상향식 파싱과 동적 프로그래밍을 사용한다. 이 알고리즘은 1961년 Itiroo Sakai에 의해 처음 발표되었으며, 이후 John Cocke, Daniel Younger, Tadao Kasami, Jacob T. Schwartz에 의해 독립적으로 재발견되어 그들의 이름을 따서 명명되었다. 이 알고리즘은 주어진 문자열이 문법에 의해 생성될 수 있는지 결정하며, 가능하다면 해당 문자열에 대한 모든 가능한 파싱 트리를 구성할 수 있다.
표준 버전의 CKY는 오직 촘스키 정규형(CNF)의 문맥 자유 문법에서만 작동하며, 여기서 모든 생성 규칙은 A → BC(두 개의 비단말 기호) 또는 A → a(단말 기호) 형태 중 하나이다. 빈 문자열을 생성하지 않는 모든 문맥 자유 문법은 알고리즘적으로 동등한 CNF 문법으로 변환될 수 있으므로, 이 제한은 원칙적으로 알고리즘의 적용 가능성을 제한하지 않는다. 빈 문자열을 생성하는 문법의 경우, 시작 기호 S에 대해 S → ε 규칙을 명시적으로 허용할 수 있다.
CKY 파싱의 중요성은 최악의 경우 시간 복잡도가 O(n^3 · |G|)라는 점에서 비롯되며, 여기서 n은 입력 문자열의 길이이고 |G|는 CNF 문법의 크기이다. 이는 점근적 최악의 경우 동작 측면에서 가장 효율적인 파싱 알고리즘 중 하나로 만든다. 다만 다른 알고리즘들이 실제 시나리오에서 더 나은 평균 실행 시간을 가질 수 있다.
알고리즘 개요
이 알고리즘은 3차원 테이블 P[l, s, v]를 채우는 방식으로 작동하며, 각 항목은 위치 s에서 시작하는 길이 l의 부분 문자열이 비단말 기호 R_v로부터 생성될 수 있는지 여부를 나타내는 부울 값이다. 테이블은 부분 문자열 길이의 증가 순서로 채워지며, 길이 1의 부분 문자열부터 시작한다.
입력의 각 단말 기호에 대해, 알고리즘은 R_v → a_s 형태의 모든 단위 생성 규칙을 확인하고 해당 테이블 항목을 true로 표시한다. 더 긴 부분 문자열의 경우, 부분 문자열을 두 부분으로 나누는 모든 가능한 분할을 고려하고 A → BC 생성 규칙이 존재하여 B가 첫 번째 부분을 생성하고 C가 두 번째 부분을 생성하는지 확인한다. 그러한 생성 규칙이 존재하면 A에 대한 항목이 true로 설정된다.
의사 코드
입력을 n개의 문자로 구성된 문자열 I: a1 ... an이라고 하자.
문법에 r개의 비단말 기호 R1 ... Rr이 있고 시작 기호는 R1이라고 하자.
P[n,n,r]을 부울 배열이라고 하자. P의 모든 요소를 false로 초기화한다.
back[n,n,r]을 역추적 삼중항 목록의 배열이라고 하자. back의 모든 요소를 빈 목록으로 초기화한다.
각 s = 1부터 n까지
각 단위 생성 규칙 Rv → as에 대해
P[1,s,v] = true로 설정
각 l = 2부터 n까지 -- 스팬 길이
각 s = 1부터 n-l+1까지 -- 스팬 시작
각 p = 1부터 l-1까지 -- 스팬 분할
각 생성 규칙 Ra → Rb Rc에 대해
P[p,s,b]와 P[l-p,s+p,c]가 true이면
P[l,s,a] = true로 설정,
<p,b,c>를 back[l,s,a]에 추가
P[n,1,1]이 true이면
I는 언어의 구성원이다
back을 반환 -- back을 통해 단계를 역추적하면 문자열의 모든 가능한 파싱 트리를 쉽게 구성할 수 있다.
그렇지 않으면
"언어의 구성원이 아님"을 반환
예시
다음 CNF 문법을 고려하자:
S → NP VP
VP → VP PP
VP → V NP
VP → eats
PP → P NP
NP → Det N
NP → she
V → eats
P → with
Det → the
N → fish
문자열 "she eats the fish with the fish"를 파싱하려면, 알고리즘은 먼저 모든 길이 1 부분 문자열을 표시한다. 예를 들어, NP → she 때문에 P[1,1,NP]가 true로 설정되고, VP → eats 때문에 P[1,2,VP]가 true로 설정된다. 그런 다음 길이 2 부분 문자열을 처리하며, "she eats"는 S → NP VP로 유도될 수 있으므로 P[2,1,S]가 true가 된다. 이 과정은 더 긴 부분 문자열에 대해 모든 분할을 고려하면서 계속된다. 마지막에 P[n,1,S]가 true이면 문자열이 언어의 일부로 인식되고, 역추적 포인터를 통해 파싱 트리 재구성이 가능하다.
응용 및 변형
CKY 파싱은 자연어 처리와 전산 언어학에서 널리 사용되며, 특히 확률적 문맥 자유 문법을 사용한 파싱에서 두드러진다. 가중 문법을 처리하고 평균 사례 성능을 개선하기 위한 알고리즘 변형이 개발되었다. 알고리즘의 동적 프로그래밍 접근 방식은 CNF 변환 없이 임의의 문맥 자유 문법을 처리하지만 유사한 최악의 경우 복잡도를 가진 Earley 파서와 같은 다른 파싱 방법과도 연결된다.
현대 Artificial intelligence 시스템에서 CKY 파싱은 주로 Neural network 기반 접근 방식, 특히 Large language model에서 사용되는 Transformer (architecture) 모델에 의해 크게 대체되었다. 그러나 이 알고리즘은 형식 언어 이론에서 여전히 중요한 기초 기술로 남아 있으며 컴퓨터 과학 교육 과정에서 여전히 가르쳐진다. 동적 프로그래밍과 상향식 분석의 원리는 Sequence-to-Sequence (Seq2Seq) 모델 및 Beam Search 디코딩과 같은 다른 영역에서도 나타난다.
알고리즘의 효율성과 명확성은 파싱 및 Machine learning 교과서에서 표준 예시로 만들었다. MIT CSAIL 및 Stanford AI Lab과 같은 연구 기관이 그 연구와 응용에 기여했으며, 생물정보학 및 컴파일러 설계와 같이 구조화된 데이터의 정확한 파싱이 필요한 분야에서 여전히 관련성이 있다.
한계
CKY 파싱은 문법이 촘스키 정규형이어야 하며, 이는 생성 규칙 수와 문법 크기를 증가시킬 수 있다. O(n^3) 최악의 경우 시간 복잡도는 특히 실시간 응용에서 매우 긴 입력 문자열에 대해 금지적일 수 있다. 또한 알고리즘의 공간 복잡도는 O(n^2 · r)이며, 이는 많은 비단말 기호를 가진 문법에서 클 수 있다. 이러한 한계에도 불구하고 CKY 파싱은 정확한 파싱 알고리즘의 벤치마크이자 문맥 자유 언어 연구의 핵심 개념으로 남아 있다.