Hafman

─────────────────────────────── ──────────────────────────────── * Forwarded by Oleg Grigoriev (500:812/5.2) * Area: RU.ALGORITHMS * From : Maxim Lopatkin, 2:5054/34.28 (12 Mar 99, 22:12:20) * To : Artem Igorevich * Subj: Hafman ─────────────────────────────── ──────────────────────────────── Hello Artem!!! [it was echoed, I tweaked it a bit] Huffman. First of all, let's define what causes compression. Compression occurs by encoding more frequently repeated characters in the file with shorter codes. Example: AAABCCD - 7 Byte A - '0' C - '10' D - '110' B - '111' We get: AAABCCD = '0001111010110' = 1 byte and 5 bits. Further explanations. It is not difficult to see that a prerequisite is uniqueness of binary codes, cat. achieved through a Huffman tree. Coding. 1. Statistics Read the file you want to archive while counting number of characters. That is, you create a table in which each ASCII code matches the number of this character in the file, Example. So, let us have a 5 letter alphabet. ABCDE And the following file is zipped: AABCABDCAB The table will look like: A - 4 B - 3 C - 2 D - 1 E - 0 2. Formation of Huffman codes.This is perhaps the most important stage of the method. Binary codes are formed here Huffman. A Huffman tree is used for this. Again, using our example (for convenience, I put all our symbols in order increasing the frequency of delivery) A bit is assigned to the side, the x-th of this arc. E 0──1──┐ ├─0+1=1──1─┐ │ │ D 1──0──┘ ├──1+2=3───1──┐ │ │ │ │ C 2──────────────0─┘ ├────3+3=6───1──┐ │ │ │ │ B 3────────────────────────────0─┘ ├───6+4=10──root │ │ A 4──0──────────────────── ───────────────────────┘ In fact, we do the following - we find two codes with a minimum occurrence to a file, then we combine them into a vertex, which will have a hit frequency is equal to the sum of the frequencies of these two selected vertices. The resulting peak is again participates in the search at the next step, and the two from which this one was obtained top - do not participate. bits 1, 0 are arranged as follows - arc with the first minimum is assigned '1' (as in the figure), the arc with the second - '0' or vice versa. The main thing is that from one vertex there should not be two identically markedarcs. Case or ──0────┐ ────1───┐ │ │ are unacceptable. ──0────┘ ────1───┘ That is step1 step2 step3 step4 step5 A - 4 A - 4 A - 4 A - 4 ABCDE=10 B - 3 B - 3 B - 3 min BCDE=6 C - 2 C - 2 min CDE - DE+C = 3 min D - 1 min DE = D+E=1 min E - 0 min So, now there is a tree, let's create conversion codes. (and turn attention - this tree construction ensures that rarer codes a shorter sequence of bits will be assigned.) So... A - '0' B - '10' C - '110' D - '1110' E - '1111' Now let's do our coding. A A B C A B D C A B AABCABDCAB - 0 0 10 110 0 10 1110 110 0 10 10 Byte 00101100 10111011 0010 2 bytes 4 bits. It was 10 Bytes - now 2 Bytes 4 bits. So much for compression. !! you need to store the frequency table in the file that you archive. Unzipping is obvious. You read, then you transcode according to _TREE, It is easy to see that going from the root, along the branches, you will reach the leaf, which is your symbol. > Best regards, MAX.-+- GoldED 2.50.Beta4+ + Origin: The further into the forest, the more odd you are. (2:5054/34.28) ─────────────────[ end of forwarded message ]────────────────── WBR, Oleg.