## 2 Pattern Matching in POM Encoded Dictionaries
The specific order of the sequence above, which is used in the coding algorithms, is obtained as follows: just as any integer \(k\) has a standard binary representation, that is, it can be uniquely represented as a sum of powers of 2, \(k=\sum_{i\geq 0}b_{i}2^{i}\), with \(b_{i}\in\{0,1\}\), there is another possible binary representation based on Fibonacci numbers, \(k=\sum_{i\geq 0}f_{i}F(i)\), with \(f_{i}\in\{0,1\}\), where it is convenient to define the Fibonacci sequence here by \(F(0)=1\), \(F(1)=2\) and \(F(i)=F(i-1)+F(i-2)\) for \(i\geq 2\). This \begin{table}
\begin{tabular}{c c c c} \hline \hline \(i\) & **Dictionary** & **POM** & **POM \& Huffman** \\  & **Entry** & \((\boldsymbol{\ell_{i},n_{i},\sigma_{i}})\) & \(\boldsymbol{\ell_{i},n_{i}}\) **refer to bits** \\ \hline
1 & abc & (0, 3, abc) & (0, 7, 110-10-01) \\
2 & abqt & (2, 2, qt) & (5, 5, 111-00) \\
3 & abtq & (2, 2, tq) & (5, 5, 00-111) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Example for the need of a security number. Fibonacci representation will be unique if, when encoding an integer, one repeatedly tries to fit in the largest possible Fibonacci number. For example, the largest Fibonacci number fitting into 19 is 13, for the remainder 6 one can use the Fibonacci number 5, and the remainder 1 is a Fibonacci number itself. So one would represent 19 as \(19=13+5+1\), yielding the binary string 101001. Note that the bit positions correspond to \(F(i)\) for increasing values of \(i\) from right to left, just as for the standard binary representation, in which \(19=16+2+1\) would be represented by 10011. Each such Fibonacci representation starts with a 1, so by preceding it with an additional 1, one gets a set of uniquely decipherable codewords. Decoding, however, would not be instantaneous, because the set lacks the prefix property, but this can be overcome by simply reversing each of the codewords, which yields the sequence above. The adjacent 1s are then at the right instead of at the left end of each codeword, e.g., the codeword corresponding to 19 would be 1001011. In our case, we wish to encode dictionary entries, each consisting of several codewords. We know already how to parse an encoded string into its constituting codewords, what still is needed is a separator between adjacent dictionary entries. At first sight it seems that just an additional 1-bit would be enough, since the pattern 111 never appears within a codeword. However, a sequence of 3 consecutive ones can appear _between_ adjacent codewords, as in 011-1011. Therefore we must add _two_ 1-bits as separators between dictionary entries. The additional expense is alleviated by the fact that the \(n_{i}\) component becomes redundant and can be omitted, so that the compressed dictionary will contain only the Fibonacci compressed forms of the \(\ell_{i}\) and \(\sigma_{i}\) fields. There is, however, a problem with the first codeword 11, which is exceptional, being the only one which does not have the suffix 011. Our goal is to be able to jump to the beginning of the following dictionary entry without having to decode the current one completely. If the first codeword 11 were to be omitted, one could then simply search for the next occurrence of the string 01111, but if 11 is permitted, a sequence of 1's of any length could appear, so no separator would be possible. Our first solution is thus simply omitting 11 from the Fibonacci code, which comes at the price of adding one bit to each codeword which is the last one of a block of codewords of the same length. Table 3 compares the storage performance of the two Fibonacci encodings with or without 11, on three test dictionaries of different sizes. Details on the test files are given in the next section. The first column gives the size, in bytes, of the uncompressed dictionaries, the second and third columns the sizes of the POM-Fibonacci compressed dictionaries, without and with the use of the first codeword 11, respectively. As can be seen, it is worth eliminating the 11 codeword, though the difference is small.