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.
It now supports 3 different workflows:
- Build FST and use it immediately entirely in RAM and then discard it
- Build FST and use it immediately entirely in RAM and also save it to other DataOutput, and load it later and use it
- Build FST but stream it immediately to disk (except the FSTMetaData, to be saved at the end). In order to use it, you need to construct the corresponding DataInput and use the FST constructor to read it.
-
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
private static final class
This class is used for FST backed by non-FSTReader DataOutput.(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) long
(package private) final DataOutput
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
private static final FSTReader
(package private) int[]
private long
(package private) int[]
private boolean
(package private) final GrowableByteArrayDataOutput
(package private) final int
-
Constructor Summary
ConstructorsModifierConstructorDescriptionprivate
FSTCompiler
(FST.INPUT_TYPE inputType, double suffixRAMLimitMB, Outputs<T> outputs, boolean allowFixedLengthArcs, DataOutput dataOutput, 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 the metadata of the final FST.private FSTCompiler.CompiledNode
compileNode
(FSTCompiler.UnCompiledNode<T> nodeIn) (package private) void
finish
(long newStartNode) private void
freezeTail
(int prefixLenPlus1) long
long
long
float
Get the respectiveFSTReader
of theDataOutput
.long
static DataOutput
getOnHeapReaderWriter
(int blockBits) Get an on-heap DataOutput that allows the FST to be read immediately after writing, and also optionally saved to an external DataOutput.private void
Reverse the scratch bytes in place.(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, int maxBytesPerArc) private void
writeNodeForDirectAddressingOrContinuous
(FSTCompiler.UnCompiledNode<T> nodeIn, int maxBytesPerArcWithoutLabel, int labelRange, boolean continuous) private void
Write the padding byte, ensure no node gets address 0 which is reserved to mean the stop state w/ no arcsprivate void
writePresenceBits
(FSTCompiler.UnCompiledNode<T> nodeIn) private void
writeScratchBytes
(int destPos, byte[] bytes, int offset, int length) Write bytes from a source byte[] to the scratch bytes.
-
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:
-
NULL_FST_READER
-
dedupHash
-
fst
-
NO_OUTPUT
-
lastInput
-
paddingBytePending
private boolean paddingBytePending -
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 -
dataOutput
-
scratchBytes
-
numBytesWritten
private long numBytesWritten
-
-
Constructor Details
-
FSTCompiler
private FSTCompiler(FST.INPUT_TYPE inputType, double suffixRAMLimitMB, Outputs<T> outputs, boolean allowFixedLengthArcs, DataOutput dataOutput, float directAddressingMaxOversizingFactor, int version)
-
-
Method Details
-
getOnHeapReaderWriter
Get an on-heap DataOutput that allows the FST to be read immediately after writing, and also optionally saved to an external DataOutput.- Parameters:
blockBits
- how many bits wide to make each block of the DataOutput- Returns:
- the DataOutput
-
getFSTReader
Get the respectiveFSTReader
of theDataOutput
. To call this method, you need to use the default DataOutput orgetOnHeapReaderWriter(int)
, otherwise we will throw an exception.- Returns:
- the DataOutput as FSTReader
- Throws:
IllegalStateException
- if the DataOutput does not implement FSTReader
-
getDirectAddressingMaxOversizingFactor
public float getDirectAddressingMaxOversizingFactor() -
getNodeCount
public long getNodeCount() -
getArcCount
public long getArcCount() -
compileNode
private FSTCompiler.CompiledNode compileNode(FSTCompiler.UnCompiledNode<T> nodeIn) throws IOException - Throws:
IOException
-
addNode
- Throws:
IOException
-
writePaddingByte
Write the padding byte, ensure no node gets address 0 which is reserved to mean the stop state w/ no arcs- 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
-
reverseScratchBytes
private void reverseScratchBytes()Reverse the scratch bytes in place. This operation does not affect scratchBytes.getPosition(). -
writeScratchBytes
private void writeScratchBytes(int destPos, byte[] bytes, int offset, int length) Write bytes from a source byte[] to the scratch bytes. The written bytes must fit within what was already written in the scratch bytes.This operation does not affect scratchBytes.getPosition().
- Parameters:
destPos
- the position in the scratch bytesbytes
- the source byte[]offset
- the offset inside the source byte[]length
- the number of bytes to write
-
writeNodeForDirectAddressingOrContinuous
private void writeNodeForDirectAddressingOrContinuous(FSTCompiler.UnCompiledNode<T> nodeIn, 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 the metadata of the final FST. NOTE: this will return null if nothing is accepted by the FST themselves.To create the FST, you need to:
- If a FSTReader DataOutput was used, such as the one returned by
getOnHeapReaderWriter(int)
fstMetadata = fstCompiler.compile(); fst = FST.fromFSTReader(fstMetadata, fstCompiler.getFSTReader());
- If a non-FSTReader DataOutput was used, such as
IndexOutput
, you need to first create the correspondingDataInput
, such asIndexInput
then pass it to the FST constructfstMetadata = fstCompiler.compile(); fst = new FST<>(fstMetadata, dataInput, new OffHeapFSTStore());
- Throws:
IOException
-
fstRamBytesUsed
public long fstRamBytesUsed() -
fstSizeInBytes
public long fstSizeInBytes()
-