Debian Codegraph @

scripts/apertium-editdist

raw
1 #!/usr/bin/python3
2
3 # see apertium-editdist --help for usage
4
5 import sys
6 import struct
7 import argparse
8
9 description_string = "Produce an edit distance transducer in ATT format."
10
11 epilog_string = """
12 For the default case, all the desired transitions are generated with weight 1.0.
13
14 The specification file should be in the following format:
15 * First, an (optional) list of tokens separated by newlines
16 All transitions involving these tokens that are otherwise unspecified
17 are generated with weight 1.0. Symbol weights can be specified by appending
18 a tab and a weight to the symbol. Transitions involving such a symbol
19 will have the user-specified weight added to it.
20 * If you want to exclude symbols that may be induced from a transducer,
21 add a leading ~ character to that line.
22 * If you want to specify transitions, insert a line with the content "@@"
23 (without the quotes)
24 * In the following lines, specified transitions with the form
25 FROM <TAB> TO <TAB> WEIGHT
26 where FROM is the source token, TO is the destination token and WEIGHT is
27 a nonnegative floating point number specifying the weight. By default,
28 if only one transition involving FROM and TO is specified, the same WEIGHT
29 will be used to specify the transition TO -> FROM (assuming that both are
30 listed in the list of tokens).
31 * If the command line option to generate swaps is set, you can also specify swap
32 weights with
33 FROM,TO <TAB> TO,FROM <TAB> WEIGHT
34 Again, unspecified swaps will be generated automatically with weight 1.0.
35 * Lines starting with ## are comments.
36
37 with d for distance and S for size of alphabet plus one
38 (for epsilon), expected output is a transducer in ATT format with
39 * Swapless:
40 ** d + 1 states
41 ** d*(S^2 + S - 1) transitions
42 * Swapful:
43 ** d*(S^2 - 3S + 3) + 1 states
44 ** d*(3S^2 - 5S + 3) transitions
45 """
46
47 def maketrans(from_st, to_st, from_sy, to_sy, weight):
48 return "{0}\t{1}\t{2}\t{3}\t{4}".format(from_st, to_st, from_sy, to_sy, weight)
49
50 class Transducer:
51 def __init__(self, dist, other, epsilon, swap, elim):
52 self.distance = dist
53 self.alphabet = {}
54 self.exclusions = set()
55 self.substitutions = {}
56 self.swaps = {}
57 self.should_swap = swap
58 self.should_elim = elim
59 self.other = other
60 self.epsilon = epsilon
61 self.swapstate = self.distance + 1
62 self.skipstate = self.swapstate + 1
63 self.transitions = []
64
65 def read_input_file(self, fname):
66 def parse_error(err, line):
67 nonlocal fname
68 sys.stderr.write('Syntax error on line %s of %s: %s.\n' % (fname, line, err))
69 sys.exit(1)
70 with open(fname) as fin:
71 in_alpha = True
72 for i, line_ in enumerate(fin, 1):
73 line = line_.strip()
74 if not line or line.startswith('##'):
75 continue
76 if in_alpha:
77 if line == '@@':
78 in_alpha = False
79 elif len(line) > 1 and line[0] == '~':
80 self.exclusions.add(line[1:].strip())
81 continue
82 elif '\t' in line:
83 if line.count('\t') > 1:
84 parse_error('Too many tabs', i)
85 symbol, weight = line.split('\t')
86 try:
87 self.alphabet[symbol] = float(weight)
88 except:
89 parse_error('Unable to parse weight', i)
90 else:
91 self.alphabet[line] = 0.0
92 else:
93 if line.count('\t') > 2 or line.count('\t') == 1:
94 parse_error('Wrong number of tabs, expected 3 tab-separated columns', i)
95 elif line.count('\t') == 0:
96 parse_error('Substitutions and swaps must be tab-separated', i)
97 l, r, w = line.split('\t')
98 weight = 0.0
99 try:
100 weight = float(w)
101 except:
102 parse_error('Unable to parse weight', i)
103 if ',' in line:
104 frompair = tuple(l.split(','))
105 topair = tuple(r.split(','))
106 if not (len(frompair) == len(topair) == 2):
107 parse_error('Swap-specification has wrong number of comma separators', i)
108 self.swaps.setdefault((frompair, topair), weight)
109 else:
110 self.substitutions.setdefault((l, r), weight)
111
112 def read_optimized_lookup_alphabet(self, fname):
113 with open(fname, "rb") as fin:
114 byt = fin.read(5)
115 if byt == b"HFST\0":
116 # just ignore any hfst3 header
117 header_length = struct.unpack_from("<H", fin.read(3), 0)[0]
118 fin.read(header_length)
119 # hopefully there's nothing surprising in here
120 byt = fin.read(56)
121 else:
122 byt += fin.read(56 - 5)
123 symbol_count = struct.unpack_from("<H", byt, 2)[0]
124 for n in range(symbol_count):
125 s = fin.read(1)
126 while s[-1] != 0:
127 s += fin.read(1)
128 sym = s[:-1].decode('utf-8')
129 if len(sym) != 1:
130 sys.stderr.write("Ignored symbol " + sym + "\n")
131 elif not sym.isspace() and sym not in self.exclusions:
132 self.alphabet.setdefault(sym, 0.0)
133
134 def extend_alphabet(self, alpha):
135 for c in alpha:
136 if c not in self.exclusions:
137 self.alphabet.setdefault(c, 0.0)
138
139 def clean_alphabet(self):
140 # depending on what order read_input_file(), extend_alphabet()
141 # and read_optimzed_lookup_alphabet() are called in, symbols
142 # might get included in the alphabet which should be excluded
143 # so remove those
144 for s in self.exclusions:
145 if s in self.alphabet:
146 del self.alphabet[s]
147
148 def generate(self):
149 # for substitutions and swaps that weren't defined by the user,
150 # generate standard subs and swaps
151 self.substitutions.setdefault((self.other, self.epsilon), 1.0)
152 for symbol in self.alphabet:
153 w = 1.0 + self.alphabet[symbol]
154 self.substitutions.setdefault((self.other, symbol), w)
155 self.substitutions.setdefault((self.epsilon, symbol), w)
156 self.substitutions.setdefault((symbol, self.epsilon), w)
157 for symbol2 in self.alphabet:
158 if symbol == symbol2: continue
159 w += self.alphabet[symbol2]
160 p12 = (symbol, symbol2)
161 p21 = (symbol2, symbol)
162 self.swaps.setdefault((p12, p21), self.swaps.get((p21, p12), w))
163 self.substitutions.setdefault(p12, self.substitutions.get(p21, w))
164
165 def next_special(self, state):
166 if state == "swap":
167 self.swapstate += 1
168 while self.swapstate == self.skipstate:
169 self.swapstate += 1
170 elif state == "skip":
171 self.skipstate += 1
172 while self.skipstate == self.swapstate:
173 self.skipstate += 1
174 else:
175 raise Exception
176
177 def make_identities(self, state, nextstate = None):
178 if nextstate is None:
179 nextstate = state
180 ret = []
181 for symbol in self.alphabet:
182 if symbol not in (self.epsilon, self.other):
183 ret.append(maketrans(state, nextstate, symbol, symbol, 0.0))
184 return ret
185
186 def make_swaps(self, state, nextstate = None):
187 if nextstate is None:
188 nextstate = state + 1
189 ret = []
190 if self.should_swap:
191 for swap in self.swaps:
192 ret.append(maketrans(state, self.swapstate, swap[0][0], swap[0][1], self.swaps[swap]))
193 ret.append(maketrans(self.swapstate, nextstate, swap[1][0], swap[1][1], 0.0))
194 self.next_special("swap")
195 return ret
196
197 # for substitutions, we try to eliminate redundancies by refusing to do
198 # deletion right after insertion and insertion right after deletion
199 def make_substitutions(self, state, nextstate = None):
200 if nextstate is None:
201 nextstate = state + 1
202 ret = []
203 for sub in self.substitutions:
204 if (nextstate + 1 >= self.distance) or not self.should_elim:
205 ret.append(maketrans(state, nextstate, sub[0], sub[1], self.substitutions[sub]))
206 elif sub[1] is self.epsilon: # deletion
207 ret.append(maketrans(state, self.skipstate, sub[0], sub[1], self.substitutions[sub]))
208 ret += self.make_identities(self.skipstate, nextstate)
209 ret += self.make_swaps(self.skipstate, nextstate + 1)
210 for sub2 in self.substitutions:
211 # after deletion, refuse to do insertion
212 if sub2[0] != self.epsilon:
213 ret.append(maketrans(self.skipstate, nextstate + 1, sub2[0], sub2[1], self.substitutions[sub2]))
214 self.next_special("skip")
215 elif sub[0] is self.epsilon: # insertion
216 ret.append(maketrans(state, self.skipstate, sub[0], sub[1], self.substitutions[sub]))
217 ret += self.make_identities(self.skipstate, nextstate)
218 ret += self.make_swaps(self.skipstate, nextstate + 1)
219 for sub2 in self.substitutions:
220 # after insertion, refuse to do deletion
221 if sub2[1] != self.epsilon:
222 ret.append(maketrans(self.skipstate, nextstate + 1, sub2[0], sub2[1], self.substitutions[sub2]))
223 self.next_special("skip")
224 else:
225 ret.append(maketrans(state, nextstate, sub[0], sub[1], self.substitutions[sub]))
226 return ret
227
228 def make_transitions(self):
229 for state in range(self.distance):
230 self.transitions.append(str(state + 1) + "\t0.0") # final states
231 self.transitions += self.make_identities(state)
232 self.transitions += self.make_substitutions(state)
233 self.transitions += self.make_swaps(state)
234 self.transitions += self.make_identities(self.distance)
235
236 def verbose_report(self):
237 template = '''
238 {states} states and {trans} transitions written for
239 distance {dist} and base alphabet size {alpha_size}
240
241 The alphabet was:
242 {alpha}
243 The exclusions were:
244 {excl}
245 '''
246 alpha = ' '.join('%s:%s' % (s, w) for s, w in self.alphabet.items())
247 excl = ' '.join(self.exclusions)
248 report = template.format(states=max(self.skipstate, self.swapstate),
249 trans=len(self.transitions),
250 dist=self.distance,
251 alpha_size=len(self.alphabet),
252 alpha=alpha,
253 excl=excl)
254 sys.stderr.write(report)
255
256 def main():
257 parser = argparse.ArgumentParser(description=description_string,
258 epilog=epilog_string,
259 formatter_class=argparse.RawDescriptionHelpFormatter)
260 parser.add_argument('-d', '--distance', type=int, metavar='DIST', default=1,
261 help='edit depth, default is 1')
262 parser.add_argument('-e', '--epsilon', default='@0@', metavar='EPS',
263 help='epsilon symbol, default is @0@')
264 parser.add_argument('--no-elim', action='store_true',
265 help="don't reduce elimination")
266 parser.add_argument('-s', '--swap', action='store_true',
267 help='generate swaps in addition to insertions and deletions')
268 parser.add_argument('-v', '--verbose', action='store_true',
269 help='print summary to stderr')
270 alpha = parser.add_argument_group('Alphabet', 'Specify the alphabet of the transducer (these may be combined and repeated)')
271 alpha.add_argument('-i', '--input', dest='inputfile', metavar='INPUT',
272 action='append', default=[],
273 help='specification file in edit-distance syntax')
274 alpha.add_argument('-a', '--alphabet', dest='alphabetfile', metavar='TRANS',
275 action='append', default=[],
276 help='optimized-lookup format transducer to read alphabet from (ignoring multi-character symbols)')
277 alpha.add_argument('alphabet_string', nargs='*',
278 help='the alphabet as a string on the command line')
279 options = parser.parse_args()
280
281 transducer = Transducer(options.distance, '@_UNKNOWN_SYMBOL_@', options.epsilon, options.swap, not options.no_elim)
282
283 if not options.inputfile and not options.alphabet_string and not options.alphabetfile:
284 parser.error('Must provide an alphabet')
285 for fl in options.inputfile:
286 transducer.read_input_file(fl)
287 for s in options.alphabet_string:
288 transducer.extend_alphabet(s)
289 for fl in options.alphabetfile:
290 transducer.read_optimized_lookup_alphabet(fl)
291 transducer.clean_alphabet()
292
293 transducer.generate()
294 transducer.make_transitions()
295 for transition in transducer.transitions:
296 print(transition)
297
298 if options.verbose:
299 transducer.verbose_report()
300
301 if __name__ == '__main__':
302 main()