Коды постоянной и переменной длины. Вопросы и задания. Кодирование и сжатие информаци

>>Информатика: Информатика 9 класс. Дополнение к главе 1

Дополнение к главе 1

1.1. Передача информации по техническим каналам связи

Основные темы параграфа:

♦ схема К. Шеннона;
♦ кодирование и декодирование информации;
♦ шум и защита от шума. Теория кодирования К. Шеннона.

Схема К. Шеннона

Американским ученым, одним из основателей теории информации, Клодом Шенноном была предложена схема процесса передачи информации по техническим каналам связи, представленная на рис. 1.3.

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

Связь, при которой передача производится в форме непрерывного электрического сигнала, называется аналоговой связью.

Кодирование и декодирование информации

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

На заре эры радиосвязи применялся азбуки Морзе. Текст преобразовывался в последовательность точек и тире (коротких и длинных сигналов) и передавался в эфир. Принимавший на слух такую передачу человек должен был суметь декодировать код обратно в текст. Еще раньше азбука Морзе использовалась в телеграфной связи. Передача информации с помощью азбуки Морзе - это пример дискретной связи.

В настоящее время широко используется цифровая связь, когда передаваемая информация кодируется в двоичную форму (0 и 1 - двоичные цифры), а затем декодируется в текст, изображение, звук. Цифровая связь, очевидно, тоже является дискретной.

Шум и защита от шума. Теория кодирования К. Шеннона

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

В первую очередь применяются технические способы защиты каналов связи от воздействия шумов. Такие способы бывают самыми разными, иногда - простыми, иногда - очень сложными. Например, использование экранированного кабеля вместо «голого» провода; применение разного рода фильтров, отделяющих полезный сигнал от шума, и пр.

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

Однако нельзя делать избыточность слишком большой. Это приведет к задержкам и удорожанию связи. Теория кодирования К. Шеннона как раз и позволяет получить такой код, который будет оптимальным. При этом избыточность передаваемой информации будет минимально возможной, а достоверность принятой информации - максимальной.

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

Коротко о главном

Любая техническая система передачи информации состоит из источника, приемника, устройств кодирования и декодирования и канала связи.

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

Шум - это помехи, приводящие к потере информации.

В теории кодирования разработаны методы представления передаваемой информации с целью уменьшения ее потерь под воздействием шума.

Вопросы и задания

1. Назовите основные элементы схемы передачи информации, предложенной К. Шенноном.
2. Что такое кодирование и декодирование при передаче информации?
3. Что такое шум? Каковы его последствия при передаче информации?
4. Какие существуют способы борьбы с шумом?

1.2. Архивирование и разархивирование файлов

Основные темы параграфа:

♦ проблема сжатия данных;
♦ алгоритм сжатия с использованием кода переменной длины;
♦ алгоритм сжатия с использованием коэффициента повторения;
♦ программы-архиваторы.

Проблема сжатия данных

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

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

Сжатие данных (архивирование файлов) происходит по специальным алгоритмам. В этих алгоритмах чаще всего используются две принципиально различающиеся идеи.

Алгоритм сжатия с использованием кода переменной длины

Первая идея: использование кода переменной длины. Данные, подвергающиеся сжатию, специальным образом делят на части (цепочки символов, «слова»). Заметим, что «словом» может быть и отдельный символ (код АSСII). Для каждого «слова» находится частота встречаемости: отношение количества повторений данного «слова» к общему числу «слов» в массиве данных. Идея алгоритма сжатия информации: кодировать наиболее часто встречающиеся «слова» кодами меньшей длины, чем редко встречающиеся «слова». При этом можно существенно сократить объем файла.

Такой подход известен давно. Он используется в азбуке Морзе, где символы кодируются различными последовательностями точек и тире, причем чаще встречающиеся символы имеют более короткие коды. Например, часто используемая буква «А» кодируется так: -. А редкая буква «Ж» кодируется: -. В отличие от кодов одинаковой длины, в этом случае возникает проблема отделения кодов букв друг от друга. В азбуке Морзе эта проблема решается с помощью «паузы» (пробела), которая, по сути, является третьим символом алфавита Морзе, то есть алфавит Морзе не двух-, а трех символьный.

Информация в памяти ЭВМ хранится с использованием двух символьного алфавита. Специального символа-разделителя нет. И все же удалось придумать способ сжатия данных с переменной длиной кода «слов», не требующий символа-разделителя. Такой алгоритм называется алгоритмом Д. Хаффмена (впервые опубликован в 1952 году). Все универсальные архиваторы работают по алгоритмам, подобным алгоритму Хаффмена.

Алгоритм сжатия с использованием коэффициента повторения

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

Программы-архиваторы

Программы-архиваторы создают архивные файлы (архивы). Архив представляет собой файл, в котором в сжатом виде хранятся один или несколько файлов. Для использования заархивированных файлов необходимо произвести их излечение из архива - разархивирование. Все программы -архиваторы обычно предоставляют следующие возможности:

Добавление файлов в архив;
извлечение файлов из архива;
удаление файлов из архива;
просмотр содержимого архива.

В настоящее время наиболее популярны архиваторы WinRar и WinZip. WinRar обладает более широкими возможностями по сравнению с WinZip. В частности, он дает возможность создания многотомного архива (это удобно, если архив необходимо скопировать на дискету, а его размер превышает 1,44 Мбайт), а также возможность создания самораспаковывающегося архива (в этом случае для извлечения данных из архива не нужен сам архиватор).

Приведем пример выгоды использования архиваторов при передаче данных по сети. Размер текстового документа, содержащего параграф, который вы сейчас читаете, - 31 Кб. Если этот документ заархивировать с помощью WinRar, то размер архивного файла составит всего 6 Кб. Как говорится, выгода налицо.

Пользоваться программами-архиваторами очень просто. Чтобы создать архив, нужно сначала выбрать файлы, которые необходимо в него включить, затем установить необходимые параметры (способ архивации, формат архива, размер тома, если архив многотомный), и, наконец, отдать команду СОЗДАТЬ АРХИВ. Похожим образом происходит обратное действие - извлечение файлов из архива (распаковка архива). Во-первых, нужно выбрать файлы, извлекаемые из архива, во-вторых, определить, куда должны быть помещены эти файлы, и, наконец, отдать команду ИЗВЛЕЧЬ ФАЙЛЫ ИЗ АРХИВА. Подробнее с работой программ-архиваторов вы познакомитесь на практических занятиях.

Коротко о главном

Сжатие информации производится с помощью специальных программ-архиваторов.

Чаще всего в алгоритмах сжатия используются два метода: использование кода переменной длины и использование коэффициента повторения группы символов.

Вопросы и задания

1. В чем различие кодов постоянной и переменной длины?
2. Какими возможностями обладают программы-архиваторы?
3. Какова причина широкого применения программ-архиваторов?
4. Знаете ли вы другие программы-архиваторы, кроме перечисленных в этом параграфе?

И. Семакин, Л. Залогова, С. Русаков, Л. Шестакова, Информатика, 9 класс
Отослано читателями из интернет-сайтов

Открытый урок информатики, школьный план , рефераты информатики , всё школьнику для выполнения домашнего задания, скачать информатику 9 класс

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

Если у вас есть исправления или предложения к данному уроку,

Блок А

Постоянные затраты

Переменные затраты

Анализируя выпускаемую продукцию, основное внимание следует уделить анализу её себестоимости. Себестоимость - это стоимостная оценка используемых в процессе производства продукции (работ, услуг) природных ресурсов, сырья, материалов, топлива, энергии, основных фондов, трудовых ресурсов и других затрат на ее производство и реализацию. Под определением себестоимости продукции понимается исчислении затрат, приходящихся на ед. продукции. Выпуск продукции можно считать оправданным если выручка от продажи продукции, закроет все затраты, имеющиеся на предприятии. А если же нет, то выпуск продукции является убыточным. Т.е. выпуск будет оправданным при достижении на предприятии объема выпуска и реализации, соответствующего точке нулевой прибыли. ТНП это тот объем продаж начиная с которого предприятие получает прибыль.

Также, в соответствии с критерием оптимальности структуры выпуска по Парето выпуск будет эффективным, если он будет одновременно максимизировать полезность покупателей и не будет выходить за пределы имеющихся ресурсов (т.е. будет лежать на кривой производственных возможностей). Структура выпуска эффективна, если произ-ли и потреб-ли одновременно находятся в состоянии равновесия.

В чем отличие бухгалтерской прибыли предприятия от полученного им маржинального дохода за это же время?

Маржинальный доход исчисляется в виде разности между выручкой от реализации продукции (без НДС и акцизов) и переменными расходами. Другими словами,МД- это сумма постоянных расходов и прибыли от продаж. МД должен покрывать постоянные расходы предприятия и обеспечить ему прибыль от реализации продукции, работ, услуг. Этот показатель также называют суммой покрытия.

МД = Выручка от продаж – переменные затраты

МД= Постоянные затраты + Прибыль от продаж

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

Бухгалтерская прибыль = Совокупный доход предприятия- Бухгалтерские (Явные) издержки

(Таким образом, бухгалтерская прибыль меньше маржинального дохода на сумму явных постоянных издержек.)

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

Большую роль в обосновании управленческих решений играет маржинальный (предельный) анализ, методика которого базируется на изучении соотношения между тремя группами важнейших экономических показателей «издержки - объем производства (реализации) продукции - прибыль» и прогнозировании критической и оптимальной величины каждого из этих показателей при заданном значении других. Основной категорией маржинального анализа является маржинальный доход. Маржинальный доход (прибыль) - это разность между выручкой от реализации (без учета НДС и акцизов) и переменными затратами. На изменение маржинального дохода могу влиять (вместе или по отдельности) два фактора – увеличение (уменьшение) выручки и себестоимости. Важным фактором, влияющим на доходность отдельных объектов маржинальной прибыли, является величина и структура неполной себестоимости. От величины неполной себестоимости напрямую зависит величина маржинального дохода (прибыли). Преобладание в структуре неполной себестоимости переменных затрат указывает на тот факт, что для достижения безубыточности данного объекта маржинального дохода не требуется значительного объема продаж. Преобладание в структуре неполной себестоимости прямых постоянных затрат указывает на необходимость увеличения объема продаж для их возмещения.

Блок Б

В чем различие между сокращенной себестоимостью продукции предприятия в директ-косте и ее полной себестоимостью в бухгалтерском учете?

Сокращенная себестоимость промышленной продукции в директ-косте учитывается и планируется только в части переменных затрат. Постоянные расходы собираются на отдельном счете и с заданной периодичностью списываются непосредственно на дебет счета финансовых результатов, например «Прибыли и убытки». По переменным расходам оцениваются также остатки ГП на складах на начало и конец года и НЗП. Полная себестоимость в бухгалтерском учете предполагает включение в себестоимость постоянных и переменных расходов.

Варианты расчета себестоимости взаимооказываемых работ соответствующих трансфертных цен.

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

Где R ni – сумма первичных затрат мест; q i – объем услуг, предоставленных подразделению; n – место затрат i -му подразделению (i = 1, ... n ); k i , k j – коэффициенты распределения затрат j -го места издержек.

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

Где К – коэффициент распределения; R пм – затраты первичных мест; Q пм – объем услуг, потребленных в сумме всеми подразделениями основного производства предприятия.

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

Где R fix , R var – постоянные и переменные расходы, распределенные предыдущим центром затрат; Q пм – объем первичных услуг, переданных следующему подразделению предприятия.

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

Блок С

1. От чего зависит и как измеряется загрузка производственных мощностей предприятия?

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

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

Как правило, ПМ не используются полностью в виду влияния следующих ограничивающих факторов: уровень спроса на производимую продукцию, объем доступных материальных ресурсов (материалы, сырье, топливо), необходимых для производства, ограниченная возможность использования других мощностей предприятия, влияющая на максимально возможный уровень производства в рамках одного цикла и др.

2. Какие расходы зависят от степени загрузки производственных мощностей предприятия ?

Производственные мощности или возможности предприятия - не однородная, а гомогенная величина, состоящая из производственных мощностей отдельных подразделений (цехов, участков) предприятия. В силу разных, в том числе объективных, причин эти мощности не полностью сопряжены друг с другом, например, из-за разной производительности станков, машин и другого оборудования. Отсюда ясно, что затраты материальных и трудовых ресурсов должны учитываться исходя из определенного уровня использования производственных мощностей, как правило, меньшего, чем 100%. Недоиспользованные мощности означают неиспользованные возможности увеличения производства и снижения себестоимости продукции. Отсюда следует, что уровень загрузки ПМ влияет на размер переменных затрат.

3. Что представляет собой размер общей суммы расходов предприятия?

Размер общей суммы расходов предприятия – валовые издержки предприятия (?), представляющие собой совокупность постоянных, не изменяющихся, издержек и переменных издержек, зависящих от объема производимой и реализуемой продукции.

Плюсы

Система калькуляции по нормативным затратам позволяет существенно сократить объем учетной работы;

Обеспечивает твердую основу для выявления существенных отклонений при сопоставлении затрат;

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

Нормативные затраты служат лучшим критерием для оценки фактических затрат;

Обеспечивает пользователей информацией об ожидаемых затратах на производство и продажу продукции;

Позволяет установить цены на основе заранее определенной себестоимости единицы продукции;

Позволяет составить отчет о доходах и расходах с выявлением отклонений от норм и причин их возникновения.

Минусы

Много внимания фокусируется на стоимости и производительности труда;

Не обеспечивает предприятие достаточной информацией для поиска путей усовершенствования его деятельности;

Охватывает далеко не все аспекты повышения эффективности производства;

Применяется для периодически повторяемых затрат;

Успешность применения зависит от состава и качества нормативной базы;

Невозможность установить нормы по отдельным видам затрат.

Блок Д

Блок А

В чем различие между постоянными и переменными расходами предприятия?

Критерием разделения затрат на постоянные и переменные является их зависимость от объема производства.

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

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

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

Переменные затраты возрастают или уменьшаются в абсолютной сумме в зависимости от изменения объема производства и делятся на пропорциональную и непропорциональную части.

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

Непропорциональные затраты могут быть прогрессирующими (т.е. возрастающими быстрее, чем объем производства) и дегрессирующими (если величины их прироста меньше, чем изменение количества продукции)

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

В восьмиразрядной таблице символьной кодировки (например, ASCII) каждый символ кодируется восемью битами и, следовательно, занимает в памяти 1 байт. В разделе 1.3 нашего учебника рассказывалось о том, что частота встречаемости разных букв (знаков) в тексте разная. Там же было показано, что информационный вес символов тем больше, чем меньше его частота встре­чаемости. С этим обстоятельством и связана идея сжа­тия текста в компьютерной памяти: отказаться от коди­рования всех символов кодами одинаковой длины. Сим­волы с меньшим информационным весом, т.е. часто встречающиеся, кодировать более коротким кодом по сравнению с реже встречающимися символами. При таком подходе можно существенно сократить объем общего кода текста и, соответственно, места, занимае­мого им в памяти компьютера.

Такой подход известен давно. Он используется в ши­роко известной азбуке Морзе, несколько кодов которой приведены в табл. 3.1, где "точка" кодируется нулем, а "тире" - единицей.

Таблица 3.1

Буква

Как видно из этого примера и табл. 3.1, чаще встре­чающиеся буквы имеют более короткий код.

В отличие от кодов равной длины, которые использу­ются в стандарте ASCII, в этом случае возникает про­блема разделения между кодами отдельных букв. В аз­буке Морзе эта проблема решается с помощью "паузы" (пробела), которая, по сути, является третьим симво­лом алфавита Морзе, т.е. алфавит Морзе не двух-, а трех-символьный.

А как быть с компьютерной кодировкой, где исполь­зуется двоичный алфавит? Одним из простейших, но весьма эффективных способов построения кодов разной длины, не требующих специального разделителя, явля­ется алгоритм Д.Хаффмена (D.A. Huffman, 1952 г.). С помощью этого алгоритма строится двоичное дерево, которое позволяет однозначно декодировать двоичный код, состоящий из символьных кодов различной длины. Двоичным называется дерево, из каждой вершины ко­торого выходят две ветви. На рис. 3.2 приведен при­мер такого дерева, постро­енного для алфавита англий­ского языка с учетом часто­ты встречаемости его букв. Полученные, таким обра­зом, коды можно свести в таблицу.

Таблица 3.2

Буква	Код Хаффмена

С помощью табл. 3.2 легко кодировать текст. Так, например, строка из 29 знаков

WENEEDMOR ESNOWFORBE TTERSKIING преобразуется в код: 011101 100 1100 100 100 110110001111101011100 ОНО 1100 1110 011101 01001 1110 1011 011100 100 001001 100 10110110 110100011 1010 1010 1100 00001, который при размещении его в памяти побайтно при­мет вид:

01110110 01100100 10011011 00011111 01011100 01101100 11100111 01010011 11010110 1110010000100110 01011011 01101000 11101010 10110000 001

Таким образом, текст, занимающий в кодировке ASCII 29 байт, в кодировке Хаффмена займет только 16 байт.

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

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

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

Коротко о главном

Сжатием информации называют такое ее преобразо­вание, которое ведет к сокращению объема занимаемой памяти при сохранении закодированного содержания.

Идея способа сжатия текста: длина кода символа уменьшается с уменьшением его информационного веса, т.е. с увеличением частоты встречаемости в тексте.

Алгоритм сжатия по Хаффмену представляется в виде двоичного дерева.

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

Вопросы и задания

В чем различие кодов постоянной и переменной длины?

За счет чего коды переменной длины позволяют "сжимать" текст?

Закодируйте с помощью ASCII-кодов и кодов Хафф­мена следующий текст: HAPPYNEWYEAR. Подсчитай­те в обоих случаях требуемый объем памяти.

4. Раскодируйте с помощью двоичного дерева (см.рисунок) следующий код:

11110111 10111100 00011100 00101100 10010011 01110100 11001111 11101101 001100

Двоичное дерево алфавита английского языка, используемое для кодирования методом Хаффмена