## 2 Pattern Matching in POM Encoded Dictionaries
For example, if \(\mathcal{E}(P)=\) 1100-1101 and \(\sigma_{1}=\) 1100-110101, then the longest common prefix in characters is of length 1, (_i.e._, the decoding of 1100), but the longest common prefix in bits is the binary string 1100-1101, which could be wrongly interpreted as _two_ codewords. This can be corrected by checking whether the string which follows the longest common binary prefix in both \(\mathcal{E}(P)\) and \(\sigma_{i}\) is at the beginning of a codeword, _i.e._, starts with 11. The function _fib-pre_ in Algorithm 3 refers to this corrected version: it calculates the number of codewords, rather than the number of bits, in the common prefix, and returns the number of bits in these codewords. For the example above, _fib-pre\((\mathcal{E}(P),\sigma_{1})=4\)_. Since Fibonacci codes, like Huffman codes, do not necessarily preserve lexicographic order, they also cannot return the closest lexicographically preceding word in case the word is not found. Consider the same example used above, where the alphabet {t, c, b, a, q} is encoded by \(\{110,1100,\,1101,11000,\)\(11001\}\), respectively. The dictionary entry bc precedes cb, contrarily to their respective encodings 1101-1100 and 1100-1101. Compressed pattern matching in POM and Fibonacci can thus only return the matched entry or announce a mismatch. ## 5 Alternative Method

[PERSON] and [PERSON] [25] introduce a data structure called an LZ-trie for compressing static dictionaries which is a generic Lempel-Ziv compression of a linked list trie. This compressed trie reduces the size of the dictionary beyond that of a minimal finite automaton and allows the incorporation of the additional data in the trie itself. They perform it by sharing not only common prefixes or suffixes, but also internal patterns. In order to speed up the quadratic time compressing procedure, they use suffix arrays for looking for repeated substrings in the trie. LZ linked list tries perform best for dictionaries of inflected languages (e.g., Romanic, Slavic) and are less efficient for English. The compression performance of the LZ-trie improves over larger dictionaries. Since the strings are represented by a compressed trie structure, the look up is not performed sequentially but by following the trie links. The search done by the LZ linked list trie is therefore significantly faster than that of other methods, that use sequential searching. ## 6 Experimental Results

The experiments were performed on small POM files of several \(K\) bytes because of the following particular application: POM is often used to store dictionaries in B-trees; since the B-tree structure supports an efficient access to memory pages, each node is limited to a page size, and each page has to be compressed on its own, that is, for the first entry of each page, \(\ell_{1}=0\). A part of the B-tree may reside in cache, but if it does not fit in its entirety in memory, parts of it have to be fetched on request. Experiments were performed on an Intel PC with 900 MHz AMD Athlon CPU with 256 KB cache memory and 256 MB of main memory running RedHat Linux-7.3. For our experiments, we have chosen files of different nature: the English Bible _bib_, and a large XML file _xml_. Their dictionaries were built from all the words that occur in these files. We then considered different prefixes of these dictionaries, so that we get sub-dictionaries of approximate sizes 2K, 4K, 8K and 16K. To see how the methods scale up, we have also included as last line the dictionary of all the words in the Hebrew Bible. Table 4 gives the compression performance: the second column gives the sizes of the original sub-dictionaries, the third column gives the size of the POM file after using Huffman coding, when the values for \(n_{i}\) and \(\ell_{i}\) are expressed in bits, the fourth column contains the corresponding values for the Fibonacci variant, \(\ell_{i}\) being expressed in characters.