3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This is similar to a 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. $\endgroup$ – Peter Shor Mar 12 '11 at 17:02
1
$\begingroup$

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...)

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Suresh Venkat Mar 13 '11 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.