Debian Codegraph @

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

raw
1 package morfologik.fsa.builders;
2
3 import static morfologik.fsa.FSAFlags.*;
4
5 import java.io.IOException;
6 import java.io.OutputStream;
7 import java.nio.ByteBuffer;
8 import java.util.Arrays;
9 import java.util.BitSet;
10 import java.util.EnumSet;
11 import java.util.Set;
12
13 import morfologik.fsa.FSA;
14 import morfologik.fsa.FSA5;
15 import morfologik.fsa.FSAFlags;
16 import morfologik.fsa.FSAHeader;
17
18 import com.carrotsearch.hppc.IntIntHashMap;
19 import com.carrotsearch.hppc.IntStack;
20
21 /**
22 * Serializes in-memory {@link FSA} graphs to a binary format compatible with
23 * Jan Daciuk's <code>fsa</code>'s package <code>FSA5</code> format.
24 *
25 * <p>
26 * It is possible to serialize the automaton with numbers required for perfect
27 * hashing. See {@link #withNumbers()} method.
28 * </p>
29 *
30 * @see FSA5
31 * @see FSA#read(java.io.InputStream)
32 */
33 public final class FSA5Serializer implements FSASerializer {
34 /**
35 * Maximum number of bytes for a serialized arc.
36 */
37 private final static int MAX_ARC_SIZE = 1 + 5;
38
39 /**
40 * Maximum number of bytes for per-node data.
41 */
42 private final static int MAX_NODE_DATA_SIZE = 16;
43
44 /**
45 * Number of bytes for the arc's flags header (arc representation without the
46 * goto address).
47 */
48 private final static int SIZEOF_FLAGS = 1;
49
50 /**
51 * Supported flags.
52 */
53 private final static EnumSet<FSAFlags> flags = EnumSet.of(NUMBERS, SEPARATORS, FLEXIBLE, STOPBIT, NEXTBIT);
54
55 /**
56 * @see FSA5#filler
57 */
58 public byte fillerByte = FSA5.DEFAULT_FILLER;
59
60 /**
61 * @see FSA5#annotation
62 */
63 public byte annotationByte = FSA5.DEFAULT_ANNOTATION;
64
65 /**
66 * <code>true</code> if we should serialize with numbers.
67 *
68 * @see #withNumbers()
69 */
70 private boolean withNumbers;
71
72 /**
73 * A hash map of [state, offset] pairs.
74 */
75 private IntIntHashMap offsets = new IntIntHashMap();
76
77 /**
78 * A hash map of [state, right-language-count] pairs.
79 */
80 private IntIntHashMap numbers = new IntIntHashMap();
81
82 /**
83 * Serialize the automaton with the number of right-language sequences in each
84 * node. This is required to implement perfect hashing. The numbering also
85 * preserves the order of input sequences.
86 *
87 * @return Returns the same object for easier call chaining.
88 */
89 public FSA5Serializer withNumbers() {
90 withNumbers = true;
91 return this;
92 }
93
94 /**
95 * {@inheritDoc}
96 */
97 @Override
98 public FSA5Serializer withFiller(byte filler) {
99 this.fillerByte = filler;
100 return this;
101 }
102
103 /**
104 * {@inheritDoc}
105 */
106 @Override
107 public FSA5Serializer withAnnotationSeparator(byte annotationSeparator) {
108 this.annotationByte = annotationSeparator;
109 return this;
110 }
111
112 /**
113 * Serialize root state <code>s</code> to an output stream in
114 * <code>FSA5</code> format.
115 *
116 * @see #withNumbers()
117 * @return Returns <code>os</code> for chaining.
118 */
119 @Override
120 public <T extends OutputStream> T serialize(final FSA fsa, T os) throws IOException {
121
122 // Prepare space for arc offsets and linearize all the states.
123 int[] linearized = linearize(fsa);
124
125 /*
126 * Calculate the number of bytes required for the node data, if
127 * serializing with numbers.
128 */
129 int nodeDataLength = 0;
130 if (withNumbers) {
131 this.numbers = FSAUtils.rightLanguageForAllStates(fsa);
132 int maxNumber = numbers.get(fsa.getRootNode());
133 while (maxNumber > 0) {
134 nodeDataLength++;
135 maxNumber >>>= 8;
136 }
137 }
138
139 // Calculate minimal goto length.
140 int gtl = 1;
141 while (true) {
142 // First pass: calculate offsets of states.
143 if (!emitArcs(fsa, null, linearized, gtl, nodeDataLength)) {
144 gtl++;
145 continue;
146 }
147
148 // Second pass: check if goto overflows anywhere.
149 if (emitArcs(fsa, null, linearized, gtl, nodeDataLength))
150 break;
151
152 gtl++;
153 }
154
155 /*
156 * Emit the header.
157 */
158 FSAHeader.write(os, FSA5.VERSION);
159 os.write(fillerByte);
160 os.write(annotationByte);
161 os.write((nodeDataLength << 4) | gtl);
162
163 /*
164 * Emit the automaton.
165 */
166 boolean gtlUnchanged = emitArcs(fsa, os, linearized, gtl, nodeDataLength);
167 assert gtlUnchanged : "gtl changed in the final pass.";
168
169 return os;
170 }
171
172 /**
173 * Return supported flags.
174 */
175 @Override
176 public Set<FSAFlags> getFlags() {
177 return flags;
178 }
179
180 /**
181 * Linearization of states.
182 */
183 private int[] linearize(final FSA fsa) {
184 int[] linearized = new int[0];
185 int last = 0;
186
187 BitSet visited = new BitSet();
188 IntStack nodes = new IntStack();
189 nodes.push(fsa.getRootNode());
190
191 while (!nodes.isEmpty()) {
192 final int node = nodes.pop();
193 if (visited.get(node)) {
194 continue;
195 }
196
197 if (last >= linearized.length) {
198 linearized = Arrays.copyOf(linearized, linearized.length + 100000);
199 }
200
201 visited.set(node);
202 linearized[last++] = node;
203
204 for (int arc = fsa.getFirstArc(node); arc != 0; arc = fsa.getNextArc(arc)) {
205 if (!fsa.isArcTerminal(arc)) {
206 int target = fsa.getEndNode(arc);
207 if (!visited.get(target))
208 nodes.push(target);
209 }
210 }
211 }
212
213 return Arrays.copyOf(linearized, last);
214 }
215
216 /**
217 * Update arc offsets assuming the given goto length.
218 */
219 private boolean emitArcs(FSA fsa, OutputStream os, int[] linearized, int gtl, int nodeDataLength) throws IOException {
220 final ByteBuffer bb = ByteBuffer.allocate(Math.max(MAX_NODE_DATA_SIZE, MAX_ARC_SIZE));
221
222 int offset = 0;
223
224 // Add dummy terminal state.
225 offset += emitNodeData(bb, os, nodeDataLength, 0);
226 offset += emitArc(bb, os, gtl, 0, (byte) 0, 0);
227
228 // Add epsilon state.
229 offset += emitNodeData(bb, os, nodeDataLength, 0);
230 if (fsa.getRootNode() != 0)
231 offset += emitArc(bb, os, gtl, FSA5.BIT_LAST_ARC | FSA5.BIT_TARGET_NEXT, (byte) '^', 0);
232 else
233 offset += emitArc(bb, os, gtl, FSA5.BIT_LAST_ARC, (byte) '^', 0);
234
235 int maxStates = linearized.length;
236 for (int j = 0; j < maxStates; j++) {
237 final int s = linearized[j];
238
239 if (os == null) {
240 offsets.put(s, offset);
241 } else {
242 assert offsets.get(s) == offset : s + " " + offsets.get(s) + " " + offset;
243 }
244
245 offset += emitNodeData(bb, os, nodeDataLength, withNumbers ? numbers.get(s) : 0);
246
247 for (int arc = fsa.getFirstArc(s); arc != 0; arc = fsa.getNextArc(arc)) {
248 int targetOffset;
249 final int target;
250 if (fsa.isArcTerminal(arc)) {
251 targetOffset = 0;
252 target = 0;
253 } else {
254 target = fsa.getEndNode(arc);
255 targetOffset = offsets.get(target);
256 }
257
258 int flags = 0;
259 if (fsa.isArcFinal(arc)) {
260 flags |= FSA5.BIT_FINAL_ARC;
261 }
262
263 if (fsa.getNextArc(arc) == 0) {
264 flags |= FSA5.BIT_LAST_ARC;
265
266 if (j + 1 < maxStates && target == linearized[j + 1] && targetOffset != 0) {
267 flags |= FSA5.BIT_TARGET_NEXT;
268 targetOffset = 0;
269 }
270 }
271
272 int bytes = emitArc(bb, os, gtl, flags, fsa.getArcLabel(arc), targetOffset);
273 if (bytes < 0)
274 // gtl too small. interrupt eagerly.
275 return false;
276
277 offset += bytes;
278 }
279 }
280
281 return true;
282 }
283
284 /** */
285 private int emitArc(ByteBuffer bb, OutputStream os, int gtl, int flags, byte label, int targetOffset)
286 throws IOException {
287 int arcBytes = (flags & FSA5.BIT_TARGET_NEXT) != 0 ? SIZEOF_FLAGS : gtl;
288
289 flags |= (targetOffset << 3);
290 bb.put(label);
291 for (int b = 0; b < arcBytes; b++) {
292 bb.put((byte) flags);
293 flags >>>= 8;
294 }
295
296 if (flags != 0) {
297 // gtl too small. interrupt eagerly.
298 return -1;
299 }
300
301 bb.flip();
302 int bytes = bb.remaining();
303 if (os != null) {
304 os.write(bb.array(), bb.position(), bb.remaining());
305 }
306 bb.clear();
307
308 return bytes;
309 }
310
311 /** */
312 private int emitNodeData(ByteBuffer bb, OutputStream os, int nodeDataLength, int number) throws IOException {
313 if (nodeDataLength > 0 && os != null) {
314 for (int i = 0; i < nodeDataLength; i++) {
315 bb.put((byte) number);
316 number >>>= 8;
317 }
318
319 bb.flip();
320 os.write(bb.array(), bb.position(), bb.remaining());
321 bb.clear();
322 }
323
324 return nodeDataLength;
325 }
326 }