Dictionary Compression (LZ)

LZ77, published by Abraham Lempel and Jacob Ziv in 1977, is the foundational algorithm. It uses a sliding window divided into two parts:

• Search Buffer: Contains recently encoded data (the dictionary).
• Look-Ahead Buffer: Contains data yet to be encoded.

The encoder searches for the longest match of the look-ahead buffer's prefix within the search buffer. It outputs a token consisting of:

• Offset: Distance back to the start of the match.
• Length: Length of the matching sequence.
• Next Symbol: The first non-matching symbol after the match. This scheme is inherently adaptive, as the sliding window continuously updates, making it effective for streaming data. The DEFLATE algorithm (used in gzip and PNG) combines LZ77 with Huffman coding.

LZ78, published in 1978, differs fundamentally by building an explicit dictionary of previously encountered phrases (substrings).

• The dictionary starts empty.
• The encoder parses the input into phrases where each phrase is the longest dictionary match plus one new character.
• It outputs a token: (dictionary index, new character).
• The new phrase (match + new character) is then added to the dictionary. Unlike LZ77's sliding window, the LZ78 dictionary grows until a size limit is reached, potentially capturing longer-term repetitions. Its need to transmit the new character with every token can be less efficient on highly repetitive data compared to LZ77.

LZW, a practical refinement of LZ78 by Terry Welch, is one of the most widely implemented algorithms (GIF, TIFF, Unix compress). Key modifications:

• The dictionary is pre-initialized with all possible single-character strings (e.g., 256 entries for 8-bit data).
• Output tokens are only dictionary indices; the 'new character' is implied as the first character of the next phrase.
• The decoder builds the dictionary synchronously, avoiding the need to transmit the dictionary. Process: The encoder finds the longest string W in the dictionary, outputs its index, and adds W + next character to the dictionary. Its simplicity and decent compression ratio led to widespread adoption in early file formats.

LZSS, introduced by Storer and Szymanski in 1982, is an efficient improvement over LZ77 that resolves a key inefficiency.

• In LZ77, every token includes a 'next symbol', even for long matches.
• LZSS uses a flag bit (or byte) to distinguish between two output types:
  1. A match token: (Offset, Length) for sequences longer than a threshold.
  2. A literal character: The raw symbol itself, for no suitable match. This eliminates the overhead of the 'next symbol' for matches, significantly improving compression on moderately redundant data. It is the core algorithm in formats like ZIP (via DEFLATE) and RAR.

LZMA, used in the 7z format, represents a modern, high-compression variant. It combines an advanced LZ77-style sliding window match finder with a range coder (an efficient form of arithmetic coding) for entropy coding. Key Features:

• Uses a large sliding window (up to gigabytes) to find long-distance matches.
• Employs complex hash chains or binary trees for fast match searching.
• The output from the LZ77 stage (literal/match decisions, offsets, lengths) is then encoded using a context-based range coder, which adapts probability models based on recent data types (e.g., literal vs. match state, position within a word). This two-stage process—dictionary compression followed by sophisticated statistical compression—achieves very high ratios, especially on text and executable code.

The performance of LZ variants hinges on dictionary management strategies, which involve core trade-offs:

• Sliding Window (LZ77/LZSS/LZMA):
  • Pros: Continuously adaptive, excellent for local repetition and streaming.
  • Cons: Cannot capture repetitions beyond the window size; search complexity increases with window size.
• Growing Dictionary (LZ78/LZW):
  • Pros: Can capture very long-term, global repetitions.
  • Cons: Dictionary size grows unbounded, requiring reset or pruning; less efficient on data with only short-range redundancy.
• Match Finding: Algorithms use hash tables, suffix trees, or hash chains to accelerate the search for the longest match, which is the most computationally intensive step in LZ77-style encoding. The choice of variant involves balancing compression ratio, speed, memory usage, and suitability for the data's redundancy structure.

A technique that stores only the changes (deltas) between sequential states or document versions. This is highly effective for compressing memory streams where states evolve incrementally, such as an agent's internal monologue or a changing world model.

• Encodes differences rather than full snapshots.
• Minimizes storage for incremental updates in experience replay buffers or versioned knowledge.
• Underpins efficient state synchronization in multi-agent systems.

A data format where most elements are zero, enabling massive storage and computational savings. This is a core principle in model compression (e.g., pruned networks) and efficient data structures for agent memory.

• Enables specialized algorithms (e.g., sparse matrix multiplication) that skip zero operations.
• Bloom filters are a sparse, probabilistic data structure for fast set membership queries in memory caches.
• Graph compression often relies on sparse adjacency matrices.

A direct memory compression technique for language model agents, where a long conversation history or document context is condensed into a shorter, coherent summary. This manages the finite context window of transformer models.

• Lossy compression that aims to preserve semantic meaning and key facts.
• Can be performed by a dedicated summarization model or the agent itself through reflection.
• Essential for long-horizon task execution where the full history cannot be retained.

Techniques to reduce the size and dimensionality of dense vector embeddings, which are the core of semantic memory in agents. This optimizes the storage and retrieval speed from vector databases.

• Quantization (e.g., to 8-bit integers) reduces the precision of embedding values.
• Dimensionality reduction (e.g., PCA) projects high-dimensional vectors into a lower-dimensional space.
• Product quantization splits vectors into subvectors for more efficient approximate nearest neighbor search.