# Optimal Prefix Free Codes with Partial Sorting +
## 4 Preliminary Experiments  
There are many mature implementations [5; 18] to compute optimal prefix free codes: [PERSON]'s solution [1] to the problem of optimal prefix free codes is not only ancient (67 years from 1952 to 2019), but also one still in wide use: In 1991, [PERSON] stated that \"products that use Huffman code might fill a consumer electronics store\" [26]. In 2010, the answer to the question \"what are the real-world applications of Huffman coding?\" on the website Stacks Exchange [27] stated that \"Huffman is widely used in all the mainstream compression formats that you might encounter--from GZIP, PKZIP (winzip etc.) and BZIP2, to image formats such as JPEG and PNG.\" In 2019, the Wikipedia website on Huffman coding still states that \" prefix codes nevertheless remain in wide use because of their simplicity, high speed, and lack of patent coverage. They are often used as a \"back-end\" to other compression methods. DEFLATE (PKZIP's algorithm) and multimedia codecs such as JPEG and MP3 have a front-end model and quantization followed by the use of prefix codes (...).\" [28]. Presenting an implementation competitive with industrial ones is well beyond the scope of this (theoretical) work, but it is possible to perform some preliminary experimental work in order to predict the potential practical impact of algorithms taking advantage of various difficulty measures introduced so far. We realized such an implementation (which sources are publicly available, see Supplementary Materials) and present preliminary experimental results using such an implementation. Albeit the computation of optimal prefix free codes occurs in many applications (In several applications, optimal prefix free codes are fixed once for all, but there are still many applications for which such codes are computed again for each instance) (e.g., BZIP2 [6], JPEG [7], etc. ), the alphabet size is not necessarily increasing with the size of the data to be compressed. In order to evaluate the potential improvement of adaptive techniques such as presented in this work and others [16; 17], we consider the application of optimal prefix free codes to the word-based compression of natural language texts, cited as an example of \"large alphabet\" application by [PERSON] [3], and studied by [PERSON] et al. [29]. As for the natural language texts themselves, we considered a random selection of nine texts from the Gutenberg project [30], listed in Table 2.  
Compared to the many difficulty measures known for sorting [31; 32], there are only a few ones for the computation of optimal prefix free codes, respectively introduced by [PERSON] and [PERSON] [15], [PERSON] et al. [19], [PERSON] and [PERSON] [16; 17], and ourselves in this work: Table 3 describes those measures of difficulty, and the experimental values of the most relevant ones on the texts listed in Table 2. Even if optimized implementations might have some constant factor of the running time (in particular concerning the computation of the median of a set of values), studying the ratio between theoretical complexities yields an idea of how big such a constant factor must be to make a difference. \begin{table}
\begin{tabular}{c l} \hline \hline
**File Name** & **Description** \\ \hline
14529-0.txt & The Old English Physiologus, EBook \#14529 \\
32575-0.txt & The Head Girl at the Gables, EBook \#32575 \\ pg12944.txt & Punch, Or The London Charivari, EBook \#12944 \\ pg24742.txt & Mary, Mary, EBook \#24742 \\ pg25373.txt & Woodward’s Graperies and Horticultural Buildings, EBook \#25373 \\ pg31471.txt & The Girl in the Mirror, EBook \#31471 \\ pg4545.txt & An American Papyrus: 25 Poems, EBook \#4545 \\ pg7925.txt & Expositions of Holy Scripture, EBook \#7925 \\ shakespeare.txt & The Complete Works of [PERSON], EBook \#100 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Data sets used for the experimentation measures, all from the Project Gutenberg.