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 2010/05/04 01:23:58 UTC
svn commit: r940671 [2/3] - in /lucene/dev/trunk: lucene/
lucene/src/java/org/apache/lucene/search/
lucene/src/java/org/apache/lucene/util/
lucene/src/java/org/apache/lucene/util/automaton/
lucene/src/test/org/apache/lucene/search/ lucene/src/test/org/...
Modified: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/BasicOperations.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/BasicOperations.java?rev=940671&r1=940670&r2=940671&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/BasicOperations.java (original)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/BasicOperations.java Mon May 3 23:23:57 2010
@@ -29,15 +29,22 @@
package org.apache.lucene.util.automaton;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.UnicodeUtil;
+import org.apache.lucene.util.RamUsageEstimator;
+
import java.util.ArrayList;
import java.util.BitSet;
+import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
+import java.util.IdentityHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
+import java.util.Random;
/**
* Basic automata operations.
@@ -73,7 +80,8 @@ final public class BasicOperations {
s.addEpsilon(a2.initial);
}
a1.deterministic = deterministic;
- a1.clearHashCode();
+ //a1.clearHashCode();
+ a1.clearNumberedStates();
a1.checkMinimizeAlways();
return a1;
}
@@ -125,7 +133,8 @@ final public class BasicOperations {
ac = ns;
}
b.deterministic = false;
- b.clearHashCode();
+ //b.clearHashCode();
+ b.clearNumberedStates();
b.checkMinimizeAlways();
return b;
}
@@ -144,7 +153,8 @@ final public class BasicOperations {
s.accept = true;
a.initial = s;
a.deterministic = false;
- a.clearHashCode();
+ //a.clearHashCode();
+ a.clearNumberedStates();
a.checkMinimizeAlways();
return a;
}
@@ -165,7 +175,8 @@ final public class BasicOperations {
p.addEpsilon(s);
a.initial = s;
a.deterministic = false;
- a.clearHashCode();
+ //a.clearHashCode();
+ a.clearNumberedStates();
a.checkMinimizeAlways();
return a;
}
@@ -217,7 +228,8 @@ final public class BasicOperations {
for (State p : b.getAcceptStates())
p.addEpsilon(d.initial);
b.deterministic = false;
- b.clearHashCode();
+ //b.clearHashCode();
+ b.clearNumberedStates();
b.checkMinimizeAlways();
}
return b;
@@ -233,7 +245,7 @@ final public class BasicOperations {
a = a.cloneExpandedIfRequired();
a.determinize();
a.totalize();
- for (State p : a.getStates())
+ for (State p : a.getNumberedStates())
p.accept = !p.accept;
a.removeDeadTransitions();
return a;
@@ -274,10 +286,8 @@ final public class BasicOperations {
else return BasicAutomata.makeEmpty();
}
if (a1 == a2) return a1.cloneIfRequired();
- Transition[][] transitions1 = Automaton
- .getSortedTransitions(a1.getStates());
- Transition[][] transitions2 = Automaton
- .getSortedTransitions(a2.getStates());
+ Transition[][] transitions1 = a1.getSortedTransitions();
+ Transition[][] transitions2 = a2.getSortedTransitions();
Automaton c = new Automaton();
LinkedList<StatePair> worklist = new LinkedList<StatePair>();
HashMap<StatePair,StatePair> newstates = new HashMap<StatePair,StatePair>();
@@ -302,9 +312,9 @@ final public class BasicOperations {
newstates.put(q, q);
r = q;
}
- char min = t1[n1].min > t2[n2].min ? t1[n1].min : t2[n2].min;
- char max = t1[n1].max < t2[n2].max ? t1[n1].max : t2[n2].max;
- p.s.transitions.add(new Transition(min, max, r.s));
+ int min = t1[n1].min > t2[n2].min ? t1[n1].min : t2[n2].min;
+ int max = t1[n1].max < t2[n2].max ? t1[n1].max : t2[n2].max;
+ p.s.addTransition(new Transition(min, max, r.s));
}
}
}
@@ -313,6 +323,24 @@ final public class BasicOperations {
c.checkMinimizeAlways();
return c;
}
+
+ /** Returns true if these two auotomata accept exactly the
+ * same language. This is a costly computation! Note
+ * also that a1 and a2 will be determinized as a side
+ * effect. */
+ public static boolean sameLanguage(Automaton a1, Automaton a2) {
+ if (a1 == a2) {
+ return true;
+ }
+ if (a1.isSingleton() && a2.isSingleton()) {
+ return a1.singleton.equals(a2.singleton);
+ } else if (a1.isSingleton()) {
+ // subsetOf is faster if the first automaton is a singleton
+ return subsetOf(a1, a2) && subsetOf(a2, a1);
+ } else {
+ return subsetOf(a2, a1) && subsetOf(a1, a2);
+ }
+ }
/**
* Returns true if the language of <code>a1</code> is a subset of the language
@@ -328,10 +356,8 @@ final public class BasicOperations {
return BasicOperations.run(a2, a1.singleton);
}
a2.determinize();
- Transition[][] transitions1 = Automaton
- .getSortedTransitions(a1.getStates());
- Transition[][] transitions2 = Automaton
- .getSortedTransitions(a2.getStates());
+ Transition[][] transitions1 = a1.getSortedTransitions();
+ Transition[][] transitions2 = a2.getSortedTransitions();
LinkedList<StatePair> worklist = new LinkedList<StatePair>();
HashSet<StatePair> visited = new HashSet<StatePair>();
StatePair p = new StatePair(a1.initial, a2.initial);
@@ -339,19 +365,24 @@ final public class BasicOperations {
visited.add(p);
while (worklist.size() > 0) {
p = worklist.removeFirst();
- if (p.s1.accept && !p.s2.accept) return false;
+ if (p.s1.accept && !p.s2.accept) {
+ return false;
+ }
Transition[] t1 = transitions1[p.s1.number];
Transition[] t2 = transitions2[p.s2.number];
for (int n1 = 0, b2 = 0; n1 < t1.length; n1++) {
while (b2 < t2.length && t2[b2].max < t1[n1].min)
b2++;
int min1 = t1[n1].min, max1 = t1[n1].max;
+
for (int n2 = b2; n2 < t2.length && t1[n1].max >= t2[n2].min; n2++) {
- if (t2[n2].min > min1) return false;
- if (t2[n2].max < Character.MAX_VALUE) min1 = t2[n2].max + 1;
+ if (t2[n2].min > min1) {
+ return false;
+ }
+ if (t2[n2].max < Character.MAX_CODE_POINT) min1 = t2[n2].max + 1;
else {
- min1 = Character.MAX_VALUE;
- max1 = Character.MIN_VALUE;
+ min1 = Character.MAX_CODE_POINT;
+ max1 = Character.MIN_CODE_POINT;
}
StatePair q = new StatePair(t1[n1].to, t2[n2].to);
if (!visited.contains(q)) {
@@ -359,7 +390,9 @@ final public class BasicOperations {
visited.add(q);
}
}
- if (min1 <= max1) return false;
+ if (min1 <= max1) {
+ return false;
+ }
}
}
return true;
@@ -387,7 +420,8 @@ final public class BasicOperations {
s.addEpsilon(a2.initial);
a1.initial = s;
a1.deterministic = false;
- a1.clearHashCode();
+ //a1.clearHashCode();
+ a1.clearNumberedStates();
a1.checkMinimizeAlways();
return a1;
}
@@ -414,64 +448,257 @@ final public class BasicOperations {
Automaton a = new Automaton();
a.initial = s;
a.deterministic = false;
- a.clearHashCode();
+ //a.clearHashCode();
+ a.clearNumberedStates();
a.checkMinimizeAlways();
return a;
}
-
+
+ // Simple custom ArrayList<Transition>
+ private final static class TransitionList {
+ Transition[] transitions = new Transition[2];
+ int count;
+
+ public void add(Transition t) {
+ if (transitions.length == count) {
+ Transition[] newArray = new Transition[ArrayUtil.oversize(1+count, RamUsageEstimator.NUM_BYTES_OBJ_REF)];
+ System.arraycopy(transitions, 0, newArray, 0, count);
+ transitions = newArray;
+ }
+ transitions[count++] = t;
+ }
+ }
+
+ // Holds all transitions that start on this int point, or
+ // end at this point-1
+ private final static class PointTransitions implements Comparable<PointTransitions> {
+ int point;
+ final TransitionList ends = new TransitionList();
+ final TransitionList starts = new TransitionList();
+ public int compareTo(PointTransitions other) {
+ return point - other.point;
+ }
+
+ public void reset(int point) {
+ this.point = point;
+ ends.count = 0;
+ starts.count = 0;
+ }
+
+ public boolean equals(Object other) {
+ return ((PointTransitions) other).point == point;
+ }
+
+ public int hashCode() {
+ return point;
+ }
+ }
+
+ private final static class PointTransitionSet {
+ int count;
+ PointTransitions[] points = new PointTransitions[5];
+
+ private final static int HASHMAP_CUTOVER = 30;
+ private final HashMap<Integer,PointTransitions> map = new HashMap<Integer,PointTransitions>();
+ private boolean useHash = false;
+
+ private PointTransitions next(int point) {
+ // 1st time we are seeing this point
+ if (count == points.length) {
+ final PointTransitions[] newArray = new PointTransitions[ArrayUtil.oversize(1+count, RamUsageEstimator.NUM_BYTES_OBJ_REF)];
+ System.arraycopy(points, 0, newArray, 0, count);
+ points = newArray;
+ }
+ PointTransitions points0 = points[count];
+ if (points0 == null) {
+ points0 = points[count] = new PointTransitions();
+ }
+ points0.reset(point);
+ count++;
+ return points0;
+ }
+
+ private PointTransitions find(int point) {
+ if (useHash) {
+ final Integer pi = point;
+ PointTransitions p = map.get(pi);
+ if (p == null) {
+ p = next(point);
+ map.put(pi, p);
+ }
+ return p;
+ } else {
+ for(int i=0;i<count;i++) {
+ if (points[i].point == point) {
+ return points[i];
+ }
+ }
+
+ final PointTransitions p = next(point);
+ if (count == HASHMAP_CUTOVER) {
+ // switch to HashMap on the fly
+ assert map.size() == 0;
+ for(int i=0;i<count;i++) {
+ map.put(points[i].point, points[i]);
+ }
+ useHash = true;
+ }
+ return p;
+ }
+ }
+
+ public void reset() {
+ if (useHash) {
+ map.clear();
+ useHash = false;
+ }
+ count = 0;
+ }
+
+ public void sort() {
+ if (count > 1) {
+ Arrays.sort(points, 0, count);
+ }
+ }
+
+ public void add(Transition t) {
+ find(t.min).starts.add(t);
+ find(1+t.max).ends.add(t);
+ }
+
+ public String toString() {
+ StringBuilder s = new StringBuilder();
+ for(int i=0;i<count;i++) {
+ if (i > 0) {
+ s.append(' ');
+ }
+ s.append(points[i].point).append(':').append(points[i].starts.count).append(',').append(points[i].ends.count);
+ }
+ return s.toString();
+ }
+ }
+
/**
* Determinizes the given automaton.
* <p>
- * Complexity: exponential in number of states.
+ * Worst case complexity: exponential in number of states.
*/
- public static void determinize(Automaton a) {
- if (a.deterministic || a.isSingleton()) return;
- Set<State> initialset = new HashSet<State>();
- initialset.add(a.initial);
- determinize(a, initialset);
- }
-
- /**
- * Determinizes the given automaton using the given set of initial states.
- */
- static void determinize(Automaton a, Set<State> initialset) {
- char[] points = a.getStartPoints();
+ static void determinize(Automaton a) {
+ if (a.deterministic || a.isSingleton()) {
+ return;
+ }
+
+ final State[] allStates = a.getNumberedStates();
+
// subset construction
- Map<Set<State>,Set<State>> sets = new HashMap<Set<State>,Set<State>>();
- LinkedList<Set<State>> worklist = new LinkedList<Set<State>>();
- Map<Set<State>,State> newstate = new HashMap<Set<State>,State>();
- sets.put(initialset, initialset);
- worklist.add(initialset);
+ final boolean initAccept = a.initial.accept;
+ final int initNumber = a.initial.number;
a.initial = new State();
+ SortedIntSet.FrozenIntSet initialset = new SortedIntSet.FrozenIntSet(initNumber, a.initial);
+
+ LinkedList<SortedIntSet.FrozenIntSet> worklist = new LinkedList<SortedIntSet.FrozenIntSet>();
+ Map<SortedIntSet.FrozenIntSet,State> newstate = new HashMap<SortedIntSet.FrozenIntSet,State>();
+
+ worklist.add(initialset);
+
+ a.initial.accept = initAccept;
newstate.put(initialset, a.initial);
+
+ int newStateUpto = 0;
+ State[] newStatesArray = new State[5];
+ newStatesArray[newStateUpto] = a.initial;
+ a.initial.number = newStateUpto;
+ newStateUpto++;
+
+ // like Set<Integer,PointTransitions>
+ final PointTransitionSet points = new PointTransitionSet();
+
+ // like SortedMap<Integer,Integer>
+ final SortedIntSet statesSet = new SortedIntSet(5);
+
while (worklist.size() > 0) {
- Set<State> s = worklist.removeFirst();
- State r = newstate.get(s);
- for (State q : s)
- if (q.accept) {
- r.accept = true;
- break;
- }
- for (int n = 0; n < points.length; n++) {
- Set<State> p = new HashSet<State>();
- for (State q : s)
- for (Transition t : q.transitions)
- if (t.min <= points[n] && points[n] <= t.max) p.add(t.to);
- if (!sets.containsKey(p)) {
- sets.put(p, p);
- worklist.add(p);
- newstate.put(p, new State());
- }
- State q = newstate.get(p);
- char min = points[n];
- char max;
- if (n + 1 < points.length) max = (char) (points[n + 1] - 1);
- else max = Character.MAX_VALUE;
- r.transitions.add(new Transition(min, max, q));
+ SortedIntSet.FrozenIntSet s = worklist.removeFirst();
+
+ // Collate all outgoing transitions by min/1+max:
+ for(int i=0;i<s.values.length;i++) {
+ final State s0 = allStates[s.values[i]];
+ for(int j=0;j<s0.numTransitions;j++) {
+ points.add(s0.transitionsArray[j]);
+ }
+ }
+
+ if (points.count == 0) {
+ // No outgoing transitions -- skip it
+ continue;
+ }
+
+ points.sort();
+
+ int lastPoint = -1;
+ int accCount = 0;
+
+ final State r = s.state;
+ for(int i=0;i<points.count;i++) {
+
+ final int point = points.points[i].point;
+
+ if (statesSet.upto > 0) {
+ assert lastPoint != -1;
+
+ statesSet.computeHash();
+
+ State q = newstate.get(statesSet);
+ if (q == null) {
+ q = new State();
+ final SortedIntSet.FrozenIntSet p = statesSet.freeze(q);
+ worklist.add(p);
+ if (newStateUpto == newStatesArray.length) {
+ final State[] newArray = new State[ArrayUtil.oversize(1+newStateUpto, RamUsageEstimator.NUM_BYTES_OBJ_REF)];
+ System.arraycopy(newStatesArray, 0, newArray, 0, newStateUpto);
+ newStatesArray = newArray;
+ }
+ newStatesArray[newStateUpto] = q;
+ q.number = newStateUpto;
+ newStateUpto++;
+ q.accept = accCount > 0;
+ newstate.put(p, q);
+ } else {
+ assert (accCount > 0 ? true:false) == q.accept: "accCount=" + accCount + " vs existing accept=" + q.accept + " states=" + statesSet;
+ }
+
+ r.addTransition(new Transition(lastPoint, point-1, q));
+ }
+
+ // process transitions that end on this point
+ // (closes an overlapping interval)
+ Transition[] transitions = points.points[i].ends.transitions;
+ int limit = points.points[i].ends.count;
+ for(int j=0;j<limit;j++) {
+ final Transition t = transitions[j];
+ final Integer num = t.to.number;
+ statesSet.decr(num);
+ accCount -= t.to.accept ? 1:0;
+ }
+ points.points[i].ends.count = 0;
+
+ // process transitions that start on this point
+ // (opens a new interval)
+ transitions = points.points[i].starts.transitions;
+ limit = points.points[i].starts.count;
+ for(int j=0;j<limit;j++) {
+ final Transition t = transitions[j];
+ final Integer num = t.to.number;
+ statesSet.incr(num);
+ accCount += t.to.accept ? 1:0;
+ }
+ lastPoint = point;
+ points.points[i].starts.count = 0;
}
+ points.reset();
+ assert statesSet.upto == 0: "upto=" + statesSet.upto;
}
a.deterministic = true;
- a.removeDeadTransitions();
+ a.setNumberedStates(newStatesArray, newStateUpto);
}
/**
@@ -535,7 +762,8 @@ final public class BasicOperations {
for (StatePair p : pairs)
p.s1.addEpsilon(p.s2);
a.deterministic = false;
- a.clearHashCode();
+ //a.clearHashCode();
+ a.clearNumberedStates();
a.checkMinimizeAlways();
}
@@ -545,7 +773,7 @@ final public class BasicOperations {
*/
public static boolean isEmptyString(Automaton a) {
if (a.isSingleton()) return a.singleton.length() == 0;
- else return a.initial.accept && a.initial.transitions.isEmpty();
+ else return a.initial.accept && a.initial.numTransitions() == 0;
}
/**
@@ -553,7 +781,7 @@ final public class BasicOperations {
*/
public static boolean isEmpty(Automaton a) {
if (a.isSingleton()) return false;
- return !a.initial.accept && a.initial.transitions.isEmpty();
+ return !a.initial.accept && a.initial.numTransitions() == 0;
}
/**
@@ -561,10 +789,10 @@ final public class BasicOperations {
*/
public static boolean isTotal(Automaton a) {
if (a.isSingleton()) return false;
- if (a.initial.accept && a.initial.transitions.size() == 1) {
- Transition t = a.initial.transitions.iterator().next();
- return t.to == a.initial && t.min == Character.MIN_VALUE
- && t.max == Character.MAX_VALUE;
+ if (a.initial.accept && a.initial.numTransitions() == 1) {
+ Transition t = a.initial.getTransitions().iterator().next();
+ return t.to == a.initial && t.min == Character.MIN_CODE_POINT
+ && t.max == Character.MAX_CODE_POINT;
}
return false;
}
@@ -580,24 +808,23 @@ final public class BasicOperations {
if (a.isSingleton()) return s.equals(a.singleton);
if (a.deterministic) {
State p = a.initial;
- for (int i = 0; i < s.length(); i++) {
- State q = p.step(s.charAt(i));
+ for (int i = 0, cp = 0; i < s.length(); i += Character.charCount(cp)) {
+ State q = p.step(cp = s.codePointAt(i));
if (q == null) return false;
p = q;
}
return p.accept;
} else {
- Set<State> states = a.getStates();
- Automaton.setStateNumbers(states);
+ State[] states = a.getNumberedStates();
LinkedList<State> pp = new LinkedList<State>();
LinkedList<State> pp_other = new LinkedList<State>();
- BitSet bb = new BitSet(states.size());
- BitSet bb_other = new BitSet(states.size());
+ BitSet bb = new BitSet(states.length);
+ BitSet bb_other = new BitSet(states.length);
pp.add(a.initial);
ArrayList<State> dest = new ArrayList<State>();
boolean accept = a.initial.accept;
- for (int i = 0; i < s.length(); i++) {
- char c = s.charAt(i);
+ for (int i = 0, c = 0; i < s.length(); i += Character.charCount(c)) {
+ c = s.codePointAt(i);
accept = false;
pp_other.clear();
bb_other.clear();
@@ -622,4 +849,149 @@ final public class BasicOperations {
return accept;
}
}
+
+ // picks a random int code point that this transition
+ // accepts, avoiding the surrogates range since they are
+ // "defined" in UTF32. Don't call this on a transition
+ // that only accepts UTF16 surrogate values!!
+ private static int getRandomCodePoint(final Random r, final Transition t) {
+ while(true) {
+ final int v = t.min+r.nextInt(t.max-t.min+1);
+ if (v < UnicodeUtil.UNI_SUR_HIGH_START ||
+ v > UnicodeUtil.UNI_SUR_LOW_END) {
+ return v;
+ }
+ }
+ }
+
+ public static class RandomAcceptedStrings {
+
+ private final Map<Transition,Boolean> leadsToAccept;
+ private final Automaton a;
+
+ private static class ArrivingTransition {
+ final State from;
+ final Transition t;
+ public ArrivingTransition(State from, Transition t) {
+ this.from = from;
+ this.t = t;
+ }
+ }
+
+ public RandomAcceptedStrings(Automaton a) {
+ this.a = a;
+ if (a.isSingleton()) {
+ leadsToAccept = null;
+ return;
+ }
+
+ // must use IdentityHashmap because two Transitions w/
+ // different start nodes can be considered the same
+ leadsToAccept = new IdentityHashMap<Transition,Boolean>();
+ final Map<State,List<ArrivingTransition>> allArriving = new HashMap<State,List<ArrivingTransition>>();
+
+ final LinkedList<State> q = new LinkedList<State>();
+ final Set<State> seen = new HashSet<State>();
+
+ // reverse map the transitions, so we can quickly look
+ // up all arriving transitions to a given state
+ for(State s: a.getNumberedStates()) {
+ for(int i=0;i<s.numTransitions;i++) {
+ final Transition t = s.transitionsArray[i];
+ List<ArrivingTransition> tl = allArriving.get(t.to);
+ if (tl == null) {
+ tl = new ArrayList<ArrivingTransition>();
+ allArriving.put(t.to, tl);
+ }
+ tl.add(new ArrivingTransition(s, t));
+ }
+ if (s.accept) {
+ q.add(s);
+ seen.add(s);
+ }
+ }
+
+ // Breadth-first search, from accept states,
+ // backwards:
+ while(!q.isEmpty()) {
+ final State s = q.pop();
+ List<ArrivingTransition> arriving = allArriving.get(s);
+ if (arriving != null) {
+ for(ArrivingTransition at : arriving) {
+ final State from = at.from;
+ if (!seen.contains(from)) {
+ q.add(from);
+ seen.add(from);
+ leadsToAccept.put(at.t, Boolean.TRUE);
+ }
+ }
+ }
+ }
+ }
+
+ public int[] getRandomAcceptedString(Random r) {
+
+ final List<Integer> soFar = new ArrayList<Integer>();
+ if (a.isSingleton()) {
+ // accepts only one
+ final String s = a.singleton;
+
+ int charUpto = 0;
+ while(charUpto < s.length()) {
+ final int cp = s.codePointAt(charUpto);
+ charUpto += Character.charCount(cp);
+ soFar.add(cp);
+ }
+ } else {
+
+ State s = a.initial;
+
+ while(true) {
+
+ if (s.accept) {
+ if (s.numTransitions == 0) {
+ // stop now
+ break;
+ } else {
+ if (r.nextBoolean()) {
+ break;
+ }
+ }
+ }
+
+ if (s.numTransitions == 0) {
+ throw new RuntimeException("this automaton has dead states");
+ }
+
+ boolean cheat = r.nextBoolean();
+
+ final Transition t;
+ if (cheat) {
+ // pick a transition that we know is the fastest
+ // path to an accept state
+ List<Transition> toAccept = new ArrayList<Transition>();
+ for(int i=0;i<s.numTransitions;i++) {
+ final Transition t0 = s.transitionsArray[i];
+ if (leadsToAccept.containsKey(t0)) {
+ toAccept.add(t0);
+ }
+ }
+ if (toAccept.size() == 0) {
+ // this is OK -- it means we jumped into a cycle
+ t = s.transitionsArray[r.nextInt(s.numTransitions)];
+ } else {
+ t = toAccept.get(r.nextInt(toAccept.size()));
+ }
+ } else {
+ t = s.transitionsArray[r.nextInt(s.numTransitions)];
+ }
+
+ soFar.add(getRandomCodePoint(r, t));
+ s = t.to;
+ }
+ }
+
+ return ArrayUtil.toIntArray(soFar);
+ }
+ }
}
Added: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/ByteRunAutomaton.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/ByteRunAutomaton.java?rev=940671&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/ByteRunAutomaton.java (added)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/ByteRunAutomaton.java Mon May 3 23:23:57 2010
@@ -0,0 +1,38 @@
+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.
+ */
+
+public class ByteRunAutomaton extends RunAutomaton {
+
+ public ByteRunAutomaton(Automaton a) {
+ super(new UTF32ToUTF8().convert(a), 256, true);
+ }
+
+ /**
+ * Returns true if the given byte array is accepted by this automaton
+ */
+ public boolean run(byte[] s, int offset, int length) {
+ int p = initial;
+ int l = offset + length;
+ for (int i = offset; i < l; i++) {
+ p = step(p, s[i] & 0xFF);
+ if (p == -1) return false;
+ }
+ return accept[p];
+ }
+}
Propchange: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/ByteRunAutomaton.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/CharacterRunAutomaton.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/CharacterRunAutomaton.java?rev=940671&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/CharacterRunAutomaton.java (added)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/CharacterRunAutomaton.java Mon May 3 23:23:57 2010
@@ -0,0 +1,51 @@
+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.
+ */
+
+public class CharacterRunAutomaton extends RunAutomaton {
+
+ public CharacterRunAutomaton(Automaton a) {
+ super(a, Character.MAX_CODE_POINT, false);
+ }
+
+ /**
+ * Returns true if the given string is accepted by this automaton.
+ */
+ public boolean run(String s) {
+ int p = initial;
+ int l = s.length();
+ for (int i = 0, cp = 0; i < l; i += Character.charCount(cp)) {
+ p = step(p, cp = s.codePointAt(i));
+ if (p == -1) return false;
+ }
+ return accept[p];
+ }
+
+ /**
+ * Returns true if the given string is accepted by this automaton
+ */
+ public boolean run(char[] s, int offset, int length) {
+ int p = initial;
+ int l = offset + length;
+ for (int i = offset, cp = 0; i < l; i += Character.charCount(cp)) {
+ p = step(p, cp = Character.codePointAt(s, i, l));
+ if (p == -1) return false;
+ }
+ return accept[p];
+ }
+}
Propchange: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/CharacterRunAutomaton.java
------------------------------------------------------------------------------
svn:eol-style = native
Modified: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/LevenshteinAutomata.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/LevenshteinAutomata.java?rev=940671&r1=940670&r2=940671&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/LevenshteinAutomata.java (original)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/LevenshteinAutomata.java Mon May 3 23:23:57 2010
@@ -21,11 +21,6 @@ import java.util.Iterator;
import java.util.SortedSet;
import java.util.TreeSet;
-import org.apache.lucene.util.automaton.Automaton;
-import org.apache.lucene.util.automaton.BasicAutomata;
-import org.apache.lucene.util.automaton.State;
-import org.apache.lucene.util.automaton.Transition;
-
/**
* Class to construct DFAs that match a word within some edit distance.
* <p>
@@ -39,13 +34,13 @@ public class LevenshteinAutomata {
public static final int MAXIMUM_SUPPORTED_DISTANCE = 2;
/* input word */
final String input;
- final char word[];
+ final int word[];
/* the automata alphabet. */
- final char alphabet[];
+ final int alphabet[];
/* the unicode ranges outside of alphabet */
- final char rangeLower[];
- final char rangeUpper[];
+ final int rangeLower[];
+ final int rangeUpper[];
int numRanges = 0;
ParametricDescription descriptions[];
@@ -55,42 +50,46 @@ public class LevenshteinAutomata {
*/
public LevenshteinAutomata(String input) {
this.input = input;
- this.word = input.toCharArray();
+ int length = Character.codePointCount(input, 0, input.length());
+ word = new int[length];
+ for (int i = 0, j = 0, cp = 0; i < input.length(); i += Character.charCount(cp)) {
+ word[j++] = cp = input.codePointAt(i);
+ }
// calculate the alphabet
- SortedSet<Character> set = new TreeSet<Character>();
+ SortedSet<Integer> set = new TreeSet<Integer>();
for (int i = 0; i < word.length; i++)
set.add(word[i]);
- alphabet = new char[set.size()];
- Iterator<Character> iterator = set.iterator();
+ alphabet = new int[set.size()];
+ Iterator<Integer> iterator = set.iterator();
for (int i = 0; i < alphabet.length; i++)
alphabet[i] = iterator.next();
- rangeLower = new char[alphabet.length + 2];
- rangeUpper = new char[alphabet.length + 2];
+ rangeLower = new int[alphabet.length + 2];
+ rangeUpper = new int[alphabet.length + 2];
// calculate the unicode range intervals that exclude the alphabet
// these are the ranges for all unicode characters not in the alphabet
int lower = 0;
for (int i = 0; i < alphabet.length; i++) {
- char higher = alphabet[i];
+ int higher = alphabet[i];
if (higher > lower) {
- rangeLower[numRanges] = (char) lower;
- rangeUpper[numRanges] = (char) (higher - 1);
+ rangeLower[numRanges] = lower;
+ rangeUpper[numRanges] = higher - 1;
numRanges++;
}
lower = higher + 1;
}
/* add the final endpoint */
- if (lower <= 0xFFFF) {
- rangeLower[numRanges] = (char) lower;
- rangeUpper[numRanges] = '\uFFFF';
+ if (lower <= Character.MAX_CODE_POINT) {
+ rangeLower[numRanges] = lower;
+ rangeUpper[numRanges] = Character.MAX_CODE_POINT;
numRanges++;
}
descriptions = new ParametricDescription[] {
null, /* for n=0, we do not need to go through the trouble */
- new Lev1ParametricDescription(input.length()),
- new Lev2ParametricDescription(input.length()),
+ new Lev1ParametricDescription(word.length),
+ new Lev2ParametricDescription(word.length),
};
}
@@ -119,6 +118,7 @@ public class LevenshteinAutomata {
// create all states, and mark as accept states if appropriate
for (int i = 0; i < states.length; i++) {
states[i] = new State();
+ states[i].number = i;
states[i].setAccept(description.isAccept(i));
}
// create transitions from state to state
@@ -129,7 +129,7 @@ public class LevenshteinAutomata {
final int end = xpos + Math.min(word.length - xpos, range);
for (int x = 0; x < alphabet.length; x++) {
- final char ch = alphabet[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);
@@ -143,13 +143,15 @@ public class LevenshteinAutomata {
if (dest >= 0)
for (int r = 0; r < numRanges; r++)
states[k].addTransition(new Transition(rangeLower[r], rangeUpper[r], states[dest]));
+ // reduce the state: this doesn't appear to help anything
+ //states[k].reduce();
}
- Automaton a = new Automaton();
- a.setInitialState(states[0]);
+ Automaton a = new Automaton(states[0]);
a.setDeterministic(true);
+ a.setNumberedStates(states);
// we need not trim transitions to dead states, as they are not created.
- // a.restoreInvariant();
+ //a.restoreInvariant();
return a;
}
@@ -157,7 +159,7 @@ public class LevenshteinAutomata {
* Get the characteristic vector <code>X(x, V)</code>
* where V is <code>substring(pos, end)</code>
*/
- int getVector(char x, int pos, int end) {
+ int getVector(int x, int pos, int end) {
int vector = 0;
for (int i = pos; i < end; i++) {
vector <<= 1;
Modified: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/MinimizationOperations.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/MinimizationOperations.java?rev=940671&r1=940670&r2=940671&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/MinimizationOperations.java (original)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/MinimizationOperations.java Mon May 3 23:23:57 2010
@@ -31,7 +31,6 @@ package org.apache.lucene.util.automaton
import java.util.ArrayList;
import java.util.LinkedList;
-import java.util.Set;
/**
* Operations for minimizing automata.
@@ -41,7 +40,7 @@ import java.util.Set;
final public class MinimizationOperations {
private MinimizationOperations() {}
-
+
/**
* Minimizes (and determinizes if not already deterministic) the given
* automaton.
@@ -53,8 +52,8 @@ final public class MinimizationOperation
minimizeHopcroft(a);
}
// recompute hash code
- a.hash_code = a.getNumberOfStates() * 3 + a.getNumberOfTransitions() * 2;
- if (a.hash_code == 0) a.hash_code = 1;
+ //a.hash_code = 1a.getNumberOfStates() * 3 + a.getNumberOfTransitions() * 2;
+ //if (a.hash_code == 0) a.hash_code = 1;
}
private static <T> void initialize(ArrayList<T> list, int size) {
@@ -67,24 +66,18 @@ final public class MinimizationOperation
*/
public static void minimizeHopcroft(Automaton a) {
a.determinize();
- Set<Transition> tr = a.initial.getTransitions();
- if (tr.size() == 1) {
- Transition t = tr.iterator().next();
- if (t.to == a.initial && t.min == Character.MIN_VALUE
- && t.max == Character.MAX_VALUE) return;
+ if (a.initial.numTransitions == 1) {
+ Transition t = a.initial.transitionsArray[0];
+ if (t.to == a.initial && t.min == Character.MIN_CODE_POINT
+ && t.max == Character.MAX_CODE_POINT) return;
}
a.totalize();
- // make arrays for numbered states and effective alphabet
- Set<State> ss = a.getStates();
- State[] states = new State[ss.size()];
- int number = 0;
- for (State q : ss) {
- states[number] = q;
- q.number = number++;
- }
- char[] sigma = a.getStartPoints();
+
+ int[] sigma = a.getStartPoints();
// initialize data structures
ArrayList<ArrayList<LinkedList<State>>> reverse = new ArrayList<ArrayList<LinkedList<State>>>();
+ final State[] states = a.getNumberedStates();
+
for (int q = 0; q < states.length; q++) {
ArrayList<LinkedList<State>> v = new ArrayList<LinkedList<State>>();
initialize(v, sigma.length);
@@ -121,7 +114,7 @@ final public class MinimizationOperation
partition.get(j).add(qq);
block[qq.number] = j;
for (int x = 0; x < sigma.length; x++) {
- char y = sigma[x];
+ int y = sigma[x];
State p = qq.step(y);
reverse.get(p.number).get(x).add(qq);
reverse_nonempty[p.number][x] = true;
@@ -218,9 +211,10 @@ final public class MinimizationOperation
for (int n = 0; n < newstates.length; n++) {
State s = newstates[n];
s.accept = states[s.number].accept;
- for (Transition t : states[s.number].transitions)
- s.transitions.add(new Transition(t.min, t.max, newstates[t.to.number]));
+ for (Transition t : states[s.number].getTransitions())
+ s.addTransition(new Transition(t.min, t.max, newstates[t.to.number]));
}
+ a.clearNumberedStates();
a.removeDeadTransitions();
}
Modified: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/RegExp.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/RegExp.java?rev=940671&r1=940670&r2=940671&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/RegExp.java (original)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/RegExp.java Mon May 3 23:23:57 2010
@@ -366,9 +366,9 @@ public class RegExp {
Kind kind;
RegExp exp1, exp2;
String s;
- char c;
+ int c;
int min, max, digits;
- char from, to;
+ int from, to;
String b;
int flags;
@@ -625,10 +625,10 @@ public class RegExp {
b.append(")");
break;
case REGEXP_CHAR:
- b.append("\\").append(c);
+ b.append("\\").appendCodePoint(c);
break;
case REGEXP_CHAR_RANGE:
- b.append("[\\").append(from).append("-\\").append(to).append("]");
+ b.append("[\\").appendCodePoint(from).append("-\\").appendCodePoint(to).append("]");
break;
case REGEXP_ANYCHAR:
b.append(".");
@@ -725,9 +725,9 @@ public class RegExp {
static private RegExp makeString(RegExp exp1, RegExp exp2) {
StringBuilder b = new StringBuilder();
if (exp1.kind == Kind.REGEXP_STRING) b.append(exp1.s);
- else b.append(exp1.c);
+ else b.appendCodePoint(exp1.c);
if (exp2.kind == Kind.REGEXP_STRING) b.append(exp2.s);
- else b.append(exp2.c);
+ else b.appendCodePoint(exp2.c);
return makeString(b.toString());
}
@@ -777,14 +777,14 @@ public class RegExp {
return r;
}
- static RegExp makeChar(char c) {
+ static RegExp makeChar(int c) {
RegExp r = new RegExp();
r.kind = Kind.REGEXP_CHAR;
r.c = c;
return r;
}
- static RegExp makeCharRange(char from, char to) {
+ static RegExp makeCharRange(int from, int to) {
RegExp r = new RegExp();
r.kind = Kind.REGEXP_CHAR_RANGE;
r.from = from;
@@ -834,13 +834,13 @@ public class RegExp {
}
private boolean peek(String s) {
- return more() && s.indexOf(b.charAt(pos)) != -1;
+ return more() && s.indexOf(b.codePointAt(pos)) != -1;
}
- private boolean match(char c) {
+ private boolean match(int c) {
if (pos >= b.length()) return false;
- if (b.charAt(pos) == c) {
- pos++;
+ if (b.codePointAt(pos) == c) {
+ pos += Character.charCount(c);
return true;
}
return false;
@@ -850,9 +850,11 @@ public class RegExp {
return pos < b.length();
}
- private char next() throws IllegalArgumentException {
+ private int next() throws IllegalArgumentException {
if (!more()) throw new IllegalArgumentException("unexpected end-of-string");
- return b.charAt(pos++);
+ int ch = b.codePointAt(pos);
+ pos += Character.charCount(ch);
+ return ch;
}
private boolean check(int flag) {
@@ -933,7 +935,7 @@ public class RegExp {
}
final RegExp parseCharClass() throws IllegalArgumentException {
- char c = parseCharExp();
+ int c = parseCharExp();
if (match('-')) return makeCharRange(c, parseCharExp());
else return makeChar(c);
}
@@ -993,7 +995,7 @@ public class RegExp {
} else return makeChar(parseCharExp());
}
- final char parseCharExp() throws IllegalArgumentException {
+ final int parseCharExp() throws IllegalArgumentException {
match('\\');
return next();
}
Modified: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/RunAutomaton.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/RunAutomaton.java?rev=940671&r1=940670&r2=940671&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/RunAutomaton.java (original)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/RunAutomaton.java Mon May 3 23:23:57 2010
@@ -30,22 +30,22 @@
package org.apache.lucene.util.automaton;
import java.io.Serializable;
-import java.util.Set;
/**
* Finite-state automaton with fast run operation.
*
* @lucene.experimental
*/
-public final class RunAutomaton implements Serializable {
-
+public abstract class RunAutomaton implements Serializable {
+ final int maxInterval;
final int size;
final boolean[] accept;
final int initial;
final int[] transitions; // delta(state,c) = transitions[state*points.length +
// getCharClass(c)]
- final char[] points; // char interval start points
+ final int[] points; // char interval start points
final int[] classmap; // map from char number to class class
+ final Automaton automaton;
/**
* Returns a string representation of this automaton.
@@ -61,10 +61,10 @@ public final class RunAutomaton implemen
for (int j = 0; j < points.length; j++) {
int k = transitions[i * points.length + j];
if (k != -1) {
- char min = points[j];
- char max;
- if (j + 1 < points.length) max = (char) (points[j + 1] - 1);
- else max = Character.MAX_VALUE;
+ int min = points[j];
+ int max;
+ if (j + 1 < points.length) max = (points[j + 1] - 1);
+ else max = maxInterval;
b.append(" ");
Transition.appendCharString(min, b);
if (min != max) {
@@ -81,52 +81,59 @@ public final class RunAutomaton implemen
/**
* Returns number of states in automaton.
*/
- public int getSize() {
+ public final int getSize() {
return size;
}
/**
* Returns acceptance status for given state.
*/
- public boolean isAccept(int state) {
+ public final boolean isAccept(int state) {
return accept[state];
}
/**
* Returns initial state.
*/
- public int getInitialState() {
+ public final int getInitialState() {
return initial;
}
/**
- * Returns array of character class interval start points. The array should
+ * Returns array of codepoint class interval start points. The array should
* not be modified by the caller.
*/
- public char[] getCharIntervals() {
+ public final int[] getCharIntervals() {
return points.clone();
}
/**
- * Gets character class of given char.
+ * Gets character class of given codepoint
*/
- int getCharClass(char c) {
+ final int getCharClass(int c) {
return SpecialOperations.findIndex(c, points);
}
/**
+ * @return the automaton
+ */
+ public Automaton getAutomaton() {
+ return automaton;
+ }
+
+ /**
* Constructs a new <code>RunAutomaton</code> from a deterministic
* <code>Automaton</code>.
*
* @param a an automaton
*/
- public RunAutomaton(Automaton a) {
+ public RunAutomaton(Automaton a, int maxInterval, boolean tableize) {
+ this.maxInterval = maxInterval;
a.determinize();
points = a.getStartPoints();
- Set<State> states = a.getStates();
- Automaton.setStateNumbers(states);
initial = a.initial.number;
- size = states.size();
+ final State[] states = a.getNumberedStates();
+ size = states.length;
accept = new boolean[size];
transitions = new int[size * points.length];
for (int n = 0; n < size * points.length; n++)
@@ -142,12 +149,18 @@ public final class RunAutomaton implemen
/*
* Set alphabet table for optimal run performance.
*/
- classmap = new int[Character.MAX_VALUE + 1];
- int i = 0;
- for (int j = 0; j <= Character.MAX_VALUE; j++) {
- if (i + 1 < points.length && j == points[i + 1]) i++;
- classmap[j] = i;
+ 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;
+ }
+ } else {
+ classmap = null;
}
+ this.automaton = a;
}
/**
@@ -157,54 +170,10 @@ public final class RunAutomaton implemen
* if a dead state is entered in an equivalent automaton with a total
* transition function.)
*/
- public int step(int state, char c) {
- return transitions[state * points.length + classmap[c]];
- }
-
- /**
- * Returns true if the given string is accepted by this automaton.
- */
- public boolean run(String s) {
- int p = initial;
- int l = s.length();
- for (int i = 0; i < l; i++) {
- p = step(p, s.charAt(i));
- if (p == -1) return false;
- }
- return accept[p];
- }
-
- /**
- * Returns true if the given string is accepted by this automaton
- */
- public boolean run(char[] s, int offset, int length) {
- int p = initial;
- int l = offset + length;
- for (int i = offset; i < l; i++) {
- p = step(p, s[i]);
- if (p == -1) return false;
- }
- return accept[p];
- }
-
- /**
- * Returns the length of the longest accepted run of the given string starting
- * at the given offset.
- *
- * @param s the string
- * @param offset offset into <code>s</code> where the run starts
- * @return length of the longest accepted run, -1 if no run is accepted
- */
- public int run(String s, int offset) {
- int p = initial;
- int l = s.length();
- int max = -1;
- for (int r = 0; offset <= l; offset++, r++) {
- if (accept[p]) max = r;
- if (offset == l) break;
- p = step(p, s.charAt(offset));
- if (p == -1) break;
- }
- return max;
+ public final int step(int state, int c) {
+ if (classmap == null)
+ return transitions[state * points.length + getCharClass(c)];
+ else
+ return transitions[state * points.length + classmap[c]];
}
}
Added: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/SortedIntSet.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/SortedIntSet.java?rev=940671&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/SortedIntSet.java (added)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/SortedIntSet.java Mon May 3 23:23:57 2010
@@ -0,0 +1,272 @@
+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.TreeMap;
+import java.util.Map;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.RamUsageEstimator;
+
+// Just holds a set of int[] states, plus a corresponding
+// int[] count per state. Used by
+// BasicOperations.determinize
+final class SortedIntSet {
+ int[] values;
+ int[] counts;
+ int upto;
+ private int hashCode;
+
+ // If we hold more than this many states, we switch from
+ // O(N^2) linear ops to O(N log(N)) TreeMap
+ private final static int TREE_MAP_CUTOVER = 30;
+
+ private final Map<Integer,Integer> map = new TreeMap<Integer,Integer>();
+
+ private boolean useTreeMap;
+
+ State state;
+
+ public SortedIntSet(int capacity) {
+ values = new int[capacity];
+ counts = new int[capacity];
+ }
+
+ // Adds this state to the set
+ public void incr(int num) {
+ if (useTreeMap) {
+ final Integer key = num;
+ Integer val = map.get(key);
+ if (val == null) {
+ map.put(key, 1);
+ } else {
+ map.put(key, 1+val);
+ }
+ return;
+ }
+
+ if (upto == values.length) {
+ values = ArrayUtil.grow(values, 1+upto);
+ counts = ArrayUtil.grow(counts, 1+upto);
+ }
+
+ for(int i=0;i<upto;i++) {
+ if (values[i] == num) {
+ counts[i]++;
+ return;
+ } else if (num < values[i]) {
+ // insert here
+ int j = upto-1;
+ while (j >= i) {
+ values[1+j] = values[j];
+ counts[1+j] = counts[j];
+ j--;
+ }
+ values[i] = num;
+ counts[i] = 1;
+ upto++;
+ return;
+ }
+ }
+
+ // append
+ values[upto] = num;
+ counts[upto] = 1;
+ upto++;
+
+ if (upto == TREE_MAP_CUTOVER) {
+ useTreeMap = true;
+ for(int i=0;i<upto;i++) {
+ map.put(values[i], counts[i]);
+ }
+ }
+ }
+
+ // Removes this state from the set, if count decrs to 0
+ public void decr(int num) {
+
+ if (useTreeMap) {
+ final int count = map.get(num);
+ if (count == 1) {
+ map.remove(num);
+ } else {
+ map.put(num, count-1);
+ }
+ // Fall back to simple arrays once we touch zero again
+ if (map.size() == 0) {
+ useTreeMap = false;
+ upto = 0;
+ }
+ return;
+ }
+
+ for(int i=0;i<upto;i++) {
+ if (values[i] == num) {
+ counts[i]--;
+ if (counts[i] == 0) {
+ final int limit = upto-1;
+ while(i < limit) {
+ values[i] = values[i+1];
+ counts[i] = counts[i+1];
+ i++;
+ }
+ upto = limit;
+ }
+ return;
+ }
+ }
+ assert false;
+ }
+
+ public void computeHash() {
+ if (useTreeMap) {
+ if (map.size() > values.length) {
+ final int size = ArrayUtil.oversize(map.size(), RamUsageEstimator.NUM_BYTES_INT);
+ values = new int[size];
+ counts = new int[size];
+ }
+ hashCode = map.size();
+ upto = 0;
+ for(int state : map.keySet()) {
+ hashCode = 683*hashCode + state;
+ values[upto++] = state;
+ }
+ } else {
+ hashCode = upto;
+ for(int i=0;i<upto;i++) {
+ hashCode = 683*hashCode + values[i];
+ }
+ }
+ }
+
+ public FrozenIntSet freeze(State state) {
+ final int[] c = new int[upto];
+ System.arraycopy(values, 0, c, 0, upto);
+ return new FrozenIntSet(c, hashCode, state);
+ }
+
+ public int hashCode() {
+ return hashCode;
+ }
+
+ public boolean equals(Object _other) {
+ if (_other == null) {
+ return false;
+ }
+ if (!(_other instanceof FrozenIntSet)) {
+ return false;
+ }
+ FrozenIntSet other = (FrozenIntSet) _other;
+ if (hashCode != other.hashCode) {
+ return false;
+ }
+ if (other.values.length != upto) {
+ return false;
+ }
+ for(int i=0;i<upto;i++) {
+ if (other.values[i] != values[i]) {
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+ public String toString() {
+ StringBuilder sb = new StringBuilder().append('[');
+ for(int i=0;i<upto;i++) {
+ if (i > 0) {
+ sb.append(' ');
+ }
+ sb.append(values[i]).append(':').append(counts[i]);
+ }
+ sb.append(']');
+ return sb.toString();
+ }
+
+ public final static class FrozenIntSet {
+ final int[] values;
+ final int hashCode;
+ final State state;
+
+ public FrozenIntSet(int[] values, int hashCode, State state) {
+ this.values = values;
+ this.hashCode = hashCode;
+ this.state = state;
+ }
+
+ public FrozenIntSet(int num, State state) {
+ this.values = new int[] {num};
+ this.state = state;
+ this.hashCode = 683+num;
+ }
+
+ public int hashCode() {
+ return hashCode;
+ }
+
+ public boolean equals(Object _other) {
+ if (_other == null) {
+ return false;
+ }
+ if (_other instanceof FrozenIntSet) {
+ FrozenIntSet other = (FrozenIntSet) _other;
+ if (hashCode != other.hashCode) {
+ return false;
+ }
+ if (other.values.length != values.length) {
+ return false;
+ }
+ for(int i=0;i<values.length;i++) {
+ if (other.values[i] != values[i]) {
+ return false;
+ }
+ }
+ return true;
+ } else if (_other instanceof SortedIntSet) {
+ SortedIntSet other = (SortedIntSet) _other;
+ if (hashCode != other.hashCode) {
+ return false;
+ }
+ if (other.values.length != values.length) {
+ return false;
+ }
+ for(int i=0;i<values.length;i++) {
+ if (other.values[i] != values[i]) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ return false;
+ }
+
+ public String toString() {
+ StringBuilder sb = new StringBuilder().append('[');
+ for(int i=0;i<values.length;i++) {
+ if (i > 0) {
+ sb.append(' ');
+ }
+ sb.append(values[i]);
+ }
+ sb.append(']');
+ return sb.toString();
+ }
+ }
+}
+
Propchange: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/SortedIntSet.java
------------------------------------------------------------------------------
svn:eol-style = native
Modified: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/SpecialOperations.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/SpecialOperations.java?rev=940671&r1=940670&r2=940671&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/SpecialOperations.java (original)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/SpecialOperations.java Mon May 3 23:23:57 2010
@@ -33,6 +33,8 @@ import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
+import org.apache.lucene.util.BytesRef;
+
/**
* Special automata operations.
*
@@ -46,7 +48,7 @@ final public class SpecialOperations {
* Finds the largest entry whose value is less than or equal to c, or 0 if
* there is no such entry.
*/
- static int findIndex(char c, char[] points) {
+ static int findIndex(int c, int[] points) {
int a = 0;
int b = points.length;
while (b - a > 1) {
@@ -70,9 +72,11 @@ final public class SpecialOperations {
* Checks whether there is a loop containing s. (This is sufficient since
* there are never transitions to dead states.)
*/
+ // TODO: not great that this is recursive... in theory a
+ // large automata could exceed java's stack
private static boolean isFinite(State s, HashSet<State> path) {
path.add(s);
- for (Transition t : s.transitions)
+ for (Transition t : s.getTransitions())
if (path.contains(t.to) || !isFinite(t.to, path)) return false;
path.remove(s);
return true;
@@ -93,10 +97,10 @@ final public class SpecialOperations {
do {
done = true;
visited.add(s);
- if (!s.accept && s.transitions.size() == 1) {
- Transition t = s.transitions.iterator().next();
+ if (!s.accept && s.numTransitions() == 1) {
+ Transition t = s.getTransitions().iterator().next();
if (t.min == t.max && !visited.contains(t.to)) {
- b.append(t.min);
+ b.appendCodePoint(t.min);
s = t.to;
done = false;
}
@@ -105,6 +109,31 @@ final public class SpecialOperations {
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.
+ public static BytesRef getCommonPrefixBytesRef(Automaton a) {
+ if (a.isSingleton()) return new BytesRef(a.singleton);
+ BytesRef ref = new BytesRef(10);
+ HashSet<State> visited = new HashSet<State>();
+ State s = a.initial;
+ boolean done;
+ do {
+ done = true;
+ visited.add(s);
+ if (!s.accept && s.numTransitions() == 1) {
+ Transition t = s.getTransitions().iterator().next();
+ if (t.min == t.max && !visited.contains(t.to)) {
+ ref.grow(++ref.length);
+ ref.bytes[ref.length - 1] = (byte)t.min;
+ s = t.to;
+ done = false;
+ }
+ }
+ } while (!done);
+ return ref;
+ }
+
/**
* Returns the longest string that is a suffix of all accepted strings and
* visits each state at most once.
@@ -119,7 +148,30 @@ final public class SpecialOperations {
Automaton r = a.clone();
reverse(r);
r.determinize();
- return reverseUnicode3(SpecialOperations.getCommonPrefix(r));
+ return new StringBuilder(SpecialOperations.getCommonPrefix(r)).reverse().toString();
+ }
+
+ public static BytesRef getCommonSuffixBytesRef(Automaton a) {
+ if (a.isSingleton()) // if singleton, the suffix is the string itself.
+ return new BytesRef(a.singleton);
+
+ // reverse the language of the automaton, then reverse its common prefix.
+ Automaton r = a.clone();
+ reverse(r);
+ r.determinize();
+ BytesRef ref = SpecialOperations.getCommonPrefixBytesRef(r);
+ reverseBytes(ref);
+ return ref;
+ }
+
+ private static void reverseBytes(BytesRef ref) {
+ if (ref.length <= 1) return;
+ int num = ref.length >> 1;
+ for (int i = ref.offset; i < ( ref.offset + num ); i++) {
+ byte b = ref.bytes[i];
+ ref.bytes[i] = ref.bytes[ref.offset * 2 + ref.length - i - 1];
+ ref.bytes[ref.offset * 2 + ref.length - i - 1] = b;
+ }
}
/**
@@ -130,8 +182,11 @@ final public class SpecialOperations {
a.expandSingleton();
// reverse all edges
HashMap<State, HashSet<Transition>> m = new HashMap<State, HashSet<Transition>>();
- Set<State> states = a.getStates();
- Set<State> accept = a.getAcceptStates();
+ State[] states = a.getNumberedStates();
+ Set<State> accept = new HashSet<State>();
+ for (State s : states)
+ if (s.isAccept())
+ accept.add(s);
for (State r : states) {
m.put(r, new HashSet<Transition>());
r.accept = false;
@@ -139,41 +194,17 @@ final public class SpecialOperations {
for (State r : states)
for (Transition t : r.getTransitions())
m.get(t.to).add(new Transition(t.min, t.max, r));
- for (State r : states)
- r.transitions = m.get(r);
+ for (State r : states) {
+ Set<Transition> tr = m.get(r);
+ r.setTransitions(tr.toArray(new Transition[tr.size()]));
+ }
// make new initial+final states
a.initial.accept = true;
a.initial = new State();
for (State r : accept)
a.initial.addEpsilon(r); // ensures that all initial states are reachable
a.deterministic = false;
+ a.clearNumberedStates();
return accept;
}
-
- /**
- * Intentionally use a unicode 3 reverse.
- * This is because we are only going to reverse it again...
- */
- private static String reverseUnicode3( final String input ){
- char[] charInput = input.toCharArray();
- reverseUnicode3(charInput, 0, charInput.length);
- return new String(charInput);
- }
-
- /**
- * Intentionally use a unicode 3 reverse.
- * This is because it is only used by getCommonSuffix(),
- * which will reverse the entire FSM using code unit reversal,
- * so we must then reverse its common prefix back using the
- * same code unit reversal.
- */
- private static void reverseUnicode3(char[] buffer, int start, int len){
- if (len <= 1) return;
- int num = len>>1;
- for (int i = start; i < ( start + num ); i++) {
- char c = buffer[i];
- buffer[i] = buffer[start * 2 + len - i - 1];
- buffer[start * 2 + len - i - 1] = c;
- }
- }
}
Modified: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/State.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/State.java?rev=940671&r1=940670&r2=940671&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/State.java (original)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/State.java Mon May 3 23:23:57 2010
@@ -28,13 +28,14 @@
*/
package org.apache.lucene.util.automaton;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.RamUsageEstimator;
import java.io.Serializable;
import java.util.Arrays;
import java.util.Collection;
-import java.util.HashSet;
-import java.util.List;
-import java.util.Set;
+import java.util.Comparator;
+import java.util.Iterator;
/**
* <tt>Automaton</tt> state.
@@ -44,7 +45,8 @@ import java.util.Set;
public class State implements Serializable, Comparable<State> {
boolean accept;
- Set<Transition> transitions;
+ public Transition[] transitionsArray;
+ public int numTransitions;
int number;
@@ -63,7 +65,25 @@ public class State implements Serializab
* Resets transition set.
*/
final void resetTransitions() {
- transitions = new HashSet<Transition>();
+ transitionsArray = new Transition[0];
+ numTransitions = 0;
+ }
+
+ private class TransitionsIterable implements Iterable<Transition> {
+ public Iterator<Transition> iterator() {
+ return new Iterator<Transition>() {
+ int upto;
+ public boolean hasNext() {
+ return upto < numTransitions;
+ }
+ public Transition next() {
+ return transitionsArray[upto++];
+ }
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+ };
+ }
}
/**
@@ -72,8 +92,17 @@ public class State implements Serializab
*
* @return transition set
*/
- public Set<Transition> getTransitions() {
- return transitions;
+ public Iterable<Transition> getTransitions() {
+ return new TransitionsIterable();
+ }
+
+ public int numTransitions() {
+ return numTransitions;
+ }
+
+ public void setTransitions(Transition[] transitions) {
+ this.numTransitions = transitions.length;
+ this.transitionsArray = transitions;
}
/**
@@ -82,7 +111,12 @@ public class State implements Serializab
* @param t transition
*/
public void addTransition(Transition t) {
- transitions.add(t);
+ if (numTransitions == transitionsArray.length) {
+ final Transition[] newArray = new Transition[ArrayUtil.oversize(1+numTransitions, RamUsageEstimator.NUM_BYTES_OBJ_REF)];
+ System.arraycopy(transitionsArray, 0, newArray, 0, numTransitions);
+ transitionsArray = newArray;
+ }
+ transitionsArray[numTransitions++] = t;
}
/**
@@ -106,44 +140,88 @@ public class State implements Serializab
/**
* Performs lookup in transitions, assuming determinism.
*
- * @param c character to look up
+ * @param c codepoint to look up
* @return destination state, null if no matching outgoing transition
- * @see #step(char, Collection)
+ * @see #step(int, Collection)
*/
- public State step(char c) {
- for (Transition t : transitions)
+ public State step(int c) {
+ assert c >= 0;
+ for (int i=0;i<numTransitions;i++) {
+ final Transition t = transitionsArray[i];
if (t.min <= c && c <= t.max) return t.to;
+ }
return null;
}
/**
* Performs lookup in transitions, allowing nondeterminism.
*
- * @param c character to look up
+ * @param c codepoint to look up
* @param dest collection where destination states are stored
- * @see #step(char)
+ * @see #step(int)
*/
- public void step(char c, Collection<State> dest) {
- for (Transition t : transitions)
+ public void step(int c, Collection<State> dest) {
+ for (int i=0;i<numTransitions;i++) {
+ final Transition t = transitionsArray[i];
if (t.min <= c && c <= t.max) dest.add(t.to);
+ }
}
void addEpsilon(State to) {
if (to.accept) accept = true;
- for (Transition t : to.transitions)
- transitions.add(t);
+ for (Transition t : to.getTransitions())
+ addTransition(t);
+ }
+
+ /** Downsizes transitionArray to numTransitions */
+ public void trimTransitionsArray() {
+ if (numTransitions < transitionsArray.length) {
+ final Transition[] newArray = new Transition[numTransitions];
+ System.arraycopy(transitionsArray, 0, newArray, 0, numTransitions);
+ transitionsArray = newArray;
+ }
}
/**
- * Returns transitions sorted by (min, reverse max, to) or (to, min, reverse
- * max)
- */
- public Transition[] getSortedTransitionArray(boolean to_first) {
- Transition[] e = transitions.toArray(new Transition[transitions.size()]);
- Arrays.sort(e, new TransitionComparator(to_first));
- return e;
+ * Reduces this state. A state is "reduced" by combining overlapping
+ * and adjacent edge intervals with same destination.
+ */
+ public void reduce() {
+ if (numTransitions <= 1) {
+ return;
+ }
+ sortTransitions(Transition.CompareByDestThenMinMax);
+ State p = null;
+ int min = -1, max = -1;
+ int upto = 0;
+ for (int i=0;i<numTransitions;i++) {
+ final Transition t = transitionsArray[i];
+ if (p == t.to) {
+ if (t.min <= max + 1) {
+ if (t.max > max) max = t.max;
+ } else {
+ if (p != null) {
+ transitionsArray[upto++] = new Transition(min, max, p);
+ }
+ min = t.min;
+ max = t.max;
+ }
+ } else {
+ if (p != null) {
+ transitionsArray[upto++] = new Transition(min, max, p);
+ }
+ p = t.to;
+ min = t.min;
+ max = t.max;
+ }
+ }
+
+ if (p != null) {
+ transitionsArray[upto++] = new Transition(min, max, p);
+ }
+ numTransitions = upto;
}
-
+
/**
* Returns sorted list of outgoing transitions.
*
@@ -151,10 +229,11 @@ public class State implements Serializab
* reverse max, to)
* @return transition list
*/
- public List<Transition> getSortedTransitions(boolean to_first) {
- return Arrays.asList(getSortedTransitionArray(to_first));
- }
+ /** Sorts transitions array in-place. */
+ public void sortTransitions(Comparator<Transition> comparator) {
+ Arrays.sort(transitionsArray, 0, numTransitions, comparator);
+ }
/**
* Return this state's number.
@@ -178,7 +257,7 @@ public class State implements Serializab
if (accept) b.append(" [accept]");
else b.append(" [reject]");
b.append(":\n");
- for (Transition t : transitions)
+ for (Transition t : getTransitions())
b.append(" ").append(t.toString()).append("\n");
return b.toString();
}
@@ -190,20 +269,4 @@ public class State implements Serializab
public int compareTo(State s) {
return s.id - id;
}
-
- /**
- * See {@link java.lang.Object#equals(java.lang.Object)}.
- */
- @Override
- public boolean equals(Object obj) {
- return super.equals(obj);
- }
-
- /**
- * See {@link java.lang.Object#hashCode()}.
- */
- @Override
- public int hashCode() {
- return super.hashCode();
- }
}
Modified: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/Transition.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/Transition.java?rev=940671&r1=940670&r2=940671&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/Transition.java (original)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/Transition.java Mon May 3 23:23:57 2010
@@ -30,12 +30,13 @@
package org.apache.lucene.util.automaton;
import java.io.Serializable;
+import java.util.Comparator;
/**
* <tt>Automaton</tt> transition.
* <p>
* A transition, which belongs to a source state, consists of a Unicode
- * character interval and a destination state.
+ * codepoint interval and a destination state.
*
* @lucene.experimental
*/
@@ -45,18 +46,18 @@ public class Transition implements Seria
* CLASS INVARIANT: min<=max
*/
- char min;
- char max;
-
- State to;
+ final int min;
+ final int max;
+ final State to;
/**
* Constructs a new singleton interval transition.
*
- * @param c transition character
+ * @param c transition codepoint
* @param to destination state
*/
- public Transition(char c, State to) {
+ public Transition(int c, State to) {
+ assert c >= 0;
min = max = c;
this.to = to;
}
@@ -68,9 +69,11 @@ public class Transition implements Seria
* @param max transition interval maximum
* @param to destination state
*/
- public Transition(char min, char max, State to) {
+ public Transition(int min, int max, State to) {
+ assert min >= 0;
+ assert max >= 0;
if (max < min) {
- char t = max;
+ int t = max;
max = min;
min = t;
}
@@ -80,12 +83,12 @@ public class Transition implements Seria
}
/** Returns minimum of this transition interval. */
- public char getMin() {
+ public int getMin() {
return min;
}
/** Returns maximum of this transition interval. */
- public char getMax() {
+ public int getMax() {
return max;
}
@@ -134,14 +137,18 @@ public class Transition implements Seria
}
}
- static void appendCharString(char c, StringBuilder b) {
- if (c >= 0x21 && c <= 0x7e && c != '\\' && c != '"') b.append(c);
+ static void appendCharString(int c, StringBuilder b) {
+ if (c >= 0x21 && c <= 0x7e && c != '\\' && c != '"') b.appendCodePoint(c);
else {
- b.append("\\u");
+ b.append("\\\\U");
String s = Integer.toHexString(c);
- if (c < 0x10) b.append("000").append(s);
- else if (c < 0x100) b.append("00").append(s);
- else if (c < 0x1000) b.append("0").append(s);
+ 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);
}
}
@@ -171,4 +178,96 @@ public class Transition implements Seria
}
b.append("\"]\n");
}
+
+ private static final class CompareByDestThenMinMaxSingle implements Comparator<Transition> {
+ public int compare(Transition t1, Transition t2) {
+ if (t1.to != t2.to) {
+ if (t1.to.number < t2.to.number) return -1;
+ else if (t1.to.number > t2.to.number) return 1;
+ }
+ if (t1.min < t2.min) return -1;
+ if (t1.min > t2.min) return 1;
+ if (t1.max > t2.max) return -1;
+ if (t1.max < t2.max) return 1;
+ return 0;
+ }
+ }
+
+ public static final Comparator<Transition> CompareByDestThenMinMax = new CompareByDestThenMinMaxSingle();
+
+ private static final class CompareByMinMaxThenDestSingle implements Comparator<Transition> {
+ public int compare(Transition t1, Transition t2) {
+ if (t1.min < t2.min) return -1;
+ if (t1.min > t2.min) return 1;
+ if (t1.max > t2.max) return -1;
+ if (t1.max < t2.max) return 1;
+ if (t1.to != t2.to) {
+ if (t1.to.number < t2.to.number) return -1;
+ if (t1.to.number > t2.to.number) return 1;
+ }
+ return 0;
+ }
+ }
+
+ public static final Comparator<Transition> CompareByMinMaxThenDest = new CompareByMinMaxThenDestSingle();
+
+ private static class UTF8InUTF16Order {
+ protected int compareCodePoint(int aByte, int bByte) {
+ if (aByte != bByte) {
+ // See http://icu-project.org/docs/papers/utf16_code_point_order.html#utf-8-in-utf-16-order
+
+ // We know the terms are not equal, but, we may
+ // have to carefully fixup the bytes at the
+ // difference to match UTF16's sort order:
+ if (aByte >= 0xee && bByte >= 0xee) {
+ if ((aByte & 0xfe) == 0xee) {
+ aByte += 0x10;
+ }
+ if ((bByte&0xfe) == 0xee) {
+ bByte += 0x10;
+ }
+ }
+ return aByte - bByte;
+ }
+ return 0;
+ }
+ }
+
+ private static final class CompareByDestThenMinMaxUTF8InUTF16OrderSingle extends UTF8InUTF16Order implements Comparator<Transition> {
+ public int compare(Transition t1, Transition t2) {
+ if (t1.to != t2.to) {
+ if (t1.to == null) return -1;
+ else if (t2.to == null) return 1;
+ else if (t1.to.number < t2.to.number) return -1;
+ else if (t1.to.number > t2.to.number) return 1;
+ }
+ int minComp = compareCodePoint(t1.min, t2.min);
+ if (minComp != 0) return minComp;
+ int maxComp = compareCodePoint(t1.max, t2.max);
+ if (maxComp != 0) return maxComp;
+ return 0;
+ }
+ }
+
+ public static final Comparator<Transition> CompareByDestThenMinMaxUTF8InUTF16Order = new CompareByDestThenMinMaxUTF8InUTF16OrderSingle();
+
+ private static final class CompareByMinMaxThenDestUTF8InUTF16OrderSingle extends UTF8InUTF16Order implements Comparator<Transition> {
+ public int compare(Transition t1, Transition t2) {
+ int minComp = compareCodePoint(t1.min, t2.min);
+ if (minComp != 0) return minComp;
+ int maxComp = compareCodePoint(t1.max, t2.max);
+ if (maxComp != 0) return maxComp;
+ if (t1.to != t2.to) {
+ if (t1.to == null) return -1;
+ else if (t2.to == null) return 1;
+ else if (t1.to.number < t2.to.number) return -1;
+ else if (t1.to.number > t2.to.number) return 1;
+ }
+ return 0;
+ }
+ }
+
+ public static final Comparator<Transition> CompareByMinMaxThenDestUTF8InUTF16Order = new CompareByMinMaxThenDestUTF8InUTF16OrderSingle();
+
+
}
Added: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/UTF32ToUTF8.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/UTF32ToUTF8.java?rev=940671&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/UTF32ToUTF8.java (added)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/UTF32ToUTF8.java Mon May 3 23:23:57 2010
@@ -0,0 +1,324 @@
+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 org.apache.lucene.util.RamUsageEstimator;
+import org.apache.lucene.util.ArrayUtil;
+
+import java.util.List;
+import java.util.ArrayList;
+
+// TODO
+// - do we really need the .bits...? if not we can make util in UnicodeUtil to convert 1 char into a BytesRef
+
+final class UTF32ToUTF8 {
+
+ // Unicode boundaries for UTF8 bytes 1,2,3,4
+ private static final int[] startCodes = new int[] {0, 128, 2048, 65536};
+ private static final int[] endCodes = new int[] {127, 2047, 65535, 1114111};
+
+ static int[] MASKS = new int[32];
+ static {
+ int v = 2;
+ for(int i=0;i<32;i++) {
+ MASKS[i] = v-1;
+ v *= 2;
+ }
+ }
+
+ // Represents one of the N utf8 bytes that (in sequence)
+ // define a code point. value is the byte value; bits is
+ // how many bits are "used" by utf8 at that byte
+ private static class UTF8Byte {
+ int value; // TODO: change to byte
+ byte bits;
+ }
+
+ // Holds a single code point, as a sequence of 1-4 utf8 bytes:
+ // TODO: maybe move to UnicodeUtil?
+ private static class UTF8Sequence {
+ private final UTF8Byte[] bytes;
+ private int len;
+
+ public UTF8Sequence() {
+ bytes = new UTF8Byte[4];
+ for(int i=0;i<4;i++) {
+ bytes[i] = new UTF8Byte();
+ }
+ }
+
+ public int byteAt(int idx) {
+ return bytes[idx].value;
+ }
+
+ public int numBits(int idx) {
+ return bytes[idx].bits;
+ }
+
+ private void set(int code) {
+ if (code < 128) {
+ // 0xxxxxxx
+ bytes[0].value = code;
+ bytes[0].bits = 7;
+ len = 1;
+ } else if (code < 2048) {
+ // 110yyyxx 10xxxxxx
+ bytes[0].value = (6 << 5) | (code >> 6);
+ bytes[0].bits = 5;
+ setRest(code, 1);
+ len = 2;
+ } else if (code < 65536) {
+ // 1110yyyy 10yyyyxx 10xxxxxx
+ bytes[0].value = (14 << 4) | (code >> 12);
+ bytes[0].bits = 4;
+ setRest(code, 2);
+ len = 3;
+ } else {
+ // 11110zzz 10zzyyyy 10yyyyxx 10xxxxxx
+ bytes[0].value = (30 << 3) | (code >> 18);
+ bytes[0].bits = 3;
+ setRest(code, 3);
+ len = 4;
+ }
+ }
+
+ private void setRest(int code, int numBytes) {
+ for(int i=0;i<numBytes;i++) {
+ bytes[numBytes-i].value = 128 | (code & MASKS[5]);
+ bytes[numBytes-i].bits = 6;
+ code = code >> 6;
+ }
+ }
+
+ public String toString() {
+ StringBuilder b = new StringBuilder();
+ for(int i=0;i<len;i++) {
+ if (i > 0) {
+ b.append(' ');
+ }
+ b.append(Integer.toBinaryString(bytes[i].value));
+ }
+ return b.toString();
+ }
+ }
+
+ private final UTF8Sequence startUTF8 = new UTF8Sequence();
+ private final UTF8Sequence endUTF8 = new UTF8Sequence();
+
+ private final UTF8Sequence tmpUTF8a = new UTF8Sequence();
+ private final UTF8Sequence tmpUTF8b = new UTF8Sequence();
+
+ // Builds necessary utf8 edges between start & end
+ void convertOneEdge(State start, State end, int startCodePoint, int endCodePoint) {
+ startUTF8.set(startCodePoint);
+ endUTF8.set(endCodePoint);
+ //System.out.println("start = " + startUTF8);
+ //System.out.println(" end = " + endUTF8);
+ build(start, end, startUTF8, endUTF8, 0);
+ }
+
+ private void build(State start, State end, UTF8Sequence startUTF8, UTF8Sequence endUTF8, int upto) {
+
+ // Break into start, middle, end:
+ if (startUTF8.byteAt(upto) == endUTF8.byteAt(upto)) {
+ // Degen case: lead with the same byte:
+ if (upto == startUTF8.len-1 && upto == endUTF8.len-1) {
+ // Super degen: just single edge, one UTF8 byte:
+ start.addTransition(new Transition(startUTF8.byteAt(upto), endUTF8.byteAt(upto), end));
+ return;
+ } else {
+ assert startUTF8.len > upto+1;
+ assert endUTF8.len > upto+1;
+ State n = newUTF8State();
+
+ // Single value leading edge
+ start.addTransition(new Transition(startUTF8.byteAt(upto), n)); // type=single
+
+ // Recurse for the rest
+ build(n, end, startUTF8, endUTF8, 1+upto);
+ }
+ } else if (startUTF8.len == endUTF8.len) {
+ if (upto == startUTF8.len-1) {
+ start.addTransition(new Transition(startUTF8.byteAt(upto), endUTF8.byteAt(upto), end)); // type=startend
+ } else {
+ start(start, end, startUTF8, upto, false);
+ if (endUTF8.byteAt(upto) - startUTF8.byteAt(upto) > 1) {
+ // There is a middle
+ all(start, end, startUTF8.byteAt(upto)+1, endUTF8.byteAt(upto)-1, startUTF8.len-upto-1);
+ }
+ end(start, end, endUTF8, upto, false);
+ }
+ } else {
+
+ // start
+ start(start, end, startUTF8, upto, true);
+
+ // possibly middle, spanning multiple num bytes
+ int byteCount = 1+startUTF8.len-upto;
+ final int limit = endUTF8.len-upto;
+ while (byteCount < limit) {
+ // wasteful: we only need first byte, and, we should
+ // statically encode this first byte:
+ tmpUTF8a.set(startCodes[byteCount-1]);
+ tmpUTF8b.set(endCodes[byteCount-1]);
+ all(start, end,
+ tmpUTF8a.byteAt(0),
+ tmpUTF8b.byteAt(0),
+ tmpUTF8a.len - 1);
+ byteCount++;
+ }
+
+ // end
+ end(start, end, endUTF8, upto, true);
+ }
+ }
+
+ private void start(State start, State end, UTF8Sequence utf8, int upto, boolean doAll) {
+ if (upto == utf8.len-1) {
+ // Done recursing
+ start.addTransition(new Transition(utf8.byteAt(upto), utf8.byteAt(upto) | MASKS[utf8.numBits(upto)-1], end)); // type=start
+ } else {
+ State n = newUTF8State();
+ start.addTransition(new Transition(utf8.byteAt(upto), n)); // type=start
+ start(n, end, utf8, 1+upto, true);
+ int endCode = utf8.byteAt(upto) | MASKS[utf8.numBits(upto)-1];
+ if (doAll && utf8.byteAt(upto) != endCode) {
+ all(start, end, utf8.byteAt(upto)+1, endCode, utf8.len-upto-1);
+ }
+ }
+ }
+
+ private void end(State start, State end, UTF8Sequence utf8, int upto, boolean doAll) {
+ if (upto == utf8.len-1) {
+ // Done recursing
+ start.addTransition(new Transition(utf8.byteAt(upto) & (~MASKS[utf8.numBits(upto)-1]), utf8.byteAt(upto), end)); // type=end
+ } else {
+ final int startCode;
+ if (utf8.numBits(upto) == 5) {
+ // special case -- avoid created unused edges (utf8
+ // doesn't accept certain byte sequences) -- there
+ // are other cases we could optimize too:
+ startCode = 194;
+ } else {
+ startCode = utf8.byteAt(upto) & (~MASKS[utf8.numBits(upto)-1]);
+ }
+ if (doAll && utf8.byteAt(upto) != startCode) {
+ all(start, end, startCode, utf8.byteAt(upto)-1, utf8.len-upto-1);
+ }
+ State n = newUTF8State();
+ start.addTransition(new Transition(utf8.byteAt(upto), n)); // type=end
+ end(n, end, utf8, 1+upto, true);
+ }
+ }
+
+ private void all(State start, State end, int startCode, int endCode, int left) {
+ if (left == 0) {
+ start.addTransition(new Transition(startCode, endCode, end)); // type=all
+ } else {
+ State lastN = newUTF8State();
+ start.addTransition(new Transition(startCode, endCode, lastN)); // type=all
+ while (left > 1) {
+ State n = newUTF8State();
+ lastN.addTransition(new Transition(128, 191, n)); // type=all*
+ left--;
+ lastN = n;
+ }
+ lastN.addTransition(new Transition(128, 191, end)); // type = all*
+ }
+ }
+
+ private State[] utf8States;
+ private int utf8StateCount;
+
+ /** Converts an incoming utf32 automaton to an equivalent
+ * utf8 one. The incoming automaton need not be
+ * deterministic. Note that the returned automaton will
+ * not in general be deterministic, so you must
+ * determinize it if that's needed. */
+ public Automaton convert(Automaton utf32) {
+ if (utf32.isSingleton()) {
+ utf32 = utf32.cloneExpanded();
+ }
+
+ State[] map = new State[utf32.getNumberedStates().length];
+ List<State> pending = new ArrayList<State>();
+ State utf32State = utf32.getInitialState();
+ pending.add(utf32State);
+ Automaton utf8 = new Automaton();
+ utf8.setDeterministic(false);
+
+ State utf8State = utf8.getInitialState();
+
+ utf8States = new State[5];
+ utf8StateCount = 0;
+ utf8State.number = utf8StateCount;
+ utf8States[utf8StateCount] = utf8State;
+ utf8StateCount++;
+
+ utf8State.setAccept(utf32State.isAccept());
+
+ map[utf32State.number] = utf8State;
+
+ while(pending.size() != 0) {
+ utf32State = pending.remove(pending.size()-1);
+ utf8State = map[utf32State.number];
+ for(int i=0;i<utf32State.numTransitions;i++) {
+ final Transition t = utf32State.transitionsArray[i];
+ final State destUTF32 = t.to;
+ State destUTF8 = map[destUTF32.number];
+ if (destUTF8 == null) {
+ destUTF8 = newUTF8State();
+ destUTF8.accept = destUTF32.accept;
+ map[destUTF32.number] = destUTF8;
+ pending.add(destUTF32);
+ }
+ convertOneEdge(utf8State, destUTF8, t.min, t.max);
+ }
+ }
+
+ utf8.setNumberedStates(utf8States, utf8StateCount);
+
+ return utf8;
+ }
+
+ private State newUTF8State() {
+ State s = new State();
+ if (utf8StateCount == utf8States.length) {
+ final State[] newArray = new State[ArrayUtil.oversize(1+utf8StateCount, RamUsageEstimator.NUM_BYTES_OBJ_REF)];
+ System.arraycopy(utf8States, 0, newArray, 0, utf8StateCount);
+ utf8States = newArray;
+ }
+ utf8States[utf8StateCount] = s;
+ s.number = utf8StateCount;
+ utf8StateCount++;
+ return s;
+ }
+
+ public static void main(String[] args) {
+ final int startCode = Integer.parseInt(args[0]);
+ final int endCode = Integer.parseInt(args[1]);
+
+ Automaton a = new Automaton();
+ State start = a.getInitialState();
+ State end = new State();
+ end.setAccept(true);
+
+ UTF32ToUTF8 converter = new UTF32ToUTF8();
+ converter.convertOneEdge(start, end, startCode, endCode);
+ }
+}
Propchange: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/UTF32ToUTF8.java
------------------------------------------------------------------------------
svn:eol-style = native