Ім'я файлу: Лаб. 5.docx
Розширення: docx
Розмір: 30кб.
Дата: 19.04.2023
скачати
Пов'язані файли:
БЖД.docx
Реф6.docx
Реферат.pdf

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

Словарні методи кодування

Мета роботи: вивчити роботу алгоритму кодування Лемпела-Зіва.

Завдання 1

Використовуючи алгоритм Лемпела-Зіва, закодувала текстове повідомлення: «Префіксною множиною двійкових послідовностей S називається скінченна множина двійкових послідовностей, таких, що ні одна послідовність у цій множині не є префіксом, або початком, ніякої іншої послідовності в S.»

Вхідна фраза
Код
Позиція словника







0

П
<0,’П’>
1

р
<0,’р’>
2

е
<0,’е’>
3

ф
<0,’ф’>
4

і
<0,’і’>
5

к
<0,’к’>
6

с
<0,’с’>
7

н
<0,’н’>
8

о
<0,’о’>
9

ю
<0,’ю’>
10

_
<0,’_’>
11

м
<0,’м’>
12

но
<8,’о’>
13

Ж
<0,’ж’>
14

и
<0,’и’>
15

ною
<13,’ю’>
16

_д
<11,’д’>
17

в
<0,’в’>
18

ій
<5,’й’>
19

ко
<6,’о’>
20

ви
<18,’и’>
21

х
<0,’х’>
22

_п
<11,’п’>
23

ос
<9,’с’>
24

л
<0,’л’>
25

ід
<5,’д’>
26

ов
<9,’в’>
27

нос
<13,’с’>
28

т
<0,’т’>
29

ей
<3,’1’>
30

_S
<11,’S’>
31

_н
<11,’н’>
32

а
<0,’а’>
33

з
<0,’з’>
34

ив
<15,’в’>
35

ає
<33,’є’>
36

ть
<29,’ь’>
37

ся
<7,’я’>
38

_с
<11,’с’>
39

кі
<6,’і’>
40

нч
<8,’ч’>
41

ен
<3,’н’>
42

на
<8,’а’>
43

_м
<11,’м’>
44

нож
<13,’ж’>
45

ин
<15,’н’>
46

а_
<33,’_’>
47

д
<0,’д’>
48

ві
<18,’і’>
49

й
<0,’й’>
50

ков
<6,’в’>
51

их
<15,’х’>
52

_по
<23,’о’>
53

сл
<7,’л’>
54

ід
<5,’д’>
55

овн
<27,’н’>
56

ост
<24,’т’>
57

ей_
<30,’_’>
58

,
<0,’,’>
59

_т
<11,’т’>
60

ак
<33,’к’>
61

их,
<52,’,’>
62

_щ
<11,’щ’>
63

о_
<9,’_’>
64

ні
<8,’і’>
65

_о
<11,’о’>
66

дн
<48,’н’>
67

а_п
<47,’п’>
68

осл
<24,’л’>
69

ідо
<55,’о’>
70

вн
<18,’н’>
71

іс
<5,’с’>
72

ть_
<37,’_’>
73

у_
<у,’_’>
74

ц
<0,’ц’>
75

ій_
<19,’_’>
76

мн
<12,’н’>
77

ож
<9,’ж’>
78

ині
<46,’і’>
79

_не
<32,’е’>
80

_є
<11,’є’>
81

_пр
<23,’р’>
82

еф
<3,’ф’>
83

ік
<5,’к’>
84

со
<7,’о’>
85

м,
<12,’,’>
86

_а
<11,’а’>
87

б
<0,’б’>
88

о_п
<64,’п’>
89

оч
<9,’ч’>
90

ат
<33,’т’>
91

ком
<20,’м’>
92

,_
<59,’_’>
93

нія
<65,’я’>
94

кої
<20,’ї’>
95

_і
<11,’і’>
96

нш
<8,’ш’>
97

ої
<9,’ї’>
98

_пос
<53,’с’>
99

лі
<25,’і’>
100

до
<48,’о’>
102

вно
<71,’о’>
103

ст
<7,’т’>
104

і_
<5,’_’>
105

в_
<18,’_’>
106

S
<0,’S’>
107

.
<0,’.’>
108

Завдання 2

Оцінити ступінь стиснення повідомлення:

Символів до стиснення: 205

Символів після стиснення: 108



Висновки:

Під час виконання даної лабораторної роботи явивчив роботу алгоритму кодування Лемпела-Зіва. Та закодував власне повідомлення, ступінь стиснення якого вийшла 52.68%.

Контрольні запитання:

  1. У чому різниця між статистичними та словарними методами кодування?

Статистичні методи кодування використовують частоти виникнення символів або груп символів для стиснення даних.

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

  1. Загальна характеристика сімейства алгоритмів Лемпела-Зіва.

Загальна характеристика полягає в тому, що фрази в стискуваному тексті замінюються вказівкою на те місце, де вони у цьому тексті з’являлися раніше.

  1. Порівняти відомі методи словарного кодування.

LZ77:

- Використовує статичний словник, який передається разом з закодованим файлом.

Шукає найбільшу повторювану послідовність символів в словнику та кодує її в позиції та довжині;

- Ефективний при стисненні файлів з багато повторюваних послідовностей.

LZ78:

- Використовує динамічний словник, який змінюється під час роботи алгоритму.

- Кодує нові послідовності символів в словник збільшенням його розміру та присвоєнням нового індексу;

- Менш ефективний за LZ77 при стисненні файлів з багато повторюваних послідовностей, але ефективний при кодуванні маленьких послідовностей.

LZW:

- Використовує динамічний словник, який змінюється під час роботи алгоритму;

Кодує нові послідовності символів в словник збільшенням його розміру та присвоєнням нового індексу;

- Найбільш ефективний з усіх методів при стисненні текстових файлів, що містять багато повторюваних послідовностей.

  1. За рахунок чого відбувається зменшення об’єму повідомлення при словарному кодуванні?

За рахунок заміни повторюваних послідовностей символів на коротші кодові слова, які вказують на місце в словнику, де ця послідовність вже зустрічалась.
скачати

© Усі права захищені
написати до нас