/*
 * dk.brics.automaton
 * 
 * Copyright (c) 2001-2009 Anders Moeller
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. The name of the author may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

package org.apache.lucene.util.automaton;

import java.util.*;

import org.apache.lucene.util.BytesRef;
import org.apache.lucene.util.StringHelper;

Construction of basic automata.
@lucene.experimental
/** * Construction of basic automata. * * @lucene.experimental */
final public class Automata { private Automata() {}
Returns a new (deterministic) automaton with the empty language.
/** * Returns a new (deterministic) automaton with the empty language. */
public static Automaton makeEmpty() { Automaton a = new Automaton(); a.finishState(); return a; }
Returns a new (deterministic) automaton that accepts only the empty string.
/** * Returns a new (deterministic) automaton that accepts only the empty string. */
public static Automaton makeEmptyString() { Automaton a = new Automaton(); a.createState(); a.setAccept(0, true); return a; }
Returns a new (deterministic) automaton that accepts all strings.
/** * Returns a new (deterministic) automaton that accepts all strings. */
public static Automaton makeAnyString() { Automaton a = new Automaton(); int s = a.createState(); a.setAccept(s, true); a.addTransition(s, s, Character.MIN_CODE_POINT, Character.MAX_CODE_POINT); a.finishState(); return a; }
Returns a new (deterministic) automaton that accepts all binary terms.
/** * Returns a new (deterministic) automaton that accepts all binary terms. */
public static Automaton makeAnyBinary() { Automaton a = new Automaton(); int s = a.createState(); a.setAccept(s, true); a.addTransition(s, s, 0, 255); a.finishState(); return a; }
Returns a new (deterministic) automaton that accepts any single codepoint.
/** * Returns a new (deterministic) automaton that accepts any single codepoint. */
public static Automaton makeAnyChar() { return makeCharRange(Character.MIN_CODE_POINT, Character.MAX_CODE_POINT); }
Accept any single character starting from the specified state, returning the new state
/** Accept any single character starting from the specified state, returning the new state */
public static int appendAnyChar(Automaton a, int state) { int newState = a.createState(); a.addTransition(state, newState, Character.MIN_CODE_POINT, Character.MAX_CODE_POINT); return newState; }
Returns a new (deterministic) automaton that accepts a single codepoint of the given value.
/** * Returns a new (deterministic) automaton that accepts a single codepoint of * the given value. */
public static Automaton makeChar(int c) { return makeCharRange(c, c); }
Appends the specified character to the specified state, returning a new state.
/** Appends the specified character to the specified state, returning a new state. */
public static int appendChar(Automaton a, int state, int c) { int newState = a.createState(); a.addTransition(state, newState, c, c); return newState; }
Returns a new (deterministic) automaton that accepts a single codepoint whose value is in the given interval (including both end points).
/** * Returns a new (deterministic) automaton that accepts a single codepoint whose * value is in the given interval (including both end points). */
public static Automaton makeCharRange(int min, int max) { if (min > max) { return makeEmpty(); } Automaton a = new Automaton(); int s1 = a.createState(); int s2 = a.createState(); a.setAccept(s2, true); a.addTransition(s1, s2, min, max); a.finishState(); return a; }
Constructs sub-automaton corresponding to decimal numbers of length x.substring(n).length().
/** * Constructs sub-automaton corresponding to decimal numbers of length * x.substring(n).length(). */
private static int anyOfRightLength(Automaton.Builder builder, String x, int n) { int s = builder.createState(); if (x.length() == n) { builder.setAccept(s, true); } else { builder.addTransition(s, anyOfRightLength(builder, x, n + 1), '0', '9'); } return s; }
Constructs sub-automaton corresponding to decimal numbers of value at least x.substring(n) and length x.substring(n).length().
/** * Constructs sub-automaton corresponding to decimal numbers of value at least * x.substring(n) and length x.substring(n).length(). */
private static int atLeast(Automaton.Builder builder, String x, int n, Collection<Integer> initials, boolean zeros) { int s = builder.createState(); if (x.length() == n) { builder.setAccept(s, true); } else { if (zeros) { initials.add(s); } char c = x.charAt(n); builder.addTransition(s, atLeast(builder, x, n + 1, initials, zeros && c == '0'), c); if (c < '9') { builder.addTransition(s, anyOfRightLength(builder, x, n + 1), (char) (c + 1), '9'); } } return s; }
Constructs sub-automaton corresponding to decimal numbers of value at most x.substring(n) and length x.substring(n).length().
/** * Constructs sub-automaton corresponding to decimal numbers of value at most * x.substring(n) and length x.substring(n).length(). */
private static int atMost(Automaton.Builder builder, String x, int n) { int s = builder.createState(); if (x.length() == n) { builder.setAccept(s, true); } else { char c = x.charAt(n); builder.addTransition(s, atMost(builder, x, (char) n + 1), c); if (c > '0') { builder.addTransition(s, anyOfRightLength(builder, x, n + 1), '0', (char) (c - 1)); } } return s; }
Constructs sub-automaton corresponding to decimal numbers of value between x.substring(n) and y.substring(n) and of length x.substring(n).length() (which must be equal to y.substring(n).length()).
/** * Constructs sub-automaton corresponding to decimal numbers of value between * x.substring(n) and y.substring(n) and of length x.substring(n).length() * (which must be equal to y.substring(n).length()). */
private static int between(Automaton.Builder builder, String x, String y, int n, Collection<Integer> initials, boolean zeros) { int s = builder.createState(); if (x.length() == n) { builder.setAccept(s, true); } else { if (zeros) { initials.add(s); } char cx = x.charAt(n); char cy = y.charAt(n); if (cx == cy) { builder.addTransition(s, between(builder, x, y, n + 1, initials, zeros && cx == '0'), cx); } else { // cx<cy builder.addTransition(s, atLeast(builder, x, n + 1, initials, zeros && cx == '0'), cx); builder.addTransition(s, atMost(builder, y, n + 1), cy); if (cx + 1 < cy) { builder.addTransition(s, anyOfRightLength(builder, x, n+1), (char) (cx + 1), (char) (cy - 1)); } } } return s; } private static boolean suffixIsZeros(BytesRef br, int len) { for(int i=len;i<br.length;i++) { if (br.bytes[br.offset+i] != 0) { return false; } } return true; }
Creates a new deterministic, minimal automaton accepting all binary terms in the specified interval. Note that unlike makeDecimalInterval, the returned automaton is infinite, because terms behave like floating point numbers leading with a decimal point. However, in the special case where min == max, and both are inclusive, the automata will be finite and accept exactly one term.
/** Creates a new deterministic, minimal automaton accepting * all binary terms in the specified interval. Note that unlike * {@link #makeDecimalInterval}, the returned automaton is infinite, * because terms behave like floating point numbers leading with * a decimal point. However, in the special case where min == max, * and both are inclusive, the automata will be finite and accept * exactly one term. */
public static Automaton makeBinaryInterval(BytesRef min, boolean minInclusive, BytesRef max, boolean maxInclusive) { if (min == null && minInclusive == false) { throw new IllegalArgumentException("minInclusive must be true when min is null (open ended)"); } if (max == null && maxInclusive == false) { throw new IllegalArgumentException("maxInclusive must be true when max is null (open ended)"); } if (min == null) { min = new BytesRef(); minInclusive = true; } int cmp; if (max != null) { cmp = min.compareTo(max); } else { cmp = -1; if (min.length == 0 && minInclusive) { return makeAnyBinary(); } } if (cmp == 0) { if (minInclusive == false || maxInclusive == false) { return makeEmpty(); } else { return makeBinary(min); } } else if (cmp > 0) { // max > min return makeEmpty(); } if (max != null && StringHelper.startsWith(max, min) && suffixIsZeros(max, min.length)) { // Finite case: no sink state! int maxLength = max.length; // the == case was handled above assert maxLength > min.length; // bar -> bar\0+ if (maxInclusive == false) { maxLength--; } if (maxLength == min.length) { if (minInclusive == false) { return makeEmpty(); } else { return makeBinary(min); } } Automaton a = new Automaton(); int lastState = a.createState(); for (int i=0;i<min.length;i++) { int state = a.createState(); int label = min.bytes[min.offset+i] & 0xff; a.addTransition(lastState, state, label); lastState = state; } if (minInclusive) { a.setAccept(lastState, true); } for(int i=min.length;i<maxLength;i++) { int state = a.createState(); a.addTransition(lastState, state, 0); a.setAccept(state, true); lastState = state; } a.finishState(); return a; } Automaton a = new Automaton(); int startState = a.createState(); int sinkState = a.createState(); a.setAccept(sinkState, true); // This state accepts all suffixes: a.addTransition(sinkState, sinkState, 0, 255); boolean equalPrefix = true; int lastState = startState; int firstMaxState = -1; int sharedPrefixLength = 0; for(int i=0;i<min.length;i++) { int minLabel = min.bytes[min.offset+i] & 0xff; int maxLabel; if (max != null && equalPrefix && i < max.length) { maxLabel = max.bytes[max.offset+i] & 0xff; } else { maxLabel = -1; } int nextState; if (minInclusive && i == min.length-1 && (equalPrefix == false || minLabel != maxLabel)) { nextState = sinkState; } else { nextState = a.createState(); } if (equalPrefix) { if (minLabel == maxLabel) { // Still in shared prefix a.addTransition(lastState, nextState, minLabel); } else if (max == null) { equalPrefix = false; sharedPrefixLength = 0; a.addTransition(lastState, sinkState, minLabel+1, 0xff); a.addTransition(lastState, nextState, minLabel); } else { // This is the first point where min & max diverge: assert maxLabel > minLabel; a.addTransition(lastState, nextState, minLabel); if (maxLabel > minLabel + 1) { a.addTransition(lastState, sinkState, minLabel+1, maxLabel-1); } // Now fork off path for max: if (maxInclusive || i < max.length-1) { firstMaxState = a.createState(); if (i < max.length-1) { a.setAccept(firstMaxState, true); } a.addTransition(lastState, firstMaxState, maxLabel); } equalPrefix = false; sharedPrefixLength = i; } } else { // OK, already diverged: a.addTransition(lastState, nextState, minLabel); if (minLabel < 255) { a.addTransition(lastState, sinkState, minLabel+1, 255); } } lastState = nextState; } // Accept any suffix appended to the min term: if (equalPrefix == false && lastState != sinkState && lastState != startState) { a.addTransition(lastState, sinkState, 0, 255); } if (minInclusive) { // Accept exactly the min term: a.setAccept(lastState, true); } if (max != null) { // Now do max: if (firstMaxState == -1) { // Min was a full prefix of max sharedPrefixLength = min.length; } else { lastState = firstMaxState; sharedPrefixLength++; } for(int i=sharedPrefixLength;i<max.length;i++) { int maxLabel = max.bytes[max.offset+i]&0xff; if (maxLabel > 0) { a.addTransition(lastState, sinkState, 0, maxLabel-1); } if (maxInclusive || i < max.length-1) { int nextState = a.createState(); if (i < max.length-1) { a.setAccept(nextState, true); } a.addTransition(lastState, nextState, maxLabel); lastState = nextState; } } if (maxInclusive) { a.setAccept(lastState, true); } } a.finishState(); assert a.isDeterministic(): a.toDot(); return a; }
Returns a new automaton that accepts strings representing decimal (base 10) non-negative integers in the given interval.
Params:
  • min – minimal value of interval
  • max – maximal value of interval (both end points are included in the interval)
  • digits – if > 0, use fixed number of digits (strings must be prefixed by 0's to obtain the right length) - otherwise, the number of digits is not fixed (any number of leading 0s is accepted)
Throws:
  • IllegalArgumentException – if min > max or if numbers in the interval cannot be expressed with the given fixed number of digits
/** * Returns a new automaton that accepts strings representing decimal (base 10) * non-negative integers in the given interval. * * @param min minimal value of interval * @param max maximal value of interval (both end points are included in the * interval) * @param digits if &gt; 0, use fixed number of digits (strings must be prefixed * by 0's to obtain the right length) - otherwise, the number of * digits is not fixed (any number of leading 0s is accepted) * @exception IllegalArgumentException if min &gt; max or if numbers in the * interval cannot be expressed with the given fixed number of * digits */
public static Automaton makeDecimalInterval(int min, int max, int digits) throws IllegalArgumentException { String x = Integer.toString(min); String y = Integer.toString(max); if (min > max || (digits > 0 && y.length() > digits)) { throw new IllegalArgumentException(); } int d; if (digits > 0) d = digits; else d = y.length(); StringBuilder bx = new StringBuilder(); for (int i = x.length(); i < d; i++) { bx.append('0'); } bx.append(x); x = bx.toString(); StringBuilder by = new StringBuilder(); for (int i = y.length(); i < d; i++) { by.append('0'); } by.append(y); y = by.toString(); Automaton.Builder builder = new Automaton.Builder(); if (digits <= 0) { // Reserve the "real" initial state: builder.createState(); } Collection<Integer> initials = new ArrayList<>(); between(builder, x, y, 0, initials, digits <= 0); Automaton a1 = builder.finish(); if (digits <= 0) { a1.addTransition(0, 0, '0'); for (int p : initials) { a1.addEpsilon(0, p); } a1.finishState(); } return a1; }
Returns a new (deterministic) automaton that accepts the single given string.
/** * Returns a new (deterministic) automaton that accepts the single given * string. */
public static Automaton makeString(String s) { Automaton a = new Automaton(); int lastState = a.createState(); for (int i = 0, cp = 0; i < s.length(); i += Character.charCount(cp)) { int state = a.createState(); cp = s.codePointAt(i); a.addTransition(lastState, state, cp); lastState = state; } a.setAccept(lastState, true); a.finishState(); assert a.isDeterministic(); assert Operations.hasDeadStates(a) == false; return a; }
Returns a new (deterministic) automaton that accepts the single given binary term.
/** * Returns a new (deterministic) automaton that accepts the single given * binary term. */
public static Automaton makeBinary(BytesRef term) { Automaton a = new Automaton(); int lastState = a.createState(); for (int i=0;i<term.length;i++) { int state = a.createState(); int label = term.bytes[term.offset+i] & 0xff; a.addTransition(lastState, state, label); lastState = state; } a.setAccept(lastState, true); a.finishState(); assert a.isDeterministic(); assert Operations.hasDeadStates(a) == false; return a; }
Returns a new (deterministic) automaton that accepts the single given string from the specified unicode code points.
/** * Returns a new (deterministic) automaton that accepts the single given * string from the specified unicode code points. */
public static Automaton makeString(int[] word, int offset, int length) { Automaton a = new Automaton(); a.createState(); int s = 0; for (int i = offset; i < offset+length; i++) { int s2 = a.createState(); a.addTransition(s, s2, word[i]); s = s2; } a.setAccept(s, true); a.finishState(); return a; }
Returns a new (deterministic and minimal) automaton that accepts the union of the given collection of BytesRefs representing UTF-8 encoded strings.
Params:
  • utf8Strings – The input strings, UTF-8 encoded. The collection must be in sorted order.
Returns:An Automaton accepting all input strings. The resulting automaton is codepoint based (full unicode codepoints on transitions).
/** * Returns a new (deterministic and minimal) automaton that accepts the union * of the given collection of {@link BytesRef}s representing UTF-8 encoded * strings. * * @param utf8Strings * The input strings, UTF-8 encoded. The collection must be in sorted * order. * * @return An {@link Automaton} accepting all input strings. The resulting * automaton is codepoint based (full unicode codepoints on * transitions). */
public static Automaton makeStringUnion(Collection<BytesRef> utf8Strings) { if (utf8Strings.isEmpty()) { return makeEmpty(); } else { return DaciukMihovAutomatonBuilder.build(utf8Strings); } } }