## 2 Pattern Matching in POM Encoded Dictionaries
```
1:\(i\longleftarrow 2\); \(j\longleftarrow pre(\mathcal{E}(P),\sigma_{1})\);
2:\(security\longleftarrow\max_{c\in P}\{|\mathcal{E}(c)|\}\)
3:while (\(j<|\mathcal{E}(P)|\)) and dictionary not exhausted // Pattern not found {
4:while \(\mathcal{D}(\ell_{i})>j\)
5:skip \(n_{i}\) bits to the following entry
6:\(i\longleftarrow i+1\)
7:if \(\mathcal{D}(\ell_{i})+security<j\) return FALSE
8:else // \(j-security\leq\mathcal{D}(\ell_{i})\leq j\)
9:\(\{\)
10:\(tmp\longleftarrow pre(\mathcal{E}(P)[\mathcal{D}(\ell_{i})+1,|\mathcal{E}(P)| ],\sigma_{i})\)
11:\(j\longleftarrow\mathcal{D}(\ell_{i})+tmp\)
12:skip \(n_{i}-tmp\) bits to the following entry
13:\(i\longleftarrow i+1\)
14:\(\}\)
15:return \(i-1\)
```
**Algorithm 2** Searching for \(\mathcal{E}(P)\) in \(T\) for Huffman coding. An additional complication for this variant is the need for a _security_ number to assure correctness. In Algorithm 1, the closest lexicographically preceding word is found once \(\ell_{i}\) is smaller than the longest common prefix we have already detected. Here, to guarantee that the word does really not appear, the condition has to be reinforced and we check that \(\mathcal{D}(\ell_{i})+security\) is still less than \(j\). To illustrate the need for that change, refer to the above mentioned canonical Huffman code and the dictionary of Table 2. Suppose we are searching for the pattern abtq, the encoded form of which is 110-10-00-111. Performing line 1.1 of Algorithm 2 we get that \(j=6\). As \(j<|\mathcal{E}(P)|=10\), we perform line 2.1. But as \(\mathcal{D}(\ell_{2})=5<j\), we would return FALSE, which is wrong. The security number gives us a security margin, forcing a closer analysis in the else clause. If we detect an entry the \(\ell_{i}\) component of which is less than the current longest match, we can be sure the word we are looking for is missing only if the difference is more than the length of the encoding of one character. Therefore, the _security_ number could be chosen as the maximum number of bits which are used to encode the characters of the alphabet, _i.e._, _security_\(=\max\limits_{c\in\Sigma}\{|\mathcal{E}(c)|\}\). As we deal only with the characters of the pattern, we can choose the security number to be the maximum number of bits needed to encode one of the characters of \(P\), _i.e._, _security_\(=\max\limits_{c\in P}\{|\mathcal{E}(c)|\}\). ## 4 Combining POM with Fibonacci Coding

In the previous section we used Huffman codes in order to perform compressed pattern matching on POM files. This way we could skip to the following entry by counting the bits with no need of decompressing the \(\sigma_{i}\) coordinates. We still had to decompress the \(\ell_{i}\) components for arithmetic comparison. A part of the processing time might be saved by using alternatives to Huffman codes which have recently been suggested, such as \((s,c)\)-dense codes [22] or Fibonacci codes [23], trading the optimality of Huffman's compression performance against improved decoding and search capabilities. In this section we present a pattern matching algorithm working on a POM file which has been compressed using a binary _Fibonacci code_. This is a universal variable length encoding of the integers based on the Fibonacci sequence rather than on powers of 2, and a subset of these encodings can be used as a fixed alternative to Huffman codes, giving obviously less compression, but adding simplicity (there is no need to generate a new code every time), robustness and speed [23,24]. The particular property of the Fibonacci encoding is that there are no adjacent 1's, so that the string 11 can act like a _comma_ between codewords, yielding the following sequence: \(\{11,\,011,\,0011,\,1011,\,00011,\,100011,\,100011,\,010011,\,001011,\,101011,\,0000011,\,\ldots\}\). More precisely, the codeword set consists of all the binary strings for which the substring 11 appears exactly once, at the right end of the string.