{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:40:20Z","timestamp":1775281220194,"version":"3.50.1"},"reference-count":25,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2011,3,22]],"date-time":"2011-03-22T00:00:00Z","timestamp":1300752000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The problem of compressed pattern matching, which has recently been treated in many papers dealing with free text, is extended to structured files, specifically to dictionaries, which appear in any full-text retrieval system. The prefix-omission method is combined with Huffman coding and a new variant based on Fibonacci codes is presented. Experimental results suggest that the new methods are often preferable to earlier ones, in particular for small files which are typical for dictionaries, since these are usually kept in small chunks.<\/jats:p>","DOI":"10.3390\/a4010061","type":"journal-article","created":{"date-parts":[[2011,3,25]],"date-time":"2011-03-25T11:14:25Z","timestamp":1301051665000},"page":"61-74","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Compressed Matching in Dictionaries"],"prefix":"10.3390","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9478-3303","authenticated-orcid":false,"given":"Shmuel T.","family":"Klein","sequence":"first","affiliation":[{"name":"Department of Computer Science, Bar Ilan University, Ramat-Gan 52900, Israel"}]},{"given":"Dana","family":"Shapira","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Ashkelon Academic College, Ashkelon, Israel"}]}],"member":"1968","published-online":{"date-parts":[[2011,3,22]]},"reference":[{"key":"ref_1","unstructured":"Amir, A., and Benson, G. (1992, January March). Efficient two-dimensional compressed matching. Snowbird, UT, USA."},{"key":"ref_2","unstructured":"Klein, S.T., and Shapira, D. Compressed matching in dictionaries. Snowbird, UT, USA."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"829","DOI":"10.1016\/j.ipm.2003.08.008","article-title":"Pattern matching in Huffman encoded texts","volume":"41","author":"Klein","year":"2005","journal-title":"Inform. Process. Manage."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1006\/jcss.1996.0023","article-title":"Let sleeping files lie: Pattern matching in Z-compressed files","volume":"52","author":"Amir","year":"1996","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_5","unstructured":"Farach, M., and Thorup, M. String matching in Lempel-Ziv compressed strings. New York, NY, USA."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1007\/3-540-48452-3_2","article-title":"A general practical approach to pattern matching over Ziv-Lempel compressed text","volume":"1645","author":"Navarro","year":"1999","journal-title":"Lect. Notes Comput. Sci."},{"key":"ref_7","unstructured":"Klein, S.T., and Shapira, D. (, January March,). A new compression method for compressed matching. Snowbird, UT."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1145\/248625.248639","article-title":"A text compression scheme that allows fast searching directly in the compressed file","volume":"15","author":"Manber","year":"1997","journal-title":"ACM Trans. Inform. Syst."},{"key":"ref_9","unstructured":"Navarro, G., Kida, T., Takeda, M., Shinohara, A., and Arikawa, S. (, January March). Faster approximate string matching over compressed text. Snowbird, UT, USA."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"314","DOI":"10.1109\/69.591455","article-title":"Block-oriented compression techniques for large statistical Databases","volume":"9","author":"Ng","year":"1997","journal-title":"IEEE Trans. Knowl. Data. Eng."},{"key":"ref_11","unstructured":"Levene, M., and Wood, P. (2002). XML Structure Compression, University of London. Technical Report BBKCS-02-05."},{"key":"ref_12","unstructured":"Liefke, H., and Suciu, D. (, January June). XMill: An efficient compressor for XML data. New York, NY, USA."},{"key":"ref_13","unstructured":"Cheney, J. (, January March). Compressing XML with multiplexed hierarchical PPM models. Snowbird, UT, USA."},{"key":"ref_14","unstructured":"Tolani, P.M., and Haritsa, J.R. (01,, January February). XGRIND: A query-friendly XML compressor. San Jose, CA, USA."},{"key":"ref_15","unstructured":"XMLSolutions, XMLZip. Available online: http:\/\/www.xmls.com (accessed on 30 January 2011)."},{"key":"ref_16","unstructured":"Buchsbaum, A.L., Caldwell, D.F., Church, K.W., Fowler, G.S., and Muthukrishnan, S. (, January February). Engineering the compression of massive tables: An experimental approach. New York, NY, USA."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"825","DOI":"10.1145\/950620.950622","article-title":"Improving compression with combinatorial optimization","volume":"50","author":"Buchsbaum","year":"2003","journal-title":"J. ACM"},{"key":"ref_18","first-page":"22","article-title":"Responsa: A full-text retrieval system with linguistic processing for a 65-million word corpus of Jewish heritage in Hebrew","volume":"14","author":"Choueka","year":"1989","journal-title":"IEEE Data Eng. Bull."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1016\/0306-4573(92)90069-C","article-title":"A systematic approach to compressing a full text retrieval system","volume":"28","author":"Bookstein","year":"1992","journal-title":"Inform. Process. Manage."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/0306-4573(82)90004-8","article-title":"Processing Truncated Terms in Document Retrieval Systems","volume":"18","author":"Bratley","year":"1982","journal-title":"Inform. Process. Manage."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1023\/A:1009910017828","article-title":"Skeleton trees for efficient decoding of Huffman encoded texts","volume":"3","author":"Klein","year":"2000","journal-title":"Inf. Retr."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1007\/978-3-540-39984-1_10","article-title":"(S,C)-dense coding: An optimized compression code for natural language text databases","volume":"2857","author":"Brisaboa","year":"2003","journal-title":"Lect. Notes Comput. Sci."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1093\/comjnl\/bxp046","article-title":"On the usefulness of fibonacci compression codes","volume":"53","author":"Klein","year":"2010","journal-title":"Comput. J."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/0166-218X(93)00116-H","article-title":"Robust universal complete codes for transmission and compression","volume":"64","author":"Fraenkel","year":"1996","journal-title":"Discrete. Appl. Math."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1007\/3-540-48452-3_15","article-title":"Ziv Lempel compression of huge natural language data tries using suffix arrays","volume":"1645","author":"Ristov","year":"1999","journal-title":"Lect. Notes Comput. Sci."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/4\/1\/61\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:55:36Z","timestamp":1760219736000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/4\/1\/61"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3,22]]},"references-count":25,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2011,3]]}},"alternative-id":["a4010061"],"URL":"https:\/\/doi.org\/10.3390\/a4010061","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,3,22]]}}}