Changeset 253 for liacs/TPFL2010/assignment3/cyk.py
- Timestamp:
- Dec 15, 2010, 4:42:17 PM (14 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
liacs/TPFL2010/assignment3/cyk.py
r252 r253 3 3 # Very nasty hacks to make python algoritm look similar to pg.142 CYK algoritm. 4 4 # 5 from pprint import pprint 5 6 6 7 … … 22 23 n = len(w) 23 24 r = [[[]]*(n+1) for x in irange(0,n)] 25 cyk = dict(); 24 26 25 27 28 for k in cnf.keys(): 29 for i in irange(1,n): 30 for j in irange(1,n): 31 cyk[(k,i,j)] = [] 26 32 27 33 28 def printr(): 34 def print_r(): 35 print ''' 36 \\begin{table}[htbp] 37 \\center 38 \\begin{tabular}{|c||%s} 39 \\hline 40 ''' % ('c|'*n) 29 41 print 'i\\textbackslash j &', 30 42 for i in irange(1,n): 31 print "%-10s &" % i, 43 print "%-10s" % i, 44 if i != n: 45 print "&", 32 46 print "\\\\ \\hline \\hline" 33 47 … … 37 51 for j in irange(1,n): 38 52 if r[i][j] == [None]: 39 item = "@" 40 else: 41 item = ",".join(r[i][j]), 42 print "%-10s &" % item, 53 item = "$\\emptyset$", 54 else: 55 item = '' 56 for k in r[i][j]: 57 c = from_cyk(k,i,j) 58 if c: 59 item += "%s: %s \\\\" % (k, c) 60 else: 61 item += "%s \\\\" % k 62 63 print "\\begin{tabular}{l}", 64 print "%-10s \\end{tabular}" % item, 65 if j != n: 66 print "&", 43 67 print "\\\\ \\hline" 68 print ''' 69 \\end{tabular} 70 \\label{tb:cyk} 71 \\caption{$CYK(L(G),babbbab)$. Algoritme in \cite{JS2009}[pg.~142]} 72 \\end{table} 73 ''' 74 44 75 45 76 def to_r(i,j,k): … … 52 83 def from_r(i,j): 53 84 return r[i][j] 85 86 def to_cyk(A,i,j,B): 87 cyk[(A,i,j)] += [B] 88 89 def from_cyk(A,i,j): 90 r = cyk[(A,i,j)] 91 if not r: 92 return None 93 else: 94 return ",".join([str(x) for x in r]) 95 54 96 55 97 def letter(i): … … 74 116 if x[0] in from_r(i,k) and x[1] in from_r(k+1,j): 75 117 to_r(i,j,y) 118 to_cyk(y,i,j,(x[0],x[1],k)) 76 119 77 120 78 printr() 121 print_r() 122 #pprint(cyk)
Note:
See TracChangeset
for help on using the changeset viewer.