{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,2]],"date-time":"2024-01-02T15:02:26Z","timestamp":1704207746481},"reference-count":7,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2006,12]]},"abstract":"<jats:p> We design a succinct full-text index based on the idea of Huffman-compressing the text and then applying the Burrows-Wheeler transform over it. The resulting structure can be searched as an FM-index, with the benefit of removing the sharp dependence on the alphabet size, \u03c3, present in that structure. On a text of length n with zero-order entropy H<jats:sub>0<\/jats:sub>, our index needs O(n(H<jats:sub>0<\/jats:sub> + 1)) bits of space, without any significant dependence on \u03c3. The average search time for a pattern of length m is O(m(H<jats:sub>0<\/jats:sub> + 1)), under reasonable assumptions. Each position of a text occurrence can be located in worst case time O((H<jats:sub>0<\/jats:sub> + 1) log n), while any text substring of length L can be retrieved in O((H<jats:sub>0<\/jats:sub> + 1)L) average time in addition to the previous worst case time. Our index provides a relevant space\/time tradeoff between existing succinct data structures, with the additional interest of being easy to implement. We also explore other coding variants alternative to Huffman and exploit their synchronization properties. Our experimental results on various types of texts show that our indexes are highly competitive in the space\/time tradeoff map. <\/jats:p>","DOI":"10.1142\/s0129054106004467","type":"journal-article","created":{"date-parts":[[2006,12,13]],"date-time":"2006-12-13T12:02:04Z","timestamp":1166011324000},"page":"1365-1384","source":"Crossref","is-referenced-by-count":12,"title":["A SIMPLE ALPHABET-INDEPENDENT FM-INDEX"],"prefix":"10.1142","volume":"17","author":[{"given":"SZYMON","family":"GRABOWSKI","sequence":"first","affiliation":[{"name":"Computer Engineering Department, Technical University of \u0141\u00f3d\u017a, Al. Politechniki 11, 90-924 \u0141\u00f3d\u017a, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"GONZALO","family":"NAVARRO","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Chile, Blanco Encalada 2120, 3er piso, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"RAFA\u0141","family":"PRZYWARSKI","sequence":"additional","affiliation":[{"name":"Computer Engineering Department, Technical University of \u0141\u00f3d\u017a, Al. Politechniki 11, 90-924 \u0141\u00f3d\u017a, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ALEJANDRO","family":"SALINGER","sequence":"additional","affiliation":[{"name":"David R. Cheriton School of Computer Science, University of Waterloo, 200 University Avenue West, Waterloo, Ontario, Canada N2L 3G1, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"VELI","family":"M\u00c4KINEN","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Helsinki, P. O. Box 68 (Gustaf H\u00e4llstr\u00f6min katu 2b), FIN-00014 Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1965.1053772"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"rf16","first-page":"191","volume":"56","author":"M\u00e4kinen V.","journal-title":"Fundamenta Informaticae"},{"key":"rf18","first-page":"40","volume":"12","author":"M\u00e4kinen V.","journal-title":"Nordic J. of Computing"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-8667(03)00066-2"},{"key":"rf25","volume-title":"Managing Gigabytes","author":"Witten I.","year":"1999"},{"key":"rf26","first-page":"179","volume":"41","author":"Zeckendorf E.","journal-title":"Bull. Soc. Roy. Sci. Li\u00e8ge"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054106004467","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:27:39Z","timestamp":1565191659000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054106004467"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,12]]},"references-count":7,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2006,12]]}},"alternative-id":["10.1142\/S0129054106004467"],"URL":"https:\/\/doi.org\/10.1142\/s0129054106004467","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,12]]}}}