| 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() |