java.lang.Object
org.apache.lucene.util.fst.FSTCompiler<T>
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 ClassesModifier and TypeClassDescription(package private) static class
Expert: holds a pending (seen but not yet serialized) arc.static class
Fluent-style constructor for FSTFSTCompiler
.(package private) static final class
(package private) static class
Reusable buffer for building nodes with fixed length arcs (binary search or direct addressing).(package private) static interface
(package private) static final class
Expert: holds a pending (seen but not yet serialized) Node. -
Field Summary
FieldsModifier and TypeFieldDescription(package private) final boolean
(package private) long
(package private) long
(package private) final BytesStore
(package private) long
private static final float
Maximum oversizing factor allowed for direct addressing compared to binary search when expansion credits allow the oversizing.(package private) static final float
(package private) long
(package private) final float
(package private) long
(package private) static final int
(package private) static final int
(package private) static final int
(package private) final FSTCompiler.FixedLengthArcsBuffer
private FSTCompiler.UnCompiledNode<T>[]
(package private) long
private final IntsRefBuilder
private final T
(package private) long
(package private) int[]
(package private) int[]
(package private) final int
-
Constructor Summary
ConstructorsModifierConstructorDescriptionprivate
FSTCompiler
(FST.INPUT_TYPE inputType, double suffixRAMLimitMB, Outputs<T> outputs, boolean allowFixedLengthArcs, int bytesPageBits, float directAddressingMaxOversizingFactor, int version) -
Method Summary
Modifier and TypeMethodDescriptionvoid
Add the next input/output pair.(package private) long
addNode
(FSTCompiler.UnCompiledNode<T> nodeIn) 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
long
long
float
long
long
(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
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)
-
Field Details
-
DIRECT_ADDRESSING_MAX_OVERSIZING_FACTOR
static final float DIRECT_ADDRESSING_MAX_OVERSIZING_FACTOR- See Also:
-
FIXED_LENGTH_ARC_SHALLOW_DEPTH
static final int FIXED_LENGTH_ARC_SHALLOW_DEPTH- See Also:
-
FIXED_LENGTH_ARC_SHALLOW_NUM_ARCS
static final int FIXED_LENGTH_ARC_SHALLOW_NUM_ARCS- See Also:
-
FIXED_LENGTH_ARC_DEEP_NUM_ARCS
static final int FIXED_LENGTH_ARC_DEEP_NUM_ARCS- See Also:
-
DIRECT_ADDRESSING_MAX_OVERSIZE_WITH_CREDIT_FACTOR
private static final float DIRECT_ADDRESSING_MAX_OVERSIZE_WITH_CREDIT_FACTORMaximum 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:
-
dedupHash
-
fst
-
NO_OUTPUT
-
lastInput
-
frontier
-
lastFrozenNode
long lastFrozenNode -
numBytesPerArc
int[] numBytesPerArc -
numLabelBytesPerArc
int[] numLabelBytesPerArc -
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
-
-
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
- Throws:
IOException
-
writeLabel
- Throws:
IOException
-
shouldExpandNodeWithFixedLengthArcs
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:
-
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
-
freezeTail
- Throws:
IOException
-
add
Add the next input/output pair. The provided input must be sorted after the previous one according toIntsRef.compareTo(org.apache.lucene.util.IntsRef)
. It's also OK to add the same input twice in a row with different outputs, as long asOutputs
implements theOutputs.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 (egByteSequenceOutputs
orIntSequenceOutputs
) then you cannot reuse across calls.- Throws:
IOException
-
setEmptyOutput
-
finish
void finish(long newStartNode) -
validOutput
-
compile
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()
-