Как определить количество байтов в итерации арифметического сжатия?

Question

[alex_ak1]

Реализую алгоритм арифметического сжатия.
Пусть есть файл в 1к символов и 20 разных символов. Я считаю статистику и интервалы каждого - и тут уже у меня возникает какое-то сомнение - интервалы слишком узкие, то есть через 3-4 итерации сжатия у меня граница интервала практически не меняются. То есть 4 байта запихать в интервал нормально получается, а дальше - не очень, надо левую часть выводить в файл, обнулять интервал и начинать заново.
Как определить, когда же надо сохранять интервал в файл - через 4 байта, через 5, а может когда-то можно и через 10 байт его сохранять?

Answer 1

[vasiliev]

Следует проверять длину текущего интервала, чтобы она была не менее какого-то значения.

Например, в двоичном MQ-кодере из JPEG2000 гарантируется, что размер интервала от 0.75 до 1.5. Если текущий интервал становится меньше 0.75, то происходит ренормализация: интервал и кодовое слово увеличиваются в 2 раза, а счётчик бит увеличивается на 1 итеративно до тех пор, пока интервал не станет больше 0.75. Когда счётчик бит становится больше чем 8+{несколько дополнительных бит}, считается что старшие биты кодового слова "устаканились" и их можно выдать в выходной поток. Тем не менее, иногда возникают ситуации, когда оставшееся слово переполняется и требуется увеличить на 1 уже выданные в выходной поток байты, это тоже надо учесть. Потенциально может потребоваться изменить все предыдущие байты; в MQ-кодере этот момент обходят за счёт процедуры бит-стаффинга.

Неплохо арифметические кодеры с практической точки зрения расписаны у Amir Said, у него же есть неплохая референсная реализация.

Comments

[alex_ak1]

Ничего не понял :)
Пошел читать ваши статьи :) Спасибо за ответ