# Lyndon Factorization Algorithms for Small Alphabets and Run-Length Encoded Strings +
## 6 Experimental Results
#### Testing LF-skip. At first we tested the variations of LF-skip against the variations of LF-Duval. The texts were random sequences of 5 MB symbols. For each alphabet size \(\sigma=2,4,\ldots,256\) we generated 100 sequences with a uniform distribution, and each run with each sequence was repeated 500 times. The average run times are given in Table 1 which is shown in a graphical form in Figure 4.  
LF-skip was faster than the best variation of LF-Duval for all tested values of \(\sigma\). The speed-up was significant for small alphabets. LF-skip2 was faster than LF-skip for \(\sigma\leq 16\) and slower for \(\sigma>16\). The speed of LF-Duval did not depend on \(\sigma\). LF-Duval2 became faster when the size of the alphabet grew. For large alphabets LF-Duval2 was faster than LF-Duval and for small alphabets the other way round. In additional refined experiments, \(\sigma=5\) was the threshold value. When we compiled LF-Duval and LF-Duval2 without optimization, both of the variations behaved in a similar way. So the better performance of LF-Duval2 for large alphabets is due to compiler optimization, possibly by cause of branch prediction. \begin{table}
\begin{tabular}{c c c c c} \hline \hline \(\sigma\) & **LF-Duval** & **LF-Duval2** & **LF-skip** & **LF-skip2** \\ \hline
2 & 14.6 & 21.9 & 2.5 & 1.5 \\
4 & 14.6 & 14.9 & 1.6 & 1.1 \\
8 & 14.7 & 9.1 & 1.3 & 1.1 \\
16 & 14.7 & 6.4 & 1.3 & 1.2 \\
32 & 14.7 & 5.0 & 1.4 & 1.6 \\
64 & 14.7 & 4.3 & 1.7 & 2.3 \\
128 & 14.7 & 4.0 & 2.0 & 3.2 \\
192 & 14.6 & 3.8 & 1.7 & 3.7 \\
256 & 14.6 & 3.8 & 2.6 & 4.1 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Run times in milliseconds on random sequences (5 MB) with a uniform distribution of a varying alphabet size. Figure 4: Comparison of the algorithms on random sequences (5 MB) with a uniform distribution of a varying alphabet size. We tested the variations of LF-skip also with longer random sequences of four characters up to 500 MB. The average speed did not essentially change when the sequence became longer. In addition, we tested LF-skip and LF-skip2 with real texts. At first we did experiments with texts of natural language. Because runs are very short in a natural language and newline or some other control character is the smallest character, the benefit of LF-skip or LF-skip2 was marginal. If it were acceptable to relax the lexicographic order of the characters, some gain could be obtained. For example, LF-skip achieved the speed-up of 2 over LF-Duval2 in the case of the KJV Bible when '\(l\)' is the smallest character. For the DNA sequence of fruitfly (15 MB), LF-skip2 was 20.3 times faster than LF-Duval. For the protein sequence of the saccharomyces cerevisiae (2.9 MB), LF-skip2 was 8.7 times faster than LF-Duval2. The run times on these biological sequences are shown in Table 2.  
Testing LF-rle.To assess the performance of the LF-rle algorithm, we tested it together with LF-Duval, LF-Duval2 and LF-skip2 for random binary sequences of 5 MB with different probability distributions, so as to vary the number of runs in the sequence. The running time of LF-rle does not include the time needed to compute the RLE of the sequence, i.e., we assumed that the sequence is given in the RLE form, since otherwise other algorithms are preferable. For each test we generated 100 sequences, and each run with each sequence was repeated 500 times. The average run times are given in Table 3 which is shown in a graphical form in Figure 5. \begin{table}
\begin{tabular}{c c c c c} \hline \hline  & **LF-Duval** & **LF-Duval2** & **LF-skip2** & **LF-skip2** \\ \hline DNA (15 MB) & 44.7 & 52.2 & 3.0 & 2.2 \\ Protein (2.9 MB) & 8.5 & 3.4 & 0.50 & 0.39 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Run times in milliseconds on two biological sequences. Figure 5: Comparison of the algorithms on random binary sequences (5 MB) with a skew distribution.