| 1 |
# Original Algorithm: |
| 2 |
# By Steve Hanov, 2011. Released to the public domain. |
| 3 |
# Please see http://stevehanov.ca/blog/index.php?id=115 for the accompanying article. |
| 4 |
# |
| 5 |
# Adapted for PyPy/CPython by Carl Friedrich Bolz-Tereick |
| 6 |
# |
| 7 |
# Based on Daciuk, Jan, et al. "Incremental construction of minimal acyclic finite-state automata." |
| 8 |
# Computational linguistics 26.1 (2000): 3-16. |
| 9 |
# |
| 10 |
# Updated 2014 to use DAWG as a mapping; see |
| 11 |
# Kowaltowski, T.; CL. Lucchesi (1993), "Applications of finite automata representing large vocabularies", |
| 12 |
# Software-Practice and Experience 1993 |
| 13 |
|
| 14 |
from collections import defaultdict |
| 15 |
from functools import cached_property |
| 16 |
|
| 17 |
|
| 18 |
# This class represents a node in the directed acyclic word graph (DAWG). It |
| 19 |
# has a list of edges to other nodes. It has functions for testing whether it |
| 20 |
# is equivalent to another node. Nodes are equivalent if they have identical |
| 21 |
# edges, and each identical edge leads to identical states. The __hash__ and |
| 22 |
# __eq__ functions allow it to be used as a key in a python dictionary. |
| 23 |
|
| 24 |
|
| 25 |
class DawgNode: |
| 26 |
|
| 27 |
def __init__(self, dawg): |
| 28 |
self.id = dawg.next_id |
| 29 |
dawg.next_id += 1 |
| 30 |
self.final = False |
| 31 |
self.edges = {} |
| 32 |
|
| 33 |
self.linear_edges = None # later: list of (string, next_state) |
| 34 |
|
| 35 |
def __str__(self): |
| 36 |
if self.final: |
| 37 |
arr = ["1"] |
| 38 |
else: |
| 39 |
arr = ["0"] |
| 40 |
|
| 41 |
for (label, node) in sorted(self.edges.items()): |
| 42 |
arr.append(label) |
| 43 |
arr.append(str(node.id)) |
| 44 |
|
| 45 |
return "_".join(arr) |
| 46 |
__repr__ = __str__ |
| 47 |
|
| 48 |
def _as_tuple(self): |
| 49 |
edges = sorted(self.edges.items()) |
| 50 |
edge_tuple = tuple((label, node.id) for label, node in edges) |
| 51 |
return (self.final, edge_tuple) |
| 52 |
|
| 53 |
def __hash__(self): |
| 54 |
return hash(self._as_tuple()) |
| 55 |
|
| 56 |
def __eq__(self, other): |
| 57 |
return self._as_tuple() == other._as_tuple() |
| 58 |
|
| 59 |
@cached_property |
| 60 |
def num_reachable_linear(self): |
| 61 |
# returns the number of different paths to final nodes reachable from |
| 62 |
# this one |
| 63 |
|
| 64 |
count = 0 |
| 65 |
# staying at self counts as a path if self is final |
| 66 |
if self.final: |
| 67 |
count += 1 |
| 68 |
for label, node in self.linear_edges: |
| 69 |
count += node.num_reachable_linear |
| 70 |
|
| 71 |
return count |
| 72 |
|
| 73 |
|
| 74 |
class Dawg: |
| 75 |
def __init__(self): |
| 76 |
self.previous_word = "" |
| 77 |
self.next_id = 0 |
| 78 |
self.root = DawgNode(self) |
| 79 |
|
| 80 |
# Here is a list of nodes that have not been checked for duplication. |
| 81 |
self.unchecked_nodes = [] |
| 82 |
|
| 83 |
# To deduplicate, maintain a dictionary with |
| 84 |
# minimized_nodes[canonical_node] is canonical_node. |
| 85 |
# Based on __hash__ and __eq__, minimized_nodes[n] is the |
| 86 |
# canonical node equal to n. |
| 87 |
# In other words, self.minimized_nodes[x] == x for all nodes found in |
| 88 |
# the dict. |
| 89 |
self.minimized_nodes = {} |
| 90 |
|
| 91 |
# word: value mapping |
| 92 |
self.data = {} |
| 93 |
# value: word mapping |
| 94 |
self.inverse = {} |
| 95 |
|
| 96 |
def insert(self, word, value): |
| 97 |
if not all(0 <= ord(c) < 128 for c in word): |
| 98 |
raise ValueError("Use 7-bit ASCII characters only") |
| 99 |
if word <= self.previous_word: |
| 100 |
raise ValueError("Error: Words must be inserted in alphabetical order.") |
| 101 |
if value in self.inverse: |
| 102 |
raise ValueError(f"value {value} is duplicate, got it for word {self.inverse[value]} and now {word}") |
| 103 |
|
| 104 |
# find common prefix between word and previous word |
| 105 |
common_prefix = 0 |
| 106 |
for i in range(min(len(word), len(self.previous_word))): |
| 107 |
if word[i] != self.previous_word[i]: |
| 108 |
break |
| 109 |
common_prefix += 1 |
| 110 |
|
| 111 |
# Check the unchecked_nodes for redundant nodes, proceeding from last |
| 112 |
# one down to the common prefix size. Then truncate the list at that |
| 113 |
# point. |
| 114 |
self._minimize(common_prefix) |
| 115 |
|
| 116 |
self.data[word] = value |
| 117 |
self.inverse[value] = word |
| 118 |
|
| 119 |
# add the suffix, starting from the correct node mid-way through the |
| 120 |
# graph |
| 121 |
if len(self.unchecked_nodes) == 0: |
| 122 |
node = self.root |
| 123 |
else: |
| 124 |
node = self.unchecked_nodes[-1][2] |
| 125 |
|
| 126 |
for letter in word[common_prefix:]: |
| 127 |
next_node = DawgNode(self) |
| 128 |
node.edges[letter] = next_node |
| 129 |
self.unchecked_nodes.append((node, letter, next_node)) |
| 130 |
node = next_node |
| 131 |
|
| 132 |
node.final = True |
| 133 |
self.previous_word = word |
| 134 |
|
| 135 |
def finish(self): |
| 136 |
if not self.data: |
| 137 |
raise ValueError("need at least one word in the dawg") |
| 138 |
# minimize all unchecked_nodes |
| 139 |
self._minimize(0) |
| 140 |
|
| 141 |
self._linearize_edges() |
| 142 |
|
| 143 |
topoorder, linear_data, inverse = self._topological_order() |
| 144 |
return self.compute_packed(topoorder), linear_data, inverse |
| 145 |
|
| 146 |
def _minimize(self, down_to): |
| 147 |
# proceed from the leaf up to a certain point |
| 148 |
for i in range(len(self.unchecked_nodes) - 1, down_to - 1, -1): |
| 149 |
(parent, letter, child) = self.unchecked_nodes[i] |
| 150 |
if child in self.minimized_nodes: |
| 151 |
# replace the child with the previously encountered one |
| 152 |
parent.edges[letter] = self.minimized_nodes[child] |
| 153 |
else: |
| 154 |
# add the state to the minimized nodes. |
| 155 |
self.minimized_nodes[child] = child |
| 156 |
self.unchecked_nodes.pop() |
| 157 |
|
| 158 |
def _lookup(self, word): |
| 159 |
""" Return an integer 0 <= k < number of strings in dawg |
| 160 |
where word is the kth successful traversal of the dawg. """ |
| 161 |
node = self.root |
| 162 |
skipped = 0 # keep track of number of final nodes that we skipped |
| 163 |
index = 0 |
| 164 |
while index < len(word): |
| 165 |
for label, child in node.linear_edges: |
| 166 |
if word[index] == label[0]: |
| 167 |
if word[index:index + len(label)] == label: |
| 168 |
if node.final: |
| 169 |
skipped += 1 |
| 170 |
index += len(label) |
| 171 |
node = child |
| 172 |
break |
| 173 |
else: |
| 174 |
return None |
| 175 |
skipped += child.num_reachable_linear |
| 176 |
else: |
| 177 |
return None |
| 178 |
return skipped |
| 179 |
|
| 180 |
def enum_all_nodes(self): |
| 181 |
stack = [self.root] |
| 182 |
done = set() |
| 183 |
while stack: |
| 184 |
node = stack.pop() |
| 185 |
if node.id in done: |
| 186 |
continue |
| 187 |
yield node |
| 188 |
done.add(node.id) |
| 189 |
for label, child in sorted(node.edges.items()): |
| 190 |
stack.append(child) |
| 191 |
|
| 192 |
def prettyprint(self): |
| 193 |
for node in sorted(self.enum_all_nodes(), key=lambda e: e.id): |
| 194 |
s_final = " final" if node.final else "" |
| 195 |
print(f"{node.id}: ({node}) {s_final}") |
| 196 |
for label, child in sorted(node.edges.items()): |
| 197 |
print(f" {label} goto {child.id}") |
| 198 |
|
| 199 |
def _inverse_lookup(self, number): |
| 200 |
assert 0, "not working in the current form, but keep it as the pure python version of compact lookup" |
| 201 |
result = [] |
| 202 |
node = self.root |
| 203 |
while 1: |
| 204 |
if node.final: |
| 205 |
if pos == 0: |
| 206 |
return "".join(result) |
| 207 |
pos -= 1 |
| 208 |
for label, child in sorted(node.edges.items()): |
| 209 |
nextpos = pos - child.num_reachable_linear |
| 210 |
if nextpos < 0: |
| 211 |
result.append(label) |
| 212 |
node = child |
| 213 |
break |
| 214 |
else: |
| 215 |
pos = nextpos |
| 216 |
else: |
| 217 |
assert 0 |
| 218 |
|
| 219 |
def _linearize_edges(self): |
| 220 |
# compute "linear" edges. the idea is that long chains of edges without |
| 221 |
# any of the intermediate states being final or any extra incoming or |
| 222 |
# outgoing edges can be represented by having removing them, and |
| 223 |
# instead using longer strings as edge labels (instead of single |
| 224 |
# characters) |
| 225 |
incoming = defaultdict(list) |
| 226 |
nodes = sorted(self.enum_all_nodes(), key=lambda e: e.id) |
| 227 |
for node in nodes: |
| 228 |
for label, child in sorted(node.edges.items()): |
| 229 |
incoming[child].append(node) |
| 230 |
for node in nodes: |
| 231 |
node.linear_edges = [] |
| 232 |
for label, child in sorted(node.edges.items()): |
| 233 |
s = [label] |
| 234 |
while len(child.edges) == 1 and len(incoming[child]) == 1 and not child.final: |
| 235 |
(c, child), = child.edges.items() |
| 236 |
s.append(c) |
| 237 |
node.linear_edges.append((''.join(s), child)) |
| 238 |
|
| 239 |
def _topological_order(self): |
| 240 |
# compute reachable linear nodes, and the set of incoming edges for each node |
| 241 |
order = [] |
| 242 |
stack = [self.root] |
| 243 |
seen = set() |
| 244 |
while stack: |
| 245 |
# depth first traversal |
| 246 |
node = stack.pop() |
| 247 |
if node.id in seen: |
| 248 |
continue |
| 249 |
seen.add(node.id) |
| 250 |
order.append(node) |
| 251 |
for label, child in node.linear_edges: |
| 252 |
stack.append(child) |
| 253 |
|
| 254 |
# do a (slightly bad) topological sort |
| 255 |
incoming = defaultdict(set) |
| 256 |
for node in order: |
| 257 |
for label, child in node.linear_edges: |
| 258 |
incoming[child].add((label, node)) |
| 259 |
no_incoming = [order[0]] |
| 260 |
topoorder = [] |
| 261 |
positions = {} |
| 262 |
while no_incoming: |
| 263 |
node = no_incoming.pop() |
| 264 |
topoorder.append(node) |
| 265 |
positions[node] = len(topoorder) |
| 266 |
# use "reversed" to make sure that the linear_edges get reorderd |
| 267 |
# from their alphabetical order as little as necessary (no_incoming |
| 268 |
# is LIFO) |
| 269 |
for label, child in reversed(node.linear_edges): |
| 270 |
incoming[child].discard((label, node)) |
| 271 |
if not incoming[child]: |
| 272 |
no_incoming.append(child) |
| 273 |
del incoming[child] |
| 274 |
# check result |
| 275 |
assert set(topoorder) == set(order) |
| 276 |
assert len(set(topoorder)) == len(topoorder) |
| 277 |
|
| 278 |
for node in order: |
| 279 |
node.linear_edges.sort(key=lambda element: positions[element[1]]) |
| 280 |
|
| 281 |
for node in order: |
| 282 |
for label, child in node.linear_edges: |
| 283 |
assert positions[child] > positions[node] |
| 284 |
# number the nodes. afterwards every input string in the set has a |
| 285 |
# unique number in the 0 <= number < len(data). We then put the data in |
| 286 |
# self.data into a linear list using these numbers as indexes. |
| 287 |
topoorder[0].num_reachable_linear |
| 288 |
linear_data = [None] * len(self.data) |
| 289 |
inverse = {} # maps value back to index |
| 290 |
for word, value in self.data.items(): |
| 291 |
index = self._lookup(word) |
| 292 |
linear_data[index] = value |
| 293 |
inverse[value] = index |
| 294 |
|
| 295 |
return topoorder, linear_data, inverse |
| 296 |
|
| 297 |
def compute_packed(self, order): |
| 298 |
def compute_chunk(node, offsets): |
| 299 |
""" compute the packed node/edge data for a node. result is a |
| 300 |
list of bytes as long as order. the jump distance calculations use |
| 301 |
the offsets dictionary to know where in the final big output |
| 302 |
bytestring the individual nodes will end up. """ |
| 303 |
result = bytearray() |
| 304 |
offset = offsets[node] |
| 305 |
encode_varint_unsigned(number_add_bits(node.num_reachable_linear, node.final), result) |
| 306 |
if len(node.linear_edges) == 0: |
| 307 |
assert node.final |
| 308 |
encode_varint_unsigned(0, result) # add a 0 saying "done" |
| 309 |
prev_child_offset = offset + len(result) |
| 310 |
for edgeindex, (label, targetnode) in enumerate(node.linear_edges): |
| 311 |
label = label.encode('ascii') |
| 312 |
child_offset = offsets[targetnode] |
| 313 |
child_offset_difference = child_offset - prev_child_offset |
| 314 |
|
| 315 |
info = number_add_bits(child_offset_difference, len(label) == 1, edgeindex == len(node.linear_edges) - 1) |
| 316 |
if edgeindex == 0: |
| 317 |
assert info != 0 |
| 318 |
encode_varint_unsigned(info, result) |
| 319 |
prev_child_offset = child_offset |
| 320 |
if len(label) > 1: |
| 321 |
encode_varint_unsigned(len(label), result) |
| 322 |
result.extend(label) |
| 323 |
return result |
| 324 |
|
| 325 |
def compute_new_offsets(chunks, offsets): |
| 326 |
""" Given a list of chunks, compute the new offsets (by adding the |
| 327 |
chunk lengths together). Also check if we cannot shrink the output |
| 328 |
further because none of the node offsets are smaller now. if that's |
| 329 |
the case return None. """ |
| 330 |
new_offsets = {} |
| 331 |
curr_offset = 0 |
| 332 |
should_continue = False |
| 333 |
for node, result in zip(order, chunks): |
| 334 |
if curr_offset < offsets[node]: |
| 335 |
# the new offset is below the current assumption, this |
| 336 |
# means we can shrink the output more |
| 337 |
should_continue = True |
| 338 |
new_offsets[node] = curr_offset |
| 339 |
curr_offset += len(result) |
| 340 |
if not should_continue: |
| 341 |
return None |
| 342 |
return new_offsets |
| 343 |
|
| 344 |
# assign initial offsets to every node |
| 345 |
offsets = {} |
| 346 |
for i, node in enumerate(order): |
| 347 |
# we don't know position of the edge yet, just use something big as |
| 348 |
# the starting position. we'll have to do further iterations anyway, |
| 349 |
# but the size is at least a lower limit then |
| 350 |
offsets[node] = i * 2 ** 30 |
| 351 |
|
| 352 |
|
| 353 |
# due to the variable integer width encoding of edge targets we need to |
| 354 |
# run this to fixpoint. in the process we shrink the output more and |
| 355 |
# more until we can't any more. at any point we can stop and use the |
| 356 |
# output, but we might need padding zero bytes when joining the chunks |
| 357 |
# to have the correct jump distances |
| 358 |
last_offsets = None |
| 359 |
while 1: |
| 360 |
chunks = [compute_chunk(node, offsets) for node in order] |
| 361 |
last_offsets = offsets |
| 362 |
offsets = compute_new_offsets(chunks, offsets) |
| 363 |
if offsets is None: # couldn't shrink |
| 364 |
break |
| 365 |
|
| 366 |
# build the final packed string |
| 367 |
total_result = bytearray() |
| 368 |
for node, result in zip(order, chunks): |
| 369 |
node_offset = last_offsets[node] |
| 370 |
if node_offset > len(total_result): |
| 371 |
# need to pad to get the offsets correct |
| 372 |
padding = b"\x00" * (node_offset - len(total_result)) |
| 373 |
total_result.extend(padding) |
| 374 |
assert node_offset == len(total_result) |
| 375 |
total_result.extend(result) |
| 376 |
return bytes(total_result) |
| 377 |
|
| 378 |
|
| 379 |
# ______________________________________________________________________ |
| 380 |
# the following functions operate on the packed representation |
| 381 |
|
| 382 |
def number_add_bits(x, *bits): |
| 383 |
for bit in bits: |
| 384 |
assert bit == 0 or bit == 1 |
| 385 |
x = (x << 1) | bit |
| 386 |
return x |
| 387 |
|
| 388 |
def encode_varint_unsigned(i, res): |
| 389 |
# https://en.wikipedia.org/wiki/LEB128 unsigned variant |
| 390 |
more = True |
| 391 |
startlen = len(res) |
| 392 |
if i < 0: |
| 393 |
raise ValueError("only positive numbers supported", i) |
| 394 |
while more: |
| 395 |
lowest7bits = i & 0b1111111 |
| 396 |
i >>= 7 |
| 397 |
if i == 0: |
| 398 |
more = False |
| 399 |
else: |
| 400 |
lowest7bits |= 0b10000000 |
| 401 |
res.append(lowest7bits) |
| 402 |
return len(res) - startlen |
| 403 |
|
| 404 |
def number_split_bits(x, n, acc=()): |
| 405 |
if n == 1: |
| 406 |
return x >> 1, x & 1 |
| 407 |
if n == 2: |
| 408 |
return x >> 2, (x >> 1) & 1, x & 1 |
| 409 |
assert 0, "implement me!" |
| 410 |
|
| 411 |
def decode_varint_unsigned(b, index=0): |
| 412 |
res = 0 |
| 413 |
shift = 0 |
| 414 |
while True: |
| 415 |
byte = b[index] |
| 416 |
res = res | ((byte & 0b1111111) << shift) |
| 417 |
index += 1 |
| 418 |
shift += 7 |
| 419 |
if not (byte & 0b10000000): |
| 420 |
return res, index |
| 421 |
|
| 422 |
def decode_node(packed, node): |
| 423 |
x, node = decode_varint_unsigned(packed, node) |
| 424 |
node_count, final = number_split_bits(x, 1) |
| 425 |
return node_count, final, node |
| 426 |
|
| 427 |
def decode_edge(packed, edgeindex, prev_child_offset, offset): |
| 428 |
x, offset = decode_varint_unsigned(packed, offset) |
| 429 |
if x == 0 and edgeindex == 0: |
| 430 |
raise KeyError # trying to decode past a final node |
| 431 |
child_offset_difference, len1, last_edge = number_split_bits(x, 2) |
| 432 |
child_offset = prev_child_offset + child_offset_difference |
| 433 |
if len1: |
| 434 |
size = 1 |
| 435 |
else: |
| 436 |
size, offset = decode_varint_unsigned(packed, offset) |
| 437 |
return child_offset, last_edge, size, offset |
| 438 |
|
| 439 |
def _match_edge(packed, s, size, node_offset, stringpos): |
| 440 |
if size > 1 and stringpos + size > len(s): |
| 441 |
# past the end of the string, can't match |
| 442 |
return False |
| 443 |
for i in range(size): |
| 444 |
if packed[node_offset + i] != s[stringpos + i]: |
| 445 |
# if a subsequent char of an edge doesn't match, the word isn't in |
| 446 |
# the dawg |
| 447 |
if i > 0: |
| 448 |
raise KeyError |
| 449 |
return False |
| 450 |
return True |
| 451 |
|
| 452 |
def lookup(packed, data, s): |
| 453 |
return data[_lookup(packed, s)] |
| 454 |
|
| 455 |
def _lookup(packed, s): |
| 456 |
stringpos = 0 |
| 457 |
node_offset = 0 |
| 458 |
skipped = 0 # keep track of number of final nodes that we skipped |
| 459 |
false = False |
| 460 |
while stringpos < len(s): |
| 461 |
#print(f"{node_offset=} {stringpos=}") |
| 462 |
_, final, edge_offset = decode_node(packed, node_offset) |
| 463 |
prev_child_offset = edge_offset |
| 464 |
edgeindex = 0 |
| 465 |
while 1: |
| 466 |
child_offset, last_edge, size, edgelabel_chars_offset = decode_edge(packed, edgeindex, prev_child_offset, edge_offset) |
| 467 |
#print(f" {edge_offset=} {child_offset=} {last_edge=} {size=} {edgelabel_chars_offset=}") |
| 468 |
edgeindex += 1 |
| 469 |
prev_child_offset = child_offset |
| 470 |
if _match_edge(packed, s, size, edgelabel_chars_offset, stringpos): |
| 471 |
# match |
| 472 |
if final: |
| 473 |
skipped += 1 |
| 474 |
stringpos += size |
| 475 |
node_offset = child_offset |
| 476 |
break |
| 477 |
if last_edge: |
| 478 |
raise KeyError |
| 479 |
descendant_count, _, _ = decode_node(packed, child_offset) |
| 480 |
skipped += descendant_count |
| 481 |
edge_offset = edgelabel_chars_offset + size |
| 482 |
_, final, _ = decode_node(packed, node_offset) |
| 483 |
if final: |
| 484 |
return skipped |
| 485 |
raise KeyError |
| 486 |
|
| 487 |
def inverse_lookup(packed, inverse, x): |
| 488 |
pos = inverse[x] |
| 489 |
return _inverse_lookup(packed, pos) |
| 490 |
|
| 491 |
def _inverse_lookup(packed, pos): |
| 492 |
result = bytearray() |
| 493 |
node_offset = 0 |
| 494 |
while 1: |
| 495 |
node_count, final, edge_offset = decode_node(packed, node_offset) |
| 496 |
if final: |
| 497 |
if pos == 0: |
| 498 |
return bytes(result) |
| 499 |
pos -= 1 |
| 500 |
prev_child_offset = edge_offset |
| 501 |
edgeindex = 0 |
| 502 |
while 1: |
| 503 |
child_offset, last_edge, size, edgelabel_chars_offset = decode_edge(packed, edgeindex, prev_child_offset, edge_offset) |
| 504 |
edgeindex += 1 |
| 505 |
prev_child_offset = child_offset |
| 506 |
descendant_count, _, _ = decode_node(packed, child_offset) |
| 507 |
nextpos = pos - descendant_count |
| 508 |
if nextpos < 0: |
| 509 |
assert edgelabel_chars_offset >= 0 |
| 510 |
result.extend(packed[edgelabel_chars_offset: edgelabel_chars_offset + size]) |
| 511 |
node_offset = child_offset |
| 512 |
break |
| 513 |
elif not last_edge: |
| 514 |
pos = nextpos |
| 515 |
edge_offset = edgelabel_chars_offset + size |
| 516 |
else: |
| 517 |
raise KeyError |
| 518 |
else: |
| 519 |
raise KeyError |
| 520 |
|
| 521 |
|
| 522 |
def build_compression_dawg(ucdata): |
| 523 |
d = Dawg() |
| 524 |
ucdata.sort() |
| 525 |
for name, value in ucdata: |
| 526 |
d.insert(name, value) |
| 527 |
packed, pos_to_code, reversedict = d.finish() |
| 528 |
print("size of dawg [KiB]", round(len(packed) / 1024, 2)) |
| 529 |
# check that lookup and inverse_lookup work correctly on the input data |
| 530 |
for name, value in ucdata: |
| 531 |
assert lookup(packed, pos_to_code, name.encode('ascii')) == value |
| 532 |
assert inverse_lookup(packed, reversedict, value) == name.encode('ascii') |
| 533 |
return packed, pos_to_code |