{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,2]],"date-time":"2025-03-02T05:59:18Z","timestamp":1740895158886,"version":"3.38.0"},"reference-count":72,"publisher":"Elsevier","isbn-type":[{"type":"print","value":"9780120121632"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1016\/s0065-2458(04)63006-3","type":"book-chapter","created":{"date-parts":[[2011,1,19]],"date-time":"2011-01-19T05:56:21Z","timestamp":1295416581000},"page":"207-262","source":"Crossref","is-referenced-by-count":0,"title":["Search and Retrieval of Compressed Text"],"prefix":"10.1016","author":[{"given":"Amar","family":"Mukherjee","sequence":"first","affiliation":[]},{"given":"Nan","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Tao","family":"Tao","sequence":"additional","affiliation":[]},{"given":"Ravi Vijaya","family":"Satya","sequence":"additional","affiliation":[]},{"given":"Weifeng","family":"Sun","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0065-2458(04)63006-3_bib001","series-title":"Proceedings, IEEE Data Compression Conference","first-page":"445","article-title":"Pattern matching in BWT- transformed text","author":"Adjeroh","year":"2002"},{"key":"10.1016\/S0065-2458(04)63006-3_bib002","unstructured":"Adjeroh D.A., Powell M., Zhang N., Mukherjee A., Bell T., \u201cPattern matching on BWT-text: Exact matching\u201d, Manuscript, 2002"},{"issue":"6","key":"10.1016\/S0065-2458(04)63006-3_bib003","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1145\/360825.360855","article-title":"Efficient string matching: An aid to bibliographic search","volume":"18","author":"Aho","year":"1975","journal-title":"Communications of the ACM"},{"key":"10.1016\/S0065-2458(04)63006-3_bib004","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":"Journal of Computer and System Sciences"},{"key":"10.1016\/S0065-2458(04)63006-3_bib005","series-title":"Combinatorial Pattern Matching","first-page":"320","article-title":"Alphabet independent and dictionary scaled matching","volume":"vol. 1075","author":"Amir","year":"1996"},{"key":"10.1016\/S0065-2458(04)63006-3_bib006","series-title":"Proceedings, Complexity and Compression of Sequences","article-title":"Matching for run-length encoded strings","author":"Apostolico","year":"1997"},{"key":"10.1016\/S0065-2458(04)63006-3_bib007","series-title":"Proceedings of the Conference on Data Compression","first-page":"193","article-title":"Move-to-front and inversion coding","author":"Arnavut","year":"2000"},{"year":"1999","series-title":"Modern Information Retrieval","author":"Baeza-Yates","key":"10.1016\/S0065-2458(04)63006-3_bib008"},{"key":"10.1016\/S0065-2458(04)63006-3_bib009","doi-asserted-by":"crossref","unstructured":"Barcaccia P., Cresti A., Agostino S.D., \u201cPattern matching in text compressed with the ID heuristic\u201d, 1998, pp. 113\u2014118","DOI":"10.1109\/DCC.1998.672137"},{"issue":"1","key":"10.1016\/S0065-2458(04)63006-3_bib010","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1093\/comjnl\/32.1.16","article-title":"A note on the DMC data compression scheme","volume":"32","author":"Bell","year":"1989","journal-title":"Computer Journal"},{"key":"10.1016\/S0065-2458(04)63006-3_bib011","series-title":"Proceedings, IEEE Data Compression Conference","first-page":"112","article-title":"Searching BWT compressed text with the Boyer\u2013Moore algorithm and binary search","author":"Bell","year":"2002"},{"key":"10.1016\/S0065-2458(04)63006-3_bib012","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1145\/5684.5688","article-title":"A locally adaptive data compression scheme","volume":"29","author":"Bentley","year":"1986","journal-title":"Communications of the ACM"},{"key":"10.1016\/S0065-2458(04)63006-3_bib013","series-title":"Proceedings of the 8th Annual ACM\u2013SIAM Symposium on Discrete Algorithms","first-page":"360","article-title":"Fast algorithms for sorting and searching strings","author":"Bentley","year":"1997"},{"issue":"10","key":"10.1016\/S0065-2458(04)63006-3_bib014","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1145\/359842.359859","article-title":"A fast string searching algorithm","volume":"20","author":"Boyer","year":"1977","journal-title":"Communications of the ACM"},{"key":"10.1016\/S0065-2458(04)63006-3_bib015","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/BF02243873","article-title":"An algorithm for matching run-length coded strings","volume":"50","author":"Bunke","year":"1993","journal-title":"Computing"},{"key":"10.1016\/S0065-2458(04)63006-3_bib016","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0020-0190(95)00005-W","article-title":"An improved algorithm for computing the edit distance of run-length coded strings","volume":"54","author":"Bunke","year":"1995","journal-title":"Information Processing Letters"},{"key":"10.1016\/S0065-2458(04)63006-3_bib017","unstructured":"Burrows M., Wheeler D., \u201cA block-sorting lossless data compression algorithm\u201d, Technical report, Digital Equipment Corporation, Palo Alto, CA, 1994"},{"key":"10.1016\/S0065-2458(04)63006-3_bib018","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1145\/568727.568730","article-title":"A general-purpose compression scheme for large collections","volume":"20","author":"Cannane","year":"2002","journal-title":"ACM Transactions on Information Systems"},{"issue":"5","key":"10.1016\/S0065-2458(04)63006-3_bib019","first-page":"1","article-title":"Unbounded length contexts for PPM","volume":"36","author":"Cleary","year":"1997","journal-title":"The Computer Journal"},{"key":"10.1016\/S0065-2458(04)63006-3_bib020","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1109\/TCOM.1984.1096090","article-title":"Data compression using adaptive coding and partial string matching","volume":"32","author":"Cleary","year":"1984","journal-title":"IEEE Transactions on Communications"},{"issue":"6","key":"10.1016\/S0065-2458(04)63006-3_bib021","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1093\/comjnl\/30.6.541","article-title":"Data compression using dynamic Markov modelling","volume":"30","author":"Cormack","year":"1987","journal-title":"Computer Journal"},{"key":"10.1016\/S0065-2458(04)63006-3_bib022","unstructured":"Corpus C, \u201cThe Canterbury Corpus\u201dhttp:\/\/corpus.canterbury.ac.nz, 2000"},{"key":"10.1016\/S0065-2458(04)63006-3_bib023","unstructured":"Corpus C, \u201cThe Calgary Corpus\u201d, ftp:\/\/ftp.cpsc.ucalgary.ca\/pub\/projects\/text.compression.corpus, 2000"},{"key":"10.1016\/S0065-2458(04)63006-3_bib024","unstructured":"Corpus G, \u201cThe Gutenberg Corpus\u201d, http:\/\/www.promo.net\/pg\/"},{"issue":"11","key":"10.1016\/S0065-2458(04)63006-3_bib025","doi-asserted-by":"crossref","first-page":"1756","DOI":"10.1109\/5.892711","article-title":"Data compression using antidictionaries","volume":"88","author":"Crochemore","year":"2000","journal-title":"Proceedings of the IEEE"},{"year":"1994","series-title":"Text Algorithms","author":"Crochemore","key":"10.1016\/S0065-2458(04)63006-3_bib026"},{"key":"10.1016\/S0065-2458(04)63006-3_bib027","series-title":"Proceedings of the 27th Annual ACM Symposium on the Theory of Computing","first-page":"703","article-title":"String matching in Lempel\u2013Ziv compressed strings","author":"Farach","year":"1995"},{"key":"10.1016\/S0065-2458(04)63006-3_bib028","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1007\/PL00009202","article-title":"String matching in Lempel\u2013Ziv compressed strings","volume":"20","author":"Farach","year":"1998","journal-title":"Algorithmica"},{"issue":"9","key":"10.1016\/S0065-2458(04)63006-3_bib029","doi-asserted-by":"crossref","first-page":"731","DOI":"10.1093\/comjnl\/39.9.731","article-title":"The Burrows\u2013Wheeler transform for block sorting text compression","volume":"39","author":"Fenwick","year":"1996","journal-title":"The Computer Journal"},{"key":"10.1016\/S0065-2458(04)63006-3_bib030","series-title":"Proceedings of the 3rd Forum on Research and Technology, Advances in Digital Libraries","first-page":"130","article-title":"Data compression using encrypted text","author":"Franceschini","year":"1996"},{"key":"10.1016\/S0065-2458(04)63006-3_bib031","unstructured":"Futamura N., Aluru S., Kurtz S., \u201cParallel sux sorting\u201d, 2001"},{"key":"10.1016\/S0065-2458(04)63006-3_bib032","series-title":"Proceedings, Combinatorial Pattern Matching","first-page":"39","article-title":"Randomized efficient algorithms for compressed strings: the finger-print approach","volume":"vol. 1075","author":"Gasieniec","year":"1996"},{"year":"1998","series-title":"Digital Compression for Multimedia: Principles and Standards","author":"Gibson","key":"10.1016\/S0065-2458(04)63006-3_bib033"},{"issue":"9","key":"10.1016\/S0065-2458(04)63006-3_bib034","doi-asserted-by":"crossref","first-page":"1098","DOI":"10.1109\/JRPROC.1952.273898","article-title":"A method for the construction of minimum redundancy codes","volume":"40","author":"Huffman","year":"1952","journal-title":"Proceedings of IRE"},{"key":"10.1016\/S0065-2458(04)63006-3_bib035","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/PL00009205","article-title":"Lempel\u2013Ziv index for q-grams","volume":"21","author":"Karkkainen","year":"1998","journal-title":"Algorithmica"},{"issue":"1","key":"10.1016\/S0065-2458(04)63006-3_bib036","article-title":"Multiple pattern matching in Izw compressed text","volume":"1","author":"Kida","year":"2000","journal-title":"Journal of Discrete Algorithm"},{"key":"10.1016\/S0065-2458(04)63006-3_bib037","series-title":"Proceedings, Data Compression Conference","first-page":"103","article-title":"Multiple pattern matching in Izw compressed text","author":"Kida","year":"1998"},{"key":"10.1016\/S0065-2458(04)63006-3_bib038","first-page":"18","article-title":"Parallel Lempel Ziv coding","volume":"vol. 2089","author":"Klein","year":"2001"},{"issue":"2","key":"10.1016\/S0065-2458(04)63006-3_bib039","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","article-title":"Fast pattern matching in strings","volume":"6","author":"Knuth","year":"1977","journal-title":"SIAM Journal of Computing"},{"issue":"2","key":"10.1016\/S0065-2458(04)63006-3_bib040","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1145\/358923.358934","article-title":"Information retrieval on the web","volume":"32","author":"Kobayashi","year":"2000","journal-title":"ACM Computing Surveys"},{"key":"10.1016\/S0065-2458(04)63006-3_bib041","series-title":"Proceedings of IEEE Data Compression Conference","article-title":"Preprocessing text to improve compression ratios","author":"Kruse","year":"1998"},{"author":"Lyman","key":"10.1016\/S0065-2458(04)63006-3_bib042"},{"key":"10.1016\/S0065-2458(04)63006-3_bib043","series-title":"Proceedings, Combinatorial Pattern Matching","first-page":"31","article-title":"Approximate matching of run-length compressed strings","author":"M\u00e4kinen","year":"2001"},{"issue":"2","key":"10.1016\/S0065-2458(04)63006-3_bib044","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 Transactions on Information Systems"},{"issue":"2","key":"10.1016\/S0065-2458(04)63006-3_bib045","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1109\/18.52489","article-title":"Linear time adaptive arithmetic coding","volume":"36","author":"Moffat","year":"1990","journal-title":"IEEE Transactions on Information Theory"},{"key":"10.1016\/S0065-2458(04)63006-3_bib046","series-title":"Proceedings of TREC Text Retrieval Conference","first-page":"181","article-title":"Retrieval of partial documents","author":"Moffat","year":"1993"},{"year":"2002","series-title":"Compression and Coding Algorithms","author":"Moffat","key":"10.1016\/S0065-2458(04)63006-3_bib047"},{"issue":"2","key":"10.1016\/S0065-2458(04)63006-3_bib048","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1145\/348751.348754","article-title":"Fast and flexible word searching on compressed text","volume":"18","author":"Moura","year":"2000","journal-title":"ACM Transactions on Information Systems"},{"key":"10.1016\/S0065-2458(04)63006-3_bib049","series-title":"Lossless Compression Handbook","article-title":"Text compression","author":"Mukherjee","year":"2002"},{"key":"10.1016\/S0065-2458(04)63006-3_bib050","series-title":"Proceedings, Combinatorial Pattern Matching","first-page":"14","article-title":"A general practical approach to pattern matching over Ziv\u2013Lempel compressed text","volume":"vol. 1645","author":"Navarro","year":"1999"},{"issue":"2","key":"10.1016\/S0065-2458(04)63006-3_bib051","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1147\/rd.232.0149","article-title":"Arithmetic coding","volume":"23","author":"Rissanen","year":"1979","journal-title":"IBM Journal of Research and Development"},{"year":"2000","series-title":"Data Compression: The Complete Reference","author":"Salomon","key":"10.1016\/S0065-2458(04)63006-3_bib052"},{"year":"2000","series-title":"Introduction to Data Compression","author":"Sayood","key":"10.1016\/S0065-2458(04)63006-3_bib053"},{"key":"10.1016\/S0065-2458(04)63006-3_bib054","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","article-title":"A mathematical theory of communication","volume":"27","author":"Shannon","year":"1948","journal-title":"Bell Systems Technical Journal"},{"key":"10.1016\/S0065-2458(04)63006-3_bib055","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1002\/j.1538-7305.1951.tb01366.x","article-title":"Prediction and entropy of printed English","volume":"30","author":"Shannon","year":"1951","journal-title":"Bell Systems Technical Journal"},{"year":"1998","series-title":"The Mathematical Theory of Communication","author":"Shannon","key":"10.1016\/S0065-2458(04)63006-3_bib056"},{"key":"10.1016\/S0065-2458(04)63006-3_bib057","unstructured":"Shibata Y., Kida T., Fukamachi S., Takeda T., Shinohara A., Shinohara S., Arikawa S., \u201cByte-pair encoding: A text compression scheme that accelerates pattern matching\u201d, Technical report, Department of Informatics, Kyushu University, Japan, 1999"},{"key":"10.1016\/S0065-2458(04)63006-3_bib058","series-title":"Proceedings, Combinatorial Pattern Matching","first-page":"37","article-title":"Pattern matching in text compressed by using antidictionaries","volume":"vol. 1645","author":"Shibata","year":"1999"},{"key":"10.1016\/S0065-2458(04)63006-3_bib059","unstructured":"Stauffer L.M., Hirschberg D.S., \u201cParallel text compression\u201d, Technical report, University of California, Irvine, CA, 1993"},{"key":"10.1016\/S0065-2458(04)63006-3_bib060","series-title":"Proceedings of IEEE Data Compression Conference","article-title":"LZW based compressed pattern matching","author":"Tao","year":"2004"},{"key":"10.1016\/S0065-2458(04)63006-3_bib061","series-title":"Data Compression Conference","first-page":"53","article-title":"The entropy of English using PPM-based models","author":"Teahan","year":"1996"},{"key":"10.1016\/S0065-2458(04)63006-3_bib063","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1109\/MC.1984.1659158","article-title":"A technique for high performance data compression","volume":"17","author":"Welch","year":"1984","journal-title":"IEEE Computer"},{"year":"1999","series-title":"Managing Gigabytes: Compressing and Indexing Documents and Images","author":"Witten","key":"10.1016\/S0065-2458(04)63006-3_bib064"},{"key":"10.1016\/S0065-2458(04)63006-3_bib065","series-title":"Proceedings of Data Compression Conference, Snowbird, UT","article-title":"Approximate pattern matching using the burrows-wheeler transform","author":"Zhang","year":"2003"},{"key":"10.1016\/S0065-2458(04)63006-3_bib066","series-title":"Proceedings of International Conference on Information Technology: Coding and Computing, Las Vegas, NV","first-page":"224","article-title":"Modified LZW algorithm for efficient compressed text retrieval","author":"Zhang","year":"2004"},{"key":"10.1016\/S0065-2458(04)63006-3_bib067","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","article-title":"A universal algorithm for sequential data compression","volume":"IT-23","author":"Ziv","year":"1977","journal-title":"IEEE Transactions on Information Theory"},{"key":"10.1016\/S0065-2458(04)63006-3_bib068","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","article-title":"Compression of individual sequences via variable rate coding","volume":"IT-24","author":"Ziv","year":"1978","journal-title":"IEEE Transactions on Information Theory"},{"issue":"11","key":"10.1016\/S0065-2458(04)63006-3_bib069","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1109\/2.881693","article-title":"Compression: A key for next generation text retrieval systems","volume":"33","author":"Ziviani","year":"2000","journal-title":"IEEE Computer"},{"year":"1997","series-title":"Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology","author":"Gusfield","key":"10.1016\/S0065-2458(04)63006-3_bib070"},{"key":"10.1016\/S0065-2458(04)63006-3_bib071","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/BF01185432","article-title":"A sublinear algorithm for approximate keyword searching","volume":"12","author":"Myers","year":"1994","journal-title":"Algorithmica"},{"issue":"1","key":"10.1016\/S0065-2458(04)63006-3_bib072","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/375360.375365","article-title":"A guided tour of approximate string matching","volume":"33","author":"Navarro","year":"2001","journal-title":"ACM Computing Surveys"},{"key":"10.1016\/S0065-2458(04)63006-3_bib073","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0196-6774(85)90023-9","article-title":"Finding approximate patterns in strings","volume":"6","author":"Ukkonen","year":"1985","journal-title":"Journal of Algorithms"}],"container-title":["Advances in Computers"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T22:32:52Z","timestamp":1740868372000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0065245804630063"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9780120121632"],"references-count":72,"URL":"https:\/\/doi.org\/10.1016\/s0065-2458(04)63006-3","relation":{},"ISSN":["0065-2458"],"issn-type":[{"type":"print","value":"0065-2458"}],"subject":[],"published":{"date-parts":[[2005]]}}}