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

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

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

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

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

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

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

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

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

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

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

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

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

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

Разбор задач

Минимальная длина фиксированного кода

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

1. Проверим длину 1: двумя битовыми комбинациями можно обозначить только два символа, этого мало.
2. Проверим длину 2: комбинаций четыре, для восьми символов их также недостаточно.
3. Проверим длину 3: 2³ = 8, значит, комбинаций хватает ровно на весь алфавит.

Ответ: минимальная фиксированная длина равна 3 битам на символ. Проверка по степеням двойки помогает не путать размер алфавита с длиной кодового слова. Если символов было бы больше восьми, трёх битов уже не хватило бы.

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

Условие: построить код Хаффмана для символов А, Б, В и Г с частотами 5, 2, 1 и 1 соответственно. На каждом шаге выбирают два узла с наименьшими частотами. Значения 0 и 1 на ветвях можно назначить по-разному, поэтому возможны разные, но равноценные таблицы кодов.

1. Два узла с частотой 1 — В и Г — объединяем в узел с частотой 2.
2. Теперь наименьшие частоты равны 2: у Б и у нового узла. Объединяем их, получая узел с частотой 4.
3. Объединяем узлы с частотами 4 и 5 в корень с частотой 9. Назначим ветви так: корень ведёт к А по 0, к узлу частоты 4 по 1; внутри него Б получает 10, а В и Г — 110 и 111.

Ответ: один из вариантов кодов — А: 0, Б: 10, В: 110, Г: 111. Код префиксный: ни одно из этих слов не является началом другого. Символу А с наибольшей частотой досталось самое короткое слово, а символам В и Г — самые длинные.

Кодирование и сравнение объёма

Условие: для таблицы А: 0, Б: 10, В: 110, Г: 111 закодировать сообщение АБВГА и сравнить результат с фиксированным кодом для четырёх символов. В фиксированном варианте каждому символу нужны два бита, потому что 2² = 4. Сначала заменим каждую букву её словом, затем посчитаем биты.

1. Подставим кодовые слова по порядку: АБВГА превращается в 0, 10, 110, 111, 0.
2. Запишем их подряд: 0101101110. Длина результата равна 1 + 2 + 3 + 3 + 1 = 10 битов.
3. Проверим чтение слева направо: 0 — это А, затем 10 — Б, 110 — В, 111 — Г, последний 0 — А. Фиксированный код занял бы 5 × 2 = 10 битов.

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

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

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

Ошибка: путать число символов алфавита с длиной слова в битах. Для фиксированного кода длину выбирают по условию 2ⁿ не меньше размера алфавита, а не просто берут число символов. Проверка: подставьте выбранное n и убедитесь, что комбинаций хватает, а для n − 1 их недостаточно.

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

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

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

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

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

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

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

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