16 ms·

Gzip + poetry = awesome

370 points by jvns 13y ago

aviksh 13y ago
The deflation algorithm used by gzip is a variation of LZ77.
JacksonGariety 13y ago
Can anyone explain what is going on here?
- gry 13y ago
  > Once upon a midnight dreary, while I {pon}ered It's a visual demonstration how gzip works. The first line says it all. 'pon' matches the bytes in 'upon', the first first instance, thus it's pointer to those bytes instead of "duplicating" the pattern. As the text goes on, there are more matches, thus more pointers.
- jws 13y ago
  gzip works by constructing, on the fly, a dictionary of strings it has seen before and sort of inserting them by reference. When you see something red and in braces, that is a bit that has occurred before and been inserted by reference. I'm guessing that it is happening at a constant symbol rate, you'll notice it speeding up as it includes more and more text by reference instead of a single character at a time.
- promoCode 13y ago
  For those who don't feel like watching a youtube video that shows a recording of the animated command line output, simply click this link: https://rawgithub.com/jvns/7155528/raw/ef9785f023fc68d78dc4f61e732007149eec1e69/raven.html https://rawgithub.com/jvns/7155528/raw/ef9785f023fc68d78dc4f... The author explains what he did to produce this output, and provides links to his program's source code in his post, so OP's link is still a worthwhile read, but that link cuts to the chase.
CGamesPlay 13y ago
Audio is unnecessary. The video shows a slow-motion decoding of a gzipped version of the poem. The red text between brackets is a chunk of text that was earlier stored into the huffman tree (example "W{hile I }" means that the "hile I" was previously encoded; it occurred in the substring "while I pondered"). You can see the red chunks quickly occupy the larger volume of the poem, which visually highlights the symmetry in lyric that the computer is using to encode the file as gzip. Pretty neat.
- codezero 13y ago
  s/decryption/decompression
  - CGamesPlay 13y ago
    Fixed, thanks :)
    - codezero 13y ago
      I appreciate your indulging my pedantic nature!
- willvarfar 13y ago
  (Its not a Huffman tree. When you replace a fragment with a reference to previous content, its termed 'dictionary coding'. Huffman trees are what you use for `entropy coding`, which is how you compress the bits you didn't zap with the dictionary.)
alexholehouse 13y ago
For some reason I find theories and approaches in compression really interesting. For those unfamiliar I recommend Blelloch's introduction to compression (http://www.cs.cmu.edu/~guyb/realworld/compression.pdf http://www.cs.cmu.edu/~guyb/realworld/compression.pdf)
- willvarfar 13y ago
  Another excellent source is Matt Mahoney's Data Compression Explained: http://mattmahoney.net/dc/dce.html http://mattmahoney.net/dc/dce.html
  - tehwalrus 13y ago
    And yet another is David Mackay, who taught me at undergrad: http://www.inference.phy.cam.ac.uk/mackay/itila/ http://www.inference.phy.cam.ac.uk/mackay/itila/ scroll to the bottom for the free PDF. (the book is about all sorts of stuff, but compression is the main example used when defining information theory.)
    - kevgnulldev 13y ago
      Along similar lines, but a more focused book (no learning, etc) is the classic Cover and Thomas: http://www.elementsofinformationtheory.com/ http://www.elementsofinformationtheory.com/
    - khafra 13y ago
      And let's not forget Marcus Hutter and Jurgen Schmidhuber, who use compression to explain general reasoning and human curiosity http://prize.hutter1.net/ http://prize.hutter1.net/ http://www.idsia.ch/~juergen/interest.html http://www.idsia.ch/~juergen/interest.html
deleted 13y ago
[deleted]
- jvns 13y ago
  To clear this up: This is exactly how gzip actually works. I wrote a version of gunzip from scratch and just inserted some print statements in the middle to get this visualization.
  - jvns 13y ago
    If anyone is interested, the part of the source code that produces the visualization is here: https://github.com/jvns/gzip.jl/blob/visualization/gzip.jl#L360 https://github.com/jvns/gzip.jl/blob/visualization/gzip.jl#L...
    - msumpter 13y ago
      I ended up compiling Julia just so I could watch it in action myself: http://showterm.io/2b572805187a499194e91#fast http://showterm.io/2b572805187a499194e91#fast Beautiful
      - jvns 13y ago
        THIS IS COOL. I did not know about showterm.io.
  - jcampbell1 13y ago
    You are quite right, I am an idiot.
    - cbhl 13y ago
      Frankly, learning about LZW[0][1] and the Burrows-Wheeler Transform[2] was probably one of the highlights of my first undergrad algorithms course. The latter certainly made me feel like an idiot, too. [0] http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welc... [1] For the record, LZW isn't used in gzip; it was the patent-encumbered compression format used in GIF. [2] http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transfo... (used in bzip2)
tempestn 13y ago
This is extremely cool. For anyone curious what the various compression levels of gzip do, the full explanation is here: http://www.gzip.org/algorithm.txt http://www.gzip.org/algorithm.txt. Basically the higher the compression level, the more times it spends searching for the longest possible matching string to point to.
mvleming 13y ago
Wow, this is a incredible visualization of how compression works. I never understood how it worked before, but the simple mentioning of pointers and then that video was all it took for me. I've always wondered if this is true: If we approach infinite computational power, does the amount of information we need to represent data decrease? (Excuse any incorrect use of my terminology here.) I think about a number like pi that, as far as we know, has an infinite number of digits, and theoretically speaking every message is contained in that number. So if we just get the pointer of where that message is contained in the number and then calculate the number up to that pointer then we'll have ourselves the message. Hence, more computational power, less information needed.
- rmc 13y ago
  It's impossible to have a lossless compression system that will always compress anything down to less size than it was originally, otherwise you could run it as many times as you want and compress everything down to 1 bit. This includes "pointer to pi digits". What would probably happen there is the byte representation of the offset would be longer than the input string itself! Although, now for curiousity, I'd like to actually try that "offset in pi" algorithm. :) Just for fun.
  - tjgq 13y ago
    Not to spoil your weekend project, but someone's done it already :) https://github.com/philipl/pifs https://github.com/philipl/pifs
- ryanpetrich 13y ago
  It's possible that for many messages, the pointer of the message into the representation of pi may actually be larger than the message itself.
- willvarfar 13y ago
  There is a flaw in your random sequence approach; lets see if you can find it? Its a fun thinking exercise. You can estimate the minimum bound on compression using Shannon's estimate http://en.wikipedia.org/wiki/Entropy_(information_theory) http://en.wikipedia.org/wiki/Entropy_(information_theory) An excellent problem for hobby coders is the Hutter Prize. Even if you don't win - and that'd be front page HN news if you did - its a really fun challenge and an excellent introduction to compression: http://prize.hutter1.net/ http://prize.hutter1.net/ Also worth googling is Kolmogorov complexity.
tete 13y ago
Julia programming Julia? Pretty cool too! That's how you recognize a real hacker...
- jvns 13y ago
  =D Since a lot of the Julia core is written in Julia, it's also possible to have Julia working on Julia in Julia.
aortega 13y ago
This is a demonstration of a simplified LZ77 algorithm, not Gzip. Gzip is a unix utility, LZ77 is an algorithm, this distinction is not pedantic. This is what happens when you go to "hacker school" before regular CS school.
- zackbloom 13y ago
  That last line was not necessary, there are plenty of people with CS degrees who wouldn't know the difference between different versions of LZW.
  - aortega 13y ago
    Yet the basic premise of the video is still wrong. Gzip uses many algorithms internally, among them LZ77 and huffman. It's like doing a video about "this is how mysql works" and showing the quicksort algorithm.
    - nbevans 13y ago
      I agree with you. Gzip is merely a container format, just like AVI, MKV are for video/audio content. Gzip supports several compression encodings with Deflate being the the most common one I believe.
- shawabawa3 13y ago
  > Gzip is a unix utility, LZ77 is an algorithm, this distinction is not pedantic. It's basically the definition of pedantic. Gzip uses the LZ77 algorithm, so it's a simplified demonstration of what gzip does. It's also a simplified demonstration of LZ77.
  - jvns 13y ago
    The video title is in fact not quite accurate -- I chose to err in the direction of "cool soundbyte", since "LZ77 + poetry = awesome" doesn't have quite the same ring. aortega is quite right that this video actually explains LZ77, which is only one part of how gzip compresses. gzip (or the DEFLATE algorithm) also uses Huffman coding to compress the alphabet and pointers after LZ77 compression. I explain a bit more about the phases at http://jvns.ca/blog/2013/10/23/day-15-how-gzip-works http://jvns.ca/blog/2013/10/23/day-15-how-gzip-works And if you really want to know how it works, you should read http://www.infinitepartitions.com/art001.html http://www.infinitepartitions.com/art001.html, which is the reference I used for writing my implementation of gunzip. It includes C source code. The dig at hacker schoolers was unnecessary, though :)
ot 13y ago
Compression is truly fascinating. It's what got me into reading computer science papers several years ago, and then became one of my research topics. What is shown here is the LZ77 [1] factorization of a string. Compression in general works by exploiting redundancy in the source, and natural language is highly redundant, since many words repeat often. Hence the factors in the factorization often look like frequent words or n-grams. A recent line of research is grammar compression, which tries to turn a text into a tree of rules that generate that text. While still not very good at general-purpose compression, the generated tree are much more interesting than the LZ77 factorization, since they "discover" something that looks like a syntactic parsing of the string, finding syllabes, words, phrases, sentences... In Craig Nevill-Manning's Ph.D. thesis [2] introduction there are several examples of the inferred grammar of pieces of text, music, fractals, source code, etc... While the algorithm presented there (Sequitur) is now kind of obsolete, the thesis is very interesting because it makes some considerations with a linguistic perspective. [1] http://en.wikipedia.org/wiki/LZ77_and_LZ78 http://en.wikipedia.org/wiki/LZ77_and_LZ78 [2] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.5.1112&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.5.1...
- jmmcd 13y ago
  Wow, that PhD thesis is very interesting. I use grammars to generate music (and other things sometimes), but I would also really like to be able to infer them. Since you say it's obsolete, do you have any links to papers or software related to successors of the Sequitur algorithm?
  - ot 13y ago
    It depends on what you want to do. RePair [1] is currently the best grammar-based compressor, but it doesn't give good theoretical guarantees. In theory, instead, there is an O(log n) approximation to the smallest grammar problem [2], but AFAIK doesn't work very well in practice. In the same paper there is a good introduction to the problem and an analysis of the previous algorithms, including Sequitur. [1] http://www.larsson.dogma.net/dcc99.pdf http://www.larsson.dogma.net/dcc99.pdf [2] http://www.cs.virginia.edu/~shelat/papers/GrammarIEEE.pdf http://www.cs.virginia.edu/~shelat/papers/GrammarIEEE.pdf
daronphq672 13y ago
my parents inlaw recently got a very nice Mercedes-Benz C-Class Convertible by working part time off of a pc. this contact form .............http://www.BAM21.CoM http://www.BAM21.CoM
- V-2 13y ago
  That's just great! Many thanks for the info.
  - V-2 13y ago
    chill out downvoters, I was being sarcy
annnnd 13y ago
I get this: Offline Site: jvns.ca You have requested a site that is currently offline. This generally happens when a site is temporarily disabled for some reason, but has not been permanently removed...
- josephb 13y ago
  Unexpected HN traffic is likely to have used all the site owners pre-paid credit. Edit: To clarify, NearlyFreeSpeech hosting is prepaid.
  - jvns 13y ago
    Yup, apparently the $2 I had left in my account didn't cover it. Back up now!
heyadayo 13y ago
Mirror: https://web.archive.org/web/20131025035238/http://jvns.ca/blog/2013/10/24/day-16-gzip-plus-poetry-equals-awesome/ https://web.archive.org/web/20131025035238/http://jvns.ca/bl... http://www.youtube.com/watch?feature=player_embedded&v=D2JWSNDgkoE http://www.youtube.com/watch?feature=player_embedded&v=D2JWS...
Jotace 13y ago
Today the site is down...
_quasimodo 13y ago
As the author mentioned, poetry usually compresses quite well, thanks to rhyming. Here is another fun example: http://codegolf.stackexchange.com/questions/6043/were-no-strangers-to-code-golf-you-know-the-rules-and-so-do-i http://codegolf.stackexchange.com/questions/6043/were-no-str...
pdknsk 13y ago
What I noticed in the other text, Hamlet, is that HAMLET in the last sentence has no pointer to Hamlet, obviously. This seems like an opportunity for optimisation, for text at least. Usually a word is either lowercase, capitalised or uppercase. In more complex and rare cases this could be efficiently encoded bitwise (0 = keep, 1 = swap case), so HAMLEt becomes 011110 plus a pointer to Hamlet. I wonder if any compression algorithm does this. Probably not, because the benefit is likely minimal at significantly increased de/compression time.
- cbhl 13y ago
  One problem is that way of thinking is distinctly ASCII-centric -- what happens when you have accents, umlats, Chinese, and the rest of the stuff that comes out of Unicode? I suspect the encoding you propose would actually increase the size of the average plaintext, simply because people rarely will type "Hamlet" and then later type "HaMlEt" in the same document. I think a far more common case would be "Hamlet" (beginning of sentence) and "hamlet" (inline), where you can reuse the substring "amlet". (Either that, or they're consistent with the usage of all-caps, like MICROSOFT(R).) Besides, if you know you're doing English, you can save 12.5% simply by using 7-bit ASCII instead of of 8-bit ASCII.
  - pdknsk 13y ago
    It seems simple enough to implement case-pairs for Unicode. Most likely it already is. Either way, you're right. It was just a simple idea.
    - judk 13y ago
      http://www.unicode.org/faq/casemap_charprop.html http://www.unicode.org/faq/casemap_charprop.html Still provincial
- apw 13y ago
  Your idea is good, and many modern compression systems, like the PAQ system, exploit it [1]. [1] https://en.wikipedia.org/wiki/PAQ#Text_preprocessing https://en.wikipedia.org/wiki/PAQ#Text_preprocessing

370 points by jvns 13y ago

aviksh 13y ago

The deflation algorithm used by gzip is a variation of LZ77.

JacksonGariety 13y ago

Can anyone explain what is going on here?

gry 13y ago
> Once upon a midnight dreary, while I {pon}ered It's a visual demonstration how gzip works. The first line says it all. 'pon' matches the bytes in 'upon', the first first instance, thus it's pointer to those bytes instead of "duplicating" the pattern. As the text goes on, there are more matches, thus more pointers.
jws 13y ago
gzip works by constructing, on the fly, a dictionary of strings it has seen before and sort of inserting them by reference. When you see something red and in braces, that is a bit that has occurred before and been inserted by reference. I'm guessing that it is happening at a constant symbol rate, you'll notice it speeding up as it includes more and more text by reference instead of a single character at a time.
promoCode 13y ago
For those who don't feel like watching a youtube video that shows a recording of the animated command line output, simply click this link: https://rawgithub.com/jvns/7155528/raw/ef9785f023fc68d78dc4f61e732007149eec1e69/raven.html https://rawgithub.com/jvns/7155528/raw/ef9785f023fc68d78dc4f... The author explains what he did to produce this output, and provides links to his program's source code in his post, so OP's link is still a worthwhile read, but that link cuts to the chase.

CGamesPlay 13y ago

Audio is unnecessary. The video shows a slow-motion decoding of a gzipped version of the poem. The red text between brackets is a chunk of text that was earlier stored into the huffman tree (example "W{hile I }" means that the "hile I" was previously encoded; it occurred in the substring "while I pondered"). You can see the red chunks quickly occupy the larger volume of the poem, which visually highlights the symmetry in lyric that the computer is using to encode the file as gzip. Pretty neat.

codezero 13y ago
s/decryption/decompression
- CGamesPlay 13y ago
  Fixed, thanks :)
  - codezero 13y ago
    I appreciate your indulging my pedantic nature!
willvarfar 13y ago
(Its not a Huffman tree. When you replace a fragment with a reference to previous content, its termed 'dictionary coding'. Huffman trees are what you use for `entropy coding`, which is how you compress the bits you didn't zap with the dictionary.)

alexholehouse 13y ago

For some reason I find theories and approaches in compression really interesting. For those unfamiliar I recommend Blelloch's introduction to compression (http://www.cs.cmu.edu/~guyb/realworld/compression.pdf http://www.cs.cmu.edu/~guyb/realworld/compression.pdf)

willvarfar 13y ago
Another excellent source is Matt Mahoney's Data Compression Explained: http://mattmahoney.net/dc/dce.html http://mattmahoney.net/dc/dce.html
- tehwalrus 13y ago
  And yet another is David Mackay, who taught me at undergrad: http://www.inference.phy.cam.ac.uk/mackay/itila/ http://www.inference.phy.cam.ac.uk/mackay/itila/ scroll to the bottom for the free PDF. (the book is about all sorts of stuff, but compression is the main example used when defining information theory.)
  - kevgnulldev 13y ago
    Along similar lines, but a more focused book (no learning, etc) is the classic Cover and Thomas: http://www.elementsofinformationtheory.com/ http://www.elementsofinformationtheory.com/
  - khafra 13y ago
    And let's not forget Marcus Hutter and Jurgen Schmidhuber, who use compression to explain general reasoning and human curiosity http://prize.hutter1.net/ http://prize.hutter1.net/ http://www.idsia.ch/~juergen/interest.html http://www.idsia.ch/~juergen/interest.html

deleted 13y ago

[deleted]

jvns 13y ago
To clear this up: This is exactly how gzip actually works. I wrote a version of gunzip from scratch and just inserted some print statements in the middle to get this visualization.
- jvns 13y ago
  If anyone is interested, the part of the source code that produces the visualization is here: https://github.com/jvns/gzip.jl/blob/visualization/gzip.jl#L360 https://github.com/jvns/gzip.jl/blob/visualization/gzip.jl#L...
  - msumpter 13y ago
    I ended up compiling Julia just so I could watch it in action myself: http://showterm.io/2b572805187a499194e91#fast http://showterm.io/2b572805187a499194e91#fast Beautiful
    - jvns 13y ago
      THIS IS COOL. I did not know about showterm.io.
- jcampbell1 13y ago
  You are quite right, I am an idiot.
  - cbhl 13y ago
    Frankly, learning about LZW[0][1] and the Burrows-Wheeler Transform[2] was probably one of the highlights of my first undergrad algorithms course. The latter certainly made me feel like an idiot, too. [0] http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welc... [1] For the record, LZW isn't used in gzip; it was the patent-encumbered compression format used in GIF. [2] http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transfo... (used in bzip2)

tempestn 13y ago

This is extremely cool. For anyone curious what the various compression levels of gzip do, the full explanation is here: http://www.gzip.org/algorithm.txt http://www.gzip.org/algorithm.txt. Basically the higher the compression level, the more times it spends searching for the longest possible matching string to point to.

mvleming 13y ago

Wow, this is a incredible visualization of how compression works. I never understood how it worked before, but the simple mentioning of pointers and then that video was all it took for me. I've always wondered if this is true: If we approach infinite computational power, does the amount of information we need to represent data decrease? (Excuse any incorrect use of my terminology here.) I think about a number like pi that, as far as we know, has an infinite number of digits, and theoretically speaking every message is contained in that number. So if we just get the pointer of where that message is contained in the number and then calculate the number up to that pointer then we'll have ourselves the message. Hence, more computational power, less information needed.

rmc 13y ago
It's impossible to have a lossless compression system that will always compress anything down to less size than it was originally, otherwise you could run it as many times as you want and compress everything down to 1 bit. This includes "pointer to pi digits". What would probably happen there is the byte representation of the offset would be longer than the input string itself! Although, now for curiousity, I'd like to actually try that "offset in pi" algorithm. :) Just for fun.
- tjgq 13y ago
  Not to spoil your weekend project, but someone's done it already :) https://github.com/philipl/pifs https://github.com/philipl/pifs
ryanpetrich 13y ago
It's possible that for many messages, the pointer of the message into the representation of pi may actually be larger than the message itself.
willvarfar 13y ago
There is a flaw in your random sequence approach; lets see if you can find it? Its a fun thinking exercise. You can estimate the minimum bound on compression using Shannon's estimate http://en.wikipedia.org/wiki/Entropy_(information_theory) http://en.wikipedia.org/wiki/Entropy_(information_theory) An excellent problem for hobby coders is the Hutter Prize. Even if you don't win - and that'd be front page HN news if you did - its a really fun challenge and an excellent introduction to compression: http://prize.hutter1.net/ http://prize.hutter1.net/ Also worth googling is Kolmogorov complexity.

tete 13y ago

Julia programming Julia? Pretty cool too! That's how you recognize a real hacker...

jvns 13y ago
=D Since a lot of the Julia core is written in Julia, it's also possible to have Julia working on Julia in Julia.

aortega 13y ago

This is a demonstration of a simplified LZ77 algorithm, not Gzip. Gzip is a unix utility, LZ77 is an algorithm, this distinction is not pedantic. This is what happens when you go to "hacker school" before regular CS school.

zackbloom 13y ago
That last line was not necessary, there are plenty of people with CS degrees who wouldn't know the difference between different versions of LZW.
- aortega 13y ago
  Yet the basic premise of the video is still wrong. Gzip uses many algorithms internally, among them LZ77 and huffman. It's like doing a video about "this is how mysql works" and showing the quicksort algorithm.
  - nbevans 13y ago
    I agree with you. Gzip is merely a container format, just like AVI, MKV are for video/audio content. Gzip supports several compression encodings with Deflate being the the most common one I believe.
shawabawa3 13y ago
> Gzip is a unix utility, LZ77 is an algorithm, this distinction is not pedantic. It's basically the definition of pedantic. Gzip uses the LZ77 algorithm, so it's a simplified demonstration of what gzip does. It's also a simplified demonstration of LZ77.
- jvns 13y ago
  The video title is in fact not quite accurate -- I chose to err in the direction of "cool soundbyte", since "LZ77 + poetry = awesome" doesn't have quite the same ring. aortega is quite right that this video actually explains LZ77, which is only one part of how gzip compresses. gzip (or the DEFLATE algorithm) also uses Huffman coding to compress the alphabet and pointers after LZ77 compression. I explain a bit more about the phases at http://jvns.ca/blog/2013/10/23/day-15-how-gzip-works http://jvns.ca/blog/2013/10/23/day-15-how-gzip-works And if you really want to know how it works, you should read http://www.infinitepartitions.com/art001.html http://www.infinitepartitions.com/art001.html, which is the reference I used for writing my implementation of gunzip. It includes C source code. The dig at hacker schoolers was unnecessary, though :)

ot 13y ago

Compression is truly fascinating. It's what got me into reading computer science papers several years ago, and then became one of my research topics. What is shown here is the LZ77 [1] factorization of a string. Compression in general works by exploiting redundancy in the source, and natural language is highly redundant, since many words repeat often. Hence the factors in the factorization often look like frequent words or n-grams. A recent line of research is grammar compression, which tries to turn a text into a tree of rules that generate that text. While still not very good at general-purpose compression, the generated tree are much more interesting than the LZ77 factorization, since they "discover" something that looks like a syntactic parsing of the string, finding syllabes, words, phrases, sentences... In Craig Nevill-Manning's Ph.D. thesis [2] introduction there are several examples of the inferred grammar of pieces of text, music, fractals, source code, etc... While the algorithm presented there (Sequitur) is now kind of obsolete, the thesis is very interesting because it makes some considerations with a linguistic perspective. [1] http://en.wikipedia.org/wiki/LZ77_and_LZ78 http://en.wikipedia.org/wiki/LZ77_and_LZ78 [2] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.5.1112&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.5.1...

jmmcd 13y ago
Wow, that PhD thesis is very interesting. I use grammars to generate music (and other things sometimes), but I would also really like to be able to infer them. Since you say it's obsolete, do you have any links to papers or software related to successors of the Sequitur algorithm?
- ot 13y ago
  It depends on what you want to do. RePair [1] is currently the best grammar-based compressor, but it doesn't give good theoretical guarantees. In theory, instead, there is an O(log n) approximation to the smallest grammar problem [2], but AFAIK doesn't work very well in practice. In the same paper there is a good introduction to the problem and an analysis of the previous algorithms, including Sequitur. [1] http://www.larsson.dogma.net/dcc99.pdf http://www.larsson.dogma.net/dcc99.pdf [2] http://www.cs.virginia.edu/~shelat/papers/GrammarIEEE.pdf http://www.cs.virginia.edu/~shelat/papers/GrammarIEEE.pdf

daronphq672 13y ago

my parents inlaw recently got a very nice Mercedes-Benz C-Class Convertible by working part time off of a pc. this contact form .............http://www.BAM21.CoM http://www.BAM21.CoM

V-2 13y ago
That's just great! Many thanks for the info.
- V-2 13y ago
  chill out downvoters, I was being sarcy

annnnd 13y ago

I get this: Offline Site: jvns.ca You have requested a site that is currently offline. This generally happens when a site is temporarily disabled for some reason, but has not been permanently removed...

josephb 13y ago
Unexpected HN traffic is likely to have used all the site owners pre-paid credit. Edit: To clarify, NearlyFreeSpeech hosting is prepaid.
- jvns 13y ago
  Yup, apparently the $2 I had left in my account didn't cover it. Back up now!

heyadayo 13y ago

Mirror: https://web.archive.org/web/20131025035238/http://jvns.ca/blog/2013/10/24/day-16-gzip-plus-poetry-equals-awesome/ https://web.archive.org/web/20131025035238/http://jvns.ca/bl... http://www.youtube.com/watch?feature=player_embedded&v=D2JWSNDgkoE http://www.youtube.com/watch?feature=player_embedded&v=D2JWS...

Jotace 13y ago

Today the site is down...

_quasimodo 13y ago

As the author mentioned, poetry usually compresses quite well, thanks to rhyming. Here is another fun example: http://codegolf.stackexchange.com/questions/6043/were-no-strangers-to-code-golf-you-know-the-rules-and-so-do-i http://codegolf.stackexchange.com/questions/6043/were-no-str...

pdknsk 13y ago

What I noticed in the other text, Hamlet, is that HAMLET in the last sentence has no pointer to Hamlet, obviously. This seems like an opportunity for optimisation, for text at least. Usually a word is either lowercase, capitalised or uppercase. In more complex and rare cases this could be efficiently encoded bitwise (0 = keep, 1 = swap case), so HAMLEt becomes 011110 plus a pointer to Hamlet. I wonder if any compression algorithm does this. Probably not, because the benefit is likely minimal at significantly increased de/compression time.

cbhl 13y ago
One problem is that way of thinking is distinctly ASCII-centric -- what happens when you have accents, umlats, Chinese, and the rest of the stuff that comes out of Unicode? I suspect the encoding you propose would actually increase the size of the average plaintext, simply because people rarely will type "Hamlet" and then later type "HaMlEt" in the same document. I think a far more common case would be "Hamlet" (beginning of sentence) and "hamlet" (inline), where you can reuse the substring "amlet". (Either that, or they're consistent with the usage of all-caps, like MICROSOFT(R).) Besides, if you know you're doing English, you can save 12.5% simply by using 7-bit ASCII instead of of 8-bit ASCII.
- pdknsk 13y ago
  It seems simple enough to implement case-pairs for Unicode. Most likely it already is. Either way, you're right. It was just a simple idea.
  - judk 13y ago
    http://www.unicode.org/faq/casemap_charprop.html http://www.unicode.org/faq/casemap_charprop.html Still provincial
apw 13y ago
Your idea is good, and many modern compression systems, like the PAQ system, exploit it [1]. [1] https://en.wikipedia.org/wiki/PAQ#Text_preprocessing https://en.wikipedia.org/wiki/PAQ#Text_preprocessing