Изменения

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

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

Известно<ref>https://scask.ru/a_book_sel.php?id=23</ref>, что совсем необязательно, чтобы подинтервалы более частых символов располагались ближе к началу рабочего интервала, порядок может быть абсолютно любым. Поэтому для адаптивного арифметического кодирования можно расставить подинтервалы, соответствующие каждому символу, в порядке появления этих символов в тексте, зарезервировав последний подинтервал для случая, когда очередной символ встречается во входном потоке первый раз. В этом случае передается сначала этот последний подинтервал, а затем сам символ, что позволяет декодеру "опознать" его. Когда известных с начала входного потока символов несколько, их [[Кумуляция|кумулятивные]] частоты можно хранить в обычном [[Массив (тип данных)|массиве]], если же их число достигает сотни и больше, удобно применять такую структуру данных, как [[Двоичное дерево|бинарное сбалансированное дерево]]<ref>[https://scask.ru/a_book_sel.php?id=23 https://scask.ru/a_book_sel.php?id=23], чуть ниже Табл. 1.36</ref>, в котором каждая ветвь хранит два значения: непосредственную частоту символа и сумму частот всех символов, входящих в эту ветвь.<ref group="Комм.">А также [[Ссылка (программирование)|ссылку]] на родительскую ветвь в качестве "служебного" поля: когда частота [[Присваивание|изменяется]], дерево должно [[Сеттер (программирование)|автоматически изменить]] соответствующие суммы частот для родительской ветви, для родительской от родительской ветви и т. д. до корня.</ref> При появлении очередного символа его частота в дереве увеличивается на 1, но лишь ''после'' изменения рабочего интервала, иначе декодирование станет невозможным.

Известно<ref>[https://scask.ru/a_book_sel.php?id=23 1.8. Адаптивное арифметическое кодирование<!-- Заголовок добавлен ботом -->]</ref>, что совсем необязательно, чтобы подинтервалы более частых символов располагались ближе к началу рабочего интервала, порядок может быть абсолютно любым. Поэтому для адаптивного арифметического кодирования можно расставить подинтервалы, соответствующие каждому символу, в порядке появления этих символов в тексте, зарезервировав последний подинтервал для случая, когда очередной символ встречается во входном потоке первый раз. В этом случае передается сначала этот последний подинтервал, а затем сам символ, что позволяет декодеру "опознать" его. Когда известных с начала входного потока символов несколько, их [[Кумуляция|кумулятивные]] частоты можно хранить в обычном [[Массив (тип данных)|массиве]], если же их число достигает сотни и больше, удобно применять такую структуру данных, как [[Двоичное дерево|бинарное сбалансированное дерево]]<ref>[https://scask.ru/a_book_sel.php?id=23 https://scask.ru/a_book_sel.php?id=23], чуть ниже Табл. 1.36</ref>, в котором каждая ветвь хранит два значения: непосредственную частоту символа и сумму частот всех символов, входящих в эту ветвь.<ref group="Комм.">А также [[Ссылка (программирование)|ссылку]] на родительскую ветвь в качестве "служебного" поля: когда частота [[Присваивание|изменяется]], дерево должно [[Сеттер (программирование)|автоматически изменить]] соответствующие суммы частот для родительской ветви, для родительской от родительской ветви и т. д. до корня.</ref> При появлении очередного символа его частота в дереве увеличивается на 1, но лишь ''после'' изменения рабочего интервала, иначе декодирование станет невозможным.

Другой вариант алгоритма для входного потока, структура которого заранее известна, предложен здесь: <ref>https://studfile.net/preview/6085051/page:8/</ref>. В этом случае не резервируется подинтервал для нового символа, а подинтервалы для всех символов с самого начала имеют "вес", равный 1 (и в дальнейшем он всегда на 1 больше, чем в первом варианте).

Другой вариант алгоритма для входного потока, структура которого заранее известна, предложен здесь: <ref>[https://studfile.net/preview/6085051/page:8/ Адаптивное арифметическое кодирование<!-- Заголовок добавлен ботом -->]</ref>. В этом случае не резервируется подинтервал для нового символа, а подинтервалы для всех символов с самого начала имеют "вес", равный 1 (и в дальнейшем он всегда на 1 больше, чем в первом варианте).

<!-- закомментировано под перевод

<!-- закомментировано под перевод