Структура данных алгоритма разбора CYK - PullRequest
Новая
       46

Структура данных алгоритма разбора CYK

0 голосов
/ 21 сентября 2018

Я читал алгоритм синтаксического анализа CYK, и я не понимаю одну структуру данных, которая представляет собой P [M, i, j] = новое дерево (M, i, j, ноль, ноль, ноль, 0,0);Как мне реализовать этот вид массива в Java?Алгоритм выглядит следующим образом: 

    class Tree {  
    NonTerm phrase %  The Non-terminal
    int startPhrase, int endPhrase; % indices of starting and ending word
    String word;   %  If a leaf, then the word 
    Tree left;     
    Tree right;    
    double prob;   
  }

    function CYK-PARSE(sentence,grammar) return P, a chart. {

1. N = length(sentence);
2. for (i = 1 to N) {
3.   word = sentence[i];
4.    for (each rule  "POS --> Word [prob]" in the grammar) 
5.       P[POS,i,i] = new Tree(POS,i,i,word,null,null,prob);
6.    }                           % endfor line 2.

7. for (length = 2 to N)          % length = length of phrase
8.   for (i = 1 to N+1-length) {  % i == start of phrase
9.     j = i+length-1;            % j == end of phrase
10.    for (each NonTerm M)  {
11.        P[M,i,j] = new Tree(M,i,j,null,null,null,0.0);
12.        for (k = i to j-1)    % k = end of first subphrase
13.            for (each rule "M -> Y,Z [prob]" in the grammar) {
14.                newProb = P[Y,i,k].prob * P[Z,k+1,j].prob * prob;
15.                if (newProb > P[M,i,j].prob) {
16.                   P[M,i,j].left = P[Y,i,k];
17.                   P[M,i,j].right = P[Z,k+1,j];
18.                   P[M,i,j].prob = newProb;
19.                }  % endif line 15 
20.            }      % endfor line 13
21.      }            % endfor line 10
22.    }              % endfor line 8

23. return P;
24. }  % end CYK-PARSE.

Он говорит, что «Основная структура данных в процедуре - это диаграмма, которая представляет собой массив P [M, I, J]. M индексируется на нетерминальной, I и J переходят от 1 к N (длина предложения). P [M, I, J] - это узел с NonTerm == M, startPhrase == I и endPhrase == J. «Я неполучить, что такое диаграмма.Если бы я реализовал это на Java, какую структуру данных я бы использовал для этого P [M, i, j], который содержит объекты Tree.

...