With the recent discussion about the use of compression tools in code golf, I thought it would be a nice challenge to write your own text compressor and decompressor.
Challenge:
Write two programs: one to compress ASCII text into a sequence of bytes, and another to decompress it. The programs need not be in the same language.
The first program should read a piece of ASCII text (from a file or from standard input, or using whatever mechanism is most natural to the language) and output a compressed version of it. (The compressed output may consist or arbitrary bytes; it need not be readable.) The second program should read the output of the first and recreate the original input text.
Scoring:
The score of a solution will be the sum of the following three counts:
- The length of the compressor program in characters.
- The length of the output of the compressor, given the test input below, in bytes.
- The length of the decompressor program (if different from the compressor) in characters.
You should note all three counts and their sum in your answer. Since this is code golf, the lower the score, the better.
Rules and restrictions:
You may not use any pre-existing compression or decompression tools or libraries, even if they come bundled with your chosen language. If in doubt about whether a given tool or function is allowed, please ask.
Your compressor program must be capable of handling input consisting of any printable ASCII text, including tabs (ASCII 9) and line feeds (ASCII 10). You may, but are not required to, handle arbitrary Unicode and/or binary input.
Your decompressor program must produce exactly the same output as was given to the compressor as input. In particular, take care not to output a trailing line feed if the input did not have one. (The test input below does have a trailing line feed, so you'll need to test for this separately. Tip for GolfScript:
'':n
.)Your compressor and decompressor may be the same program (with the appropriate mode selected e.g. with a command line switch). In that case, its length is only counted once.
The programs should not be exceedingly slow or memory-hungry. If either compressing or decompressing the test input takes more than a minute on my not-so-new desktop (2.2GHz AMD Athlon64 X2) or consumes more than a gigabyte of RAM, I'm going to rule the solution invalid. These limits are deliberately lax — please try not to push them. (See amendment below: you need to be able to handle at least 100 kB of input within these limits.)
Even though only the test input matters for scoring, you should at least make an effort at compressing arbitrary input text. A solution that achieves a decent compression ratio only for the test input, and for nothing else, is technically valid but isn't going to get an upvote from me.
Your compressor and decompressor programs should be self-contained. In particular, if they depend on being able to read some file or network resource that is not part of your chosen language's standard runtime environment, the length of that file or resource should be counted as part of the length of the program(s). (This is to disallow "compressors" that compare the input to a file on the web and output zero bytes if they match. Sorry, but that's not a new trick anymore.)
Amendments and clarifications:
Your compressor must be able to handle files consisting of at least 100 kB of typical English text within reasonable time and memory usage (at most one minute and one GB of memory). Your decompressor must be able to decompress the resulting output within the same limits. Of course, being able to handle files longer than that is perfectly fine and commendable. It's OK to split long input files into chunks and compress them individually, or to use other means to trade off compression efficiency for speed for long inputs.
Your compressor may require its input to be given using your preferred platform's native newline representation (LF, CR+LF, CR, etc.), as long as your decompressor uses the same newline representation in its output. Of course, it's also fine for the compressor to accept any kind of newlines (or even only Unix newlines regardless of platform), as long as your decompressor then outputs the same kind of newlines as in the original input.
Test input:
To judge the compression efficiency of the answers, the following test input (The Raven by Edgar Allan Poe, courtesy of Project Gutenberg) will be used:
Once upon a midnight dreary, while I pondered, weak and weary,
Over many a quaint and curious volume of forgotten lore,
While I nodded, nearly napping, suddenly there came a tapping,
As of some one gently rapping, rapping at my chamber door.
"'T is some visiter," I muttered, "tapping at my chamber door--
Only this, and nothing more."
Ah, distinctly I remember it was in the bleak December,
And each separate dying ember wrought its ghost upon the floor.
Eagerly I wished the morrow:--vainly I had sought to borrow
From my books surcease of sorrow--sorrow for the lost Lenore--
For the rare and radiant maiden whom the angels name Lenore--
Nameless here for evermore.
And the silken sad uncertain rustling of each purple curtain
Thrilled me--filled me with fantastic terrors never felt before;
So that now, to still the beating of my heart, I stood repeating
"'T is some visiter entreating entrance at my chamber door
Some late visiter entreating entrance at my chamber door;--
This it is, and nothing more."
Presently my soul grew stronger; hesitating then no longer,
"Sir," said I, "or Madam, truly your forgiveness I implore;
But the fact is I was napping, and so gently you came rapping,
And so faintly you came tapping, tapping at my chamber door,
That I scarce was sure I heard you"--here I opened wide the door;--
Darkness there, and nothing more.
Deep into that darkness peering, long I stood there wondering, fearing,
Doubting, dreaming dreams no mortal ever dared to dream before;
But the silence was unbroken, and the darkness gave no token,
And the only word there spoken was the whispered word, "Lenore!"
This I whispered, and an echo murmured back the word, "Lenore!"
Merely this and nothing more.
Back into the chamber turning, all my soul within me burning,
Soon again I heard a tapping, somewhat louder than before.
"Surely," said I, "surely that is something at my window lattice;
Let me see, then, what thereat is, and this mystery explore--
Let my heart be still a moment and this mystery explore;--
'T is the wind and nothing more!"
Open here I flung the shutter, when, with many a flirt and flutter,
In there stepped a stately Raven of the saintly days of yore.
Not the least obeisance made he; not a minute stopped or stayed he;
But, with mien of lord or lady, perched above my chamber door--
Perched upon a bust of Pallas just above my chamber door--
Perched, and sat, and nothing more.
Then this ebony bird beguiling my sad fancy into smiling,
By the grave and stern decorum of the countenance it wore,
"Though thy crest be shorn and shaven, thou," I said, "art sure no craven,
Ghastly grim and ancient Raven wandering from the Nightly shore,--
Tell me what thy lordly name is on the Night's Plutonian shore!"
Quoth the Raven, "Nevermore."
Much I marvelled this ungainly fowl to hear discourse so plainly,
Though its answer little meaning--little relevancy bore;
For we cannot help agreeing that no living human being
Ever yet was blessed with seeing bird above his chamber door--
Bird or beast upon the sculptured bust above his chamber door,
With such name as "Nevermore."
But the Raven, sitting lonely on the placid bust, spoke only
That one word, as if his soul in that one word he did outpour.
Nothing further then he uttered--not a feather then he fluttered--
Till I scarcely more than muttered, "Other friends have flown before--
On the morrow _he_ will leave me, as my hopes have flown before."
Then the bird said, "Nevermore."
Startled at the stillness broken by reply so aptly spoken,
"Doubtless," said I, "what it utters is its only stock and store,
Caught from some unhappy master whom unmerciful Disaster
Followed fast and followed faster till his songs one burden bore--
Till the dirges of his Hope that melancholy burden bore
Of 'Never--nevermore.'"
But the Raven still beguiling all my sad soul into smiling,
Straight I wheeled a cushioned seat in front of bird and bust and door;
Then, upon the velvet sinking, I betook myself to linking
Fancy unto fancy, thinking what this ominous bird of yore--
What this grim, ungainly, ghastly, gaunt and ominous bird of yore
Meant in croaking "Nevermore."
This I sat engaged in guessing, but no syllable expressing
To the fowl whose fiery eyes now burned into my bosom's core;
This and more I sat divining, with my head at ease reclining
On the cushion's velvet lining that the lamplight gloated o'er,
But whose velvet violet lining with the lamplight gloating o'er
_She_ shall press, ah, nevermore!
Then, methought, the air grew denser, perfumed from an unseen censer
Swung by seraphim whose foot-falls tinkled on the tufted floor.
"Wretch," I cried, "thy God hath lent thee--by these angels he hath sent thee
Respite--respite and nepenthe from thy memories of Lenore!
Quaff, oh quaff this kind nepenthe, and forget this lost Lenore!"
Quoth the Raven, "Nevermore."
"Prophet!" said I, "thing of evil!--prophet still, if bird or devil!--
Whether Tempter sent, or whether tempest tossed thee here ashore,
Desolate yet all undaunted, on this desert land enchanted--
On this home by Horror haunted--tell me truly, I implore--
Is there--_is_ there balm in Gilead?--tell me--tell me, I implore!"
Quoth the Raven, "Nevermore."
"Prophet!" said I, "thing of evil--prophet still, if bird or devil!
By that Heaven that bends above, us--by that God we both adore--
Tell this soul with sorrow laden if, within the distant Aidenn,
It shall clasp a sainted maiden whom the angels name Lenore--
Clasp a rare and radiant maiden whom the angels name Lenore."
Quoth the Raven, "Nevermore."
"Be that word our sign of parting, bird or fiend!" I shrieked, upstarting--
"Get thee back into the tempest and the Night's Plutonian shore!
Leave no black plume as a token of that lie thy soul hath spoken!
Leave my loneliness unbroken!--quit the bust above my door!
Take thy beak from out my heart, and take thy form from off my door!"
Quoth the Raven, "Nevermore."
And the Raven, never flitting, still is sitting, still is sitting
On the pallid bust of Pallas just above my chamber door;
And his eyes have all the seeming of a demon's that is dreaming,
And the lamplight o'er him streaming throws his shadow on the floor;
And my soul from out that shadow that lies floating on the floor
Shall be lifted--nevermore!
The correct test input (encoded with Unix-style LF newlines) should be 7043 bytes long, and have the hexadecimal MD5 hash 286206abbb7eca7b1ab69ea4b81da227
. (md5sum -t
should produce the same hash value even if you use CR+LF newlines on DOS/Windows.) The output of your decompressor should have the same length and hash.
Ps. Keep in mind that this challenge is only as hard as you make it. Really, anything under 7043 counts as a good score. (At the other end of the scale, I'll be extremely impressed if anyone achieves a score under 2500.)