1. Number of nodes. In general, the number of nodes in the (S)CDAWG of a corpus is much smaller than the number of nodes in a suffix tree or DAWG. This is seen in Figure 1. A more informative picture is found in Table 1 where we compare the size of these index structures for a small collection of corpora of distinct sizes. For the sake of completeness, the table also includes data for suffix tries, a simplified version of suffix trees where each suffix represents a node.
2. Naturalness of nodes. Most of the infixes representing the nodes of a (S)CDAWG are very natural from an intuitive point of view[4]: imagine we index the German version of Goethe's Faust. Among the nodes of the suffix tree, we will find right-closed infixes such as ephisto, phisto, retchen, and etchen. In the DAWG we find left-closed infixes such as Mephist, Mephis, Gretche and Gretch. In the (S)CDAWG we only have the two-sided closures Mephisto and Gretchen. The example indicates that two-sided closure is a very natural property when looking for “interesting” and “meaningful” infixes of a corpus.
3. Node Extension Property. Among the infixes that represent the nodes of the index (suffix tree, DAWG, or (S)CDAWG) in general there are many inclusion relations where one infix \(v\) is a substring of another one \(w\). In a suffix tree, DAWG, or CDAWG extension steps departing from node \(v\) in many cases do not lead to node \(w\). For example, in the suffix tree in Figure 1 we cannot reach op 1 in A from in following the transitions. In contrast, the two-directional edge structure of SCDAWGs completely covers infix containment in the sense that whenever node \(v\) is a substring of \(w\) there exists a chain of left and right extensions leading from \(v\) to \(w\). In other words, starting from a node \(v\) and traversing the index we find each context containing \(v\). For the sake of reference, this property will be called the “Node Extension Property”. It can be used, for example, to find in a very elegant way all texts where an infix \(v\) occurs: starting from the node that represents (the two-sided closure of) \(v\), compute all maximal chains of left extensions followed by all maximal chains of right extensions. The nodes reached at the end represent the texts in which \(v\) occurs. For example, in Figure 1 starting from op or in we reach the nodes representing the two input texts.

Procedure FindTexts(\(\mu\)) 
if \(T(\mu)\) is already defined, then
    output \(T(\mu)\);
else if \(\mu\) is a leaf (text), then
    let \(n\) be the number of the text;
    define \(T(\mu) := \{n\}\);
    output \(\{n\}\);
otherwise
    let \(\nu_1,\ldots,\nu_k\) be the (left or right) immediate successors of \(\mu\).
    call FindTexts(\(\nu_1\)), ...., FindTexts(\(\nu_k\));
    define \(T(\mu) :=\bigcup_{i=1,\ldots, k} T(\nu_i);\)
    output \(T(\mu)\);
                        

Figure 2. 

A text \(A\) leading to a value \(r=130,000\) for the LIS problem if compared with a similar parallel text \(B\).

1. the infix associated with \(\mu\) occurs in both texts \(A\) and \(B\),
2. \(\mu\) does not have any transition that leads to another node \(\mu\)’ with the Property 1.

• We consider each node reached from \(\mu\) with a single left or right transition in the SCDAWG. Each such node representing an infix occurring both in \(A\) and \(B\) is added to the end of the queue.
• If \(\mu\) does not have any extension representing an infix occurring both in \(A\) and \(B\), then \(\mu\) is added to the list of quasi maximal nodes.

1. the infix associated with \(\mu\) occurs in all texts \(A_1,\ldots, A_n\),
2. \(\mu\) does not have any transition that leads to another node \(\mu\)’ with Property 1.

Figure 4. 

Subsegment of the multi-alignment of three texts (OCR outputs and ground truth) using quasi-maximal nodes. Grey parts represent quasi-maximal nodes, for the coloured regions at least two texts show a disagreement.

• laut und leise, Unterric... träumt, Angenehme zu hören
• wälzend kam die Sturmesf ... der Chor vom ganzen Haine

Figure 6. 

Text reuses in the Poems Corpus - quasi maximal nodes and pointers to 5 poems, zoomed subregion of upper graph in Figure 5.

• She tied you to a kitche .. Hallelujah, Hallelojah}
• s seen the light It's a -- ah Hallelujah, Hallelujah}

Figure 7. 

Text reuses in the Lyrics Corpus - quasi maximal nodes and pointers to lyrics, zoomed subregion of lower graph in Figure 5.