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/17 11:37:42 UTC
svn commit: r1603106 - in /lucene/dev/branches/lucene5752/lucene: ./
core/src/java/org/apache/lucene/util/automaton/
core/src/test/org/apache/lucene/util/automaton/
test-framework/src/java/org/apache/lucene/util/
test-framework/src/java/org/apache/luce...
Author: mikemccand
Date: Tue Jun 17 09:37:41 2014
New Revision: 1603106
URL: http://svn.apache.org/r1603106
Log:
LUCENE-5752: remove last nocommits; turn on method-level javadocs for oal.util.automaton; improve tests
Modified:
lucene/dev/branches/lucene5752/lucene/build.xml
lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Automata.java
lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Automaton.java
lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/CompiledAutomaton.java
lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/DaciukMihovAutomatonBuilder.java
lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/LevenshteinAutomata.java
lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/MinimizationOperations.java
lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java
lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Transition.java
lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/UTF32ToUTF8.java
lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/util/automaton/TestAutomaton.java
lucene/dev/branches/lucene5752/lucene/test-framework/src/java/org/apache/lucene/util/TestRuleLimitSysouts.java
lucene/dev/branches/lucene5752/lucene/test-framework/src/java/org/apache/lucene/util/automaton/AutomatonTestUtil.java
Modified: lucene/dev/branches/lucene5752/lucene/build.xml
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/build.xml?rev=1603106&r1=1603105&r2=1603106&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/build.xml (original)
+++ lucene/dev/branches/lucene5752/lucene/build.xml Tue Jun 17 09:37:41 2014
@@ -258,6 +258,7 @@
<!-- test-framework: problems -->
<!-- too much to fix core/ for now, but enforce full javadocs for key packages -->
+ <check-missing-javadocs dir="build/docs/core/org/apache/lucene/util/automaton" level="method"/>
<check-missing-javadocs dir="build/docs/core/org/apache/lucene/analysis" level="method"/>
<check-missing-javadocs dir="build/docs/core/org/apache/lucene/document" level="method"/>
<check-missing-javadocs dir="build/docs/core/org/apache/lucene/search/similarities" level="method"/>
Modified: lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Automata.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Automata.java?rev=1603106&r1=1603105&r2=1603106&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Automata.java (original)
+++ lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Automata.java Tue Jun 17 09:37:41 2014
@@ -79,7 +79,8 @@ final public class Automata {
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 */
public static int appendAnyChar(Automaton a, int state) {
int newState = a.createState();
a.addTransition(state, newState, Character.MIN_CODE_POINT, Character.MAX_CODE_POINT);
@@ -93,7 +94,8 @@ final public class Automata {
public static Automaton makeChar(int c) {
return makeCharRange(c, c);
}
-
+
+ /** 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);
@@ -211,7 +213,7 @@ final public class Automata {
* interval)
* @param 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
+ * digits is not fixed (any number of leading 0s is accepted)
* @exception IllegalArgumentException if min>max or if numbers in the
* interval cannot be expressed with the given fixed number of
* digits
Modified: lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Automaton.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Automaton.java?rev=1603106&r1=1603105&r2=1603106&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Automaton.java (original)
+++ lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Automaton.java Tue Jun 17 09:37:41 2014
@@ -32,14 +32,24 @@ import org.apache.lucene.util.Sorter;
// - could use packed int arrays instead
// - could encode dest w/ delta from to?
-/** 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.
+/** Represents an automaton and all its states and transitions. States
+ * are integers and must be created using {@link #createState}. Mark a
+ * state as an accept state using {@link #setAccept}. Add transitions
+ * using {@link #addTransition}. Each state must have all of its
+ * transitions added at once; if this is too restrictive then use
+ * {@link Automaton.Builder} instead. State 0 is always the
+ * initial state. Once a state is finished, either
+ * because you've starting adding transitions to another state or you
+ * call {@link #finishState}, then that states transitions are sorted
+ * (first by min, then max, then dest) and reduced (transitions with
+ * adjacent labels going to the same dest are combined).
*
* @lucene.experimental */
public class Automaton {
+ /** Where we next write to the int[] states; this increments by 2 for
+ * each added state because we pack a pointer to the transitions
+ * array and a count of how many transitions leave the state. */
private int nextState;
/** Where we next write to in int[] transitions; this
@@ -58,14 +68,19 @@ public class Automaton {
* of transitions. */
private int[] states = new int[4];
- /** Holds toState, min, max for each transition: */
+ /** Holds toState, min, max for each transition. */
private int[] transitions = new int[6];
- private final Set<Integer> finalStates = new HashSet<Integer>();
+ private final Set<Integer> acceptStates = new HashSet<Integer>();
/** True if no state has two transitions leaving with the same label. */
private boolean deterministic = true;
+ /** Sole constructor; creates an automaton with no states. */
+ public Automaton() {
+ }
+
+ /** Create a new state. */
public int createState() {
growStates();
int state = nextState/2;
@@ -74,19 +89,20 @@ public class Automaton {
return state;
}
- /** Mark this state as an accept state. */
+ /** Set or clear this state as an accept state. */
public void setAccept(int state, boolean isAccept) {
if (state >= getNumStates()) {
throw new IllegalArgumentException("state=" + state + " is out of bounds (numStates=" + getNumStates() + ")");
}
if (isAccept) {
- finalStates.add(state);
+ acceptStates.add(state);
} else {
- finalStates.remove(state);
+ acceptStates.remove(state);
}
}
- /** Sugar, but object-heavy; it's better to iterate instead. */
+ /** Sugar to get all transitions for all states. This is
+ * object-heavy; it's better to iterate state by state instead. */
public Transition[][] getSortedTransitions() {
int numStates = getNumStates();
Transition[][] transitions = new Transition[numStates][];
@@ -103,19 +119,22 @@ public class Automaton {
return transitions;
}
+ /** Returns accept states. */
public Set<Integer> getAcceptStates() {
- return finalStates;
+ return acceptStates;
}
/** Returns true if this state is an accept state. */
public boolean isAccept(int state) {
- return finalStates.contains(state);
+ return acceptStates.contains(state);
}
+ /** Add a new transition with min = max = label. */
public void addTransition(int source, int dest, int label) {
addTransition(source, dest, label, label);
}
+ /** Add a new transition with the specified source, dest, min, max. */
public void addTransition(int source, int dest, int min, int max) {
assert nextTransition%3 == 0;
@@ -126,10 +145,8 @@ public class Automaton {
throw new IllegalArgumentException("dest=" + dest + " is out of bounds (max state is " + (nextState/2-1) + ")");
}
- //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();
}
@@ -151,6 +168,9 @@ public class Automaton {
states[2*curState+1]++;
}
+ /** Add a [virtual] epsilon transition between source and dest.
+ * Dest state must already have all transitions added because this
+ * method simply copies those same transitions over to source. */
public void addEpsilon(int source, int dest) {
Transition t = new Transition();
int count = initTransition(dest, t);
@@ -167,23 +187,6 @@ public class Automaton {
* are sequentially assigned (appended). */
public void copy(Automaton 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);
- }
- }
- */
-
// Bulk copy and then fixup the state pointers:
int stateOffset = getNumStates();
states = ArrayUtil.grow(states, nextState + other.nextState);
@@ -213,22 +216,15 @@ public class Automaton {
}
}
- /** Freezes the last state, reducing and sorting its transitions. */
+ /** Freezes the last state, sorting and reducing the 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;
@@ -293,23 +289,20 @@ public class Automaton {
lastMax = transitions[offset + 3*i + 2];
}
}
-
- /*
- 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]);
- }
- */
}
+ /** Returns true if this automaton is deterministic (for ever state
+ * there is only one transition for each label). */
public boolean isDeterministic() {
return deterministic;
}
- /** Finishes the current state; call this once you are done adding transitions for a state. */
+ /** Finishes the current state; call this once you are done adding
+ * transitions for a state. This is automatically called if you
+ * start adding transitions to a new source state, but for the last
+ * state you add you need to this method yourself. */
public void finishState() {
if (curState != -1) {
- //System.out.println("finish: finish current state " + curState);
finishCurrentState();
curState = -1;
}
@@ -317,10 +310,12 @@ public class Automaton {
// TODO: add finish() to shrink wrap the arrays?
+ /** How many states this automaton has. */
public int getNumStates() {
return nextState/2;
}
+ /** How many transitions this state has. */
public int getNumTransitions(int state) {
int count = states[2*state+1];
if (count == -1) {
@@ -330,18 +325,6 @@ public class Automaton {
}
}
- 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);
@@ -508,42 +491,6 @@ public class Automaton {
}
}
- // nocommit move to Operations
- public Automaton totalize() {
- Automaton result = new Automaton();
- 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.finishState();
- return result;
- }
-
- // nocommit
/*
public void writeDot(String fileName) {
if (fileName.indexOf('/') == -1) {
@@ -559,6 +506,8 @@ public class Automaton {
}
*/
+ /** Returns the dot (graphviz) representation of this automaton.
+ * This is extremely useful for visualizing the automaton. */
public String toDot() {
// TODO: breadth first search so we can see get layered output...
@@ -640,9 +589,9 @@ public class Automaton {
/**
* Performs lookup in transitions, assuming determinism.
*
- * @param c codepoint to look up
+ * @param state starting state
+ * @param label 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;
@@ -665,23 +614,30 @@ public class Automaton {
/** Records new states and transitions and then {@link
* #finish} creates the {@link Automaton}. Use this
- * when it's too restrictive to have to add all transitions
+ * when you cannot create the Automaton directly because
+ * 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 Automaton a = new Automaton();
- public void addTransition(int from, int to, int label) {
- addTransition(from, to, label, label);
+ /** Sole constructor. */
+ public Builder() {
+ }
+
+ /** Add a new transition with min = max = label. */
+ public void addTransition(int source, int dest, int label) {
+ addTransition(source, dest, label, label);
}
- public void addTransition(int from, int to, int min, int max) {
+ /** Add a new transition with the specified source, dest, min, max. */
+ public void addTransition(int source, int dest, int min, int max) {
if (transitions.length < nextTransition+4) {
transitions = ArrayUtil.grow(transitions, nextTransition+4);
}
- transitions[nextTransition++] = from;
- transitions[nextTransition++] = to;
+ transitions[nextTransition++] = source;
+ transitions[nextTransition++] = dest;
transitions[nextTransition++] = min;
transitions[nextTransition++] = max;
}
@@ -751,9 +707,11 @@ public class Automaton {
}
};
+ /** Compiles all added states and transitions into a new {@code Automaton}
+ * and returns it. */
public Automaton finish() {
//System.out.println("LA.Builder.finish: count=" + (nextTransition/4));
- // nocommit: we could make this more efficient,
+ // TODO: 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");
@@ -771,18 +729,22 @@ public class Automaton {
return a;
}
+ /** Create a new state. */
public int createState() {
return a.createState();
}
+ /** Set or clear this state as an accept state. */
public void setAccept(int state, boolean accept) {
a.setAccept(state, accept);
}
+ /** Returns true if this state is an accept state. */
public boolean isAccept(int state) {
return a.isAccept(state);
}
+ /** How many states this automaton has. */
public int getNumStates() {
return a.getNumStates();
}
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=1603106&r1=1603105&r2=1603106&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 Tue Jun 17 09:37:41 2014
@@ -51,6 +51,8 @@ public class CompiledAutomaton {
/** Catch-all for any other automata. */
NORMAL
};
+
+ /** If simplify is true this will be the "simplified" type; else, this is NORMAL */
public final AUTOMATON_TYPE type;
/**
@@ -87,10 +89,16 @@ public class CompiledAutomaton {
*/
public final Boolean finite;
+ /** Create this, passing simplify=true and finite=null, so that we try
+ * to simplify the automaton and determine if it is finite. */
public CompiledAutomaton(Automaton automaton) {
this(automaton, null, true);
}
+ /** Create this. If finite is null, we use {@link Operations#isFinite}
+ * to determine whether it is finite. If simplify is true, we run
+ * possibly expensive operations to determine if the automaton is one
+ * the cases in {@link CompiledAutomaton.AUTOMATON_TYPE}. */
public CompiledAutomaton(Automaton automaton, Boolean finite, boolean simplify) {
if (simplify) {
@@ -251,6 +259,8 @@ public class CompiledAutomaton {
// TODO: should this take startTerm too? This way
// Terms.intersect could forward to this method if type !=
// NORMAL:
+ /** Return a {@link TermsEnum} intersecting the provided {@link Terms}
+ * with the terms accepted by this automaton. */
public TermsEnum getTermsEnum(Terms terms) throws IOException {
switch(type) {
case NONE:
@@ -371,34 +381,6 @@ public class CompiledAutomaton {
}
}
}
-
- public String toDot() {
- StringBuilder b = new StringBuilder("digraph CompiledAutomaton {\n");
- b.append(" rankdir = LR;\n");
- int initial = 0;
- for (int i = 0; i < automaton.getNumStates(); i++) {
- b.append(" ").append(i);
- if (automaton.isAccept(i)) b.append(" [shape=doublecircle,label=\"\"];\n");
- else b.append(" [shape=circle,label=\"\"];\n");
- if (i == 0) {
- b.append(" initial [shape=plaintext,label=\"\"];\n");
- b.append(" initial -> ").append(i).append("\n");
- }
- int numTransitions = automaton.initTransition(i, transition);
- for (int j = 0; j < numTransitions; j++) {
- b.append(" ").append(i);
- b.append(" -> ");
- b.append(transition.dest);
- b.append(transition.min);
- if (transition.min != transition.max) {
- b.append("-");
- b.append(transition.max);
- }
- automaton.getNextTransition(transition);
- }
- }
- return b.append("}\n").toString();
- }
@Override
public int hashCode() {
Modified: lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/DaciukMihovAutomatonBuilder.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/DaciukMihovAutomatonBuilder.java?rev=1603106&r1=1603105&r2=1603106&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/DaciukMihovAutomatonBuilder.java (original)
+++ lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/DaciukMihovAutomatonBuilder.java Tue Jun 17 09:37:41 2014
@@ -29,7 +29,7 @@ import org.apache.lucene.util.UnicodeUti
* (nearly linear with the input size).
*
* @see #build(Collection)
- * @see BasicAutomata#makeStringUnion(Collection)
+ * @see Automata#makeStringUnion(Collection)
*/
final class DaciukMihovAutomatonBuilder {
/**
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=1603106&r1=1603105&r2=1603106&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 Tue Jun 17 09:37:41 2014
@@ -32,7 +32,8 @@ import org.apache.lucene.util.UnicodeUti
* @lucene.experimental
*/
public class LevenshteinAutomata {
- /** @lucene.internal */
+ /** Maximum edit distance this class can generate an automaton for.
+ * @lucene.internal */
public static final int MAXIMUM_SUPPORTED_DISTANCE = 2;
/* input word */
final int word[];
@@ -130,6 +131,18 @@ public class LevenshteinAutomata {
return toAutomaton(n, "");
}
+ /**
+ * Compute a DFA that accepts all strings within an edit distance of <code>n</code>,
+ * matching the specified exact prefix.
+ * <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 Automaton toAutomaton(int n, String prefix) {
assert prefix != null;
if (n == 0) {
Modified: lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/MinimizationOperations.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/MinimizationOperations.java?rev=1603106&r1=1603105&r2=1603106&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/MinimizationOperations.java (original)
+++ lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/MinimizationOperations.java Tue Jun 17 09:37:41 2014
@@ -46,8 +46,6 @@ final public class MinimizationOperation
/**
* Minimizes (and determinizes if not already deterministic) the given
* automaton.
- *
- * @see Automaton#setMinimization(int)
*/
public static Automaton minimize(Automaton a) {
return minimizeHopcroft(a);
@@ -72,7 +70,7 @@ final public class MinimizationOperation
return a;
}
}
- a = a.totalize();
+ a = Operations.totalize(a);
//a.writeDot("atot");
// initialize data structures
Modified: lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java?rev=1603106&r1=1603105&r2=1603106&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java (original)
+++ lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java Tue Jun 17 09:37:41 2014
@@ -265,7 +265,7 @@ final public class Operations {
* Complexity: linear in number of states (if already deterministic).
*/
static public Automaton complement(Automaton a) {
- a = determinize(a).totalize();
+ a = totalize(determinize(a));
int numStates = a.getNumStates();
for (int p=0;p<numStates;p++) {
a.setAccept(p, !a.isAccept(p));
@@ -465,6 +465,12 @@ final public class Operations {
return union(Arrays.asList(a1, a2));
}
+ /**
+ * Returns an automaton that accepts the union of the languages of the given
+ * automata.
+ * <p>
+ * Complexity: linear in number of states.
+ */
public static Automaton union(Collection<Automaton> l) {
Automaton result = new Automaton();
@@ -1042,6 +1048,15 @@ final public class Operations {
return b.toString();
}
+ // TODO: this currently requites a determinized machine,
+ // but it need not -- we can speed it up by walking the
+ // NFA instead. it'd still be fail fast.
+ /**
+ * Returns the longest BytesRef that is a prefix of all accepted strings and
+ * visits each state at most once. The automaton must be deterministic.
+ *
+ * @return common prefix
+ */
public static BytesRef getCommonPrefixBytesRef(Automaton a) {
BytesRef ref = new BytesRef(10);
HashSet<Integer> visited = new HashSet<>();
@@ -1065,6 +1080,13 @@ final public class Operations {
return ref;
}
+ /**
+ * Returns the longest BytesRef that is a suffix of all accepted strings.
+ * Worst case complexity: exponential in number of states (this calls
+ * determinize).
+ *
+ * @return common suffix
+ */
public static BytesRef getCommonSuffixBytesRef(Automaton a) {
// reverse the language of the automaton, then reverse its common prefix.
Automaton r = Operations.determinize(reverse(a));
@@ -1082,12 +1104,14 @@ final public class Operations {
ref.bytes[ref.offset * 2 + ref.length - i - 1] = b;
}
}
-
+
+ /** Returns an automaton accepting the reverse language. */
public static Automaton reverse(Automaton a) {
return reverse(a, null);
}
- public static Automaton reverse(Automaton a, Set<Integer> initialStates) {
+ /** Reverses the automaton, returning the new initial states. */
+ static Automaton reverse(Automaton a, Set<Integer> initialStates) {
if (Operations.isEmpty(a)) {
return new Automaton();
@@ -1282,4 +1306,42 @@ final public class Operations {
return results;
}
+
+ /** Returns a new automaton accepting the same language with added
+ * transitions to a dead state so that from every state and every label
+ * there is a transition. */
+ static Automaton totalize(Automaton a) {
+ Automaton result = new Automaton();
+ int numStates = a.getNumStates();
+ for(int i=0;i<numStates;i++) {
+ result.createState();
+ result.setAccept(i, a.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 = a.initTransition(i, t);
+ for(int j=0;j<count;j++) {
+ a.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.finishState();
+ return result;
+ }
}
Modified: lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Transition.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Transition.java?rev=1603106&r1=1603105&r2=1603106&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Transition.java (original)
+++ lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Transition.java Tue Jun 17 09:37:41 2014
@@ -17,13 +17,24 @@ package org.apache.lucene.util.automaton
* limitations under the License.
*/
-/** Used temporarily when iterating through transitions from a {@link LightAutomaton}
- * {@link getTransition} and {@link #getNextTransition}. */
+/** Used temporarily when iterating through transitions from a {@link Automaton}
+ * {@link Automaton#initTransition} and {@link Automaton#getNextTransition}. */
public class Transition {
+ /** Sole constructor. */
+ public Transition() {
+ }
+
+ /** Source state. */
public int source;
+
+ /** Destination state. */
public int dest;
+
+ /** Minimum accepted label (inclusive). */
public int min;
+
+ /** Maximum accepted label (inclusive). */
public int max;
/** Remembers where we are in the iteration; init to -1 to provoke
Modified: lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/UTF32ToUTF8.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/UTF32ToUTF8.java?rev=1603106&r1=1603105&r2=1603106&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/UTF32ToUTF8.java (original)
+++ lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/UTF32ToUTF8.java Tue Jun 17 09:37:41 2014
@@ -120,6 +120,10 @@ public final class UTF32ToUTF8 {
}
}
+ /** Sole constructor. */
+ public UTF32ToUTF8() {
+ }
+
private final UTF8Sequence startUTF8 = new UTF8Sequence();
private final UTF8Sequence endUTF8 = new UTF8Sequence();
Modified: lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/util/automaton/TestAutomaton.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/util/automaton/TestAutomaton.java?rev=1603106&r1=1603105&r2=1603106&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/util/automaton/TestAutomaton.java (original)
+++ lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/util/automaton/TestAutomaton.java Tue Jun 17 09:37:41 2014
@@ -571,7 +571,7 @@ public class TestAutomaton extends Lucen
}
private Automaton randomNoOp(Automaton a) {
- switch (random().nextInt(5)) {
+ switch (random().nextInt(7)) {
case 0:
if (VERBOSE) {
System.out.println(" randomNoOp: determinize");
@@ -604,6 +604,11 @@ public class TestAutomaton extends Lucen
System.out.println(" randomNoOp: union empty automaton");
}
return Operations.union(a, Automata.makeEmpty());
+ case 6:
+ if (VERBOSE) {
+ System.out.println(" randomNoOp: do nothing!");
+ }
+ return a;
}
assert false;
return null;
@@ -632,12 +637,9 @@ public class TestAutomaton extends Lucen
return randomNoOp(a);
}
- private String getRandomString(boolean isAscii) {
- if (isAscii) {
- return TestUtil.randomSimpleString(random());
- } else {
- return TestUtil.randomRealisticUnicodeString(random());
- }
+ private String getRandomString() {
+ //return TestUtil.randomSimpleString(random());
+ return TestUtil.randomRealisticUnicodeString(random());
}
public void testRandomFinite() throws Exception {
@@ -645,16 +647,13 @@ public class TestAutomaton extends Lucen
int numTerms = atLeast(10);
int iters = atLeast(100);
- // Some of the ops we do (stripping random byte, reverse) turn valid UTF8 into invalid if we allow non-ascii:
- boolean isAscii = random().nextBoolean();
-
if (VERBOSE) {
- System.out.println("TEST: isAscii=" + isAscii + " numTerms" + numTerms + " iters=" + iters);
+ System.out.println("TEST: numTerms" + numTerms + " iters=" + iters);
}
Set<BytesRef> terms = new HashSet<>();
while (terms.size() < numTerms) {
- terms.add(new BytesRef(getRandomString(isAscii)));
+ terms.add(new BytesRef(getRandomString()));
}
Automaton a = unionTerms(terms);
@@ -668,7 +667,7 @@ public class TestAutomaton extends Lucen
System.out.println(" " + term);
}
}
- switch(random().nextInt(14)) {
+ switch(random().nextInt(15)) {
case 0:
// concatenate prefix
@@ -677,7 +676,7 @@ public class TestAutomaton extends Lucen
System.out.println(" op=concat prefix");
}
Set<BytesRef> newTerms = new HashSet<>();
- BytesRef prefix = new BytesRef(getRandomString(isAscii));
+ BytesRef prefix = new BytesRef(getRandomString());
for(BytesRef term : terms) {
BytesRef newTerm = BytesRef.deepCopyOf(prefix);
newTerm.append(term);
@@ -693,7 +692,7 @@ public class TestAutomaton extends Lucen
case 1:
// concatenate suffix
{
- BytesRef suffix = new BytesRef(getRandomString(isAscii));
+ BytesRef suffix = new BytesRef(getRandomString());
if (VERBOSE) {
System.out.println(" op=concat suffix " + suffix);
}
@@ -708,8 +707,6 @@ public class TestAutomaton extends Lucen
}
break;
- // nocommit sometimes concat a suffix accepting more than 1 term, and sometimes non-det
-
case 2:
// determinize
if (VERBOSE) {
@@ -736,7 +733,7 @@ public class TestAutomaton extends Lucen
Set<BytesRef> newTerms = new HashSet<>();
int numNewTerms = random().nextInt(5);
while (newTerms.size() < numNewTerms) {
- newTerms.add(new BytesRef(getRandomString(isAscii)));
+ newTerms.add(new BytesRef(getRandomString()));
}
terms.addAll(newTerms);
Automaton newA = unionTerms(newTerms);
@@ -879,15 +876,17 @@ public class TestAutomaton extends Lucen
case 9:
// reverse
- if (VERBOSE) {
- System.out.println(" op=reverse");
- }
- a = Operations.reverse(a);
- Set<BytesRef> newTerms = new HashSet<>();
- for(BytesRef term : terms) {
- newTerms.add(new BytesRef(new StringBuilder(term.utf8ToString()).reverse().toString()));
+ {
+ if (VERBOSE) {
+ System.out.println(" op=reverse");
+ }
+ a = Operations.reverse(a);
+ Set<BytesRef> newTerms = new HashSet<>();
+ for(BytesRef term : terms) {
+ newTerms.add(new BytesRef(new StringBuilder(term.utf8ToString()).reverse().toString()));
+ }
+ terms = newTerms;
}
- terms = newTerms;
break;
case 10:
@@ -899,26 +898,28 @@ public class TestAutomaton extends Lucen
case 11:
// interval
- int min = random().nextInt(1000);
- int max = min + random().nextInt(50);
- // digits must be non-zero else we make cycle
- int digits = Integer.toString(max).length();
- if (VERBOSE) {
- System.out.println(" op=union interval min=" + min + " max=" + max + " digits=" + digits);
- }
- a = Operations.union(a, Automata.makeInterval(min, max, digits));
- StringBuilder b = new StringBuilder();
- for(int i=0;i<digits;i++) {
- b.append('0');
- }
- String prefix = b.toString();
- for(int i=min;i<=max;i++) {
- String s = Integer.toString(i);
- if (s.length() < digits) {
- // Left-fill with 0s
- s = prefix.substring(s.length()) + s;
+ {
+ int min = random().nextInt(1000);
+ int max = min + random().nextInt(50);
+ // digits must be non-zero else we make cycle
+ int digits = Integer.toString(max).length();
+ if (VERBOSE) {
+ System.out.println(" op=union interval min=" + min + " max=" + max + " digits=" + digits);
+ }
+ a = Operations.union(a, Automata.makeInterval(min, max, digits));
+ StringBuilder b = new StringBuilder();
+ for(int i=0;i<digits;i++) {
+ b.append('0');
+ }
+ String prefix = b.toString();
+ for(int i=min;i<=max;i++) {
+ String s = Integer.toString(i);
+ if (s.length() < digits) {
+ // Left-fill with 0s
+ s = prefix.substring(s.length()) + s;
+ }
+ terms.add(new BytesRef(s));
}
- terms.add(new BytesRef(s));
}
break;
@@ -937,9 +938,60 @@ public class TestAutomaton extends Lucen
a = Operations.union(a, Automata.makeEmptyString());
terms.add(new BytesRef());
break;
+
+ case 14:
+ // Safety in case we are really unlucky w/ the dice:
+ if (terms.size() <= numTerms * 10) {
+ if (VERBOSE) {
+ System.out.println(" op=concat finite automaton");
+ }
+ int count = random().nextBoolean() ? 2 : 3;
+ Set<BytesRef> addTerms = new HashSet<>();
+ while (addTerms.size() < count) {
+ addTerms.add(new BytesRef(getRandomString()));
+ }
+ if (VERBOSE) {
+ for(BytesRef term : addTerms) {
+ System.out.println(" term=" + term);
+ }
+ }
+ Automaton a2 = unionTerms(addTerms);
+ Set<BytesRef> newTerms = new HashSet<>();
+ if (random().nextBoolean()) {
+ // suffix
+ if (VERBOSE) {
+ System.out.println(" do suffix");
+ }
+ a = Operations.concatenate(a, randomNoOp(a2));
+ for(BytesRef term : terms) {
+ for(BytesRef suffix : addTerms) {
+ BytesRef newTerm = BytesRef.deepCopyOf(term);
+ newTerm.append(suffix);
+ newTerms.add(newTerm);
+ }
+ }
+ } else {
+ // prefix
+ if (VERBOSE) {
+ System.out.println(" do prefix");
+ }
+ a = Operations.concatenate(randomNoOp(a2), a);
+ for(BytesRef term : terms) {
+ for(BytesRef prefix : addTerms) {
+ BytesRef newTerm = BytesRef.deepCopyOf(prefix);
+ newTerm.append(term);
+ newTerms.add(newTerm);
+ }
+ }
+ }
+
+ terms = newTerms;
+ }
+ break;
}
- assertSame(terms, a);
+ // assertSame(terms, a);
+ assertEquals(AutomatonTestUtil.isDeterministicSlow(a), a.isDeterministic());
}
assertSame(terms, a);
Modified: lucene/dev/branches/lucene5752/lucene/test-framework/src/java/org/apache/lucene/util/TestRuleLimitSysouts.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/test-framework/src/java/org/apache/lucene/util/TestRuleLimitSysouts.java?rev=1603106&r1=1603105&r2=1603106&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/test-framework/src/java/org/apache/lucene/util/TestRuleLimitSysouts.java (original)
+++ lucene/dev/branches/lucene5752/lucene/test-framework/src/java/org/apache/lucene/util/TestRuleLimitSysouts.java Tue Jun 17 09:37:41 2014
@@ -176,9 +176,6 @@ public class TestRuleLimitSysouts extend
}
protected boolean isEnforced() {
- // nocommit
- return false;
- /*
Class<?> target = RandomizedTest.getContext().getTargetClass();
if (LuceneTestCase.VERBOSE ||
@@ -192,7 +189,6 @@ public class TestRuleLimitSysouts extend
}
return true;
- */
}
/**
Modified: lucene/dev/branches/lucene5752/lucene/test-framework/src/java/org/apache/lucene/util/automaton/AutomatonTestUtil.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/test-framework/src/java/org/apache/lucene/util/automaton/AutomatonTestUtil.java?rev=1603106&r1=1603105&r2=1603106&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/test-framework/src/java/org/apache/lucene/util/automaton/AutomatonTestUtil.java (original)
+++ lucene/dev/branches/lucene5752/lucene/test-framework/src/java/org/apache/lucene/util/automaton/AutomatonTestUtil.java Tue Jun 17 09:37:41 2014
@@ -484,7 +484,6 @@ public class AutomatonTestUtil {
assert a.getNumStates() == a2.getNumStates() : "automaton has " + (a.getNumStates() - a2.getNumStates()) + " detached states";
}
- // nocommit where to assert this...
/** Returns true if the automaton is deterministic. */
public static boolean isDeterministicSlow(Automaton a) {
Transition t = new Transition();