Data compression

Abstract

Methodology and concomitant circuitry for compacting an incoming data stream into an outgoing compacted data stream utilize a multiple, doubly-linked list and an associated class promotion data structure. The incoming data stream is partitioned into a sequence of symbols. A memory associated with the data structure stores each symbol, information regarding the recency rank of each symbol as it arrives in sequence as well as class information and pointer information for each symbol. For each symbol, the memory is checked to determine if the symbol is new or repeated. If the symbol is repeated, only the recency rank is used to form that part of the outgoing data stream associated with the new symbol. If the symbol is new, identification information is added to the symbol and both the identification information are emitted as part of the compacted stream. Memory update operations are then effected to change class, recency rank and pointer information. The decoding methodology and circuitry performs the inverse to the compacting operations using the class promotion data structure.