Debian Codegraph @

morfologik-fsa-builders/src/main/java/morfologik/fsa/builders/FSABuilder.java

raw
1 package morfologik.fsa.builders;
2
3 import java.util.*;
4
5 import morfologik.fsa.FSA;
6 import static morfologik.fsa.builders.ConstantArcSizeFSA.*;
7
8 /**
9 * Fast, memory-conservative finite state automaton builder, returning an
10 * in-memory {@link FSA} that is a tradeoff between construction speed and
11 * memory consumption. Use serializers to compress the returned automaton into
12 * more compact form.
13 *
14 * @see FSASerializer
15 */
16 public final class FSABuilder {
17 /**
18 * Debug and information constants.
19 *
20 * @see FSABuilder#getInfo()
21 */
22 public enum InfoEntry {
23 SERIALIZATION_BUFFER_SIZE("Serialization buffer size"),
24 SERIALIZATION_BUFFER_REALLOCATIONS("Serialization buffer reallocs"),
25 CONSTANT_ARC_AUTOMATON_SIZE("Constant arc FSA size"),
26 MAX_ACTIVE_PATH_LENGTH("Max active path"),
27 STATE_REGISTRY_TABLE_SLOTS("Registry hash slots"),
28 STATE_REGISTRY_SIZE("Registry hash entries"),
29 ESTIMATED_MEMORY_CONSUMPTION_MB("Estimated mem consumption (MB)");
30
31 private final String stringified;
32
33 InfoEntry(String stringified) {
34 this.stringified = stringified;
35 }
36
37 @Override
38 public String toString() {
39 return stringified;
40 }
41 }
42
43 /** A megabyte. */
44 private final static int MB = 1024 * 1024;
45
46 /**
47 * Internal serialized FSA buffer expand ratio.
48 */
49 private final static int BUFFER_GROWTH_SIZE = 5 * MB;
50
51 /**
52 * Maximum number of labels from a single state.
53 */
54 private final static int MAX_LABELS = 256;
55
56 /**
57 * A comparator comparing full byte arrays. Unsigned byte comparisons ('C'-locale).
58 */
59 public static final Comparator<byte[]> LEXICAL_ORDERING = new Comparator<byte[]>() {
60 public int compare(byte[] o1, byte[] o2) {
61 return FSABuilder.compare(o1, 0, o1.length, o2, 0, o2.length);
62 }
63 };
64
65 /**
66 * Internal serialized FSA buffer expand ratio.
67 */
68 private final int bufferGrowthSize;
69
70 /**
71 * Holds serialized and mutable states. Each state is a sequential list of
72 * arcs, the last arc is marked with {@link #BIT_ARC_LAST}.
73 */
74 private byte[] serialized = new byte[0];
75
76 /**
77 * Number of bytes already taken in {@link #serialized}. Start from 1 to keep
78 * 0 a sentinel value (for the hash set and final state).
79 */
80 private int size;
81
82 /**
83 * States on the "active path" (still mutable). Values are addresses of each
84 * state's first arc.
85 */
86 private int[] activePath = new int[0];
87
88 /**
89 * Current length of the active path.
90 */
91 private int activePathLen;
92
93 /**
94 * The next offset at which an arc will be added to the given state on
95 * {@link #activePath}.
96 */
97 private int[] nextArcOffset = new int[0];
98
99 /**
100 * Root state. If negative, the automaton has been built already and cannot be
101 * extended.
102 */
103 private int root;
104
105 /**
106 * An epsilon state. The first and only arc of this state points either to the
107 * root or to the terminal state, indicating an empty automaton.
108 */
109 private int epsilon;
110
111 /**
112 * Hash set of state addresses in {@link #serialized}, hashed by
113 * {@link #hash(int, int)}. Zero reserved for an unoccupied slot.
114 */
115 private int[] hashSet = new int[2];
116
117 /**
118 * Number of entries currently stored in {@link #hashSet}.
119 */
120 private int hashSize = 0;
121
122 /**
123 * Previous sequence added to the automaton in {@link #add(byte[], int, int)}.
124 * Used in assertions only.
125 */
126 private byte[] previous;
127
128 /**
129 * Information about the automaton and its compilation.
130 */
131 private TreeMap<InfoEntry, Object> info;
132
133 /**
134 * {@link #previous} sequence's length, used in assertions only.
135 */
136 private int previousLength;
137
138 /** */
139 public FSABuilder() {
140 this(BUFFER_GROWTH_SIZE);
141 }
142
143 /**
144 * @param bufferGrowthSize Buffer growth size (in bytes) when constructing the automaton.
145 */
146 public FSABuilder(int bufferGrowthSize) {
147 this.bufferGrowthSize = Math.max(bufferGrowthSize, ARC_SIZE * MAX_LABELS);
148
149 // Allocate epsilon state.
150 epsilon = allocateState(1);
151 serialized[epsilon + FLAGS_OFFSET] |= BIT_ARC_LAST;
152
153 // Allocate root, with an initial empty set of output arcs.
154 expandActivePath(1);
155 root = activePath[0];
156 }
157
158 /**
159 * Add a single sequence of bytes to the FSA. The input must be
160 * lexicographically greater than any previously added sequence.
161 *
162 * @param sequence The array holding input sequence of bytes.
163 * @param start Starting offset (inclusive)
164 * @param len Length of the input sequence (at least 1 byte).
165 */
166 public void add(byte[] sequence, int start, int len) {
167 assert serialized != null : "Automaton already built.";
168 assert previous == null || len == 0 || compare(previous, 0, previousLength, sequence, start, len) <= 0 : "Input must be sorted: "
169 + Arrays.toString(Arrays.copyOf(previous, previousLength))
170 + " >= "
171 + Arrays.toString(Arrays.copyOfRange(sequence, start, len));
172 assert setPrevious(sequence, start, len);
173
174 // Determine common prefix length.
175 final int commonPrefix = commonPrefix(sequence, start, len);
176
177 // Make room for extra states on active path, if needed.
178 expandActivePath(len);
179
180 // Freeze all the states after the common prefix.
181 for (int i = activePathLen - 1; i > commonPrefix; i--) {
182 final int frozenState = freezeState(i);
183 setArcTarget(nextArcOffset[i - 1] - ARC_SIZE, frozenState);
184 nextArcOffset[i] = activePath[i];
185 }
186
187 // Create arcs to new suffix states.
188 for (int i = commonPrefix + 1, j = start + commonPrefix; i <= len; i++) {
189 final int p = nextArcOffset[i - 1];
190
191 serialized[p + FLAGS_OFFSET] = (byte) (i == len ? BIT_ARC_FINAL : 0);
192 serialized[p + LABEL_OFFSET] = sequence[j++];
193 setArcTarget(p, i == len ? TERMINAL_STATE : activePath[i]);
194
195 nextArcOffset[i - 1] = p + ARC_SIZE;
196 }
197
198 // Save last sequence's length so that we don't need to calculate it again.
199 this.activePathLen = len;
200 }
201
202 /** Number of serialization buffer reallocations. */
203 private int serializationBufferReallocations;
204
205 /**
206 * @return Finalizes the construction of the automaton and returns it.
207 */
208 public FSA complete() {
209 add(new byte[0], 0, 0);
210
211 if (nextArcOffset[0] - activePath[0] == 0) {
212 // An empty FSA.
213 setArcTarget(epsilon, TERMINAL_STATE);
214 } else {
215 // An automaton with at least a single arc from root.
216 root = freezeState(0);
217 setArcTarget(epsilon, root);
218 }
219
220 info = new TreeMap<InfoEntry, Object>();
221 info.put(InfoEntry.SERIALIZATION_BUFFER_SIZE, serialized.length);
222 info.put(InfoEntry.SERIALIZATION_BUFFER_REALLOCATIONS, serializationBufferReallocations);
223 info.put(InfoEntry.CONSTANT_ARC_AUTOMATON_SIZE, size);
224 info.put(InfoEntry.MAX_ACTIVE_PATH_LENGTH, activePath.length);
225 info.put(InfoEntry.STATE_REGISTRY_TABLE_SLOTS, hashSet.length);
226 info.put(InfoEntry.STATE_REGISTRY_SIZE, hashSize);
227 info.put(InfoEntry.ESTIMATED_MEMORY_CONSUMPTION_MB,
228 (this.serialized.length + this.hashSet.length * 4) / (double) MB);
229
230 final FSA fsa = new ConstantArcSizeFSA(java.util.Arrays.copyOf(this.serialized, this.size), epsilon);
231 this.serialized = null;
232 this.hashSet = null;
233 return fsa;
234 }
235
236 /**
237 * Build a minimal, deterministic automaton from a sorted list of byte
238 * sequences.
239 *
240 * @param input Input sequences to build automaton from.
241 * @return Returns the automaton encoding all input sequences.
242 */
243 public static FSA build(byte[][] input) {
244 final FSABuilder builder = new FSABuilder();
245
246 for (byte[] chs : input) {
247 builder.add(chs, 0, chs.length);
248 }
249
250 return builder.complete();
251 }
252
253 /**
254 * Build a minimal, deterministic automaton from an iterable list of byte
255 * sequences.
256 *
257 * @param input Input sequences to build automaton from.
258 * @return Returns the automaton encoding all input sequences.
259 */
260 public static FSA build(Iterable<byte[]> input) {
261 final FSABuilder builder = new FSABuilder();
262
263 for (byte[] chs : input) {
264 builder.add(chs, 0, chs.length);
265 }
266
267 return builder.complete();
268 }
269
270 /**
271 * @return Returns various statistics concerning the FSA and its compilation.
272 * @see InfoEntry
273 */
274 public Map<InfoEntry, Object> getInfo() {
275 return info;
276 }
277
278 /** Is this arc the state's last? */
279 private boolean isArcLast(int arc) {
280 return (serialized[arc + FLAGS_OFFSET] & BIT_ARC_LAST) != 0;
281 }
282
283 /** Is this arc final? */
284 private boolean isArcFinal(int arc) {
285 return (serialized[arc + FLAGS_OFFSET] & BIT_ARC_FINAL) != 0;
286 }
287
288 /** Get label's arc. */
289 private byte getArcLabel(int arc) {
290 return serialized[arc + LABEL_OFFSET];
291 }
292
293 /**
294 * Fills the target state address of an arc.
295 */
296 private void setArcTarget(int arc, int state) {
297 arc += ADDRESS_OFFSET + TARGET_ADDRESS_SIZE;
298 for (int i = 0; i < TARGET_ADDRESS_SIZE; i++) {
299 serialized[--arc] = (byte) state;
300 state >>>= 8;
301 }
302 }
303
304 /**
305 * Returns the address of an arc.
306 */
307 private int getArcTarget(int arc) {
308 arc += ADDRESS_OFFSET;
309 return (serialized[arc] ) << 24 |
310 (serialized[arc + 1] & 0xff) << 16 |
311 (serialized[arc + 2] & 0xff) << 8 |
312 (serialized[arc + 3] & 0xff);
313 }
314
315 /**
316 * @return The number of common prefix characters with the previous sequence.
317 */
318 private int commonPrefix(byte[] sequence, int start, int len) {
319 // Empty root state case.
320 final int max = Math.min(len, activePathLen);
321 int i;
322 for (i = 0; i < max; i++) {
323 final int lastArc = nextArcOffset[i] - ARC_SIZE;
324 if (sequence[start++] != getArcLabel(lastArc)) {
325 break;
326 }
327 }
328
329 return i;
330 }
331
332 /**
333 * Freeze a state: try to find an equivalent state in the interned states
334 * dictionary first, if found, return it, otherwise, serialize the mutable
335 * state at <code>activePathIndex</code> and return it.
336 */
337 private int freezeState(final int activePathIndex) {
338 final int start = activePath[activePathIndex];
339 final int end = nextArcOffset[activePathIndex];
340 final int len = end - start;
341
342 // Set the last arc flag on the current active path's state.
343 serialized[end - ARC_SIZE + FLAGS_OFFSET] |= BIT_ARC_LAST;
344
345 // Try to locate a state with an identical content in the hash set.
346 final int bucketMask = (hashSet.length - 1);
347 int slot = hash(start, len) & bucketMask;
348 for (int i = 0;;) {
349 int state = hashSet[slot];
350 if (state == 0) {
351 state = hashSet[slot] = serialize(activePathIndex);
352 if (++hashSize > hashSet.length / 2)
353 expandAndRehash();
354 return state;
355 } else if (equivalent(state, start, len)) {
356 return state;
357 }
358
359 slot = (slot + (++i)) & bucketMask;
360 }
361 }
362
363 /**
364 * Reallocate and rehash the hash set.
365 */
366 private void expandAndRehash() {
367 final int[] newHashSet = new int[hashSet.length * 2];
368 final int bucketMask = (newHashSet.length - 1);
369
370 for (int j = 0; j < hashSet.length; j++) {
371 final int state = hashSet[j];
372 if (state > 0) {
373 int slot = hash(state, stateLength(state)) & bucketMask;
374 for (int i = 0; newHashSet[slot] > 0;) {
375 slot = (slot + (++i)) & bucketMask;
376 }
377 newHashSet[slot] = state;
378 }
379 }
380 this.hashSet = newHashSet;
381 }
382
383 /**
384 * The total length of the serialized state data (all arcs).
385 */
386 private int stateLength(int state) {
387 int arc = state;
388 while (!isArcLast(arc)) {
389 arc += ARC_SIZE;
390 }
391 return arc - state + ARC_SIZE;
392 }
393
394 /**
395 * Return <code>true</code> if two regions in {@link #serialized} are
396 * identical.
397 */
398 private boolean equivalent(int start1, int start2, int len) {
399 if (start1 + len > size || start2 + len > size)
400 return false;
401
402 while (len-- > 0)
403 if (serialized[start1++] != serialized[start2++])
404 return false;
405
406 return true;
407 }
408
409 /**
410 * Serialize a given state on the active path.
411 */
412 private int serialize(final int activePathIndex) {
413 expandBuffers();
414
415 final int newState = size;
416 final int start = activePath[activePathIndex];
417 final int len = nextArcOffset[activePathIndex] - start;
418 System.arraycopy(serialized, start, serialized, newState, len);
419
420 size += len;
421 return newState;
422 }
423
424 /**
425 * Hash code of a fragment of {@link #serialized} array.
426 */
427 private int hash(int start, int byteCount) {
428 assert byteCount % ARC_SIZE == 0 : "Not an arc multiply?";
429
430 int h = 0;
431 for (int arcs = byteCount / ARC_SIZE; --arcs >= 0; start += ARC_SIZE) {
432 h = 17 * h + getArcLabel(start);
433 h = 17 * h + getArcTarget(start);
434 if (isArcFinal(start))
435 h += 17;
436 }
437
438 return h;
439 }
440
441 /**
442 * Append a new mutable state to the active path.
443 */
444 private void expandActivePath(int size) {
445 if (activePath.length < size) {
446 final int p = activePath.length;
447 activePath = java.util.Arrays.copyOf(activePath, size);
448 nextArcOffset = java.util.Arrays.copyOf(nextArcOffset, size);
449
450 for (int i = p; i < size; i++) {
451 nextArcOffset[i] = activePath[i] = allocateState(/* assume max labels count */MAX_LABELS);
452 }
453 }
454 }
455
456 /**
457 * Expand internal buffers for the next state.
458 */
459 private void expandBuffers() {
460 if (this.serialized.length < size + ARC_SIZE * MAX_LABELS) {
461 serialized = java.util.Arrays.copyOf(serialized, serialized.length + bufferGrowthSize);
462 serializationBufferReallocations++;
463 }
464 }
465
466 /**
467 * Allocate space for a state with the given number of outgoing labels.
468 *
469 * @return state offset
470 */
471 private int allocateState(int labels) {
472 expandBuffers();
473 final int state = size;
474 size += labels * ARC_SIZE;
475 return state;
476 }
477
478 /**
479 * Copy <code>current</code> into an internal buffer.
480 */
481 private boolean setPrevious(byte[] sequence, int start, int length) {
482 if (previous == null || previous.length < length) {
483 previous = new byte[length];
484 }
485
486 System.arraycopy(sequence, start, previous, 0, length);
487 previousLength = length;
488 return true;
489 }
490
491 /**
492 * Lexicographic order of input sequences. By default, consistent with the "C"
493 * sort (absolute value of bytes, 0-255).
494 */
495 private static int compare(byte[] s1, int start1, int lens1, byte[] s2, int start2, int lens2) {
496 final int max = Math.min(lens1, lens2);
497
498 for (int i = 0; i < max; i++) {
499 final byte c1 = s1[start1++];
500 final byte c2 = s2[start2++];
501 if (c1 != c2)
502 return (c1 & 0xff) - (c2 & 0xff);
503 }
504
505 return lens1 - lens2;
506 }
507 }