Package org.apache.lucene.util.fst

Class FST<T>

java.lang.Object

org.apache.lucene.util.fst.FST<T>

All Implemented Interfaces:

Accountable

public final class FST<T>
extends Object
implements Accountable

Represents an finite state machine (FST), using a compact byte[] format.

The format is similar to what's used by Morfologik (https://github.com/morfologik/morfologik-stemming).

See the package documentation for some simple examples.

WARNING: This API is experimental and might change in incompatible ways in the next release.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static final class	FST.Arc<T>	Represents a single arc.
static class	FST.BytesReader	Reads bytes stored in an FST.
static enum	FST.INPUT_TYPE	Specifies allowed range of each int input label for this FST.

Field Summary

Fields

Modifier and Type	Field	Description
static final byte	ARCS_FOR_BINARY_SEARCH	Value of the arc flags to declare a node with fixed length arcs designed for binary search.
static final int	BIT_ARC_HAS_OUTPUT	This flag is set if the arc has an output.
static final int	END_LABEL	If arc has this label then that arc is final/accepted
final Outputs<T>	outputs

Fields inherited from interface org.apache.lucene.util.Accountable

NULL_ACCOUNTABLE

Constructor Summary

Constructors

Constructor	Description
FST(DataInput metaIn, DataInput in, Outputs<T> outputs)	Load a previously saved FST.
FST(DataInput metaIn, DataInput in, Outputs<T> outputs, FSTStore fstStore)	Load a previously saved FST; maxBlockBits allows you to control the size of the byte[] pages used to hold the FST bytes.

Method Summary

Modifier and Type	Method	Description
FST.Arc<T>	findTargetArc(int labelToMatch, FST.Arc<T> follow, FST.Arc<T> arc, FST.BytesReader in)	Finds an arc leaving the incoming arc, replacing the arc in place.
FST.BytesReader	getBytesReader()	Returns a FST.BytesReader for this FST, positioned at position 0.
T	getEmptyOutput()
FST.Arc<T>	getFirstArc(FST.Arc<T> arc)	Fills virtual 'start' arc, ie, an empty incoming arc to the FST's start node
long	ramBytesUsed()	Return the memory usage of this object in bytes.
static <T> FST<T>	read(Path path, Outputs<T> outputs)	Reads an automaton from a file.
FST.Arc<T>	readArcByDirectAddressing(FST.Arc<T> arc, FST.BytesReader in, int rangeIndex)	Reads a present direct addressing node arc, with the provided index in the label range.
FST.Arc<T>	readArcByIndex(FST.Arc<T> arc, FST.BytesReader in, int idx)
FST.Arc<T>	readFirstRealTargetArc(long nodeAddress, FST.Arc<T> arc, FST.BytesReader in)
FST.Arc<T>	readFirstTargetArc(FST.Arc<T> follow, FST.Arc<T> arc, FST.BytesReader in)	Follow the follow arc and read the first arc of its target; this changes the provided arc (2nd arg) in-place and returns it.
int	readLabel(DataInput in)	Reads one BYTE1/2/4 label from the provided DataInput.
FST.Arc<T>	readLastArcByDirectAddressing(FST.Arc<T> arc, FST.BytesReader in)	Reads the last arc of a direct addressing node.
FST.Arc<T>	readNextArc(FST.Arc<T> arc, FST.BytesReader in)	In-place read; returns the arc.
FST.Arc<T>	readNextRealArc(FST.Arc<T> arc, FST.BytesReader in)	Never returns null, but you should never call this if arc.isLast() is true.
void	save(Path path)	Writes an automaton to a file.
void	save(DataOutput metaOut, DataOutput out)
static <T> boolean	targetHasArcs(FST.Arc<T> arc)	returns true if the node at this address has any outgoing arcs
String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface org.apache.lucene.util.Accountable

getChildResources

Field Details

BIT_ARC_HAS_OUTPUT

public static final int BIT_ARC_HAS_OUTPUT

This flag is set if the arc has an output.

See Also:

• Constant Field Values

ARCS_FOR_BINARY_SEARCH

public static final byte ARCS_FOR_BINARY_SEARCH

Value of the arc flags to declare a node with fixed length arcs designed for binary search.

See Also:

• Constant Field Values

END_LABEL

public static final int END_LABEL

If arc has this label then that arc is final/accepted

See Also:

• Constant Field Values

outputs

public final Outputs<T> outputs

Constructor Details

FST

public FST(DataInput metaIn,
 DataInput in,
 Outputs<T> outputs)
    throws IOException

Load a previously saved FST.

Throws:

IOException

FST

public FST(DataInput metaIn,
 DataInput in,
 Outputs<T> outputs,
 FSTStore fstStore)
    throws IOException

Load a previously saved FST; maxBlockBits allows you to control the size of the byte[] pages used to hold the FST bytes.

Throws:

IOException

Method Details

ramBytesUsed

public long ramBytesUsed()

Description copied from interface: Accountable

Return the memory usage of this object in bytes. Negative values are illegal.

Specified by:

ramBytesUsed in interface Accountable

toString

public String toString()

Overrides:

toString in class Object

getEmptyOutput

public T getEmptyOutput()

save

public void save(DataOutput metaOut,
 DataOutput out)
          throws IOException

Throws:

IOException

save

public void save(Path path)
          throws IOException

Writes an automaton to a file.

Throws:

IOException

read

public static <T> FST<T> read(Path path,
 Outputs<T> outputs)
                       throws IOException

Reads an automaton from a file.

Throws:

IOException

readLabel

public int readLabel(DataInput in)
              throws IOException

Reads one BYTE1/2/4 label from the provided DataInput.

Throws:

IOException

targetHasArcs

public static <T> boolean targetHasArcs(FST.Arc<T> arc)

returns true if the node at this address has any outgoing arcs

getFirstArc

public FST.Arc<T> getFirstArc(FST.Arc<T> arc)

Fills virtual 'start' arc, ie, an empty incoming arc to the FST's start node

readFirstTargetArc

public FST.Arc<T> readFirstTargetArc(FST.Arc<T> follow,
 FST.Arc<T> arc,
 FST.BytesReader in)
                              throws IOException

Follow the follow arc and read the first arc of its target; this changes the provided arc (2nd arg) in-place and returns it.

Returns:

Returns the second argument (arc).

Throws:

IOException

readFirstRealTargetArc

public FST.Arc<T> readFirstRealTargetArc(long nodeAddress,
 FST.Arc<T> arc,
 FST.BytesReader in)
                                  throws IOException

Throws:

IOException

readNextArc

public FST.Arc<T> readNextArc(FST.Arc<T> arc,
 FST.BytesReader in)
                       throws IOException

In-place read; returns the arc.

Throws:

IOException

readArcByIndex

public FST.Arc<T> readArcByIndex(FST.Arc<T> arc,
 FST.BytesReader in,
 int idx)
                          throws IOException

Throws:

IOException

readArcByDirectAddressing

public FST.Arc<T> readArcByDirectAddressing(FST.Arc<T> arc,
 FST.BytesReader in,
 int rangeIndex)
                                     throws IOException

Reads a present direct addressing node arc, with the provided index in the label range.

Parameters:

rangeIndex - The index of the arc in the label range. It must be present. The real arc offset is computed based on the presence bits of the direct addressing node.

Throws:

IOException

readLastArcByDirectAddressing

public FST.Arc<T> readLastArcByDirectAddressing(FST.Arc<T> arc,
 FST.BytesReader in)
                                         throws IOException

Reads the last arc of a direct addressing node. This method is equivalent to call readArcByDirectAddressing(Arc, BytesReader, int) with rangeIndex equal to arc.numArcs() - 1, but it is faster.

Throws:

IOException

readNextRealArc

public FST.Arc<T> readNextRealArc(FST.Arc<T> arc,
 FST.BytesReader in)
                           throws IOException

Never returns null, but you should never call this if arc.isLast() is true.

Throws:

IOException

findTargetArc

public FST.Arc<T> findTargetArc(int labelToMatch,
 FST.Arc<T> follow,
 FST.Arc<T> arc,
 FST.BytesReader in)
                         throws IOException

Finds an arc leaving the incoming arc, replacing the arc in place. This returns null if the arc was not found, else the incoming arc.

Throws:

IOException

getBytesReader

public FST.BytesReader getBytesReader()

Returns a FST.BytesReader for this FST, positioned at position 0.