Всё для Учёбы — студенческий файлообменник
1 монета
doc

Студенческий документ № 000032 из ДГТУ (бывш. РИСХМ)

Лабораторная работа № 4

"Метод Шеннона - Фано"

Цель работы: Изучение метода эффективного кодирования Шеннона - Фано.

Форма отчета: Выполнение зачетного задания.

Задание Провести кодирование ансамбля из девяти знаков методом Шеннона - Фано.

Таблица 1 Результаты первого кодирования методом Шеннона - Фано

Знак (буква, символ) Вероятность появления знака Кодовая последовательность

Длина qi

pi*qi Номер разбиения 1 2 3 4 x1 0,35 1 1 - - 2 0,7 x2 0,13 1 0 - - 2 0,26 x3 0,1 0 1 1 - 3 0,3 x4 0,09 0 1 0 1 4 0,36 x5 0,08 0 1 0 0 4 0,32 x6 0,07 0 0 1 1 4 0,28 x7 0,07 0 0 1 0 4 0,28 x8 0,06 0 0 0 1 4 0,24 x9 0,05 0 0 0 1 4 0,2 В данном коде буквы имеющие наибольшую вероятность появления в тексте, кодируются наиболее короткими кодовыми последовательностями, а более длинные комбинации присваиваются редким буквам. Если i-я буква, вероятность которой Рi, получает кодовую комбинацию длины qi, то средняя длина комбинации qcp равна

, где m- количество символов в первичном алфавите.

Для кода представленного в таблице 1 qcp= 0,7+0,26+0,3+0,36+ 0,32+0,28+0,28+0,24+0,2= 2,94.

Таблица 1 Результаты второг кодирования методом Шеннона - Фано

Знак (буква, символ) Вероятность появления знака Кодовая последовательность

Длина qi

pi*qi Номер разбиения 1 2 3 4 x1 0,35 1 1 - - 2 0,7 x2 0,13 1 0 1 - 3 0,39 x3 0,1 1 0 0 - 3 0,3 x4 0,09 0 1 1 - 3 0,27 x5 0,08 0 1 0 - 3 0,24 x6 0,07 0 0 1 1 4 0,28 x7 0,07 0 0 1 0 4 0,28 x8 0,06 0 0 0 1 4 0,24 x9 0,05 0 0 0 0 4 0,2 Для кода представленного в таблице 2 qcp= 0,7+0,39+0,3+0,27+ 0,24+0,28+0,28+0,24+0,2= 2,90.

Контрольные вопросы

1. Цель эффективного кодирования ?

2. Средняя длина комбинации ?

3. Длина кодовой кмбинации.

Лабораторная работа № 5

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

Цель работы: Изучение алгоритма Хаффмана.

Форма отчета: Выполнение зачетного задания.

Динамический алгоритм Хаффмана

1. Необходимо посчитать количество появлений каждого символа в исходном тексте.

2. Строится таблица. Элементы таблицы образованы набором символов и числом - суммарным количеством вхождений данных символов в тексте. Назовем указанное число - весом узла.

3. Строится бинарное дерево. Листьями дерева будут узлы, образованные одним символом:

4. Циклически необходимо выполнять следующие действия:

- определить среди узлов, не имеющих родителя, два узла, имеющих в сумме наименьший вес;

- создать новый узел, его потомками будут два выбранных узла. Его весом будет сумма весов выбранных улов. Его набор символов будет образован в результате объединения наборов символов выбранных узлов.

Пример . Закодировать алгоритмом Хоффмана строку "исходящее сообщение".

Решение. Определяем количество появлений каждого символа в строке.

и с х о д я щ е ' ' б н 2 2 1 3 1 1 2 3 1 1 1

Создаем новые узлы на основе букв с единичным вхождением в строку.

и с х о д я щ е ' ' б н 2 2 1 3 1 1 2 3 1 1 1

Добавляем еще один узел с буквами входящими в строку дважды.

и с х о д я щ е ' ' б н 2 2 1 3 1 1 2 3 1 1 1

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

и с х о д я щ е ' ' б н 2 2 1 3 1 1 2 3 1 1 1

и с х о д я щ е ' ' б н 2 2 1 3 1 1 2 3 1 1 1

Теперь для каждого узла, имеющего потомков, пометим дуги, идущие вниз, на одной дуге напишем 0, на другой 1.

и с х о д я щ е ' ' б н 2 2 1 3 1 1 2 3 1 1 1

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

Символ Код символа o 111 е 110 и 001 с 000 щ 101 х 0111 д 0110 я 0101 ' ' 0100 б 1001 н 1000

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

В закодированном виде фраза "исходящее сообщение" будет выглядеть так:

и с х о д я щ е е ' ' с о о б щ е н и е 001 000 0111 111 0110 0101 101 110 110 0100 000 111 111 1001 101 110 1000 001 110

Таким образом двоичная последовательность будет иметь вид:

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

1) Смотрим, какое значение у текущего бита, и идем в низ по дереву по дуге, на которой указано такое же значение.

2) Переходим к следующему биту.

3) Если сейчас находимся в листе дерева: читаем символ находящийся в этом листе и записываем его в результат декодирования, переходим снова в корень дерева.

Контрольные вопросы

1. Определение узлов дерева.

2. Бинарное дерево

3. Итеративность алгоритма.

Показать полностью…
Рекомендуемые документы в приложении