Package morfologik.fsa
Class CFSA
java.lang.Object
morfologik.fsa.FSA
morfologik.fsa.CFSA
- All Implemented Interfaces:
Iterable<ByteBuffer>
CFSA (Compact Finite State Automaton) binary format implementation. This is a
slightly reorganized version of
FSA5
offering smaller automata size
at some (minor) performance penalty.
Note: Serialize to CFSA2
for new code.
The encoding of automaton body is as follows.
---- FSA header (standard) Byte Description +-+-+-+-+-+-+-+-+\ 0 | | | | | | | | | +------ '\' +-+-+-+-+-+-+-+-+/ +-+-+-+-+-+-+-+-+\ 1 | | | | | | | | | +------ 'f' +-+-+-+-+-+-+-+-+/ +-+-+-+-+-+-+-+-+\ 2 | | | | | | | | | +------ 's' +-+-+-+-+-+-+-+-+/ +-+-+-+-+-+-+-+-+\ 3 | | | | | | | | | +------ 'a' +-+-+-+-+-+-+-+-+/ +-+-+-+-+-+-+-+-+\ 4 | | | | | | | | | +------ version (fixed 0xc5) +-+-+-+-+-+-+-+-+/ +-+-+-+-+-+-+-+-+\ 5 | | | | | | | | | +------ filler character +-+-+-+-+-+-+-+-+/ +-+-+-+-+-+-+-+-+\ 6 | | | | | | | | | +------ annot character +-+-+-+-+-+-+-+-+/ +-+-+-+-+-+-+-+-+\ 7 |C|C|C|C|G|G|G|G| +------ C - node data size (ctl), G - address size (gotoLength) +-+-+-+-+-+-+-+-+/ +-+-+-+-+-+-+-+-+\ 8-32 | | | | | | | | | +------ labels mapped for type (1) of arc encoding. : : : : : : : : : | +-+-+-+-+-+-+-+-+/ ---- Start of a node; only if automaton was compiled with NUMBERS option. Byte +-+-+-+-+-+-+-+-+\ 0 | | | | | | | | | \ LSB +-+-+-+-+-+-+-+-+ + 1 | | | | | | | | | | number of strings recognized +-+-+-+-+-+-+-+-+ +----- by the automaton starting : : : : : : : : : | from this node. +-+-+-+-+-+-+-+-+ + ctl-1 | | | | | | | | | / MSB +-+-+-+-+-+-+-+-+/ ---- A vector of node's arcs. Conditional format, depending on flags. 1) NEXT bit set, mapped arc label. +--------------- arc's label mapped in M bits if M's field value > 0 | +------------- node pointed to is next | | +----------- the last arc of the node _______| | | +--------- the arc is final / | | | | +-+-+-+-+-+-+-+-+\ 0 |M|M|M|M|M|1|L|F| +------ flags + (M) index of the mapped label. +-+-+-+-+-+-+-+-+/ 2) NEXT bit set, label separate. +--------------- arc's label stored separately (M's field is zero). | +------------- node pointed to is next | | +----------- the last arc of the node | | | +--------- the arc is final | | | | +-+-+-+-+-+-+-+-+\ 0 |0|0|0|0|0|1|L|F| +------ flags +-+-+-+-+-+-+-+-+/ +-+-+-+-+-+-+-+-+\ 1 | | | | | | | | | +------ label +-+-+-+-+-+-+-+-+/ 3) NEXT bit not set. Full arc. +------------- node pointed to is next | +----------- the last arc of the node | | +--------- the arc is final | | | +-+-+-+-+-+-+-+-+\ 0 |A|A|A|A|A|0|L|F| +------ flags + (A) address field, lower bits +-+-+-+-+-+-+-+-+/ +-+-+-+-+-+-+-+-+\ 1 | | | | | | | | | +------ label +-+-+-+-+-+-+-+-+/ : : : : : : : : : +-+-+-+-+-+-+-+-+\ gtl-1 |A|A|A|A|A|A|A|A| +------ address, continuation (MSB) +-+-+-+-+-+-+-+-+/
-
Field Summary
FieldsModifier and TypeFieldDescriptionbyte[]
An array of bytes with the internal representation of the automaton.static final int
Bitmask indicating that an arc corresponds to the last character of a sequence available when building the automaton.static final int
Bitmask indicating that an arc is the last one of the node's list and the following one belongs to another node.static final int
Bitmask indicating that the target node of this arc follows it in the compressed automaton structure (no goto field).Flags for this automaton version.final int
Number of bytes each address takes in full, expanded form (goto length).final byte[]
Label mapping for arcs of type (1) (see class documentation).final int
The length of the node header structure (if the automaton was compiled withNUMBERS
option).static final byte
Automaton header version value. -
Constructor Summary
ConstructorsConstructorDescriptionCFSA
(InputStream stream) Creates a new automaton, reading it from a file in FSA format, version 5. -
Method Summary
Modifier and TypeMethodDescriptionint
getArc
(int node, byte label) byte
getArcLabel
(int arc) (package private) final int
getDestinationNodeOffset
(int arc) Returns the address of the node pointed to by this arc.int
getEndNode
(int arc) final int
getFirstArc
(int node) getFlags()
final int
getNextArc
(int arc) int
getRightLanguageCount
(int node) int
Returns the start node of this automaton.boolean
isArcFinal
(int arc) boolean
isArcLast
(int arc) Returnstrue
if this arc hasNEXT
bit set.boolean
isArcTerminal
(int arc) boolean
isLabelCompressed
(int arc) boolean
isNextSet
(int arc) private int
skipArc
(int offset) Read the arc's layout and skip as many bytes, as needed, to skip it.Methods inherited from class morfologik.fsa.FSA
getArcCount, getSequences, getSequences, iterator, read, read, readRemaining, visitAllStates, visitInPostOrder, visitInPostOrder, visitInPreOrder, visitInPreOrder
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface java.lang.Iterable
forEach, spliterator
-
Field Details
-
VERSION
public static final byte VERSIONAutomaton header version value.- See Also:
-
BIT_FINAL_ARC
public static final int BIT_FINAL_ARCBitmask indicating that an arc corresponds to the last character of a sequence available when building the automaton.- See Also:
-
BIT_LAST_ARC
public static final int BIT_LAST_ARCBitmask indicating that an arc is the last one of the node's list and the following one belongs to another node.- See Also:
-
BIT_TARGET_NEXT
public static final int BIT_TARGET_NEXTBitmask indicating that the target node of this arc follows it in the compressed automaton structure (no goto field).- See Also:
-
arcs
public byte[] arcsAn array of bytes with the internal representation of the automaton. Please see the documentation of this class for more information on how this structure is organized. -
nodeDataLength
public final int nodeDataLengthThe length of the node header structure (if the automaton was compiled withNUMBERS
option). Otherwise zero. -
flags
Flags for this automaton version. -
gtl
public final int gtlNumber of bytes each address takes in full, expanded form (goto length). -
labelMapping
public final byte[] labelMappingLabel mapping for arcs of type (1) (see class documentation). The array is indexed by mapped label's value and contains the original label.
-
-
Constructor Details
-
CFSA
CFSA(InputStream stream) throws IOException Creates a new automaton, reading it from a file in FSA format, version 5.- Throws:
IOException
-
-
Method Details
-
getRootNode
public int getRootNode()Returns the start node of this automaton. May return0
if the start node is also an end node.- Specified by:
getRootNode
in classFSA
- Returns:
- Returns the identifier of the root node of this automaton. Returns 0 if the start node is also the end node (the automaton is empty).
-
getFirstArc
public final int getFirstArc(int node) - Specified by:
getFirstArc
in classFSA
- Parameters:
node
- Identifier of the node.- Returns:
- Returns the identifier of the first arc leaving
node
or 0 if the node has no outgoing arcs.
-
getNextArc
public final int getNextArc(int arc) - Specified by:
getNextArc
in classFSA
- Parameters:
arc
- The arc's identifier.- Returns:
- Returns the identifier of the next arc after
arc
and leavingnode
. Zero is returned if no more arcs are available for the node.
-
getArc
public int getArc(int node, byte label) -
getEndNode
public int getEndNode(int arc) - Specified by:
getEndNode
in classFSA
- Parameters:
arc
- The arc's identifier.- Returns:
- Return the end node pointed to by a given
arc
. Terminal arcs (those that point to a terminal state) have no end node representation and throw a runtime exception.
-
getArcLabel
public byte getArcLabel(int arc) - Specified by:
getArcLabel
in classFSA
- Parameters:
arc
- The arc's identifier.- Returns:
- Return the label associated with a given
arc
.
-
getRightLanguageCount
public int getRightLanguageCount(int node) - Overrides:
getRightLanguageCount
in classFSA
- Parameters:
node
- Identifier of the node.- Returns:
- Returns the number of sequences reachable from the given state if
the automaton was compiled with
FSAFlags.NUMBERS
. The size of the right language of the state, in other words.
-
isArcFinal
public boolean isArcFinal(int arc) - Specified by:
isArcFinal
in classFSA
- Parameters:
arc
- The arc's identifier.- Returns:
- Returns
true
if the destination node at the end of thisarc
corresponds to an input sequence created when building this automaton.
-
isArcTerminal
public boolean isArcTerminal(int arc) - Specified by:
isArcTerminal
in classFSA
- Parameters:
arc
- The arc's identifier.- Returns:
- Returns
true
if thisarc
does not have a terminating node (@linkFSA.getEndNode(int)
will throw an exception). ImpliesFSA.isArcFinal(int)
.
-
isArcLast
public boolean isArcLast(int arc) Returnstrue
if this arc hasNEXT
bit set.- Parameters:
arc
- The node's arc identifier.- Returns:
- Returns true if the argument is the last arc of a node.
- See Also:
-
isNextSet
public boolean isNextSet(int arc) - Parameters:
arc
- The node's arc identifier.- Returns:
- Returns true if
BIT_TARGET_NEXT
is set for this arc. - See Also:
-
isLabelCompressed
public boolean isLabelCompressed(int arc) - Parameters:
arc
- The node's arc identifier.- Returns:
- Returns
true
if the label is compressed inside flags byte.
-
getFlags
For this automaton version, an additional
FSAFlags.NUMBERS
flag may be set to indicate the automaton contains extra fields for each node. -
getDestinationNodeOffset
final int getDestinationNodeOffset(int arc) Returns the address of the node pointed to by this arc. -
skipArc
private int skipArc(int offset) Read the arc's layout and skip as many bytes, as needed, to skip it.
-