- Forum
- General C++ Programming
- CYK Algorhythm
CYK Algorhythm
Hello, I'm working with the CYK Algorhytm problem. Here's a link where the problem is explained better:
http://web.cs.ucdavis.edu/~rogaway/classes/120/winter12/CYK.pdf
I find myself lost when it comes to contructing the triangular matrix. I believe i'll have to contsruct the bottom row first, and then use some algorhythm to complete the rest, but I just can't see a way to do it.
To solve this problem I thought I could make an ADT called "Grammar", which would read a file and get it's data. And then another ADT called "CYK Matrix", which w would work with "Grammar" and the "w" chain to contruct the matrix and then read it to answer the problem.... I'm still unsure about which structures to use for the information i have to work with. I don't have much knowledge about C++ and coding,,,i know how to use maps,vectors,set,matrix,trees,etc... what would you reccomend to use for this problem ? And if you have any helpful links or anything please share !
Thank you.
http://web.cs.ucdavis.edu/~rogaway/classes/120/winter12/CYK.pdf
I find myself lost when it comes to contructing the triangular matrix. I believe i'll have to contsruct the bottom row first, and then use some algorhythm to complete the rest, but I just can't see a way to do it.
To solve this problem I thought I could make an ADT called "Grammar", which would read a file and get it's data. And then another ADT called "CYK Matrix", which w would work with "Grammar" and the "w" chain to contruct the matrix and then read it to answer the problem.... I'm still unsure about which structures to use for the information i have to work with. I don't have much knowledge about C++ and coding,,,i know how to use maps,vectors,set,matrix,trees,etc... what would you reccomend to use for this problem ? And if you have any helpful links or anything please share !
Thank you.
Last edited on
Bumpity bump.
I'm pretty uncertain about how to go about this at the moment (and probably in the future, although I'll try my hand at it tomorrow), but this is an interesting question to me and I'd love to see this fleshed out by people more qualified than myself.
References I've found so far:
Implementations: http://log-cse.blogspot.com/2014/01/cyk-algorithm-implementation.html
https://github.com/agorenst/cyk
An imperfect implementation found on SO (sitting in unanswered for 1+year): http://stackoverflow.com/questions/34113601/cyk-algorithm-implementation-c
A YT video I came across using the exact grammar and same test case (baaba) outlined in the powerpoint @MatyDN05 linked to: https://www.youtube.com/watch?v=VTH1k-xiswM
I'm pretty uncertain about how to go about this at the moment (and probably in the future, although I'll try my hand at it tomorrow), but this is an interesting question to me and I'd love to see this fleshed out by people more qualified than myself.
References I've found so far:
Implementations: http://log-cse.blogspot.com/2014/01/cyk-algorithm-implementation.html
https://github.com/agorenst/cyk
An imperfect implementation found on SO (sitting in unanswered for 1+year): http://stackoverflow.com/questions/34113601/cyk-algorithm-implementation-c
A YT video I came across using the exact grammar and same test case (baaba) outlined in the powerpoint @MatyDN05 linked to: https://www.youtube.com/watch?v=VTH1k-xiswM
Last edited on
@edge6768 I've checked those implementations before (I think they're the same), they work great but I guess my coding level doesn't allow me to understand . I found another code in here : http://homepages.dcc.ufmg.br/~nvieira/cursos/ftc/a14s1/tp2.pdf , it looks nice but I don't understand why they're using a 3-dimensional matrix. I also came across that video and it was the one who helped the most to understand how the algorhythm work !!!
Thank you very much !!
Thank you very much !!
Topic archived. No new replies allowed.