{"id":224,"date":"2009-01-26T00:05:38","date_gmt":"2009-01-26T05:05:38","guid":{"rendered":"http:\/\/vgable.com\/blog\/2009\/01\/26\/compressibility-of-english-text\/"},"modified":"2009-01-29T11:06:10","modified_gmt":"2009-01-29T16:06:10","slug":"compressibility-of-english-text","status":"publish","type":"post","link":"https:\/\/vgable.com\/blog\/2009\/01\/26\/compressibility-of-english-text\/","title":{"rendered":"Compressibility of English Text"},"content":{"rendered":"

Theory:<\/h3>\n

Some early experiments by Shannon67<\/sup> and Cover and King68<\/sup> attempted to find a lower bound for the compressibility of English text by having human subjects make the predictions for a compression system. These authors concluded that English has an inherent entropy of around 1 bit per character<\/strong>, and that we are unlikely ever to be able to compress it at a better rate than this.<\/p>\n

67<\/sup> C. E. Shannon, “Prediction and entropy of printed English”, Bell Systems Technical J<\/em>. 30 (1951) 55. (Here’s a bad PDF scan<\/a>)<\/p>\n

68<\/sup> T.M. Cover and R. C. King, “A convergent gambling estimate of the entropy of English”, IEEE Trans. on Information Theory<\/em> IT-24<\/strong> (1978) 413-421\n<\/p><\/blockquote>\n

—Signal Compression: Coding of Speech, Audio, Text, Image and Video<\/em>
\nBy N. Jayant<\/a><\/p>\n

Shannon says 0.6-1.3 bits per character of English — 0.6 bits is the lowest value I have seen anyone claim.<\/p>\n

Practice:<\/h3>\n

Just as a datapoint I tried gzip --best<\/code> on plain-text file of The Adventures of Sherlock Holmes<\/em>, weighing in at 105471 words, and using 578798 bytes. The compressed file was 220417 bytes.<\/p>\n

If we assume the uncompressed version used one byte (8 bits) per character, then gzip --best<\/code> used about 3 bits per character.<\/strong><\/p>\n

Best so Far<\/h3>\n

The state-of-the-art in the Hutter Prize<\/a>, a challenge to compress 150 MB of Wikipedia content, is 1.319 bits per character. But that’s with a program tuned just<\/em> for that data set, and it took 9 hours to run.<\/p>\n","protected":false},"excerpt":{"rendered":"

Theory: Some early experiments by Shannon67 and Cover and King68 attempted to find a lower bound for the compressibility of English text by having human subjects make the predictions for a compression system. These authors concluded that English has an inherent entropy of around 1 bit per character, and that we are unlikely ever to […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[11],"tags":[187,318,317,188],"class_list":["post-224","post","type-post","status-publish","format-standard","hentry","category-research","tag-english","tag-entropy","tag-information-theory","tag-linguistics"],"_links":{"self":[{"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/posts\/224","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/comments?post=224"}],"version-history":[{"count":0,"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/posts\/224\/revisions"}],"wp:attachment":[{"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/media?parent=224"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/categories?post=224"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/vgable.com\/blog\/wp-json\/wp\/v2\/tags?post=224"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}