Search tree data structure encoding for textual substitution data compression systems

Claim 1

In a textual substitution data compression system having a compressor and an expander, the improvement in said compressor comprising buffer memory means for serially receiving source symbols and for providing first in/first out storage for a finite number of said source symbols, a portion of said buffer memory means defining a finite length search window; logic means coupled to said buffer memory means for constructing and maintaining a search tree organized data structure which links the source symbols within said search window in accordance with their order of occurrence to produce symbol strings and for tracking displacements of said symbol strings within said search window in accordance with a most recent occurrence criterion; said logic means having a test mode for testing source symbols just prior to their entry into said search window against said data structure to determine whether said search window contains any matching symbols and an extend mode for evaluating the displacement and length of the longest symbol string within said search window which matches any matched symbol and the symbols following it; encoding means coupled to said logic means for encoding matched symbol strings composed of at least a minimum plural number of source symbols as copy codewords specifying the displacement and the length of the matching symbol string and for encoding all other symbols as literal codewords specifying the symbols, thereby enabling said expander to maintain an updated replica of said search tree organized data structure; said minimum number of source symbols varying as a function of a predefined state of said encoding means.