FA-11626 / Compression format semantics / Open access

Burrows-Wheeler inversion ignores the primary row · case 01

Burrows-Wheeler inversion ignores the primary row.

Verified by executionVariant 1 · 6 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The inverse chooses the first sorted rotation regardless of recorded primary index.

VERIFIED REPAIR

Reconstruct the rotation table and select the recorded primary row rather than assuming a sorted endpoint.

Unsuccessful approach: Choosing the last rotation merely switches which primary positions fail.

Case contract

Invert a toy BWT by reconstructing sorted rotations from the last column and selecting the supplied zero-based primary row. Empty last column yields empty text.

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(last, primary):
    rows=['']*len(last)
    for _ in last: rows=sorted(last[i]+rows[i] for i in range(len(last)))
    return rows[0] if rows else ''
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('middle primary',solve('b'+'a'*N,1),'a'*(N-1)+'ba')
check('banana',solve('nnbaaa',3),'banana')
check('first primary',solve('ba',0),'ab')
check('last primary',solve('ba',1),'ba')
check('empty',solve('',0),'')
check('repeated symbol',solve('aaa',2),'aaa')
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
middle primary	`ab`	`ba`	Failed
banana	`abanan`	`banana`	Failed
first primary	`ab`	`ab`	Passed
last primary	`ab`	`ba`	Failed
empty			Passed
repeated symbol	`aaa`	`aaa`	Passed

SHA-256 / 8af7865f43b2b8d8d8fd1f70c899c04f6e72fa64a0196c82266694b20f2d987e

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(last, primary):
    rows=['']*len(last)
    for _ in last: rows=sorted(last[i]+rows[i] for i in range(len(last)))
    return rows[-1] if rows else ''
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('middle primary',solve('b'+'a'*N,1),'a'*(N-1)+'ba')
check('banana',solve('nnbaaa',3),'banana')
check('first primary',solve('ba',0),'ab')
check('last primary',solve('ba',1),'ba')
check('empty',solve('',0),'')
check('repeated symbol',solve('aaa',2),'aaa')
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
middle primary	`ba`	`ba`	Passed
banana	`nanaba`	`banana`	Failed
first primary	`ba`	`ab`	Failed
last primary	`ba`	`ba`	Passed
empty			Passed
repeated symbol	`aaa`	`aaa`	Passed

SHA-256 / 19e18c5e7b0a541a783331086b26e51be198e5bc7a32139d1895f0ce3e0c0dea

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(last, primary):
    rows=['']*len(last)
    for _ in last: rows=sorted(last[i]+rows[i] for i in range(len(last)))
    return rows[primary] if rows else ''
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('middle primary',solve('b'+'a'*N,1),'a'*(N-1)+'ba')
check('banana',solve('nnbaaa',3),'banana')
check('first primary',solve('ba',0),'ab')
check('last primary',solve('ba',1),'ba')
check('empty',solve('',0),'')
check('repeated symbol',solve('aaa',2),'aaa')
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
middle primary	`ba`	`ba`	Passed
banana	`banana`	`banana`	Passed
first primary	`ab`	`ab`	Passed
last primary	`ba`	`ba`	Passed
empty			Passed
repeated symbol	`aaa`	`aaa`	Passed

SHA-256 / f09edfcb044be84009511177c62c650f0da5d2dbce3b44836f0e3ad118785d72

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.618665+00:00.

Case digest / 6466804e1ef4b00ceae5002e06073f372d328332ba278d39a8f734a555371432