Inferno #06 03 декабря 2004

Программирование

Softinka - the benefits of packing algorithm Optimal LZH.

>> Igor Pavlov has a project 7-zip, it at the conference, I
>> Learned about the algorithm optimal lzh - when you select
>> Really the best way to matching rows in the already
>> There are tree codes of lengths and distances.
DB> hachu this algorithm.
Take this!
This algorithm is really needed for each packer on the 
Spectrum. I had to implement it for all Hrum, crunches and 
lazerkompaktov three or four years ago. Ayyayyay in general. 
For "tightly" wired codes, as is done in most of the packers at 
Speke, the algorithm will bring about, I'm afraid to say 2-20%. 
On packer type RIP to about 1-10%. This is a snapshot. Of 
course, much to the memory on the package, will seriously 
hamper, but there are various options - On pieces of a length 
split the file and prochee.Da least on the PC can packing.


-------- ------- Hrum Igor Pavlov wrote in RU.COMPRESS in 1999.

Algorithm for optimal Lempel-Ziv-Huffman coding
-------------------------------------------------- -
1)
Search for matches in the dictionary is carried out for each 
shift. When looking for further collect information on the best 
(according to distance) match with lengths from 2 to maximum 
length match.


Offsets [] = Get_Longest_And_Other_Good_Matches ();

/ / Offsets.Size = length of longest match.
/ / Offsets [i] = back offset in dictionary for match with len 
= i. 

BYTE Get_Current_Literal ();
/ / Returns current byte

2)
We can always count how many bits will presumably
any option (match / literal) on the basis of information about 
previous huffman blocks:


int Get_Match_Huffman_Price (int Length, int Offset);

/ / Length = length of match
/ / Offset = offset of match;
/ / Result = number of bits for coding this match;

int Get_Literal_Huffman_Price (BYTE Literal);
/ / Result = number of bits for coding this Literal;

3)
We construct the optimal sequence of codes, many moves
forward.

There is a large array a []:
a [i] =
 {

   int Price; / / The price path in bits to get to the i-th 
byte. 

   struct

   {

     int Prev; / / position where we jump into the current (= 
i) position 

               / / For Literal: Prev = i - 1

              / / For Match'a with length Length: Prev = i - 
Length 



     int Offset; / / Offset. in buffer (dictionary) ago in the 
case Match'a 

                 / / Write Match'a Prev by up to i

  }
}

a)
For all elements of a [] set Price = infinity.

b)
for (int i = 0; i > In general, my attitude see above, but here there is another
>> Interesting thing - just support for LZMA decompressing
>> Spectrum. However, I think, would be inconvenient to use
>> LZMA unpacker for programs at the Spectrum.
DB> But you can apply for magazines or large directories.
DB> For example, Open Letters on one disc;)

>> PS. Re-read your letter and realized that the source you
>> Sent ...
DB> There's no pint not vedesh - 1021 file, 3.4 megabytes
DB> source. Recycle Bin.
Well, half a liter is not a problem:). There's a pint and not 
vedesh. You have not tried to study just a decoder, the one in 
the file SRC7zipCompressLZMA_Clzmadecode.c, there is only 23 
kb:).