First, I apologize: Yesterday, I wrote a sudden turning light, so that this article wrote 80% had to fly to the smoke, my poor computer is also bare, there is no way, school regulations, so I have to start today. Write again. The words retired. Before writing articles, our county assumes that you have been very clear about what GIF. If you are not clear, I suggest you search online to find a "GIF file profile". GIF as a network-oriented image format, all of his design is "easy to use online" as principles. The first principle of online use is the file size. How to use a valid compression algorithm to reduce the size of the file, is the primary issue to be solved by the GIF file. For this problem, GIF uses a LZW compression algorithm that compresses a good compression efficiency. The compression efficiency of this algorithm is extremely high, but there is a little bad: it is copyrighted. So my first part is to introduce the LZW algorithm, independent of the content of the GIF file format, just an algorithm, but it is the basis of the LZW-GIF compression algorithm (the compression algorithm used by GIF). 1. Overview of the basic idea of the LZW algorithm is very simple: in an uncompressed byte stream, there must be many repeated strings, then use one byte to represent this string, not to compress Is there a role? Let's take a few concepts first, these concepts will appear repeatedly in the introduction below, so please remember them. Char stream (uncoded byte stream): As an encoded input and decoding output, the uncompressed byte stream, the object we have to handle. Code Stream: I have not written bytes, because it is not necessarily bytes, in fact, most of them are not bytes. String Table: As a dictionary encoding and decoding, its format is an index corresponding to a string, in initialization, INDEX starting from 0 in turn corresponds to the corresponding character in the character set. There is a big advantage of the LZW's coding table that he doesn't need a lot of storage, it is dynamically generated in the process of encoding, decoding, and generating him refers to a variable: the number of initial roots. Root item: Generate only one character of only one character when generating the coded table, and they have a series of features, I will detail when the algorithm is described. Ok, the concept is finished.
Now introduce the encoded algorithm: 2, the encoding algorithm is first is the pseudo code description of the algorithm: INITIAL_STRING_TABLE (ROOT_NUMBER); current_prefix = ''; // empty string While (able to take a char C in Char Stream) {current_string = current_prefix c; if (current_string present in string_table in) {current_prefix = current_string;} else {the current_string added to the end string_table; an output current_prefix corresponding in string_table the index to the Code Stream in; current_prefix = c;}} to Code Stream in Output current_prefix Corresponds to index in string_table; // Now let's see how each step is made: Step 1: Initialize our coding table. Just said, the initialization coding table only needs a parameter: root_number, that is, the number of roots. In fact, he is the number of character sets in the char stream we have to encode. Initialization is also very simple: sort all of the char in accordance with a prior agreement, then encapsulate it from zero to the zero to form an item, and then these Items from smaller to large, the initial coding table is formed. Step 2: Initialize some local variables: mainly current_prefix and current_string, set them to an empty string. Step 3: Start cyclic encoding, the method is as follows: A Char C is read from the Char Stream and then connects it to the back of Current_PREFIX to form current_string. Look in string_table, see if there is this current_string.
Yes: This current_string is "old", so don't do anything, just assign current_string to current_prefix; None: Description This current_string is "new", so the first step turns it into "old", that is Plug it into the end of string_table; then output current_prefix Index to Code Stream in String_Table in String_Table; finally restarts the repetitive string, that is, the Current_prefix is assigned. This ends, and finally, there is still a prefix, and output it. For example. Suppose our code stream is BBBCBBA, the character set is {A, B, C}, and we agree that the arrangement is ASCII ascending. The initialized string_table is as follows: ----------------------- index string00 'a'01' b'02 'c' --------- ------------ These three are called Root items. Then start encoding: During the simple period, I just list the value of each amount and make a brief description.
