Probabilistic Cocke-Kasami-Younger (PCKY) algorithm

pcky.py

import collections
import math

def build(CNF):
    G = collections.defaultdict(list)
    for left, right, p in CNF:
        G[right].append((left, math.log(p)))
    return G

def show_cell(T, i, j):
    for x, (p, l, r) in T[i][j].iteritems():
        print "[%d,%d,%s]=%g: %r and %r" % (i, j, x, math.exp(p), l, r)

def pcky(G, W):
    T = [[{} for j in range(len(W)+1)] for i in range(len(W))]
    for j in range(1, len(W)+1):
        for left, p in G.get(W[j-1], {}):
            T[j-1][j][left] = (p, (W[j-1], j, j), (W[j-1], j, j))
        show_cell(T, j-1, j)
        for i in range(j-2, -1, -1):
            for k in range(i+1, j):
                for x, (px, lx, rx) in T[i][k].iteritems():
                    for y, (py, ly, ry) in T[k][j].iteritems():
                        for left, p in G.get((x, y), {}):
                            pnew = px + py + p
                            if left not in T[i][j] or T[i][j][left][0] < pnew:
                                T[i][j][left] = (pnew, (x, i, k), (y, k, j))
            show_cell(T, i, j)
    return T

if __name__ == '__main__':
    PCNF = (
        ('S', ('NP','VP'), 0.8),
        ('S', ('VP','NP'), 0.2),
        ('VP', 'time', 0.01),
        ('VP', 'flies', 0.04),
        ('VP', 'like', 0.04),
        ('VP', 'arrow', 0.01),
        ('VP', ('Verb','NP'), 0.5),
        ('VP', ('VP','PP'), 0.4),
        ('NP', 'time', 0.04),
        ('NP', 'flies', 0.02),
        ('NP', 'arrow', 0.04),
        ('NP', ('Det','NP'), 0.4),
        ('NP', ('Noun','NP'), 0.3),
        ('NP', ('NP','PP'), 0.2),
        ('PP', ('Preposition','NP'), 1.0),
        ('Noun', 'time', 0.4),
        ('Noun', 'flies', 0.2),
        ('Noun', 'arrow', 0.4),
        ('Verb', 'time', 0.1),
        ('Verb', 'flies', 0.4),
        ('Verb', 'like', 0.4),
        ('Verb', 'arrow', 0.1),
        ('Preposition', 'like', 1.0),
        ('Det', 'an', 1.0),
    )
    G = build(PCNF)
    T = pcky(G, ('time', 'flies', 'like', 'an', 'arrow'))