Package org.apache.lucene.util.fst

Class FSTCompiler<T>

java.lang.Object

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

public class FSTCompiler<T>
extends java.lang.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 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 class	FSTCompiler.UnCompiledNode<T>	Expert: holds a pending (seen but not yet serialized) Node.

Field Summary

Fields

Modifier and Type	Field	Description
(package private) boolean	allowFixedLengthArcs
(package private) long	arcCount
(package private) long	binarySearchNodeCount
(package private) BytesStore	bytes
private NodeHash<T>	dedupHash
(package private) static float	DIRECT_ADDRESSING_MAX_OVERSIZING_FACTOR
(package private) long	directAddressingExpansionCredit
(package private) float	directAddressingMaxOversizingFactor
(package private) long	directAddressingNodeCount
private boolean	doShareNonSingletonNodes
(package private) FSTCompiler.FixedLengthArcsBuffer	fixedLengthArcsBuffer
private FSTCompiler.UnCompiledNode<T>[]	frontier
(package private) FST<T>	fst
(package private) long	lastFrozenNode
private IntsRefBuilder	lastInput
private int	minSuffixCount1
private int	minSuffixCount2
private T	NO_OUTPUT
(package private) long	nodeCount
(package private) int[]	numBytesPerArc
(package private) int[]	numLabelBytesPerArc
private int	shareMaxTailLength

Constructor Summary

Constructors

Modifier	Constructor	Description
private	FSTCompiler(FST.INPUT_TYPE inputType, int minSuffixCount1, int minSuffixCount2, boolean doShareSuffix, boolean doShareNonSingletonNodes, int shareMaxTailLength, Outputs<T> outputs, boolean allowFixedLengthArcs, int bytesPageBits, float directAddressingMaxOversizingFactor)
	FSTCompiler(FST.INPUT_TYPE inputType, Outputs<T> outputs)	Instantiates an FST/FSA builder with default settings and pruning options turned off.

Method Summary

Modifier and Type	Method	Description
void	add(IntsRef input, T output)	Add the next input/output pair.
FST<T>	compile()	Returns final FST.
private void	compileAllTargets(FSTCompiler.UnCompiledNode<T> node, int tailLength)
private FSTCompiler.CompiledNode	compileNode(FSTCompiler.UnCompiledNode<T> nodeIn, int tailLength)
private void	freezeTail(int prefixLenPlus1)
long	fstRamBytesUsed()
long	getArcCount()
float	getDirectAddressingMaxOversizingFactor()
long	getMappedStateCount()
long	getNodeCount()
long	getTermCount()
private boolean	validOutput(T output)

Methods inherited from class java.lang.Object

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

Field Detail

DIRECT_ADDRESSING_MAX_OVERSIZING_FACTOR

static final float DIRECT_ADDRESSING_MAX_OVERSIZING_FACTOR

See Also:

Constant Field Values

dedupHash

private final NodeHash<T> dedupHash

fst

final FST<T> fst

NO_OUTPUT

private final T NO_OUTPUT

minSuffixCount1

private final int minSuffixCount1

minSuffixCount2

private final int minSuffixCount2

doShareNonSingletonNodes

private final boolean doShareNonSingletonNodes

shareMaxTailLength

private final int shareMaxTailLength

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

allowFixedLengthArcs

final boolean allowFixedLengthArcs

directAddressingMaxOversizingFactor

final float directAddressingMaxOversizingFactor

directAddressingExpansionCredit

long directAddressingExpansionCredit

bytes

final BytesStore bytes

Constructor Detail

FSTCompiler

public FSTCompiler(FST.INPUT_TYPE inputType,
                   Outputs<T> outputs)

Instantiates an FST/FSA builder with default settings and pruning options turned off. For more tuning and tweaking, see FSTCompiler.Builder.

FSTCompiler

private FSTCompiler(FST.INPUT_TYPE inputType,
                    int minSuffixCount1,
                    int minSuffixCount2,
                    boolean doShareSuffix,
                    boolean doShareNonSingletonNodes,
                    int shareMaxTailLength,
                    Outputs<T> outputs,
                    boolean allowFixedLengthArcs,
                    int bytesPageBits,
                    float directAddressingMaxOversizingFactor)

Method Detail

getDirectAddressingMaxOversizingFactor

public float getDirectAddressingMaxOversizingFactor()

getTermCount

public long getTermCount()

getNodeCount

public long getNodeCount()

getArcCount

public long getArcCount()

getMappedStateCount

public long getMappedStateCount()

compileNode

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

Throws:

java.io.IOException

freezeTail

private void freezeTail(int prefixLenPlus1)
                 throws java.io.IOException

Throws:

java.io.IOException

add

public void add(IntsRef input,
                T output)
         throws java.io.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:

java.io.IOException

validOutput

private boolean validOutput(T output)

compile

public FST<T> compile()
               throws java.io.IOException

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

Throws:

java.io.IOException

compileAllTargets

private void compileAllTargets(FSTCompiler.UnCompiledNode<T> node,
                               int tailLength)
                        throws java.io.IOException

Throws:

java.io.IOException

fstRamBytesUsed

public long fstRamBytesUsed()