<p>Can't you just use the graph to build a trie, and then have the counts of <em>all</em> words.  (You would have to augment the trie slightly.)  It's a simple step from there to sort the words by number of occurrences, although the most common word will trivially be the single label that appears the most in your DAG.  (It gets more interesting if you look at most common words of a given length...)</p>

CC BY-SA 2.5
2011-03-13T20:41:29.147Z
that's what I was thinking as well, and you're right that the question is slightly ill-formed (it needs conditioning by the size of the string)
Suresh Venkat
CC BY-SA 2.5
2011-03-13T04:22:59.210Z
2011-03-13T04:22:59.210Z
rlibby
<p>I have a directed acyclic graph with ~250k nodes, each node has one of about 100 symbols as label. Letting a word be the sequence of n symbols that corresponds to a path containing n nodes in the graph, how can I find the most common words? What known algorithms should I study?</p>

<p>An interesting extension is to let edges also have one of about 100 symbols (the set of edge symbols does not intersect the set of node symbols) as label, redefining a word to be the sequence of length n+(n-1) symbols that corresponds to a path containing n nodes and n-1 edges.</p>

<p>Reading tips and wikipedia links are appreciated as well as more elaborate answers.</p>

CC BY-SA 2.5
2011-03-12T17:02:12.183Z
This is similar to a [hidden Markov model](http://en.wikipedia.org/wiki/Hidden_Markov_model). The directed acyclic graph is analogous to the underlying Markov chain, and the symbols are analogous to the visible output. There's been a lot of research on hidden Markov models, although I don't know of any that addresses your question. If you took a random walk on the graph for a while, and observed the next *n* symbols, your question would indeed be about hidden Markov models. If you're looking for a uniform distribution on paths of length *n*, this is a somewhat different question.
Peter Shor 
<ds.algorithms><graph-algorithms><directed-acyclic-graph>
Finding common label sequences in a directed acyclic graph
Jonatan Kallus
# Finding common label sequences in a directed acyclic graph

(Asked by: username_0 on 2011-03-12)

I have a directed acyclic graph with ~250k nodes, each node has one of about 100 symbols as label. Letting a word be the sequence of n symbols that corresponds to a path containing n nodes in the graph, how can I find the most common words? What known algorithms should I study?

An interesting extension is to let edges also have one of about 100 symbols (the set of edge symbols does not intersect the set of node symbols) as label, redefining a word to be the sequence of length n+(n-1) symbols that corresponds to a path containing n nodes and n-1 edges.

Reading tips and wikipedia links are appreciated as well as more elaborate answers.

**Tags:** ds.algorithms, graph-algorithms, directed-acyclic-graph
> **Comments:**
> **username_1**: This is similar to a [hidden Markov model](http://en.wikipedia.org/wiki/Hidden_Markov_model). The directed acyclic graph is analogous to the underlying Markov chain, and the symbols are analogous to the visible output. There's been a lot of research on hidden Markov models, although I don't know of any that addresses your question. If you took a random walk on the graph for a while, and observed the next *n* symbols, your question would indeed be about hidden Markov models. If you're looking for a uniform distribution on paths of length *n*, this is a somewhat different question.  

---

## 1 answers

### Answer by username_2 on 2011-03-13. Score: 1 | Accepted answer

Can't you just use the graph to build a trie, and then have the counts of *all* words. (You would have to augment the trie slightly.) It's a simple step from there to sort the words by number of occurrences, although the most common word will trivially be the single label that appears the most in your DAG. (It gets more interesting if you look at most common words of a given length...)

> **Comments:**
> **username_3**: that's what I was thinking as well, and you're right that the question is slightly ill-formed (it needs conditioning by the size of the string)  

---

