FA-11606 / Compression format semantics / Open access
Canonical Huffman codes advance without shifting at length changes · case 01
Canonical Huffman codes advance without shifting at length changes.
ROOT CAUSE
Code assignment increments without shifting when the next code is longer.
VERIFIED REPAIR
Order entries by length then symbol and shift the next available code by the increase in code length.
Unsuccessful approach: Sorting by symbol alone breaks canonical length-first ordering.
Case contract
Given valid nonzero Huffman lengths keyed by symbol, return integer codes assigned by ascending (length,symbol), incrementing then left-shifting when length grows. Empty input returns {}.
Why this case matters
A small offline codec model isolates a compression-specific failure without external files or libraries.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(lengths):
return {s:i for i,(s,n) in enumerate(sorted(lengths.items(),key=lambda p:(p[1],p[0])))}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('length jump',solve({'a':1,'b':N+2}),{'a':0,'b':2**(N+1)})
check('symbol order differs',solve({'a':2,'z':1}),{'z':0,'a':2})
check('tie order',solve({'b':2,'a':2}),{'a':0,'b':1})
check('empty',solve({}),{})
check('single',solve({'x':3}),{'x':0})
check('complete tree',solve({'a':1,'b':2,'c':2}),{'a':0,'b':2,'c':3})
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| length jump | {'a': 0, 'b': 1} | {'a': 0, 'b': 4} | Failed |
| symbol order differs | {'a': 1, 'z': 0} | {'a': 2, 'z': 0} | Failed |
| tie order | {'a': 0, 'b': 1} | {'a': 0, 'b': 1} | Passed |
| empty | {} | {} | Passed |
| single | {'x': 0} | {'x': 0} | Passed |
| complete tree | {'a': 0, 'b': 1, 'c': 2} | {'a': 0, 'b': 2, 'c': 3} | Failed |
SHA-256 / 61d8471d457ceb17f1d310a3e3936bcfc93ae3da35191e7b404259b0231dee42
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(lengths):
out={}; code=0; previous=0
for s,n in sorted(lengths.items()):
code = (code << max(0,n-previous))
out[s]=code; code+=1; previous=n
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('length jump',solve({'a':1,'b':N+2}),{'a':0,'b':2**(N+1)})
check('symbol order differs',solve({'a':2,'z':1}),{'z':0,'a':2})
check('tie order',solve({'b':2,'a':2}),{'a':0,'b':1})
check('empty',solve({}),{})
check('single',solve({'x':3}),{'x':0})
check('complete tree',solve({'a':1,'b':2,'c':2}),{'a':0,'b':2,'c':3})
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| length jump | {'a': 0, 'b': 4} | {'a': 0, 'b': 4} | Passed |
| symbol order differs | {'a': 0, 'z': 1} | {'a': 2, 'z': 0} | Failed |
| tie order | {'a': 0, 'b': 1} | {'a': 0, 'b': 1} | Passed |
| empty | {} | {} | Passed |
| single | {'x': 0} | {'x': 0} | Passed |
| complete tree | {'a': 0, 'b': 2, 'c': 3} | {'a': 0, 'b': 2, 'c': 3} | Passed |
SHA-256 / 92a2d65550848dcbcb34088e60e9dcd80b0f3be321a1dd551d8049699c6e79fa
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(lengths):
out={}; code=0; previous=0
for s,n in sorted(lengths.items(),key=lambda p:(p[1],p[0])):
code <<= n-previous
out[s]=code; code+=1; previous=n
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('length jump',solve({'a':1,'b':N+2}),{'a':0,'b':2**(N+1)})
check('symbol order differs',solve({'a':2,'z':1}),{'z':0,'a':2})
check('tie order',solve({'b':2,'a':2}),{'a':0,'b':1})
check('empty',solve({}),{})
check('single',solve({'x':3}),{'x':0})
check('complete tree',solve({'a':1,'b':2,'c':2}),{'a':0,'b':2,'c':3})
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| length jump | {'a': 0, 'b': 4} | {'a': 0, 'b': 4} | Passed |
| symbol order differs | {'a': 2, 'z': 0} | {'a': 2, 'z': 0} | Passed |
| tie order | {'a': 0, 'b': 1} | {'a': 0, 'b': 1} | Passed |
| empty | {} | {} | Passed |
| single | {'x': 0} | {'x': 0} | Passed |
| complete tree | {'a': 0, 'b': 2, 'c': 3} | {'a': 0, 'b': 2, 'c': 3} | Passed |
SHA-256 / f9f189b27106e5a4af57398b878340ff34eb359a07be53213b5010982cda215e
Verification & scope
Controlled educational model, not a complete implementation of a production compression format. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.
Observations recorded using Python 3.12.14 at 2026-09-29T14:38:49.332236+00:00.
Case digest / 510ab691e4db750c65e14be8c62cd78f06859ddc9fb321e26db767eaac662b24