|Perl: the Markov chain saw|
Efficient 7bit compressionby Limbic~Region (Chancellor)
|on Mar 14, 2005 at 15:21 UTC||Need Help??|
Limbic~Region has asked for the wisdom of the Perl Monks concerning the following question:
hacker asked in this question how to compress relatively short strings. He had a unique goal in mind with specific requirements. Since the only way I could think to do it likely wouldn't meet his requirements, I provided an intentional obfu solution. The general idea is to use 7 bits to store each character. This gives a 12.5% reduction in size but only supports ASCII 0-127.
This wasn't as straight forward as I had guessed. I asked around in the CB if there was something I was missing which apparently I wasn't. diotalevi indicated that this was one of the first problems he tried solving in Perl. Traditional compression techniques fail because with short strings they end up being bigger than the original. When you can afford the runtime cost but not the disk space (apparently every MB had to be justified during the campaign he was working), 7bit strings start to look appealing.
I mentioned on Monday (today) that I would try to provide a more straight forward solution as well as multiple implementations. One for runtime speed (assuming RAM isn't a factor), one for RAM, and one that balances both.
I didn't do very well. I was hoping others would find the task fun and provide better solutions. Here is my solution optimized for memory.
Cheers - L~R