Optimal LZ coding
ZXNet echo conference «code.zx»
Hello, All
Situation: there is a certain file, you want to pack it using the LZ method.
I load the file into memory and for each byte I build a set of all those that match it
LZ codes (length, offset, code size in bits).
What you need to do is: select the optimal chain of these codes and generate the shortest one
possible output packed files.
Question: how? =)
I'm making a megalz packer on my site.
Hello, lvd
lvd> Situation: there is a certain file, you want to pack it using the LZ method.
lvd> I load the file into memory and for each byte I build a set of all matching ones
lvd> LZ codes (length, offset, code size in bits).
lvd>
lvd> What you need to do is: select the optimal chain of these codes and generate the best one
lvd> short of possible output packed files.
lvd>
lvd> Question: how? =)
lvd>
lvd> I'm making a megalz packer on my side.
What platform?
Perhaps it will help to imagine the code as a pass through a graph, and the optimal one in
in the sense of code length, as a path through a graph of minimum length.
Hello, lvd
lvd> Situation: there is a certain file, you want to pack it using the LZ method.
Look at the source, I hope it helps.
File: lz_src.zip http://zx.pk.ru/attachment.php?attachmentid=2109
Hello, lvd
lvd> Situation: there is a certain file, you want to pack it using the LZ method.
Look at the source, I hope it helps.
File: lz_src.zip http://zx.pk.ru/attachment.php?attachmentid=2109
Hello, valker
val> What platform?
val>
What difference does it make if I’m writing in my own words... I certainly didn’t spell it! =) Eats up memory
in black, so not dos either. :)
> Perhaps it will help to present the code as a walk through a graph, a
> optimal in terms of code length, as a path along a graph of minimum length.
Well, yes - and how to find this path of minimum length? ;)
Hello, lvd
here there are n number of articles on the topic of non-greedy/lazy parsing for LZ*
algorithms:
http://www-koi.compression.ru/download/lz.html
they do not give the optimal result, but they improve compression by choosing more correct ones
chains...
Hello,Hrumer
In addition: yeah, I understand what you mean. Minimizing the number of pairs (length offset)
and literals does not mean that the file will be of minimal length. But for that
Most likely, such a file will be the fastest to unpack. Although the gain
The unpacking speed will probably be less than 0.1%.
Hello, valker
Valker: optimality of coding can be at least 2 types: optimality in
in the sense of the size of the packed file, and optimality in the sense of minimizing
number of pairs (length offset) and literals. Which one do you mean?
Hello,Hrumer
Hru> Valker: optimal coding can be of at least 2 types:
Hru> optimality in terms of the size of the packed file, and optimality in
Hru> in the sense of minimizing the number of pairs (length offset) and literals. Which
Hru> do you mean?
Hrumer, thank you for sending me in the right direction in the email :) I found the same thing
only later in infoguide #6 =)
Valker, in essence, Dijkstra’s algorithm is the same as what Khroomer suggested to me (and what in
infoguide #6), only in the second case it is simplified in relation to a specific
type of trees.
elf/2, yeah 10x, I downloaded everything, tomorrow I’ll get to the computer where it was downloaded and take a look
=))
Hello caro
car> Look at the sources, I hope it helps.
Hmm... there's not even a hint of the optimal choice of chain... =)
Hello caro
car> Three options are given, which on the same test file give
car> different packing results.
car>
Of which one is with Huffman after LZ, and the other is with arithm. coding after
LZ. I only have LZ =)
> I think there is no need to wait for a ready-made solution to the problem :)
Yes, Khrumer gave one hint in the email - I’ll dig there =)
Hello, lvd
lvd> What difference does it make if I’m writing in my own words... I’m certainly not speculating! =) Eating memory
lvd> in black, so don't dos either. :)
lvd>
lvd> Well, yes - and how to find this path of minimum length? ;)
If pure C, then implement Dijkstra's algorithm (it is suitable for
non-negative weights).
If C++, then take BGL (Boost Graph Library), there is this algorithm (and many
others) has already been implemented.
Good luck!
Hello, lvd
lvd> Hmm... there's not even a hint of the optimal choice of chain... =)
Three options are given, which give different results on the same test file
packaging results.
I think there is no need to wait for a ready-made solution to the problem :)
Hello,Hrumer
Hru> Valker: optimal coding can be of at least 2 types:
Hru> optimality in terms of the size of the packed file, and optimality in
Hru> in the sense of minimizing the number of pairs (length offset) and literals. Which
Hru> do you mean?
In the sense of the length of the received code in bits.
Hello, lvd
So, preliminary results. If the old megalz made files of 10-20 bytes
longer (or even less than 10 bytes) than crunch2, then with this algorithm it does crunch in
hundreds of bytes! Khrum3.5 generally rests (even with the subtraction of 150 bytes from the length). Rip
Naturally, he steers everyone - but that’s why he’s a half-man. The only puncture is on
in one file the crunch killed everyone. This was the asm output of the msvc compiler =)
Hello,Hrumer
Hru> 2lvd: it would be interesting to look at the results table.
Hru>
Now I’ll comb the code a little more - and there will be a release =) there will be advertising tables,
and even test files =) If it doesn’t break me...
> The next step, apparently, will be to consider other codes - just
> for experiment.
>
I'll most likely be screwed =)
> What codes do you use? (look at it for a long time
> unpacker)
like this:
┌─- code ───
Packed file format:
the first byte is copied to the output
second - goes to bits
bits in a byte of bits - most significant.
If a bit is needed, but it is no longer there (all 8 are gone), then a new byte is selected
from the stream. The bytes designated are also selected from there - but only
after fetching all the bits of the link.
In link format: - the byte that is selected from the stream
1 - copy to the output.
000abc - copy 1 old byte at offset FFF8+[abc] from the current position to
exit
(abc==000 - offset FFF8, abc==111 - FFFF)
001 - copy 2 bytes at offset FF00+ (-1..-256)
0100 - copy 3 bytes at offset FF00+
0101abcd - copy 3 bytes at offset (F[abcd]-1)*256+
(-257..-4352)It is convenient to present longer links in the form of 3 parts:
prefix: 011
link length:
1a -> 4+[a]
01ab -> 6+[ab]
001abc -> 10+[abc]
0001abcd -> 18+[abcd]
00001abcde -> 34+[abcde]
000001abcdef -> 66+[abcdef]
0000001abcdefg -> 130+[abcdefg] (here the length is no more than 255!)
offset:
0 - FF00+ back (-1..-256)
1abcd - (F[abcd]-1)*256+ (-257..-4352)
End of stream mark:
011000000001
examples:
000111 - repeat last byte
001 - repeat last byte twice (offset=-1, length 2) -
combination of LZ and RLE!!!!!
011 001101 10000 - link length %101+10 = 15 bytes with offset -4352
└── code ───
Hello,GriV
2lvd> read more carefully, there are a couple of interesting ones that follow from the general theory
2lvd> conclusions that are interesting to you as well. Search for optimal language commands
2lvd> LZ* - in general the task of an expert system and for files of different content
2lvd> (text, media, code) this problem will be solved in different ways (i.e. give
2lvd> different result, the same example was given by Caro actually). Example with the same
2lvd> LC - its commands, in general, are very well chosen for compressing images,
2lvd> however, it is highly doubtful that using LC it will be possible to effectively text
2lvd> or compress the code - its control codes are tailored for something else.
Therefore, there is no universal sequence, this is exactly what follows from the reference,
which was before the mathematician and the balloon.
If you want to make something completely mega-universal, make, say, 256 pieces
sets of control commands - each of which will be selected for the compressible
file - and in the end you will have an invariably brilliant result - for the unpacker
discrete, the entire set of commands (256 tables) is still known, but for
an unpacker integrated with the archive, even more so - it was originally
will be tailored to a given combination.Having fantasized a little (what was a little higher are banal realities
:-D) you can figure out this: the compressed file is divided into blocks of several
kilobytes, each of which is compressed according to the optimal table - the total will be
not just brilliant - but simply an excellent result, unsurpassed in principle.
A little off-topic - here one friend also wrote a packer... which all files in
Compressed 32 bytes (-; I was so happy for it, it’s a pity it’s a working algorithm -
working code - didn't show... (-%
Hello, lvd
lvd> I don't need halfman and rle at all. Exclusively lz codes
lvd> exclusively find their optimal chain, and as many have advised
lvd> - Dijkstra algorithm. Without any theories =)
The joke was of course the steering wheel (-%, and on topic (-%
It's not about RLE or Huffman at all - it's about the approach - it can also be used for chains
LZ* use :-D, and you will have to solve the same minimization problem over related
parameters in nonlinear space.
Hello,GriV
Gri> 2lvd> read more carefully, there are a couple that follow from the general theory
Gri> interesting conclusions, interesting for you as well. Search
Gri> optimal commands of the LZ* language is generally the task of the expert system and for
Gri> files of different content (text, media, code) this task is different
Gri> will be solved (i.e. give different results, the same example was given
Gri> Caro actually). An example with the same LC - his commands are generally very
Gri> are well chosen for image compression, but it is highly doubtful that
Gri> using LC it will be possible to effectively compress text or code - it
Gri> control codes are tailored for something else.
Gri> And therefore there is no universal sequence, this is exactly what follows
Gri> from a reference that was before the mathematician and the balloon.
Gri> If you want to do something completely mega-universal, do it
Gri> let's say, there are 256 sets of control commands - each of which will be
Gri> match the file being compressed - and in the end you will invariably haveGri> brilliant result - for a discrete unpacker it’s still all
Gri> the set of commands (256 tables) is known, and for the unpacker
Gri> integrated with the archive, even more so - it will initially be
Gri> is tailored to a given combination.
Gri>
Uh. I want (wanted) only to pack the most under the existing unpacker
optimal. That's it. It worked. It’s not in my plans to rewrite the unpacker
included. Here.
> A little off-topic - here one friend, also a packer, wrote... which
> compressed all files into 32 bytes (-; I was so happy for him, I feel sorry for him
> working algorithm - working code - did not show... (-%
Gee. It is easy to prove that this is impossible. =)
Hello SMT
SMT> hmm. there was a competition with a prize of a million bucks for the one who would make an archiver
SMT> compresses any file by at least 1 byte. Well, there was a smart guy who
SMT> did. formally the program satisfied all the criteria and passed everything
SMT> tests :) only when the organizers figured out that simple thing
SMT> algorithm, they bastards squeezed the money :( rednecks
SMT>
SMT> (if anyone hasn’t heard this story, I can post the algorithm)
If I remember correctly it used the file name as additional memory.
Hello caro
car> If I remember correctly, he used the file name as an additional one
car> memory.
Ha-ha, well, it’s right that they clamped down, because the cheater is vile! =)
Hello SMT
SMT> hmm. there was a competition with a prize of a million bucks for the one who would make an archiver
SMT> compresses any file by at least 1 byte. Well, there was a smart guy who
SMT> did. formally the program satisfied all the criteria and passed everything
SMT> tests :) only when the organizers figured out that simple thing
SMT> algorithm, they bastards squeezed the money :( rednecks
SMT>
SMT> (if anyone hasn’t heard this story, I can post the algorithm)
Post it. This cannot happen in principle.
Hello SMT
SMT> I disagree. there was no point in fussing when the rules were drawn up. gave
SMT> word - take it!
So let’s take into account the information about the file lengths - and that’s it. =)
Hello,Hrumer
Hru> 2caro: Yes, it looks like I heard this story.. Someone revealed a certain
Hru> is a symbol that exactly occurs in the file, and it was used to split the file into
Hru> several. The symbol itself was naturally not written to the output files.
Hru> The file names were apparently used so that it was possible
Hru> correctly merge these files...
Not only the names, but also the lengths of the files - the places where the symbol was inserted were marked, i.e.
were additional bits of information.
Hello, lvd
that's right, there was a file 1.txt with the content "Hello", it became 1-48.txt with the content
"ello", then became 1-48-65.txt with "llo", etc...
Hello, lvd
lvd> Ha-ha, well, it’s right that they clamped down, because the cheater is vile! =)
I don't agree. there was no point in fussing when the rules were drawn up. gave his word -
hold it!
Hello, lvd
2caro: Yes, it seems I heard this story.. Some people showed a certain symbol,
which is exactly found in the file, and using it to split the file into several. Himself
The symbol, of course, was not written to the output files. The file names appear to be
were used so that these files could be glued together correctly...
Hello SMT
2SMT: As I heard, initially this point was not specified in the rules at all, but
in further correspondence, the “author” of the dispute agreed that after packaging the file
the packaging result could be in several files... Here is the castati, there is a page
somewhere on the Internet by Leonid Brukhis (if I’m not mistaken) - there is a bet about compression...
Hello, lvd
hmm. there was a competition with a prize of a million bucks to the one who would make an archiver that compressed
any file at least 1 byte. Well, there was a smart guy who did it. formally
the program met all the criteria and passed all the tests :) only when
the organizers figured out that simple algorithm, they bastards squeezed the money
:( goons
(if anyone hasn’t heard this story, I can post the algorithm)
Hello Vitamin
Vit> already compressed by different packers
they increase by 1/8, i.e. by 12.5%. Always.
Hello jtn
jtn> they increase by 1/8, i.e. by 12.5%. always.
depends on the packer used for compression. and on the method of current packaging. when I
tested arithmetic compression, tried to compress wheezing files - 10..15%
won. but for rip the results were much worse - literally a few bytes
(I suspect it's in the title)
Hello Vitamin
Vit> depends on the packer used. and on the method of current packaging. I
Vit> when testing arithmetic compression, I tried wheezing files
Vit> squeeze - 10..15% won. but for rip the results were much better
Vit> worse - literally a few bytes (I suspect it's in the header)
And when you tested LZ compression, how much did you get? =)
Hello Vitamin
Vit> well, as I say, the crunch was compressed by 10...15% (and this is LZSS if I’m okay
Vit> I'm not confusing). in particular, a packed text of 10kb was compressed into approximately
Vit> 8.5. The results of the program are in one of the infoguide numbers.
Why didn’t I get it right, then you did the arithm. I tested the compression, then LZSS... =)
Hello Vitamin
Vit> well, as I say, the crunch was compressed by 10...15% (and this is LZSS if I’m okay
Vit> I'm not confusing). in particular, a packed text of 10kb was compressed into approximately
Vit> 8.5. The results of the program are in one of the infoguide numbers.
Why didn’t I get it right, then you did the arithm. I tested the compression, then LZSS... =)
Hello, lvd
lvd> And when you tested LZ compression, how much did you get? =)
Well, I’m telling you, the crunch shrank by 10...15% (and this is LZSS if I’m not confusing anything).
in particular, a packed text of 10kb was compressed into approximately 8.5. program results
are in one of the infoguide rooms.
Hello, lvd
lvd> wow, I'm not right - then you're doing the arithm. I tested compression, then LZSS... =)
Please read my first post carefully:
"When I was testing arithmetic compression, I tried to compress wheezing files"
Hello Vitamin
Vit> Carefully read my first post:
Vit>
Vit> "when I tested arithmetic compression, I tried wheezing files
Vit> squeeze"
“Don’t be smart, just point your finger.” WHAT did you use to increase the wheezing by 10-15%? =)
Possible answers:
1. LZ* method
2. arithm. coding.
3. *?
Hello Vitamin
Vit> Arithmetic coding! (do not show finger in pseudographic
Vit> it turns out %)))
Well, then why are you suggesting that LZ reap what is already packaged? Press it packed with yours
arithm. that's all. =)
Hello Vitamin
Vit> for more complete statistics. very often found in code blocks
Vit> packed pieces (incbins). therefore it is worth checking this mode
Vit> work.
I had to sculpt code blocks completely unpacked, so
packed in parts (packed inkbins). And I can say that in the second
In any case, it never occurred to me to re-press what was packaged! (sorry only codes and
the data with them is unpacked).
And the statistics here are simple - as jtn correctly noted, the increase will be 1/8
due to the fact that bytes are encoded with 9 bits. Plus a VERY SMALL win
relative to 9/8 of the original size due to RANDOM RARE matches.
Hello, lvd
lvd> Well, then why are you suggesting that LZ reap what is already packaged? Click packed
lvd> with your own arithm. that's all. =)
for more complete statistics. very often found in code blocks
packed chunks (incbins). Therefore, it is worth checking this mode of operation.
Hello, lvd
explain to a fool how you can inkbind files into one code block, and then
pack in pieces?
Hello jtn
jtn> explain to a fool how you can ink files into one code block, and
jtn> then pack it in pieces?
You take it and inkbinish. Then you compile and debug. And when it comes to release
it comes, then with pens, pens =))
Hello, lvd
I don’t know who it is, but in crunch1 the “losses” on unpacked data are
less than 12.5%...
Hello,Hrumer
Hru> I don’t know who it is, but in crunch1 there are “losses” on unpacked data
Hru> are less than 12.5%...
Yeah, but for some it’s true that they can’t pack random data in principle, because
It was done so that the non-random ones were strictly packed =)
Hello, lvd
lvd> Yeah, but for some it’s true that they can’t pack random data into
lvd> in principle, it was done so that non-random ones were purely packed =)
I suggested typing, say, at least three sets of commands - one for
initially compressed and poorly compressible data (so that a minimum of additions
was when transferring data to packed ones), the second for normal files (there
classical sequences, at least the same as in Hrast) and the third, let’s say
for multimedia
Hello, aprisobal
apr> I wanted to make this post for a long time, but there was no reason. And here is just LVD
apr> made by MegaLZ. I liked it, and especially the fact that there is a packer under
apr> Win.
apr>
apr> In general, there is a fairly strong compressor for the Commodore64
apr> PuCrunch
Yes, yes, I know that one! I read about him in some C=hacking issue, and in many ways
He became a fan of the creation of this MegaLZ. And ideas for speeding up packing
I squeezed some from there :)
And how it presses - I don't know, I was interested purely theoretically. It's cool that he's better
It turned out to be a kind of wretched 6502 =)
Hello axor
axo>
lvd> Here's a release for you all! From now on MegaLZ is the best LZ-only packer
lvd> axo> on spec! =)))))
lvd> axo>
lvd> axo> Can this be done for a real Spectrum? :)
lvd> axo>
lvd>
lvd> You can. But the cars are 512kb (no less) and very slow. By the way, who
lvd> the first one to do this on spec under tyrdos (files should be obtained
lvd> is the same length [or shorter, hehe =] as in PC called without
lvd> arguments), I will give you 6 bottles during a personal meeting
lvd> 2 liter Pepsi. =)) Another condition is support for universal drivers
lvd> memory ala al-asm. Yes, and it should be unpacked with 'branded'
lvd> 110 bytes, which is in the archive. Otherwise you'll do a lot there. :)
lvd>
lvd>
> lvd> Something even for a pussy, the packer archive is big or am I in something wrong
> lvd> moved in?
> lvd>
>
> What does big mean? The size of the EXE that msvts6 gives is 53kb. In addition> there is also an exe for Linux and for Amiga.
>
> [quote]
> And the unpacker, as I understand it, remains Spekov's?
And not only!
Hello Specter
Spe> But I am more interested in the packager in terms of packaging new versions of QC,
Spe> for which I compiled the latest beta version (QC.C file) and packaged
Spe> it using mehaLZ and QC4.00i. Result: hrust2!4 algorithm wins
Spe> for 133 bytes. ;)
Probably a ton of zeros? =) And does this take into account the length of the depacker?
Hello, lvd
Regarding crunch 2.1, I would like to say that this is already an outdated version. Last
modification from Alone Coder is version 2!4. It has fixed the proprietary
bug with loss of packing density, added algorithm for finding the best link
(lazy evaluation), 32Kb window, plus various little things.
Reducing the window size when there is insufficient memory also has a strong effect.
which worsens compression.
For comparison, I packaged all test files using QC v4.00i (beta version),
the packager which contains all the above-mentioned fixes (except
window size, there is 16Kb, which usually does not affect), but for the packaged file
46KB of memory is allocated, which is the maximum possible
The results are better than the original crunch 2.1, although not enough to catch up
megaLZ. But I am more interested in the packager in terms of packaging new versions of QC,
for which I compiled the latest beta version (QC.C file) and packaged it with
using mehaLZ and QC4.00i. Result: the hrust2!4 algorithm won with 133 bytes. ;)
Everything mentioned in the attached file.
File: Tests.rar http://zx.pk.ru/attachment.php?attachmentid=2231