+ * This interface can be used for implementing comparison strategies for symbols.
+ *
+ *
+ * @author Patrick Harms
+ */
+public interface SymbolComparator {
+
+ /**
+ *
+ * compares two symbols and returns true, if the concrete comparison strategy sees both
+ * symbols as equal. The method must be commutative, i.e.,
+ * equals(symbol1, symbol2) == equals(symbol2, symbol1).
+ *
+ *
+ * @param symbol1 the first symbol to be compared
+ * @param symbol2 the second symbol to be compared
+ *
+ * @return true if the comparison strategy sees both symbols as equal, false else.
+ */
+ public boolean equals(T symbol1, T symbol2);
+}
Index: trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/Trie.java
===================================================================
--- trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/Trie.java (revision 927)
+++ trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/Trie.java (revision 1060)
@@ -34,5 +34,5 @@
*
*
- * @author Steffen Herbold
+ * @author Steffen Herbold, Patrick Harms
*
* @param
@@ -66,9 +66,26 @@
/**
*
- * Contructor. Creates a new Trie.
+ * Comparator to be used for comparing the symbols with each other
+ *
+ */
+ private SymbolComparator comparator;
+
+ /**
+ *
+ * Contructor. Creates a new Trie with a {@link DefaultSymbolComparator}.
*
*/
public Trie() {
- rootNode = new TrieNode();
+ this(new DefaultSymbolComparator());
+ }
+
+ /**
+ *
+ * Contructor. Creates a new Trie with that uses a specific {@link SymbolComparator}.
+ *
+ */
+ public Trie(SymbolComparator comparator) {
+ this.comparator = comparator;
+ rootNode = new TrieNode(comparator);
knownSymbols = new LinkedHashSet();
}
@@ -76,5 +93,5 @@
/**
*
- * Copy-Constructor. Creates a new Trie as the copy of other. The other trie must noch be null.
+ * Copy-Constructor. Creates a new Trie as the copy of other. The other trie must not be null.
*
*
@@ -88,4 +105,5 @@
rootNode = new TrieNode(other.rootNode);
knownSymbols = new LinkedHashSet(other.knownSymbols);
+ comparator = other.comparator;
}
@@ -120,5 +138,5 @@
for (T currentEvent : sequence) {
latestActions.add(currentEvent);
- knownSymbols.add(currentEvent);
+ addToKnownSymbols(currentEvent);
i++;
if (i >= maxOrder) {
@@ -143,5 +161,5 @@
protected void add(List subsequence) {
if (subsequence != null && !subsequence.isEmpty()) {
- knownSymbols.addAll(subsequence);
+ addToKnownSymbols(subsequence);
subsequence = new LinkedList(subsequence); // defensive copy!
T firstSymbol = subsequence.get(0);
@@ -306,4 +324,133 @@
/**
*
+ * returns a list of symbol sequences which have a minimal length and that occurred most often
+ * with the same number of occurrences. The resulting list is empty, if there is no symbol
+ * sequence with the minimal length.
+ *
+ *
+ * @param minimalLength the minimal length of the returned sequences
+ *
+ * @return as described
+ */
+ public Collection> getSequencesWithMostOccurrences(int minimalLength) {
+ LinkedList> context = new LinkedList>();
+ Collection>> paths = new LinkedList>>();
+
+ context.push(rootNode);
+
+ // traverse the trie and determine all sequences, which have the maximum number of
+ // occurrences and a minimal length.
+
+ // minimalLength + 1 because we denote the depth including the root node
+ determineLongPathsWithMostOccurrences(minimalLength + 1, paths, context);
+
+ Collection> resultingPaths = new LinkedList>();
+ List resultingPath;
+
+ if (paths.size() > 0) {
+
+ for (List> path : paths) {
+ resultingPath = new LinkedList();
+
+ for (TrieNode node : path) {
+ if (node.getSymbol() != null) {
+ resultingPath.add(node.getSymbol());
+ }
+ }
+
+ resultingPaths.add(resultingPath);
+ }
+ }
+
+ return resultingPaths;
+ }
+
+ /**
+ *
+ * Traverses the trie to collect all sequences with a maximum number of occurrences and with
+ * a minimal length. The length is encoded in the provided recursion depth.
+ *
+ *
+ * @param minimalDepth the minimal recursion depth to be done
+ * @param paths the paths through the trie that all occurred with the same amount and
+ * that have the so far found maximum of occurrences (is updated each
+ * time a further path with the same number of occurrences is found; is
+ * replaced if a path with more occurrences is found)
+ * @param context the path through the trie, that is analyzed by the recursive call
+ */
+ private void determineLongPathsWithMostOccurrences(int minimalDepth,
+ Collection>> paths,
+ LinkedList> context)
+ {
+ int maxCount = 0;
+
+ // only if we already reached the depth to be achieved, we check if the paths have the
+ // maximum number of occurrences
+ if (context.size() >= minimalDepth) {
+
+ // try to determine the maximum number of occurrences so far, if any
+ if (paths.size() > 0) {
+ List> path = paths.iterator().next();
+ maxCount = path.get(path.size() - 1).getCount();
+ }
+
+ // if the current path has a higher number of occurrences than all so far, clear
+ // the paths collected so far and set the new number of occurrences as new maximum
+ if (context.getLast().getCount() > maxCount) {
+ paths.clear();
+ maxCount = context.getLast().getCount();
+ }
+
+ // if the path matches the current maximal number of occurrences, add it to the list
+ // of collected paths with these number of occurrences
+ if (context.getLast().getCount() == maxCount) {
+ paths.add(new LinkedList>(context));
+ }
+ }
+
+ // perform the trie traversal
+ for (TrieNode child : context.getLast().getChildren()) {
+ if (child.getCount() >= maxCount) {
+ context.add(child);
+ determineLongPathsWithMostOccurrences(minimalDepth, paths, context);
+ context.removeLast();
+ }
+ }
+ }
+
+ /**
+ *
+ * adds a new symbol to the collection of known symbols if this symbol is not already
+ * contained. The symbols are compared using the comparator.
+ *
+ *
+ * @param symbol the symbol to be added to the known symbols
+ */
+ private void addToKnownSymbols(T symbol) {
+ for (T knownSymbol : knownSymbols) {
+ if (comparator.equals(knownSymbol, symbol)) {
+ return;
+ }
+ }
+
+ knownSymbols.add(symbol);
+ }
+
+ /**
+ *
+ * adds a list of new symbols to the collection of known symbols. Uses the
+ * {@link #addToKnownSymbols(Object)} method for each element of the provided list.
+ *
+ *
+ * @param symbols the list of symbols to be added to the known symbols
+ */
+ private void addToKnownSymbols(List symbols) {
+ for (T symbol : symbols) {
+ addToKnownSymbols(symbol);
+ }
+ }
+
+ /**
+ *
* Helper class for graph visualization of a trie.
*
@@ -441,5 +588,5 @@
knownSymbols = new HashSet();
for (TrieNode node : rootNode.getChildren()) {
- knownSymbols.add(node.getSymbol());
+ addToKnownSymbols(node.getSymbol());
}
}
@@ -478,3 +625,4 @@
return hash;
}
+
}
Index: trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/TrieNode.java
===================================================================
--- trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/TrieNode.java (revision 927)
+++ trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/TrieNode.java (revision 1060)
@@ -33,5 +33,5 @@
*
*
- * @author Steffen Herbold
+ * @author Steffen Herbold, Patrick Harms
*
* @param
@@ -71,9 +71,46 @@
/**
*
+ * Comparator to be used for comparing the symbols with each other
+ *
+ */
+ private SymbolComparator comparator;
+
+ /**
+ *
* Constructor. Creates a new TrieNode without a symbol associated.
* This constructor should only be used to create the root node of the trie!
+ * The comparator used by the tree node will be a {@link DefaultSymbolComparator}.
*
*/
TrieNode() {
+ this(new DefaultSymbolComparator());
+ }
+
+ /**
+ *
+ * Constructor. Creates a new TrieNode. The symbol must not be null.
+ * The comparator used by the tree node will be a {@link DefaultSymbolComparator}.
+ *
+ *
+ * @param symbol
+ * symbol associated with the trie node
+ */
+ TrieNode(T symbol) {
+ this(symbol, new DefaultSymbolComparator());
+ }
+
+ /**
+ *
+ * Constructor. Creates a new TrieNode without a symbol associated using the provided
+ * comparator.
+ * This constructor should only be used to create the root node of the trie!
+ *
The comparator must not be null.
+ *
+ */
+ TrieNode(SymbolComparator comparator) {
+ if (comparator == null) {
+ throw new IllegalArgumentException("comparator must not be null!");
+ }
+ this.comparator = comparator;
this.symbol = null;
count = 0;
@@ -83,5 +120,6 @@
/**
*
- * Constructor. Creates a new TrieNode. The symbol must not be null.
+ * Constructor. Creates a new TrieNode using the provided comparator. The symbol and the
+ * comparator must not be null.
*
*
@@ -89,10 +127,16 @@
* symbol associated with the trie node
*/
- TrieNode(T symbol) {
+ TrieNode(T symbol, SymbolComparator comparator) {
if (symbol == null) {
- throw new IllegalArgumentException(
- "symbol must not be null. null is reserved for root node!");
+ throw new IllegalArgumentException
+ ("symbol must not be null. null is reserved for root node!");
}
this.symbol = symbol;
+
+ if (comparator == null) {
+ throw new IllegalArgumentException("comparator must not be null!");
+ }
+ this.comparator = comparator;
+
count = 0;
children = new LinkedList>();
@@ -112,4 +156,5 @@
symbol = other.symbol;
count = other.count;
+ comparator = other.comparator;
children = new LinkedList>();
for (TrieNode child : other.children) {
@@ -129,7 +174,6 @@
public void add(List subsequence) {
if (!subsequence.isEmpty()) {
- if (!symbol.equals(subsequence.get(0))) { // should be guaranteed by
- // the
- // recursion/TrieRoot!
+ if (!comparator.equals(symbol, subsequence.get(0))) { // should be guaranteed by
+ // the recursion/TrieRoot!
throw new AssertionError("Invalid trie operation!");
}
@@ -179,5 +223,5 @@
TrieNode node = getChild(symbol);
if (node == null) {
- node = new TrieNode(symbol);
+ node = new TrieNode(symbol, comparator);
children.add(node);
}
@@ -197,5 +241,5 @@
protected TrieNode getChild(T symbol) {
for (TrieNode child : children) {
- if (child.getSymbol().equals(symbol)) {
+ if (comparator.equals(child.getSymbol(), symbol)) {
return child;
}
@@ -267,5 +311,13 @@
@Override
public String toString() {
- String str = symbol.toString() + " #" + count;
+ String str;
+
+ if (symbol == null) {
+ str = "ROOT";
+ }
+ else {
+ str = symbol.toString() + " #" + count;
+ }
+
if (!children.isEmpty()) {
str += StringTools.ENDLINE + children.toString();
@@ -276,5 +328,5 @@
/**
*
- * Generates a {@link Tree} represenation of the trie.
+ * Generates a {@link Tree} representation of the trie.
*
*
@@ -409,10 +461,10 @@
*
* Two TrieNodes are defined as equal, if their {@link #count}, {@link #symbol}, and
- * {@link #children} are equal.
+ * {@link #children} are equal. For the comparison of their symbols the comparator is used.
*
*
* @see java.lang.Object#equals(java.lang.Object)
*/
- @SuppressWarnings("rawtypes")
+ @SuppressWarnings({ "rawtypes", "unchecked" })
@Override
public boolean equals(Object other) {
@@ -427,5 +479,7 @@
}
else {
- return count == otherNode.count && symbol.equals(((TrieNode) other).symbol) &&
+ return count == otherNode.count &&
+ symbol.getClass().isInstance(((TrieNode) other).symbol) &&
+ comparator.equals(symbol, ((TrieNode) other).symbol) &&
children.equals(((TrieNode) other).children);
}