面向预存半破坏性介质的最优数据编码算法求解

假设某介质已写入均匀分布的随机数据，写入1位为破坏性操作，写入0位为非破坏性操作（类似打孔卡打孔或熔断电路硬编码1）。现需在该介质上写入新的随机（或已压缩至近似随机）数据，要求无需预知原数据即可无损提取新数据，原数据无需保留。

显然编码效率无法超过原存储容量的~50%，目标是尽可能接近该上限。以下为几种编码方案：

编码A #

用偶数偏移位置的gap编码1位，奇数偏移位置的gap编码0位。

Offset:    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19
Tape:      G  G  H  H  H  H  H  G  H  H  H  G  H  H  H  H  G  H  H  H
           |  |                 |           |              |
New Data:  1  0                 0           0              1

编码B #

用连续两个gap编码1位，用gap后跟hole编码0位。

Offset: 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19
Tape:   H  G  G  H  H  H  H  G  H  H  H  G  G  H  H  H  G  H  G  H
            \/                \/          \/             \/    \/
New Data:   1                 0           1              0     0

上述两种编码平均效率为原容量的25%，但并非最优。

编码C #

核心逻辑：用奇数长度的hole串编码1位，偶数长度的hole串编码0位（如HHG代表0，HG/HHHG代表1）。优化点：若hole串的终止gap后接两个连续gap，则视为0。该编码稳定效率达26.666±0.005%，加窥孔优化可提升至28-30%。

编码优化思路D #

对任意编码E(x)，结合可逆变换T(x)，分别编码E('0' + DATA)与E('1' + T(DATA))，选择效率更高的方案，可小幅提升效率，说明基础编码非最优。

现寻求平均效率最优的无损编码方案，推测最优效率在30-50%之间，希望获取最优编码或相关理论文献。

额外说明：尝试构造最坏效率高于0%的编码失败，但仅关注平均效率。

内容的提问来源于stack exchange，提问作者Dillon Davis