Python 中的 QM 编码实现 - 是强制性的 16 位字

Question

我正在尝试出于教育目的实现QM编码。我的主要资源是《数据压缩手册》第 5 版中的第 5.11 章。这是我目前对编码器的粗略实现：

def _encode_bit(self, bit):
    if bit == self._lps:
        self._code_lps()
    else:
        self._code_mps()
def _code_mps(self):
    self._a = self._a - self._q_e()
    if self._a < 0x8000:
        self._switch_intervals_if_needed()
        self._renormalize()
        self._p_table.next_mps()
def _code_lps(self):
    self._c = self._c + self._a - self._q_e()
    self._a = self._q_e()
    self._switch_intervals_if_needed()
    self._renormalize()
    self._p_table.next_lps()
def _renormalize(self):
    while self._a < 0x8000:
        #C < 0,5 (0xFFFF / 3)
        if self._c < 0x5555:
            b = 0
            d = 0
        else:
            b = 1
            d = 0x5555
        self._write_bit(b)
        logger.debug("Written '%i' to output", b)
        #C = 2 * (C - D)
        self._c = (self._c - d) << 1
        #A = 2 * A
        self._a <<= 1

我

正在将间隔映射到整数，因为据我所知，它应该更有效。在书中，提到了 16 位字用于映射，但由于我在 Python 中执行此操作，我不确定是否不强制执行所有变量的 16 位长度。问题是，当我运行编码器时，如果我正确理解它，C(self._c在代码中(应该指向 MPS 间隔的底部，它很快就会溢出超过 16 位长度，并且它的值变得非常大。因此，编码位大多只是一串LPS符号。我应该以某种方式强制执行可变长度吗？还是我的代码中有其他问题？我已经花了几天时间试图弄清楚出了什么问题......

Answer 1

在任何形式的算术压缩(如 QM(中，都需要保持在允许的最大位数(本例中为 16(内，否则会遇到各种问题。 这些问题包括舍入误差，因为理论上您可能需要无限的精度。 算法本身将在必要时四舍五入，并执行重整化以最大限度地利用位范围。 您的问题的答案是"是"。