## 2 Pattern Matching in POM Encoded Dictionaries
The fifth column corresponds to a Huffman encoded POM file, for which \(n_{i}\) and \(\ell_{i}\) represent character counts (as in the third column of Table 1), rather than the number of bits (as in the fourth column): the encoded numbers are thus smaller, yielding a reduced size of the file. The sixth column is the performance of POM alone. The last column gives the sizes of the LZ tries of [25]. All the sizes are given in bytes and include the overhead caused by storing the Huffman trees. The POM-Huffman methods use three Huffman trees, one for each of the components \(\sigma_{i}\), \(\ell_{i}\) and \(n_{i}\). The POM-Fibonacci method uses only two components \(\sigma_{i}\) and \(\ell_{i}\). As can be seen, the Fibonacci variant performs better for small files. This advantage could be explained by the use of two fields instead of three, and the fact that Huffman coding requires more additional space: even if Canonical Huffman codes are used, one still needs information about the shape of the trees, _i.e._, the number of codewords of a given length, while for Fibonacci codes, these numbers are fixed and need not to be stored. The LZ trie improves on POM, but is inferior to the Huffman encoded POM files, and on the small files also to the Fibonacci encoded ones. Recall that, as mentioned above, the small files are our main target application. To empirically compare the processing times, we considered all of the words which occur in the dictionary. We thus considered one pattern for each entry in the dictionary, and averaged the search times. The results in milliseconds are given in Table 5. For comparison, we added also the search times with the LZ trie and a column headed \"decode \(+\) search\", corresponding to the character oriented Huffman coded POM file which is decoded and then scanned with the algorithm of Figure 2. The direct access of the trie approach, in comparison with the sequential access of the other methods, makes the LZ trie several orders of magnitude faster. Among the other methods, for the smaller files, there is a clear advantage of the Fibonacci approach since a part of the encoded file is not scanned. For the largest \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**File** & **Size** & **Huffman (bit encoding)** & **Fibonacci (char encoding)** & **Huffman** (char encoding)** & **POM** & **LZ trie** \\ \hline bib1 & 2044 & 775 & 716 & 616 & 1171 & 1000 \\ bib2 & 4095 & 1709 & 1666 & 1413 & 2754 & 2369 \\ bib3 & 8067 & 2769 & 2749 & 2253 & 4663 & 3496 \\ bib4 & 16199 & 5242 & 5379 & 4276 & 9217 & 6002 \\ xml1 & 2047 & 1097 & 999 & 905 & 1481 & 1614 \\ xml2 & 4093 & 1640 & 1527 & 1327 & 2457 & 2138 \\ xml3 & 8190 & 2427 & 2350 & 1957 & 4079 & 2696 \\ xml4 & 16,383 & 3898 & 4001 & 3156 & 7336 & 3785 \\ Hebbib & 253,230 & 72,514 & 80,079 & 55,149 & 148,890 & 74,363 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Comparative chart of compression performance. file the Huffman variant is better, which could be explained by the smaller file to be processed. Both compressed matching techniques are generally better than decompressing and searching afterwards. ## 7 Conclusions

We introduced two new methods to represent a POM file so that direct search could be done in these compressed dictionaries. The processing time is typically twice as fast for the Fibonacci variant than for the Huffman based algorithm, and also compared to decoding a Huffman encoded POM file and searching on the uncompressed version. We see that in the case of small files, which is the important application since dictionaries are usually kept in small chunks, the Fibonacci variant is much faster than decoding and searching or than the POM-Huffman method. Even though the compression performance might be slightly inferior to the character version of Huffman (but is still generally better than the bit version), this might well be a price worth to pay for getting the faster processing.