{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,26]],"date-time":"2023-10-26T14:11:27Z","timestamp":1698329487652},"reference-count":20,"publisher":"Wiley","issue":"7","license":[{"start":{"date-parts":[[2006,10,30]],"date-time":"2006-10-30T00:00:00Z","timestamp":1162166400000},"content-version":"vor","delay-in-days":4869,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Softw Pract Exp"],"published-print":{"date-parts":[[1993,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Ziv\u2010Lempel coding is currently one of the more practical data compression schemes. It operates by replacing a substring of a text with a pointer to its longest previous occurrence in the input, for each coding step. Decoding a compressed file is very fast, but encoding involves searching at each coding step to find the longest match for the next few characters. This paper presents eight data structures that can be used to accelerate the searching, including adaptations of four methods normally used for exact matching searching. The algorithms are evaluated analytically and empirically, indicating the trade\u2010offs available between compression speed and memory consumption. Two of the algorithms are well\u2010known methods of finding the longest match\u2014the time\u2010consuming linear search, and the storage\u2010intensive trie (digital search tree). The trie is adapted along the lines of a PATRICIA tree to operate economically. Hashing, binary search trees, splay trees and the Boyer\u2010Moore searching algorithm are traditionally used to search for exact matches, but we show how these can be adapted to find longest matches. In addition, two data structures specifically designed for the application are presented.<\/jats:p>","DOI":"10.1002\/spe.4380230705","type":"journal-article","created":{"date-parts":[[2006,11,17]],"date-time":"2006-11-17T16:43:12Z","timestamp":1163781792000},"page":"757-771","source":"Crossref","is-referenced-by-count":11,"title":["Longest\u2010match string searching for ziv\u2010lempel compression"],"prefix":"10.1002","volume":"23","author":[{"given":"Timothy","family":"Bell","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Kulp","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,30]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1984.1096090"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/30.6.541"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/214762.214771"},{"issue":"3","key":"e_1_2_1_4_3","first-page":"4","volume":"2","year":"1987","journal-title":"C Gazette"},{"key":"e_1_2_1_5_2","volume-title":"Text Compression","author":"Bell T. C.","year":"1990"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1977.1055714"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055934"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/322344.322346"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1986.1096485"},{"issue":"2","key":"e_1_2_1_10_2","first-page":"64","article-title":"A linear algorithm for data compression","volume":"19","author":"Brent R. P.","year":"1987","journal-title":"Australian Computer Journal"},{"key":"e_1_2_1_11_2","unstructured":"T. C.Bell \u2018A unifying theory and improvements for existing approaches to text compression\u2019 Ph.D. Thesis Department of Computer Science University of Canterbury Christchurch New Zealand 1987."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/0206024"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/359842.359859"},{"key":"e_1_2_1_14_2","unstructured":"D. C.Kulp \u2018Very fast pattern matching for highly repetitive text\u2019 Technical Report Department of Computer Science University of Canterbury 1992."},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/321479.321481"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321946"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322237"},{"key":"e_1_2_1_18_2","doi-asserted-by":"crossref","unstructured":"T.RaitaandJ.Teuhola \u2018Predictive text compression by hashing\u2019 ACM Conference on Information Retrieval New Orleans 1987.","DOI":"10.1145\/42005.42031"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/63334.63341"}],"container-title":["Software: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fspe.4380230705","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/spe.4380230705","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T03:41:13Z","timestamp":1698205273000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/spe.4380230705"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,7]]},"references-count":20,"journal-issue":{"issue":"7","published-print":{"date-parts":[[1993,7]]}},"alternative-id":["10.1002\/spe.4380230705"],"URL":"https:\/\/doi.org\/10.1002\/spe.4380230705","archive":["Portico"],"relation":{},"ISSN":["0038-0644","1097-024X"],"issn-type":[{"value":"0038-0644","type":"print"},{"value":"1097-024X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,7]]}}}