{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T18:10:39Z","timestamp":1770574239196,"version":"3.49.0"},"reference-count":49,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2021,2,28]],"date-time":"2021-02-28T00:00:00Z","timestamp":1614470400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>This article deals with compression of binary sequences with a given number of ones, which can also be considered as a list of indexes of a given length. The first part of the article shows that the entropy H of random n-element binary sequences with exactly k elements equal one satisfies the inequalities klog2(0.48\u00b7n\/k)&lt;H&lt;klog2(2.72\u00b7n\/k). Based on this result, we propose a simple coding using fixed length words. Its main application is the compression of random binary sequences with a large disproportion between the number of zeros and the number of ones. Importantly, the proposed solution allows for a much faster decompression compared with the Golomb-Rice coding with a relatively small decrease in the efficiency of compression. The proposed algorithm can be particularly useful for database applications for which the speed of decompression is much more important than the degree of index list compression.<\/jats:p>","DOI":"10.3390\/e23030296","type":"journal-article","created":{"date-parts":[[2021,2,28]],"date-time":"2021-02-28T20:43:32Z","timestamp":1614545012000},"page":"296","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Efficient Inverted Index Compression Algorithm Characterized by Faster Decompression Compared with the Golomb-Rice Algorithm"],"prefix":"10.3390","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6629-0029","authenticated-orcid":false,"given":"Andrzej","family":"Chmielowiec","sequence":"first","affiliation":[{"name":"The Faculty of Mechanics and Technology, Rzeszow University of Technology, Kwiatkowskiego 4, 37-450 Stalowa Wola, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4497-6553","authenticated-orcid":false,"given":"Pawe\u0142","family":"Litwin","sequence":"additional","affiliation":[{"name":"The Faculty of Mechanical Engineering and Aeronautics, Rzeszow University of Technology, Powsta\u0144c\u00f3w Warszawy 8, 35-959 Rzeszow, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,2,28]]},"reference":[{"key":"ref_1","unstructured":"Deming, W. (1986). Out of the Crisis, MIT Press."},{"key":"ref_2","unstructured":"Shewart, W. (1931). Economic Control of Quality Manufactured Product, D. Van Nostrand."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Pa\u015bko, \u0141., and Litwin, P. (2019). Methods of Data Mining for Quality Assurance in Glassworks, Springer International Publishing. Collaborative Networks and Digital Transformation.","DOI":"10.1007\/978-3-030-28464-0_17"},{"key":"ref_4","unstructured":"Buttcher, S., Clarke, C., and Cormack, G. (2010). Information Retrieval: Implementing and Evaluating Search Engines, MIT Press."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Manning, C., Raghavan, P., and Sch\u00fctze, H. (2008). Introduction to Information Retrieval, Cambridge University Press.","DOI":"10.1017\/CBO9780511809071"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1132956.1132959","article-title":"Inverted files for text search engines","volume":"38","author":"Zobel","year":"2006","journal-title":"ACM Comput. Surv."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Fano, R. (1961). Transmission of Information: A Statistical Theory of Communications, The MIT Press.","DOI":"10.1119\/1.1937609"},{"key":"ref_8","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 Syst. Tech. J."},{"key":"ref_9","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":"Proc. IRE"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1109\/TIT.1966.1053907","article-title":"Run-Length Encodings","volume":"IT-12","author":"Golomb","year":"1966","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"889","DOI":"10.1109\/TCOM.1971.1090789","article-title":"Adaptive Variable-Length Coding for Efficient Compression of Spacecraft Television Data","volume":"16","author":"Rice","year":"1971","journal-title":"IEEE Trans. Commun."},{"key":"ref_12","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. Inf. Theory"},{"key":"ref_13","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. Inf. Theory"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Brisaboa, N., Fari\u00f1a, A., Navarro, G., and Esteller, M. (2003). (S,C)-Dense Coding: An Optimized Compression Code for Natural Language Text Databases. String Processing and Information Retrieval, Springer.","DOI":"10.1007\/978-3-540-39984-1_10"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1080\/15427951.2005.10129113","article-title":"Codes for the World Wide Web","volume":"2","author":"Boldi","year":"2005","journal-title":"Internet Math."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1145\/321812.321820","article-title":"Efficient Storage and Retrieval by Content and Address of Static Files","volume":"21","author":"Elias","year":"1974","journal-title":"J. ACM"},{"key":"ref_17","unstructured":"Fano, R. (1971). On the Number of Bits Required to Implement an Associative Memory, MIT Project MAC Computer Structures Group."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1023\/A:1013002601898","article-title":"Binary Interpolative Coding for Effective Index Compression","volume":"3","author":"Moffat","year":"2000","journal-title":"Inf. Retr. J."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1023\/B:INRT.0000048490.99518.5c","article-title":"Inverted Index Compression Using Word-Aligned Binary Codes","volume":"8","author":"Anh","year":"2005","journal-title":"Inf. Retr. J."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3415148","article-title":"Techniques for Inverted Index Compression","volume":"53","author":"Pibiri","year":"2021","journal-title":"ACM Comput. Surv."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1023\/A:1022949613039","article-title":"Compressing inverted files","volume":"6","author":"Trotman","year":"2003","journal-title":"Inf. Retr. J."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Catena, M., Macdonald, C., and Ounis, I. (2014). On Inverted Index Compression for Search Engine Efficiency. Advances in Information Retrieval, Springer International Publishing.","DOI":"10.1007\/978-3-319-06028-6_30"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Salomon, D., and Motta, G. (2010). Handbook of Data Compression, Springer.","DOI":"10.1007\/978-1-84882-903-9"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1109\/TIT.1975.1055357","article-title":"Optimal Source Codes for Geometrically Distributed Integer Alphabets","volume":"IT-21","author":"Gallager","year":"1975","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1109\/TMM.2006.886260","article-title":"Extended Golomb Code for Integer Representation","volume":"9","author":"Somasundaram","year":"2007","journal-title":"IEEE Trans. Multimed."},{"key":"ref_26","unstructured":"Rice, R., and Robert, F. (1979). Some Practical Universal Noiseless Coding Techniques, Jet Propulsion Laboratory\u2014JPL Publication. Technical Report 79-22."},{"key":"ref_27","unstructured":"Rice, R. (1991). Some Practical Universal Noiseless Coding Techniques\u2014Part III. Module PSI14.K, Jet Propulsion Laboratory\u2014JPL Publication. Technical Report 91-3."},{"key":"ref_28","unstructured":"Fenwick, P. (1996). Punctured Elias Codes for Variable-Length Coding of the Integers, Department of Computer Science, The University of Auckland. Technical Report Technical Report 137."},{"key":"ref_29","unstructured":"Robinson, T. (1994). Simple Lossless and Near-Lossless Waveform Compression, Cambridge University. Technical Report Technical Report CUED\/F-INFENG\/TR.156."},{"key":"ref_30","unstructured":"Kiely, A. (2004). Selecting the Golomb Parameter in Rice Coding, Jet Propulsion Laboratory, California Institute of Technology. Technical Report 42-159."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/978-3-642-82456-2_12","article-title":"Novel Compression of Sparse Bit-Strings\u2013Preliminary Report","volume":"12","author":"Fraenkel","year":"1985","journal-title":"Comb. Algorithms Words"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1145\/331624.331631","article-title":"Prefix Compression of Sparse Binary Strings","volume":"6","author":"Salomon","year":"2000","journal-title":"ACM Crossroads Mag."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"880","DOI":"10.1109\/TIT.1982.1056593","article-title":"Efficient Run-Length Encodings","volume":"IT-28","author":"Tanaka","year":"1982","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.tcs.2006.12.012","article-title":"A simple storage scheme for strings achieving entropy bounds","volume":"372","author":"Ferragina","year":"2007","journal-title":"Theor. Comput. Sci."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Zhang, J., Long, X., and Suel, T. (2008, January 21\u201325). Performance of Compressed Inverted List Caching in Search Engines. Proceedings of the 17th International Conference on World Wide Web, New York, NY, USA.","DOI":"10.1145\/1367497.1367550"},{"key":"ref_36","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 Trans. Inf. Theory"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"1941","DOI":"10.1109\/TIT.2009.2016069","article-title":"The Universal LZ77 Compression Algorithm is Essentially Optimal for Individual Finite-Length N-Blocks","volume":"55","author":"Ziv","year":"2009","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"501","DOI":"10.7153\/jmi-06-47","article-title":"An Inequality for the Binary Entropy Function and an Application to Binomial Coefficients","volume":"6","author":"Mascioni","year":"2012","journal-title":"J. Math. Inequal."},{"key":"ref_39","first-page":"26","article-title":"A remark on Stirling\u2019s formula","volume":"62","author":"Robbins","year":"1995","journal-title":"Am. Math. Mon."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"1379","DOI":"10.1109\/TIP.2005.871116","article-title":"Lossless compression of color mosaic images","volume":"15","author":"Zhang","year":"2006","journal-title":"IEEE Trans. Image Process."},{"key":"ref_41","unstructured":"Hashimoto, M., Koike, A., and Matsumoto, S. (1999, January 5\u20139). Hierarchical image transmission system for telemedicine using segmented wavelet transform and Golomb-Rice codes. Seamless Interconnection for Universal Services. Proceedings of the Global Telecommunications Conference, GLOBECOM\u201999 (Cat. No.99CH37042), Rio de Janeiro, Brazil."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1109\/TIP.2002.807354","article-title":"Lossless Compression of Video Using Temporal Information","volume":"12","author":"Brunello","year":"2003","journal-title":"IEEE Trans. Image Process."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Nguyen, T., Marpe, D., Schwarz, H., and Wiegand, T. (2011, January 11\u201314). Reduced-Complexity Entropy Coding of Transform Coefficient Levels Using Trunceted Golomb-Rice Codes in Video Compression. Proceedings of the 2011 18th IEEE International Conference on Image Processing, Brussels, Belgium.","DOI":"10.1109\/ICIP.2011.6116664"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1016\/j.comcom.2019.11.046","article-title":"Analysis and implementation of novel Rice Golomb coding algorithm for wireless sensor networks","volume":"150","author":"Kalaivani","year":"2020","journal-title":"Comput. Commun."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"3153","DOI":"10.1109\/TIT.2018.2799629","article-title":"Optimal Golomb-Rice Code Extension for Lossless Coding of Low-Entropy Exponentially Distributed Sources","volume":"64","author":"Sugiura","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Sugiura, R., Kamamoto, Y., and Moriya, T. (2018, January 27\u201330). Integer Nesting\/Splitting for Golomb-Rice Coding of Generalized Gaussian Sources. Proceedings of the 2018 Data Compression Conference, Snowbird, UT, USA.","DOI":"10.1109\/DCC.2018.00080"},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Vasilache, A. (September, January 28). Order Adaptive Golomb Rice Coding for High Variability Sources. Proceedings of the 2017 25th European Signal Processing Conference (EUSIPCO), Kos Island, Greece.","DOI":"10.23919\/EUSIPCO.2017.8081517"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1080\/03772063.2015.1054899","article-title":"Extended Rice Code and Its application to R-Tree Compression","volume":"61","author":"Domnic","year":"2015","journal-title":"IETE J. Res."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"1223","DOI":"10.1109\/18.915692","article-title":"Compression of sparse matrices by blocked rice coding","volume":"47","author":"McKenzie","year":"2001","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/3\/296\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:30:35Z","timestamp":1760160635000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/3\/296"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,28]]},"references-count":49,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2021,3]]}},"alternative-id":["e23030296"],"URL":"https:\/\/doi.org\/10.3390\/e23030296","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,28]]}}}