Die Wikipedia Artikel zum Cocke-Younger-Kasami-Algorithmu kann man vergessen. Man kapiert nichts. Hab auf youtube ein 15min Video [1] von Benny Neugebauer dazu gefunden. Wunderbar, alles gleich verstanden :)
Hab ihn mal schnell in C++ implementiert. Hier die Hauptschleife:
/*
Für j = 2 ... n
Für i = 1 ... n - j + 1
Für k = 1 ... j - 1
Setze V_{i,j} := V_{i,j} + { l | \exists B,C in N ((l -> BC) in P and B in V_{i,k} and C in V_{i + k, j - k}) \}
Falls S \in V_{1,n}, stoppe und gib "w wird von G erzeugt" aus
Stoppe und gib "w wird nicht von G erzeugt" aus
*/
for(size_t row=1; row < n; row++) {
// cout << "row " << row << "\n";
for(size_t col=0; col < n-row; col++) {
// cout << "col " << col << "\n";
for(size_t k=0; k < row; k++) {
const auto &e1 = V.at(k, col);
const auto &e2 = V.at(row-k-1, col+k+1);
for(size_t i=0; i < e1.size(); i++) {
for(size_t j=0; j < e2.size(); j++) {
// cout << "Check " << e1.at(i) << " " << e2.at(j) << "\n";
const Production::String toTest({e1.at(i), e2.at(j)});
for(const Production& p : P) {
if(p.right == toTest) {
// uniq append
if(contains(V.at(row, col), p.left) == false) {
V.at(row, col).push_back(p.left);
}
}
}
}
}
}
}
}
Für jeden Matrixeintrag in der oberen linken Dreiecksmatrix:
Für jeden Eintrag oberhalt in der Spalte und Diagonal nach oben:
Schaue nach ob die Konkatenation der beiden Einträge in der rechten Seite der Produktionsregeln vorkommen:
Ja) Linke Seite der Produktion in die Matrix eintragen.
Steht am Ende in der letzten Zeile, erste Spalte das Startsymbol, dann kann das Wort erkannt werden.
[1] https://www.youtube.com/watch?v=JugIgxUyA4Q