# Subpath Queries on Compressed Graphs: A Survey
## 1 Introduction
### The Entropy Model: Compressed Suffix Arrays
The reason for appending \(\$\) at the end of the text is that, in this way, no suffix prefixes another suffix. Suffix arrays were independently discovered by [PERSON] and [PERSON] in 1990 (1990) and (under the name of PAT array) by [PERSON], [PERSON], and [PERSON] in 1992 (1992, 2003). An earlier solution, the _suffix tree_([PERSON], 2003), dates back to 1973 and is more time-efficient, albeit much less space efficient (by a large constant factor). The idea behind the suffix tree is to build the trie of all text's suffixes, replacing unary paths with pairs of pointers to the text.  
The suffix array \(SA\), when used together with the text \(\mathcal{T}\), is a full-text index: in order to count/locate occurrences of a pattern \(\Pi\), it is sufficient to binary search \(SA\), extracting characters from \(\mathcal{T}\) to compare \(\Pi\) with the corresponding suffixes during search. This solution permits to count the _occ_ occurrences of a pattern \(\Pi\) of length \(m\) in a text \(\mathcal{T}\) of length \(n\) in \(O(m\log n)\) time, as well as to report them in additional optimal \(O(occ)\) time.  
Figure 1: Running example used in this section.  
Figure 2: Suffix Array (SA) of the text \(\mathcal{T}\) of Figure 1. Note: we store only array \(SA\) and the text \(\mathcal{T}\), not the actual text suffixes.  
Letting the alphabet size being denoted by \(\sigma\), our index requires \(n\log\sigma+n\log n\) bits to be stored (the first component for the text and the second for the suffix array).  
Note that the suffix array cannot be considered a _small_ data structure. On a constant-sized alphabet, the term \(n\log n\) is asymptotically larger than the text. The need for processing larger and larger texts made this issue relevant by the end of the millennium. As an instructive example, consider indexing the Human genome (\(\approx\)3 billion DNA bases). DNA sequences can be modeled as strings over an alphabet of size four (\(\{A,C,G,T\}\)); therefore, the Human genome takes less than 750 MiB of space to be stored using two bits per letter. The suffix array of the Human genome requires, on the other hand, about 11 GiB.  
Although the study of _compressed text indexes_ had begun before the year 2000 [15], the turn of the millennium represented a crucial turning point for the field: two independent works by [PERSON] and [PERSON] [16] and [PERSON] and [PERSON] [17] showed how to _compress_ the suffix array.  
Consider the integer array \(\psi\) of length \(n\) defined as follows. Given a suffix array position \(i\) containing value (text position) \(j=SA[i]\), the cell \(\psi[i]\) contains the suffix array position \(i^{\prime}\) containing text position \((j\mod n)+1\) (we treat the string as circular). More formally: \(\psi[i]=SA^{-1}[(SA[i]\mod n)+1]\). See Figure 3.  
Note the following interesting property: equally-colored values in \(\psi\) are increasing. More precisely: \(\psi\)-values corresponding to suffixes beginning with the same letter form increasing subsequences. To understand why this happens, observe that \(\psi[i]\) takes us from a suffix \(\mathcal{T}[SA[i],\ldots,n]\) to suffix \(\mathcal{T}[SA[i]+1,\ldots,n]\) (let us exclude the case \(SA[i]=n\) in order to simplify our formulas). Now, assume that \(i<j\) and \(\mathcal{T}[SA[i],\ldots,n]\) and \(\mathcal{T}[SA[j],\ldots,n]\) begin with the same letter (that is: \(i\) and \(j\) have the same color in Figure 3). Since \(i<j\), we have that \(\mathcal{T}[SA[i],\ldots,n]<\mathcal{T}[SA[j],\ldots,n]\) (lexicographically). But then, since the two suffixes begin with the same letter, we also have that \(\mathcal{T}[SA[i]+1,\ldots,n]<\mathcal{T}[SA[j]+1,\ldots,n]\), i.e., \(\psi[i]<\psi[j]\).  
Let us now store just the differences between consecutive values in each increasing subsequence of \(\psi\). We denote this new array of differences as \(\Delta(\psi)\). See Figure 4 for an example.  
Two remarkable properties of \(\Delta(\psi)\) are that, using an opportune encoding for its elements, this sequence:  
1. supports accessing any \(\psi[i]\) in constant time [17], and
2. can be stored in \(nH_{0}+O(n)\) bits of space, where \(H_{0}=\sum_{c\in\Sigma}(n_{c}/n)\log(n/n_{c})\) is the zero-order empirical entropy of \(\mathcal{T}\) and \(n_{c}\) denotes the number of occurrences of \(c\in\Sigma\) in \(\mathcal{T}\).  
The fact that this strategy achieves compression is actually not hard to prove. Consider any integer encoding (for example, Elias' delta or gamma) capable to represent any integer \(x\) in \(O(1+\log x)\) bits. By the concavity of the logarithm function, the inequality \(\sum_{l=1}^{m}\log(x_{i})\leq m\cdot\log(\frac{\sum_{l=1}^{m}x_{i}}{m})\) holds for any integer sequence \(x_{1},\ldots,x_{m}\). Now, note that the sub-sequence \(x_{1},\ldots,x_{n_{c}}\) of \(\Delta(\psi)\) corresponding to letter \(c\in\Sigma\) has two properties: it has exactly \(n_{c}\) terms and \(\sum_{l=1}^{n_{c}}x_{i}\leq n\). It follows that the encoded sub-sequence takes (asymptotically) \(\sum_{l=1}^{n_{c}}(1+\log(x_{i}))\leq n_{c}\cdot\log(n/n_{c})+n_{c}\) bits. By summing this quantity  
Figure 4: The differential array \(\Delta(\psi)\).  
Figure 3: Array \(\psi\).  
over all the alphabet's characters, we obtain precisely \(O(n(H_{0}+1))\) bits. Other encodings (in particular, Elias-Fano dictionaries [18; 19]) can achieve the claimed \(nH_{0}+O(n)\) bits while supporting constant-time random access.  
The final step is to recognize that \(\psi\) moves us forward (by one position at a time) in the text. This allows us to extract suffixes _without using the text_. To achieve this, it is sufficient to store in one array \(F=\$AAAAGTTT\) (using our running example) the first character of each suffix.