Namespace Lucene.Net.Util.Fst
Finite state transducers
This package implements Finite State Transducers with the following characteristics:
Fast and low memory overhead construction of the minimal FST (but inputs must be provided in sorted order)
Low object overhead and quick deserialization (byte[] representation)
Optional two-pass compression: FST.pack
Lookup-by-output when the outputs are in sorted order (e.g., ordinals or file pointers)
Pluggable Outputs representation
N-shortest-paths search by weight
Enumerators (IntsRef and BytesRef) that behave like {@link java.util.SortedMap SortedMap} iterators
FST Construction example:
// Input values (keys). These must be provided to Builder in Unicode sorted order!
String inputValues[] = {"cat", "dog", "dogs"};
long outputValues[] = {5, 7, 12};
PositiveIntOutputs outputs = PositiveIntOutputs.getSingleton();
Builder<Long> builder = new Builder<Long>(INPUT_TYPE.BYTE1, outputs);
BytesRef scratchBytes = new BytesRef();
IntsRef scratchInts = new IntsRef();
for (int i = 0; i < inputValues.length; i++) {
scratchBytes.copyChars(inputValues[i]);
builder.add(Util.toIntsRef(scratchBytes, scratchInts), outputValues[i]);
}
FST<Long> fst = builder.finish();
Retrieval by key:
Long value = Util.get(fst, new BytesRef("dog"));
System.out.println(value); // 7
Retrieval by value:
// Only works because outputs are also in sorted order
IntsRef key = Util.getByOutput(fst, 12);
System.out.println(Util.toBytesRef(key, scratchBytes).utf8ToString()); // dogs
Iterate over key-value pairs in sorted order:
// Like TermsEnum, this also supports seeking (advance)
BytesRefFSTEnum<Long> iterator = new BytesRefFSTEnum<Long>(fst);
while (iterator.next() != null) {
InputOutput<Long> mapEntry = iterator.current();
System.out.println(mapEntry.input.utf8ToString());
System.out.println(mapEntry.output);
}
N-shortest paths by weight:
Comparator<Long> comparator = new Comparator<Long>() {
public int compare(Long left, Long right) {
return left.compareTo(right);
}
};
Arc<Long> firstArc = fst.getFirstArc(new Arc<Long>());
MinResult<Long> paths[] = Util.shortestPaths(fst, firstArc, comparator, 2);
System.out.println(Util.toBytesRef(paths[0].input, scratchBytes).utf8ToString()); // cat
System.out.println(paths[0].output); // 5
System.out.println(Util.toBytesRef(paths[1].input, scratchBytes).utf8ToString()); // dog
System.out.println(paths[1].output); // 7
Classes
Builder
LUCENENET specific type used to access nested types of Builder<T> without referring to its generic closing type.
Builder.Arc<S>
Expert: holds a pending (seen but not yet serialized) arc.
Builder.CompiledNode
Builder.FreezeTail<S>
Expert: this is invoked by Builder whenever a suffix is serialized.
Builder.UnCompiledNode<S>
Expert: holds a pending (seen but not yet serialized) Node.
Builder<T>
Builds a minimal FST (maps an Int32sRef 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
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.
ByteSequenceOutputs
An FST Outputs{BytesRef} implementation where each output is a sequence of bytes.
BytesRefFSTEnum
LUCENENET specific. This class is to mimic Java's ability to specify nested classes of Generics without having to specify the generic type (i.e. BytesRefFSTEnum.InputOutput{T} rather than BytesRefFSTEnum{T}.InputOutput{T})
BytesRefFSTEnum.InputOutput<T>
Holds a single input (BytesRef) + output pair.
BytesRefFSTEnum<T>
Enumerates all input (BytesRef) + output pairs in an FST.
CharSequenceOutputs
An FST Outputs<T> implementation where each output is a sequence of characters.
FST
LUCENENET specific: This new base class is to mimic Java's ability to use nested types without specifying a type parameter. i.e. FST.BytesReader instead of FST<BytesRef>.BytesReader
FST.Arc<T>
Represents a single arc.
FST.BytesReader
Reads bytes stored in an FST.
FST<T>
Represents an finite state machine (FST), using a compact byte[] format.
The format is similar to what's used by Morfologik (http://sourceforge.net/projects/morfologik).
See the FST package documentation for some simple examples.
FSTEnum<T>
Can Next() and Advance() through the terms in an FST
Int32SequenceOutputs
An FST Outputs<T> implementation where each output is a sequence of System.Int32s.
NOTE: This was IntSequenceOutputs in Lucene
Int32sRefFSTEnum
LUCENENET specific. This class is to mimic Java's ability to specify
nested classes of Generics without having to specify the generic type
(i.e. Int32sRefFSTEnum.InputOutput{T} rather than Int32sRefFSTEnum{T}.InputOutput{T})
NOTE: This was Int32sRefFSTEnum{T} in Lucene
Int32sRefFSTEnum.InputOutput<T>
Holds a single input (Int32sRef) + output pair.
Int32sRefFSTEnum<T>
Enumerates all input (Int32sRef) + output pairs in an FST.
NOTE: This was IntsRefFSTEnum{T} in Lucene
NoOutputs
A null FST Outputs<T> implementation; use this if you just want to build an FSA.
Outputs<T>
Represents the outputs for an FST, providing the basic algebra required for building and traversing the FST.
Note that any operation that returns NO_OUTPUT must return the same singleton object from NoOutput.
LUCENENET IMPORTANT: If T is a collection type,
it must implement System.Collections.IStructuralEquatable
in order to properly compare its nested values.
PairOutputs<A, B>
An FST Outputs<T> implementation, holding two other outputs.
PairOutputs<A, B>.Pair
Holds a single pair of two outputs.
PositiveInt32Outputs
An FST Outputs<T> implementation where each output
is a non-negative
NOTE: This was PositiveIntOutputs in Lucene
Util
Static helper methods.
Util.FSTPath<T>
Represents a path in TopNSearcher.
Util.Result<T>
Holds a single input (Int32sRef) + output, returned by ShortestPaths<T>(FST<T>, FST.Arc<T>, T, IComparer<T>, Int32, Boolean).
Util.TopNSearcher<T>
Utility class to find top N shortest paths from start point(s).
Util.TopResults<T>
Holds the results for a top N search using Util.TopNSearcher<T>
Interfaces
Builder.INode
Enums
FST.INPUT_TYPE
Specifies allowed range of each int input label for this FST.