Class CFSA2

java.lang.Object
morfologik.fsa.FSA
morfologik.fsa.CFSA2
All Implemented Interfaces:
Iterable<ByteBuffer>

public final class CFSA2 extends FSA
CFSA (Compact Finite State Automaton) binary format implementation, version 2:
  • BIT_TARGET_NEXT applicable on all arcs, not necessarily the last one.
  • v-coded goto field
  • v-coded perfect hashing numbers, if any
  • 31 most frequent labels integrated with flags byte

The encoding of automaton body is as follows.

 ---- CFSA header
 Byte                            Description 
       +-+-+-+-+-+-+-+-+\
     0 | | | | | | | | | +------ '\'
       +-+-+-+-+-+-+-+-+/
       +-+-+-+-+-+-+-+-+\
     1 | | | | | | | | | +------ 'f'
       +-+-+-+-+-+-+-+-+/
       +-+-+-+-+-+-+-+-+\
     2 | | | | | | | | | +------ 's'
       +-+-+-+-+-+-+-+-+/
       +-+-+-+-+-+-+-+-+\
     3 | | | | | | | | | +------ 'a'
       +-+-+-+-+-+-+-+-+/
       +-+-+-+-+-+-+-+-+\
     4 | | | | | | | | | +------ version (fixed 0xc6)
       +-+-+-+-+-+-+-+-+/
       +-+-+-+-+-+-+-+-+\
     5 | | | | | | | | | +----\
       +-+-+-+-+-+-+-+-+/      \ flags [MSB first]
       +-+-+-+-+-+-+-+-+\      /
     6 | | | | | | | | | +----/
       +-+-+-+-+-+-+-+-+/
       +-+-+-+-+-+-+-+-+\
     7 | | | | | | | | | +------ label lookup table size
       +-+-+-+-+-+-+-+-+/
       +-+-+-+-+-+-+-+-+\
  8-32 | | | | | | | | | +------ label value lookup table 
       : : : : : : : : : |
       +-+-+-+-+-+-+-+-+/
 
 ---- Start of a node; only if automaton was compiled with NUMBERS option.
 
 Byte
        +-+-+-+-+-+-+-+-+\
      0 | | | | | | | | | \  
        +-+-+-+-+-+-+-+-+  +
      1 | | | | | | | | |  |      number of strings recognized
        +-+-+-+-+-+-+-+-+  +----- by the automaton starting
        : : : : : : : : :  |      from this node. v-coding
        +-+-+-+-+-+-+-+-+  +
        | | | | | | | | | /  
        +-+-+-+-+-+-+-+-+/

 ---- A vector of this node's arcs. An arc's layout depends on the combination of flags.
 
 1) NEXT bit set, mapped arc label. 
 
        +----------------------- node pointed to is next
        | +--------------------- the last arc of the node
        | | +------------------- this arc leads to a final state (acceptor)
        | | |  _______+--------- arc's label; indexed if M > 0, otherwise explicit label follows
        | | | / | | | |
       +-+-+-+-+-+-+-+-+\
     0 |N|L|F|M|M|M|M|M| +------ flags + (M) index of the mapped label.
       +-+-+-+-+-+-+-+-+/
       +-+-+-+-+-+-+-+-+\
     1 | | | | | | | | | +------ optional label if M == 0
       +-+-+-+-+-+-+-+-+/
       : : : : : : : : :
       +-+-+-+-+-+-+-+-+\
       |A|A|A|A|A|A|A|A| +------ v-coded goto address
       +-+-+-+-+-+-+-+-+/
 
  • Field Details

    • VERSION

      public static final byte VERSION
      Automaton header version value.
      See Also:
    • BIT_TARGET_NEXT

      public static final int BIT_TARGET_NEXT
      The target node of this arc follows the last arc of the current state (no goto field).
      See Also:
    • BIT_LAST_ARC

      public static final int BIT_LAST_ARC
      The arc is the last one from the current node's arcs list.
      See Also:
    • BIT_FINAL_ARC

      public static final int BIT_FINAL_ARC
      The arc corresponds to the last character of a sequence available when building the automaton (acceptor transition).
      See Also:
    • LABEL_INDEX_BITS

      static final int LABEL_INDEX_BITS
      The count of bits assigned to storing an indexed label.
      See Also:
    • LABEL_INDEX_MASK

      static final int LABEL_INDEX_MASK
      Masks only the M bits of a flag byte.
      See Also:
    • LABEL_INDEX_SIZE

      public static final int LABEL_INDEX_SIZE
      Maximum size of the labels index.
      See Also:
    • arcs

      public byte[] arcs
      An 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.
    • flags

      private final EnumSet<FSAFlags> flags
      Flags for this automaton version.
    • labelMapping

      public final byte[] labelMapping
      Label mapping for M-indexed labels.
    • hasNumbers

      private final boolean hasNumbers
      If true states are prepended with numbers.
    • epsilon

      private final int epsilon
      Epsilon node's offset.
      See Also:
  • Constructor Details

  • Method Details

    • getRootNode

      public int getRootNode()
      Specified by:
      getRootNode in class FSA
      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 class FSA
      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 class FSA
      Parameters:
      arc - The arc's identifier.
      Returns:
      Returns the identifier of the next arc after arc and leaving node. Zero is returned if no more arcs are available for the node.
    • getArc

      public int getArc(int node, byte label)
      Specified by:
      getArc in class FSA
      Parameters:
      node - Identifier of the node.
      label - The arc's label.
      Returns:
      Returns the identifier of an arc leaving node and labeled with label. An identifier equal to 0 means the node has no outgoing arc labeled label.
    • getEndNode

      public int getEndNode(int arc)
      Specified by:
      getEndNode in class FSA
      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 class FSA
      Parameters:
      arc - The arc's identifier.
      Returns:
      Return the label associated with a given arc.
    • getRightLanguageCount

      public int getRightLanguageCount(int node)
      Overrides:
      getRightLanguageCount in class FSA
      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 class FSA
      Parameters:
      arc - The arc's identifier.
      Returns:
      Returns true if the destination node at the end of this arc corresponds to an input sequence created when building this automaton.
    • isArcTerminal

      public boolean isArcTerminal(int arc)
      Specified by:
      isArcTerminal in class FSA
      Parameters:
      arc - The arc's identifier.
      Returns:
      Returns true if this arc does not have a terminating node (@link FSA.getEndNode(int) will throw an exception). Implies FSA.isArcFinal(int).
    • isArcLast

      public boolean isArcLast(int arc)
      Returns true if this arc has NEXT 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:
    • getFlags

      public Set<FSAFlags> getFlags()
      Specified by:
      getFlags in class FSA
      Returns:
      Returns a set of flags for this FSA instance.
    • 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.
    • readVInt

      static int readVInt(byte[] array, int offset)
      Read a v-int.
    • vIntLength

      static int vIntLength(int value)
      Return the byte-length of a v-coded int.
    • skipVInt

      private int skipVInt(int offset)
      Skip a v-int.