## 3 Representing Array _LCP_
### Experimental Comparison  
Our computer is an Intel Core2 Duo at \(3.16\) GHz, with \(8\) GB of RAM and \(6\) MB cache, running Linux version \(2.6.24\)-\(24\). Table 2 lists the collections used for this experiment. They were obtained from the _Pizza & Chili_ site [44]. We also give some information on their LCP values and number of runs in \(\Psi\), which affects their compressibility. We tested the different LCP representations by accessing 100,000 random positions of the _LCP_ array. Figure 2 (left) shows the space/times achieved on the four texts. Only \(PT\) and _PhiSpare_ display a space/time tradeoff; in the first we use \(v=4,6,8\) and for the second \(q=16,32,64\). Because in various cases we need to access a sequence of consecutive LCP values, we show in Figure 2 (right) the time per cell when accessing 32 consecutive cells. The plots also show solution _Naive_, which stores LCP values using the number of bits required by the maximum value in the array.  
\begin{table}
\begin{tabular}{l l r r r} \hline
**Collection** & **Size** & **Description** & **Avg LCP** & **Max LCP** & **Runs (\(r/n\))** \\ \hline dna & \(100\) & DNA sequences from Gutenberg Project & \(28.1\) & \(17,772\) & 0.63 \\ xml & \(100\) & XML from dblp.uni-trier.de & \(44.5\) & \(1084\) & 0.14 \\ proteins & \(100\) & Protein sequences from the Swissprot database & \(220.6\) & \(35,246\) & 0.59 \\ sources & \(100\) & Source code obtained by concatenating files of the & \(625.1\) & \(307,871\) & 0.23 \\  & & Linux-2.6.11.6 and gcc-4.0.0 distributions & & \\ \hline \end{tabular}
\end{table}
Table 2: Data files used for tests with their size in MB, plus some information on their compressibility.  
Figure 2: Space/Time for accessing array _LCP_. On the left for random accesses and on the right for sequential accesses.  
We use [PERSON]'s CSA implementation [12], available at _Pizza & Chili_, as our CSA, with sampling \(s=16\). This is relevant because various LCP implementations need to compute \(A[i]\) from the CSA.  
A first observation is that [PERSON] _et al_.'s compression techniques for bitmap \(H\) do not compress significantly in practice (on non-repetitive collections). The value of \(r\) is not small enough to make the compressed representations noticeably smaller (and at times their space overhead over the entropy makes them larger, especially variant _FMN-OS_).  
These explicit representations of \(H\) require only \(2.1n\) bits of space and access _LCP_ in about 10 microseconds. Technique _PT_ is always dominated by them and _PhiSpare_ can achieve less space, but at the price of an unacceptable 10-fold increase in time.  
The other dominant technique is _DAC/DAC-Var_, which requires significantly more space (\(6n-8n\) bits) but can access _LCP_ within 0.1-0.2 microseconds. This is because it does not need to compute \(A[i]\) to find \(\textit{LCP}[i]\). Its time is even competitive with _Naive_, while using much less space. Technique _RP_, instead, does not perform well, doing even worse than _Naive_ in time and space. This shows, again, that (in non-repetitive) collections the value \(r\) is not small enough: While the length of the Re-Pair compressed sequence is 30%-60% of the original one, the values require more bits than in _Naive_ because Re-Pair creates many new symbols.  
_DAC_, _DAC-Var_ and _Naive_ are the only techniques that benefit from extracting consecutive values, so the former stay comparable with _Naive_ in time even in this case. This owes to the better cache usage compared with the other representations, which must access spread text positions to decode a contiguous _LCP_ area.  
For the sequel we will keep only _DAC_ and _DAC-Var_, which give the best time performance, and _FMN-RRR_ and _Sad-Gon_, which have the most robust performance at representing \(H\).