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 2015/07/03 18:34:44 UTC
svn commit: r1689047 - in /lucene/dev/branches/branch_5x: ./ lucene/
lucene/core/ lucene/core/src/java/org/apache/lucene/util/automaton/
lucene/suggest/
lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/
lucene/suggest/src/java/org/apa...
Author: mikemccand
Date: Fri Jul 3 16:34:43 2015
New Revision: 1689047
URL: http://svn.apache.org/r1689047
Log:
LUCENE-6365: add Operations.topoSort
Modified:
lucene/dev/branches/branch_5x/ (props changed)
lucene/dev/branches/branch_5x/lucene/ (props changed)
lucene/dev/branches/branch_5x/lucene/CHANGES.txt (contents, props changed)
lucene/dev/branches/branch_5x/lucene/core/ (props changed)
lucene/dev/branches/branch_5x/lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java
lucene/dev/branches/branch_5x/lucene/suggest/ (props changed)
lucene/dev/branches/branch_5x/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/AnalyzingSuggester.java
lucene/dev/branches/branch_5x/lucene/suggest/src/java/org/apache/lucene/search/suggest/document/CompletionTokenStream.java
Modified: lucene/dev/branches/branch_5x/lucene/CHANGES.txt
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/CHANGES.txt?rev=1689047&r1=1689046&r2=1689047&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/CHANGES.txt (original)
+++ lucene/dev/branches/branch_5x/lucene/CHANGES.txt Fri Jul 3 16:34:43 2015
@@ -81,6 +81,9 @@ New Features
attributes package that can be used for TokenStreams that solely produce
binary terms. (Uwe Schindler)
+* LUCENE-6365: Add Operations.topoSort, to run topological sort of the
+ states in an Automaton (Markus Heiden via Mike McCandless)
+
API Changes
* LUCENE-6508: Simplify Lock api, there is now just
Modified: lucene/dev/branches/branch_5x/lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java?rev=1689047&r1=1689046&r2=1689047&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java (original)
+++ lucene/dev/branches/branch_5x/lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java Fri Jul 3 16:34:43 2015
@@ -1420,4 +1420,33 @@ final public class Operations {
result.finishState();
return result;
}
+
+ /** Returns the topological sort of all states. Behavior is undefined if this
+ * automaton has cycles. CPU cost is O(numTransitions). */
+ public static int[] topoSortStates(Automaton a) {
+ int numStates = a.getNumStates();
+ int[] states = new int[numStates];
+ final BitSet visited = new BitSet(numStates);
+ final LinkedList<Integer> worklist = new LinkedList<>();
+ worklist.add(0);
+ visited.set(0);
+ int upto = 0;
+ states[upto] = 0;
+ upto++;
+ Transition t = new Transition();
+ while (worklist.size() > 0) {
+ int s = worklist.removeFirst();
+ int count = a.initTransition(s, t);
+ for (int i=0;i<count;i++) {
+ a.getNextTransition(t);
+ if (!visited.get(t.dest)) {
+ visited.set(t.dest);
+ worklist.add(t.dest);
+ states[upto++] = t.dest;
+ }
+ }
+ }
+
+ return states;
+ }
}
Modified: lucene/dev/branches/branch_5x/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/AnalyzingSuggester.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/AnalyzingSuggester.java?rev=1689047&r1=1689046&r2=1689047&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/AnalyzingSuggester.java (original)
+++ lucene/dev/branches/branch_5x/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/AnalyzingSuggester.java Fri Jul 3 16:34:43 2015
@@ -23,12 +23,10 @@ import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
-import java.util.BitSet;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
-import java.util.LinkedList;
import java.util.List;
import java.util.Set;
@@ -271,33 +269,6 @@ public class AnalyzingSuggester extends
}
}
- private int[] topoSortStates(Automaton a) {
- int numStates = a.getNumStates();
- int[] states = new int[numStates];
- final BitSet visited = new BitSet(numStates);
- final LinkedList<Integer> worklist = new LinkedList<>();
- worklist.add(0);
- visited.set(0);
- int upto = 0;
- states[upto] = 0;
- upto++;
- Transition t = new Transition();
- while (worklist.size() > 0) {
- int s = worklist.removeFirst();
- int count = a.initTransition(s, t);
- for (int i=0;i<count;i++) {
- a.getNextTransition(t);
- if (!visited.get(t.dest)) {
- visited.set(t.dest);
- worklist.add(t.dest);
- states[upto++] = t.dest;
- }
- }
- }
- return states;
- }
-
-
// Replaces SEP with epsilon or remaps them if
// we were asked to preserve them:
private Automaton replaceSep(Automaton a) {
@@ -310,7 +281,7 @@ public class AnalyzingSuggester extends
// Go in reverse topo sort so we know we only have to
// make one pass:
Transition t = new Transition();
- int[] topoSortStates = topoSortStates(a);
+ int[] topoSortStates = Operations.topoSortStates(a);
for(int i=0;i<topoSortStates.length;i++) {
int state = topoSortStates[topoSortStates.length-1-i];
int count = a.initTransition(state, t);
Modified: lucene/dev/branches/branch_5x/lucene/suggest/src/java/org/apache/lucene/search/suggest/document/CompletionTokenStream.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/suggest/src/java/org/apache/lucene/search/suggest/document/CompletionTokenStream.java?rev=1689047&r1=1689046&r2=1689047&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/suggest/src/java/org/apache/lucene/search/suggest/document/CompletionTokenStream.java (original)
+++ lucene/dev/branches/branch_5x/lucene/suggest/src/java/org/apache/lucene/search/suggest/document/CompletionTokenStream.java Fri Jul 3 16:34:43 2015
@@ -18,9 +18,7 @@ package org.apache.lucene.search.suggest
*/
import java.io.IOException;
-import java.util.BitSet;
import java.util.Iterator;
-import java.util.LinkedList;
import java.util.Set;
import org.apache.lucene.analysis.TokenStream;
@@ -245,7 +243,7 @@ public final class CompletionTokenStream
// Go in reverse topo sort so we know we only have to
// make one pass:
Transition t = new Transition();
- int[] topoSortStates = topoSortStates(a);
+ int[] topoSortStates = Operations.topoSortStates(a);
for (int i = 0; i < topoSortStates.length; i++) {
int state = topoSortStates[topoSortStates.length - 1 - i];
int count = a.initTransition(state, t);
@@ -281,32 +279,6 @@ public final class CompletionTokenStream
return result;
}
- private static int[] topoSortStates(Automaton a) {
- int numStates = a.getNumStates();
- int[] states = new int[numStates];
- final BitSet visited = new BitSet(numStates);
- final LinkedList<Integer> worklist = new LinkedList<>();
- worklist.add(0);
- visited.set(0);
- int upto = 0;
- states[upto] = 0;
- upto++;
- Transition t = new Transition();
- while (worklist.size() > 0) {
- int s = worklist.removeFirst();
- int count = a.initTransition(s, t);
- for (int i=0;i<count;i++) {
- a.getNextTransition(t);
- if (!visited.get(t.dest)) {
- visited.set(t.dest);
- worklist.add(t.dest);
- states[upto++] = t.dest;
- }
- }
- }
- return states;
- }
-
/**
* Attribute providing access to the term builder and UTF-16 conversion
*/