In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, the Cocke–Younger–Kasami algorithm (alternatively called CYK, or CKY) is a
parsing
Parsing, syntax analysis, or syntactic analysis is the process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar. The term ''parsing'' comes from ...
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
for
context-free grammar
In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules are of the form
:A\ \to\ \alpha
with A a ''single'' nonterminal symbol, and \alpha a string of terminals and/or nonterminals (\alpha can be em ...
s published by Itiroo Sakai in 1961. The algorithm is named after some of its rediscoverers:
John Cocke, Daniel Younger,
Tadao Kasami, and
Jacob T. Schwartz
__NOTOC__
Jacob Theodore "Jack" Schwartz (January 9, 1930 – March 2, 2009) was an American mathematician, computer scientist, and professor of computer science at the New York University Courant Institute of Mathematical Sciences. He was the ...
. It employs
bottom-up parsing In computer science, parsing reveals the grammatical structure of linear input text, as a first step in working out its meaning. Bottom-up parsing recognizes the text's lowest-level small details first, before its mid-level structures, and leavin ...
and
dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.
...
.
The standard version of CYK operates only on context-free grammars given in
Chomsky normal form
In formal language theory, a context-free grammar, ''G'', is said to be in Chomsky normal form (first described by Noam Chomsky) if all of its production rules are of the form:
: ''A'' → ''BC'', or
: ''A'' → ''a'', or
: ''S'' → ...
(CNF). However any context-free grammar may be transformed (after convention) to a CNF grammar expressing the same language .
The importance of the CYK algorithm stems from its high efficiency in certain situations. Using
big ''O'' notation, the
worst case running time of CYK is
, where
is the length of the parsed string and
is the size of the CNF grammar
. This makes it one of the most efficient parsing algorithms in terms of worst-case
asymptotic complexity, although other algorithms exist with better average running time in many practical scenarios.
Standard form
The
dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.
...
algorithm requires the context-free grammar to be rendered into
Chomsky normal form
In formal language theory, a context-free grammar, ''G'', is said to be in Chomsky normal form (first described by Noam Chomsky) if all of its production rules are of the form:
: ''A'' → ''BC'', or
: ''A'' → ''a'', or
: ''S'' → ...
(CNF), because it tests for possibilities to split the current sequence into two smaller sequences. Any context-free grammar that does not generate the empty string can be represented in CNF using only
production rules of the forms
,
, and
where
is the start symbol.
Algorithm
As pseudocode
The algorithm in
pseudocode
In computer science, pseudocode is a plain language description of the steps in an algorithm or another system. Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine re ...
is as follows:
let the input be a string ''I'' consisting of ''n'' characters: ''a''
1 ... ''a''
''n''.
let the grammar contain ''r'' nonterminal symbols ''R''
1 ... ''R''
''r'', with start symbol ''R''
1.
let ''P''
'n'',''n'',''r''be an array of booleans. Initialize all elements of ''P'' to false.
let ''back''
'n'',''n'',''r''be an array of lists of backpointing triples. Initialize all elements of ''back'' to the empty list.
for each ''s'' = 1 to ''n''
for each unit production ''R''
''v'' → ''a''
''s''
set ''P''
'1'',''s'',''v''= true
for each ''l'' = 2 to ''n'' ''-- Length of span''
for each ''s'' = 1 to ''n''-''l''+1 ''-- Start of span''
for each ''p'' = 1 to ''l''-1 ''-- Partition of span''
for each production ''R''
''a'' → ''R''
''b'' ''R''
''c''
if ''P''
'p'',''s'',''b''and ''P''
'l''-''p'',''s''+''p'',''c''then
set ''P''
'l'',''s'',''a''= true,
append
to ''back'' 'l'',''s'',''a''
if ''P'' ,''1'',''1''is true then
''I'' is member of language
return ''back'' -- by ''retracing the steps through back, one can easily construct all possible parse trees of the string.''
else
return "not a member of language"
Probabilistic CYK (for finding the most probable parse)
Allows to recover the most probable parse given the probabilities of all productions.
let the input be a string ''I'' consisting of ''n'' characters: ''a''
1 ... ''a''
''n''.
let the grammar contain ''r'' nonterminal symbols ''R''
1 ... ''R''
''r'', with start symbol ''R''
1.
let ''P''
'n'',''n'',''r''be an array of real numbers. Initialize all elements of ''P'' to zero.
let ''back''
'n'',''n'',''r''be an array of backpointing triples.
for each ''s'' = 1 to ''n''
for each unit production ''R''
''v'' →''a''
''s''
set ''P''
'1'',''s'',''v''= Pr(''R''
''v'' →''a''
''s'')
for each ''l'' = 2 to ''n'' ''-- Length of span''
for each ''s'' = 1 to ''n''-''l''+1 ''-- Start of span''
for each ''p'' = 1 to ''l''-1 ''-- Partition of span''
for each production ''R''
''a'' → ''R''
''b'' ''R''
''c''
prob_splitting = Pr(''R''
''a'' →''R''
''b'' ''R''
''c'') * ''P''
'p'',''s'',''b''* ''P''
'l''-''p'',''s''+''p'',''c'' if prob_splitting > ''P''
'l'',''s'',''a''then
set ''P''
'l'',''s'',''a''= prob_splitting
set ''back''
'l'',''s'',''a''=
if ''P'' ,''1'',''1''> 0 then
find the parse tree by retracing through ''back''
return the parse tree
else
return "not a member of language"
As prose
In informal terms, this algorithm considers every possible substring of the input string and sets