## 2 Pattern Matching in POM Encoded Dictionaries \begin{table}
\begin{tabular}{l l l l} \hline \hline \multirow{2}{*}{**Dictionary**} & \multirow{2}{*}{**POM**} & \multicolumn{2}{c}{**POM + Huffman Coding**} \\  & & **with Preserving Codeword Boundaries** & **without \(\ldots\)** \\ \hline compress & (0,8, compress) & (0,35,11001-0101-1111000.1001-000-1000-1000) & (0,35,\(\cdots\)) \\ compression & (8,3, ion) & (35,12/0110-0101-0111) & (35,12,\(\cdots\)) \\ comprise & (5,3, ise) & (24,11/0110-1000-000) & (25,10,110 \(\cdots\)) \\ compromise & (5,5, omise) & (24,20,0101-1101-0110-1000-000) & (26,18,01\(\cdots\)) \\ compulsion & (4,6, ulusion) & (20,26,1000-1011-000-0010-0101-0111) & (21,25,1000 \(\cdots\)) \\ compulsive & (8,2, ve) & (38,9,11110-000) & (38,9,\(\cdots\)) \\ compulsory & (7,3, my) & (34,14,0101-1001-111010) & (36,12,01\(\cdots\)) \\ compunction & (5,6, nction) & (25,24,0111-11001-001-0110-0111) & (25,24,\(\cdots\)) \\ computation & (5,6, tation) & (25,22,001-0100-001-0110-0101-0111) & (26,21,01\(\cdots\)) \\ compute & (6,1, e) & (28,3,000) & (29,200) \\ computer & (7,1, r) & (31,4,1001) & (31,4,1001) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Example POM and the combined POM + Huffman. The prefix omission method was apparently first mentioned by [PERSON] and [PERSON] [20]. It is based on the observation that in a dictionary of a natural language text, two consecutive entries will usually have a few leading letters in common. Therefore we eliminate these letters from the second entry, while adding to it the number of letters eliminated and to be copied from the previous entry. Since the entries have now variable length, their boundaries have to be identified, for example by adding a field representing the number of characters of the suffix string in the current entry, that is, the number of characters remaining after eliminating the prefix characters. More formally, we relate to the compressed form of the \(i\)-th entry \(X_{i}\) as an ordered triple (\(\ell_{i}\),\(n_{i}\),\(\sigma_{i}\)), where \(\ell_{i}\) is the number of characters copied from the beginning of the previous (uncompressed) entry \(X_{i-1}\), \(\sigma_{i}\) is the remaining suffix and \(n_{i}\) is the length of this suffix, _i.e._, \(n_{i}=|\sigma_{i}|\). Consider the example given in Table 1. The first column is a list of some consecutive words which were taken from the Oxford Dictionary of current English. The following column gives the compressed form of these words using the prefix omission method (the last two columns are referred to below, in Section 3). Often the POM files are further compressed by some general method \(\mathcal{E}\), such as gzip, in order to reduce space. Accessing the dictionary itself is then done in two stages: first decompressing the file \(T\) by the corresponding decompression function \(\mathcal{D}=\mathcal{E}^{-1}\) and then reversing the POM file, or more formally, searching for the pattern \(P\) in POM\({}^{-1}(\mathcal{D}(T))\). The following algorithm, adapted from [20], is more direct. Let \(P=p_{1}\cdots p_{m}\) denote the pattern of length \(m\) to be searched for, and \(P[i,j]\) the sub-pattern \(p_{i}\cdots p_{j}\), _i.e._, \(P[i,j]\) is the sub-pattern of \(P\), starting at position \(i\) and ending at position \(j\), both included. Let \(\mathcal{E}\) and \(\mathcal{D}\) denote two complementing encoding and decoding functions. Given two strings \(S=s_{1}\ \cdots\ s_{k}\) and \(T=t_{1}\cdots t_{\ell}\) the function \(pre(S,T)\) returns the length of the longest common prefix of the two strings (or zero, if this prefix is empty), that is  
\[s_{i}=t_{i}\quad\text{ for }\ 1\leq i\leq pre(S,T),\] \[\text{ and }\quad\min(k,\ell)>pre(S,T)\ \longrightarrow\quad s_{j}\
eq t_{j}\quad\text{ for }\ j=pre(S,T)+1.\]  
To formulate it in words, the first \(pre(S,T)\) characters of \(S\) and \(T\) are identical, but the character indexed \(pre(S,T)+1\) differs, if such an index exists for both \(S\) and \(T\). In particular, \(pre(S,T)=|S|\) if \(S\) is a prefix of \(T\).