next() {
+ hasNext();
+ currentChild = nextChild;
+ nextChild = null;
+ return currentChild;
+ }
+
+ public void remove() {
+ currentChildren.remove();
+ }
+ };
+ }
+
+ public String toString() {
+ return getQuery() + " " + getcorpusQueryResults() + " " + getInspections().size();
+ }
+
+}
Index: contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/package.html
===================================================================
--- contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/package.html (revision 0)
+++ contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/package.html (revision 0)
@@ -0,0 +1,318 @@
+
+
+
+
+
+
+
+
+Abstract
+
+
+ A dictionary of correctly and incorrectly spelled words
+ pointing at one or many weighted suggestions
+ created from previous user activity
+ and backed by algorithmic suggestions.
+
+
+Consumer interface
+
+The simplest implementation would look something like this:
+
+
+SuggestionFacade facade = new SuggestionFacade(new File("data"));
+facade.getDictionary().getPrioritesBySecondLevelSuggester().putAll(facade.secondLevelSuggestionFactory());
+...
+QuerySession session = facade.getQuerySessionManager().sessionFactory();
+...
+String query = "heros of mght and magik";
+Hits hits = searcher.search(queryFactory(query));
+String suggested = facade.didYouMean(query);
+session.query(query, hits.length(), suggested);* ...
+facade.getQuerySessionManager().getSessionsByID().put(session);
+...
+facade.trainExpiredSessions();
+...
+facade.close();
+
+
+Usage can be much more complex than that and would then yeild in better suggestions.
+
+Rationale
+
+
+ These are the results from contemplating on the relationships between
+
+ - the user a priori (what the users knows to be right)
+ - user queries (what the user is searching for in the system corpus) and how they are changed during a session in
+ quest for one or many specific goals
+
+ - the results a user inspected and perhaps even classified by taking further actions
+ - the system corpus (the information available to search in)
+ - and the system a priori (things the system knows to be right, probably a part of the system corpus you trust to
+ be right. E.g. movie titles, but not user comments.)
+
+
+
+
+
+ As a user progress in their search for data in a corpus,
+ by supplying queries,
+ accepting and decline suggestions,
+ manually changing queries
+ and inspect results in different ways,
+ the system tries to find the goals of the event tree
+ and suggest these goals to future users with similair behaviour.
+
+
+It is not completly wrong to call this a semi-retarded reinforcement learning strategy.
+
+
+ When a user requests a suggestion to a query prior unknown to the dictonary,
+ second level suggesters will attempt to come up with something.
+ These are usually algorithmic and not aware of the dictionary.
+
+
+
+ In a young implementation, or in one with very little user load,
+ the dictionary will more or less act as a cache against the second level suggesters.
+
+
+
+ Spell corrections, synonyms and acronyms
+ are the most common effects I have seen from an active adaptative suggester.
+
+
+
+ As all queries ever placed are stored in the dictionary (until pruned)
+ and the dictionary key is a whitespace and punctuation free version of the query,
+ any decomposited or composited typo will be handled.
+ For instance, "leonardo da vinci" will get the key "leonardodavinci" and thus suggest
+ "leonardo da vinci" in case the input query is "leonardo davinci".
+
+
+Query goal trees
+
+
+ A user session could contain multiple quests for content.
+ For example:
+ first the user looks for the Apache licence,
+ spells it wrong, inspects different results,
+ and then the user searches for the author Ivan Goncharov.
+
+
+
+ In this package they are called different query goals.
+
+
+
+ It is up to the QueryGoalTreeExtractor implementations to decide what
+ events in a session are parts of the same goal,
+ as we don't want to suggest the user to check out Goncharov
+ when they are looking for the Apache license.
+
+
+
+ In the default query goal tree extractor,
+ nodes are parts of the same goal as their parent when:
+
+ - The queries are the same.
+ - The user took a suggestion from the system.
+ - The current and the parent queries are similair enough.
+ - The queries was entered within short enough time.
+
+
+
+ User activities are kept track of in a tree of QueryGoalNode:s,
+ where each node contains a user query,
+ if the current query (node) was a suggestion to a previous user query (node),
+ what search results was further inspected,
+ when it happend,
+ and for how long.
+
+
+
+ Figure A.
+ 
+
+ User first look for "heroes of knight and magic",
+ followed by "heroes of light and magic",
+ goes back to the first query (knight) and changes that to "heroes of night and magic",
+ followed by "heroes of might and magic".
+ The user adds a comment in the third hit
+ and then inspects the first hit,
+ see that "homm" is a common acronym and searches for that too.
+ Inspects two hits in homm
+
+
+
+ Figure B.
+ 
+
+
+
+ The tree is sent to a trainer that in this case guesses
+ "heroes of might and magic" and "homm" seems to be what the user was looking for.
+ All non-inspected results are then adapted to suggest the most similar goal.
+ The two final goals are adapted to suggest each other.
+
+
+
+Adaptive training
+
+
+ Adaptive means that the suggestions to a query
+ depends on how users previously have been acting.
+ This means that the dictionary could be tampered with quite easy by hammering the trainer with data
+ and you should therefore try to train only with data from trusted users.
+
+
+
+ The default trainer implementation works like this:
+
+ - If a user accepts the suggestion made by the system, then the score for that suggestion is incresed.
+ (positive adaptation)
+
+ - If a user does not accept the suggestion made by the system, then the score for that suggestion is decreased.
+ (negative adaptation)
+
+ -
+ If the goal tree is a single query (perhaps with multiple inspections)
+ then adapt negative on suggestion once again.
+
+ -
+ Suggestions are the queries with inspections, ordered by the classification weight.
+ All the queries in the goal without inspections will be adpated positive with
+ the query with inspections that has the shortest edit distance.
+
+ - Suggests back from best goal to second best goal. homm -> heroes of might and magic -> homm
+
+
+
+Suggesting
+
+
+ Suggestions are created by the suggester, that navigates a dictionary.
+ The default implementation works like this:
+
+ -
+ Returns highest scoring suggestion available,
+ unless the score is lower than the suggestion supression threadshold.
+
+ -
+ If there are no suggestions available, the second level suggesters
+ registred to the dictionary are used to produce the suggestions.
+
+ -
+ If the top scoring suggestion is same as the query,
+ and the second best is not supressed below threadshold,
+ switch the top two suggestions. (This should probably be a setting.)
+
+
+ Ignoring a suggestion 50 times or so with a DefaultTrainer
+ supresses a suggestions below the default threadshold.
+ If a user manually change a query to a suppresed value
+ and thus be suggested again if no other suggestion is considered more important.
+
+
+Second level suggesting
+
+
+ If the dictionary does not contain a suggestion for a given query,
+ it will be passed on to any available SecondLevelSuggester,
+ usually an algorithmic suggestion scheme
+ that hopefully can come up with something.
+ When a user accepts such a suggestion
+ it will be picked up by the adaptive trainer
+ and become a part of the dictionary.
+
+
+A priori corpus dependency
+
+
+ In order for second level suggesters to work they need a corpus that is known to be correct:
+ an a priori corpus. This ought to be a small index that only contain text people do not know how
+ to spell, i.e. it only consume clock ticks at suggestion time if it is filled with phrases
+ people always get right.
+
+
+A priori corpus extraction
+
+
+ By inverting the dictionary and extracting the tokens or phrases people have most problem spelling,
+ a pretty good a priori corpus can be created. This will however require a dictionary that has been
+ exposed to quite some user activity.
+
+
+Token suggesters
+
+
+ The lowest level of suggestion is single token suggestions,
+ and the default implementation is a refactor of the contrib/spellcheck.
+
+
+NgramTokenSuggester
+
+A refactor of the Lucene crontrib/spellcheck single token ngram suggester
+
+TokenPhraseSuggester
+
+
+ Combines the output from a single token suggester, applied to each token (word) in a phrase,
+ to create possible phrases. In essense this is the same thing as a SpanFuzzyQuery.
+
+
+
+ For example, the user places the query "thh best game".
+ The matrix of similar tokens are:
+
+ the best game
+ tho rest fame
+ lame
+
+ These can be combined as:
+
+ tho best game
+ tho best fame
+ tho best lame
+ tho rest game
+ tho rest fame
+ tho rest lame
+ the best game
+ the best fame
+ the best lame
+ the rest game
+ the rest fame
+ the rest lame
+
+ A query is created for each combination to find valid suggestions in the a priori index.
+ In the default implementation SpanNearQueries are used.
+
+
+ If any of the valid hits contains a TermPositionVector
+ it will be analyzed and suggest the query in the order of terms in the corpus.
+
+
+
+ E.g. query "camel that broke the staw" is suggested with "straw that broke the camel"
+
+
+
+ todo: if term offsets available and value stored, suggest that value (for cosmetic reasons).
+
+
+MultiTokenSuggester
+
+
+ Works similar to the TokenPhraseSuggester, but uses term queries rather than span near queries,
+ used when people place queries where the terms within the query really has nothing to do with each other.
+ This second level suggester should have a lower priority than the TokenPhraseSuggester.
+
+
+
+
+
+
+
Index: contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/impl/DefaultQueryGoalJuror.java
===================================================================
--- contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/impl/DefaultQueryGoalJuror.java (revision 0)
+++ contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/impl/DefaultQueryGoalJuror.java (revision 0)
@@ -0,0 +1,78 @@
+package org.apache.lucene.search.didyoumean.impl;
+
+/*
+ * Licensed 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.search.didyoumean.QueryGoalNode;
+
+import java.util.*;
+
+/**
+ * Sets the chronologycally last placed query as the goal.
+ *
+ * @see QueryGoalJuror
+ * @author Karl Wettin
+ * Date: 2007-feb-23
+ * Time: 23:53:21
+ */
+public class DefaultQueryGoalJuror implements QueryGoalJuror {
+
+ // private static Log log = LogFactory.getLog(HitsBasedJuror.class);
+ // private static long serialVersionUID = 1l;
+
+ /**
+ * Sets the chronologycally last placed query as the goal.
+ * @param goalTreeRootNode Query goal tree root
+ * @return the goal nodes
+ * @throws RuntimeException If query goal tree already contains one or more goals.
+ */
+ public List> createGoals(QueryGoalNode goalTreeRootNode) {
+
+ List> nodes = new ArrayList>();
+
+ for (Iterator> children = goalTreeRootNode.iterateChildrenRecursive(); children.hasNext();) {
+ QueryGoalNode node = children.next();
+ for (QueryGoalNode.Inspection inspection : node.getInspections()) {
+ if (inspection.getGoalClassification() > QueryGoalNode.MOO) {
+ throw new RuntimeException("The query goal tree already contains one or more goals!");
+ }
+ }
+ nodes.add(node);
+ }
+ nodes.add(goalTreeRootNode);
+
+
+ Collections.sort(nodes, new Comparator>() {
+ public int compare(QueryGoalNode queryGoalNode, QueryGoalNode queryGoalNode1) {
+ return queryGoalNode1.getTimestamp().compareTo(queryGoalNode.getTimestamp());
+ }
+
+ });
+
+ List> goalNodes = new LinkedList>();
+
+ if (nodes.get(0).getcorpusQueryResults() > 0) {
+
+ nodes.get(0).new Inspection(null, QueryGoalNode.GOAL);
+ goalNodes.add(nodes.get(0));
+ }
+
+ return goalNodes;
+
+
+ }
+
+}
Index: contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/impl/DefaultQueryGoalTreeExtractor.java
===================================================================
--- contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/impl/DefaultQueryGoalTreeExtractor.java (revision 0)
+++ contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/impl/DefaultQueryGoalTreeExtractor.java (revision 0)
@@ -0,0 +1,240 @@
+package org.apache.lucene.search.didyoumean.impl;
+
+/*
+ * Licensed 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.search.didyoumean.EditDistance;
+import org.apache.lucene.search.didyoumean.Levenshtein;
+import org.apache.lucene.search.didyoumean.QueryGoalNode;
+
+import java.io.Serializable;
+import java.util.*;
+import java.util.concurrent.ConcurrentLinkedQueue;
+
+/**
+ *
+ * A not too advanced way to extract the goals from a session.
+ *
+ * Nodes are parts of the same goal as their parent when:
+ *
+ * - the queries are the same
+ * - the suggestion to the parent query was followed
+ * - the queries are similair enough
+ * - the queries was entered within short enough time
+ *
+ *
+ * @author Karl Wettin
+ * Date: Aug 1, 2006
+ * Time: 5:01:14 PM
+ */
+public class DefaultQueryGoalTreeExtractor implements org.apache.lucene.search.didyoumean.QueryGoalTreeExtractor, Serializable {
+
+ private static final long serialVersionUID = 1l;
+
+ public static final long DEFAULT_MAXIMUM_MILLISECONDS_BETWEEN_QUERIES = 20000;
+ public static final double DEFAULT_MINIMUM_SIMILARITY = 0.6f;
+ public static final int DEFAULT_MINIMUM_HITS_IN_FINAL_QUERY = 1;
+ public static final double DEFAULT_MINIMUM_HITS_RATIO = 0f;
+
+
+ private long maximumMillisecondsBetweenQueries = DEFAULT_MAXIMUM_MILLISECONDS_BETWEEN_QUERIES;
+ private double minimumSimilarity = DEFAULT_MINIMUM_SIMILARITY;
+ private int minimumHitsInFinalQuery = DEFAULT_MINIMUM_HITS_IN_FINAL_QUERY;
+ private double minimumHitsRatio = DEFAULT_MINIMUM_HITS_RATIO;
+
+ private double inspectionWeightGoalThreadshold = 0d;
+
+ private class GoalFactory {
+ private List> goalQueries = new LinkedList>();
+ }
+
+ public boolean isPartOfParentGoal(QueryGoalNode child) {
+ if (child.getParent() == null) {
+ // no parent
+ return false;
+ } else if (child.getQuery().equals(child.getParent().getSuggestion())) {
+ // the user followed a suggestion made by the system.
+ return true;
+ } else if (child.getQuery().equals(child.getParent().getQuery())) {
+ // it is the same query placed once more.
+ // todo: consider if this should have been merged when creating a new child in DefaultTrainer?
+ return true;
+ } else {
+ // check edit distance
+
+ EditDistance editDistance = editDistanceFactory(child.getParent().getQuery());
+ //double similarity = ((double) distance / previousLink.link.length());
+ double similarity = 1.0f - ((double) editDistance.getDistance(child.getQuery()) / Math.min(child.getQuery().length(), child.getParent().getQuery().length()));
+ if (similarity >= getMinimumSimilarity()) {
+ // similair enough
+ return true;
+ } else if (child.getTimestamp() - child.getParent().getTimestamp() < getMaximumMillisecondsBetweenQueries()) {
+ // todo: consider time spent inspecting et c.
+
+ // not similair enough.
+ // but fast enough between searches.
+
+ // if the child or its children reached the goal // todo recursive
+ // then it is a part of the parent goal.
+
+ Double weight = child.calculateInspectionWeight();
+ if (weight == null) {
+ return false;
+ } else {
+ return weight > getInspectionWeightGoalThreadshold();
+ }
+
+ }
+ }
+
+ return false;
+ }
+
+ public EditDistance editDistanceFactory(String sd) {
+ return new Levenshtein(sd);
+ }
+
+
+ public List> extractGoalRoots(QueryGoalNode sessionRoot) {
+
+ List> goalRoots = new LinkedList>();
+
+ Map, GoalFactory> goalFactoryByNodes = new HashMap, GoalFactory>();
+
+
+ Queue> leafsQueue = new ConcurrentLinkedQueue>();
+ for (Iterator> leafsIterator = sessionRoot.iterateChildrenRecursive(); leafsIterator.hasNext();) {
+ QueryGoalNode node = leafsIterator.next();
+ if (node.getChildren().size() == 0) {
+ leafsQueue.add(node);
+ }
+ }
+
+ if (leafsQueue.size() == 0) {
+ // this is just a single node.
+ goalRoots.add(sessionRoot);
+ } else while (leafsQueue.size() > 0) {
+ QueryGoalNode node = leafsQueue.poll();
+ while (isPartOfParentGoal(node)) {
+ GoalFactory nodeGoalFactory = goalFactoryByNodes.get(node);
+ if (nodeGoalFactory == null) {
+ nodeGoalFactory = new GoalFactory();
+ nodeGoalFactory.goalQueries.add(node);
+ goalFactoryByNodes.put(node, nodeGoalFactory);
+ }
+
+ if (node.getParent() != null) {
+ GoalFactory parentGoalFactory = goalFactoryByNodes.get(node.getParent());
+ if (parentGoalFactory != null) {
+ // the parent has already been added to a goal factory
+ // merge this goal factory with the parent goal factory.
+ for (QueryGoalNode childGoalNode : goalFactoryByNodes.get(node).goalQueries) {
+ goalFactoryByNodes.put(childGoalNode, parentGoalFactory);
+ parentGoalFactory.goalQueries.add(childGoalNode);
+ }
+ } else {
+ goalFactoryByNodes.put(node, nodeGoalFactory);
+ nodeGoalFactory.goalQueries.add(node.getParent());
+ }
+ }
+
+ node = node.getParent();
+ }
+
+ // make current node a new root
+ if (node.getParent() != null) {
+ leafsQueue.add(node.getParent()); // parent is a new goal leaf!
+ node.getParent().getChildren().remove(node);
+ node.setParent(null);
+ }
+ goalRoots.add(node);
+ }
+
+ return goalRoots;
+ }
+
+ /**
+ * @return maximun time in milliseconds between two queries to be considered part of the same correction sequence
+ */
+ public final long getMaximumMillisecondsBetweenQueries() {
+ return maximumMillisecondsBetweenQueries;
+ }
+
+ /**
+ * @param maximumMillisecondsBetweenQueries
+ * maximun time in milliseconds between two queries to be considered part of the same correction sequence
+ */
+ public final void setMaximumMillisecondsBetweenQueries(long maximumMillisecondsBetweenQueries) {
+ this.maximumMillisecondsBetweenQueries = maximumMillisecondsBetweenQueries;
+ }
+
+ /**
+ * @return minimum edit-distance between two queries in order to be considered part of the same correction sequence
+ */
+ public final double getMinimumSimilarity() {
+ return minimumSimilarity;
+ }
+
+ /**
+ * Using Levenshtein edit distance factory,
+ * anything less than 0.5 is crazy,
+ * 0.7 can be almost be considered fail-safe,
+ * but as this is an adapting spell checker some bad data is ok,
+ * so I set default to 0.6
+ *
+ * @param minimumSimilarity minimum edit-distance between two queries in order to be considered part of the same correction sequence
+ */
+ public final void setMinimumSimilarity(double minimumSimilarity) {
+ this.minimumSimilarity = minimumSimilarity;
+ }
+
+ /**
+ * @return number of hits required in the final query of a correction sequence
+ */
+ public final int getMinimumHitsInFinalQuery() {
+ return minimumHitsInFinalQuery;
+ }
+
+ /**
+ * @param minimumHitsInFinalQuery number of hits required in the final query of a correction sequence
+ */
+ public final void setMinimumHitsInFinalQuery(int minimumHitsInFinalQuery) {
+ this.minimumHitsInFinalQuery = minimumHitsInFinalQuery;
+ }
+
+ /**
+ * @return minimum allowed ratio of the low and top number of hits of any two queries in a correction sequence. default to 2, that is twice as many hits in the top resulting query is required
+ */
+ public final double getMinimumHitsRatio() {
+ return minimumHitsRatio;
+ }
+
+ /**
+ * @param minimumHitsRatio minimum allowed ratio of the low and top number of hits of any two queries in a correction sequence. default to 2, that is twice as many hits in the top resulting query is required
+ */
+ public final void setMinimumHitsRatio(double minimumHitsRatio) {
+ this.minimumHitsRatio = minimumHitsRatio;
+ }
+
+
+ public double getInspectionWeightGoalThreadshold() {
+ return inspectionWeightGoalThreadshold;
+ }
+
+ public void setInspectionWeightGoalThreadshold(double inspectionWeightGoalThreadshold) {
+ this.inspectionWeightGoalThreadshold = inspectionWeightGoalThreadshold;
+ }
+}
Index: contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/impl/DefaultTrainer.java
===================================================================
--- contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/impl/DefaultTrainer.java (revision 0)
+++ contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/impl/DefaultTrainer.java (revision 0)
@@ -0,0 +1,321 @@
+package org.apache.lucene.search.didyoumean.impl;
+
+/*
+ * Licensed 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.search.didyoumean.*;
+import org.apache.lucene.search.didyoumean.dictionary.Dictionary;
+import org.apache.lucene.search.didyoumean.dictionary.SuggestionList;
+
+import java.util.*;
+
+import com.sleepycat.je.DatabaseException;
+
+/**
+ * A simple adapting suggestion strategy that updates the content of a dictionary based on what a query session looked like.
+ *
+ * If a user accepts the suggestion made by the system, then we increase the score for that suggestion. (positive adaptation)
+ * If a user does not accept the suggestion made by the system, then we decrease the score for that suggestion. (negative adaptation)
+ *
+ * The the goal tree is a single query, one query only (perhaps with multiple inspections)
+ * then we adapt negative once again.
+ *
+ * Suggestions are the query with inspections, ordered by the classification weight.
+ * All the queries in the goal witout inspections will be adpated positive with
+ * the query with inspections that has the shortest edit distance.
+ *
+ * Suggest back from best goal to second best goal. homm -> heroes of might and magic -> homm
+ *
+ * In case of no inspections in a goal tree, a {@link org.apache.lucene.search.didyoumean.impl.QueryGoalJuror} is used to judge what is the goal.
+ *
+ * @author Karl Wettin
+ * Date: Jul 31, 2006
+ * Time: 4:56:13 PM
+ */
+public class DefaultTrainer implements Trainer {
+
+ private boolean trainingFinalGoalAsSelf = true;
+
+ private double notSuggestedPositiveAdaptationFactor = 1.4d;
+ private double acceptedSuggestionPositiveAdaptationFactor = 1.4d;
+ private double ignoredSuggestionNegativeAdaptationFactor = 0.9d;
+
+ private QueryGoalJuror juror = new DefaultQueryGoalJuror();
+
+ private static Comparator scoreComparator = new Comparator() {
+ public int compare(Suggestion o1, Suggestion o2) {
+ return Double.compare(o2.getScore(), o1.getScore());
+ }
+ };
+
+
+ public void trainGoalTree(Dictionary dictionary, QueryGoalNode goalTreeRoot) throws DatabaseException {
+
+ int numChildrenRecursive = 0;
+ // positive and negative adaptation of suggestion scores
+ for (Iterator> it = goalTreeRoot.iterateChildrenRecursive(); it.hasNext();) {
+ numChildrenRecursive++;
+ QueryGoalNode node = it.next();
+ if (node.getParent().getSuggestion() != null) {
+
+ SuggestionList suggestions = dictionary.getSuggestions(dictionary.keyFormatter(node.getParent().getQuery()));
+ Suggestion suggestion = suggestions.get(node.getParent().getSuggestion());
+
+ if (node.getQuery().equals(node.getParent().getSuggestion())) {
+ // user took our suggestion, increase the score of that suggestion.
+ suggestion.setScore(suggestion.getScore() * getAcceptedSuggestionPositiveAdaptationFactor());
+ } else {
+ // user did not take our suggestion, decrease the score of that suggestion.
+ suggestion.setScore(suggestion.getScore() * getIgnoredSuggestionNegativeAdaptationFactor());
+ }
+
+ suggestions.sort();
+ dictionary.getSuggestionsByQuery().put(suggestions);
+
+
+ }
+ }
+
+ if (numChildrenRecursive == 0) {
+
+ // a single query
+
+ boolean train = false;
+ for (QueryGoalNode.Inspection inspection : goalTreeRoot.getInspections()) {
+ if (inspection.getGoalClassification() > QueryGoalNode.MOO) {
+ train = true;
+ break;
+ }
+ }
+ if (train) {
+ adaptPositive(dictionary, goalTreeRoot.getQuery(), goalTreeRoot.getcorpusQueryResults(), goalTreeRoot);
+ }
+//
+// // if inspected, negative train on top suggestion,
+// // but only if available and not the same as the query
+// SuggestionList suggestions = dictionary.getSuggestions(goalTreeRoot.getQuery());
+// if (goalTreeRoot.getInspections().size() > 0 && suggestions != null && suggestions.size() > 0 && !suggestions.get(0).getSuggested().equals(goalTreeRoot.getQuery())) {
+// suggestions.get(0).setPopularity(suggestions.get(0).getPopularity() * getIgnoredSuggestionNegativeAdaptationFactor());
+// suggestions.sort();
+// }
+ } else {
+
+ /** suggestions are the nodes with inspections, ordered by the classification weight. */
+ List> nodesWithGoals = new LinkedList>();
+
+ /** all the other nodes, them without inspections, will suggest the suggestions. */
+ List> nodesWithoutGoals = new LinkedList>();
+
+ if (goalTreeRoot.getInspections().size() > 0) {
+ nodesWithGoals.add(goalTreeRoot);
+ } else {
+ nodesWithoutGoals.add(goalTreeRoot);
+ }
+ for (Iterator> it = goalTreeRoot.iterateChildrenRecursive(); it.hasNext();) {
+ QueryGoalNode node = it.next();
+ if (node.getInspections().size() > 0) {
+ for (QueryGoalNode.Inspection inspection : node.getInspections()) {
+ if (inspection.getGoalClassification() > QueryGoalNode.MOO) {
+ nodesWithGoals.add(node);
+ break;
+ }
+ }
+ }
+
+ if (!nodesWithGoals.contains(node)) {
+ nodesWithoutGoals.add(node);
+ }
+ }
+
+ if (nodesWithGoals.size() == 0) {
+ // there was no inspections.
+ // we have no clue what the users was looking for. not sure if this mean something extra.
+
+ // call juror strategy
+ nodesWithGoals = getJuror().createGoals(goalTreeRoot);
+ nodesWithoutGoals.removeAll(nodesWithGoals);
+ if (nodesWithGoals.size() == 0) {
+ return;
+ }
+ }
+
+ {
+ // order by inspection weight and time - most recent query with top importance.
+ Collections.sort(nodesWithGoals, new Comparator>() {
+ public int compare(QueryGoalNode queryGoalNode, QueryGoalNode queryGoalNode1) {
+ int ret = Double.compare(queryGoalNode1.calculateInspectionWeight(), queryGoalNode.calculateInspectionWeight());
+ if (ret == 0) {
+ // todo: consider by number of hits? does the same inspection weight but more hits mean something better or something worse?
+
+ // by time
+ if (queryGoalNode1.getTimestamp() == queryGoalNode.getTimestamp()) {
+ return 0;
+ } else if (queryGoalNode1.getTimestamp() > queryGoalNode.getTimestamp()) {
+ return 1;
+ } else {
+ return -1;
+ }
+ } else {
+ return ret;
+ }
+ }
+ });
+
+ if (isTrainingFinalGoalAsSelf()) {
+ // we also train the suggestion as suggested self,
+ // as we store the dictionary key stripped from characters.
+ // this will suggest "the da vinci code" from "thedavincicode" and "the davinci code".
+
+ // it is however not needed to suppres bad suggestions from beeing suggested.
+ // for that its enough with a low enough suggestion score detected by the suggester.
+
+ for (QueryGoalNode node : nodesWithGoals) {
+
+ // but only register it once.
+ SuggestionList suggestions = dictionary.getSuggestions(node.getQuery());
+ if (suggestions == null) {
+ suggestions = dictionary.suggestionListFactory(node.getQuery());
+ }
+
+ if (!suggestions.containsSuggested(nodesWithGoals.get(0).getQuery())) {
+ suggestions.addSuggested(nodesWithGoals.get(0).getQuery(), 1d, nodesWithGoals.get(0).getcorpusQueryResults());
+ dictionary.getSuggestionsByQuery().put(suggestions);
+ }
+
+ // uncomment to adapt every time
+ // adaptPositive(dictionary, nodesWithGoals.get(0).getQuery(), nodesWithGoals.get(0).getCorpusQueryResults(), node);
+ }
+ }
+
+ // suggest back from best goal to second best goal. homm -> heroes of might and magic -> homm
+ if (nodesWithGoals.size() > 1) {
+ adaptPositive(dictionary, nodesWithGoals.get(1).getQuery(), nodesWithGoals.get(1).getcorpusQueryResults(), nodesWithGoals.get(0));
+ }
+
+ // node without inspections are suggested to try the node with inspections that has least edit distance to the query.
+ for (QueryGoalNode node : nodesWithoutGoals) {
+ QueryGoalNode closestNode = findNodeWithShortestDistanceToQuery(node, nodesWithGoals);
+ adaptPositive(dictionary, closestNode.getQuery(), closestNode.getcorpusQueryResults(), node);
+ }
+ }
+ }
+ }
+
+
+ public EditDistance editDistanceFactory(String sd) {
+ return new Levenshtein(sd);
+ }
+
+
+ private QueryGoalNode findNodeWithShortestDistanceToQuery(QueryGoalNode queryNode, Collection> targetNodes) {
+ EditDistance editDistance = editDistanceFactory(queryNode.getQuery());
+ QueryGoalNode closest = null;
+ double closestDistance = Double.MAX_VALUE;
+ for (QueryGoalNode targetNode : targetNodes) {
+ double distanceToTarget = editDistance.getDistance(targetNode.getQuery());
+ if (distanceToTarget < closestDistance) {
+ closestDistance = distanceToTarget;
+ closest = targetNode;
+ }
+ }
+ return closest;
+ }
+
+ private void adaptPositive(Dictionary dictionary, String suggested, Integer suggestedCorpusQueryResults, QueryGoalNode dictionaryKeyNode) throws DatabaseException {
+ SuggestionList suggestions = dictionary.getSuggestions(dictionaryKeyNode.getQuery());
+ if (suggestions == null) {
+ suggestions = dictionary.suggestionListFactory(dictionaryKeyNode.getQuery());
+ suggestions.addSuggested(suggested, 1d, suggestedCorpusQueryResults);
+ } else {
+ boolean suggestionUpdated = false;
+ for (Suggestion existingSuggestion : suggestions) {
+ if (existingSuggestion.getSuggested().equals(suggested)) {
+ // the query already have this suggestion in the suggestions.
+ // increase the score for the suggestion. (positive adaptation)
+ double score = existingSuggestion.getScore() * getNotSuggestedPositiveAdaptationFactor();
+ if (score > 9999) {
+ score = 9999;
+ }
+ existingSuggestion.setScore(score);
+ suggestionUpdated = true;
+ break;
+ }
+ }
+ if (!suggestionUpdated) {
+ suggestions.addSuggested(suggested, 1d, suggestedCorpusQueryResults);
+ }
+ suggestions.sort();
+ }
+ dictionary.getSuggestionsByQuery().put(suggestions);
+ }
+
+
+ public double getAcceptedSuggestionPositiveAdaptationFactor() {
+ return acceptedSuggestionPositiveAdaptationFactor;
+ }
+
+ public void setAcceptedSuggestionPositiveAdaptationFactor(double acceptedSuggestionPositiveAdaptationFactor) {
+ this.acceptedSuggestionPositiveAdaptationFactor = acceptedSuggestionPositiveAdaptationFactor;
+ }
+
+ public double getIgnoredSuggestionNegativeAdaptationFactor() {
+ return ignoredSuggestionNegativeAdaptationFactor;
+ }
+
+ public void setIgnoredSuggestionNegativeAdaptationFactor(double ignoredSuggestionNegativeAdaptationFactor) {
+ this.ignoredSuggestionNegativeAdaptationFactor = ignoredSuggestionNegativeAdaptationFactor;
+ }
+
+ public double getNotSuggestedPositiveAdaptationFactor() {
+ return notSuggestedPositiveAdaptationFactor;
+ }
+
+ public void setNotSuggestedPositiveAdaptationFactor(double notSuggestedPositiveAdaptationFactor) {
+ this.notSuggestedPositiveAdaptationFactor = notSuggestedPositiveAdaptationFactor;
+ }
+
+ public boolean isTrainingFinalGoalAsSelf() {
+ return trainingFinalGoalAsSelf;
+ }
+
+ public void setTrainingFinalGoalAsSelf(boolean trainingFinalGoalAsSelf) {
+ this.trainingFinalGoalAsSelf = trainingFinalGoalAsSelf;
+ }
+
+ public static Comparator getScoreComparator() {
+ return scoreComparator;
+ }
+
+ public static void setScoreComparator(Comparator scoreComparator) {
+ DefaultTrainer.scoreComparator = scoreComparator;
+ }
+
+
+ /**
+ * @return Stragegy used when a query goal tree has no goals.
+ */
+ public QueryGoalJuror getJuror() {
+ return juror;
+ }
+
+ /**
+ * @param juror Stragegy used when a query goal tree has no goals.
+ */
+ public void setJuror(QueryGoalJuror juror) {
+ this.juror = juror;
+ }
+
+}
Index: contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/impl/QueryGoalJuror.java
===================================================================
--- contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/impl/QueryGoalJuror.java (revision 0)
+++ contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/impl/QueryGoalJuror.java (revision 0)
@@ -0,0 +1,37 @@
+package org.apache.lucene.search.didyoumean.impl;
+
+/*
+ * Licensed 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.search.didyoumean.QueryGoalNode;
+
+import java.util.List;
+
+/**
+ * When a query goal tree has no goals, an implementation of this interface is used to set them up.
+ *
+ * @author Karl Wettin
+ * Date: 2007-feb-24
+ * Time: 02:25:25
+ */
+public interface QueryGoalJuror {
+
+ /**
+ * @param goalTreeRootNode Query goal tree root node.
+ * @return the goal nodes
+ */
+ public abstract List> createGoals(QueryGoalNode goalTreeRootNode);
+}
Index: contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/impl/DefaultSuggester.java
===================================================================
--- contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/impl/DefaultSuggester.java (revision 0)
+++ contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/impl/DefaultSuggester.java (revision 0)
@@ -0,0 +1,232 @@
+package org.apache.lucene.search.didyoumean.impl;
+
+/*
+ * Licensed 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 com.sleepycat.je.DatabaseException;
+import org.apache.lucene.search.didyoumean.AbstractSuggester;
+import org.apache.lucene.search.didyoumean.EditDistance;
+import org.apache.lucene.search.didyoumean.Levenshtein;
+import org.apache.lucene.search.didyoumean.Suggestion;
+import org.apache.lucene.search.didyoumean.dictionary.Dictionary;
+import org.apache.lucene.search.didyoumean.dictionary.SuggestionList;
+
+import java.io.Serializable;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.LinkedList;
+import java.util.List;
+
+/**
+ * Returns highest scoring suggestion available,
+ * unless the score is lower than the suggestion supression threadshold.
+ *
+ * If there are no suggestions available, the second level suggesters
+ * registred to the dictionary are used to produce the suggestions.
+ *
+ * If the top scoring suggestion is same as the query,
+ * and the second best is not supressed below threadshold,
+ * change order
+ *
+ * Ignoring a suggestion 50 times or so with a DefaultTrainer makes a score hit 0.05d.
+ *
+ * It will navigate towards better suggestions this way:
+ *
+ * Suggestion[] currentSuggestions = toQuerySensitiveArray(suggestions, n, query);
+ * Suggestion[] topSuggestionSuggestions = toQuerySensitiveArray(gatherSuggestionList(dictionary, currentSuggestions[0].getSuggested(), n), n, currentSuggestions[0].getSuggested());
+ * // if the input query results in bad results according to some strategy,
+ * // then attempt to navigate towards a top suggestion that does result in something good,
+ * while (
+ * topSuggestionSuggestions != null && topSuggestionSuggestions.length > 0
+ * && (currentSuggestions[0].getCorpusQueryResults().size() == 0
+ * || currentSuggestions[0].getCorpusQueryResults().size() * 3 < topSuggestionSuggestions[0].getCorpusQueryResults().size())) {
+ * currentSuggestions = topSuggestionSuggestions;
+ * topSuggestionSuggestions = toQuerySensitiveArray(gatherSuggestionList(dictionary, currentSuggestions[0].getSuggested(), n), n, currentSuggestions[0].getSuggested());
+ * }
+ *
+ * todo: above should be an aggregated strategy!
+ *
+ * @author Karl Wettin
+ * Date: Jul 31, 2006
+ * Time: 4:56:34 PM
+ */
+public class DefaultSuggester extends AbstractSuggester implements Serializable {
+
+ private static final long serialVersionUID = 1l;
+
+
+ public DefaultSuggester() {
+ }
+
+ /**
+ * ignoring a suggestion 50 times or so makes hit 0.05d.
+ */
+ private double suggestionSupressionThreadshold = 0.05d;
+
+ private SuggestionList gatherSuggestionList(Dictionary dictionary, String query, int n) throws DatabaseException {
+ SuggestionList suggestions = dictionary.getSuggestions(query);
+ if (suggestions != null && suggestions.size() > 0) {
+ // if top suggestion is suppressed,
+ // then try to get some more suggestions from second level
+ if (suggestions.get(0).getScore() < getSuggestionSupressionThreadshold()) {
+ Suggestion[] secondLevel = dictionary.getSecondLevelSuggestion(query, n);
+ if (secondLevel != null && secondLevel.length > 0) {
+ // then merge the not yet seen suggestions with the dictionary suggestions.
+ // this way we don't suggest something that has been suppressed.
+ double score = 1d;
+ for (Suggestion suggestion : secondLevel) {
+ score -= 0.01d;
+ if (!suggestions.containsSuggested(suggestion.getSuggested())) {
+ suggestions.addSuggested(suggestion.getSuggested(), score, suggestion.getCorpusQueryResults());
+ dictionary.getSuggestionsByQuery().put(suggestions);
+ }
+ }
+ }
+ }
+ }
+ return suggestions;
+ }
+
+ public Suggestion[] didYouMean(Dictionary dictionary, String query, int n) throws DatabaseException {
+ SuggestionList suggestions = gatherSuggestionList(dictionary, query, n);
+ if (suggestions != null) {
+ if (suggestions.size() > 0) {
+ Suggestion[] originalSuggestions = toQuerySensitiveArray(suggestions, n, query);
+ Suggestion[] currentSuggestions = originalSuggestions;
+ Suggestion[] topSuggestionSuggestions = toQuerySensitiveArray(gatherSuggestionList(dictionary, currentSuggestions[0].getSuggested(), n), n, currentSuggestions[0].getSuggested());
+ // if the input query results in bad results according to some strategy,
+ // then attempt to navigate towards a top suggestion that does result in something good,
+ int noEternalLoops = 0;
+ while (hasBetterNestedSuggestion(topSuggestionSuggestions, currentSuggestions)) {
+ // no eternal loops!
+ if (++noEternalLoops == 100) {
+ System.out.println(query + " points back at it self or is too complex!");
+ return originalSuggestions;
+ }
+ currentSuggestions = topSuggestionSuggestions;
+ topSuggestionSuggestions = toQuerySensitiveArray(gatherSuggestionList(dictionary, currentSuggestions[0].getSuggested(), n), n, currentSuggestions[0].getSuggested());
+ }
+ return currentSuggestions;
+ } else {
+ return dictionary.getSecondLevelSuggestion(query, n);
+ }
+
+ } else {
+ return dictionary.getSecondLevelSuggestion(query, n);
+ }
+ }
+
+ /**
+ * If topSuggestionSuggestions points at something
+ * that has three times as many results as the top current suggestion
+ * then this method returns true.
+ *
+ * if the current suggestion has no hits
+ * and there is a suggestion with hits in topSuggestionSuggestions
+ * this method returns true
+ *
+ * @param topSuggestionSuggestions suggestions to first suggestion in currentSuggestions
+ * @param currentSuggestions suggestions to the current query
+ * @return true if topSuggestionSuggestions has a better suggestion than currentSuggestions
+ */
+ public boolean hasBetterNestedSuggestion(Suggestion[] topSuggestionSuggestions, Suggestion[] currentSuggestions) {
+ return topSuggestionSuggestions != null
+ && topSuggestionSuggestions.length > 0
+ && currentSuggestions[0].getCorpusQueryResults() != null
+ &&
+ ((currentSuggestions[0].getCorpusQueryResults() == 0 && topSuggestionSuggestions[0].getCorpusQueryResults() > 0)
+ || (currentSuggestions[0].getCorpusQueryResults() * 3 < topSuggestionSuggestions[0].getCorpusQueryResults())
+ );
+ }
+
+
+ public EditDistance editDistanceFactory(String sd) {
+ return new Levenshtein(sd);
+ }
+
+
+ private Suggestion[] toQuerySensitiveArray(SuggestionList suggestions, int n, String query) {
+ // build an array that is max n in size.
+
+ LinkedList ret = new LinkedList();
+ suggestions.filter(ret, new SuggestionList.SuggestionFilter() {
+
+ public boolean accept(Suggestion suggestion) {
+ return suggestion.getScore() > getSuggestionSupressionThreadshold();
+ }
+ });
+
+
+ if (ret.size() > 1) {
+
+ // if the top scoring suggestion is same as the query
+ if (query.equals(ret.get(0).getSuggested())) {
+
+ // switch top two suggestions
+ Suggestion s = ret.get(0);
+ ret.set(0, ret.get(1));
+ ret.set(1, s);
+
+ // if any other suggestion has many more hits
+ // then set that as top suggestion.
+
+ EditDistance ed = editDistanceFactory(ret.get(0).getSuggested());
+ List topHits = new LinkedList();
+ if (ret.size() > 2) {
+ for (int i = 2; i < ret.size(); i++) {
+ if (ret.get(i).getCorpusQueryResults() > ret.get(0).getCorpusQueryResults()
+ && ed.getNormalizedDistance(ret.get(i).getSuggested()) > 0.8d /* todo setting */) {
+ topHits.add(ret.get(i));
+ }
+ }
+ }
+ if (topHits.size() > 0) {
+
+ if (topHits.size() > 1) {
+ Collections.sort(topHits, new Comparator() {
+ public int compare(Suggestion suggestion, Suggestion suggestion1) {
+ return new Integer(suggestion.getCorpusQueryResults()).compareTo(suggestion1.getCorpusQueryResults());
+ }
+ });
+ }
+ ret.remove(topHits.get(0));
+ ret.addFirst(topHits.get(0));
+ }
+ }
+// else {
+// // order by number of hits
+// Arrays.sort(ret, new Comparator() {
+// public int compare(Suggestion suggestion, Suggestion suggestion1) {
+// return new Integer(suggestion1.getCorpusQueryResults().size()).compareTo(suggestion.getCorpusQueryResults().size());
+// }
+// });
+// }
+ }
+ return ret.toArray(new Suggestion[n < ret.size() ? n : ret.size()]);
+ }
+
+
+ public double getSuggestionSupressionThreadshold
+ () {
+ return suggestionSupressionThreadshold;
+ }
+
+ public void setSuggestionSupressionThreadshold
+ (
+ double suggestionSupressionThreadshold) {
+ this.suggestionSupressionThreadshold = suggestionSupressionThreadshold;
+ }
+}
Index: contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/impl/DefaultAprioriCorpusFactory.java
===================================================================
--- contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/impl/DefaultAprioriCorpusFactory.java (revision 0)
+++ contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/impl/DefaultAprioriCorpusFactory.java (revision 0)
@@ -0,0 +1,65 @@
+package org.apache.lucene.search.didyoumean.impl;
+
+import com.sleepycat.je.DatabaseException;
+import org.apache.lucene.analysis.Analyzer;
+import org.apache.lucene.document.Document;
+import org.apache.lucene.document.Field;
+import org.apache.lucene.index.facade.IndexFacade;
+import org.apache.lucene.index.facade.IndexWriterFacade;
+import org.apache.lucene.search.didyoumean.AprioriCorpusFactory;
+import org.apache.lucene.search.didyoumean.Suggester;
+import org.apache.lucene.search.didyoumean.dictionary.Dictionary;
+import org.apache.lucene.search.didyoumean.dictionary.SuggestionList;
+
+import java.io.IOException;
+import java.util.*;
+/*
+ * Licensed 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.
+ *
+ */
+
+
+/**
+ * @author karl wettin
+ * Date: 2007-okt-19
+ * Time: 02:13:00
+ */
+public class DefaultAprioriCorpusFactory implements AprioriCorpusFactory {
+
+ public void factory(Dictionary dictionary, Suggester suggester, IndexFacade aprioriIndex, String aprioriIndexField, Analyzer aprioriAnalyzer) throws IOException, DatabaseException {
+ // create an a priori index based on the inverted dictionary
+
+ System.out.println("Inverting index...");
+ Map inverted = dictionary.inverted();
+
+ IndexWriterFacade aprioriWriter = aprioriIndex.indexWriterFactory(aprioriAnalyzer, true);
+
+// int i=0;
+// int i2=0;
+ System.out.println("Extracting most commonly misspelled words and phrases...");
+ for (Map.Entry e : inverted.entrySet()) {
+ if (e.getValue().size() > 1) {
+ String suggested = suggester.didYouMean(dictionary, e.getKey());
+ if (suggested != null && suggested.equalsIgnoreCase(e.getKey())) {
+ Document d = new Document();
+ d.add(new Field(aprioriIndexField, e.getKey(), Field.Store.NO, Field.Index.TOKENIZED, Field.TermVector.WITH_POSITIONS));
+ aprioriWriter.addDocument(d);
+// i2++;
+// System.out.println(i + "\t" + i2);
+ }
+ }
+// i++;
+ }
+ aprioriWriter.close();
+ }
+}
Index: contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/secondlevel/token/SecondLevelTokenPhraseSuggester.java
===================================================================
--- contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/secondlevel/token/SecondLevelTokenPhraseSuggester.java (revision 0)
+++ contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/secondlevel/token/SecondLevelTokenPhraseSuggester.java (revision 0)
@@ -0,0 +1,49 @@
+package org.apache.lucene.search.didyoumean.secondlevel.token;
+
+/*
+ * Licensed 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.analysis.Analyzer;
+import org.apache.lucene.index.facade.IndexFacade;
+import org.apache.lucene.search.didyoumean.SecondLevelSuggester;
+import org.apache.lucene.search.didyoumean.SuggestionPriorityQueue;
+
+import java.io.IOException;
+
+/**
+ * Makes TokenPhraseSuggesterImpl a SecondLevelSuggester.
+ *
+ * todo: this is an ugly class. decoration?
+ *
+ * @author Karl Wettin
+ * Date: 2007-feb-17
+ * Time: 08:03:01
+ */
+public class SecondLevelTokenPhraseSuggester extends TokenPhraseSuggesterImpl implements SecondLevelSuggester {
+
+ public SecondLevelTokenPhraseSuggester(TokenSuggester tokenSuggester, String aprioriIndexField, boolean defaultSuggestMorePopularTokensOnly, int defaultMaxSuggestionsPerToken, Analyzer phraseAnalyzer, IndexFacade aprioriIndex) throws IOException {
+ super(tokenSuggester, aprioriIndexField, defaultSuggestMorePopularTokensOnly, defaultMaxSuggestionsPerToken, phraseAnalyzer, aprioriIndex);
+ }
+
+ public SuggestionPriorityQueue suggest(String query) {
+ return suggest(query, 1);
+ }
+
+
+ public boolean hasPersistableSuggestions() {
+ return true;
+ }
+}
Index: contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/secondlevel/token/MultiTokenSuggester.java
===================================================================
--- contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/secondlevel/token/MultiTokenSuggester.java (revision 0)
+++ contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/secondlevel/token/MultiTokenSuggester.java (revision 0)
@@ -0,0 +1,93 @@
+package org.apache.lucene.search.didyoumean.secondlevel.token;
+
+import org.apache.lucene.analysis.Analyzer;
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.index.Term;
+import org.apache.lucene.index.facade.IndexFacade;
+import org.apache.lucene.search.*;
+import org.apache.lucene.search.didyoumean.SecondLevelSuggester;
+import org.apache.lucene.search.didyoumean.Suggestion;
+import org.apache.lucene.search.didyoumean.SuggestionPriorityQueue;
+
+import java.io.IOException;
+/*
+ * Licensed 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.
+ *
+ */
+
+
+/**
+ * Uses term queries rather than span near queries.
+ *
+ * @author karl wettin
+ * Date: 2007-okt-23
+ * Time: 04:33:29
+ */
+public class MultiTokenSuggester extends TokenPhraseSuggester implements SecondLevelSuggester {
+
+ private IndexFacade aprioriIndex;
+ private IndexReader aprioriReader;
+ private IndexSearcher aprioriSearcher;
+
+
+ protected boolean isUpdateSuggestionsOrder() {
+ return false;
+ }
+
+ public boolean hasPersistableSuggestions() {
+ return false;
+ }
+
+
+ /**
+ *
+ * @param tokenSuggester
+ * @param aprioriIndexField
+ * @param defaultSuggestMorePopularTokensOnly it makes sense setting this to true
+ * @param defaultMaxSuggestionsPerToken
+ * @param queryAnalyzer
+ * @param aprioriIndex
+ * @throws IOException
+ */
+ public MultiTokenSuggester(TokenSuggester tokenSuggester, String aprioriIndexField, boolean defaultSuggestMorePopularTokensOnly, int defaultMaxSuggestionsPerToken, Analyzer queryAnalyzer, IndexFacade aprioriIndex) throws IOException {
+ super(tokenSuggester, aprioriIndexField, defaultSuggestMorePopularTokensOnly, defaultMaxSuggestionsPerToken, queryAnalyzer);
+ this.aprioriIndex = aprioriIndex;
+ this.aprioriReader = aprioriIndex.indexReaderFactory();
+ this.aprioriSearcher = new IndexSearcher(aprioriReader);
+ }
+
+ public SuggestionPriorityQueue suggest(String query) {
+ return suggest(query, 1);
+ }
+
+ protected Query suggestionAprioriQueryFactory(Suggestion[] suggestions) {
+ BooleanQuery bq = new BooleanQuery();
+ for (Suggestion suggestion : suggestions) {
+ bq.add(new TermQuery(new Term(getAprioriIndexField(), suggestion.getSuggested())), BooleanClause.Occur.MUST);
+ }
+ return bq;
+ }
+
+ public IndexFacade getAprioriIndex() {
+ return aprioriIndex;
+ }
+
+ protected IndexReader getAprioriReader() {
+ return aprioriReader;
+ }
+
+ protected IndexSearcher getAprioriSearcher() {
+ return aprioriSearcher;
+ }
+
+}
Index: contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/secondlevel/token/ngram/TermEnumIterator.java
===================================================================
--- contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/secondlevel/token/ngram/TermEnumIterator.java (revision 0)
+++ contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/secondlevel/token/ngram/TermEnumIterator.java (revision 0)
@@ -0,0 +1,85 @@
+package org.apache.lucene.search.didyoumean.secondlevel.token.ngram;
+/*
+ * Licensed 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.index.IndexReader;
+import org.apache.lucene.index.Term;
+import org.apache.lucene.index.TermEnum;
+
+import java.io.IOException;
+import java.util.Iterator;
+
+/**
+ * @author Nicolas Maisonneuve
+ * @author Karl Wettin
+ * Date: 2007-feb-03
+ * Time: 06:40:59
+ */
+public class TermEnumIterator implements Iterator {
+
+ private String field;
+
+ private TermEnum termEnum;
+ private Term actualTerm;
+ private boolean hasNextCalled;
+
+ public TermEnumIterator(IndexReader reader, String field) {
+ this.field = field.intern();
+ try {
+ termEnum = reader.terms(new Term(field, ""));
+ } catch (IOException e) {
+ e.printStackTrace();
+ }
+ }
+
+ public String next() {
+ if (!hasNextCalled) {
+ hasNext();
+ }
+ hasNextCalled = false;
+ return (actualTerm != null) ? actualTerm.text() : null;
+ }
+
+ public boolean hasNext() {
+ if (hasNextCalled) {
+ return actualTerm != null;
+ }
+ hasNextCalled = true;
+ try {
+ // if there are no more words
+ if (!termEnum.next()) {
+ actualTerm = null;
+ return false;
+ }
+ // if the next word is in the field
+ actualTerm = termEnum.term();
+ String currentField = actualTerm.field();
+ if (currentField != field) {
+ actualTerm = null;
+ return false;
+ }
+ return true;
+ } catch (IOException e) {
+ e.printStackTrace();
+ return false;
+ }
+ }
+
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+
+}
Index: contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/secondlevel/token/ngram/NgramTokenSuggester.java
===================================================================
--- contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/secondlevel/token/ngram/NgramTokenSuggester.java (revision 0)
+++ contrib/didyoumean/src/java/org/apache/lucene/search/didyoumean/secondlevel/token/ngram/NgramTokenSuggester.java (revision 0)
@@ -0,0 +1,372 @@
+package org.apache.lucene.search.didyoumean.secondlevel.token.ngram;
+/*
+ * Licensed 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.analysis.standard.StandardAnalyzer;
+import org.apache.lucene.document.Document;
+import org.apache.lucene.document.Field;
+import org.apache.lucene.index.facade.IndexFacade;
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.index.facade.IndexWriterFacade;
+import org.apache.lucene.index.Term;
+import org.apache.lucene.search.*;
+import org.apache.lucene.search.didyoumean.EditDistance;
+import org.apache.lucene.search.didyoumean.Levenshtein;
+import org.apache.lucene.search.didyoumean.Suggestion;
+import org.apache.lucene.search.didyoumean.SuggestionPriorityQueue;
+import org.apache.lucene.search.didyoumean.secondlevel.token.TokenSuggester;
+import org.apache.lucene.search.didyoumean.secondlevel.token.TokenSuggestion;
+
+import java.io.IOException;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Set;
+
+/**
+ * A single token word suggester based on n-grams.
+ *