Материал: 6 - Кодирование и сжатие

Задание 7

Тема. Кодирование и сжатие данных методами без потерь

Оглавление

Задание 1 Исследование алгоритмов сжатиянапримерах 1

Вариантызадания1 2

Задание 2 Разработать программы сжатия и восстановления текста методамиХаффмана и Шеннона – Фано 1

Требования к выполнениюзадания 2 5

Требуется выполнить два задания

Задание 1 Исследование алгоритмов сжатия на примерах

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

2. Описать процесс восстановления сжатого текста.

3. Сформировать отчет, включив задание, вариант задания, результаты выполнения заданияварианта.

Задание 2 Разработать программы сжатия и восстановлениятекста методами Хаффмана и Шеннона –Фано.

1. Реализовать и отладитьпрограммы.

2. Сформировать отчет по разработке каждой программы в соответствиис требованиями.

   • По методу Шеннона-Фано привести: постановку задачи, описать алгоритм формирования префиксного дерева и алгоритм кодирования, декодирования, код и результаты тестирования. Рассчитать коэффициентсжатия.Сравнитьсрезультатсжатиявашималгоритмомс результатом людогоархиватора.

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

Варианты задания 1

Требования к выполнению задания 2

1. Разработать алгоритм и реализовать программу сжатия текста алгоритмом Шеннона – Фано. Разработать алгоритм и программу восстановления сжатого текста. Выполнить тестирование программы на текстовом файле. Определить процентсжатия.

2. Провести кодирование(сжатие) исходной строки символов «Фамилия Имя Отчество» с использованием алгоритма Хаффмана. Исходная строка символов, таким образом, определяет индивидуальный вариант задания для каждого студента.

Для выполнения работы необходимо выполнить следующие действия:

1. Построить таблицу частот встречаемости символов в исходной строке символов для чего сформировать алфавит исходной строки и посчитать количество вхождений (частот) символов и их вероятности появления, например, для строкипупкин василий кирилловичтакая таблица будет иметьвид:

Таблица частот

(скобки < > обозначают пробел в исходной строке)

2. Отсортировать алфавит в порядке убывания частот появления символов по аналогии как показанониже

Таблица отсортированных частот

3. Построить дерево кодирования Хаффмана, в данном примереоно имеетвид:

Рисунок Дерево кодирования Хаффмана

4. Упорядочить построенное дерево слева-направо (принеобходимости).

5. Присвоить ветвямкоды.

6. Определить кодысимволов:

7. Рисунок Упорядоченное дерево кодированияХаффмана

8. Провести кодирование исходной строки по аналогии спримером:

9. Рассчитать коэффициенты сжатия относительно кодировки ASCII и относительно равномерногокода.

10. Рассчитать среднюю длину полученного кода и егодисперсию.

11. По результатам выполненной работы сделать выводы и сформировать отчет.

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

Приложение 1 Примеры оформления задач задания 1 и описание алгоритмов

1. Для метода Шеннон –Фано

Пример оформления таблицы. Закодировать фразу «Тише, мыши, тише, кот на крыше», используя метод Шеннона–Фено.

Таблица 1

Незакодированная фраза – 30*8 бит = 240 бит. Закодированная фраза –106 бит.

2. Для метода Лемпеля –ЗиваLZ77

   1. для сжатия двоичного кода

Где LZ – сжатый текст (в данном примере в связи с небольшим размером исходного текста размер текста не уменьшился)

R отмечает шаги кодирования, после которых происходит переход на представление кодов А увеличенным числом разрядов R. Так, на первом шаге вводится код 10 для комбинации 00, и поэтому на следующих двух шагах R =

2, после третьего шага R = 3, после седьмого шага R = 4, т.е. в общем случае R

= K после шага 2^K-1–1.

1. Для метода Лемпеля –Зива LZ7

LZ77используетскользящеепосообщениюокно.Неиспользуетсловарь. Допустим, на текущей итерации окно зафиксировано. С правой стороны окна наращиваем подстроку, пока она есть в строке <скользящее окно + наращиваемая строка> и начинается в скользящем окне. Назовем наращиваемую строку буфером. После наращивания алгоритм выдаеткод

<offset,len,char> состоящий из трех элементов:

• смещение в окне -offset;

• длина буфера -len;

• последний символ буфера -char.

В конце итерации алгоритм сдвигает окно на длину равную длине буфера+1.

Пример 1 сabababababm

В рамочке представлено смещающееся окно, которое определяет буфер.

Результат сжатия

с(0,0)a(0,0)(2,2)b(0,0)m(2,5)

Описание алгоритма LZ78

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

используемую в сравнениях фразу. Если в конце алгоритма мы не находим символ, нарушивший совпадения, то тогда мы выдаем код в виде (индекс строки в словаре без последнего символа, последний символ).

Пример ababaaabb

Код 0a0b1b1a3b Пример 2. сabababababm