Я пытаюсь внедрить QM-кодирование в образовательных целях. Мой главный ресурс - глава 5.11 из "Справочника по сжатию данных", 5-е издание. Это моя грубая реализация кодировщика:
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. Должен ли я каким-то образом применять переменную длину? Или есть другая проблема в моем коде? Я потратил несколько дней на это, пытаясь понять, что пошло не так...
В любой форме арифметического сжатия (например, QM) необходимо оставаться в пределах максимально допустимых бит (в этом случае 16), иначе у вас возникнут всевозможные проблемы. Эти проблемы включают ошибки округления, потому что в теории вам может понадобиться бесконечная точность. Сам алгоритм округляется, когда это необходимо, и выполняет перенормировку для максимального использования диапазона бит. Ответ на ваш вопрос: "Да".