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）之内，否则你会遇到各种问题。这些问题包括舍入误差，因为理论上您可能需要无限精度。算法本身将在必要时舍入并执行重新归一化以最大限度地利用位范围。你的问题的答案是 "Yes".

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

QM coding implementation in Python - is 16 bit word obligatory?

python

compression

computer-science

bit-manipulation