Источник информации генерирует символы с вероятностями P(A)=0.5, P(B)=0.3, P(C)=0.2: вычислите энтропию источника, предложите префиксный код (например, код Хаффмана), посчитайте ожидаемую длину кодирования и объясните, почему практическая компрессия часто не достигает энтропийного предела (модель, оверхед, адаптивность); обсудите применение этих идей в современных алгоритмах сжатия (gzip, Brotli, LZ77+экспоненты)
Источник информации генерирует символы с вероятностями P(A)=0.5, P(B)=0.3, P(C)=0.2: вычислите энтропию источника, предложите префиксный код (например, код Хаффмана), посчитайте ожидаемую длину кодирования и объясните, почему практическая компрессия часто не достигает энтропийного предела (модель, оверхед, адаптивность); обсудите применение этих идей в современных алгоритмах сжатия (gzip, Brotli, LZ77+экспоненты)
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
H=−∑ipilog2pi=−(0.5log20.5+0.3log20.3+0.2log20.2) H = -\sum_i p_i\log_2 p_i = -\big(0.5\log_2 0.5 + 0.3\log_2 0.3 + 0.2\log_2 0.2\big)
H=−i∑ pi log2 pi =−(0.5log2 0.5+0.3log2 0.3+0.2log2 0.2) H=−(0.5⋅(−1)+0.3⋅log20.3+0.2⋅log20.2)=0.5+0.52109+0.46439≈1.48548 бит/символ H = -\big(0.5\cdot(-1) + 0.3\cdot\log_2 0.3 + 0.2\cdot\log_2 0.2\big)
= 0.5 + 0.52109 + 0.46439 \approx 1.48548\ \text{бит/символ}
H=−(0.5⋅(−1)+0.3⋅log2 0.3+0.2⋅log2 0.2)=0.5+0.52109+0.46439≈1.48548 бит/символ
2) Префиксный (Хаффмановский) код — один из оптимальных: A=0, B=10, C=11A=0,\; B=10,\; C=11A=0,B=10,C=11. Длины кодов ℓ(A)=1, ℓ(B)=2, ℓ(C)=2\ell(A)=1,\;\ell(B)=2,\;\ell(C)=2ℓ(A)=1,ℓ(B)=2,ℓ(C)=2.
Ожидаемая длина:
L=∑ipiℓ(i)=0.5⋅1+0.3⋅2+0.2⋅2=0.5+0.6+0.4=1.5 бит/символ. L = \sum_i p_i\ell(i) = 0.5\cdot1 + 0.3\cdot2 + 0.2\cdot2 = 0.5+0.6+0.4 = 1.5\ \text{бит/символ}.
L=i∑ pi ℓ(i)=0.5⋅1+0.3⋅2+0.2⋅2=0.5+0.6+0.4=1.5 бит/символ. Редундантность: L−H≈1.5−1.48548≈0.01452 бит/символL-H \approx 1.5-1.48548 \approx 0.01452\ \text{бит/символ}L−H≈1.5−1.48548≈0.01452 бит/символ.
3) Почему практическая компрессия часто не достигает энтропийного предела (кратко):
- Модель: реальный источник не обязательно независим и одинаково распределён; неточная модель даёт потерю (модельное несовпадение).
- Конечная длина блоков: теорема асимптотична — при конечной длине блока дополнительные потери порядка O(logn/n)O(\log n / n)O(logn/n).
- Оверхед: заголовки, таблицы кодов, словари, метаданные и выравнивание по байтам/байт-границам.
- Адаптивность: адаптивные модели обучаются на данных, при старте теряется эффективность (начальные символы хуже кодируются); статические модели требуют передачи модели.
- Вычислительные и аппаратные ограничения: точность арифметики, целочисленное кодирование, ограничения памяти/скорости ведут к приближениям.
- Ограничения кодов: практичные требования (быстрый декодер, случайный доступ) приводят к субоптимальным конструкциям.
4) Применение в современных алгоритмах:
- Gzip/DEFLATE: LZ77 (поиск повторов -> литералы и пары длина-расстояние) + Huffman-кодирование токенов. LZ77 снижает энтропию потока, Huffman кодирует остающиеся символы; динамические таблицы Huffman создают оверхед.
- Brotli: тоже LZ77-подобные бек-референсы + контекстное моделирование литералов + Huffman-подобное кодирование; использует техники (статические словари, контекстные модели), чтобы приблизиться к энтропийному пределу при разумной производительности.
- Современные энтропийные кодеры: ANS/FSE (используется, например, в Zstd) дают очень близкие к энтропии результаты с высокой скоростью и низким оверхедом по сравнению с классическим Huffman.
- Общая схема: LZ-подобный предобработчик сокращает корреляции/повторяемость, затем энтропийный кодер (Huffman/ANS) кодирует символы почти до их энтропии. Но практический результат ограничен перечисленными факторами (модель, блоки, оверхед, скорость).
Кратко: энтропия даёт теоретический предел ≈1.4855\approx 1.4855≈1.4855 бит/символ; простой Huffman даёт 1.51.51.5 бит/символ. Практические алгоритмы комбинируют повторное кодирование (LZ77) и продвинутое энтропийное кодирование (Huffman/ANS/FSE) и приближаются к пределу, но не достигают его из‑за модели, оверхеда и инженерных ограничений.