aima.core.nlp.parsing

Class CYK

java.lang.Object

aima.core.nlp.parsing.CYK

public class CYK
extends java.lang.Object

Artificial Intelligence A Modern Approach (3rd Edition): page 894.

 function CYK-PARSE(words, grammar) returns P, a table of probabilities
   N <- LENGTH(words)
   M <- the number of nonterminal symbols in grammar
   P <- an array of size[M,N,N], initially all 0
   /* Insert Lexical rules for each word *\
   for i = 1 to N do
        for each rule of form( X -> wordsi[p]) do
                P[X,i,1] <- p
   /* Combine first and second parts of right-hand sides of rules, from short to long *\
   for length = 2 to N do
        for start = 1 to N - length + 1 do
                for len1 = 1 to N -1 do 
                        len2 <- length - len1
                for each rule of the form( X -> Y Z [p] ) do
                        p[X, start, length] <- MAX(P[X, start, length],
                                                P[Y, start, len1] * P[Z, start + len1, len2] * p)
   return P
 

Figure 23.5 The CYK algorithm for parsing. Given a sequence of words, it finds the most probable derivation for the whole sequence and for each subsequence. It returns the whole table, P, in which an entry P[X, start, len] is the probability of the most probable X of length len starting at position start. If there is no X of that size at that location, the probability is 0.

Author:

Jonathon Belotti (thundergolfer)

Constructor Summary

Constructors

Constructor and Description
CYK()

Method Summary

Modifier and Type	Method and Description
java.util.ArrayList<java.lang.String>	getMostProbableDerivation(float[][][] probTable, ProbUnrestrictedGrammar g) The probability table get's us halfway there, but this method can provide the derivation chain that most probably derives the words provided to the parser.
int	length(java.util.List<java.lang.String> ls) Simple function to make algorithm more closely resemble pseudocode
float[][][]	parse(java.util.List<java.lang.String> words, ProbCNFGrammar grammar)
void	printProbTable(float[][][] probTable, java.util.List<java.lang.String> words, ProbUnrestrictedGrammar g) Print out the probability table produced by the CYK Algorithm

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

CYK

public CYK()

Method Detail

parse

public float[][][] parse(java.util.List<java.lang.String> words,
                         ProbCNFGrammar grammar)

length

public int length(java.util.List<java.lang.String> ls)

Simple function to make algorithm more closely resemble pseudocode

Parameters:

ls -

Returns:

the length of the list

printProbTable

public void printProbTable(float[][][] probTable,
                           java.util.List<java.lang.String> words,
                           ProbUnrestrictedGrammar g)

Print out the probability table produced by the CYK Algorithm

Parameters:

probTable -

words -

g -

getMostProbableDerivation

public java.util.ArrayList<java.lang.String> getMostProbableDerivation(float[][][] probTable,
                                                                       ProbUnrestrictedGrammar g)

The probability table get's us halfway there, but this method can provide the derivation chain that most probably derives the words provided to the parser.

Parameters:

probTable -

g -

Returns: