Module org.apache.lucene.core

Package org.apache.lucene.util.automaton

Class StringsToAutomaton

java.lang.Object

org.apache.lucene.util.automaton.StringsToAutomaton

final class StringsToAutomaton
extends Object

Builds a minimal, deterministic Automaton that accepts a set of strings using the algorithm described in Incremental Construction of Minimal Acyclic Finite-State Automata by Daciuk, Mihov, Watson and Watson. This requires sorted input data, but is very fast (nearly linear with the input size). Also offers the ability to directly build a binary Automaton representation. Users should access this functionality through Automata static methods.

See Also:

• Automata.makeStringUnion(Iterable)
• Automata.makeBinaryStringUnion(Iterable)
• Automata.makeStringUnion(BytesRefIterator)
• Automata.makeBinaryStringUnion(BytesRefIterator)

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private static final class	StringsToAutomaton.State	DFSA state with char labels on transitions.

Field Summary

Fields

Modifier and Type	Field	Description
private BytesRefBuilder	previous	Used for input order checking (only through assertions right now)
private final StringsToAutomaton.State	root	Root automaton state.
private HashMap<StringsToAutomaton.State,StringsToAutomaton.State>	stateRegistry	A "registry" for state interning.

Constructor Summary

Constructors

Modifier	Constructor	Description
private	StringsToAutomaton()	The default constructor is private.

Method Summary

Modifier and Type	Method	Description
private void	add(BytesRef current, boolean asBinary)
(package private) static Automaton	build(Iterable<BytesRef> input, boolean asBinary)	Build a minimal, deterministic automaton from a sorted list of BytesRef representing strings in UTF-8.
(package private) static Automaton	build(BytesRefIterator input, boolean asBinary)	Build a minimal, deterministic automaton from a sorted list of BytesRef representing strings in UTF-8.
private Automaton	completeAndConvert()	Called after adding all terms.
private static int	convert(Automaton.Builder a, StringsToAutomaton.State s, IdentityHashMap<StringsToAutomaton.State,Integer> visited)	Internal recursive traversal for conversion.
private void	replaceOrRegister(StringsToAutomaton.State state)	Replace last child of state with an already registered state or stateRegistry the last child state.
private boolean	setPrevious(BytesRef current)	Copy current into an internal buffer.

Methods inherited from class java.lang.Object

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

Field Details

stateRegistry

private HashMap<StringsToAutomaton.State,StringsToAutomaton.State> stateRegistry

A "registry" for state interning.

root

private final StringsToAutomaton.State root

Root automaton state.

previous

private BytesRefBuilder previous

Used for input order checking (only through assertions right now)

Constructor Details

StringsToAutomaton

private StringsToAutomaton()

The default constructor is private. Use static methods directly.

Method Details

setPrevious

private boolean setPrevious(BytesRef current)

Copy current into an internal buffer.

convert

private static int convert(Automaton.Builder a,
 StringsToAutomaton.State s,
 IdentityHashMap<StringsToAutomaton.State,Integer> visited)

Internal recursive traversal for conversion.

completeAndConvert

private Automaton completeAndConvert()

Called after adding all terms. Performs final minimization and converts to a standard Automaton instance.

build

static Automaton build(Iterable<BytesRef> input,
 boolean asBinary)

Build a minimal, deterministic automaton from a sorted list of BytesRef representing strings in UTF-8. These strings must be binary-sorted. Creates an Automaton with either UTF-8 codepoints as transition labels or binary (compiled) transition labels based on asBinary.

build

static Automaton build(BytesRefIterator input,
 boolean asBinary)
                throws IOException

Build a minimal, deterministic automaton from a sorted list of BytesRef representing strings in UTF-8. These strings must be binary-sorted. Creates an Automaton with either UTF-8 codepoints as transition labels or binary (compiled) transition labels based on asBinary.

Throws:

IOException

add

private void add(BytesRef current,
 boolean asBinary)

replaceOrRegister

private void replaceOrRegister(StringsToAutomaton.State state)

Replace last child of state with an already registered state or stateRegistry the last child state.