Декодирование префиксного кода
Декодирование префиксного кода — это восстановление исходного сообщения по его закодированной последовательности. Благодаря свойству префиксности каждое очередное кодовое слово распознаётся однозначно: не нужно угадывать границы между словами и возвращаться назад.
Основные понятия
Сначала составляют таблицу соответствия: каждому символу исходного алфавита ставят в соответствие кодовое слово, обычно последовательность нулей и единиц. Например: \(А\to0\), \(Б\to10\), \(В\to110\), \(Г\to111\). Закодированное сообщение получают заменой каждого исходного символа его кодовым словом.
Префиксный код — это код, в котором ни одно кодовое слово не является началом другого кодового слова. Иначе говоря, для любых различных слов \(x\) и \(y\) слово \(x\) не является префиксом слова \(y\).
Декодирование — чтение закодированной последовательности слева направо с заменой каждого распознанного кодового слова на соответствующий исходный символ.
Префиксность гарантирует не только отсутствие совпадающих кодовых слов, но и отсутствие неоднозначного разбиения. Если во время чтения встретилось слово \(10\), то оно уже не может быть началом более длинного кодового слова: в таблице нет слова, начинающегося с \(10\).
Как распознавать кодовые слова
Работайте с последовательностью слева направо. На каждом шаге накапливайте очередной бит и проверяйте таблицу. Возможны два состояния: накопленный фрагмент ещё не является кодовым словом, либо он уже является кодовым словом. В префиксном коде после распознавания слова можно сразу начать чтение следующего фрагмента.
- Поставьте указатель перед первым битом закодированного сообщения.
- Читайте биты слева направо, пока полученный фрагмент не совпадёт с кодовым словом.
- Запишите соответствующий исходный символ.
- Перенесите указатель на первый ещё не прочитанный бит и повторите действия.
Если код префиксный, то любая последовательность кодовых слов имеет единственное разбиение. Поэтому жадный алгоритм «прочитать кратчайшее совпавшее слово и продолжить» всегда восстанавливает исходное сообщение правильно.
Удобно изображать код в виде дерева: переход по ветви с меткой \(0\) означает чтение нуля, а по ветви с меткой \(1\) — чтение единицы. Кодовое слово — путь от корня до листа. Лист нельзя продолжать другим кодовым словом, поэтому кодовые слова не могут быть префиксами друг друга.
Какое множество кодовых слов является префиксным?
Пошаговое декодирование
Рассмотрим таблицу \(А\to0\), \(Б\to10\), \(В\to110\), \(Г\to111\) и последовательность \(01101110\). Нужно не делить её на равные части: длины кодовых слов различаются. Следует каждый раз начинать с первого ещё не использованного бита.
Декодируем последовательность \(01101110\) по таблице \(А\to0\), \(Б\to10\), \(В\to110\), \(Г\to111\).
Ответ: исходное сообщение — АВГА. Проверка выполняется обратной заменой: \(АВГА\to0\,110\,111\,0=01101110\).
Алгоритм и контроль результата
Вручную достаточно таблицы и указателя на текущую позицию. При большом сообщении можно представить таблицу как словарь и последовательно проверять накопленный фрагмент. В заданиях экзамена чаще требуется именно аккуратное разбиение строки, а не написание программы.
- Записать все кодовые слова и соответствующие символы.
- Начинать чтение с самого левого ещё не обработанного бита.
- Не пропускать биты и не использовать один бит дважды.
- После каждого найденного слова сразу записывать символ.
- В конце убедиться, что использована вся последовательность.
Здесь \(s\) — закодированная строка, а \(C\) — множество кодовых слов. Успешное декодирование означает, что строка полностью представлена конкатенацией слов из \(C\). Если в конце остался фрагмент, не являющийся кодовым словом, значит, допущена ошибка в чтении или строка не была получена этим кодом.
Разбиение на равные части. Оно допустимо только для кода фиксированной длины. Поиск самого длинного слова. Для префиксного кода правильнее читать слева направо до первого совпадения. Забытый остаток. Последний фрагмент также должен быть кодовым словом. Проверка только начала строки. Нужно обработать всю последовательность. Путаница направления. Декодируют слева направо, если направление специально не указано иначе.
Подпишите над строкой вертикальные черты после каждого найденного кодового слова: \(0|110|111|0\). Так легче заметить пропущенный или повторно использованный бит.
Что происходит при неоднозначном коде
Если одно кодовое слово является началом другого, жадное чтение может привести к ошибке. Например, для слов \(А\to0\), \(Б\to01\) строка \(01\) допускает два варианта: \(Б\) или \(А\) и затем незавершённый фрагмент. В более длинной строке могут появиться два полностью завершённых разбиения. Такой код не обеспечивает однозначного декодирования.
Префиксный код является частным случаем кода переменной длины и позволяет выполнять кодирование без потерь. Таблицу соответствий строят заранее; об общих принципах можно прочитать на странице построение таблицы кодирования.
Быстрая проверка
Проверьте себя
Главное
- Префиксный код не содержит кодового слова, являющегося началом другого.
- Декодирование выполняют слева направо: читают до первого совпадения, записывают символ и продолжают.
- Однозначность разбиения обеспечивается свойством префиксности.
- После обработки всей строки не должно оставаться необработанных битов.
- Для проверки полезно восстановить кодовую последовательность обратной заменой символов.