1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
# cn.py
# Chris Dyer <redpony@umd.edu>
# Copyright (c) 2006 University of Maryland.
# vim:tabstop=4:autoindent:expandtab
import sys
import math
import sym
import log
import sgml
epsilon = sym.fromstring('*EPS*');
class CNStats(object):
def __init__(self):
self.read = 0
self.colls = 0
self.words = 0
def collect(self, cn):
self.read += 1
self.colls += cn.get_length()
for col in cn.columns:
self.words += len(col)
def __str__(self):
return "confusion net statistics:\n succ. read: %d\n columns: %d\n words: %d\n avg. words/column:\t%f\n avg. cols/sent:\t%f\n\n" % (self.read, self.colls, self.words, float(self.words)/float(self.colls), float(self.colls)/float(self.read))
class ConfusionNet(object):
def __init__(self, sent):
object.__init__(self)
if (len(sent.words) == 0):
self.columns = ()
return # empty line, it happens
line = sent.words[0]
if (line.startswith("(((")):
if (len(sent.words) > 1):
log.write("Bad sentence: %s\n" % (line))
assert(len(sent.words) == 1) # make sure there are no spaces in your confusion nets!
line = "((('<s>',1.0,1),),"+line[1:len(line)-1]+"(('</s>',1.0,1),))"
cols = eval(line)
res = []
for col in cols:
x = []
for alt in col:
costs = alt[1]
if (type(costs) != type((1,2))):
costs=(float(costs),)
j=[]
for c in costs:
j.append(float(c))
cost = tuple(j)
spanlen = 1
if (len(alt) == 3):
spanlen = alt[2]
x.append((sym.fromstring(alt[0],terminal=True), None, spanlen))
res.append(tuple(x))
self.columns = tuple(res)
else: # convert a string of input into a CN
res = [];
res.append(((sym.fromstring('<s>',terminal=True), None, 1), ))
for word in sent.words:
res.append(((sym.fromstring(word,terminal=True), None, 1), )); # (alt=word, cost=0.0)
res.append(((sym.fromstring('</s>',terminal=True), None, 1), ))
self.columns = tuple(res)
def is_epsilon(self, position):
x = self.columns[position[0]][position[1]][0]
return x == epsilon
def compute_epsilon_run_length(self, cn_path):
if (len(cn_path) == 0):
return 0
x = len(cn_path) - 1
res = 0
''' -1 denotes a non-terminal '''
while (x >= 0 and cn_path[x][0] >= 0 and self.is_epsilon(cn_path[x])):
res += 1
x -= 1
return res
def compute_cn_cost(self, cn_path):
c = None
for (col, row) in cn_path:
if (col >= 0):
if c is None:
c = self.columns[col][row][1].clone()
else:
c += self.columns[col][row][1]
return c
def get_column(self, col):
return self.columns[col]
def get_length(self):
return len(self.columns)
def __str__(self):
r = "conf net: %d\n" % (len(self.columns),)
i = 0
for col in self.columns:
r += "%d -- " % i
i += 1
for alternative in col:
r += "(%s, %s, %s) " % (sym.tostring(alternative[0]), alternative[1], alternative[2])
r += "\n"
return r
def listdown(_columns, col = 0):
# output all the possible sentences out of the self lattice
# will be used by the "dumb" adaptation of lattice decoding with suffix array
result = []
for entry in _columns[col]:
if col+entry[2]+1<=len(_columns) :
for suffix in self.listdown(_columns,col+entry[2]):
result.append(entry[0]+' '+suffix)
#result.append(entry[0]+' '+suffix)
else:
result.append(entry[0])
#result.append(entry[0])
return result
def next(self,_columns,curr_idx, min_dist=1):
# can be used only when prev_id is defined
result = []
#print "curr_idx=%i\n" % curr_idx
if curr_idx+min_dist >= len(_columns):
return result
for alt_idx in xrange(len(_columns[curr_idx])):
alt = _columns[curr_idx][alt_idx]
#print "checking %i alternative : " % alt_idx
#print "%s %f %i\n" % (alt[0],alt[1],alt[2])
#print alt
if alt[2]<min_dist:
#print "recursive next(%i, %i, %i)\n" % (curr_idx,alt_idx,min_dist-alt[2])
result.extend(self.next(_columns,curr_idx+alt[2],min_dist-alt[2]))
elif curr_idx+alt[2]<len(_columns):
#print "adding because the skip %i doesn't go beyong the length\n" % alt[2]
result.append(curr_idx+alt[2])
return set(result)
#file = open(sys.argv[1], "rb")
#sent = sgml.process_sgml_line(file.read())
#print sent
#cn = ConfusionNet(sent)
#print cn
#results = cn.listdown()
#for result in results:
# print sym.tostring(result)
#print cn.next(0);
#print cn.next(1);
#print cn.next(2);
#print cn.next(3);
#print cn
#cn = ConfusionNet()
#k = 0
#while (cn.read(file)):
# print cn
#print cn.stats
|
