Editing Directed acyclic graph (section)

=== Data compression ===
Directed acyclic graphs may also be used as a [[data compression|compact representation]] of a collection of sequences. In this type of application, one finds a DAG in which the paths form the given sequences. When many of the sequences share the same subsequences, these shared subsequences can be represented by a shared part of the DAG, allowing the representation to use less space than it would take to list out all of the sequences separately. For example, the [[Deterministic acyclic finite state automaton|directed acyclic word graph]] is a [[data structure]] in computer science formed by a directed acyclic graph with a single source and with edges labeled by letters or symbols; the paths from the source to the sinks in this graph represent a set of [[String (computer science)|strings]], such as English words.<ref>{{citation | first1=Maxime | last1=Crochemore | first2=Renaud | last2=Vérin | contribution=Direct construction of compact directed acyclic word graphs | series=Lecture Notes in Computer Science | publisher=Springer | title=Combinatorial Pattern Matching | volume=1264 | year=1997 | pages=116–129 | doi=10.1007/3-540-63220-4_55 | isbn=978-3-540-63220-7 | citeseerx=10.1.1.53.6273 | s2cid=17045308 }}.</ref> Any set of sequences can be represented as paths in a tree, by forming a tree vertex for every prefix of a sequence and making the parent of one of these vertices represent the sequence with one fewer element; the tree formed in this way for a set of strings is called a [[trie]]. A directed acyclic word graph saves space over a trie by allowing paths to diverge and rejoin, so that a set of words with the same possible suffixes can be represented by a single tree vertex.<ref>{{citation|title=Applied Combinatorics on Words|volume=105|series=Encyclopedia of Mathematics and its Applications|first=M.|last=Lothaire|author-link=M. Lothaire|publisher=Cambridge University Press|year=2005|isbn=9780521848022|page=18|url=https://books.google.com/books?id=fpLUNkj1T1EC&pg=PA18}}.</ref>

The same idea of using a DAG to represent a family of paths occurs in the [[binary decision diagram]],<ref>{{citation|first=C. Y.|last=Lee|title=Representation of switching circuits by binary-decision programs|journal=Bell System Technical Journal|volume=38|issue=4|pages=985–999|year=1959|doi=10.1002/j.1538-7305.1959.tb01585.x}}.</ref><ref>{{citation|first=Sheldon B.|last=Akers|doi=10.1109/TC.1978.1675141|title=Binary decision diagrams|journal=IEEE Transactions on Computers|volume=C-27|issue=6|pages=509–516|year=1978|s2cid=21028055}}.</ref> a DAG-based data structure for representing binary functions. In a binary decision diagram, each non-sink vertex is labeled by the name of a binary variable, and each sink and each edge is labeled by a 0 or 1. The function value for any [[truth assignment]] to the variables is the value at the sink found by following a path, starting from the single source vertex, that at each non-sink vertex follows the outgoing edge labeled with the value of that vertex's variable. Just as directed acyclic word graphs can be viewed as a compressed form of {{not a typo|tries}}, binary decision diagrams can be viewed as compressed forms of [[decision tree]]s that save space by allowing paths to rejoin when they agree on the results of all remaining decisions.<ref>{{citation
 | last1 = Friedman | first1 = S. J.
 | last2 = Supowit | first2 = K. J.
 | contribution = Finding the optimal variable ordering for binary decision diagrams
 | doi = 10.1145/37888.37941
 | isbn = 978-0-8186-0781-3
 | location = New York, NY, USA
 | pages = 348–356
 | publisher = ACM
 | title = Proc. 24th ACM/IEEE Design Automation Conference (DAC '87)
 | year = 1987| s2cid = 14796451
 }}.</ref>