| |
ChristopherJam
Registered: Aug 2004
Posts: 1423 |
On the relative pros and cons of various RLE schemes
So over in Native crunch/decrunch code. I just suggested encoding
abbcdddeffffg as
abb{0}cdd{1}eff{2}g
Raistlin kindly liked the idea, Krill quite sensibly didn't want us to hijack the post and suggested a new post for the new topic. so... Have at it! |
|
... 38 posts hidden. Click here to view all posts....
|
| |
Bitbreaker
Registered: Oct 2002
Posts: 510 |
Quoting Krill
RLE used to be LZ-crunched anyways, so RLE compression ratio wasn't much of a concern.
What is kind of hard to understand, as LZ includes RLE by design (match with offset 1) |
| |
Krill
Registered: Apr 2002
Posts: 3066 |
Quoting JackAsserCheck any Dinosours release and you'll get the point. :D I was aware that Dinasours pack everything 10 times for comedic effect,
but i thought maybe they've released the Airwolf Fixer of crunchers or something and i've missed that. :) |
| |
Krill
Registered: Apr 2002
Posts: 3066 |
Quoting BitbreakerQuoting Krill
RLE used to be LZ-crunched anyways, so RLE compression ratio wasn't much of a concern.
What is kind of hard to understand, as LZ includes RLE by design (match with offset 1) Native LZ crunchers used to require quite a bit of working memory, so the maximum size of input programs was often smaller than entirely uncompressed programs.
Thus RLE first, then LZ. Also this two-pass approach can make for better overall compression ratio. |
| |
Jetboy
Registered: Jul 2006
Posts: 354 |
Quoting KrillThus RLE first, then LZ. Also this two-pass approach can make for better overall compression ratio.
Puls LZ ones were rather slow, so prepacking with RLE first could save substantial amounts of time. As shorter file to pack tends to pack quicker. |
| |
enthusi
Registered: May 2004
Posts: 679 |
Just to add an alternative which is a bit special but cute:
Maniac Mansion and ZMK use some RLE depacker that resides in ZP and encodes most-common bytes, which I felt works rather well for graphics. I wrote something about that here:
https://www.pagetable.com/?p=603
A byte of < $40 = count of raw bytes following
$3f to < $80 represents the length of the run of the byte to follow (+$3f of course).
$7f to < $a0 is the number of runs of most common byte 1,
$9f to < $c0 and $bf to <$e0 and $df-$ff for common byte 2, 3 and 4 respectively. |
| |
ChristopherJam
Registered: Aug 2004
Posts: 1423 |
ooh, I like that one enthusi.
Really interesting the historical divide between packers and crunchers, especially the way intros tended to be displayed between one and the other. It does indeed reduce the impact on runlength limits considerably. Not sure why I ever bothered trying to improve the ratio of my higher ratio crunchers for empty spaces now :P |
| |
Martin Piper
Registered: Nov 2007
Posts: 739 |
In the old days, dictionary based compression would be quite slow and memory hungry. The usual way of speeding it up would be to limit the distance searched and limit the dictionary.
Using a RLE compression pass before a dictionary compression stage would reduce the total input data, it would reduce the strain on the dictionary, and would pass some benefit along to the dictionary based compression.
As dictionary algorithms improve, and also as time and memory becomes less of an issue, the dictionary size can be increased and this means there is less benefit to shrinking the input data with a RLE pre-pass. |
| |
Fungus
Registered: Sep 2002
Posts: 736 |
Main reason for packing first was before crunchers had REU versions with 2mhz or 8mhz support they were slow as hell and took many hours. So smaller input files crunched way faster. Also crunching large files tended to bug out. They generally were smaller too, so it became the norm. |
| |
Starfox
Registered: Jul 2014
Posts: 45 |
I researched a lot about RLE a year ago.
Forgot most of it, lol!
But you can preprocess the data before run-length encoding it, to make the RLE more successful.
There were a couple of schemes used, which were probably mostly optimized for text. Burrows-Wheeler Transform for instance.
I have my notes at home, let me see if there's anything useful. |
| |
Martin Piper
Registered: Nov 2007
Posts: 739 |
Quote: I researched a lot about RLE a year ago.
Forgot most of it, lol!
But you can preprocess the data before run-length encoding it, to make the RLE more successful.
There were a couple of schemes used, which were probably mostly optimized for text. Burrows-Wheeler Transform for instance.
I have my notes at home, let me see if there's anything useful.
If I recall, reversing BWT encoded data needs a few sorts for each stored string. Which makes it quite expensive? Creating the BWT data also needs a sort, but I don't care about that so much. |
| Previous - 1 | 2 | 3 | 4 | 5 - Next |
