CKY Algorithm?

[aetilley]

I've noticed that there are a lot of bottom-up parsers, but I don't find the exact CKY parser anywhere or the associated 'inside algorithm' for sentence scoring.

I implemented this a year ago,
https://github.com/aetilley/pcfg

and I'd be happy to re-write it inside NLTK if people think it would be worthwhile.

I understand many of the other bottom-up- / chart - parsers tend to perform better than CKY, but I believe CKY is often one of the first taught.

Just a thought.

[stevenbird]

👍

[alvations]

@aetilley It's a good idea to have a working CKY wrapper in NLTK like earleychart.py but do note the various data structures that are already implemented in NLTK; use these structures to keep the code compact without maintaining multiple classes of the same function and remain consistency with other parser interfaces, esp. Tree, CFG, PCFG and ChartParser objects.

Additionally, there's a ViterbiParser inside nltk.parse.viterbi and ChartParser that you might find useful.

Create a PR when the code is ready and someone will help review through it =)

Looking forward to the PR!

[aetilley]

@alvations Great. Yes, I already noticed there's quite a bit done. Also it seems that there's already functionality for transforming an arbitrary CFG into Chomsky Normal Form, so I don't need to bring over that machinery.

I'll get on it.

[aetilley]

(Just started a job so this might get delayed a bit, but I'm definitely still interested.)

[aetilley]

Commented on #1884

Closing issue.