Dictionary Compression (LZ)

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 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.