You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by mi...@apache.org on 2014/06/11 19:35:27 UTC
svn commit: r1601967 [2/4] - in /lucene/dev/branches/lucene5752/lucene:
analysis/common/src/java/org/apache/lucene/analysis/hunspell/
codecs/src/java/org/apache/lucene/codecs/blockterms/
codecs/src/java/org/apache/lucene/codecs/memory/ core/src/java/or...
Modified: lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/CompiledAutomaton.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/CompiledAutomaton.java?rev=1601967&r1=1601966&r2=1601967&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/CompiledAutomaton.java (original)
+++ lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/CompiledAutomaton.java Wed Jun 11 17:35:26 2014
@@ -65,15 +65,14 @@ public class CompiledAutomaton {
* only valid for {@link AUTOMATON_TYPE#NORMAL}.
*/
public final ByteRunAutomaton runAutomaton;
- // TODO: would be nice if these sortedTransitions had "int
- // to;" instead of "State to;" somehow:
+
/**
* Two dimensional array of transitions, indexed by state
* number for traversal. The state numbering is consistent with
* {@link #runAutomaton}.
* Only valid for {@link AUTOMATON_TYPE#NORMAL}.
*/
- public final Transition[][] sortedTransitions;
+ public final LightAutomaton lightAutomaton;
/**
* Shared common suffix accepted by the automaton. Only valid
* for {@link AUTOMATON_TYPE#NORMAL}, and only when the
@@ -92,7 +91,7 @@ public class CompiledAutomaton {
}
public CompiledAutomaton(Automaton automaton, Boolean finite, boolean simplify) {
-
+ //automaton.writeDot("/l/la/lucene/core/ca.dot");
if (simplify) {
// Test whether the automaton is a "simple" form and
// if so, don't create a runAutomaton. Note that on a
@@ -103,7 +102,7 @@ public class CompiledAutomaton {
term = null;
commonSuffixRef = null;
runAutomaton = null;
- sortedTransitions = null;
+ lightAutomaton = null;
this.finite = null;
return;
} else if (BasicOperations.isTotal(automaton)) {
@@ -112,7 +111,7 @@ public class CompiledAutomaton {
term = null;
commonSuffixRef = null;
runAutomaton = null;
- sortedTransitions = null;
+ lightAutomaton = null;
this.finite = null;
return;
} else {
@@ -137,7 +136,7 @@ public class CompiledAutomaton {
term = new BytesRef(singleton);
commonSuffixRef = null;
runAutomaton = null;
- sortedTransitions = null;
+ lightAutomaton = null;
this.finite = null;
return;
} else if (BasicOperations.sameLanguage(automaton, BasicOperations.concatenate(
@@ -147,7 +146,7 @@ public class CompiledAutomaton {
term = new BytesRef(commonPrefix);
commonSuffixRef = null;
runAutomaton = null;
- sortedTransitions = null;
+ lightAutomaton = null;
this.finite = null;
return;
}
@@ -156,56 +155,175 @@ public class CompiledAutomaton {
type = AUTOMATON_TYPE.NORMAL;
term = null;
+ LightAutomaton la = automaton.toLightAutomaton();
+
+ if (finite == null) {
+ this.finite = SpecialOperations.isFinite(la);
+ } else {
+ this.finite = finite;
+ }
+
+ //System.out.println("finite=" + this.finite);
+
+ //System.out.println("\nPRE");
+ //automaton.writeDot("/l/la/lucene/core/ain.dot");
+ //System.out.println("\nNOW BUILD");
+ //la.writeDot("/l/la/lucene/core/la.dot");
+ LightAutomaton utf8 = new UTF32ToUTF8Light().convert(la);
+ if (this.finite) {
+ commonSuffixRef = null;
+ } else {
+ // nocommit fixme
+ // commonSuffixRef = SpecialOperations.getCommonSuffixBytesRef(utf8);
+ commonSuffixRef = null;
+ }
+ runAutomaton = new ByteRunAutomaton(utf8, true);
+
+ lightAutomaton = runAutomaton.a;
+ }
+
+ public CompiledAutomaton(LightAutomaton automaton) {
+ this(automaton, null, true);
+ }
+
+ public CompiledAutomaton(LightAutomaton automaton, Boolean finite, boolean simplify) {
+ //System.out.println("CA simplify=" + simplify);
+ //automaton.writeDot("ca");
+ if (simplify) {
+ // Test whether the automaton is a "simple" form and
+ // if so, don't create a runAutomaton. Note that on a
+ // large automaton these tests could be costly:
+ if (BasicOperations.isEmpty(automaton)) {
+ // matches nothing
+ type = AUTOMATON_TYPE.NONE;
+ term = null;
+ commonSuffixRef = null;
+ runAutomaton = null;
+ lightAutomaton = null;
+ this.finite = null;
+ return;
+ } else if (BasicOperations.isTotal(automaton)) {
+ // matches all possible strings
+ type = AUTOMATON_TYPE.ALL;
+ term = null;
+ commonSuffixRef = null;
+ runAutomaton = null;
+ lightAutomaton = null;
+ this.finite = null;
+ return;
+ } else {
+
+ automaton = BasicOperations.determinize(automaton);
+
+ final String commonPrefix = SpecialOperations.getCommonPrefix(automaton);
+ final String singleton;
+
+ if (commonPrefix.length() > 0 && BasicOperations.sameLanguage(automaton, BasicAutomata.makeStringLight(commonPrefix))) {
+ singleton = commonPrefix;
+ } else {
+ singleton = null;
+ }
+
+ //System.out.println("CHECK PREFIX: commonPrefix=" + commonPrefix);
+
+ if (singleton != null) {
+ // matches a fixed string
+ type = AUTOMATON_TYPE.SINGLE;
+ term = new BytesRef(singleton);
+ commonSuffixRef = null;
+ runAutomaton = null;
+ lightAutomaton = null;
+ this.finite = null;
+ return;
+ } else if (commonPrefix.length() > 0) {
+ LightAutomaton other = BasicOperations.concatenateLight(BasicAutomata.makeStringLight(commonPrefix), BasicAutomata.makeAnyStringLight());
+ other = BasicOperations.determinize(other);
+ if (BasicOperations.sameLanguage(automaton, other)) {
+ // matches a constant prefix
+ type = AUTOMATON_TYPE.PREFIX;
+ term = new BytesRef(commonPrefix);
+ commonSuffixRef = null;
+ runAutomaton = null;
+ lightAutomaton = null;
+ this.finite = null;
+ return;
+ }
+ }
+ }
+ }
+
+ type = AUTOMATON_TYPE.NORMAL;
+ term = null;
+
if (finite == null) {
this.finite = SpecialOperations.isFinite(automaton);
} else {
this.finite = finite;
}
- Automaton utf8 = new UTF32ToUTF8().convert(automaton);
+
+ LightAutomaton utf8 = new UTF32ToUTF8Light().convert(automaton);
if (this.finite) {
commonSuffixRef = null;
} else {
commonSuffixRef = SpecialOperations.getCommonSuffixBytesRef(utf8);
}
runAutomaton = new ByteRunAutomaton(utf8, true);
- sortedTransitions = utf8.getSortedTransitions();
+ //utf8.writeDot("utf8");
+
+ lightAutomaton = runAutomaton.a;
}
+
+ private LightAutomaton.Transition scratch = new LightAutomaton.Transition();
//private static final boolean DEBUG = BlockTreeTermsWriter.DEBUG;
private BytesRef addTail(int state, BytesRef term, int idx, int leadLabel) {
-
+ //System.out.println("addTail state=" + state + " term=" + term.utf8ToString() + " idx=" + idx + " leadLabel=" + (char) leadLabel);
+ //System.out.println(lightAutomaton.toDot());
// Find biggest transition that's < label
// TODO: use binary search here
- Transition maxTransition = null;
- for (Transition transition : sortedTransitions[state]) {
- if (transition.min < leadLabel) {
- maxTransition = transition;
+ lightAutomaton.initTransition(state, scratch);
+ int numTransitions = lightAutomaton.getNumTransitions(state);
+ int maxIndex = -1;
+ int lastMin = 0;
+ for(int i=0;i<numTransitions;i++) {
+ lightAutomaton.getNextTransition(scratch);
+ if (scratch.min < leadLabel) {
+ maxIndex = i;
}
+ assert scratch.min >= lastMin;
+ lastMin = scratch.min;
+ // nocommit else break?
}
- assert maxTransition != null;
+ //System.out.println(" maxIndex=" + maxIndex);
+
+ assert maxIndex != -1;
+ lightAutomaton.getTransition(state, maxIndex, scratch);
// Append floorLabel
final int floorLabel;
- if (maxTransition.max > leadLabel-1) {
+ if (scratch.max > leadLabel-1) {
floorLabel = leadLabel-1;
} else {
- floorLabel = maxTransition.max;
+ floorLabel = scratch.max;
}
+ //System.out.println(" floorLabel=" + (char) floorLabel);
if (idx >= term.bytes.length) {
term.grow(1+idx);
}
//if (DEBUG) System.out.println(" add floorLabel=" + (char) floorLabel + " idx=" + idx);
term.bytes[idx] = (byte) floorLabel;
- state = maxTransition.to.getNumber();
+ state = scratch.dest;
+ //System.out.println(" dest: " + state);
idx++;
// Push down to last accept state
while (true) {
- Transition[] transitions = sortedTransitions[state];
- if (transitions.length == 0) {
+ numTransitions = lightAutomaton.getNumTransitions(state);
+ if (numTransitions == 0) {
+ //System.out.println("state=" + state + " 0 trans");
assert runAutomaton.isAccept(state);
term.length = idx;
//if (DEBUG) System.out.println(" return " + term.utf8ToString());
@@ -213,14 +331,15 @@ public class CompiledAutomaton {
} else {
// We are pushing "top" -- so get last label of
// last transition:
- assert transitions.length != 0;
- Transition lastTransition = transitions[transitions.length-1];
+ //System.out.println("get state=" + state + " numTrans=" + numTransitions);
+ lightAutomaton.getTransition(state, numTransitions-1, scratch);
if (idx >= term.bytes.length) {
term.grow(1+idx);
}
//if (DEBUG) System.out.println(" push maxLabel=" + (char) lastTransition.max + " idx=" + idx);
- term.bytes[idx] = (byte) lastTransition.max;
- state = lastTransition.to.getNumber();
+ //System.out.println(" add trans dest=" + scratch.dest + " label=" + (char) scratch.max);
+ term.bytes[idx] = (byte) scratch.max;
+ state = scratch.dest;
idx++;
}
}
@@ -301,33 +420,36 @@ public class CompiledAutomaton {
// Pop back to a state that has a transition
// <= our label:
while (true) {
- Transition[] transitions = sortedTransitions[state];
- if (transitions.length == 0) {
+ int numTransitions = lightAutomaton.getNumTransitions(state);
+ if (numTransitions == 0) {
assert runAutomaton.isAccept(state);
output.length = idx;
//if (DEBUG) System.out.println(" return " + output.utf8ToString());
return output;
- } else if (label-1 < transitions[0].min) {
+ } else {
+ lightAutomaton.getTransition(state, 0, scratch);
- if (runAutomaton.isAccept(state)) {
- output.length = idx;
- //if (DEBUG) System.out.println(" return " + output.utf8ToString());
- return output;
- }
- // pop
- if (stack.size() == 0) {
- //if (DEBUG) System.out.println(" pop ord=" + idx + " return null");
- return null;
+ if (label-1 < scratch.min) {
+
+ if (runAutomaton.isAccept(state)) {
+ output.length = idx;
+ //if (DEBUG) System.out.println(" return " + output.utf8ToString());
+ return output;
+ }
+ // pop
+ if (stack.size() == 0) {
+ //if (DEBUG) System.out.println(" pop ord=" + idx + " return null");
+ return null;
+ } else {
+ state = stack.remove(stack.size()-1);
+ idx--;
+ //if (DEBUG) System.out.println(" pop ord=" + (idx+1) + " label=" + (char) label + " first trans.min=" + (char) transitions[0].min);
+ label = input.bytes[input.offset + idx] & 0xff;
+ }
} else {
- state = stack.remove(stack.size()-1);
- idx--;
- //if (DEBUG) System.out.println(" pop ord=" + (idx+1) + " label=" + (char) label + " first trans.min=" + (char) transitions[0].min);
- label = input.bytes[input.offset + idx] & 0xff;
+ //if (DEBUG) System.out.println(" stop pop ord=" + idx + " first trans.min=" + (char) transitions[0].min);
+ break;
}
-
- } else {
- //if (DEBUG) System.out.println(" stop pop ord=" + idx + " first trans.min=" + (char) transitions[0].min);
- break;
}
}
@@ -350,18 +472,27 @@ public class CompiledAutomaton {
public String toDot() {
StringBuilder b = new StringBuilder("digraph CompiledAutomaton {\n");
b.append(" rankdir = LR;\n");
- int initial = runAutomaton.getInitialState();
- for (int i = 0; i < sortedTransitions.length; i++) {
+ int initial = 0;
+ for (int i = 0; i < lightAutomaton.getNumStates(); i++) {
b.append(" ").append(i);
- if (runAutomaton.isAccept(i)) b.append(" [shape=doublecircle,label=\"\"];\n");
+ if (lightAutomaton.isAccept(i)) b.append(" [shape=doublecircle,label=\"\"];\n");
else b.append(" [shape=circle,label=\"\"];\n");
- if (i == initial) {
+ if (i == 0) {
b.append(" initial [shape=plaintext,label=\"\"];\n");
b.append(" initial -> ").append(i).append("\n");
}
- for (int j = 0; j < sortedTransitions[i].length; j++) {
+ lightAutomaton.initTransition(i, scratch);
+ int numTransitions = lightAutomaton.getNumTransitions(i);
+ for (int j = 0; j < numTransitions; j++) {
b.append(" ").append(i);
- sortedTransitions[i][j].appendDot(b);
+ b.append(" -> ");
+ b.append(scratch.dest);
+ b.append(scratch.min);
+ if (scratch.min != scratch.max) {
+ b.append("-");
+ b.append(scratch.max);
+ }
+ lightAutomaton.getNextTransition(scratch);
}
}
return b.append("}\n").toString();
Added: lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/DaciukMihovAutomatonBuilderLight.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/DaciukMihovAutomatonBuilderLight.java?rev=1601967&view=auto
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/DaciukMihovAutomatonBuilderLight.java (added)
+++ lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/DaciukMihovAutomatonBuilderLight.java Wed Jun 11 17:35:26 2014
@@ -0,0 +1,334 @@
+package org.apache.lucene.util.automaton;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import java.util.*;
+
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.CharsRef;
+import org.apache.lucene.util.UnicodeUtil;
+
+/**
+ * Builds a minimal, deterministic {@link Automaton} that accepts a set of
+ * strings. The algorithm requires sorted input data, but is very fast
+ * (nearly linear with the input size).
+ *
+ * @see #build(Collection)
+ * @see BasicAutomata#makeStringUnion(Collection)
+ */
+final class DaciukMihovAutomatonBuilderLight {
+ /**
+ * DFSA state with <code>char</code> labels on transitions.
+ */
+ private final static class State {
+
+ /** An empty set of labels. */
+ private final static int[] NO_LABELS = new int[0];
+
+ /** An empty set of states. */
+ private final static State[] NO_STATES = new State[0];
+
+ /**
+ * Labels of outgoing transitions. Indexed identically to {@link #states}.
+ * Labels must be sorted lexicographically.
+ */
+ int[] labels = NO_LABELS;
+
+ /**
+ * States reachable from outgoing transitions. Indexed identically to
+ * {@link #labels}.
+ */
+ State[] states = NO_STATES;
+
+ /**
+ * <code>true</code> if this state corresponds to the end of at least one
+ * input sequence.
+ */
+ boolean is_final;
+
+ /**
+ * Returns the target state of a transition leaving this state and labeled
+ * with <code>label</code>. If no such transition exists, returns
+ * <code>null</code>.
+ */
+ State getState(int label) {
+ final int index = Arrays.binarySearch(labels, label);
+ return index >= 0 ? states[index] : null;
+ }
+
+ /**
+ * Two states are equal if:
+ * <ul>
+ * <li>they have an identical number of outgoing transitions, labeled with
+ * the same labels</li>
+ * <li>corresponding outgoing transitions lead to the same states (to states
+ * with an identical right-language).
+ * </ul>
+ */
+ @Override
+ public boolean equals(Object obj) {
+ final State other = (State) obj;
+ return is_final == other.is_final
+ && Arrays.equals(this.labels, other.labels)
+ && referenceEquals(this.states, other.states);
+ }
+
+ /**
+ * Compute the hash code of the <i>current</i> status of this state.
+ */
+ @Override
+ public int hashCode() {
+ int hash = is_final ? 1 : 0;
+
+ hash ^= hash * 31 + this.labels.length;
+ for (int c : this.labels)
+ hash ^= hash * 31 + c;
+
+ /*
+ * Compare the right-language of this state using reference-identity of
+ * outgoing states. This is possible because states are interned (stored
+ * in registry) and traversed in post-order, so any outgoing transitions
+ * are already interned.
+ */
+ for (State s : this.states) {
+ hash ^= System.identityHashCode(s);
+ }
+
+ return hash;
+ }
+
+ /**
+ * Return <code>true</code> if this state has any children (outgoing
+ * transitions).
+ */
+ boolean hasChildren() {
+ return labels.length > 0;
+ }
+
+ /**
+ * Create a new outgoing transition labeled <code>label</code> and return
+ * the newly created target state for this transition.
+ */
+ State newState(int label) {
+ assert Arrays.binarySearch(labels, label) < 0 : "State already has transition labeled: "
+ + label;
+
+ labels = Arrays.copyOf(labels, labels.length + 1);
+ states = Arrays.copyOf(states, states.length + 1);
+
+ labels[labels.length - 1] = label;
+ return states[states.length - 1] = new State();
+ }
+
+ /**
+ * Return the most recent transitions's target state.
+ */
+ State lastChild() {
+ assert hasChildren() : "No outgoing transitions.";
+ return states[states.length - 1];
+ }
+
+ /**
+ * Return the associated state if the most recent transition is labeled with
+ * <code>label</code>.
+ */
+ State lastChild(int label) {
+ final int index = labels.length - 1;
+ State s = null;
+ if (index >= 0 && labels[index] == label) {
+ s = states[index];
+ }
+ assert s == getState(label);
+ return s;
+ }
+
+ /**
+ * Replace the last added outgoing transition's target state with the given
+ * state.
+ */
+ void replaceLastChild(State state) {
+ assert hasChildren() : "No outgoing transitions.";
+ states[states.length - 1] = state;
+ }
+
+ /**
+ * Compare two lists of objects for reference-equality.
+ */
+ private static boolean referenceEquals(Object[] a1, Object[] a2) {
+ if (a1.length != a2.length) {
+ return false;
+ }
+
+ for (int i = 0; i < a1.length; i++) {
+ if (a1[i] != a2[i]) {
+ return false;
+ }
+ }
+
+ return true;
+ }
+ }
+
+ /**
+ * A "registry" for state interning.
+ */
+ private HashMap<State,State> stateRegistry = new HashMap<>();
+
+ /**
+ * Root automaton state.
+ */
+ private State root = new State();
+
+ /**
+ * Previous sequence added to the automaton in {@link #add(CharsRef)}.
+ */
+ private CharsRef previous;
+
+ /**
+ * A comparator used for enforcing sorted UTF8 order, used in assertions only.
+ */
+ @SuppressWarnings("deprecation")
+ private static final Comparator<CharsRef> comparator = CharsRef.getUTF16SortedAsUTF8Comparator();
+
+ /**
+ * Add another character sequence to this automaton. The sequence must be
+ * lexicographically larger or equal compared to any previous sequences added
+ * to this automaton (the input must be sorted).
+ */
+ public void add(CharsRef current) {
+ assert stateRegistry != null : "Automaton already built.";
+ assert previous == null
+ || comparator.compare(previous, current) <= 0 : "Input must be in sorted UTF-8 order: "
+ + previous + " >= " + current;
+ assert setPrevious(current);
+
+ // Descend in the automaton (find matching prefix).
+ int pos = 0, max = current.length();
+ State next, state = root;
+ while (pos < max && (next = state.lastChild(Character.codePointAt(current, pos))) != null) {
+ state = next;
+ // todo, optimize me
+ pos += Character.charCount(Character.codePointAt(current, pos));
+ }
+
+ if (state.hasChildren()) replaceOrRegister(state);
+
+ addSuffix(state, current, pos);
+ }
+
+ /**
+ * Finalize the automaton and return the root state. No more strings can be
+ * added to the builder after this call.
+ *
+ * @return Root automaton state.
+ */
+ public State complete() {
+ if (this.stateRegistry == null) throw new IllegalStateException();
+
+ if (root.hasChildren()) replaceOrRegister(root);
+
+ stateRegistry = null;
+ return root;
+ }
+
+ /**
+ * Internal recursive traversal for conversion.
+ */
+ private static int convert(LightAutomaton.Builder a, State s,
+ IdentityHashMap<State,Integer> visited) {
+
+ Integer converted = visited.get(s);
+ if (converted != null) {
+ return converted;
+ }
+
+ converted = a.createState();
+ a.setAccept(converted, s.is_final);
+
+ visited.put(s, converted);
+ int i = 0;
+ int[] labels = s.labels;
+ for (DaciukMihovAutomatonBuilderLight.State target : s.states) {
+ a.addTransition(converted, convert(a, target, visited), labels[i++]);
+ }
+
+ return converted;
+ }
+
+ /**
+ * Build a minimal, deterministic automaton from a sorted list of {@link BytesRef} representing
+ * strings in UTF-8. These strings must be binary-sorted.
+ */
+ public static LightAutomaton build(Collection<BytesRef> input) {
+ final DaciukMihovAutomatonBuilderLight builder = new DaciukMihovAutomatonBuilderLight();
+
+ CharsRef scratch = new CharsRef();
+ for (BytesRef b : input) {
+ UnicodeUtil.UTF8toUTF16(b, scratch);
+ builder.add(scratch);
+ }
+
+ LightAutomaton.Builder a = new LightAutomaton.Builder();
+ convert(a,
+ builder.complete(),
+ new IdentityHashMap<State,Integer>());
+
+ return a.finish();
+ }
+
+ /**
+ * Copy <code>current</code> into an internal buffer.
+ */
+ private boolean setPrevious(CharsRef current) {
+ // don't need to copy, once we fix https://issues.apache.org/jira/browse/LUCENE-3277
+ // still, called only from assert
+ previous = CharsRef.deepCopyOf(current);
+ return true;
+ }
+
+ /**
+ * Replace last child of <code>state</code> with an already registered state
+ * or stateRegistry the last child state.
+ */
+ private void replaceOrRegister(State state) {
+ final State child = state.lastChild();
+
+ if (child.hasChildren()) replaceOrRegister(child);
+
+ final State registered = stateRegistry.get(child);
+ if (registered != null) {
+ state.replaceLastChild(registered);
+ } else {
+ stateRegistry.put(child, child);
+ }
+ }
+
+ /**
+ * Add a suffix of <code>current</code> starting at <code>fromIndex</code>
+ * (inclusive) to state <code>state</code>.
+ */
+ private void addSuffix(State state, CharSequence current, int fromIndex) {
+ final int len = current.length();
+ while (fromIndex < len) {
+ int cp = Character.codePointAt(current, fromIndex);
+ state = state.newState(cp);
+ fromIndex += Character.charCount(cp);
+ }
+ state.is_final = true;
+ }
+}
Modified: lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/LevenshteinAutomata.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/LevenshteinAutomata.java?rev=1601967&r1=1601966&r2=1601967&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/LevenshteinAutomata.java (original)
+++ lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/LevenshteinAutomata.java Wed Jun 11 17:35:26 2014
@@ -178,6 +178,69 @@ public class LevenshteinAutomata {
//a.restoreInvariant();
return a;
}
+
+ /**
+ * Compute a DFA that accepts all strings within an edit distance of <code>n</code>.
+ * <p>
+ * All automata have the following properties:
+ * <ul>
+ * <li>They are deterministic (DFA).
+ * <li>There are no transitions to dead states.
+ * <li>They are not minimal (some transitions could be combined).
+ * </ul>
+ * </p>
+ */
+ public LightAutomaton toLightAutomaton(int n) {
+ if (n == 0) {
+ return BasicAutomata.makeString(word, 0, word.length).toLightAutomaton();
+ }
+
+ if (n >= descriptions.length)
+ return null;
+
+ final int range = 2*n+1;
+ ParametricDescription description = descriptions[n];
+ // the number of states is based on the length of the word and n
+ int numStates = description.size();
+
+ LightAutomaton a = new LightAutomaton();
+
+ // create all states, and mark as accept states if appropriate
+ for (int i = 0; i < numStates; i++) {
+ a.createState();
+ a.setAccept(i, description.isAccept(i));
+ }
+ // create transitions from state to state
+ for (int k = 0; k < numStates; k++) {
+ final int xpos = description.getPosition(k);
+ if (xpos < 0)
+ continue;
+ final int end = xpos + Math.min(word.length - xpos, range);
+
+ for (int x = 0; x < alphabet.length; x++) {
+ final int ch = alphabet[x];
+ // get the characteristic vector at this position wrt ch
+ final int cvec = getVector(ch, xpos, end);
+ int dest = description.transition(k, xpos, cvec);
+ if (dest >= 0) {
+ a.addTransition(k, dest, ch);
+ }
+ }
+ // add transitions for all other chars in unicode
+ // by definition, their characteristic vectors are always 0,
+ // because they do not exist in the input string.
+ int dest = description.transition(k, xpos, 0); // by definition
+ if (dest >= 0) {
+ for (int r = 0; r < numRanges; r++) {
+ a.addTransition(k, dest, rangeLower[r], rangeUpper[r]);
+ }
+ }
+ }
+
+ a.finish();
+
+ return a;
+ }
/**
* Get the characteristic vector <code>X(x, V)</code>
Added: lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/LightAutomaton.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/LightAutomaton.java?rev=1601967&view=auto
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/LightAutomaton.java (added)
+++ lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/LightAutomaton.java Wed Jun 11 17:35:26 2014
@@ -0,0 +1,793 @@
+package org.apache.lucene.util.automaton;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import java.io.IOException;
+import java.io.PrintWriter;
+import java.util.Arrays;
+import java.util.BitSet;
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.Set;
+
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.InPlaceMergeSorter;
+import org.apache.lucene.util.Sorter;
+
+// nocommit make tests that do the same ops w/ old and new and assertSameLang
+
+// TODO
+// - could use packed int arrays instead
+// - could encode dest w/ delta from to?
+
+// nocommit should we keep determinized bit?
+
+/** Uses only int[]s to represent the automaton, but requires that all
+ * transitions for each state are added at once. If this is too restrictive,
+ * use {@link #Builder} instead. State 0 is always the
+ * initial state.
+ *
+ * @lucene.experimental */
+
+// nocommit rename to Automaton once everything is cutover
+
+public class LightAutomaton {
+ private int nextState;
+
+ /** Where we next write to in int[] transitions; this
+ * increments by 3 for each added transition because we
+ * pack min, max, dest in sequence. */
+ private int nextTransition;
+
+ /** Current state we are adding transitions to; the caller
+ * must add all transitions for this state before moving
+ * onto another state. */
+ private int curState = -1;
+
+ /** Index in the transitions array, where this states
+ * leaving transitions are stored, or -1 if this state
+ * has not added any transitions yet, followed by number
+ * of transitions. */
+ private int[] states = new int[4];
+
+ /** Holds toState, min, max for each transition: */
+ // nocommit inefficient when labels are really bytes (max 256)
+ private int[] transitions = new int[6];
+
+ private final Set<Integer> finalStates = new HashSet<Integer>();
+
+ public int createState() {
+ growStates();
+ int state = nextState/2;
+ states[nextState] = -1;
+ nextState += 2;
+ return state;
+ }
+
+ /** Mark this state as an accept state. */
+ public void setAccept(int state, boolean isAccept) {
+ if (isAccept) {
+ finalStates.add(state);
+ } else {
+ finalStates.remove(state);
+ }
+ }
+
+ public boolean isEmpty() {
+ return finalStates.isEmpty();
+ }
+
+ /** Sugar, but object-heavy; it's better to iterate instead. */
+ public Transition[][] getSortedTransitions() {
+ int numStates = getNumStates();
+ Transition[][] transitions = new Transition[numStates][];
+ for(int s=0;s<numStates;s++) {
+ int numTransitions = getNumTransitions(s);
+ transitions[s] = new Transition[numTransitions];
+ for(int t=0;t<numTransitions;t++) {
+ Transition transition = new Transition();
+ getTransition(s, t, transition);
+ transitions[s][t] = transition;
+ }
+ }
+
+ return transitions;
+ }
+
+ public Set<Integer> getAcceptStates() {
+ return finalStates;
+ }
+
+ /** Returns true if this state is an accept state. */
+ public boolean isAccept(int state) {
+ return finalStates.contains(state);
+ }
+
+ public void addTransition(int source, int dest, int label) {
+ addTransition(source, dest, label, label);
+ }
+
+ public void addTransition(int source, int dest, int min, int max) {
+ assert nextTransition%3 == 0;
+
+ if (source >= nextState/2) {
+ throw new IllegalArgumentException("source is out of bounds");
+ }
+ if (dest >= nextState/2) {
+ throw new IllegalArgumentException("dest is out of bounds");
+ }
+
+ //System.out.println(" addTransition nextTransition=" + nextTransition + " source=" + source + " dest=" + dest + " min=" + min + " max=" + max);
+ growTransitions();
+ if (curState != source) {
+ //System.out.println(" newstate");
+ if (curState != -1) {
+ finishCurrentState();
+ }
+
+ // Move to next source:
+ curState = source;
+ if (states[2*curState] != -1) {
+ throw new IllegalStateException("from state (" + source + ") already had transitions added");
+ }
+ assert states[2*curState+1] == 0;
+ states[2*curState] = nextTransition;
+ }
+
+ transitions[nextTransition++] = dest;
+ transitions[nextTransition++] = min;
+ transitions[nextTransition++] = max;
+
+ // Increment transition count for this state
+ states[2*curState+1]++;
+ }
+
+ public void addEpsilon(int source, int dest) {
+ Transition t = new Transition();
+ int count = initTransition(dest, t);
+ for(int i=0;i<count;i++) {
+ getNextTransition(t);
+ addTransition(source, t.dest, t.min, t.max);
+ }
+ if (isAccept(dest)) {
+ setAccept(source, true);
+ }
+ }
+
+ /** Copies over all states/transitions from other. */
+ public void copy(LightAutomaton other) {
+ int offset = getNumStates();
+ int otherNumStates = other.getNumStates();
+ for(int s=0;s<otherNumStates;s++) {
+ createState();
+ setAccept(offset+s, other.isAccept(s));
+ }
+ Transition t = new Transition();
+ for(int s=0;s<otherNumStates;s++) {
+ int count = other.initTransition(s, t);
+ for(int i=0;i<count;i++) {
+ other.getNextTransition(t);
+ addTransition(offset + s, offset + t.dest, t.min, t.max);
+ }
+ }
+ }
+
+ /** Freezes the last state, reducing and sorting its transitions. */
+ private void finishCurrentState() {
+ int numTransitions = states[2*curState+1];
+ assert numTransitions > 0;
+
+ // System.out.println("finish curState=" + curState + " numTransitions=" + numTransitions);
+ int offset = states[2*curState];
+ int start = offset/3;
+ destMinMaxSorter.sort(start, start+numTransitions);
+
+ /*
+ for(int i=0;i<numTransitions;i++) {
+ System.out.println(" " + i + ": dest=" + transitions[offset+3*i] + " (accept?=" + isAccept(transitions[offset+3*i]) + ") min=" + transitions[offset+3*i+1] + " max=" + transitions[offset+3*i+2]);
+ }
+ */
+
+ // Reduce any "adjacent" transitions:
+ int upto = 0;
+ int min = -1;
+ int max = -1;
+ int dest = -1;
+
+ for(int i=0;i<numTransitions;i++) {
+ int tDest = transitions[offset+3*i];
+ int tMin = transitions[offset+3*i+1];
+ int tMax = transitions[offset+3*i+2];
+
+ if (dest == tDest) {
+ if (tMin <= max+1) {
+ if (tMax > max) {
+ max = tMax;
+ }
+ } else {
+ if (dest != -1) {
+ transitions[offset+3*upto] = dest;
+ transitions[offset+3*upto+1] = min;
+ transitions[offset+3*upto+2] = max;
+ upto++;
+ }
+ min = tMin;
+ max = tMax;
+ }
+ } else {
+ if (dest != -1) {
+ transitions[offset+3*upto] = dest;
+ transitions[offset+3*upto+1] = min;
+ transitions[offset+3*upto+2] = max;
+ upto++;
+ }
+ dest = tDest;
+ min = tMin;
+ max = tMax;
+ }
+ }
+
+ if (dest != -1) {
+ // Last transition
+ transitions[offset+3*upto] = dest;
+ transitions[offset+3*upto+1] = min;
+ transitions[offset+3*upto+2] = max;
+ upto++;
+ }
+
+ nextTransition -= (numTransitions-upto)*3;
+ states[2*curState+1] = upto;
+
+ // Sort transitions by min/max/dest:
+ minMaxDestSorter.sort(start, start+upto);
+
+ /*
+ System.out.println("after finish: reduce collapsed " + (numTransitions-upto) + " transitions");
+ for(int i=0;i<upto;i++) {
+ System.out.println(" " + i + ": dest=" + transitions[offset+3*i] + " (accept?=" + isAccept(transitions[offset+3*i]) + ") min=" + transitions[offset+3*i+1] + " max=" + transitions[offset+3*i+2]);
+ }
+ */
+ }
+
+ public void finish() {
+ if (curState != -1) {
+ //System.out.println("finish: finish current state " + curState);
+ finishCurrentState();
+ curState = -1;
+ }
+ // nocommit downsize the arrays?
+ //assert getNumStates() > 0;
+ }
+
+ public int getNumStates() {
+ return nextState/2;
+ }
+
+ public int getNumTransitions(int state) {
+ //assert curState == -1: "not finished";
+ int count = states[2*state+1];
+ if (count == -1) {
+ return 0;
+ } else {
+ return count;
+ }
+ }
+
+ public int getDest(int state, int transitionIndex) {
+ return transitions[states[2*state]];
+ }
+
+ public int getMin(int state, int transitionIndex) {
+ return transitions[states[2*state]+1];
+ }
+
+ public int getMax(int state, int transitionIndex) {
+ return transitions[states[2*state]+2];
+ }
+
+ private void growStates() {
+ if (nextState+2 >= states.length) {
+ states = ArrayUtil.grow(states, nextState+2);
+ }
+ }
+
+ private void growTransitions() {
+ if (nextTransition+3 >= transitions.length) {
+ transitions = ArrayUtil.grow(transitions, nextTransition+3);
+ }
+ }
+
+ /** Sorts transitions by dest, ascending, then min label ascending, then max label ascending */
+ private final Sorter destMinMaxSorter = new InPlaceMergeSorter() {
+
+ private void swapOne(int i, int j) {
+ int x = transitions[i];
+ transitions[i] = transitions[j];
+ transitions[j] = x;
+ }
+
+ @Override
+ protected void swap(int i, int j) {
+ int iStart = 3*i;
+ int jStart = 3*j;
+ swapOne(iStart, jStart);
+ swapOne(iStart+1, jStart+1);
+ swapOne(iStart+2, jStart+2);
+ };
+
+ @Override
+ protected int compare(int i, int j) {
+ int iStart = 3*i;
+ int jStart = 3*j;
+
+ // First dest:
+ int iDest = transitions[iStart];
+ int jDest = transitions[jStart];
+ if (iDest < jDest) {
+ return -1;
+ } else if (iDest > jDest) {
+ return 1;
+ }
+
+ // Then min:
+ int iMin = transitions[iStart+1];
+ int jMin = transitions[jStart+1];
+ if (iMin < jMin) {
+ return -1;
+ } else if (iMin > jMin) {
+ return 1;
+ }
+
+ // Then max:
+ int iMax = transitions[iStart+2];
+ int jMax = transitions[jStart+2];
+ if (iMax < jMax) {
+ return -1;
+ } else if (iMax > jMax) {
+ return 1;
+ }
+
+ return 0;
+ }
+ };
+
+ /** Sorts transitions by min label, ascending, then max label ascending, then dest ascending */
+ private final Sorter minMaxDestSorter = new InPlaceMergeSorter() {
+
+ private void swapOne(int i, int j) {
+ int x = transitions[i];
+ transitions[i] = transitions[j];
+ transitions[j] = x;
+ }
+
+ @Override
+ protected void swap(int i, int j) {
+ int iStart = 3*i;
+ int jStart = 3*j;
+ swapOne(iStart, jStart);
+ swapOne(iStart+1, jStart+1);
+ swapOne(iStart+2, jStart+2);
+ };
+
+ @Override
+ protected int compare(int i, int j) {
+ int iStart = 3*i;
+ int jStart = 3*j;
+
+ // First min:
+ int iMin = transitions[iStart+1];
+ int jMin = transitions[jStart+1];
+ if (iMin < jMin) {
+ return -1;
+ } else if (iMin > jMin) {
+ return 1;
+ }
+
+ // Then max:
+ int iMax = transitions[iStart+2];
+ int jMax = transitions[jStart+2];
+ if (iMax < jMax) {
+ return -1;
+ } else if (iMax > jMax) {
+ return 1;
+ }
+
+ // Then dest:
+ int iDest = transitions[iStart];
+ int jDest = transitions[jStart];
+ if (iDest < jDest) {
+ return -1;
+ } else if (iDest > jDest) {
+ return 1;
+ }
+
+ return 0;
+ }
+ };
+
+ /** Just used temporarily to return the transition from
+ * {@link getTransition} and {@link #getNextTransition}. */
+ public static class Transition {
+ // used only for assert:
+ public int source;
+ public int dest;
+ public int min;
+ public int max;
+
+ /** Remembers where we are in the iteration; init to -1 to provoke
+ * exception if nextTransition is called without first initTransition. */
+ private int transitionUpto = -1;
+
+ @Override
+ public String toString() {
+ return source + " --> " + dest + " " + (char) min + "-" + (char) max;
+ }
+
+ // nocommit equals? hashCode? don't want to encourage putting these into a Map...?
+ }
+
+ // nocommit createStates(int count)?
+
+ // nocommit kinda awkward iterator api...
+ /** Initialize the provided Transition for iteration; you
+ * must call {@link #getNextTransition} to get the first
+ * transition for the state. Returns the number of transitions
+ * leaving this state. */
+ public int initTransition(int state, Transition t) {
+ // assert curState == -1: "not finished";
+ t.source = state;
+ //System.out.println("initTrans source=" + state + " numTrans=" + getNumTransitions(state));
+ t.transitionUpto = states[2*state];
+ return getNumTransitions(state);
+ }
+
+ /** Iterate to the next transition after the provided one */
+ public void getNextTransition(Transition t) {
+ //assert curState == -1: "not finished";
+ // Make sure there is still a transition left:
+ //System.out.println("getNextTrans transUpto=" + t.transitionUpto);
+ //System.out.println(" states[2*t.source]=" + states[2*t.source] + " numTrans=" + states[2*t.source+1] + " transitionUpto+3=" + (t.transitionUpto+3) + " t=" + t);
+ assert (t.transitionUpto+3 - states[2*t.source]) <= 3*states[2*t.source+1];
+ t.dest = transitions[t.transitionUpto++];
+ t.min = transitions[t.transitionUpto++];
+ t.max = transitions[t.transitionUpto++];
+ }
+
+ /** Fill the provided {@link Transition} with the index'th
+ * transition leaving the specified state. */
+ public void getTransition(int state, int index, Transition t) {
+ assert curState == -1: "not finished";
+ int i = states[2*state] + 3*index;
+ t.source = state;
+ t.dest = transitions[i++];
+ t.min = transitions[i++];
+ t.max = transitions[i++];
+ }
+
+ private static void appendCharString(int c, StringBuilder b) {
+ if (c >= 0x21 && c <= 0x7e && c != '\\' && c != '"') b.appendCodePoint(c);
+ else {
+ b.append("\\\\U");
+ String s = Integer.toHexString(c);
+ if (c < 0x10) b.append("0000000").append(s);
+ else if (c < 0x100) b.append("000000").append(s);
+ else if (c < 0x1000) b.append("00000").append(s);
+ else if (c < 0x10000) b.append("0000").append(s);
+ else if (c < 0x100000) b.append("000").append(s);
+ else if (c < 0x1000000) b.append("00").append(s);
+ else if (c < 0x10000000) b.append("0").append(s);
+ else b.append(s);
+ }
+ }
+
+ public LightAutomaton totalize() {
+ LightAutomaton result = new LightAutomaton();
+ int numStates = getNumStates();
+ for(int i=0;i<numStates;i++) {
+ result.createState();
+ result.setAccept(i, isAccept(i));
+ }
+
+ int deadState = result.createState();
+ result.addTransition(deadState, deadState, Character.MIN_CODE_POINT, Character.MAX_CODE_POINT);
+
+ Transition t = new Transition();
+ for(int i=0;i<numStates;i++) {
+ int maxi = Character.MIN_CODE_POINT;
+ int count = initTransition(i, t);
+ for(int j=0;j<count;j++) {
+ getNextTransition(t);
+ result.addTransition(i, t.dest, t.min, t.max);
+ if (t.min > maxi) {
+ result.addTransition(i, deadState, maxi, t.min-1);
+ }
+ if (t.max + 1 > maxi) {
+ maxi = t.max + 1;
+ }
+ }
+
+ if (maxi <= Character.MAX_CODE_POINT) {
+ result.addTransition(i, deadState, maxi, Character.MAX_CODE_POINT);
+ }
+ }
+ result.finish();
+ return result;
+ }
+
+ public void writeDot(String fileName) {
+ if (fileName.indexOf('/') == -1) {
+ fileName = "/l/la/lucene/core/" + fileName + ".dot";
+ }
+ try {
+ PrintWriter pw = new PrintWriter(fileName);
+ pw.println(toDot());
+ pw.close();
+ } catch (IOException ioe) {
+ throw new RuntimeException(ioe);
+ }
+ }
+
+ public String toDot() {
+ // TODO: breadth first search so we can see get layered output...
+
+ StringBuilder b = new StringBuilder();
+ b.append("digraph Automaton {\n");
+ b.append(" rankdir = LR\n");
+ final int numStates = getNumStates();
+ if (numStates > 0) {
+ b.append(" initial [shape=plaintext,label=\"0\"]\n");
+ b.append(" initial -> 0\n");
+ }
+
+ Transition t = new Transition();
+
+ for(int state=0;state<numStates;state++) {
+ b.append(" ");
+ b.append(state);
+ if (isAccept(state)) {
+ b.append(" [shape=doublecircle,label=\"" + state + "\"]\n");
+ } else {
+ b.append(" [shape=circle,label=\"" + state + "\"]\n");
+ }
+ int numTransitions = getNumTransitions(state);
+ initTransition(state, t);
+ //System.out.println("toDot: state " + state + " has " + numTransitions + " transitions; t.nextTrans=" + t.transitionUpto);
+ for(int i=0;i<numTransitions;i++) {
+ getNextTransition(t);
+ //System.out.println(" t.nextTrans=" + t.transitionUpto);
+ assert t.max >= t.min;
+ b.append(" ");
+ b.append(state);
+ b.append(" -> ");
+ b.append(t.dest);
+ b.append(" [label=\"");
+ appendCharString(t.min, b);
+ if (t.max != t.min) {
+ b.append('-');
+ appendCharString(t.max, b);
+ }
+ b.append("\"]\n");
+ //System.out.println(" t=" + t);
+ }
+ }
+ b.append('}');
+ return b.toString();
+ }
+
+ /**
+ * Returns sorted array of all interval start points.
+ */
+ int[] getStartPoints() {
+ Set<Integer> pointset = new HashSet<>();
+ pointset.add(Character.MIN_CODE_POINT);
+ //System.out.println("getStartPoints");
+ for (int s=0;s<nextState;s+=2) {
+ int trans = states[s];
+ int limit = trans+3*states[s+1];
+ //System.out.println(" state=" + (s/2) + " trans=" + trans + " limit=" + limit);
+ while (trans < limit) {
+ int min = transitions[trans+1];
+ int max = transitions[trans+2];
+ //System.out.println(" min=" + min);
+ pointset.add(min);
+ if (max < Character.MAX_CODE_POINT) {
+ pointset.add(max + 1);
+ }
+ trans += 3;
+ }
+ }
+ int[] points = new int[pointset.size()];
+ int n = 0;
+ for (Integer m : pointset) {
+ points[n++] = m;
+ }
+ Arrays.sort(points);
+ return points;
+ }
+
+ /**
+ * Performs lookup in transitions, assuming determinism.
+ *
+ * @param c codepoint to look up
+ * @return destination state, -1 if no matching outgoing transition
+ * @see #step(int, Collection)
+ */
+ public int step(int state, int label) {
+ assert state >= 0;
+ assert label >= 0;
+ int trans = states[2*state];
+ int limit = trans + 3*states[2*state+1];
+ // nocommit we could do bin search; transitions are sorted
+ // System.out.println("la.step state=" + state + " label=" + label + " trans=" + trans + " limit=" + limit);
+ while (trans < limit) {
+ int dest = transitions[trans];
+ int min = transitions[trans+1];
+ int max = transitions[trans+2];
+ if (min <= label && label <= max) {
+ //System.out.println(" ret dest=" + dest);
+ return dest;
+ }
+ trans += 3;
+ }
+
+ return -1;
+ }
+
+ /** Records new states and transitions and then {@link
+ * #finish} creates the {@link LightAutomaton}. Use this
+ * when it's too restrictive to have to add all transitions
+ * leaving each state at once. */
+ public static class Builder {
+ private int[] transitions = new int[4];
+ private int nextTransition;
+ private final LightAutomaton a = new LightAutomaton();
+
+ public void addTransition(int from, int to, int label) {
+ addTransition(from, to, label, label);
+ }
+
+ public void addTransition(int from, int to, int min, int max) {
+ if (transitions.length < nextTransition+4) {
+ transitions = ArrayUtil.grow(transitions, nextTransition+4);
+ }
+ transitions[nextTransition++] = from;
+ transitions[nextTransition++] = to;
+ transitions[nextTransition++] = min;
+ transitions[nextTransition++] = max;
+ }
+
+ /** Sorts transitions first then min label ascending, then
+ * max label ascending, then dest ascending */
+ private final Sorter sorter = new InPlaceMergeSorter() {
+
+ private void swapOne(int i, int j) {
+ int x = transitions[i];
+ transitions[i] = transitions[j];
+ transitions[j] = x;
+ }
+
+ @Override
+ protected void swap(int i, int j) {
+ int iStart = 4*i;
+ int jStart = 4*j;
+ swapOne(iStart, jStart);
+ swapOne(iStart+1, jStart+1);
+ swapOne(iStart+2, jStart+2);
+ swapOne(iStart+3, jStart+3);
+ };
+
+ @Override
+ protected int compare(int i, int j) {
+ int iStart = 4*i;
+ int jStart = 4*j;
+
+ // First src:
+ int iSrc = transitions[iStart];
+ int jSrc = transitions[jStart];
+ if (iSrc < jSrc) {
+ return -1;
+ } else if (iSrc > jSrc) {
+ return 1;
+ }
+
+ // Then min:
+ int iMin = transitions[iStart+2];
+ int jMin = transitions[jStart+2];
+ if (iMin < jMin) {
+ return -1;
+ } else if (iMin > jMin) {
+ return 1;
+ }
+
+ // Then max:
+ int iMax = transitions[iStart+3];
+ int jMax = transitions[jStart+3];
+ if (iMax < jMax) {
+ return -1;
+ } else if (iMax > jMax) {
+ return 1;
+ }
+
+ // First dest:
+ int iDest = transitions[iStart+1];
+ int jDest = transitions[jStart+1];
+ if (iDest < jDest) {
+ return -1;
+ } else if (iDest > jDest) {
+ return 1;
+ }
+
+ return 0;
+ }
+ };
+
+ public LightAutomaton finish() {
+ //System.out.println("LA.Builder.finish: count=" + (nextTransition/4));
+ // nocommit: we could make this more efficient,
+ // e.g. somehow xfer the int[] to the automaton, or
+ // alloc exactly the right size from the automaton
+ //System.out.println("finish pending");
+ sorter.sort(0, nextTransition/4);
+ int upto = 0;
+ while (upto < nextTransition) {
+ a.addTransition(transitions[upto],
+ transitions[upto+1],
+ transitions[upto+2],
+ transitions[upto+3]);
+ upto += 4;
+ }
+
+ a.finish();
+ return a;
+ }
+
+ public int createState() {
+ return a.createState();
+ }
+
+ public void setAccept(int state, boolean accept) {
+ a.setAccept(state, accept);
+ }
+
+ public boolean isAccept(int state) {
+ return a.isAccept(state);
+ }
+
+ public int getNumStates() {
+ return a.getNumStates();
+ }
+
+ /** Copies over all states/transitions from other. */
+ public void copy(LightAutomaton other) {
+ int offset = getNumStates();
+ int otherNumStates = other.getNumStates();
+ for(int s=0;s<otherNumStates;s++) {
+ int newState = createState();
+ setAccept(newState, other.isAccept(s));
+ }
+ Transition t = new Transition();
+ for(int s=0;s<otherNumStates;s++) {
+ int count = other.initTransition(s, t);
+ for(int i=0;i<count;i++) {
+ other.getNextTransition(t);
+ addTransition(offset + s, offset + t.dest, t.min, t.max);
+ }
+ }
+ }
+ }
+}
Added: lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/LightAutomatonProvider.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/LightAutomatonProvider.java?rev=1601967&view=auto
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/LightAutomatonProvider.java (added)
+++ lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/LightAutomatonProvider.java Wed Jun 11 17:35:26 2014
@@ -0,0 +1,50 @@
+/*
+ * 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.io.IOException;
+
+/**
+ * Automaton provider for <code>RegExp.</code>
+ * {@link RegExp#toAutomaton(AutomatonProvider)}
+ *
+ * @lucene.experimental
+ */
+public interface LightAutomatonProvider {
+
+ /**
+ * Returns automaton of the given name.
+ *
+ * @param name automaton name
+ * @return automaton
+ * @throws IOException if errors occur
+ */
+ public LightAutomaton getAutomaton(String name) throws IOException;
+}
Added: lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/LightStatePair.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/LightStatePair.java?rev=1601967&view=auto
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/LightStatePair.java (added)
+++ lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/LightStatePair.java Wed Jun 11 17:35:26 2014
@@ -0,0 +1,89 @@
+/*
+ * 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;
+
+/**
+ * Pair of states.
+ *
+ * @lucene.experimental
+ */
+public class LightStatePair {
+ int s;
+ int s1;
+ int s2;
+
+ LightStatePair(int s, int s1, int s2) {
+ this.s = s;
+ this.s1 = s1;
+ this.s2 = s2;
+ }
+
+ /**
+ * Constructs a new state pair.
+ *
+ * @param s1 first state
+ * @param s2 second state
+ */
+ public LightStatePair(int s1, int s2) {
+ this.s1 = s1;
+ this.s2 = s2;
+ this.s = -1;
+ }
+
+ /**
+ * Checks for equality.
+ *
+ * @param obj object to compare with
+ * @return true if <tt>obj</tt> represents the same pair of states as this
+ * pair
+ */
+ @Override
+ public boolean equals(Object obj) {
+ if (obj instanceof LightStatePair) {
+ LightStatePair p = (LightStatePair) obj;
+ return p.s1 == s1 && p.s2 == s2;
+ } else return false;
+ }
+
+ /**
+ * Returns hash code.
+ *
+ * @return hash code
+ */
+ @Override
+ public int hashCode() {
+ return s1 ^ s2;
+ }
+
+ @Override
+ public String toString() {
+ return "LightStatePair(s1=" + s1 + " s2=" + s2 + ")";
+ }
+}
Added: lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/MinimizationOperationsLight.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/MinimizationOperationsLight.java?rev=1601967&view=auto
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/MinimizationOperationsLight.java (added)
+++ lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/MinimizationOperationsLight.java Wed Jun 11 17:35:26 2014
@@ -0,0 +1,308 @@
+/*
+ * 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.BitSet;
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.LinkedList;
+
+/**
+ * Operations for minimizing automata.
+ *
+ * @lucene.experimental
+ */
+final public class MinimizationOperationsLight {
+
+ private MinimizationOperationsLight() {}
+
+ /**
+ * Minimizes (and determinizes if not already deterministic) the given
+ * automaton.
+ *
+ * @see Automaton#setMinimization(int)
+ */
+ public static LightAutomaton minimize(LightAutomaton a) {
+ return minimizeHopcroft(a);
+ }
+
+ /**
+ * Minimizes the given automaton using Hopcroft's algorithm.
+ */
+ public static LightAutomaton minimizeHopcroft(LightAutomaton a) {
+ if (a.isEmpty()) {
+ return new LightAutomaton();
+ }
+ a = BasicOperations.determinize(a);
+ //a.writeDot("adet");
+ if (a.getNumTransitions(0) == 1) {
+ LightAutomaton.Transition t = new LightAutomaton.Transition();
+ a.getTransition(0, 0, t);
+ if (t.dest == 0 && t.min == Character.MIN_CODE_POINT
+ && t.max == Character.MAX_CODE_POINT) {
+ // Accepts all strings
+ return a;
+ }
+ }
+ a = a.totalize();
+ //a.writeDot("atot");
+
+ // initialize data structures
+ final int[] sigma = a.getStartPoints();
+ final int sigmaLen = sigma.length, statesLen = a.getNumStates();
+
+ @SuppressWarnings({"rawtypes","unchecked"}) final ArrayList<Integer>[][] reverse =
+ (ArrayList<Integer>[][]) new ArrayList[statesLen][sigmaLen];
+ @SuppressWarnings({"rawtypes","unchecked"}) final HashSet<Integer>[] partition =
+ (HashSet<Integer>[]) new HashSet[statesLen];
+ @SuppressWarnings({"rawtypes","unchecked"}) final ArrayList<Integer>[] splitblock =
+ (ArrayList<Integer>[]) new ArrayList[statesLen];
+ final int[] block = new int[statesLen];
+ final StateList[][] active = new StateList[statesLen][sigmaLen];
+ final StateListNode[][] active2 = new StateListNode[statesLen][sigmaLen];
+ final LinkedList<IntPair> pending = new LinkedList<>();
+ final BitSet pending2 = new BitSet(sigmaLen*statesLen);
+ final BitSet split = new BitSet(statesLen),
+ refine = new BitSet(statesLen), refine2 = new BitSet(statesLen);
+ for (int q = 0; q < statesLen; q++) {
+ splitblock[q] = new ArrayList<>();
+ partition[q] = new HashSet<>();
+ for (int x = 0; x < sigmaLen; x++) {
+ active[q][x] = new StateList();
+ }
+ }
+ // find initial partition and reverse edges
+ for (int q = 0; q < statesLen; q++) {
+ final int j = a.isAccept(q) ? 0 : 1;
+ partition[j].add(q);
+ block[q] = j;
+ for (int x = 0; x < sigmaLen; x++) {
+ final ArrayList<Integer>[] r = reverse[a.step(q, sigma[x])];
+ if (r[x] == null) {
+ r[x] = new ArrayList<>();
+ }
+ r[x].add(q);
+ }
+ }
+ // initialize active sets
+ for (int j = 0; j <= 1; j++) {
+ for (int x = 0; x < sigmaLen; x++) {
+ for (int q : partition[j]) {
+ if (reverse[q][x] != null) {
+ active2[q][x] = active[j][x].add(q);
+ }
+ }
+ }
+ }
+
+ // initialize pending
+ for (int x = 0; x < sigmaLen; x++) {
+ final int j = (active[0][x].size <= active[1][x].size) ? 0 : 1;
+ pending.add(new IntPair(j, x));
+ pending2.set(x*statesLen + j);
+ }
+
+ // process pending until fixed point
+ int k = 2;
+ //System.out.println("start min");
+ while (!pending.isEmpty()) {
+ //System.out.println(" cycle pending");
+ final IntPair ip = pending.removeFirst();
+ final int p = ip.n1;
+ final int x = ip.n2;
+ //System.out.println(" pop n1=" + ip.n1 + " n2=" + ip.n2);
+ pending2.clear(x*statesLen + p);
+ // find states that need to be split off their blocks
+ for (StateListNode m = active[p][x].first; m != null; m = m.next) {
+ final ArrayList<Integer> r = reverse[m.q][x];
+ if (r != null) {
+ for (int i : r) {
+ if (!split.get(i)) {
+ split.set(i);
+ final int j = block[i];
+ splitblock[j].add(i);
+ if (!refine2.get(j)) {
+ refine2.set(j);
+ refine.set(j);
+ }
+ }
+ }
+ }
+ }
+
+ // refine blocks
+ for (int j = refine.nextSetBit(0); j >= 0; j = refine.nextSetBit(j+1)) {
+ final ArrayList<Integer> sb = splitblock[j];
+ if (sb.size() < partition[j].size()) {
+ final HashSet<Integer> b1 = partition[j];
+ final HashSet<Integer> b2 = partition[k];
+ for (int s : sb) {
+ b1.remove(s);
+ b2.add(s);
+ block[s] = k;
+ for (int c = 0; c < sigmaLen; c++) {
+ final StateListNode sn = active2[s][c];
+ if (sn != null && sn.sl == active[j][c]) {
+ sn.remove();
+ active2[s][c] = active[k][c].add(s);
+ }
+ }
+ }
+ // update pending
+ for (int c = 0; c < sigmaLen; c++) {
+ final int aj = active[j][c].size,
+ ak = active[k][c].size,
+ ofs = c*statesLen;
+ if (!pending2.get(ofs + j) && 0 < aj && aj <= ak) {
+ pending2.set(ofs + j);
+ pending.add(new IntPair(j, c));
+ } else {
+ pending2.set(ofs + k);
+ pending.add(new IntPair(k, c));
+ }
+ }
+ k++;
+ }
+ refine2.clear(j);
+ for (int s : sb) {
+ split.clear(s);
+ }
+ sb.clear();
+ }
+ refine.clear();
+ }
+
+ LightAutomaton result = new LightAutomaton();
+
+ LightAutomaton.Transition t = new LightAutomaton.Transition();
+
+ //System.out.println(" k=" + k);
+
+ // make a new state for each equivalence class, set initial state
+ int[] stateMap = new int[statesLen];
+ int[] stateRep = new int[k];
+
+ // nocommit maybe LA should be born already with the initial state?
+ result.createState();
+
+ //System.out.println("min: k=" + k);
+ for (int n = 0; n < k; n++) {
+ //System.out.println(" n=" + n);
+
+ boolean isInitial = false;
+ for (int q : partition[n]) {
+ if (q == 0) {
+ isInitial = true;
+ //System.out.println(" isInitial!");
+ break;
+ }
+ }
+
+ int newState;
+ if (isInitial) {
+ newState = 0;
+ } else {
+ newState = result.createState();
+ }
+
+ //System.out.println(" newState=" + newState);
+
+ for (int q : partition[n]) {
+ stateMap[q] = newState;
+ //System.out.println(" q=" + q + " isAccept?=" + a.isAccept(q));
+ result.setAccept(newState, a.isAccept(q));
+ stateRep[newState] = q; // select representative
+ }
+ }
+
+ // build transitions and set acceptance
+ for (int n = 0; n < k; n++) {
+ int numTransitions = a.initTransition(stateRep[n], t);
+ for(int i=0;i<numTransitions;i++) {
+ a.getNextTransition(t);
+ //System.out.println(" add trans");
+ result.addTransition(n, stateMap[t.dest], t.min, t.max);
+ }
+ }
+ result.finish();
+ //System.out.println(result.getNumStates() + " states");
+
+ return BasicOperations.removeDeadTransitions(result);
+ }
+
+ static final class IntPair {
+
+ final int n1, n2;
+
+ IntPair(int n1, int n2) {
+ this.n1 = n1;
+ this.n2 = n2;
+ }
+ }
+
+ static final class StateList {
+
+ int size;
+
+ StateListNode first, last;
+
+ StateListNode add(int q) {
+ return new StateListNode(q, this);
+ }
+ }
+
+ static final class StateListNode {
+
+ final int q;
+
+ StateListNode next, prev;
+
+ final StateList sl;
+
+ StateListNode(int q, StateList sl) {
+ this.q = q;
+ this.sl = sl;
+ if (sl.size++ == 0) sl.first = sl.last = this;
+ else {
+ sl.last.next = this;
+ prev = sl.last;
+ sl.last = this;
+ }
+ }
+
+ void remove() {
+ sl.size--;
+ if (sl.first == this) sl.first = next;
+ else prev.next = next;
+ if (sl.last == this) sl.last = prev;
+ else next.prev = prev;
+ }
+ }
+}
Modified: lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/RegExp.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/RegExp.java?rev=1601967&r1=1601966&r2=1601967&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/RegExp.java (original)
+++ lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/RegExp.java Wed Jun 11 17:35:26 2014
@@ -419,17 +419,17 @@ public class RegExp {
to = e.to;
b = null;
}
-
+
/**
* Constructs new <code>Automaton</code> from this <code>RegExp</code>. Same
* as <code>toAutomaton(null)</code> (empty automaton map).
*/
- public Automaton toAutomaton() {
- return toAutomatonAllowMutate(null, null);
+ public LightAutomaton toLightAutomaton() {
+ return toLightAutomaton(null, null);
}
/**
- * Constructs new <code>Automaton</code> from this <code>RegExp</code>. The
+ * Constructs new <code>LightAutomaton</code> from this <code>RegExp</code>. The
* constructed automaton is minimal and deterministic and has no transitions
* to dead states.
*
@@ -437,9 +437,9 @@ public class RegExp {
* @exception IllegalArgumentException if this regular expression uses a named
* identifier that is not available from the automaton provider
*/
- public Automaton toAutomaton(AutomatonProvider automaton_provider)
+ public LightAutomaton toLightAutomaton(LightAutomatonProvider automaton_provider)
throws IllegalArgumentException {
- return toAutomatonAllowMutate(null, automaton_provider);
+ return toLightAutomaton(null, automaton_provider);
}
/**
@@ -448,49 +448,26 @@ public class RegExp {
* to dead states.
*
* @param automata a map from automaton identifiers to automata (of type
- * <code>Automaton</code>).
+ * <code>LightAutomaton</code>).
* @exception IllegalArgumentException if this regular expression uses a named
* identifier that does not occur in the automaton map
*/
- public Automaton toAutomaton(Map<String,Automaton> automata)
+ public LightAutomaton toLightAutomaton(Map<String,LightAutomaton> automata)
throws IllegalArgumentException {
- return toAutomatonAllowMutate(automata, null);
+ return toLightAutomaton(automata, null);
}
-
- /**
- * Sets or resets allow mutate flag. If this flag is set, then automata
- * construction uses mutable automata, which is slightly faster but not thread
- * safe. By default, the flag is not set.
- *
- * @param flag if true, the flag is set
- * @return previous value of the flag
- */
- public boolean setAllowMutate(boolean flag) {
- boolean b = allow_mutation;
- allow_mutation = flag;
- return b;
- }
-
- private Automaton toAutomatonAllowMutate(Map<String,Automaton> automata,
- AutomatonProvider automaton_provider) throws IllegalArgumentException {
- boolean b = false;
- if (allow_mutation) b = Automaton.setAllowMutate(true); // thread unsafe
- Automaton a = toAutomaton(automata, automaton_provider);
- if (allow_mutation) Automaton.setAllowMutate(b);
- return a;
- }
-
- private Automaton toAutomaton(Map<String,Automaton> automata,
- AutomatonProvider automaton_provider) throws IllegalArgumentException {
- List<Automaton> list;
- Automaton a = null;
+
+ private LightAutomaton toLightAutomaton(Map<String,LightAutomaton> automata,
+ LightAutomatonProvider automaton_provider) throws IllegalArgumentException {
+ List<LightAutomaton> list;
+ LightAutomaton a = null;
switch (kind) {
case REGEXP_UNION:
list = new ArrayList<>();
findLeaves(exp1, Kind.REGEXP_UNION, list, automata, automaton_provider);
findLeaves(exp2, Kind.REGEXP_UNION, list, automata, automaton_provider);
- a = BasicOperations.union(list);
- MinimizationOperations.minimize(a);
+ a = BasicOperations.unionLight(list);
+ MinimizationOperationsLight.minimize(a);
break;
case REGEXP_CONCATENATION:
list = new ArrayList<>();
@@ -498,77 +475,85 @@ public class RegExp {
automaton_provider);
findLeaves(exp2, Kind.REGEXP_CONCATENATION, list, automata,
automaton_provider);
- a = BasicOperations.concatenate(list);
- MinimizationOperations.minimize(a);
+ a = BasicOperations.concatenateLight(list);
+ MinimizationOperationsLight.minimize(a);
break;
case REGEXP_INTERSECTION:
- a = exp1.toAutomaton(automata, automaton_provider).intersection(
- exp2.toAutomaton(automata, automaton_provider));
- MinimizationOperations.minimize(a);
+ a = BasicOperations.intersectionLight(
+ exp1.toLightAutomaton(automata, automaton_provider),
+ exp2.toLightAutomaton(automata, automaton_provider));
+ a = MinimizationOperationsLight.minimize(a);
break;
case REGEXP_OPTIONAL:
- a = exp1.toAutomaton(automata, automaton_provider).optional();
- MinimizationOperations.minimize(a);
+ a = BasicOperations.optionalLight(exp1.toLightAutomaton(automata, automaton_provider));
+ a = MinimizationOperationsLight.minimize(a);
break;
case REGEXP_REPEAT:
- a = exp1.toAutomaton(automata, automaton_provider).repeat();
- MinimizationOperations.minimize(a);
+ a = BasicOperations.repeatLight(exp1.toLightAutomaton(automata, automaton_provider));
+ a = MinimizationOperationsLight.minimize(a);
break;
case REGEXP_REPEAT_MIN:
- a = exp1.toAutomaton(automata, automaton_provider).repeat(min);
- MinimizationOperations.minimize(a);
+ a = BasicOperations.repeatLight(exp1.toLightAutomaton(automata, automaton_provider), min);
+ a = MinimizationOperationsLight.minimize(a);
break;
case REGEXP_REPEAT_MINMAX:
- a = exp1.toAutomaton(automata, automaton_provider).repeat(min, max);
- MinimizationOperations.minimize(a);
+ a = BasicOperations.repeatLight(exp1.toLightAutomaton(automata, automaton_provider), min, max);
+ a = MinimizationOperationsLight.minimize(a);
break;
case REGEXP_COMPLEMENT:
- a = exp1.toAutomaton(automata, automaton_provider).complement();
- MinimizationOperations.minimize(a);
+ a = BasicOperations.complementLight(exp1.toLightAutomaton(automata, automaton_provider));
+ a = MinimizationOperationsLight.minimize(a);
break;
case REGEXP_CHAR:
- a = BasicAutomata.makeChar(c);
+ a = BasicAutomata.makeCharLight(c);
break;
case REGEXP_CHAR_RANGE:
- a = BasicAutomata.makeCharRange(from, to);
+ a = BasicAutomata.makeCharRangeLight(from, to);
break;
case REGEXP_ANYCHAR:
- a = BasicAutomata.makeAnyChar();
+ a = BasicAutomata.makeAnyCharLight();
break;
case REGEXP_EMPTY:
- a = BasicAutomata.makeEmpty();
+ a = BasicAutomata.makeEmptyLight();
break;
case REGEXP_STRING:
- a = BasicAutomata.makeString(s);
+ a = BasicAutomata.makeStringLight(s);
break;
case REGEXP_ANYSTRING:
- a = BasicAutomata.makeAnyString();
+ a = BasicAutomata.makeAnyStringLight();
break;
case REGEXP_AUTOMATON:
- Automaton aa = null;
- if (automata != null) aa = automata.get(s);
- if (aa == null && automaton_provider != null) try {
- aa = automaton_provider.getAutomaton(s);
- } catch (IOException e) {
- throw new IllegalArgumentException(e);
+ LightAutomaton aa = null;
+ if (automata != null) {
+ aa = automata.get(s);
+ }
+ if (aa == null && automaton_provider != null) {
+ try {
+ aa = automaton_provider.getAutomaton(s);
+ } catch (IOException e) {
+ throw new IllegalArgumentException(e);
+ }
+ }
+ if (aa == null) {
+ throw new IllegalArgumentException("'" + s + "' not found");
}
- if (aa == null) throw new IllegalArgumentException("'" + s
- + "' not found");
- a = aa.clone(); // always clone here (ignore allow_mutate)
+ a = aa;
break;
case REGEXP_INTERVAL:
- a = BasicAutomata.makeInterval(min, max, digits);
+ a = BasicAutomata.makeIntervalLight(min, max, digits);
break;
}
return a;
}
- private void findLeaves(RegExp exp, Kind kind, List<Automaton> list,
- Map<String,Automaton> automata, AutomatonProvider automaton_provider) {
+ private void findLeaves(RegExp exp, Kind kind, List<LightAutomaton> list,
+ Map<String,LightAutomaton> automata, LightAutomatonProvider automaton_provider) {
if (exp.kind == kind) {
findLeaves(exp.exp1, kind, list, automata, automaton_provider);
findLeaves(exp.exp2, kind, list, automata, automaton_provider);
- } else list.add(exp.toAutomaton(automata, automaton_provider));
+ } else {
+ list.add(exp.toLightAutomaton(automata, automaton_provider));
+ }
}
/**
Modified: lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/RunAutomaton.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/RunAutomaton.java?rev=1601967&r1=1601966&r2=1601967&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/RunAutomaton.java (original)
+++ lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/RunAutomaton.java Wed Jun 11 17:35:26 2014
@@ -37,6 +37,8 @@ import java.util.Arrays;
* @lucene.experimental
*/
public abstract class RunAutomaton {
+ // nocommit
+ final LightAutomaton a;
final int maxInterval;
final int size;
final boolean[] accept;
@@ -121,9 +123,13 @@ public abstract class RunAutomaton {
*/
public RunAutomaton(Automaton a, int maxInterval, boolean tableize) {
this.maxInterval = maxInterval;
+ this.a = null;
a.determinize();
+ //System.out.println("AFTER DET tableize=" + tableize + ": ");
+ //System.out.println(a.toDot());
points = a.getStartPoints();
final State[] states = a.getNumberedStates();
+ //System.out.println(" states=" + states.length);
initial = a.initial.number;
size = states.length;
accept = new boolean[size];
@@ -153,6 +159,52 @@ public abstract class RunAutomaton {
classmap = null;
}
}
+
+ public RunAutomaton(LightAutomaton a, int maxInterval, boolean tableize) {
+ this.maxInterval = maxInterval;
+ //System.out.println("before det a=" + a.getNumStates());
+ a = BasicOperations.determinize(a);
+ this.a = a;
+ //System.out.println("AFTER DET tableize= " + tableize + ": ");
+ //System.out.println(a.toDot());
+ points = a.getStartPoints();
+ //System.out.println(" points=" + Arrays.toString(points));
+ initial = 0;
+ size = Math.max(1,a.getNumStates());
+ accept = new boolean[size];
+ transitions = new int[size * points.length];
+ Arrays.fill(transitions, -1);
+ //System.out.println("RA: size=" + size + " points.length=" + points.length + " total=" + (size * points.length));
+ for (int n=0;n<size;n++) {
+ accept[n] = a.isAccept(n);
+ //System.out.println("n=" + n + " acc=" + accept[n] + " size=" + size);
+ for (int c = 0; c < points.length; c++) {
+ int dest = a.step(n, points[c]);
+ //System.out.println(" step from point=" + c + " n=" + n + " label=" + (char) points[c] + " -> " + dest);
+ assert dest == -1 || dest < size;
+ transitions[n * points.length + c] = dest;
+ //System.out.println(" trans label=" + points[c] + " dest=" + transitions[n * points.length + c]);
+ }
+ }
+
+ /*
+ * Set alphabet table for optimal run performance.
+ */
+ if (tableize) {
+ classmap = new int[maxInterval + 1];
+ int i = 0;
+ for (int j = 0; j <= maxInterval; j++) {
+ if (i + 1 < points.length && j == points[i + 1]) {
+ i++;
+ }
+ classmap[j] = i;
+ //System.out.println("classmap[" + (char) j + "]=" + i);
+ }
+ //System.out.println(" after classmap i=" + i + " maxInterval=" + maxInterval);
+ } else {
+ classmap = null;
+ }
+ }
/**
* Returns the state obtained by reading the given char from the given state.
@@ -162,10 +214,13 @@ public abstract class RunAutomaton {
* transition function.)
*/
public final int step(int state, int c) {
- if (classmap == null)
+ //System.out.println(" step state=" + state + " c=" + c + " points.length=" + points.length + " transitions.len=" + transitions.length);
+ if (classmap == null) {
return transitions[state * points.length + getCharClass(c)];
- else
+ } else {
+ //System.out.println(" classmap[c]=" + classmap[c]);
return transitions[state * points.length + classmap[c]];
+ }
}
@Override