Главная
страница 1
Алексей Жоров

гр. 14-502

Обязательное задание к практической работе №1

«Алгоритмы сжатия двоичной информации»

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

Исходная информационная последовательность: 13 10 9 8 7 8 8 10 9 8 7 9 9 8 7 10 9 5




Символ

Статистика появления

Двоичное представление

13

1

0001

10

3

0010

9

5

0011

8

5

0100

7

3

0101

5

1

0110

Объем исходного текста: 18 (символов) х 4 (бита) = 72 бита













Символ

Частость

Код

13

1

0000

5

1

0001

10

3

001

9

3

10

8

5

11

7

5

01

Объем сжатого текста: 1х4 + 1х4 + 3х3 + 5х2 + 5х2 +3х2 =43 бита

Ксж = 43/72 = 1,67

Алгоритм Лемпеля-Зива LZ77

Сжатие


Словарь 16 бит

Буфер 7 бит

Код

Двоичный код

















































13

10

9

8

7

8

8

0, 0, ’13’

0000 000 0001














































13

10

9

8

7

8

8

10

0, 0, ’10’

0000 000 0010











































13

10

9

8

7

8

8

10

9

0, 0, ‘9’

0000 000 0011








































13

10

9

8

7

8

8

10

9

8

0, 0, ‘8’

0000 000 0100





































13

10

9

8

7

8

8

10

9

8

7

0, 0, ‘7’

0000 000 0101


































13

10

9

8

7

8

8

10

9

8

7

9

3, 1, ‘8’

0011 001 0100




























13

10

9

8

7

8

8

10

9

8

7

9

9

8

1, 4, ‘9’

0100 100 0011













13

10

9

8

7

8

8

10

9

8

7

9

9

8

7

10

9

5




2, 3, '10’

0010 011 0010

13

10

9

8

7

8

8

10

9

8

7

9

9

8

7

10

9

5
















2, 1, ‘5’

0010 001 0110

9

8

7

8

8

10

9

8

7

9

9

8

7

10

9

5




























Распаковка

Двоичный код

Код для распаковки

Словарь 16 бит

Восстановленный текст



0000 000 0001

0, 0, ’13’














































13

13

0000 000 0010

0, 0, ’10’











































13

10

10

0000 000 0011

0, 0, ‘9’








































13

10

9

9

0000 000 0100

0, 0, ‘8’





































13

10

9

8

8

0000 000 0101

0, 0, ‘7’


































13

10

9

8

7

7

0011 010 0100

3, 1, ‘8’




























13

10

9

8

7

8

8

8 8

0010 100 0011

1, 4, ‘9’













13

10

9

8

7

8

8

10

9

8

7

9

10 9 8 7 9

0010 011 0010

2, 3, '10’

13

10

9

8

7

8

8

10

9

8

7

9

9

8

7

10

9 8 7 10

0010 001 0110

2, 1, ‘5’

9

8

7

8

8

10

9

8

7

9

9

8

7

10

9

5

9 5

Объем исходного текста: 18 (символов) х 4 (бита) = 72 бита

Объем сжатого текста: 9 (кодов) х 11 (бит)= 99 бит



Ксж= 99/ 72 = 1,38

Алгоритм Лемпеля - Зива - Сторера - Шимански LZSS
Сжатие

Словарь 16 бит

Буфер 7 бит

Код

Двоичный код

















































13

10

9

8

7

8

8

0, ’13’

0 0001














































13

10

9

8

7

8

8

10

0, ’10’

0 0010











































13

10

9

8

7

8

8

10

9

0, ‘9’

0 0011








































13

10

9

8

7

8

8

10

9

8

0, ‘8’

0 0100





































13

10

9

8

7

8

8

10

9

8

7

0, ‘7’

0 0101


































13

10

9

8

7

8

8

10

9

8

7

9

0, ‘8’

0 0100































13

10

9

8

7

8

8

10

9

8

7

9

9

0, ‘8’

0 0100




























13

10

9

8

7

8

8

10

9

8

7

9

9

8

1, 1, 4

1 0001 100
















13

10

9

8

7

8

8

10

9

8

7

9

9

8

7

10

9

5

0, ‘9’

0 0011













13

10

9

8

7

8

8

10

9

8

7

9

9

8

7

10

9

5




1, 2, 3

1 0010 011




13

10

9

8

7

8

8

10

9

8

7

9

9

8

7

10

9

5













1, 1, 2

1 0001 010

10

9

8

7

8

8

10

9

8

7

9

9

8

7

10

9

5



















0, ‘5’

0 0110

9

8

7

8

8

10

9

8

7

9

9

8

7

10

9

5




























Распаковка



Двоичный код

Код для распаковки

Словарь 16 бит

Восстановленный текст



0 0001

0, ’13’














































13

13

0 0010

0, ’10’











































13

10

10

0 0011

0, ‘9’








































13

10

9

9

0 0100

0, ‘8’





































13

10

9

8

8

0 0101

0, ‘7’


































13

10

9

8

7

7

0 0100

0, ‘8’































13

10

9

8

7

8

8

0 0100

0, ‘8’




























13

10

9

8

7

8

8

8

1 0001 100

1, 1, 4
















13

10

9

8

7

8

8

10

9

8

7

10 9 8 7

0 0011

0, ‘9’













13

10

9

8

7

8

8

10

9

8

7

9

9

1 0010 011

1, 2, 3




13

10

9

8

7

8

8

10

9

8

7

9

9

8

7

9 8 7

1 0001 010

1, 1, 2

10

9

8

7

8

8

10

9

8

7

9

9

8

7

10

9

10 9

0 0110

0, ‘5’

9

8

7

8

8

10

9

8

7

9

9

8

7

10

9

5

5

Объем исходного текста: 18 (символов) х 4 бита = 72 бита

Объем сжатого текста: 9 (кодов) х 5 бит + 3 (кодов) х 8 бит = 69 бит



Ксж= 69/ 72 = 0,96


Смотрите также:
Алексей Жоров гр. 14-502 Обязательное задание к практической работе №1 «Алгоритмы сжатия двоичной информации»
206.71kb.
1 стр.
Магистерские программы
18.28kb.
1 стр.
Л. Н. Никитин Алгоритмы сжатия изображений и стандарты цифрового кодирования
1086.9kb.
5 стр.
Rtl-модели блоков сжатия звуковых сигналов
21.85kb.
1 стр.
Методические указания к курсовой работе по курсу «Теория информационных процессов и систем»
179.04kb.
1 стр.
Алексей Ананьевич Ананьев Супы
1527.56kb.
14 стр.
Литература 19 Словарные методы сжатия данных 19 Идея словарных методов 19 Классические алгоритмы Зива-Лемпела 20
2114.32kb.
15 стр.
"Зима покой природы. Жизнь растений и животных" Урок проводился в 1 классе «Б» педагогом Купцовой Н. Г
64.37kb.
1 стр.
Разработка и оценка алгоритмов деятельности экипажа в типовой боевой ситуации «дальний воздушный бой» в работе рассматриваются вопросы разработки и оценки алгоритмы деятельности экипажа в типовой боевой ситуации «дальний воздушный бой»
26.9kb.
1 стр.
Урок русского языка в 8 классе «Способы и приемы сжатия текста»
59.35kb.
1 стр.
Рудневский Алексей Максимович
16.95kb.
1 стр.
Критическая секция
604.6kb.
5 стр.