Category Archives: Uncategorized

A tribute to CKY

Recently, here in the School of Informatics we held a Jamboree, and one of the organized events was a “vote for the best/most favorite algorithm.” All sorts of algorithms made it to the list, even including the amazingly ineffective Bogosort algorithm. This event made me think — what is my favorite algorithm? And here’s my answer:

You, my CKY algorithm,
dictate every parser’s rhythm,
if Cocke, Younger and Kasami hadn’t bothered,
all of our parsing dreams would have been shattered.

You are so simple, yet so powerful,
and with the proper semiring and time,
you will be truthful,
to return the best parse — anything less would be a crime.

With dynamic programming, memoization or tabularization,
you are one of a kind,
I really don’t need to mention,
if it weren’t for you, all syntax trees would be behind.

Failed attempts have been made to show there are better,
for example, by using matrix multiplication,
all of these impractical algorithms didn’t matter –
you came out stronger, insisting on just using summation.

All parsing algorithms to you hail,
at least those with backbones which are context-free,
you will never become stale,
as long as we need to have a syntax tree.

It doesn’t matter that the C is always in front,
or that the K and Y can swap,
you are still on the same hunt,
maximizing and summing, nonstop.

Every NLP student knows you intimately,
they have seen your variants dozens of times,
you have earned that respect legitimately,
and you will follow them through their primes.

CKY, going backward and forward,
inside and out,
it is so straightforward –
You are the best, there is no doubt.