для фразы МАМА МЫЛА РАМУ
Как поэтапно построить двоичное дерево?
Как определить коды символов?
Как сравнить длину равномерного и неравномерного двоичного кода?
Как закодировать неравномерным двоичным кодом фразу МАМА МЫЛА РАМУ?
Для кодирования и декодирования фразы или сообщения сначала необходимо построить двоичное дерево по которому определяются коды символов.
Двоичное дерево строится по таблице вероятностей распределения символов или по таблице частот распределения символов.
Составляем таблицу частот, для этого надо просто посчитать сколько раз каждый символ встречается в тексе сообщения: МАМА_МЫЛА_РАМУ
- М встречается 4 раза
- А встречается 4 раза
- _ встречается 2 раза
- Ы встречается 1 раз
- Л встречается 1 раз
- Р встречается 1 раз
- У встречается 1 раза
Каждый символ является листом (конечным узлом) двоичного дерева
добавим каждый лист в список нераспределенных узлов назначив ему вес, равный его частоте и запишем в порядке возрастания весов:
попарно объединяем узлы с наименьшим весом в один родительский узел, вес которого равен сумме весов этих узлов и добавляем в список нераспределенных узлов вместо объединенных узлов в соответствии с весом нового узла.
Левому узлу ставим ребро, добавляющее к к коду символа 0, а правому ребро, добавляющее к коду символа 1, поскольку дерево строится снизу код образуется с конца, сначала добавляется последний символ,потом предпоследний и так далее.
После объединения узлов "Ы" и "Л" в узел 1 список нераспределенных узлов примет вид:
на шаге 2 объединения узлов "Р" и "У" в узел 2 получим
на шаге 3 объединяем узлы 1 и 2 в узел 3 и получаем
на шаге 4 объединяем узлы "_" и 3 в узел 4
Теперь на шаге 6 объединяем узлы "М" и "А" в узел 5
На шаге 7 объединяем узлы 4 и 5 в узел 6 и дерево готово
проходя по дереву от корня до каждого листа получаем коды символов:
"У" код равен 0101
"Р" код равен 0100
"Л" код равен 0111
"Ы" код равен 0110
Чем чаще встречается символ, тем короче его код, это позволяет увеличить сжатие, по сравнению с равномерным кодированием.
Каждый код не является началом другого кода т.е. выполняется условие Фано.
Длина закодированного сообщения равна сумме произведений длины кода на частоту символа в сообщении:
1*4+1*4+1*4+1*4+2*2+ 4*2+4*2=36 бит
Длина кодированного сообщения 36 бит:
Длина исходного сообщения 14 символов или 14 байт (112 бит) в ASCII:
при использовании сжатия по алгоритму Хаффмана коэффициэнт сжатия равен 112/36=3.11
сообщение содержит 7 различных символов. Длина кода одного символа при равна log₂(7)=3 бит
длина кодированного текста равна 14*3=42 бит
коэффициэнт сжатия равен по сравнению с несжатым текстом 112/36=2.66
коэффициэнт сжатия по сравнению с равномерно сжатым текстом равен 42/36=1.17
Идёт приём заявок
Подать заявку 
Для учеников 1-11 классов и дошкольников
1. Информационный объем сообщения: Люблю грозу в начале мая» — равен:
2. Одно из свойств информации – это:
3. Применение двоичной системы счисления в вычислительной технике обусловлено:
А) размерами компьютера;
В) особенностями программного обеспечения;
С) спецификой изготовления и работы электронных схем;
Д) особенностями устройства процессора.
4. Предмет информатики – это:
А) язык программирования;
В) устройство робота;
С) способы накопления, хранения, обработки, передачи информации
Д) информированность общества.
5. Перед посадкой самолета бортинженер поручил стюардессе сделать объявление пассажирам: «Сейчас в городе идет дождь, температура воздуха два градуса». Кем в данном случае является стюардесса?
А) Источником информации;
В) получателем информации;
С) передатчиком информации;
1. Информационный объем сообщения: «Очень хочу учиться» — равен:
2. Актуальность, объективность, полнота это свойства:
4. Супруга царя Салтана родила Гвидона и хочет обрадовать мужа. В этой ситуации Салтан – это:
А) источник информации;
В) получатель информации;
5. Актуальность, объективность, полнота – это свойства:
1. Информационный объем сообщения: «Мама мыла раму» — равен:
2. Одно из свойств информации – это:
3. Ясность, актуальность, измеримость – это:
А) фундаментальные понятия информатики;
В) свойства информации;
С) свойства алгоритма;
Д) свойства языка программирования
4. Одно из фундаментальных понятий информатики – это:
D) Norton Commander .
5. Каждый дверной ключ имеет свои «бороздки», с помощью которых открывается замок. Чем в данном случае является замок?
А) Источником информации;
С) каналом связи;
D) получателем информации.
1. Число бит в тексте: «Мама, мама» — равен:
2. Одно из свойств информации — это:
3. Тройками из нулей и единиц можно закодировать…различных символов.
4. Поиск, сбор, хранение, преобразование, использование информации – это предмет изучения:
5. Капитан спрашивает матроса: «Работает ли маяк?» Матрос отвечает: «То загорается, то погаснет!» Чем является маяк в этой ситуации?
А) Получателем информации;
В) источником информации;
С) каналом связи;
1. Одна строка из 60 символов в памяти занимает:
2. Одно из свойств информации – это:
3. Различными восьмерками из нулей и единиц можно закодировать:
А) только алфавит из русских прописных и строчных букв;
В) только английский алфавит;
С) 256 различных символов;
Д) только знаки арифметических операций
4. Перед посадкой самолета бортинженер поручил стюардессе сделать объявление пассажирам: «Сейчас в городе идет дождь, температура воздуха два градуса». Кем в данном случае является бортинженер?
А) Каналом связи;
В) получателем информации;
С) источником информации;
5. Информация в ЭВМ кодируется:
А) в двоичных кодах;
В) в десятичных кодах;
Д) в машинных словах
Эталон ответов к тесту по теме «Информация. Виды работ с информацией»
- Макеева Елена СергеевнаНаписать 7014 17.10.2015
Номер материала: ДВ-072009
- 17.10.2015 38133
- 17.10.2015 1271
- 17.10.2015 610
- 17.10.2015 761
- 17.10.2015 1674
- 17.10.2015 622
- 17.10.2015 6051
Не нашли то что искали?
Вам будут интересны эти курсы:
Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение редакции может не совпадать с точкой зрения авторов.
Ответственность за разрешение любых спорных моментов, касающихся самих материалов и их содержания, берут на себя пользователи, разместившие материал на сайте. Однако редакция сайта готова оказать всяческую поддержку в решении любых вопросов связанных с работой и содержанием сайта. Если Вы заметили, что на данном сайте незаконно используются материалы, сообщите об этом администрации сайта через форму обратной связи.
Пусть имеется следующая таблица префиксных кодов:
Требуется декодировать сообщение:
Декодирование производится циклическим повторением следующих действий:
(a) отрезать от текущего сообщения крайний левый символ, присоединить справа к рабочему кодовому слову;
(b) сравнить рабочее кодовое слово с кодовой таблицей; если совпадения нет, перейти к (а);
(c) декодировать рабочее кодовое слово, очистить его;
(d) проверить, имеются ли еще знаки в сообщении; если «да», перейти к (а).
Применение данного алгоритма дает:
Доведя процедуру до конца, получим сообщение: «мама мыла раму».
Таким образом, использование префиксного кодирования позволяет делать сообщение более коротким, поскольку нет необходимости передавать разделители знаков. Однако условие Фано не устанавливает способа формирования префиксного кода и, в частности, наилучшего из возможных. Мы рассмотрим две схемы построения префиксных кодов.
Префиксный код Шеннона-Фано
Данный вариант кодирования был предложен в 1948-1949 гг. независимо Р. Фано и К. Шенноном и по этой причине назван по их именам. Рассмотрим схему на следующем примере: пусть имеется первичный алфавит А, состоящий из шести знаков а1 . а6 с вероятностями появления в сообщении, соответственно, 0,3; 0,2; 0,2; 0,15; 0,1; 0,05. Расположим эти знаки в таблице в порядке убывания вероятностей (см. табл. 3.2). Разделим знаки на две группы таким образом, чтобы суммы вероятностей в каждой из них были бы приблизительно равными. В нашем примере в первую группу попадут a1 и а2 с суммой вероятностей 0,5 — им присвоим первый знак кода "0". Сумма вероятностей для остальных четырех знаков также 0,5; у них первый знак кода будет "1". Продолжим деление каждой из групп на подгруппы по этой же схеме, т.е. так, чтобы суммы вероятностей на каждом шаге в соседних подгруппах были бы возможно более близкими. В результате получаем:
Из процедуры построения кодов легко видеть, что они удовлетворяют условию Фано и, следовательно, код является префиксным. Средняя длина кода равна:
I1 ( A ) = 2,390 бит. Подставляя указанные значения в (3.5), получаем избыточность кода Q(A,2) = 0,0249, т.е. около 2,5%. Однако, данный код нельзя считать оптимальным, поскольку вероятности появления 0 и 1 неодинаковы (0,35 и 0,65, соответственно). Применение изложенной схемы построения к русскому алфавиту дает избыточность кода 0,0147.
Префиксный код Хаффмана
Способ оптимального префиксного двоичного кодирования был предложен Д. Хаффманом. Построение кодов Хаффмана мы рассмотрим на том же примере. Создадим новый вспомогательный алфавит A1, объединив два знака с наименьшими вероятностями (а5 и а6) и заменив их одним знаком (например, а (1) ); вероятность нового знака будет равна сумме вероятностей тех, что в него вошли, т.е. 0,15; остальные знаки исходного алфавита включим в новый без изменений; общее число знаков в новом алфавите, очевидно, будет на 1 меньше, чем в исходном. Аналогичным образом продолжим создавать новые алфавиты, пока в последнем не останется два знака; ясно, что количество таких шагов будет равно N — 2, где N — число знаков исходного алфавита (в нашем случае N = 6, следовательно, необходимо построить 4 вспомогательных алфавита). В промежуточных алфавитах каждый раз будем переупорядочивать знаки по убыванию вероятностей. Всю процедуру построения представим в виде таблицы:
Теперь в обратном направлении проведем процедуру кодирования. Двум знакам последнего алфавита присвоим коды 0 и 1 (которому какой — роли не играет; условимся, что верхний знак будет иметь код 0, а нижний — 1). В нашем примере знак а1 (4) алфавита A (4) , имеющий вероятность 0,6, получит код 0, а a2 (4) с вероятностью 0,4 — код 1. В алфавите А (3) знак a1 (3) получает от a2 (4) его вероятность 0,4 и код (1); коды знаков a2 (3) и a3 (3) , происходящие от знака a1 (4) с вероятностью 0,6, будут уже двузначным: их первой цифрой станет код их «родителя» (т.е. 0), а вторая цифра — как условились — у верхнего 0, у нижнего — 1; таким образом, a2 (3) будет иметь код 00, а a3 (3) — код 01. Полностью процедура кодирования представлена в таблице, приведенной на с.70.
Из процедуры построения кодов вновь видно, что они удовлетворяют условию Фано и, следовательно, не требуют разделителя. Средняя длина кода, как и в предыдущем примере оказывается:
К(А,2) = 0,3 ∙ 2 + 0,2 ∙ 2 + 0,2 ∙ 2 +0,15 ∙ 3 + 0,1 ∙ 4 + 0,05 ∙ 4 = 2,45.
Избыточность снова оказывается равной Q(A, 2) = 0,0249, однако, вероятности 0 и 1 сблизились (0,47 и 0,53, соответственно). Более высокая эффективность кодов Хаффмана по сравнению с кодами Шеннона-Фано становится очевидной, если сравнить избыточности кодов для какого-либо естественного языка. Применение описанного метода для букв русского алфавита порождает коды, представленные в табл. 3.2. (для удобства сопоставления они приведены в формате табл. 3.1).
Средняя длина кода оказывается равной К(r,2) = 4,395; избыточность кода Q(r,2) = 0,0090, т.е. не превышает 1 %, что заметно меньше избыточности кода Шеннона-Фано (см. выше).
Код Хаффмана важен в теоретическом отношении, поскольку можно доказать, что он является самым экономичным из всех возможных, т.е. ни для какого метода алфавитного кодирования длина кода не может оказаться меньше, чем код Хаффмана (см. [49, с.209-211]).
Таким образом, можно заключить, что существует способ построения оптимального неравномерного алфавитного кода. Не следует думать, что он представляет число теоретический интерес. Метод Хаффмана и его модификация — метод адаптивного кодирования (динамическое кодирование Хаффмана) — нашли широчайшее применение в программах-архиваторах, программах резервного копирования файлов и дисков, в системах сжатия информации в модемах и факсах.