For the following algorithm, I was wondering what is a chart and what kind of ar
ID: 3751310 • Letter: F
Question
For the following algorithm, I was wondering what is a chart and what kind of array would hold such objects? It says it P[M, i, j], but M is a Nonterm, and i and j are integers. Is it a 3d array? If so how would I declare it in Java? Please help me understand that part !
A node of the parse tree is an object with the following data fields (in Java-esque notation) claas Tree i NonTerm phrase % The Non-terminal int startPhrase, int endPhrase; % indices of starting and ending word String word; % If a leaf, then the ord Tree lefti Tree right; double prob; The fields left, right, and prob are the left-hand child, right-hand child and probability in the best parse found so far for this particular non-terminal from this start to this end (e.g. the best parse for an NP from word 3 to word 6). Note that the probability on a node is_not the probability of this parse tree given the phrase, it is the probability of the parse tree including the choice of word given the non-terminal at the root. However for any particular non-terminal and choice of sentence those two probabilities are proportional, by Bayes' rule. which we will come to later in the course The main data structure in the procedure is a chart which is an array P[M,IJ. M is indexed on the non-terminal, I and J go from 1 to N (the length of the sentence). P[MIJ is the node with NonTerm- M, startPhrase-I and endPhraseJ. Note that this uses 1-based indexing, like the textbook. Eunction CYK-PARSE (sentence,grammar return ?, a chart. ( 1. N-length (sentence)i 2" for (i = 1 to N) { 3 word-sentenceli]i for (each rule "POS> Word (probl' in the grammar) Pf POS , , l Tree { P0s, , ¡ , word, null , null , prob) ; = new endfor line 2. % length- length of phrase % j end of phraBe 7. for (length2 to N) 8. for (i- 1 to N+1-length) { % --start of phrase j = for i+length-1; (each NonTerm M) PIN,i,j)-ne Tree(M,i,j,null,null, nu1l,0.a); for {k-i to J-1) k- end of first subphrase 10. 12 13 14 15. for (each rule "M -> Y, 2 Iprob]" in the gramar) newProb- PIY, , k.prob * PIZ.k+1, j].prob if (newProb > PIM,i.j] prob) prob ; * PIM,i,j).left-PIY, i,k P[M,i,j].right2,k+1,j1 P[X, , j].prob-newProb; 17 18 19 20 21 endif line 15 endfor line 13 % endfor line 10 % endfor line 8 23. return P; 24.> * end CYK-PARSE The value returned in PT"S'.1N] is the root of the most probable parseExplanation / Answer
Yes, looks like 3D array where P[M, i, j] means M is copied at every ith row and jth column of the P. Declaring 3D array in java is same as 2D array. Consider array below:
Where M will be copied twice which is the third dimension of the array.