06.12.2023 / Сжатие данных

Сжатие данных

Учет частотности символов при выборе неравномерного кода

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

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

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

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

Алгоритм LZW

В этом случае для символов, которые часто встречаются, используются более короткие коды, чем для редко встречающихся символов. Однако при использовании таких кодов возникают проблемы при декодировании сообщений, записанных таким образом.

Эти проблемы были решены американскими учёными К. Шенноном и Р. М. Фано, которые сформулировали условие, достаточное для однозначного декодирования сообщений с переменной длиной кодовых слов: никакое кодовое слово не может быть началом другого кодового слова. Обычно это условие называют условием Шеннона-Фано, а код, удовлетворяющий этому условию, – префиксным кодом.

Алгоритм Хаффмана

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

Алгоритм Хаффмана – жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Метод основывается на создании бинарных деревьев, где узел может быть либо конечным, либо внутренним. Изначально все узлы считаются листьями, представляющими символ и его вес. Внутренние узлы содержат вес символа и ссылаются на два узла-наследника.

При построении дерева Хаффмана отбрасываются неиспользуемые символы для получения кодов оптимальной длины. Используется очередь с приоритетами, где узлу с наименьшей частотой присваивается высший приоритет. Шаги построения дерева:

1. Создаем узел-лист для каждого символа и добавляем их в очередь с приоритетами.

2. Пока в очереди больше одного листа, повторяем следующее:

   • Удаляем два узла с наивысшим приоритетом (с наименьшей частотой) из очереди.

   • Создаем новый внутренний узел, где эти два узла будут наследниками, а частота будет равна сумме их частот.

   • Добавляем новый узел в очередь приоритетов.

3. Оставшийся узел становится корневым, завершая построение дерева.

Пример частот символов: A-16, B-7, C-6, D-6, E-5.