Debian Codegraph @

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

raw
1 package morfologik.fsa.builders;
2
3 import static morfologik.fsa.CFSA2.*;
4 import static morfologik.fsa.FSAFlags.*;
5
6 import java.io.IOException;
7 import java.io.OutputStream;
8 import java.util.BitSet;
9 import java.util.Comparator;
10 import java.util.EnumSet;
11 import java.util.Locale;
12 import java.util.PriorityQueue;
13 import java.util.Set;
14 import java.util.TreeSet;
15 import java.util.logging.Level;
16 import java.util.logging.Logger;
17
18 import com.carrotsearch.hppc.BoundedProportionalArraySizingStrategy;
19 import com.carrotsearch.hppc.IntArrayList;
20 import com.carrotsearch.hppc.IntIntHashMap;
21 import com.carrotsearch.hppc.IntStack;
22 import com.carrotsearch.hppc.cursors.IntCursor;
23 import com.carrotsearch.hppc.cursors.IntIntCursor;
24
25 import morfologik.fsa.CFSA2;
26 import morfologik.fsa.FSA;
27 import morfologik.fsa.FSAFlags;
28 import morfologik.fsa.FSAHeader;
29 import morfologik.fsa.StateVisitor;
30 import morfologik.fsa.builders.FSAUtils.IntIntHolder;
31
32 /**
33 * Serializes in-memory {@link FSA} graphs to {@link CFSA2}.
34 *
35 * <p>
36 * It is possible to serialize the automaton with numbers required for perfect
37 * hashing. See {@link #withNumbers()} method.
38 * </p>
39 *
40 * @see CFSA2
41 */
42 public final class CFSA2Serializer implements FSASerializer {
43 private final Logger logger = Logger.getLogger(getClass().getName());
44
45 /**
46 * Supported flags.
47 */
48 private final static EnumSet<FSAFlags> flags = EnumSet.of(NUMBERS, FLEXIBLE, STOPBIT, NEXTBIT);
49
50 /**
51 * No-state id.
52 */
53 private final static int NO_STATE = -1;
54
55 /**
56 * <code>true</code> if we should serialize with numbers.
57 *
58 * @see #withNumbers()
59 */
60 private boolean withNumbers;
61
62 /**
63 * A hash map of [state, offset] pairs.
64 */
65 private IntIntHashMap offsets = new IntIntHashMap();
66
67 /**
68 * A hash map of [state, right-language-count] pairs.
69 */
70 private IntIntHashMap numbers = new IntIntHashMap();
71
72 /**
73 * Scratch array for serializing vints.
74 */
75 private final byte[] scratch = new byte[5];
76
77 /**
78 * The most frequent labels for integrating with the flags field.
79 */
80 private byte[] labelsIndex;
81
82 /**
83 * Inverted index of labels to be integrated with flags field. A label at
84 * index <code>i<code> has the index or zero (no integration).
85 */
86 private int[] labelsInvIndex;
87
88 /**
89 * Serialize the automaton with the number of right-language sequences in each
90 * node. This is required to implement perfect hashing. The numbering also
91 * preserves the order of input sequences.
92 *
93 * @return Returns the same object for easier call chaining.
94 */
95 public CFSA2Serializer withNumbers() {
96 withNumbers = true;
97 return this;
98 }
99
100 /**
101 * Serializes any {@link FSA} to {@link CFSA2} stream.
102 *
103 * @see #withNumbers()
104 * @return Returns <code>os</code> for chaining.
105 */
106 @Override
107 public <T extends OutputStream> T serialize(final FSA fsa, T os) throws IOException {
108 /*
109 * Calculate the most frequent labels and build indexed labels dictionary.
110 */
111 computeLabelsIndex(fsa);
112
113 /*
114 * Calculate the number of bytes required for the node data, if
115 * serializing with numbers.
116 */
117 if (withNumbers) {
118 this.numbers = FSAUtils.rightLanguageForAllStates(fsa);
119 }
120
121 /*
122 * Linearize all the states, optimizing their layout.
123 */
124 IntArrayList linearized = linearize(fsa);
125
126 /*
127 * Emit the header.
128 */
129 FSAHeader.write(os, CFSA2.VERSION);
130
131 EnumSet<FSAFlags> fsaFlags = EnumSet.of(FLEXIBLE, STOPBIT, NEXTBIT);
132 if (withNumbers) {
133 fsaFlags.add(NUMBERS);
134 }
135
136 final short sflags = FSAFlags.asShort(fsaFlags);
137 os.write((sflags >> 8) & 0xFF);
138 os.write((sflags) & 0xFF);
139
140 /*
141 * Emit labels index.
142 */
143 os.write(labelsIndex.length);
144 os.write(labelsIndex);
145
146 /*
147 * Emit the automaton.
148 */
149 int size = emitNodes(fsa, os, linearized);
150 assert size == 0 : "Size changed in the final pass?";
151
152 return os;
153 }
154
155 /**
156 * Compute a set of labels to be integrated with the flags field.
157 */
158 private void computeLabelsIndex(final FSA fsa) {
159 // Compute labels count.
160 final int[] countByValue = new int[256];
161
162 fsa.visitAllStates(new StateVisitor() {
163 public boolean accept(int state) {
164 for (int arc = fsa.getFirstArc(state); arc != 0; arc = fsa.getNextArc(arc))
165 countByValue[fsa.getArcLabel(arc) & 0xff]++;
166 return true;
167 }
168 });
169
170 // Order by descending frequency of counts and increasing label value.
171 Comparator<IntIntHolder> comparator = new Comparator<IntIntHolder>() {
172 public int compare(IntIntHolder o1, IntIntHolder o2) {
173 int countDiff = o2.b - o1.b;
174 if (countDiff == 0) {
175 countDiff = o1.a - o2.a;
176 }
177 return countDiff;
178 }
179 };
180
181 TreeSet<IntIntHolder> labelAndCount = new TreeSet<IntIntHolder>(comparator);
182 for (int label = 0; label < countByValue.length; label++) {
183 if (countByValue[label] > 0) {
184 labelAndCount.add(new IntIntHolder(label, countByValue[label]));
185 }
186 }
187
188 labelsIndex = new byte[1 + Math.min(labelAndCount.size(), CFSA2.LABEL_INDEX_SIZE)];
189 labelsInvIndex = new int[256];
190 for (int i = labelsIndex.length - 1; i > 0 && !labelAndCount.isEmpty(); i--) {
191 IntIntHolder p = labelAndCount.first();
192 labelAndCount.remove(p);
193 labelsInvIndex[p.a] = i;
194 labelsIndex[i] = (byte) p.a;
195 }
196 }
197
198 /**
199 * Return supported flags.
200 */
201 @Override
202 public Set<FSAFlags> getFlags() {
203 return flags;
204 }
205
206 /**
207 * Linearization of states.
208 */
209 private IntArrayList linearize(final FSA fsa) throws IOException {
210 /*
211 * Compute the states with most inlinks. These should be placed as close to the
212 * start of the automaton, as possible so that v-coded addresses are tiny.
213 */
214 final IntIntHashMap inlinkCount = computeInlinkCount(fsa);
215
216 /*
217 * An array of ordered states for serialization.
218 */
219 final IntArrayList linearized = new IntArrayList(0, new BoundedProportionalArraySizingStrategy(1000, 10000, 1.5f));
220
221 /*
222 * Determine which states should be linearized first (at fixed positions) so as to
223 * minimize the place occupied by goto fields.
224 */
225 int maxStates = Integer.MAX_VALUE;
226 int minInlinkCount = 2;
227 int [] states = computeFirstStates(inlinkCount, maxStates, minInlinkCount);
228
229 /*
230 * Compute initial addresses, without node rearrangements.
231 */
232 int serializedSize = linearizeAndCalculateOffsets(fsa, new IntArrayList(), linearized, offsets);
233
234 /*
235 * Probe for better node arrangements by selecting between [lower, upper]
236 * nodes from the potential candidate nodes list.
237 */
238 IntArrayList sublist = new IntArrayList();
239 sublist.buffer = states;
240 sublist.elementsCount = states.length;
241
242 /*
243 * Probe the initial region a little bit, looking for optimal cut. It can't be binary search
244 * because the result isn't monotonic.
245 */
246 log(Level.FINE, "Compacting, initial output size: %,d", serializedSize);
247 int cutAt = 0;
248 for (int cut = Math.min(25, states.length); cut <= Math.min(150, states.length); cut += 25) {
249 sublist.elementsCount = cut;
250 int newSize = linearizeAndCalculateOffsets(fsa, sublist, linearized, offsets);
251 log(Level.FINE, "Moved %,d states, output size: %,d", sublist.size(), newSize);
252 if (newSize >= serializedSize) {
253 break;
254 }
255 cutAt = cut;
256 }
257
258 /*
259 * Cut at the calculated point and repeat linearization.
260 */
261 sublist.elementsCount = cutAt;
262 int size = linearizeAndCalculateOffsets(fsa, sublist, linearized, offsets);
263 log(Level.FINE, "%,d states moved, final size: %,d", sublist.size(), size);
264 return linearized;
265 }
266
267 private void log(Level level, String msg, Object... args) {
268 logger.log(level, String.format(Locale.ROOT, msg, args));
269 }
270
271 /**
272 * Linearize all states, putting <code>states</code> in front of the automaton
273 * and calculating stable state offsets.
274 */
275 private int linearizeAndCalculateOffsets(FSA fsa, IntArrayList states, IntArrayList linearized,
276 IntIntHashMap offsets) throws IOException {
277 final BitSet visited = new BitSet();
278 final IntStack nodes = new IntStack();
279 linearized.clear();
280
281 /*
282 * Linearize states with most inlinks first.
283 */
284 for (int i = 0; i < states.size(); i++) {
285 linearizeState(fsa, nodes, linearized, visited, states.get(i));
286 }
287
288 /*
289 * Linearize the remaining states by chaining them one after another, in depth-order.
290 */
291 nodes.push(fsa.getRootNode());
292 while (!nodes.isEmpty()) {
293 final int node = nodes.pop();
294 if (visited.get(node))
295 continue;
296
297 linearizeState(fsa, nodes, linearized, visited, node);
298 }
299
300 /*
301 * Calculate new state offsets. This is iterative. We start with
302 * maximum potential offsets and recalculate until converged.
303 */
304 int MAX_OFFSET = Integer.MAX_VALUE;
305 for (IntCursor c : linearized) {
306 offsets.put(c.value, MAX_OFFSET);
307 }
308
309 int i, j = 0;
310 while ((i = emitNodes(fsa, null, linearized)) > 0) {
311 j = i;
312 }
313 return j;
314 }
315
316 /**
317 * Add a state to linearized list.
318 */
319 private void linearizeState(final FSA fsa, IntStack nodes, IntArrayList linearized, BitSet visited, int node) {
320 linearized.add(node);
321 visited.set(node);
322 for (int arc = fsa.getFirstArc(node); arc != 0; arc = fsa.getNextArc(arc)) {
323 if (!fsa.isArcTerminal(arc)) {
324 final int target = fsa.getEndNode(arc);
325 if (!visited.get(target))
326 nodes.push(target);
327 }
328 }
329 }
330
331 /**
332 * Compute the set of states that should be linearized first to minimize other
333 * states goto length.
334 */
335 private int[] computeFirstStates(IntIntHashMap inlinkCount, int maxStates, int minInlinkCount) {
336 Comparator<IntIntHolder> comparator = new Comparator<FSAUtils.IntIntHolder>() {
337 public int compare(IntIntHolder o1, IntIntHolder o2) {
338 int v = o1.a - o2.a;
339 return v == 0 ? (o1.b - o2.b) : v;
340 }
341 };
342
343 PriorityQueue<IntIntHolder> stateInlink = new PriorityQueue<IntIntHolder>(1, comparator);
344 IntIntHolder scratch = new IntIntHolder();
345 for (IntIntCursor c : inlinkCount) {
346 if (c.value > minInlinkCount) {
347 scratch.a = c.value;
348 scratch.b = c.key;
349
350 if (stateInlink.size() < maxStates || comparator.compare(scratch, stateInlink.peek()) > 0) {
351 stateInlink.add(new IntIntHolder(c.value, c.key));
352 if (stateInlink.size() > maxStates) {
353 stateInlink.remove();
354 }
355 }
356 }
357 }
358
359 int [] states = new int [stateInlink.size()];
360 for (int position = states.length; !stateInlink.isEmpty();) {
361 IntIntHolder i = stateInlink.remove();
362 states[--position] = i.b;
363 }
364
365 return states;
366 }
367
368 /**
369 * Compute in-link count for each state.
370 */
371 private IntIntHashMap computeInlinkCount(final FSA fsa) {
372 IntIntHashMap inlinkCount = new IntIntHashMap();
373 BitSet visited = new BitSet();
374 IntStack nodes = new IntStack();
375 nodes.push(fsa.getRootNode());
376
377 while (!nodes.isEmpty()) {
378 final int node = nodes.pop();
379 if (visited.get(node))
380 continue;
381
382 visited.set(node);
383
384 for (int arc = fsa.getFirstArc(node); arc != 0; arc = fsa.getNextArc(arc)) {
385 if (!fsa.isArcTerminal(arc)) {
386 final int target = fsa.getEndNode(arc);
387 inlinkCount.putOrAdd(target, 1, 1);
388 if (!visited.get(target))
389 nodes.push(target);
390 }
391 }
392 }
393
394 return inlinkCount;
395 }
396
397 /**
398 * Update arc offsets assuming the given goto length.
399 */
400 private int emitNodes(FSA fsa, OutputStream os, IntArrayList linearized) throws IOException {
401 int offset = 0;
402
403 // Add epsilon state.
404 offset += emitNodeData(os, 0);
405 if (fsa.getRootNode() != 0)
406 offset += emitArc(os, BIT_LAST_ARC, (byte) '^', offsets.get(fsa.getRootNode()));
407 else
408 offset += emitArc(os, BIT_LAST_ARC, (byte) '^', 0);
409
410 boolean offsetsChanged = false;
411 final int max = linearized.size();
412 for (IntCursor c : linearized) {
413 final int state = c.value;
414 final int nextState = c.index + 1 < max ? linearized.get(c.index + 1) : NO_STATE;
415
416 if (os == null) {
417 offsetsChanged |= (offsets.get(state) != offset);
418 offsets.put(state, offset);
419 } else {
420 assert offsets.get(state) == offset : state + " " + offsets.get(state) + " " + offset;
421 }
422
423 offset += emitNodeData(os, withNumbers ? numbers.get(state) : 0);
424 offset += emitNodeArcs(fsa, os, state, nextState);
425 }
426
427 return offsetsChanged ? offset : 0;
428 }
429
430 /**
431 * Emit all arcs of a single node.
432 */
433 private int emitNodeArcs(FSA fsa, OutputStream os, final int state, final int nextState) throws IOException {
434 int offset = 0;
435 for (int arc = fsa.getFirstArc(state); arc != 0; arc = fsa.getNextArc(arc)) {
436 int targetOffset;
437 final int target;
438
439 if (fsa.isArcTerminal(arc)) {
440 target = 0;
441 targetOffset = 0;
442 } else {
443 target = fsa.getEndNode(arc);
444 targetOffset = offsets.get(target);
445 }
446
447 int flags = 0;
448
449 if (fsa.isArcFinal(arc)) {
450 flags |= BIT_FINAL_ARC;
451 }
452
453 if (fsa.getNextArc(arc) == 0) {
454 flags |= BIT_LAST_ARC;
455 }
456
457 if (targetOffset != 0 && target == nextState) {
458 flags |= BIT_TARGET_NEXT;
459 targetOffset = 0;
460 }
461
462 offset += emitArc(os, flags, fsa.getArcLabel(arc), targetOffset);
463 }
464
465 return offset;
466 }
467
468 /** */
469 private int emitArc(OutputStream os, int flags, byte label, int targetOffset) throws IOException {
470 int length = 0;
471
472 int labelIndex = labelsInvIndex[label & 0xff];
473 if (labelIndex > 0) {
474 if (os != null)
475 os.write(flags | labelIndex);
476 length++;
477 } else {
478 if (os != null) {
479 os.write(flags);
480 os.write(label);
481 }
482 length += 2;
483 }
484
485 if ((flags & BIT_TARGET_NEXT) == 0) {
486 int len = writeVInt(scratch, 0, targetOffset);
487 if (os != null) {
488 os.write(scratch, 0, len);
489 }
490 length += len;
491 }
492
493 return length;
494 }
495
496 /** */
497 private int emitNodeData(OutputStream os, int number) throws IOException {
498 int size = 0;
499
500 if (withNumbers) {
501 size = writeVInt(scratch, 0, number);
502 if (os != null) {
503 os.write(scratch, 0, size);
504 }
505 }
506
507 return size;
508 }
509
510 /** */
511 @Override
512 public CFSA2Serializer withFiller(byte filler) {
513 throw new UnsupportedOperationException("CFSA2 does not support filler. Use .info file.");
514 }
515
516 /** */
517 @Override
518 public CFSA2Serializer withAnnotationSeparator(byte annotationSeparator) {
519 throw new UnsupportedOperationException("CFSA2 does not support separator. Use .info file.");
520 }
521
522 /**
523 * Write a v-int to a byte array.
524 */
525 static int writeVInt(byte[] array, int offset, int value) {
526 assert value >= 0 : "Can't v-code negative ints.";
527
528 while (value > 0x7F) {
529 array[offset++] = (byte) (0x80 | (value & 0x7F));
530 value >>= 7;
531 }
532 array[offset++] = (byte) value;
533
534 return offset;
535 }
536 }