Methodology and concomitant circuitry for compacting an incoming data stream into an outgoing compacted data stream utilize a plurality of memories or lists. The incoming data stream is partitioned into a sequence of tokens. A primary memory (3262) stores each token, with the most recently appearing token occupying the top rank in the list. A secondary memory (3282) stores the location in the primary memory of each of a subset of tokens. The compacted data stream is generated as a coded representation of the token itself, the position of the token in the primary memory, or the position in secondary memory of the location of the token in primary memory. A tertiary list may also be employed to generate a coded representation of the position in the tertiary list of the secondary list. Searching of the lists is effected with a hashing function. Updating of the lists utilizes tree splaying.
