4511
правок
Арифметическое кодирование для сжатия данных: различия между версиями
Материал из WEGA
Арифметическое кодирование для сжатия данных (посмотреть исходный код)
Версия от 18:27, 7 августа 2023
, 7 августа 2023→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 88: | Строка 88: | ||
2. Для каждого события в файле выполняются два шага. | 2. Для каждого события в файле выполняются два шага. | ||
(а) Разделить текущий интервал на подынтервалы, по одному на каждое возможное событие. Размер подынтервала события пропорционален расчетной вероятности того, что это событие будет следующим в файле, согласно модели входных данных. | |||
(б) Выбрать подынтервал, соответствующий событию, которое действительно произойдет следующим, и сделать его новым текущим интервалом. | |||
3. Вывести достаточное количество бит, чтобы отличить конечный текущий интервал от всех других возможных конечных интервалов. | 3. Вывести достаточное количество бит, чтобы отличить конечный текущий интервал от всех других возможных конечных интервалов. | ||
Длина конечного подынтервала, очевидно, равна произведению вероятностей отдельных событий, что и является вероятностью p конкретной общей последовательности событий. Можно показать, что для отличия файла от всех других возможных файлов достаточно | Длина конечного подынтервала, очевидно, равна произведению вероятностей отдельных событий, что и является вероятностью p конкретной общей последовательности событий. Можно показать, что для отличия файла от всех других возможных файлов достаточно <math>\lfloor - log_2 \; \rfloor p + 2</math> бит. | ||
Для файлов конечной длины необходимо указать конец файла. При арифметическом кодировании это легко сделать, введя специальное маловероятное событие, которое может быть добавлено во входной поток в любой момент. Это добавляет всего O(log m) бит к кодированной длине m-символьного файла. | Для файлов конечной длины необходимо указать конец файла. При арифметическом кодировании это легко сделать, введя специальное маловероятное событие, которое может быть добавлено во входной поток в любой момент. Это добавляет всего O(log m) бит к кодированной длине m-символьного файла. | ||
На шаге 2 необходимо вычислить только подынтервал, соответствующий событию | |||
На шаге 2 необходимо вычислить только подынтервал, соответствующий событию <math>a_i</math>, которое действительно произошло. Для этого удобно использовать две «кумулятивные» вероятности: кумулятивную вероятность <math>P_C = \sum_{k = 1}^{i - 1} p_k</math> и следующую кумулятивную вероятность <math>P_N = P_C + p_i = \sum_{k = 1}^i p_k</math>. Новый подынтервал имеет вид <math>[L + P_C(H - L); L + P_N(H - L))</math>. Необходимость хранения и предоставления кумулятивных вероятностей требует от модели сложной структуры данных – например, как у Моффата [7] – особенно когда возможно более двух событий. | |||
