§ 18. Экономные коды. Алгоритмы сжатия

Определения и обозначения

Экономный код — код, который сокращает среднюю длину сообщения, назначая короткие кодовые слова часто встречающимся символам. Например, если буква повторяется много раз, каждый сэкономленный для неё бит уменьшает общий размер заметнее, чем для редкой буквы. Поэтому при оценке кода важно знать не только сами слова, но и частоты символов.

Префиксный код — код, в котором ни одно кодовое слово не является началом другого. Тогда декодер, читая поток слева направо, как только встречает полное кодовое слово, однозначно определяет соответствующий символ и начинает искать следующий. Границы слов находятся без пробелов и дополнительных разделителей.

Средняя длина кодового слова — среднее число бит, приходящееся на один символ с учётом того, как часто он встречается. Её находят, умножая длину каждого кодового слова на долю соответствующего символа и складывая результаты. Эта величина помогает сравнить коды независимо от длины конкретного сообщения.

Сжатие без потерь — уменьшение объёма данных, после которого исходное сообщение можно восстановить полностью и без изменений. Для этого при декодировании должны быть известны и сами кодовые слова, и правила их чтения. Такой подход нужен там, где нельзя потерять ни одного символа или бита исходных данных.

Как это устроено

Если все символы встречаются одинаково часто, ни один из них не даёт повода выделять ему более короткий код. При небольшом алфавите можно назначить всем символам слова одной длины: так проще кодировать и декодировать сообщение. Минимальную длину выбирают так, чтобы хватило разных слов для всех символов; для n бит существует 2ⁿ вариантов. Если частоты различаются, одинаковые коды могут расходовать лишние биты на часто повторяющиеся символы.

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

Метод Шеннона—Фано строит дерево последовательным делением списка. Сначала символы упорядочивают по убыванию частоты, затем делят на две группы так, чтобы суммы частот в них были как можно ближе. Группам назначают биты 0 и 1, а каждую группу таким же способом делят дальше, пока в каждой части не останется один символ. Код символа — последовательность битов на пути к нему; деление на группы создаёт префиксный код.

В алгоритме Хаффмана сначала каждый символ считают отдельным узлом с его частотой. На каждом шаге два узла с наименьшими частотами объединяют в новый узел, частота которого равна их сумме; затем выбирают следующую наименее частую пару. Когда остаётся один корень, ветвям дерева присваивают 0 и 1, а код каждого символа получают по пути от корня. Редкие символы обычно оказываются глубже, а частые — ближе к корню, что сокращает среднюю длину.

Чтобы сравнить кодирование, для каждого символа умножают его частоту на длину кодового слова и складывают результаты. Так получают общее число бит для сообщения; для средней длины сумму делят на количество символов. Однако кодировщику и получателю нужна таблица соответствий символов и кодов, а её передача тоже занимает место. Поэтому итоговый размер — это не только закодированная последовательность, но и служебные данные, особенно заметные для короткого сообщения.

Сравнение способов кодирования символов

Сначала выбери строку, которая отвечает на нужный вопрос: например, как учитываются частоты или как именно строят код. Чтобы сравнить экономичность, одной длины отдельных слов недостаточно — посчитай суммарное количество бит для заданных частот. Затем прибавь размер таблицы, если сравнивается полный объём передаваемых данных.

Разбор задач

Четыре равновероятных символа

Нужно определить минимальное число бит для каждого символа и привести пример кодовых слов. Поскольку символы равновероятны, нет смысла назначать одному из них более короткое слово за счёт другого. Ищем наименьшую длину, для которой доступно не меньше четырёх разных двоичных слов.

1. Считаем число вариантов для коротких слов: при длине 1 доступны 2 слова, а при длине 2 — 2² = 4. Двух вариантов недостаточно для четырёх символов. Значит, минимальная подходящая длина — 2 бита.

2. Назначаем символам, например, слова 00, 01, 10 и 11. Все слова имеют одинаковую длину, поэтому их границы очевидны при чтении потока. Этот код также префиксный: слова одинаковой длины не могут быть началом друг друга.

Ответ: достаточно 2 бит на символ; пример кодов — 00, 01, 10, 11.

Метод Шеннона—Фано для пяти символов

Пусть частоты символов A, B, C, D, E равны соответственно 16, 8, 7, 5, 4, а сообщение — ABCDE. Сумма частот равна 40, поэтому при построении дерева нужно делить символы на группы с близкими суммами. После каждого деления добавляем к кодам бит соответствующей ветви.

1. Упорядочивать символы уже не нужно: они расположены по убыванию частоты. Делим их на группы A с частотой 16 и B, C, D, E с суммой 24. Назначим первой группе 0, второй — 1.

2. Группу B, C, D, E делим на B, C с суммой 15 и D, E с суммой 9. Приписываем этим группам соответственно 0 и 1 после уже полученной единицы.

3. Делим B и C на отдельные символы, а затем так же поступаем с D и E. Получаем коды A = 0, B = 100, C = 101, D = 110, E = 111. Каждое слово не является началом другого, поэтому сообщение можно декодировать однозначно.

4. Для сообщения ABCDE выписываем код каждого символа по порядку. Соединяем слова без разделителей: 0 + 100 + 101 + 110 + 111 = 0100101110111. Число бит равно сумме длин слов: 1 + 3 + 3 + 3 + 3 = 13.

Ответ: коды A = 0, B = 100, C = 101, D = 110, E = 111; сообщение ABCDE кодируется как 0100101110111.

Построение кода Хаффмана

Пусть частоты A, B, C, D равны 8, 4, 2, 1, а сообщение — ABCD. Построим дерево Хаффмана и сравним его с кодом одинаковой длины. Чтобы увидеть экономию, будем считать суммарное число бит для каждой буквы с учётом её частоты.

1. Выбираем два наименее частых узла: D с частотой 1 и C с частотой 2. Объединяем их в узел частоты 3. Теперь частоты узлов равны 3, 4 и 8.

2. Объединяем два наименее частых узла: узел 3 и символ B с частотой 4. Получаем узел 7, который объединяем с A частоты 8. Назначая ветвям 0 и 1, можно получить коды A = 1, B = 00, C = 010, D = 011.

3. Кодируем ABCD: получаем 1 + 00 + 010 + 011 = 100010011. Для таблицы частот суммарная длина равна 8 × 1 + 4 × 2 + 2 × 3 + 1 × 3 = 25 бит. При одинаковых двухбитных словах было бы 15 символов × 2 = 30 бит.

4. Сравниваем результаты: код Хаффмана экономит 5 бит на закодированной последовательности. Он не обязательно короче для каждого отдельного короткого сообщения, но при заданных частотах имеет меньшую суммарную длину. Перед передачей ещё нужно учесть размер таблицы кодов.

Ответ: один из кодов Хаффмана: A = 1, B = 00, C = 010, D = 011; последовательность ABCD занимает 9 бит. Для приведённых частот код одинаковой длины занял бы 30 бит, а код Хаффмана — 25 бит.

Типичные ошибки

Считать любой код с короткими словами экономным — ошибка, потому что важно, каким символам эти слова назначены. Её допускают, когда сравнивают отдельные длины и забывают о частотах; короткий код редкого символа может почти ничего не изменить. Проверка: вычисли сумму произведений частот на длины, а не оценивай одно слово отдельно.

Использовать слова переменной длины без префиксности рискованно: без разделителей поток может читаться неоднозначно. Например, при словах 1 и 10 последовательность 10 можно понять как один символ или как два. Проверяй каждую пару слов: ни одно не должно быть началом другого.

При построении дерева Хаффмана иногда объединяют самые частые узлы, потому что так кажется проще уменьшить глубину дерева. Но алгоритм требует каждый раз брать именно два узла с наименьшими частотами, иначе полученное дерево может не дать минимальную среднюю длину. После каждого шага заново упорядочивай частоты, включая частоты уже созданных узлов.

Сравнивать только длину закодированной последовательности недостаточно: для восстановления символов получателю нужна таблица кодов. Эту часть затрат часто не замечают, особенно если считают только биты сообщения. Проверь итоговый размер целиком — сложи длину закодированных данных и объём таблицы; на коротком сообщении таблица может свести экономию на нет.

Связь с другими темами

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

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

Что запомнить

• Экономный код использует частоты символов, чтобы уменьшить среднюю длину кодового слова.
• Частым символам выгодно назначать более короткие кодовые слова.
• Префиксный код можно однозначно декодировать без разделителей между кодовыми словами.
• В коде Шеннона—Фано символы последовательно делят на группы с близкими суммарными частотами.
• В алгоритме Хаффмана на каждом шаге объединяют два наименее частых узла.
• Сжатие без потерь позволяет восстановить исходное сообщение, но для декодирования нужно знать код.