| 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 |
} |