Повышение производительности реализации арифметического кодирования

Я работаю над оптимизацией реализации арифметического сжатия. Я включил базовый алгоритм арифметического кодирования ниже:

lower bound = 0
upper bound = 1

while there are still symbols to encode
  current range = upper bound - lower bound
  upper bound = lower bound + (current range × upper bound of new symbol)
  lower bound = lower bound + (current range × lower bound of new symbol)
end while

У меня есть идея округлить мои значения, но для этого расчет верхней границы НЕ МОЖЕТ использовать значение нижней границы. Я не могу понять, как это сделать.

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

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


person John McBrown    schedule 20.03.2013    source источник
comment
Вы намеренно исключаете операцию сдвига/масштабирования из своего псевдокода или планируете хранить все свои данные в памяти до тех пор, пока не завершится сжатие? Я думаю, что тип округления, который вам нужен, зависит от деталей того, как вы справляетесь с этим...   -  person comingstorm    schedule 21.03.2013
comment
Я только что прочитал о смещении битов. Но я использую BigDecimals в своей реализации Java, и мне трудно работать только с наиболее значимыми битами. Знаете ли вы, как я могу сделать это на Java с помощью BigDecimals?   -  person John McBrown    schedule 22.03.2013
comment
Вместо этого я рекомендую использовать long.   -  person comingstorm    schedule 22.03.2013
comment
Хм.. вы не знаете, смогу ли я свободно использовать сдвиг, используя лонг?   -  person John McBrown    schedule 22.03.2013
comment
Поскольку вы используете Java, вы можете использовать беззнаковый оператор сдвига вправо >>> для выполнения сдвига, необходимого для арифметического сжатия.   -  person comingstorm    schedule 22.03.2013
comment
Я провожу некоторые исследования, чтобы понять, не могу ли я попробовать использовать его вместо этого. Спасибо за вашу помощь, я сообщу вам в ближайшее время. Если бы вы могли предоставить любой код, я также был бы очень благодарен.   -  person John McBrown    schedule 22.03.2013
comment
К сожалению, на самом деле основной оператор, который вам больше всего понадобится для арифметического сжатия, — это оператор сдвига влево <<. Однако, в зависимости от того, как вы реализуете свою математику, знание о беззнаковом операторе сдвига вправо также может быть полезным...   -  person comingstorm    schedule 22.03.2013


Ответы (1)


Что касается смещения вашей строки влево, используйте: string.substring(1)

person Amir    schedule 23.06.2013