Cocke-Younger-Kasami 알고리즘(CYK, 또는 CKY)은 컴퓨터 과학에서 문맥 자유 문법을 위한 구문 분석 알고리즘이다. 이 알고리즘은 1961년 Itiroo Sakai에 의해 처음 발표되었으며, 이후 John Cocke, Daniel Younger, Tadao Kasami, 그리고 Jacob T. Schwartz에 의해 재발견되어 그들의 이름을 따서 명명되었다. 이 알고리즘은 상향식 구문 분석과 동적 프로그래밍을 사용하여 주어진 문자열이 주어진 문법에 의해 생성될 수 있는지 여부를 결정하며, 구문 트리를 구성할 수도 있다. 최악의 경우 실행 시간은 O(n^3 · |G|)이며, 여기서 n은 입력 문자열의 길이이고 |G|는 촘스키 정규형 문법의 크기이다. 이는 점근적 최악의 복잡도 측면에서 가장 효율적인 구문 분석 알고리즘 중 하나로 만든다. 다만 실제로는 다른 알고리즘이 평균 성능에서 더 나을 수 있다.
CYK 알고리즘은 자연어 처리와 컴파일러 설계에서 널리 사용되며, 구문 분석은 기본적인 단계이다. 이 알고리즘은 특히 단순성과 보장된 다항 시간으로 인해 가치가 있으며, 모호한 문법에서도 적용 가능하다. 동적 프로그래밍에 의존하는 이 알고리즘은 모든 가능한 구문 분석을 체계적으로 처리할 수 있어, 프로그래밍 언어의 구문 분석과 인공지능 시스템의 구문 분석과 같은 응용 분야에서 유용하다.
역사적 배경
이 알고리즘은 1961년 Itiroo Sakai에 의해 처음 기술되었지만, 1960년대 후반 John Cocke, Daniel Younger, Tadao Kasami에 의한 독립적인 재발견을 통해 주목받게 되었다. Jacob T. Schwartz도 개발에 기여했다. 알고리즘의 이름은 이러한 재발견을 반영하며, CYK라는 약어는 Cocke, Younger, Kasami에서 유래했다. 이 알고리즘은 형식 언어와 오토마타 이론 과정에서 컴퓨터 과학 교육의 표준 주제가 되었다. 그 개발은 현대의 기계 학습 및 신경망 기반 구문 분석 접근법보다 앞서지만, 기초 기술로서 여전히 관련성을 유지하고 있다.
표준 형식: 촘스키 정규형
CYK 알고리즘의 표준 버전은 문맥 자유 문법이 촘스키 정규형(CNF)일 것을 요구한다. CNF에서 모든 생성 규칙은 A → BC(B와 C는 비단말 기호) 또는 A → α(α는 단말 기호) 형태이다. 또한 시작 기호 S는 빈 문자열을 허용하기 위해 S → ε 생성 규칙을 가질 수 있다. 빈 문자열을 생성하지 않는 모든 문맥 자유 문법은 Sipser가 1997년에 보여준 것처럼 동등한 CNF 문법으로 변환될 수 있다. 이 변환은 알고리즘적이며 문법이 생성하는 언어를 보존한다. CNF 요구 사항은 부분 문자열이 두 부분으로 분할되는 방식을 제한하여 효율적인 동적 프로그래밍을 가능하게 하므로 구문 분석 과정을 단순화한다.
알고리즘 설명
CYK 알고리즘은 3차원 테이블 P[l, s, v]을 채우는 방식으로 작동하며, 여기서 l은 부분 문자열의 길이, s는 해당 부분 문자열의 시작 위치, v는 비단말 기호이다. 항목 P[l, s, v]는 위치 s에서 시작하는 길이 l의 부분 문자열이 비단말 기호 R_v에서 유도될 수 있으면 true로 설정된다. 알고리즘은 부분 문자열 길이의 증가 순서로 진행되며, 길이 1부터 시작한다.
길이 1의 각 부분 문자열에 대해 알고리즘은 R_v → a_s 형태의 단위 생성 규칙을 확인하며, 여기서 a_s는 위치 s의 단말 기호이다. 길이 2 이상의 부분 문자열에 대해서는 부분 문자열을 두 부분으로 나누는 모든 가능한 분할을 고려하고, 각 생성 규칙 A → BC에 대해 첫 번째 부분이 B에서 유도될 수 있고 두 번째 부분이 C에서 유도될 수 있는지 확인한다. 그렇다면 부분 문자열이 A에서 유도 가능하다고 표시한다. 알고리즘은 또한 구문 트리 재구성을 허용하기 위해 역추적 포인터 테이블을 유지한다.
마지막에 입력 문자열은 P[n, 1, 1]이 true이면 언어의 구성원으로 인식되며, 이는 시작 기호 R_1이 전체 문자열을 유도할 수 있음을 의미한다. 그런 다음 역추적 포인터를 사용하여 모든 가능한 구문 트리를 구성할 수 있다.
예시
다음 CNF 문법을 고려하자:
- S → NP VP
- VP → VP PP
- VP → V NP
- VP → eats
- PP → P NP
- NP → Det N
- NP → she
- V → eats
- P → with
- N → fish
- Det → the
이 문법은 "she eats the fish with the fork"와 같은 문장을 구문 분석할 수 있다. CYK 알고리즘은 먼저 단일 단어 부분 문자열을 표시하여 테이블을 채운다: "she"는 NP, "eats"는 VP 또는 V, "the"는 Det, "fish"는 N, "with"는 P, "fork"는 N으로 표시한다. 그런 다음 부분 문자열을 결합한다: "the fish"는 NP(Det N), "eats the fish"는 VP(V NP) 등으로 표시한다. 결국 전체 문장이 S에서 유도될 수 있음을 결정하며, 역추적 포인터는 구문 트리 구조를 드러낸다.
응용 및 중요성
CYK 알고리즘은 구문 분석 이론과 실제에서 중요하다. 자연어 처리에서 구문 분석, 컴파일러 설계에서 프로그래밍 언어 구문 분석, 생물정보학에서 RNA 2차 구조 예측에 사용된다. 최악의 경우 시간 복잡도 O(n^3)은 일반적인 문맥 자유 문법 구문 분석에서 최악의 경우 최적이지만, Earley 파서와 같은 특수 알고리즘은 특정 문법에서 더 효율적일 수 있다. 이 알고리즘의 동적 프로그래밍 접근법은 모호한 문법에도 적합하며, 모든 가능한 구문 분석을 열거할 수 있다. 현대 인공지능에서 CYK 알고리즘은 확률적 문맥 자유 문법과 통계적 구문 분석에 적응되었으며, 생성 규칙의 확률 분포가 주어졌을 때 가장 가능성 높은 구문 트리를 계산한다.
한계 및 확장
표준 CYK 알고리즘의 한계 중 하나는 CNF 요구 사항으로, 이는 문법의 크기를 증가시키고 효율성에 영향을 줄 수 있다. CNF가 아닌 문법을 위한 확장이 존재하며, 예를 들어 Earley 알고리즘은 임의의 문맥 자유 문법을 직접 처리한다. 또한 CYK 알고리즘은 가중 문법과 확률적 문법을 처리하도록 확장되었으며, 각 생성 규칙에 가중치 또는 확률이 있고 최대 가중치 또는 확률을 가진 구문 분석을 찾는 것이 목표이다. 이러한 확장은 음성 인식과 기계 번역에 사용된다. 이 알고리즘은 또한 딥 러닝 기반 모델의 더 고급 구문 분석 기술의 기초를 형성하지만, 이러한 모델은 종종 명시적 문법 규칙보다는 신경망 접근법을 사용한다.