Реализация алгоритма CYK - PullRequest
Новая
       43

Реализация алгоритма CYK

0 голосов
/ 22 октября 2018

Я пытаюсь реализовать псевдокод CYK, предоставленный wikipedia .Введенное мной в качестве примера предложение должно выводить True, однако выводит false.Я думаю, что у меня возникают проблемы с индексацией, учитывая, что приведенный пример начинается с 1.

Код: 

def is_in_language(self, tokens):
    n = len(tokens)
    rules = self.grammar.lhs_to_rules
    table = defaultdict(lambda: defaultdict(dict))
    #Initialize dictionary table[row][column][nonterminal r] = boolean
    for row in range(n+1):
        for col in range(n+1):
            for r in rules:
                table[row][col][r] = False

    for i in range(n):
        nonTerminalList = self.grammar.rhs_to_rules[(tokens[i],)]
        print(nonTerminalList)
        for nonTerminal in nonTerminalList:
            (r,right,prob) = nonTerminal
            table[0][i][r] =  True


    for l in range(2,n+1):
        for s in range(n-l+1):
            for p in range(l-1+1):
                for B in rules:
                    for C in rules:
                        AList = self.grammar.rhs_to_rules[B,C]
                        if(len(AList) > 0):
                            for A in AList:
                                (leftA, rightBC, prob) = A


                                try:
                                    if(table[p][s][B] and table[l-p][s+p][C]):
                                        table[l][s][leftA] = True
                                except:
                                    pass

    print(table[n][0][self.grammar.startsymbol])
    return table
...