Consider the following input data stream in a 4 color (A, B, C, D) system. We will build a table of codes which represent strings of colors. Each time we find a new string, we will give it the next code, and break it into a prefix string and a suffix color. The symbols \ or --- represent the prefix string, and / represents the suffix color. The first 4 entries in the table are the 4 colors with codes 0 thru 3, each of which represents a single color. The next 2 codes (4 and 5) are the clear code and the end of image code. The first available code to represent a string of colors is 6. Each time we find a new code, we will send the prefix for that code to the output data stream.
A B A B A B A B B B A B A B A A C D A C D A D C A B A A A B A B ... \/\/---/-----/\/---/-------/\/ \/ \ /\/---/---/\ /\/-----/---/---/ 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 Code 6 8 10 8 14 16 8 13 7 Prefix
The encoder table is built from input data stream. Always start with the suffix of last code, and keep getting colors until you have a new combination. ─────────┬─────────┬────────┬────────┬─────────┬────────────────────────── Colour │ Code │ Prefix │ Suffix │ String │ Output ─────────┴─────────┼────────┼────────┼─────────┼────────────────────────── A 0 │ │ │ - │ B 1 │ │ │ - │ C 2 │ │ │ - │ D 3 │ │ │ - │ Clear 4 │ │ │ - │ End 5 │ │ │ - │ A \ │ A │ A │ │ First col is a special case. B / \ 6 │ A │ B │ AB │ A A | / 7 │ B │ A │ BA │ B B | │ │ │ │ A / | 8 │ 6 │ A │ ABA │ 6 B | │ │ │ │ A | │ │ │ │ B \ / 9 │ 8 │ B │ ABAB │ 8 B / | 10 │ B │ B │ BB │ B B | │ │ │ │ A | / 11 │ 10 │ A │ BBA │ 10 B | │ │ │ │ A | │ │ │ │ B | │ │ │ │ A / \ 12 │ 9 │ A │ ABABA │ 9 A \ / 13 │ A │ A │ AA │ A C / \ 14 │ A │ C │ AC │ A D \ / 15 │ C │ D │ CD │ C A / | 16 │ D │ A │ DA │ D C | │ │ │ │ D | / 17 │ 14 │ D │ ACD │ 14 A | │ │ │ │ D / \ 18 │ 16 │ D │ DAD │ 16 C \ / 19 │ D │ C │ DC │ D A / | 20 │ C │ A │ CA │ C B | │ │ │ │ A | │ │ │ │ A | / 21 │ 8 │ A │ ABAA │ 8 A | │ │ │ │ B / | 22 │ 13 │ B │ AAB │ 13 A | │ │ │ │ B / 23 │ 7 │ B │ BAB │ 7 ───────────────────┴────────┴────────┴─────────┴──────────────────────────
The resultant output stream is: A B 6 8 B 10 9 A A C D 14 16 D C 8 .... The GIF encoder starts with a code length of 2+1=3 bits for 4 colours, so when the code reaches 8 we will have to increase the code size to 4 bits. Similarly, when the code gets to 16 we will have to increse the code size to 5 bits, etc. If the code gets to 13 bits, we send a clear code and start over. See GIFENCOD.GIF for a flow diagram of the encoding process. This uses a tree method to search if a new string is already in the table, which is much simpler, faster, and easier to understand than hashing.