1313
правок
Арифметическое кодирование для сжатия данных: различия между версиями
Материал из WEGA
Арифметическое кодирование для сжатия данных (посмотреть исходный код)
Версия от 04:50, 7 декабря 2024
, 7 декабря 2024→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показаны 2 промежуточные версии 1 участника) | |||
| Строка 146: | Строка 146: | ||
Число возможных состояний (после применения процедуры расширения интервала) арифметического кодера, использующего целочисленный интервал [0, N), равно <math>3N^2/16</math>. Очевидным способом уменьшения числа состояний | Число возможных состояний (после применения процедуры расширения интервала) арифметического кодера, использующего целочисленный интервал [0, N), равно <math>3N^2/16</math>. Очевидным способом уменьшения числа состояний до такого, при котором использование таблиц поиска становится практичным, является уменьшение значения N. Двоичное квазиарифметическое кодирование приводит к незначительному увеличению длины кода по сравнению с чисто арифметическим кодированием. | ||
'''Теорема 2. В квазиарифметическом кодере, основанном на полном интервале [0, N), использующем корректные оценки вероятностей и исключающем очень большие и очень малые вероятности, количество бит на входное событие, при котором средняя длина кода, полученного квазиарифметическим кодером, превышает длину кода, полученного точным арифметическим кодером, составляет не более''' <math>\frac{4}{ln \; 2} \bigg( log_2 \; \frac{2}{e \; ln \; 2} \bigg) \frac{1}{N} + O \bigg( \frac{1}{N^2} \bigg) \approx \frac{0,497}{N} + O \bigg( \frac{1}{N^2} \bigg),</math> | '''Теорема 2. В квазиарифметическом кодере, основанном на полном интервале [0, N), использующем корректные оценки вероятностей и исключающем очень большие и очень малые вероятности, количество бит на входное событие, при котором средняя длина кода, полученного квазиарифметическим кодером, превышает длину кода, полученного точным арифметическим кодером, составляет не более''' <math>\frac{4}{ln \; 2} \bigg( log_2 \; \frac{2}{e \; ln \; 2} \bigg) \frac{1}{N} + O \bigg( \frac{1}{N^2} \bigg) \approx \frac{0,497}{N} + O \bigg( \frac{1}{N^2} \bigg),</math> | ||
'''а доля, на которую средняя длина кода, полученная квазиарифметическим кодером, превышает длину кода, полученную точным арифметическим кодером, не | '''а доля, на которую средняя длина кода, полученная квазиарифметическим кодером, превышает длину кода, полученную точным арифметическим кодером, составляет не более''' <math>\bigg( log_2 \; \frac{2}{e \; ln \; 2} \bigg) \frac{1}{log_2 \; N} + O \bigg( \frac{1}{(log_2 \; N)^2} \bigg) \approx \frac{0,0861}{log_2 \; N} + O \bigg( \frac{1}{(log_2 \; N)^2} \bigg).</math> | ||
| Строка 160: | Строка 160: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Технические проблемы, связанные с арифметическим кодированием, полностью решены. Оставшиеся нерешенными | Технические проблемы, связанные с арифметическим кодированием, полностью решены. Оставшиеся нерешенными задачи связаны с моделированием – разложением входного набора данных на последовательность событий, причем набор событий, возможных в каждой точке набора данных, должен быть описан распределением вероятностей, пригодным для ввода в кодер. Вопросы моделирования полностью зависят от конкретного применения. | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
| Строка 197: | Строка 197: | ||
11. Witten, I.H., Neal, R.M., Cleary, J.G.: Arithmetic coding for data compression. Commun. ACM 30, 520-540 (1987) | 11. Witten, I.H., Neal, R.M., Cleary, J.G.: Arithmetic coding for data compression. Commun. ACM 30, 520-540 (1987) | ||
[[Категория: Совместное определение связанных терминов]] | |||
