## 2 Pattern Matching in POM Encoded Dictionaries
Denote by \(\succ\) the lexicographic order relation, _i.e._, \(S\succ T\) if the string \(S\) follows \(T\) in lexicographic order. Algorithm 1 presents the algorithm for searching for a pattern \(P\) in a dictionary compressed by POM, based on decompressing each entry. It assumes as input a POM compressed dictionary that has been further encoded by some function \(\mathcal{E}\), hence the use of the decoding function \(\mathcal{D}\) for each of the components. The algorithm returns the index of the closest lexicographically preceding word to the word we are searching for. We start with \(\mathcal{D}(\sigma_{1})\), which is the first element, since \(\ell_{1}\) is always zero. As long as the component \(\mathcal{D}(\ell_{i})\), indicating the number of characters copied from the previous entry, is larger than the current longest match, we simply move to the following entry (line 2.1) by skipping over \(\mathcal{D}(\sigma_{i})\). This is done by decoding the following \(n_{i}\) codewords. The correctness here is based on the fact that in this case there is at least one character following the characters of the longest match that is not part of an extended match. If the component \(\mathcal{D}(\ell_{i})\) is less than the length of the current longest match, we have already found the closest lexicographically preceding word in the previous entry, and we return its index (line 2.2). When \(\mathcal{D}(\ell_{i})\) is exactly equal to the current length of the longest match, we try to extend the match to the following characters (line 2.3). ```
1\(i\longleftarrow 2\); \(j\longleftarrow pre(P,\mathcal{D}(\sigma_{1}))\);
2 while \((j<m)\) and dictionary not exhausted // Pattern not found {  while \(\mathcal{D}(\ell_{i})>j\) \(i\longleftarrow i+1\) if \(\mathcal{D}(\ell_{i})<j\) // The closest lexicographically preceding word  return \(i-1\) else // \(\mathcal{D}(\ell_{i})=j\) \(\{\)  if \(P[j+1,m]\prec\mathcal{D



lengths of one or more whole codewords. In the last column of Table 1, the definition of \(\ell_{i}\) is extended to be the maximal number of _bits_ copied from the previous entry, regardless of codeword boundaries. Though the number of copied bits is only occasionally increased and only by a small number of bits, the extension frees the function \(pre(S,T)\) of the need of checking for codewords. One can thus apply \(pre()\) on bitstrings regardless of their interpretation as codewords, which can be done efficiently with a few assembly commands. There is, however, a drawback when moving to perform the pattern matching directly on Huffman encoded dictionaries. In Algorithm 1, when the pattern word does not appear in the dictionary, we are able to locate the closest lexicographically preceding word, basing ourselves on the lexicographic order of the dictionary entries. The problem here stems from the fact that Huffman coding does not necessarily preserve the lexicographic order. Even canonical codes, for which the codewords are lexicographically ordered, induce the order from the frequencies of the encoded items, not from their own lexicographic order. For example, refer to the alphabet {t, c, b, a, q} encoded by the canonical code {00, 01, 10, 110, 111}. The string qt precedes tq, but considering their encodings, 11100 follows 00111. We can therefore only either locate the pattern, or announce a mismatch. The compressed matching algorithm in POM files which were compressed by using Huffman coding is given in Algorithm 2, with \(pre()\) now working on bit strings. Note that instead of decompressing the \(\sigma_{i}\) components, as done in the previous approach, we compress the pattern \(P\) and refer to bits instead of characters.