{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,20]],"date-time":"2026-10-20T12:46:32Z","timestamp":1792500392986,"version":"4.5.0"},"reference-count":44,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T00:00:00Z","timestamp":1586217600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>It seems reasonable to expect from a good compression method that its output should not be further compressible, because it should behave essentially like random data. We investigate this premise for a variety of known lossless compression techniques, and find that, surprisingly, there is much variability in the randomness, depending on the chosen method. Arithmetic coding seems to produce perfectly random output, whereas that of Huffman or Ziv-Lempel coding still contains many dependencies. In particular, the output of Huffman coding has already been proven to be random under certain conditions, and we present evidence here that arithmetic coding may produce an output that is identical to that of Huffman.<\/jats:p>","DOI":"10.3390\/info11040196","type":"journal-article","created":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T05:59:47Z","timestamp":1586325587000},"page":"196","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["On the Randomness of Compressed Data"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9478-3303","authenticated-orcid":false,"given":"Shmuel T.","family":"Klein","sequence":"first","affiliation":[{"name":"Computer Science Department, Bar Ilan University, Ramat-Gan 5290002, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2320-9064","authenticated-orcid":false,"given":"Dana","family":"Shapira","sequence":"additional","affiliation":[{"name":"Computer Science Department, Data Science and Artificial Intelligence Center, Ariel University, Ariel 40700, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2020,4,7]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Huffman, D.A. (2020, April 05). A Method for the Construction of Minimum-Redundancy Codes. Available online: http:\/\/compression.ru\/download\/articles\/huff\/huffman_1952_minimum-redundancy-codes.pdf.","DOI":"10.1109\/JRPROC.1952.273898"},{"key":"ref_2","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_3","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1145\/63522.214390","article-title":"Algorithm 673: Dynamic Huffman coding","volume":"15","author":"Vitter","year":"1989","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_4","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 Trans. Commun."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"928","DOI":"10.1145\/322344.322346","article-title":"Data compression via textural substitution","volume":"29","author":"Storer","year":"1982","journal-title":"J. ACM"},{"key":"ref_6","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":"ref_7","doi-asserted-by":"crossref","first-page":"777","DOI":"10.1016\/j.ipm.2011.01.005","article-title":"On improving Tunstall codes","volume":"47","author":"Klein","year":"2011","journal-title":"Inf. Process. Manag."},{"key":"ref_8","unstructured":"Amir, A., and Benson, G. (1992, January 24\u201327). Efficient two-dimensional compressed matching. Proceedings of the Data Compression Conference, Snowbird, UT, USA."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1016\/j.ipm.2005.02.003","article-title":"Adapting the Knuth-Morris-Pratt algorithm for pattern matching in Huffman encoded texts","volume":"42","author":"Shapira","year":"2006","journal-title":"Inf. Process. Manag."},{"key":"ref_10","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":"ref_11","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":"ref_12","doi-asserted-by":"crossref","first-page":"61","DOI":"10.3390\/a4010061","article-title":"Compressed Matching in Dictionaries","volume":"4","author":"Klein","year":"2011","journal-title":"Algorithms"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Baruch, G., Klein, S.T., and Shapira, D. (2018, January 7\u20139). Applying Compression to Hierarchical Clustering. Proceedings of the SISAP 2018: 11th International Conference on Similarity Search and Applications, Lima, Peru.","DOI":"10.1007\/978-3-030-02224-2_12"},{"key":"ref_14","unstructured":"Jacobson, G. (November, January 30). Space efficient static trees and graphs. Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, NC, USA."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Navarro, G. (2016). Compact Data Structures: A Practical Approach, Cambridge University Press.","DOI":"10.1017\/CBO9781316588284"},{"key":"ref_16","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":"Discret. Appl. Math."},{"key":"ref_17","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. Discret. Algorithms"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1093\/comjnl\/bxr096","article-title":"Boosting Text Compression with Word-Based Statistical Encoding","volume":"55","author":"Navarro","year":"2012","journal-title":"Comput. J."},{"key":"ref_19","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":"ref_20","doi-asserted-by":"crossref","unstructured":"Huo, H., Sun, Z., Li, S., Vitter, J.S., Wang, X., Yu, Q., and Huan, J. (April, January 30). CS2A: A Compressed Suffix Array-Based Method for Short Read Alignment. Proceedings of the 2016 Data Compression Conference (DCC), Snowbird, SLC, USA.","DOI":"10.1109\/DCC.2016.58"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Benza, E., Klein, S.T., and Shapira, D. (2020). Smaller Compressed Suffix Arrays. Comput. J., 63.","DOI":"10.1093\/comjnl\/bxaa016"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1080\/0161-117991854061","article-title":"Cryptographic Aspects of Data Compression Codes","volume":"3","author":"Rubin","year":"1979","journal-title":"Cryptologia"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Klein, S.T., and Shapira, D. (2017, January 6\u20139). Integrated Encryption in Dynamic Arithmetic Compression. Proceedings of the 11th International Conference on Language and Automata Theory and Applications, Ume\u00e5, Sweden.","DOI":"10.1007\/978-3-319-53733-7_10"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"972","DOI":"10.1109\/18.490558","article-title":"On breaking a Huffman code","volume":"42","author":"Gillman","year":"1996","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1007\/BF01185434","article-title":"Complexity Aspects of Guessing Prefix Codes","volume":"12","author":"Fraenkel","year":"1994","journal-title":"Algorithmica"},{"key":"ref_26","first-page":"22:1","article-title":"TestU01: A C library for empirical testing of random number generators","volume":"33","author":"Simard","year":"2007","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Chang, W., Yun, X., Li, N., and Bao, X. (2012, January 11\u201313). Investigating Randomness of the LZSS Compression Algorithm. Proceedings of the 2012 International Conference on Computer Science and Service System, Nanjing, China.","DOI":"10.1109\/CSSS.2012.499"},{"key":"ref_28","unstructured":"Chang, W., Fang, B., Yun, X., Wang, S., and Yu, X. (2010). Randomness Testing of Compressed Data. arXiv."},{"key":"ref_29","unstructured":"Knuth, D.E. (1969). The Art of Computer Programming, Volume II: Seminumerical Algorithms, Addison-Wesley."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1145\/65943.65946","article-title":"Storing Text Retrieval Systems on CD-ROM: Compression and Encryption Considerations","volume":"7","author":"Klein","year":"1989","journal-title":"ACM Trans. Inf. Syst."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1109\/TIT.1982.1056452","article-title":"An application of informational divergence to Huffman codes","volume":"28","author":"Longo","year":"1982","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF02243872","article-title":"Is Huffman coding dead?","volume":"50","author":"Bookstein","year":"1993","journal-title":"Computing"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"520","DOI":"10.1145\/214762.214771","article-title":"Arithmetic Coding for Data Compression","volume":"30","author":"Witten","year":"1987","journal-title":"Commun. ACM"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Klein, S.T. (2016). Basic Concepts in Data Structures, Cambridge University Press.","DOI":"10.1017\/CBO9781316676226"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"825","DOI":"10.1145\/31846.42227","article-title":"Design and analysis of dynamic Huffman codes","volume":"34","author":"Vitter","year":"1987","journal-title":"J. ACM"},{"key":"ref_36","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 Comput."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","article-title":"A universal algorithm for sequential data compression","volume":"23","author":"Ziv","year":"1977","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","article-title":"Compression of individual sequences via variable-rate coding","volume":"24","author":"Ziv","year":"1978","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1214\/aoms\/1177729694","article-title":"On information and sufficiency","volume":"22","author":"Kullback","year":"1951","journal-title":"Ann. Math. Stat."},{"key":"ref_40","unstructured":"Burrows, M., and Wheeler, D.J. (2020, April 05). A Block Sorting Lossless Data Compression Algorithm. Available online: https:\/\/www.hpl.hp.com\/techreports\/Compaq-DEC\/SRC-RR-124.pdf."},{"key":"ref_41","unstructured":"Nelson, M., and Gailly, J.L. (1996). The Data Compression Book, M & T Books. [2nd ed.]."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1002\/spe.4380190207","article-title":"Word-based Text Compression","volume":"19","author":"Moffat","year":"1989","journal-title":"Softw. Pract. Exp."},{"key":"ref_43","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":"Comput. J."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1109\/18.382012","article-title":"The context-tree weighting method: basic properties","volume":"41","author":"Willems","year":"1995","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/11\/4\/196\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T09:16:05Z","timestamp":1760174165000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/11\/4\/196"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,7]]},"references-count":44,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2020,4]]}},"alternative-id":["info11040196"],"URL":"https:\/\/doi.org\/10.3390\/info11040196","relation":{},"ISSN":["2078-2489"],"issn-type":[{"value":"2078-2489","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,7]]}}}