Module org.apache.lucene.core

Package org.apache.lucene.util.fst

Class FSTCompiler<T>

java.lang.Object

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

public class FSTCompiler<T>
extends Object

Builds a minimal FST (maps an IntsRef term to an arbitrary output) from pre-sorted terms with outputs. The FST becomes an FSA if you use NoOutputs. The FST is written on-the-fly into a compact serialized format byte array, which can be saved to / loaded from a Directory or used directly for traversal. The FST is always finite (no cycles).

NOTE: The algorithm is described at http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.3698

The parameterized type T is the output type. See the subclasses of Outputs.

FSTs larger than 2.1GB are now possible (as of Lucene 4.2). FSTs containing more than 2.1B nodes are also now possible, however they cannot be packed.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
(package private) static class	FSTCompiler.Arc<T>	Expert: holds a pending (seen but not yet serialized) arc.
static class	FSTCompiler.Builder<T>	Fluent-style constructor for FST FSTCompiler.
(package private) static final class	FSTCompiler.CompiledNode
(package private) static class	FSTCompiler.FixedLengthArcsBuffer	Reusable buffer for building nodes with fixed length arcs (binary search or direct addressing).
(package private) static interface	FSTCompiler.Node
(package private) static final class	FSTCompiler.UnCompiledNode<T>	Expert: holds a pending (seen but not yet serialized) Node.

Field Summary

Fields

Modifier and Type	Field	Description
(package private) final boolean	allowFixedLengthArcs
(package private) long	arcCount
(package private) long	binarySearchNodeCount
(package private) final BytesStore	bytes
(package private) long	continuousNodeCount
private final NodeHash<T>	dedupHash
private static final float	DIRECT_ADDRESSING_MAX_OVERSIZE_WITH_CREDIT_FACTOR	Maximum oversizing factor allowed for direct addressing compared to binary search when expansion credits allow the oversizing.
(package private) static final float	DIRECT_ADDRESSING_MAX_OVERSIZING_FACTOR
(package private) long	directAddressingExpansionCredit
(package private) final float	directAddressingMaxOversizingFactor
(package private) long	directAddressingNodeCount
(package private) static final int	FIXED_LENGTH_ARC_DEEP_NUM_ARCS
(package private) static final int	FIXED_LENGTH_ARC_SHALLOW_DEPTH
(package private) static final int	FIXED_LENGTH_ARC_SHALLOW_NUM_ARCS
(package private) final FSTCompiler.FixedLengthArcsBuffer	fixedLengthArcsBuffer
private FSTCompiler.UnCompiledNode<T>[]	frontier
(package private) final FST<T>	fst
(package private) long	lastFrozenNode
private final IntsRefBuilder	lastInput
private final T	NO_OUTPUT
(package private) long	nodeCount
(package private) int[]	numBytesPerArc
(package private) int[]	numLabelBytesPerArc
(package private) final int	version

Constructor Summary

Constructors

Modifier	Constructor	Description
private	FSTCompiler(FST.INPUT_TYPE inputType, double suffixRAMLimitMB, Outputs<T> outputs, boolean allowFixedLengthArcs, int bytesPageBits, float directAddressingMaxOversizingFactor, int version)

Method Summary

Modifier and Type	Method	Description
void	add(IntsRef input, T output)	Add the next input/output pair.
(package private) long	addNode(FSTCompiler.UnCompiledNode<T> nodeIn)
FST<T>	compile()	Returns final FST.
private FSTCompiler.CompiledNode	compileNode(FSTCompiler.UnCompiledNode<T> nodeIn, int tailLength)
(package private) void	finish(long newStartNode)
private void	freezeTail(int prefixLenPlus1)
long	fstRamBytesUsed()
long	fstSizeInBytes()
long	getArcCount()
float	getDirectAddressingMaxOversizingFactor()
long	getMappedStateCount()
long	getNodeCount()
(package private) void	setEmptyOutput(T v)
private boolean	shouldExpandNodeWithDirectAddressing(FSTCompiler.UnCompiledNode<T> nodeIn, int numBytesPerArc, int maxBytesPerArcWithoutLabel, int labelRange)	Returns whether the given node should be expanded with direct addressing instead of binary search.
private boolean	shouldExpandNodeWithFixedLengthArcs(FSTCompiler.UnCompiledNode<T> node)	Returns whether the given node should be expanded with fixed length arcs.
private boolean	validOutput(T output)
private void	writeLabel(DataOutput out, int v)
private void	writeNodeForBinarySearch(FSTCompiler.UnCompiledNode<T> nodeIn, long startAddress, int maxBytesPerArc)
private void	writeNodeForDirectAddressingOrContinuous(FSTCompiler.UnCompiledNode<T> nodeIn, long startAddress, int maxBytesPerArcWithoutLabel, int labelRange, boolean continuous)
private void	writePresenceBits(FSTCompiler.UnCompiledNode<T> nodeIn)

Methods inherited from class java.lang.Object

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

Field Details

DIRECT_ADDRESSING_MAX_OVERSIZING_FACTOR

static final float DIRECT_ADDRESSING_MAX_OVERSIZING_FACTOR

See Also:

• Constant Field Values

FIXED_LENGTH_ARC_SHALLOW_DEPTH

static final int FIXED_LENGTH_ARC_SHALLOW_DEPTH

See Also:

• shouldExpandNodeWithFixedLengthArcs(org.apache.lucene.util.fst.FSTCompiler.UnCompiledNode<T>)
• Constant Field Values

FIXED_LENGTH_ARC_SHALLOW_NUM_ARCS

static final int FIXED_LENGTH_ARC_SHALLOW_NUM_ARCS

See Also:

• shouldExpandNodeWithFixedLengthArcs(org.apache.lucene.util.fst.FSTCompiler.UnCompiledNode<T>)
• Constant Field Values

FIXED_LENGTH_ARC_DEEP_NUM_ARCS

static final int FIXED_LENGTH_ARC_DEEP_NUM_ARCS

See Also:

• shouldExpandNodeWithFixedLengthArcs(org.apache.lucene.util.fst.FSTCompiler.UnCompiledNode<T>)
• Constant Field Values

DIRECT_ADDRESSING_MAX_OVERSIZE_WITH_CREDIT_FACTOR

private static final float DIRECT_ADDRESSING_MAX_OVERSIZE_WITH_CREDIT_FACTOR

Maximum oversizing factor allowed for direct addressing compared to binary search when expansion credits allow the oversizing. This factor prevents expansions that are obviously too costly even if there are sufficient credits.

See Also:

• shouldExpandNodeWithDirectAddressing(org.apache.lucene.util.fst.FSTCompiler.UnCompiledNode<T>, int, int, int)
• Constant Field Values

dedupHash

private final NodeHash<T> dedupHash

fst

final FST<T> fst

NO_OUTPUT

private final T NO_OUTPUT

lastInput

private final IntsRefBuilder lastInput

frontier

private FSTCompiler.UnCompiledNode<T>[] frontier

lastFrozenNode

long lastFrozenNode

numBytesPerArc

int[] numBytesPerArc

numLabelBytesPerArc

int[] numLabelBytesPerArc

fixedLengthArcsBuffer

final FSTCompiler.FixedLengthArcsBuffer fixedLengthArcsBuffer

arcCount

long arcCount

nodeCount

long nodeCount

binarySearchNodeCount

long binarySearchNodeCount

directAddressingNodeCount

long directAddressingNodeCount

continuousNodeCount

long continuousNodeCount

allowFixedLengthArcs

final boolean allowFixedLengthArcs

directAddressingMaxOversizingFactor

final float directAddressingMaxOversizingFactor

version

final int version

directAddressingExpansionCredit

long directAddressingExpansionCredit

bytes

final BytesStore bytes

Constructor Details

FSTCompiler

private FSTCompiler(FST.INPUT_TYPE inputType,
 double suffixRAMLimitMB,
 Outputs<T> outputs,
 boolean allowFixedLengthArcs,
 int bytesPageBits,
 float directAddressingMaxOversizingFactor,
 int version)

Method Details

getDirectAddressingMaxOversizingFactor

public float getDirectAddressingMaxOversizingFactor()

getNodeCount

public long getNodeCount()

getArcCount

public long getArcCount()

getMappedStateCount

public long getMappedStateCount()

compileNode

private FSTCompiler.CompiledNode compileNode(FSTCompiler.UnCompiledNode<T> nodeIn,
 int tailLength)
                                      throws IOException

Throws:

IOException

addNode

long addNode(FSTCompiler.UnCompiledNode<T> nodeIn)
      throws IOException

Throws:

IOException

writeLabel

private void writeLabel(DataOutput out,
 int v)
                 throws IOException

Throws:

IOException

shouldExpandNodeWithFixedLengthArcs

private boolean shouldExpandNodeWithFixedLengthArcs(FSTCompiler.UnCompiledNode<T> node)

Returns whether the given node should be expanded with fixed length arcs. Nodes will be expanded depending on their depth (distance from the root node) and their number of arcs.

Nodes with fixed length arcs use more space, because they encode all arcs with a fixed number of bytes, but they allow either binary search or direct addressing on the arcs (instead of linear scan) on lookup by arc label.

shouldExpandNodeWithDirectAddressing

private boolean shouldExpandNodeWithDirectAddressing(FSTCompiler.UnCompiledNode<T> nodeIn,
 int numBytesPerArc,
 int maxBytesPerArcWithoutLabel,
 int labelRange)

Returns whether the given node should be expanded with direct addressing instead of binary search.

Prefer direct addressing for performance if it does not oversize binary search byte size too much, so that the arcs can be directly addressed by label.

See Also:

• getDirectAddressingMaxOversizingFactor()

writeNodeForBinarySearch

private void writeNodeForBinarySearch(FSTCompiler.UnCompiledNode<T> nodeIn,
 long startAddress,
 int maxBytesPerArc)

writeNodeForDirectAddressingOrContinuous

private void writeNodeForDirectAddressingOrContinuous(FSTCompiler.UnCompiledNode<T> nodeIn,
 long startAddress,
 int maxBytesPerArcWithoutLabel,
 int labelRange,
 boolean continuous)

writePresenceBits

private void writePresenceBits(FSTCompiler.UnCompiledNode<T> nodeIn)

freezeTail

private void freezeTail(int prefixLenPlus1)
                 throws IOException

Throws:

IOException

add

public void add(IntsRef input,
 T output)
         throws IOException

Add the next input/output pair. The provided input must be sorted after the previous one according to IntsRef.compareTo(org.apache.lucene.util.IntsRef). It's also OK to add the same input twice in a row with different outputs, as long as Outputs implements the Outputs.merge(T, T) method. Note that input is fully consumed after this method is returned (so caller is free to reuse), but output is not. So if your outputs are changeable (eg ByteSequenceOutputs or IntSequenceOutputs) then you cannot reuse across calls.

Throws:

IOException

setEmptyOutput

void setEmptyOutput(T v)

finish

void finish(long newStartNode)

validOutput

private boolean validOutput(T output)

compile

public FST<T> compile()
               throws IOException

Returns final FST. NOTE: this will return null if nothing is accepted by the FST.

Throws:

IOException

fstRamBytesUsed

public long fstRamBytesUsed()

fstSizeInBytes

public long fstSizeInBytes()