Data compression method and apparatus implemented with limited length character tables and compact string code utilization

Abstract

An LZW compressor implementation architecture utilizes a plurality of limited length character tables corresponding to the respective characters of the alphabet. A string is stored by storing the code associated with the string in the character table corresponding to the extension character of the string at a character table location corresponding to the code of the string prefix. A character table is created when the character corresponding thereto is first encountered in the input. The input data character stream is searched by comparing the input stream to the stored strings to determine longest matches therewith. The codes associated with the longest matched strings are outputted so as to provide an output stream of compressed codes. The respective lengths of the character tables are limited in accordance with the frequency of occurrence of the characters of the alphabet. If a character table is limited in length to a number of strings less than a predetermined threshold, the character table is excluded from creation. The stored strings are updated by inserting extended strings into the character tables, terminating storage into a character table when the table is full. Additionally, an extended string is excluded from storage when the appropriate character table therefor is excluded from creation. The code counter assigning the string codes is not incremented when an extended string is not stored.