{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:22:05Z","timestamp":1759638125710},"reference-count":30,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2020,4,13]],"date-time":"2020-04-13T00:00:00Z","timestamp":1586736000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,5,19]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>An alternative to compressed suffix arrays is introduced, based on representing a sequence of integers using Fibonacci encodings, thereby reducing the space requirements of state-of-the-art implementations of the suffix array, while retaining the searching functionalities. Empirical tests support the theoretical space complexity improvements and show that there is no deterioration in the processing times.<\/jats:p>","DOI":"10.1093\/comjnl\/bxaa016","type":"journal-article","created":{"date-parts":[[2020,2,12]],"date-time":"2020-02-12T12:10:35Z","timestamp":1581509435000},"page":"721-730","source":"Crossref","is-referenced-by-count":7,"title":["Smaller Compressed Suffix Arrays\u2020"],"prefix":"10.1093","volume":"64","author":[{"given":"Ekaterina","family":"Benza","sequence":"first","affiliation":[{"name":"Department of Computer Science, Ariel University, Ariel 40700, Israel"}]},{"given":"Shmuel T","family":"Klein","sequence":"additional","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, Ariel University, Ariel 40700, Israel"}]}],"member":"286","published-online":{"date-parts":[[2020,4,13]]},"reference":[{"key":"2021052810194491300_ref1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781316588284","volume-title":"Compact Data Structures\u2014A Practical Approach","author":"Navarro","year":"2016"},{"key":"2021052810194491300_ref2","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1109\/SFCS.1989.63533","article-title":"Space-Efficient Static Trees and Graphs","volume-title":"Proc. 30th Annual Symposium on Foundations of Computer Science","author":"Jacobson","year":"1989"},{"key":"2021052810194491300_ref3","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/1290672.1290680","article-title":"Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets","volume":"3","author":"Raman","year":"2007","journal-title":"ACM Trans. Algorithms"},{"key":"2021052810194491300_ref4","first-page":"295","article-title":"Fast, small, simple rank\/select on bitmaps","volume-title":"Experimental Algorithms\u2014Proc. 11th Int. Symposium, SEA 2012, Bordeaux, France, June 7\u20139","author":"Navarro","year":"2012"},{"key":"2021052810194491300_ref5","article-title":"High-Order Entropy-Compressed Text Indexes","volume-title":"Proc. 14th ACM-SIAM Symposium on Discrete Algorithms, Baltimore, Maryland, January 12\u201314","author":"Grossi","year":"2003"},{"key":"2021052810194491300_ref6","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1007\/s10791-012-9184-1","article-title":"Implicit indexing of natural language text by reorganizing bytecodes","volume":"15","author":"Brisaboa","year":"2012","journal-title":"Inf. Retr."},{"key":"2021052810194491300_ref7","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1016\/j.ipm.2012.08.003","article-title":"DACs: bringing direct access to variable-length codes","volume":"49","author":"Brisaboa","year":"2013","journal-title":"Inf. Process. Manage."},{"key":"2021052810194491300_ref8","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1109\/DCC.2014.74","article-title":"Enhanced Variable-Length Codes: Improved Compression With Efficient Random Access","volume-title":"Proc. Data Compression Conference, DCC 2014, Snowbird, UT, USA, 26\u201328 March","author":"K\u00fclekci","year":"2014"},{"key":"2021052810194491300_ref9","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1016\/j.tcs.2015.12.021","article-title":"Compressed matching for feature vectors","volume":"638","author":"Klein","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"2021052810194491300_ref10","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.dam.2018.07.016","article-title":"Accelerated partial decoding in wavelet trees","volume":"274","author":"Baruch","year":"2020","journal-title":"Discrete Appl. Math."},{"key":"2021052810194491300_ref11","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1016\/j.jda.2016.12.001","article-title":"A space efficient direct access data structure","volume":"43","author":"Baruch","year":"2017","journal-title":"J. Discrete Algorithms"},{"key":"2021052810194491300_ref12","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1137\/S0097539702402354","article-title":"Compressed suffix arrays and suffix trees with applications to text indexing and string matching","volume":"35","author":"Grossi","year":"2005","journal-title":"SIAM J. Comput."},{"key":"2021052810194491300_ref13","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0222058","article-title":"Suffix arrays: a new method for on-line string searches","volume":"22","author":"Manber","year":"1993","journal-title":"SIAM J. Comput."},{"key":"2021052810194491300_ref14","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1016\/S0196-6774(03)00087-7","article-title":"New text indexing functionalities of the compressed suffix arrays","volume":"48","author":"Sadakane","year":"2003","journal-title":"J. Algorithms"},{"key":"2021052810194491300_ref15","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1145\/1082036.1082039","article-title":"Indexing compressed text","volume":"52","author":"Ferragina","year":"2005","journal-title":"J. ACM"},{"key":"2021052810194491300_ref16","article-title":"A Block Sorting Lossless Data Compression Algorithm","author":"Burrows","year":"1994"},{"key":"2021052810194491300_ref17","doi-asserted-by":"crossref","DOI":"10.1109\/DCC.2014.49","article-title":"A Practical Implementation of Compressed Suffix Arrays With Applications to Self-Indexing","volume-title":"Proc. Data Compression Conference, DCC 2014, Snowbird, UT, USA","author":"Huo","year":"2014"},{"key":"2021052810194491300_ref18","doi-asserted-by":"crossref","DOI":"10.1109\/DCC.2016.58","article-title":"CS2A: A Compressed Suffix Array-Based Method for Short Read Alignment","volume-title":"Proc. Data Compression Conference, DCC 2016, Snowbird, UT, USA, March 30\u2013April 1","author":"Huo","year":"2016"},{"key":"2021052810194491300_ref19","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1109\/TIT.1975.1055349","article-title":"Universal codeword sets and representations of the integers","volume":"21","author":"Elias","year":"1975","journal-title":"IEEE Trans. Information Theory"},{"key":"2021052810194491300_ref20","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-36618-0_33","article-title":"An Efficient Compression Code for Text Databases","volume-title":"Advances in Information Retrieval, Proc. 25th European Conference on IR Research, ECIR 2003, Pisa, Italy, April 14\u201316","author":"Brisaboa","year":"2003"},{"key":"2021052810194491300_ref21","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1007\/978-3-540-39984-1_10","article-title":"$\\left (\\mathrm{s},\\mathrm{c}\\right )$-Dense Coding: An Optimized Compression Code for Natural Language Text Databases","volume-title":"Proc. 10th Symposium on String Processing and Information Retrieval, SPIRE 2003, Manaus, Brazil, October 8\u201310","author":"Brisaboa","year":"2003"},{"key":"2021052810194491300_ref22","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1109\/TIT.1987.1057284","article-title":"Robust transmission of unbounded strings using Fibonacci representations","volume":"33","author":"Apostolico","year":"1987","journal-title":"IEEE Trans. Information Theory"},{"key":"2021052810194491300_ref23","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.dam.2015.11.003","article-title":"Random access to Fibonacci encoded files","volume":"212","author":"Klein","year":"2016","journal-title":"Discrete Appl. Math."},{"key":"2021052810194491300_ref24","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":"2021052810194491300_ref25","doi-asserted-by":"crossref","first-page":"1297","DOI":"10.1142\/S012905410600442X","article-title":"Compressed pattern matching in JPEG images","volume":"17","author":"Klein","year":"2006","journal-title":"Int. J. Found. Comput. Sci."},{"key":"2021052810194491300_ref26","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1093\/comjnl\/bxy020","article-title":"Context sensitive rewriting codes for flash memory","volume":"62","author":"Klein","year":"2019","journal-title":"Comput. J."},{"key":"2021052810194491300_ref27","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":"2021052810194491300_ref28","first-page":"273","article-title":"Partitioned Elias\u2013Fano Indexes","volume-title":"The 37th Conference on Research and Development in Information Retrieval, SIGIR\u201914, Gold Coast, QLD, Australia, July 06\u201311","author":"Ottaviano","year":"2014"},{"key":"2021052810194491300_ref29","first-page":"73","article-title":"CSA++: Fast Pattern Search for Large Alphabets","volume-title":"Proc. 19th Workshop on Algorithm Engineering and Experiments, ALENEX 2017","author":"Gog","year":"2017"},{"key":"2021052810194491300_ref30","first-page":"3","article-title":"Fibonacci Based Compressed Suffix Array","volume-title":"Prague Stringology Conference 2018, Prague, Czech Republic, August 27\u201328, 2018","author":"Benza","year":"2018"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/64\/5\/721\/38334902\/bxaa016.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/64\/5\/721\/38334902\/bxaa016.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,26]],"date-time":"2023-09-26T19:18:23Z","timestamp":1695755903000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/64\/5\/721\/5819212"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,13]]},"references-count":30,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2020,4,13]]},"published-print":{"date-parts":[[2021,5,19]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxaa016","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,5]]},"published":{"date-parts":[[2020,4,13]]}}}