Changeset 129

Timestamp:

07/20/11 11:13:50 (13 years ago)

Author:

sherbold

Message:

• renamed de.ugoe.cs.eventbench.models.IStochasticProcess.getNumStates() to getNumSymbols()
• renamed de.ugoe.cs.eventbench.models.IStochasticProcess.getStateStrings() to getSymbolStrings()

+ added de.ugoe.cs.eventbench.models.IStochasticProcess.getNumFOMStates(); this function returns the number states an equivalent first-order Markov model would have
+ added methods that count the ancestors of trie leaves, which is in turn used to determine the FOM-equivalent

Location:

trunk/EventBenchCore/src/de/ugoe/cs/eventbench

Files:

• coverage/SequenceTools.java (modified) (1 diff)
• models/IStochasticProcess.java (modified) (2 diffs)
• models/Trie.java (modified) (2 diffs)
• models/TrieBasedModel.java (modified) (3 diffs)
• models/TrieNode.java (modified) (2 diffs)

trunk/EventBenchCore/src/de/ugoe/cs/eventbench/coverage/SequenceTools.java

@@ -69 +69 @@
          */
         public static long numSequences(IStochasticProcess process, int length) {
-                return (long) Math.pow(process.getNumStates(), length);
+                return (long) Math.pow(process.getNumSymbols(), length);
         }
 

trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/IStochasticProcess.java

@@ -107 +107 @@
          * @return number of states
          */
-        public int getNumStates();
+        public int getNumSymbols();
 
         /**
@@ -116 +116 @@
          * @return string representation for all known states
          */
-        public String[] getStateStrings();
+        public String[] getSymbolStrings();
+        
+        /**
+         * <p>
+         * Returns the number of states the process would have if it would be flattened through state-splitting to a first-order Markov model.
+         * </p>
+         * <p>
+         * If it is not possible to flatten the model, -1 is returned.
+         * </p>
+         * 
+         * @return number of states an equivalent FOM would have; -1 is not available
+         */
+        public int getNumFOMStates();
 
         /**

trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/Trie.java

@@ -3 +3 @@
 import java.io.Serializable;
 import java.util.Collection;
+import java.util.HashSet;
 import java.util.LinkedHashSet;
 import java.util.LinkedList;
 import java.util.List;
+import java.util.Set;
 
 import de.ugoe.cs.util.StringTools;
@@ -364 +366 @@
          * </p>
          * 
-         * @return
+         * @return number of symbols contained in the trie
          */
         public int getNumSymbols() {
                 return knownSymbols.size();
         }
+
+        /**
+         * <p>
+         * Returns the number of trie nodes that are ancestors of a leaf. This is
+         * the equivalent to the number of states a first-order markov model would
+         * have.
+         * <p>
+         * 
+         * @return number of trie nodes that are ancestors of leafs.
+         */
+        public int getNumLeafAncestors() {
+                Set<TrieNode<T>> ancestors = new HashSet<TrieNode<T>>();
+                rootNode.getLeafAncestors(ancestors);
+                return ancestors.size();
+        }
 }

trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/TrieBasedModel.java

@@ -179 +179 @@
          */
         @Override
-        public int getNumStates() {
+        public int getNumSymbols() {
                 return trie.getNumSymbols();
         }
@@ -189 +189 @@
          */
         @Override
-        public String[] getStateStrings() {
-                String[] stateStrings = new String[getNumStates()];
+        public String[] getSymbolStrings() {
+                String[] stateStrings = new String[getNumSymbols()];
                 int i = 0;
                 for (Event<?> symbol : trie.getKnownSymbols()) {
@@ -309 +309 @@
         }
 
+        /* (non-Javadoc)
+         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getNumFOMStates()
+         */
+        @Override
+        public int getNumFOMStates() {
+                return trie.getNumLeafAncestors();
+        }
 }

trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/TrieNode.java

@@ -6 +6 @@
 import java.util.LinkedList;
 import java.util.List;
+import java.util.Set;
 
 import de.ugoe.cs.eventbench.models.Trie.Edge;
@@ -286 +287 @@
                 }
         }
+
+        /**
+         * <p>
+         * Checks if the node is a leaf.
+         * </p>
+         * 
+         * @return true if the node is a leaf, false otherwise.
+         */
+        protected boolean isLeaf() {
+                return children.isEmpty();
+        }
+
+        /**
+         * <p>
+         * Recursive methods that collects all nodes that are ancestors of leafs and
+         * stores them in the set.
+         * </p>
+         * 
+         * @param ancestors
+         *            set of all ancestors of leafs
+         */
+        protected void getLeafAncestors(Set<TrieNode<T>> ancestors) {
+                boolean isAncestor = false;
+                for (TrieNode<T> child : children) {
+                        child.getLeafAncestors(ancestors);
+                        isAncestor |= child.isLeaf();
+                }
+                if (isAncestor) {
+                        ancestors.add(this);
+                }
+        }
 }