Дальномерное кодирование без двусмысленного или незаконного выхода

Question

В кодировщике диапазона с использованием арифметики с конечной точностью могут быть случаи, когда невозможно кодировать следующий символ без предварительного применения какого-либо флеша или настройки, чтобы открыть пространство в рабочие регистры.

Следствием этого является то, что в зависимости от того, как все изменилось, в наборе законных битовых потоков может быть оставлен небольшой промежуток.

Например, Wikipedia page предлагает сузить диапазон выходного сигнала до того, что позволяет вывести больше битов, оставив некоторую часть исходного диапазона неопределенной.

В декодере можно прийти к той же точке, а затем обнаружить, что входной поток битов сам по себе не соответствует настройке энкодера, а вместо этого переходит в зазор, который должен был быть отброшен кодером. Нет правильного декодирования такого битового потока.

Контрастируйте это с чем-то вроде Хаффмана, который обычно определяется без какой-либо неоднозначной конфигурации ввода (за исключением конца потока, где может быть неполный символ). Таким образом, можно декодировать произвольный бит-поток в сообщение, которое затем может быть перекодировано в исходный поток битов.

Мой вопрос заключается в следующем: возможно ли сформулировать какую-то настройку, которая касается пределов точности, но не создает возможности недоказуемого или неоднозначного битового потока? Такой, что при произвольном битовом потоке всегда можно декодировать его до некоторого набора символов, который может быть повторно закодирован обратно в исходный бит-поток?

Интуитивно кажется, что это должно быть невозможно, и я не должен биться головой об этой проблеме; но я смотрю на Хаффмана и рассуждает, что у него есть свойство, которое я смогу смоделировать.

Answer 1

И в процессе написания вопроса, я считаю, что, возможно, нашел решение; но я пока не уверен. Я оставлю это здесь, и кто-то (возможно, я сам) в конце концов скажу, почему я ошибаюсь, или это будет правильно и потенциально полезно для других ...

Когда вы дойдете до точки, что диапазон выход слишком мал для следующего символа, подразумевается, что этот диапазон охватывает величину, которая является большой мощностью двух, и именно та точка, в которой нижняя и верхняя границы заканчиваются, отличаются друг от друга самым значительным битом.

Итак, возьмите таблицу частот символов и разделите ее примерно на то же место, что и граница POT в вашем диапазоне. Затем установите либо верхнюю, либо нижнюю границу для POT в зависимости от того, является ли символ первой или второй секцией; затем очистить вновь выпущенные биты и закодировать раздел, как если бы он был полным символом и продолжался.

Возможно, существует функционально эквивалентный способ сделать это, что является менее длинным.