From Naive to Near-Optimal: An autonomous iterative approach to hybrid string compression

An Autonomous Iterative Approach to Hybrid String Compression

Introduction & Motivation

Compression algorithms are typically designed through careful theoretical analysis, implemented once, and rarely revisited. What happens when instead we treat the algorithm itself as a parameter to be optimized—iteratively measuring, analyzing, and rewriting the implementation in a tight feedback loop?

This paper documents an experiment in autonomous iterative optimization: a system that writes compression code, benchmarks it against a fixed corpus, identifies bottlenecks, generates an improved version, and repeats—stopping only when gains become negligible. The goal was not to compete with mature compressors like zstd or brotli, but to explore how much ground can be covered autonomously from a deliberately poor starting point.

We constrained the problem space for tractability:

• Input domain: ASCII strings, 26–1000 characters
• Test corpus: 12 fixed vectors spanning repeated chars, natural language, DNA sequences, JSON, and log entries
• Evaluation metric: Combined score = 0.7 × avg_ratio + 0.3 × normalized_speed
• Runtime: Node.js v20, single-threaded, 1000-run benchmarks with 100-run warmup

Experimental Methodology

Each iteration follows a four-phase cycle: Analyze → Hypothesize → Implement → Measure. The analysis phase examines per-test breakdowns to identify which input types are underserved. The hypothesis phase proposes a specific algorithmic change. Implementation must preserve correctness (roundtrip fidelity), and measurement uses high-resolution nanosecond timers with JIT warmup.

The test corpus was designed to stress different compression strategies:

Table 1 — Test corpus composition. Each vector targets a different compression primitive.

The Final Encoding Format

The V4+ algorithm uses a single-byte control code to distinguish three operation types. Each control byte uses a 2-bit prefix to identify the operation, with the remaining 6 bits encoding the payload:

Figure 1 — Control byte encoding. Pink bits are fixed discriminators; cyan bits encode variable-length fields.

Evolution Timeline

Each version represents a complete rewrite of the compression logic, informed by per-test analysis of the previous iteration's weaknesses. Below is the full 10-version progression with key decisions and measured outcomes.

Quantitative Results

Figure 2 — Key metrics from the final V8 algorithm compared to V1 baseline.

Table 2 — Complete results across all 10 iterations. V8 achieves the best combined score.

Figure 3 — Score convergence curve. The sharp initial drop (V1→V2) followed by asymptotic flattening is characteristic of greedy optimization.

Key Findings

The per-test breakdown reveals that different test vectors "unlocked" at different iterations:

Table 3 — Per-test improvement breakdown showing which iteration "unlocked" each test vector.

Implementation Deep-Dive

The V8 implementation uses a single-pass architecture that interleaves RLE detection and LZ77 matching:

function compress(input) {
  const n = input.length;
  if (n === 0) return '';

  // Reset pre-allocated structures (zero GC pressure)
  hashTable.fill(-1);
  chainTable.fill(-1);
  let outPos = 0;
  let litStart = 0,
    litCount = 0;

  let i = 0;
  while (i < n) {
    // 1. Check for character run (RLE candidate)
    let runLen = 1;
    while (i + runLen < n && input[i + runLen] === input[i]) runLen++;

    if (runLen >= 3) {
      // Flush pending literals, emit RLE
      flushLiterals();
      emitRLE(input.charCodeAt(i), runLen);
      i += runLen;
      continue;
    }

    // 2. Check hash table for LZ77 match
    if (i + 3 < n) {
      const hash = h3(i);
      let bestLen = 3,
        bestDist = 0;
      let candidate = hashTable[hash];

      while (candidate >= 0 && i - candidate <= 127) {
        const matchLen = countMatch(i, candidate);
        if (matchLen > bestLen) {
          bestLen = matchLen;
          bestDist = i - candidate;
        }
        candidate = chainTable[candidate];
      }

      // Update hash chain
      chainTable[i] = hashTable[hash];
      hashTable[hash] = i;

      if (bestDist > 0) {
        flushLiterals();
        emitBackref(bestDist, bestLen);
        i += bestLen;
        continue;
      }
    }

    // 3. No match — accumulate as literal
    litCount++;
    i++;
  }
  flushLiterals();
  return output.subarray(0, outPos);
}

The hash function uses a 12-bit trigram hash with XOR-shift mixing. Collisions are handled by chaining (up to 12 lookback entries per bucket), providing a good tradeoff between hash quality and computation cost:

function h3(i) {
  return ((input.charCodeAt(i) << 5) ^ (input.charCodeAt(i + 1) << 2) ^ input.charCodeAt(i + 2)) & 0xfff;
}

Convergence Analysis

The optimization exhibits a classic diminishing returns curve. We define the marginal improvement as the percentage change in combined score between consecutive iterations:

Figure 4 — Marginal gains per iteration. After V4, improvements are consistently below 3% with occasional regressions.

The final three iterations (V8→V10) show changes of less than ±1.5%, confirming convergence. The stopping criterion—terminate when the absolute delta falls below 1% for two consecutive iterations—was met at V10.

Lessons for Practitioners

Beyond the compression-specific results, this experiment offers several transferable engineering insights:

1. Measure before optimizing. Without per-test breakdowns, we would never have identified that V2 left english_text and json_like untouched (ratio = 1.0), motivating the LZ77 addition in V3.

2. Regressions are data, not failures. V5 and V7's regressions provided critical negative results—Buffer allocation costs and BPE preprocessing overhead are lessons that cannot be learned from successes alone.

3. Data structure choice matters more than clever algorithms. V4→V8 was the same algorithm. The only difference was Map → Int32Array and Array.push → pre-allocated Uint16Array. Result: 2.7× speedup.

4. Know when to stop. The autonomous loop naturally converged—V8 through V10 varied by less than 0.03%. Further iterations would spend compute without meaningful progress. Recognizing this inflection point is itself a key optimization skill.

5. Hybrid approaches beat pure strategies. Neither pure RLE nor pure LZ77 matched the hybrid. Different data patterns require different tools, and a single-pass algorithm that selects the right tool at each position outperforms any single strategy.

Conclusion & Future Work

We have demonstrated that an autonomous optimization loop, starting from a deliberately naive implementation, can discover a competitive hybrid compression algorithm in 10 iterations. The key architectural decisions—binary control-byte encoding, hash-chain LZ77 matching, pre-allocated typed arrays—emerged naturally from iterative measurement and analysis rather than theoretical design.

The final V8 algorithm compresses a diverse test corpus to 49.5% of original size at 4.80μs per operation, representing an 80.9% improvement in combined score over the baseline. This performance is achieved with a remarkably simple codebase (~80 lines of compression logic) that requires no external dependencies.

Future directions include extending the corpus to larger inputs (10KB–1MB) where BPE and Huffman coding become viable, multi-threaded benchmarking for more stable timing, exploring learned compression (neural network–based tokenizers), and applying the same autonomous optimization framework to other domains—sort algorithms, cache eviction strategies, or database query plans.