python - 处理自适应算术编码中的下溢

Question

我一直在 python 中实现 PPM 压缩算法，并且在使用自适应算术编码器处理下溢时遇到了一些困难（在为有限精度实现维护整数 L 和 H 时）。

根据研究，解决方案是检测 L = 01xxxx 和 H = 10yyyy 的时间，然后重新缩放以使 L = 0xxxx0 和 H = 1yyyy1。每次发生这种情况时都会保持计数器 cntr 并递增，如果 L 和 H 的 MSB 相等，则输出（正常），如果 MSB 为 1，则输出 cntr 0s，如果 MSB 为 0，则输出 cntr 1s。然后重置为 0 并继续编码。这是我的编码和解码代码。

precision = 32
a = 0
b = 2**precision - 1
cntr = 0

def arithmetic_coder(low_cum_freq, high_cum_freq):
    global a, b, cntr
    old_a = a
    ret = ""
    w = b - a + 1
    a = a + math.floor(w * low_cum_freq)
    b = old_a + math.floor(w * high_cum_freq) - 1
    a_bin = np.binary_repr(a).zfill(precision)
    b_bin = np.binary_repr(b).zfill(precision)
    if a_bin[0] == b_bin[0]:
        ret += a_bin[0]
        if cntr > 0:
            if a_bin[0] == "0":
                ret += '1' * cntr
            else:
                ret += '0' * cntr
            cntr = 0
        a_bin = a_bin[1:] + "0"
        b_bin = b_bin[1:] + "1"
    while a_bin[0] == b_bin[0]:
        ret += a_bin[0]
        a_bin = a_bin[1:] + "0"
        b_bin = b_bin[1:] + "1"
    while a_bin[0] == "0" and a_bin[1] == "1" and b_bin[0] == "1" and b_bin[1] == "0":
        a_bin = a_bin[0] + a_bin[2:] + "0"
        b_bin = b_bin[0] + b_bin[2:] + "1"
        cntr += 1
    a = int(a_bin, 2)
    b = int(b_bin, 2)
    return ret

    precision = 32

和解码器：

a = 0
b = 2**precision - 1
decode_pos = 0

def arithmetic_decoder(frequencies):
    global a, b, decode_pos, cntr
    w = b - a + 1
    old_a = a
    frequencies = [0] + frequencies
    for i in range(1, len(frequencies)):
        frequencies[i] += frequencies[i - 1]
    index = math.floor(((int(enc[decode_pos : decode_pos + precision], 2) - a + 1) * frequencies[-1] - 1) / w)
    char = 0
    for i in range(len(frequencies)):
        if frequencies[i] > index:
            char = i - 1
            break
    a = old_a + math.floor(w*frequencies[char]/frequencies[-1])
    b = old_a + math.floor(w*frequencies[char + 1]/frequencies[-1]) - 1
    a_bin = np.binary_repr(a).zfill(precision)
    b_bin = np.binary_repr(b).zfill(precision)
    while a_bin[0] == b_bin[0]:
        a_bin = a_bin[1:] + "0"
        b_bin = b_bin[1:] + "1"
        decode_pos += 1
    a = int(a_bin, 2)
    b = int(b_bin, 2)
    return char

当我对文本文件进行编码然后解码时，解码器的输出在一定程度上是正确的（下溢校正器首先激活的地方），从那时起它就是乱码。

解码器是否需要更改某些内容，或者我只是不了解算术编码的下溢校正？

谢谢。

标签： pythonmathencodingcompression