Skip to content

Instantly share code, notes, and snippets.

@chokkan
Created October 24, 2012 17:12
Show Gist options
  • Save chokkan/3947395 to your computer and use it in GitHub Desktop.
Save chokkan/3947395 to your computer and use it in GitHub Desktop.
Probabilistic Cocke-Kasami-Younger (PCKY) algorithm
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'))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment