PKZIP - compression algorithms

Hello everyone! These are the algorithms that are used in PKZIP. I also use PKZIP Shannon-Fano codes, but I don’t have such a description, in the description of the PKZIP format Everything is presented quite clearly in English with examples. Two-stage coding. Lempel-Ziv algorithm ===================================================== A much greater degree of compression can be achieved by extracting from the input stream repeating chains - blocks, and encoding links to these chains with building hash tables from the first to the nth level. The method that will be discussed belongs to Lempel and Ziv and is usually called LZ-compression. Its essence is as follows: the packer constantly stores a certain amount last processed characters in the buffer. As the input stream is processed newly arrived characters end up at the end of the buffer, shifting the previous ones characters and displacing the oldest ones. The dimensions of this buffer, also called a sliding dictionary dictionary), vary among different implementations of encoding systems. It has been experimentally established that the LHarc program uses The buffer is 4 KB, LHA and PKZIP are 8, and ARJ is 16 KB. Then, after constructing the hash tables, the algorithm selects (by searching in the dictionary) the longest initial substring of the input stream that matches one of substrings in the dictionary, and outputs a pair (length, distance), where length isthe length of the substring found in the dictionary, and distance is the distance from it to the input substrings (that is, actually the index of the substring in the buffer, subtracted from its size). If such a substring is not found, it is simply copied to the output stream the next symbol of the input stream. In the initial version of the algorithm it was proposed to use the simplest search by to all the dictionaries. However, later it was proposed to use binary tree and hashing for fast dictionary lookup, which allowed an order of magnitude increase the speed of the algorithm. Thus, the Lempel-Ziv algorithm converts one stream of source symbols into two parallel streams of lengths and indexes in the table (length + distance). Obviously, these streams are character streams with two new alphabets, and one of the methods mentioned above can be applied to them (RLE, encoding Huffman or arithmetic coding). So we come to a two-stage coding scheme - the most effective of practically used at present. When implementing this method It is necessary to achieve consistent output of both streams into one file. This The problem is usually solved by alternately writing character codes from both streams. Example: First stage - abcabcabcabcabc - 1 a 1 b 1 c 3 3 6 3 9 3 12 3 The second stage is the exclusion of a large group of repeating sequences 1a 1 b 1 c 12 3 and RLE compression, Huffman coding, arithmetic coding. Huffman algorithm ================= When compressing a file using the Huffman algorithm, the first thing we must do is necessary read the file completely and count how many times each character appears from extended ASCII set. If we take into account all 256 characters, then there will be no difference in compression for us text and EXE file. After calculating the frequency of occurrence of each symbol, you need to look table of ASCII codes and form a binary tree. Example: We have a file that is 100 bytes long and has 6 different characters in it. We We counted the occurrence of each character in the file and got the following: A - 10 B - 20 C - 30 D - 5 E - 25 F - 10 Now we take these numbers and call them the frequency of occurrence for each symbol. We will take 2 symbols with the lowest frequency from the last table. In our case this is D (5) and any symbol from F or A (10), you can take any of them for example A. Let us form a new “node” from “nodes” D and A, the occurrence frequency for which will be equal to the sum of frequencies D and A Now we are again looking for the two symbols with the lowest occurrence frequencies. Excluding from viewing D and A and considering instead a new “node” with the total frequency occurrences. The lowest frequency is now y F and the new "node". Let's do it again node merging operation.Consider the table again for the next two characters (B and E). We We continue in this mode until the entire “tree” is formed, i.e. not yet will be reduced to one node. Now that our tree is created, we can encode the . We must always start from the root (Root). Coding the first character (leaf of tree C) We trace up the tree all the branches turn and if we make a left turn, then remember the 0th bit, and similarly the 1st bit for a right turn. So for C, we We will go left to 55 (and remember 0), then left again (0) to the symbol itself. The Huffman code for our symbol C is 00. For the next symbol (A) we have it turns out - left, right, left, left, which results in the sequence 0100. Carrying out the above for all symbols we get C = 00 (2 bits) A = 0100 (4 bits) D = 0101 (4 bits) F = 011 (3 bits) B = 10 (2 bits) E = 11 (2 bits) When encoding, we replace characters with sequence data. Stanislav

||*()*|| Hello, _/Stanislav/_! August 28, 2002 23:54, Stanislav Yudin wrote to All: SY> These are the algorithms that are used in PKZIP. More in PKZIP SY> I use Shannon-Fano codes, but I don’t have such a description, in SY> description of the PKZIP format is quite clear, everything is presented in English SY> language with examples. Separately, I did both LZ and Huffman on Spec. The latter has one problem - you also need to save a frequency table (or tree), which can sometimes take up larger than the file itself. But I haven't tried combining... All the best! /*Boh*/ / /Image Crew/ was with you. ||*()*||

Press RESET immediately, Aleksey! 29 Aug 02 12:59, Aleksey Senilov wrote to Stanislav Yudin: AS> Separately, I did both LZ and Huffman on Speck. The latter has one AS> problem - you need to save the frequency table (or tree), which AS> can sometimes take up more than the file itself. You can apply an algorithm that has some initially known table, which in the encoder (and decoder) adapts to the input flow.

Hello, Aleksey Somehow Thursday August 29, 2002 at 12:59:09 a conflict occurred Aleksey Senilov and Stanislav Yudin argued on the topic of PKZIP - compression algorithms I decided to add some heat to this dialogue. AS> Separately, I did both LZ and Huffman on Speck. U AS> the latter has one problem - it is necessary to save the frequency table AS> (or tree), which can sometimes take up more than itself AS> file. PKZIP on Spec is necessary primarily for compatibility, although, for example, TRD It will be okay for them to pack. AS> But I haven’t tried combining... Maybe it's worth a try? Best regards, Stanislav Yudin.

Hi, Alexey! August 29, 2002 12:59, Aleksey Senilov wrote to Stanislav Yudin: AS> Separately, I did both LZ and Huffman on Speck. The latter has one AS> problem - you need to save the frequency table (or tree), which sometimes AS> may take up more than the file itself. By the way, in ZX-Review 4-5'97 (Forum section) there is a Huffman method with a sign of only 32 byte. In addition, there are not 256 codes, but 256+32=288, that is, 32 more codes are possible use it somehow. For example, designate with them 32 frequently repeated strings (here's a lot of LZ for you). Maybe someday, based on this idea, I will I will create... AS> * Origin: Who am I? (FZ/SL) (500:8332/1) GOD :))) Bye Alexey...

||*()*|| Hello, _/Kirill/_! August 30, 2002 01:50, Kirill Frolov wrote to Aleksey Senilov: AS>> Separately, I did both LZ and Huffman on Speck. The last one AS>> one problem - you need to save the frequency table (or tree), AS>> which can sometimes take up more than the file itself. KF> You can apply an algorithm that has some initially known KF> table, which in the encoder (and decoder) adapts to KF> input stream. It's possible. But then I didn’t go into such details, but was only satisfied implementation of the algorithm. I had no intention of writing a packer :) All the best! /*Boh*/ / /Image Crew/ was with you. ||*()*||

||*()*|| Hello, _/Stanislav/_! August 31, 2002 20:46, Stanislav Yudin wrote to Aleksey Senilov: AS>> Separately, I did both LZ and Huffman on Speck. U AS>> the latter has one problem - it is necessary to save the frequency table AS>> (or tree), which can sometimes take up more than itself AS>> file. SY> PKZIP on Spec is necessary primarily for compatibility, although SY> for example, TRD will be fine to pack. I don’t argue, but with proper implementation, it may well become “main” archiver, along with zxzip and hrip... AS>> But I haven’t tried combining... SY> Maybe it's worth a try? Are you offering me, or is it a question of whether you should? If you want, do it... I would supported. All the best! /*Boh*/ / /Image Crew/ was with you. ||*()*||

Hello Aleksey! 01 Sep 02 19:00, Aleksey Senilov -> Stanislav Yudin: AS>>> But I haven’t tried to combine... SY>> Maybe it’s worth a try? AS> Are you offering me, or is it a question of whether you should? If you want, do it... I AS> b supported. My phrase should have been interpreted as “Maybe you should try?” I have everything stalled at the stage of searching for the required algorithm :( Stanislav

||*()*|| Hello, _/Stanislav/_! 03 September 2002 22:40, Stanislav Yudin wrote to Aleksey Senilov: AS>> Are you offering me, or is it a question of whether you should? Do you want AS>> do it... I would support it. SY> My phrase should have been interpreted as “Or maybe you should try?” U SY> I was completely stuck at the stage of searching for the required algorithm :( Firstly, those sources of mine got lost somewhere. Secondly, are you talking about the pkzip algorithm itself, or individual compression methods? Can you make the same LZ or Huffman separately? All the best! /*Boh*/ / /Image Crew/ was with you. ||*()*||