Index: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/markov/HighOrderMarkovModel.java =================================================================== --- trunk/EventBenchCore/src/de/ugoe/cs/eventbench/markov/HighOrderMarkovModel.java (revision 12) +++ (revision ) @@ -1,37 +1,0 @@ -package de.ugoe.cs.eventbench.markov; - -import java.util.LinkedList; -import java.util.List; -import java.util.Random; - -import de.ugoe.cs.eventbench.data.Event; -import de.ugoe.cs.eventbench.ppm.TrieBasedModel; - -public class HighOrderMarkovModel extends TrieBasedModel { - - public HighOrderMarkovModel(int maxOrder, Random r) { - super(maxOrder, r); - } - - @Override - protected double getProbability(List> context, Event symbol) { - double result = 0.0d; - - List> contextCopy = new LinkedList>(context); - - - List> followers = trie.getFollowingSymbols(contextCopy); - int sumCountFollowers = 0; // N(s\sigma') - for( Event follower : followers ) { - sumCountFollowers += trie.getCount(contextCopy, follower); - } - - int countSymbol = trie.getCount(contextCopy, symbol); - if( sumCountFollowers!=0 ) { - result = ((double) countSymbol / sumCountFollowers); - } - - return result; - } - -} Index: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/HighOrderMarkovModel.java =================================================================== --- trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/HighOrderMarkovModel.java (revision 13) +++ trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/HighOrderMarkovModel.java (revision 13) @@ -0,0 +1,36 @@ +package de.ugoe.cs.eventbench.models; + +import java.util.LinkedList; +import java.util.List; +import java.util.Random; + +import de.ugoe.cs.eventbench.data.Event; + +public class HighOrderMarkovModel extends TrieBasedModel { + + public HighOrderMarkovModel(int maxOrder, Random r) { + super(maxOrder, r); + } + + @Override + protected double getProbability(List> context, Event symbol) { + double result = 0.0d; + + List> contextCopy = new LinkedList>(context); + + + List> followers = trie.getFollowingSymbols(contextCopy); + int sumCountFollowers = 0; // N(s\sigma') + for( Event follower : followers ) { + sumCountFollowers += trie.getCount(contextCopy, follower); + } + + int countSymbol = trie.getCount(contextCopy, symbol); + if( sumCountFollowers!=0 ) { + result = ((double) countSymbol / sumCountFollowers); + } + + return result; + } + +} Index: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/PredictionByPartialMatch.java =================================================================== --- trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/PredictionByPartialMatch.java (revision 13) +++ trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/PredictionByPartialMatch.java (revision 13) @@ -0,0 +1,132 @@ +package de.ugoe.cs.eventbench.models; + +import java.util.ArrayList; +import java.util.LinkedList; +import java.util.List; +import java.util.Random; + +import de.ugoe.cs.eventbench.data.Event; +import de.ugoe.cs.util.console.Console; + +public class PredictionByPartialMatch extends TrieBasedModel { + + double probEscape; + + public PredictionByPartialMatch(int maxOrder, Random r) { + this(maxOrder, r, 0.1); + } + + public PredictionByPartialMatch(int maxOrder, Random r, double probEscape) { + super(maxOrder, r); + this.probEscape = probEscape; + } + + public void setProbEscape(double probEscape) { + this.probEscape = probEscape; + } + + public double getProbEscape() { + return probEscape; + } + + @Override + protected double getProbability(List> context, Event symbol) { + double result = 0.0d; + double resultCurrentContex = 0.0d; + double resultShorterContex = 0.0d; + + List> contextCopy = new LinkedList>(context); // defensive copy + + + List> followers = trie.getFollowingSymbols(contextCopy); // \Sigma' + int sumCountFollowers = 0; // N(s\sigma') + for( Event follower : followers ) { + sumCountFollowers += trie.getCount(contextCopy, follower); + } + + int countSymbol = trie.getCount(contextCopy, symbol); // N(s\sigma) + if( contextCopy.size()==0 ) { + resultCurrentContex = ((double) countSymbol) / sumCountFollowers; + } else { + resultCurrentContex = ((double) countSymbol / sumCountFollowers)*(1-probEscape); + contextCopy.remove(0); + double probSuffix = getProbability(contextCopy, symbol); + if( followers.size()==0 ) { + resultShorterContex = probSuffix; + } else { + resultShorterContex = probEscape*probSuffix; + } + } + result = resultCurrentContex+resultShorterContex; + + return result; + } + + public void testStuff() { + // basically an inline unit test without assertions but manual observation + List> list = new ArrayList>(); + list.add(new Event("a")); + list.add(new Event("b")); + list.add(new Event("r")); + list.add(new Event("a")); + list.add(new Event("c")); + list.add(new Event("a")); + list.add(new Event("d")); + list.add(new Event("a")); + list.add(new Event("b")); + list.add(new Event("r")); + list.add(new Event("a")); + + int maxOrder = 3; + PredictionByPartialMatch model = new PredictionByPartialMatch(maxOrder, new Random()); + model.trie = new Trie>(); + model.trie.train(list, maxOrder); + model.trie.display(); + + List> context = new ArrayList>(); + Event symbol = new Event("a"); + // expected: 5 + Console.traceln(""+model.trie.getCount(context, symbol)); + + // expected: 0 + context.add(new Event("b")); + Console.traceln(""+model.trie.getCount(context, symbol)); + + // expected: 2 + context.add(new Event("r")); + Console.traceln(""+model.trie.getCount(context, symbol)); + + // exptected: [b, r] + context = new ArrayList>(); + context.add(new Event("a")); + context.add(new Event("b")); + context.add(new Event("r")); + Console.traceln(model.trie.getContextSuffix(context).toString()); + + // exptected: [] + context = new ArrayList>(); + context.add(new Event("e")); + Console.traceln(model.trie.getContextSuffix(context).toString()); + + // exptected: {a, b, c, d, r} + context = new ArrayList>(); + Console.traceln(model.trie.getFollowingSymbols(context).toString()); + + // exptected: {b, c, d} + context = new ArrayList>(); + context.add(new Event("a")); + Console.traceln(model.trie.getFollowingSymbols(context).toString()); + + // exptected: [] + context = new ArrayList>(); + context.add(new Event("a")); + context.add(new Event("b")); + context.add(new Event("r")); + Console.traceln(model.trie.getFollowingSymbols(context).toString()); + + // exptected: 0.0d + context = new ArrayList>(); + context.add(new Event("a")); + Console.traceln(""+model.getProbability(context, new Event("z"))); + } +} Index: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/Trie.java =================================================================== --- trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/Trie.java (revision 13) +++ trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/Trie.java (revision 13) @@ -0,0 +1,196 @@ +package de.ugoe.cs.eventbench.models; + +import java.awt.Dimension; +import java.awt.Rectangle; +import java.awt.Shape; +import java.util.LinkedHashSet; +import java.util.LinkedList; +import java.util.List; +import java.util.Set; + +import javax.swing.JFrame; + +import org.apache.commons.collections15.Transformer; + +import de.ugoe.cs.eventbench.markov.IncompleteMemory; + +import edu.uci.ics.jung.algorithms.layout.Layout; +import edu.uci.ics.jung.algorithms.layout.TreeLayout; +import edu.uci.ics.jung.graph.DelegateTree; +import edu.uci.ics.jung.graph.Tree; +import edu.uci.ics.jung.visualization.BasicVisualizationServer; +import edu.uci.ics.jung.visualization.decorators.ToStringLabeller; +import edu.uci.ics.jung.visualization.renderers.Renderer.VertexLabel.Position; + +public class Trie { + + private Set knownSymbols; + + private final TrieNode rootNode; + + public Trie() { + rootNode = new TrieNode(); + knownSymbols = new LinkedHashSet(); + } + + public Set getKnownSymbols() { + return new LinkedHashSet(knownSymbols); + } + + // trains the current Trie using the given sequence and adds all subsequence of length maxOrder + public void train(List sequence, int maxOrder) { + IncompleteMemory latestActions = new IncompleteMemory(maxOrder); + int i=0; + for(T currentEvent : sequence) { + latestActions.add(currentEvent); + knownSymbols.add(currentEvent); + i++; + if( i>=maxOrder ) { + add(latestActions.getLast(maxOrder)); + } + } + int sequenceLength = sequence.size(); + for( int j=maxOrder-1 ; j>0 ; j-- ) { + add(sequence.subList(sequenceLength-j, sequenceLength)); + } + } + + + // increases the counters for each symbol in the subsequence + public void add(List subsequence) { + if( subsequence!=null && !subsequence.isEmpty() ) { + knownSymbols.addAll(subsequence); + subsequence = new LinkedList(subsequence); // defensive copy! + T firstSymbol = subsequence.get(0); + TrieNode node = getChildCreate(firstSymbol); + node.add(subsequence); + } + } + + protected TrieNode getChildCreate(T symbol) { + return rootNode.getChildCreate(symbol); + } + + protected TrieNode getChild(T symbol) { + return rootNode.getChild(symbol); + } + + // get the count of "sequence" + public int getCount(List sequence) { + int count = 0; + TrieNode node = find(sequence); + if( node!=null ) { + count = node.getCount(); + } + return count; + } + + // get the count of "sequence,follower" + public int getCount(List sequence, T follower) { + List tmpSequence = new LinkedList(sequence); + tmpSequence.add(follower); + return getCount(tmpSequence); + + } + + public TrieNode find(List sequence) { + if( sequence==null || sequence.isEmpty() ) { + return rootNode; + } + List sequenceCopy = new LinkedList(sequence); + TrieNode result = null; + TrieNode node = getChild(sequenceCopy.get(0)); + if( node!=null ) { + sequenceCopy.remove(0); + result = node.find(sequenceCopy); + } + return result; + } + + // returns all symbols that follow the defined sequence + public List getFollowingSymbols(List sequence) { + List result = new LinkedList(); + TrieNode node = find(sequence); + if( node!=null ) { + result = node.getFollowingSymbols(); + } + return result; + } + + // longest suffix of context, that is contained in the tree and whose children are leaves + // possibly already deprecated + public List getContextSuffix(List context) { + List contextSuffix = new LinkedList(context); // defensive copy + boolean suffixFound = false; + + while(!suffixFound) { + if( contextSuffix.isEmpty() ) { + suffixFound = true; // suffix is the empty word + } else { + TrieNode node = find(contextSuffix); + if( node!=null ) { + if( !node.getFollowingSymbols().isEmpty() ) { + suffixFound = true; + } + } + if( !suffixFound ) { + contextSuffix.remove(0); + } + } + } + + return contextSuffix; + } + + + static public class Edge{} + + static public class TrieVertex { + private String id; + protected TrieVertex(String id) { + this.id = id; + } + public String toString() { + return id; + } + } + + private Tree getGraph() { + DelegateTree graph = new DelegateTree(); + rootNode.getGraph(null, graph); + return graph; + } + + public void display() { + Tree graph = this.getGraph(); + Layout layout = new TreeLayout(graph, 60); + // The BasicVisualizationServer is parameterized by the edge types + BasicVisualizationServer vv = + new BasicVisualizationServer(layout); + vv.setPreferredSize(new Dimension(1100,850)); //Sets the viewing area size + + + final Rectangle rect = new Rectangle(40, 20); + + Transformer vertexShapeTransformer = + new Transformer() { + public Shape transform(TrieVertex s) { + return rect; + } + }; + vv.getRenderer().getVertexLabelRenderer().setPosition(Position.CNTR); + vv.getRenderContext().setVertexShapeTransformer(vertexShapeTransformer); + vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller()); + + JFrame frame = new JFrame("Trie"); + frame.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE); + frame.getContentPane().add(vv); + frame.pack(); + frame.setVisible(true); + } + + @Override + public String toString() { + return rootNode.toString(); + } +} Index: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/TrieBasedModel.java =================================================================== --- trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/TrieBasedModel.java (revision 13) +++ trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/TrieBasedModel.java (revision 13) @@ -0,0 +1,74 @@ +package de.ugoe.cs.eventbench.models; + +import java.util.LinkedList; +import java.util.List; +import java.util.Random; + +import de.ugoe.cs.eventbench.data.Event; +import de.ugoe.cs.eventbench.markov.IncompleteMemory; + +public abstract class TrieBasedModel { + + protected int maxOrder; + + protected abstract double getProbability(List> context, Event symbol); + + protected Trie> trie; + protected final Random r; + + + public TrieBasedModel(int maxOrder, Random r) { + super(); + this.maxOrder = maxOrder; + this.r = r; + } + + public void train(List>> sequences) { + trie = new Trie>(); + + for(List> sequence : sequences) { + List> currentSequence = new LinkedList>(sequence); // defensive copy + currentSequence.add(0, Event.STARTEVENT); + currentSequence.add(Event.ENDEVENT); + + trie.train(currentSequence, maxOrder); + } + } + + public List> randomSequence() { + List> sequence = new LinkedList>(); + + IncompleteMemory> context = new IncompleteMemory>(maxOrder-1); + context.add(Event.STARTEVENT); + + Event currentState = Event.STARTEVENT; + + boolean endFound = false; + + while(!endFound) { + double randVal = r.nextDouble(); + double probSum = 0.0; + List> currentContext = context.getLast(maxOrder); + for( Event symbol : trie.getKnownSymbols() ) { + probSum += getProbability(currentContext, symbol); + if( probSum>=randVal ) { + endFound = (symbol==Event.ENDEVENT); + if( !(symbol==Event.STARTEVENT || symbol==Event.ENDEVENT) ) { + // only add the symbol the sequence if it is not START or END + context.add(symbol); + currentState = symbol; + sequence.add(currentState); + } + break; + } + } + } + return sequence; + } + + @Override + public String toString() { + return trie.toString(); + } + +} Index: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/TrieNode.java =================================================================== --- trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/TrieNode.java (revision 13) +++ trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/TrieNode.java (revision 13) @@ -0,0 +1,123 @@ +package de.ugoe.cs.eventbench.models; + +import java.security.InvalidParameterException; +import java.util.LinkedList; +import java.util.List; + +import de.ugoe.cs.eventbench.models.Trie.Edge; +import de.ugoe.cs.eventbench.models.Trie.TrieVertex; +import de.ugoe.cs.util.StringTools; +import edu.uci.ics.jung.graph.DelegateTree; + + +class TrieNode { + + private int count; + private final T symbol; + + private List> children; + + TrieNode() { + this.symbol = null; + count = 0; + children = new LinkedList>(); + } + + public TrieNode(T symbol) { + if( symbol==null ) { + throw new InvalidParameterException("symbol must not be null."); + } + this.symbol = symbol; + count = 0; + children = new LinkedList>(); + } + + public void add(List subsequence) { + if( !subsequence.isEmpty() ) { + if( !symbol.equals(subsequence.get(0)) ) { // should be guaranteed by the recursion/TrieRoot! + throw new AssertionError("Invalid trie operation!"); + } + count++; + subsequence.remove(0); + if( !subsequence.isEmpty() ) { + T nextSymbol = subsequence.get(0); + getChildCreate(nextSymbol).add(subsequence); + } + } + } + + public T getSymbol() { + return symbol; + } + + public int getCount() { + return count; + } + + protected TrieNode getChildCreate(T symbol) { + TrieNode node = getChild(symbol); + if( node==null ) { + node = new TrieNode(symbol); + children.add(node); + } + return node; + } + + protected TrieNode getChild(T symbol) { + for( TrieNode child : children ) { + if( child.getSymbol().equals(symbol) ) { + return child; + } + } + return null; + } + + + + public TrieNode find(List subsequence) { + TrieNode result = null; + if( subsequence.isEmpty() ) { + result = this; + } else { + TrieNode node = getChild(subsequence.get(0)); + if( node!=null ) { + subsequence.remove(0); + result = node.find(subsequence); + } + } + return result; + } + + // returns all symbols that follow this node + public List getFollowingSymbols() { + List followingSymbols = new LinkedList(); + for( TrieNode child : children ) { + followingSymbols.add(child.getSymbol()); + } + return followingSymbols; + } + + @Override + public String toString() { + String str = symbol.toString()+" #"+count; + if( !children.isEmpty() ) { + str += StringTools.ENDLINE + children.toString(); + } + return str; + } + + public void getGraph(TrieVertex parent, DelegateTree graph) { + TrieVertex currentVertex; + if( symbol==null ){ + currentVertex = new TrieVertex("root"); + graph.addVertex(currentVertex); + } else { + currentVertex = new TrieVertex(getSymbol().toString()+"#"+getCount()); + graph.addChild( new Edge() , parent, currentVertex ); + } + for( TrieNode node : children ) { + node.getGraph(currentVertex, graph); + } + } + +} Index: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/PredictionByPartialMatch.java =================================================================== --- trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/PredictionByPartialMatch.java (revision 12) +++ (revision ) @@ -1,132 +1,0 @@ -package de.ugoe.cs.eventbench.ppm; - -import java.util.ArrayList; -import java.util.LinkedList; -import java.util.List; -import java.util.Random; - -import de.ugoe.cs.eventbench.data.Event; -import de.ugoe.cs.util.console.Console; - -public class PredictionByPartialMatch extends TrieBasedModel { - - double probEscape; - - public PredictionByPartialMatch(int maxOrder, Random r) { - this(maxOrder, r, 0.1); - } - - public PredictionByPartialMatch(int maxOrder, Random r, double probEscape) { - super(maxOrder, r); - this.probEscape = probEscape; - } - - public void setProbEscape(double probEscape) { - this.probEscape = probEscape; - } - - public double getProbEscape() { - return probEscape; - } - - @Override - protected double getProbability(List> context, Event symbol) { - double result = 0.0d; - double resultCurrentContex = 0.0d; - double resultShorterContex = 0.0d; - - List> contextCopy = new LinkedList>(context); // defensive copy - - - List> followers = trie.getFollowingSymbols(contextCopy); // \Sigma' - int sumCountFollowers = 0; // N(s\sigma') - for( Event follower : followers ) { - sumCountFollowers += trie.getCount(contextCopy, follower); - } - - int countSymbol = trie.getCount(contextCopy, symbol); // N(s\sigma) - if( contextCopy.size()==0 ) { - resultCurrentContex = ((double) countSymbol) / sumCountFollowers; - } else { - resultCurrentContex = ((double) countSymbol / sumCountFollowers)*(1-probEscape); - contextCopy.remove(0); - double probSuffix = getProbability(contextCopy, symbol); - if( followers.size()==0 ) { - resultShorterContex = probSuffix; - } else { - resultShorterContex = probEscape*probSuffix; - } - } - result = resultCurrentContex+resultShorterContex; - - return result; - } - - public void testStuff() { - // basically an inline unit test without assertions but manual observation - List> list = new ArrayList>(); - list.add(new Event("a")); - list.add(new Event("b")); - list.add(new Event("r")); - list.add(new Event("a")); - list.add(new Event("c")); - list.add(new Event("a")); - list.add(new Event("d")); - list.add(new Event("a")); - list.add(new Event("b")); - list.add(new Event("r")); - list.add(new Event("a")); - - int maxOrder = 3; - PredictionByPartialMatch model = new PredictionByPartialMatch(maxOrder, new Random()); - model.trie = new Trie>(); - model.trie.train(list, maxOrder); - model.trie.display(); - - List> context = new ArrayList>(); - Event symbol = new Event("a"); - // expected: 5 - Console.traceln(""+model.trie.getCount(context, symbol)); - - // expected: 0 - context.add(new Event("b")); - Console.traceln(""+model.trie.getCount(context, symbol)); - - // expected: 2 - context.add(new Event("r")); - Console.traceln(""+model.trie.getCount(context, symbol)); - - // exptected: [b, r] - context = new ArrayList>(); - context.add(new Event("a")); - context.add(new Event("b")); - context.add(new Event("r")); - Console.traceln(model.trie.getContextSuffix(context).toString()); - - // exptected: [] - context = new ArrayList>(); - context.add(new Event("e")); - Console.traceln(model.trie.getContextSuffix(context).toString()); - - // exptected: {a, b, c, d, r} - context = new ArrayList>(); - Console.traceln(model.trie.getFollowingSymbols(context).toString()); - - // exptected: {b, c, d} - context = new ArrayList>(); - context.add(new Event("a")); - Console.traceln(model.trie.getFollowingSymbols(context).toString()); - - // exptected: [] - context = new ArrayList>(); - context.add(new Event("a")); - context.add(new Event("b")); - context.add(new Event("r")); - Console.traceln(model.trie.getFollowingSymbols(context).toString()); - - // exptected: 0.0d - context = new ArrayList>(); - context.add(new Event("a")); - Console.traceln(""+model.getProbability(context, new Event("z"))); - } -} Index: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/Trie.java =================================================================== --- trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/Trie.java (revision 12) +++ (revision ) @@ -1,196 +1,0 @@ -package de.ugoe.cs.eventbench.ppm; - -import java.awt.Dimension; -import java.awt.Rectangle; -import java.awt.Shape; -import java.util.LinkedHashSet; -import java.util.LinkedList; -import java.util.List; -import java.util.Set; - -import javax.swing.JFrame; - -import org.apache.commons.collections15.Transformer; - -import de.ugoe.cs.eventbench.markov.IncompleteMemory; - -import edu.uci.ics.jung.algorithms.layout.Layout; -import edu.uci.ics.jung.algorithms.layout.TreeLayout; -import edu.uci.ics.jung.graph.DelegateTree; -import edu.uci.ics.jung.graph.Tree; -import edu.uci.ics.jung.visualization.BasicVisualizationServer; -import edu.uci.ics.jung.visualization.decorators.ToStringLabeller; -import edu.uci.ics.jung.visualization.renderers.Renderer.VertexLabel.Position; - -public class Trie { - - private Set knownSymbols; - - private final TrieNode rootNode; - - public Trie() { - rootNode = new TrieNode(); - knownSymbols = new LinkedHashSet(); - } - - public Set getKnownSymbols() { - return new LinkedHashSet(knownSymbols); - } - - // trains the current Trie using the given sequence and adds all subsequence of length maxOrder - public void train(List sequence, int maxOrder) { - IncompleteMemory latestActions = new IncompleteMemory(maxOrder); - int i=0; - for(T currentEvent : sequence) { - latestActions.add(currentEvent); - knownSymbols.add(currentEvent); - i++; - if( i>=maxOrder ) { - add(latestActions.getLast(maxOrder)); - } - } - int sequenceLength = sequence.size(); - for( int j=maxOrder-1 ; j>0 ; j-- ) { - add(sequence.subList(sequenceLength-j, sequenceLength)); - } - } - - - // increases the counters for each symbol in the subsequence - public void add(List subsequence) { - if( subsequence!=null && !subsequence.isEmpty() ) { - knownSymbols.addAll(subsequence); - subsequence = new LinkedList(subsequence); // defensive copy! - T firstSymbol = subsequence.get(0); - TrieNode node = getChildCreate(firstSymbol); - node.add(subsequence); - } - } - - protected TrieNode getChildCreate(T symbol) { - return rootNode.getChildCreate(symbol); - } - - protected TrieNode getChild(T symbol) { - return rootNode.getChild(symbol); - } - - // get the count of "sequence" - public int getCount(List sequence) { - int count = 0; - TrieNode node = find(sequence); - if( node!=null ) { - count = node.getCount(); - } - return count; - } - - // get the count of "sequence,follower" - public int getCount(List sequence, T follower) { - List tmpSequence = new LinkedList(sequence); - tmpSequence.add(follower); - return getCount(tmpSequence); - - } - - public TrieNode find(List sequence) { - if( sequence==null || sequence.isEmpty() ) { - return rootNode; - } - List sequenceCopy = new LinkedList(sequence); - TrieNode result = null; - TrieNode node = getChild(sequenceCopy.get(0)); - if( node!=null ) { - sequenceCopy.remove(0); - result = node.find(sequenceCopy); - } - return result; - } - - // returns all symbols that follow the defined sequence - public List getFollowingSymbols(List sequence) { - List result = new LinkedList(); - TrieNode node = find(sequence); - if( node!=null ) { - result = node.getFollowingSymbols(); - } - return result; - } - - // longest suffix of context, that is contained in the tree and whose children are leaves - // possibly already deprecated - public List getContextSuffix(List context) { - List contextSuffix = new LinkedList(context); // defensive copy - boolean suffixFound = false; - - while(!suffixFound) { - if( contextSuffix.isEmpty() ) { - suffixFound = true; // suffix is the empty word - } else { - TrieNode node = find(contextSuffix); - if( node!=null ) { - if( !node.getFollowingSymbols().isEmpty() ) { - suffixFound = true; - } - } - if( !suffixFound ) { - contextSuffix.remove(0); - } - } - } - - return contextSuffix; - } - - - static public class Edge{} - - static public class TrieVertex { - private String id; - protected TrieVertex(String id) { - this.id = id; - } - public String toString() { - return id; - } - } - - private Tree getGraph() { - DelegateTree graph = new DelegateTree(); - rootNode.getGraph(null, graph); - return graph; - } - - public void display() { - Tree graph = this.getGraph(); - Layout layout = new TreeLayout(graph, 60); - // The BasicVisualizationServer is parameterized by the edge types - BasicVisualizationServer vv = - new BasicVisualizationServer(layout); - vv.setPreferredSize(new Dimension(1100,850)); //Sets the viewing area size - - - final Rectangle rect = new Rectangle(40, 20); - - Transformer vertexShapeTransformer = - new Transformer() { - public Shape transform(TrieVertex s) { - return rect; - } - }; - vv.getRenderer().getVertexLabelRenderer().setPosition(Position.CNTR); - vv.getRenderContext().setVertexShapeTransformer(vertexShapeTransformer); - vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller()); - - JFrame frame = new JFrame("Trie"); - frame.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE); - frame.getContentPane().add(vv); - frame.pack(); - frame.setVisible(true); - } - - @Override - public String toString() { - return rootNode.toString(); - } -} Index: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/TrieBasedModel.java =================================================================== --- trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/TrieBasedModel.java (revision 12) +++ (revision ) @@ -1,74 +1,0 @@ -package de.ugoe.cs.eventbench.ppm; - -import java.util.LinkedList; -import java.util.List; -import java.util.Random; - -import de.ugoe.cs.eventbench.data.Event; -import de.ugoe.cs.eventbench.markov.IncompleteMemory; - -public abstract class TrieBasedModel { - - protected int maxOrder; - - protected abstract double getProbability(List> context, Event symbol); - - protected Trie> trie; - protected final Random r; - - - public TrieBasedModel(int maxOrder, Random r) { - super(); - this.maxOrder = maxOrder; - this.r = r; - } - - public void train(List>> sequences) { - trie = new Trie>(); - - for(List> sequence : sequences) { - List> currentSequence = new LinkedList>(sequence); // defensive copy - currentSequence.add(0, Event.STARTEVENT); - currentSequence.add(Event.ENDEVENT); - - trie.train(currentSequence, maxOrder); - } - } - - public List> randomSequence() { - List> sequence = new LinkedList>(); - - IncompleteMemory> context = new IncompleteMemory>(maxOrder-1); - context.add(Event.STARTEVENT); - - Event currentState = Event.STARTEVENT; - - boolean endFound = false; - - while(!endFound) { - double randVal = r.nextDouble(); - double probSum = 0.0; - List> currentContext = context.getLast(maxOrder); - for( Event symbol : trie.getKnownSymbols() ) { - probSum += getProbability(currentContext, symbol); - if( probSum>=randVal ) { - endFound = (symbol==Event.ENDEVENT); - if( !(symbol==Event.STARTEVENT || symbol==Event.ENDEVENT) ) { - // only add the symbol the sequence if it is not START or END - context.add(symbol); - currentState = symbol; - sequence.add(currentState); - } - break; - } - } - } - return sequence; - } - - @Override - public String toString() { - return trie.toString(); - } - -} Index: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/TrieNode.java =================================================================== --- trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/TrieNode.java (revision 12) +++ (revision ) @@ -1,123 +1,0 @@ -package de.ugoe.cs.eventbench.ppm; - -import java.security.InvalidParameterException; -import java.util.LinkedList; -import java.util.List; - -import de.ugoe.cs.eventbench.ppm.Trie.Edge; -import de.ugoe.cs.eventbench.ppm.Trie.TrieVertex; -import de.ugoe.cs.util.StringTools; -import edu.uci.ics.jung.graph.DelegateTree; - - -class TrieNode { - - private int count; - private final T symbol; - - private List> children; - - TrieNode() { - this.symbol = null; - count = 0; - children = new LinkedList>(); - } - - public TrieNode(T symbol) { - if( symbol==null ) { - throw new InvalidParameterException("symbol must not be null."); - } - this.symbol = symbol; - count = 0; - children = new LinkedList>(); - } - - public void add(List subsequence) { - if( !subsequence.isEmpty() ) { - if( !symbol.equals(subsequence.get(0)) ) { // should be guaranteed by the recursion/TrieRoot! - throw new AssertionError("Invalid trie operation!"); - } - count++; - subsequence.remove(0); - if( !subsequence.isEmpty() ) { - T nextSymbol = subsequence.get(0); - getChildCreate(nextSymbol).add(subsequence); - } - } - } - - public T getSymbol() { - return symbol; - } - - public int getCount() { - return count; - } - - protected TrieNode getChildCreate(T symbol) { - TrieNode node = getChild(symbol); - if( node==null ) { - node = new TrieNode(symbol); - children.add(node); - } - return node; - } - - protected TrieNode getChild(T symbol) { - for( TrieNode child : children ) { - if( child.getSymbol().equals(symbol) ) { - return child; - } - } - return null; - } - - - - public TrieNode find(List subsequence) { - TrieNode result = null; - if( subsequence.isEmpty() ) { - result = this; - } else { - TrieNode node = getChild(subsequence.get(0)); - if( node!=null ) { - subsequence.remove(0); - result = node.find(subsequence); - } - } - return result; - } - - // returns all symbols that follow this node - public List getFollowingSymbols() { - List followingSymbols = new LinkedList(); - for( TrieNode child : children ) { - followingSymbols.add(child.getSymbol()); - } - return followingSymbols; - } - - @Override - public String toString() { - String str = symbol.toString()+" #"+count; - if( !children.isEmpty() ) { - str += StringTools.ENDLINE + children.toString(); - } - return str; - } - - public void getGraph(TrieVertex parent, DelegateTree graph) { - TrieVertex currentVertex; - if( symbol==null ){ - currentVertex = new TrieVertex("root"); - graph.addVertex(currentVertex); - } else { - currentVertex = new TrieVertex(getSymbol().toString()+"#"+getCount()); - graph.addChild( new Edge() , parent, currentVertex ); - } - for( TrieNode node : children ) { - node.getGraph(currentVertex, graph); - } - } - -}