How 7-Zip Optimizes LZMA String Searching

This article explores the mechanisms 7-Zip uses to accelerate string searching during dictionary lookup phases in its LZMA and LZMA2 compression algorithms. By combining multi-level hash arrays, binary tree structures, and strict traversal cutoffs, 7-Zip minimizes computational overhead and maximizes compression ratios while scanning large sliding dictionary windows for repeated data patterns.

Multi-Level Hashing

Traditional Lempel-Ziv algorithms check each position in a sliding dictionary to identify repeated byte sequences. 7-Zip accelerates this by avoiding linear scanning entirely. Instead, it utilizes multi-level hash tables that index prefixes of varying lengths—typically 2-byte, 3-byte, and 4-byte sequences (often denoted as Hash2, Hash3, and Hash4).

When analyzing an incoming byte stream, 7-Zip computes hash values for short byte sequences to quickly look up candidate positions. By checking smaller hash tables first, the algorithm can instantly discard candidate locations that do not match even the initial few bytes. This eliminates costly pointer dereferencing and memory reads for non-matching sequences.

Binary Tree Match Finders

For maximum compression efficiency, 7-Zip relies heavily on Binary Tree match finders (such as BT4, the default engine in high-compression modes). Rather than maintaining a simple linked list of match candidates, the algorithm organizes potential matches into a cyclic binary search tree sorted lexicographically by the data that follows the candidate prefix.

During a lookup:

  1. The engine checks the hash table to find the root of the candidate tree.
  2. It traverses down the binary tree, comparing the current input sequence with existing strings.
  3. Because the tree is ordered, each comparison allows the finder to branch left or right, effectively narrowing the search space in logarithmic time rather than linear time.
  4. Concurrently, the tree is dynamically restructured so that the newest position replaces older nodes, maintaining an up-to-date sliding dictionary without requiring complex rebalancing routines.

Cyclic Buffers and Memory Locality

7-Zip manages its search trees using flat, cyclic arrays rather than standard pointer-based tree nodes allocated dynamically on the heap. Node references are stored as simple array indices within contiguous memory blocks. This approach significantly reduces memory fragmentation and maximizes CPU L1/L2 cache locality, allowing the processor to fetch adjacent dictionary pointers rapidly during deep tree traversals.

Heuristic Cutoffs and Early Exits

Exhaustive search within large dictionaries (which can reach several gigabytes) can severely degrade compression speeds. To prevent worst-case latency scenarios on repetitive or pathological data, 7-Zip enforces heuristic cutoffs:

  • Nice Length Parameter: If the algorithm discovers a match that meets or exceeds a predefined threshold (such as 32, 64, or 273 bytes), it terminates the search immediately, accepting the match as optimal.
  • Depth Limits: The match finder caps the maximum number of tree traversals allowed per byte position. Once this cutoff depth is reached, the search halts, ensuring predictable processing throughput even when handling highly repetitive files.