## 2 Pattern Matching in POM Encoded Dictionaries
On the other hand, one can get much faster processing using tries, rather than sequential search, but for small dictionaries, compression will then be inferior. ## Acknowledgment

The authors wish to thank two anonymous referees for their useful remarks and [PERSON] for his help with the implementation of the experiments. ## References

* [PERSON] and [PERSON] (1992) [PERSON]; [PERSON] Efficient two-dimensional compressed matching. In _Proceeding of Data Compression Conference DCC'92_, Snowbird, UT, USA, March 24-27, 1992; pp. 279-288. * [PERSON] and [PERSON] (2002) [PERSON]; [PERSON] Compressed matching in dictionaries. In _Proceeding of Data Compression Conference DCC'02_, Snowbird, UT, USA, 2002; pp. 142-151. * [PERSON] and [PERSON] (2005) [PERSON]; [PERSON] Pattern matching in Huffman encoded texts. _Inform. Process. Manage._**2005**, _41_, 829-841. * [PERSON] et al. (1996) [PERSON]; [PERSON]; [PERSON] Let sleeping files lie: Pattern matching in Z-compressed files. _J. Comput. Syst. Sci._**1996**, _52_, 299-307. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**File** & **size** & **Huffman** & **Fibonacci** & **decode \(+\) search** & **LZ trie** \\ \hline bib1 & 2044 & 6.7 & 2.8 & 7.7 &.02 \\ bib2 & 4095 & 7.5 & 3.7 & 8.8 &.01 \\ bib3 & 8067 & 8.4 & 4.9 & 8.9 &.01 \\ bib4 & 16,199 & 9.9 & 6.8 & 10.1 &.01 \\ xml1 & 2047 & 7.3 & 3.2 & 7.0 &.01 \\ xml2 & 4093 & 7.9 & 3.8 & 7.6 &.01 \\ xml3 & 8190 & 8.5 & 4.7 & 8.3 &.02 \\ xml4 & 16,383 & 9.7 & 6.1 & 9.7 &.02 \\ Hebbib & 253,230 & 50 & 65 & 64 &.02 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Empirical comparison of processing time. * [5] [PERSON]; [PERSON] String matching in Lempel-Ziv compressed strings. In _Proceedings of 27 th Annual ACM Symposium on the Theory of Computing_, New York, NY, USA, 1995, 703-712. * [6] [PERSON]; [PERSON] A general practical approach to pattern matching over Ziv-Lempel compressed text. _Lect. Notes Comput. Sci._**1999**, _1645_, 14-36. * [7] [PERSON]; [PERSON] A new compression method for compressed matching. In _Proceedings of Data Compression Conference DCC'00_, Snowbird, UT, March, 2000; pp. 400-409. * [8] [PERSON] A text compression scheme that allows fast searching directly in the compressed file. _ACM Trans. Inform. Syst._**1997**, _15_, 124-136. * [9] [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON] Faster approximate string matching over compressed text. In _Proceedings of Data Compression Conference DCC'01_, Snowbird, UT, USA, March 2001; pp. 459-468. * [10] [PERSON]; [PERSON] Block-oriented compression techniques for large statistical Databases. _IEEE Trans. Knowl. Data. Eng._**1997**, \(9\), 314-328. * [11] [PERSON]; [PERSON] _XML Structure Compression_; Technical Report BBKCS-02-05; University of London: London, UK; 2002. * [12] [PERSON]; [PERSON] XMill: An efficient compressor for XML data. In _proeedings of ACM SIGMOD Conference_, New York, NY, USA, June 2000; pp. 153-164. * [13] [PERSON] Compressing XML with multiplexed hierarchical PPM models. In _proceedings of IEEE Data Compression Conference DCC'01_, Snowbird, UT, USA, March 2001; pp. 163-172. * [14] [PERSON]; [PERSON] [PERSON] XGRIND: A query-friendly XML compressor. In _proceedings of 18 th International Conference on Data Engineering ICDE'02_, San Jose, CA, USA, February 26-March 01, 2002; pp. 225-234. * [15] XMLSolutions, XMLZip. Available online: [[http://www.xmls.com](http://www.xmls.com)]([http://www.xmls.com](http://www.xmls.com)) (accessed on 30 January 2011). * [16] [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON] Engineering the compression of massive tables: An experimental approach. In _proceedings of 10 th ACM SIAM Symp. on Discrete Algorithms SODA'00_, New York, NY, USA, February 2000; pp. 175-184. * [17] [PERSON]; [PERSON]; [PERSON] Improving compression with combinatorial optimization. _J. ACM_**2003**, _50_, 825-851. * [18] [PERSON] [PERSON] Responsa: A full-text retrieval system with linguistic processing for a 65-million word corpus of Jewish heritage in Hebrew. _IEEE Data Eng. Bull._**1989**, _14_, 22-31.