Если Вы попали на эту страницу, значит уже усели познакомиться с алфавитным кодированием. А если так, то самое время перейти к блочному. Что это такое? Как это работает? Зачем вообще информацию кодировать и сжимать? Интересно? Тогда скорее листайте вниз, будем разбираться.
На сегодняшний день наилучший результат (наименьшая избыточность) был получен при кодировании методом Хаффмана — для русского алфавита избыточность оказалась менее 1 %. При этом указывалось, что код Хаффмана улучшить невозможно. На первый взгляд это противоречит первой теореме Шеннона, утверждающей, что всегда можно предложить способ кодирования, при котором избыточность будет сколь угодно малой величиной. На самом деле это противоречие возникло из-за того, что до сих пор мы ограничивали себя алфавитным кодированием.
При алфавитном кодировании передаваемое сообщение представляет собой последовательность кодов отдельных знаков первичного алфавита. Однако возможны варианты кодирования, при которых кодовый знак относится сразу к нескольким буквам первичного алфавита (будем называть такую комбинацию блоком) или даже к целому слову первичного языка. Кодирование блоков понижает избыточность. B этом легко убедиться на простом примере.
Пусть первичный алфавит состоит из двух знаков a и b с вероятностями 0,75 и 0,25 соответственно. Необходимо сравнить избыточность кода Хаффмана при алфавитном и блочном двухбуквенном кодировании.
При алфавитном кодировании:
При блочном двухбуквенном кодировании :
Различных сочетаний может быть 4; если сообщение является шенновским, что для каждой пары pij = pipj . B результате алфавит (A′) состоит из 4-х знаков с известными вероятностями; применяя к нему метод Хаффмана, получаем коды:
Таким образом, блочное кодирование обеспечивает построение более сжатого кода, чем алфавитное. При использовании блоков большей длины (трехбуквенных и более) избыточность стремится к нулю в полном соответствии с первой теоремой Шеннона.
Цель сжатия — уменьшение количества бит, необходимых для хранения или передачи заданной информации, что дает возможность передавать сообщения более быстро и хранить более экономно и оперативно (последнее означает, что операция извлечения данной информации с устройства ее хранения будет проходить быстрее, что возможно, если скорость распаковки данных выше скорости считывания данных с носителя информации).
Сжатие позволяет, например, записать больше информации на носитель, эффективно увеличить размер жесткого диска, ускорить работу с модемом и т. д.
При работе с компьютерами широко используются программы-архиваторы данных формата ZIP, GZ, ARJ и других.
Методы сжатия информации были разработаны как математическая теория, которая долгое время (до первой половины 80-х годов) мало использовалась в компьютерах на практике.
Следует осознавать, что, несмотря на кажущиеся преимущества, применение блочного кодирования создать дополнительные проблемы, поскольку требует, наряду с передачей информационных бит, пересылки на приемный конец и таблицы блочных кодов, без чего декодирование оказывается невозможным.
Это важно! Никогда не забывайте, что у любой медали - две стороны. И прежде чем сделать выбор, обязательно посмотрите на обе.
Спасибо за обращение к данной статье. Надеюсь, материал оказался для Вас полезен!
