Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лабораторная работа - Метод кодирования по Хаффману - файл Андреева Ольга Олеговна.docx


Лабораторная работа - Метод кодирования по Хаффману
скачать (51.5 kb.)

Доступные файлы (4):

Андреева Ольга Олеговна.docx27kb.15.03.2009 12:14скачать
Андреева Ольга Олеговна.txt1kb.25.02.2009 22:47скачать
Принцип кодирования по Хаффману.doc186kb.12.02.2007 01:33скачать
Таблица.doc69kb.26.02.2009 16:03скачать

Загрузка...

Андреева Ольга Олеговна.docx

Реклама MarketGid:
Загрузка...
Лабораторная работа №1.

Принцип кодирования по Хаффману

Задание

Закодируйте по алгоритму Хаффмана строку с вашим именем, отчеством, фамилией, датой и местом рождения (например, «Иванова Наталья Николаевна, 1 января 1990 года, город Тверь»).

При кодировании не округляйте частоты менее, чем четыре знака после запятой – сокращение точности понижает эффективность кодирования.

Подсчитайте коэффициент сжатия.

Наберите эту же строку в редакторе «Блокнот» и сохраните текст в txt-формате (количество байт в файле должно в точности соответствовать числу знаков – букв, цифр и служебных символов – в строке.

Примените к файлу любой архиватор и сравните его степень сжатия с алгоритмом Хаффмана.

Ход работы

Андреева Ольга Олеговна, 24 февраля 1990 года, город Брянск

  1. Чтобы снизить размеры файла при записи, определим вначале частоту встречаемости отдельных букв:

Буква

Частота

А

6

Н

3

Д

3

Р

4

Е

4

В

3

О

6

Л

3

Ь

1

Г

4

2

1

4

1

Ф

1

Я

2

1

1

9

2

0

1

Б

1

С

1

К

1

Пробел

8

,

2



№ пп

Символ

Повтор

Частота

1

Пробел

8

0,1356

2

А

6

0,1017

3

О

6

0,1017

4

Р

4

0,0678

5

Е

4

0,0678

6

Г

4

0,0678

7

Н

3

0,0508

8

Д

3

0,0508

9

В

3

0,0508

10

Л

3

0,0508

11

Я

2

0,0339

12

9

2

0,0339

13

,

2

0,0339

14

Ь

1

0,0169

15

2

1

0,0169

16

4

1

0,0169

17

Ф

1

0,0169

18

1

1

0,0169

19

0

1

0,0169

20

Б

1

0,0169

21

С

1

0,0169

22

К

1

0,0169

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

Шаг 1

 




Шаг 2

 




Шаг 3

 

1

0,1356




1

0,1356




1

0,1356

2

0,1017




2

0,1017




2

0,1017

3

0,1017




3

0,1017




3

0,1017

4

0,0678




4

0,0678




4

0,0678

5

0,0678




5

0,0678




5

0,0678

6

0,0678




6

0,0678




6

0,0678

7

0,0508




7

0,0508




11, 12

0,0678

8

0,0508




8

0,0508




13, 15, 16

0,0678

9

0,0508




9

0,0508




17, 18, 19, 20

0,0678

10

0,0508




10

0,0508




7

0,0508

11

0,0339




14, 21, 22

0,0508




8

0,0508

12

0,0339




11

0,0339




9

0,0508

13

0,0339




12

0,0339




10

0,0508

14

0,0169




13

0,0339




14, 21, 22

0,0508

15, 16

0,0339




15, 16

0,0339










17, 18

0,0339




17, 18

0,0339










19, 20

0,0339




19, 20

0,0339










21, 22

0,0339





















Шаг 4

 




Шаг 5

 




Шаг 6

 

1

0,1356




1

0,1356




1

0,1356

2

0,1017




7, 17, 18, 19, 20

0,1186




5, 6

0,1356

3

0,1017




2

0,1017




11, 12, 13, 15, 16

0,1356

8, 9

0,1016




3

0,1017




7, 17, 18, 19, 20

0,1186

10, 14, 21, 22

0,1016




8, 9

0,1016




2

0,1017

4

0,0678




10, 14, 21, 22

0,1016




3

0,1017

5

0,0678




4

0,0678




8, 9

0,1016

6

0,0678




5

0,0678




10, 14, 21, 22

0,1016

11, 12

0,0678




6

0,0678




4

0,0678

13, 15, 16

0,0678




11, 12

0,0678










17, 18, 19, 20

0,0678




13, 15, 16

0,0678










7

0,0508











































Шаг 7

 




Шаг 8

 




Шаг 9

 

4, 10, 14, 21, 22

0,1694




3, 8, 9

0,2033




2, 7, 17, 18, 19, 20

0,2203

1

0,1356




4, 10, 14, 21, 22

0,1694




3, 8, 9

0,2033

5, 6

0,1356




1

0,1356




4, 10, 14, 21, 22

0,1694

11, 12, 13, 15, 16

0,1356




5, 6

0,1356




1

0,1356

7, 17, 18, 19, 20

0,1186




11, 12, 13, 15, 16

0,1356




5, 6

0,1356

2

0,1017




7, 17, 18, 19, 20

0,1186




11, 12, 13, 15, 16

0,1356

3

0,1017




2

0,1017










8, 9

0,1016











































Шаг 10

 




Шаг 11

 




Шаг 12

 

5, 6, 11, 12, 13, 15, 16

0,2712




1, 4, 10, 14, 21, 22

0,305




2, 3, 7, 8, 9, 17, 18, 19, 20

0,4236

2, 7, 17, 18, 19, 20

0,2203




5, 6, 11, 12, 13, 15, 16

0,2712




1, 4, 10, 14, 21, 22

0,305

3, 8, 9

0,2033




2, 7, 17, 18, 19, 20

0,2203




5, 6, 11, 12, 13, 15, 16

0,2712

4, 10, 14, 21, 22

0,1694




3, 8, 9

0,2033










1

0,1356











































Шаг 13

 



















1, 4, 5, 6, 10, 11, 12, 13, 14, 15, 16, 21, 22

0,5762



















2, 3, 7, 8, 9, 17, 18, 19, 20

0,4236




















  1. Теперь, пользуясь таблицами в обратной последовательности, построим дерево кодирования. (дерево идет отдельным файлом «таблица» в папке)



  1. 

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

№ пп

Символ

Двоичный код

1

Пробел

110

2

А

001

3

О

010

4

Р

1110

5

Е

1000

6

Г

1001

7

Н

0110

8

Д

0000

9

В

0001

10

Л

11111

11

Я

10100

12

9

10101

13

,

10110

14

Ь

111100

15

2

101110

16

4

101111

17

Ф

011110

18

1

011111

19

0

011100

20

Б

011101

21

С

1111010

22

К

1111011



  1. Подсчитаем полученную степень сжатия, умножая длину кода на сумму символов, кодируемых кодом данной длины:

3*20+4*21+5*9+6*7+7*2=245 бит = 30,625 байт

Коэффициент сжатия = 59/30,625 = 1,93

Размер файла в «Блокноте» = 59 байт, после сжатия WinRAR = 170 байт.


Скачать файл (51.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации