ДЗ по Дискретной математике 2
.docx
Міністерство освіти і науки України
Національний авіаційний Університет
Кафедра прикладної інформатики
Домашня робота №2
з дисципліни «Дискретна математика»
Виконав: студент ТП-113
Односумов М.С.
Київ 2016
Скоромовка:
“Павло і Пилипко Поливали липки. Виросли липки У Павла і Пилипка.”
Завдання:
-
Переробити будь-яку українську скоромовку в її закодований варіант використовуючи різні алгоритми і методи.
-
Перевести скоромовку в побітовий варіант для використання її у перших двох методах.
-
Зробити таблиці довжин кодів для перших двох методів і розрахувати ентропію і середню довжину.
-
Порівняти ефективність методу Хафмана і Шенона-Фано.
-
Закодувати скоромовку використовуючи алгоритми Леннеля-Зіва.
Метод Хаффмана.
|
Xi |
P(Xi) |
Кодова комбінація |
Li |
|
X1 (П) |
5/61 |
10000 |
5 |
|
X2 (В) |
1/61 |
1010000 |
7 |
|
X3 (У) |
1/61 |
1010001 |
7 |
|
X4 (а) |
5/61 |
10001 |
5 |
|
X5 (в) |
3/61 |
11100 |
5 |
|
X7 (л) |
9/61 |
1001 |
4 |
|
X7 (о) |
4/61 |
10101 |
5 |
|
X8 (і) |
2/61 |
101001 |
6 |
|
X9 (и) |
12/61 |
110 |
3 |
|
X10 (п) |
4/61 |
11101 |
5 |
|
X11 (р) |
1/61 |
1011100 |
7 |
|
X12 (к) |
4/61 |
10110 |
5 |
|
X13 (с) |
1/61 |
1011100 |
7 |
|
X14 (_) |
7/61 |
1111 |
4 |
|
X15 (.) |
2/61 |
101111 |
6 |
Метод Шеннона-Фано.
|
Xi |
P(Xi) |
Кодова комбінація |
Li |
|
X1 (П) |
5/61 |
100 |
3 |
|
X2 (В) |
1/61 |
111100 |
6 |
|
X3 (У) |
1/61 |
111101 |
6 |
|
X4 (а) |
5/61 |
1010 |
4 |
|
X5 (в) |
3/61 |
11011 |
5 |
|
X7 (л) |
9/61 |
010 |
3 |
|
X7 (о) |
4/61 |
1011 |
4 |
|
X8 (і) |
2/61 |
11100 |
5 |
|
X9 (и) |
12/61 |
00 |
2 |
|
X10 (п) |
4/61 |
1100 |
4 |
|
X11 (р) |
1/61 |
111110 |
6 |
|
X12 (к) |
4/61 |
11010 |
5 |
|
X13 (с) |
1/61 |
111111 |
6 |
|
X14 (_) |
7/61 |
011 |
3 |
|
X15 (.) |
2/61 |
11101 |
5 |
Ентропія – міра невизначеності, непрогнозованости ситуації.
Середня довжина бітової комбінації – сумма множини числа бітів усіх комбінацій та вірогідності появи цих символів.
H = -(12/61)*(log2 of (12/61))-(9/61)*(log2 of (9/61))-(7/61)*(log2 of (7/61))-(2*(5/61)*(log2 of (5/61)))-(3*(4/61)*(log2 of(4/61)))-(3/61)*(log2 of (3/61))-(2*(2/61)*(log2 of (2/61)))-(4*(1/61)*(log2 of (1/61))) =0.712+2.592= 3.304
Розрахуємо середні довжини для різних методів.
Середня довжина для методу Хаффмана:
lсер=5*5/61+7*1/61+7*1/61+6*5/61+5*3/61+4*9/61+5*4/61+6*2/61+3*12/61+5*4/61+7*1/61+5*4/61+7*1/61+4*7/61+6*2/61 = 4.623
Середня довжина для методу Шеннона-Фано:
lсер=3*5/61+6*1/61+6*1/61+4*5/61+5*3/61+3*9/61+4*4/61+5*2/61+2*12/61+4*4/61+6*1/61+5*4/61+6*1/61+3*7/61+5*2/61 = 3.573
Як можно побачити – ефективніше буде метод Шеннона-Фано.
Ентропія цієї скоромовки дуже близька до середньої довжини, що значить, що код дуже оптимізований.
Кодування скоромовки алгоритма Лемпеля-Зіва.
-
Про алгоритм:
LZ77 і LZ78, алгори́тм Ле́мпеля — Зі́ва (англ. Lempel–Ziv algorithm) — універсальний алгоритм стискування даних без втрат, створений у 1977—1978 роках Авраамом Лемпелем і Яковом Зівом. Алгоритм розроблений так, щоб його можна було швидко реалізувати, але він не обов'язково є оптимальним, оскільки не проводить жодного аналізу вхідних даних. 1984 року Террі Велчем опублікована покращена реалізація алгоритму LZ78 — алгоритм Лемпеля — Зіва — Велча
-
Історія виникнення:
Більше тридцяти років алгоритм стиснення Хаффмана і його варіанти залишалися найпопулярнішими методами. Проте 1977 року ізраїльскі дослідники Авраам Лемпель і Яків Зів запропонували абсолютно інший підхід до цієї проблеми, висунувши ідею формування «словника» загальних послідовностей даних.
При цьому стиснення даних здійснюється за рахунок заміни записів відповідними кодами із словника. Існують два алгоритми стиснення даних — LZ77 і LZ78.
-
Кодування скоромовки алгоритмом LZ77
Приклад: ПАВЛО_І_ПИЛИПКО_ПОЛИВАЛИ_ЛИПКИ._ВИРОСЛИ_ЛИПКИ_У_ПАВЛА_І_ПИЛИПКА.
Після використання алгоритму LZ77:
ПАВЛО_І_ПИЛИПКО_ПОЛИВАЛИ_(-15,4)И.(-15,6)_У_(-48,4)А(-48,9)А.
-
Кодування скоромовки алгоритмом LZ78
Приклад: ПАВЛО_І_ПИЛИПКО_ПОЛИВАЛИ_ЛИПКИ._ВИРОСЛИ_ЛИПКИ_У_ПАВЛА_І_ПИЛИПКА.
Після використання алгоритму LZ78:
(0,П)(0,А)(0,В)(0,Л)(0,О)(0,_)(0,І)(6,П)(0,И)(4,И)(1,К)(5,_)(1,О)(10,В)(2,Л)(9,_)(10,П)(О,К)(9,.)(6,В)(9,Р)(5,С)(10,_)(17,К)(16,У)(8,А)(3,Л)(2,_)(7,_)(1,И)(24,А)(0,.)
Таблиця символів для алгоритму LZ78
|
Позиція словника |
Вхідні данні |
Код |
|
1 |
П |
(0,П) |
|
2 |
А |
(0,А) |
|
3 |
В |
(0,В) |
|
4 |
Л |
(0,Л) |
|
5 |
О |
(0,О) |
|
6 |
_ |
(0,_) |
|
7 |
І |
(0,І) |
|
8 |
_П |
(6,П) |
|
9 |
И |
(0,И) |
|
10 |
ЛИ |
(4,И) |
|
11 |
ПК |
(1,К) |
|
12 |
О_ |
(5,_) |
|
13 |
ПО |
(1,О) |
|
14 |
ЛИВ |
(10,В) |
|
15 |
АЛ |
(2,Л) |
|
16 |
И_ |
(9,_) |
|
17 |
ЛИП |
(10,П) |
|
18 |
К |
(0,К) |
|
19 |
И. |
(9,.) |
|
20 |
_В |
(6,В) |
|
21 |
ИР |
(9,Р) |
|
22 |
ОС |
(5,С) |
|
23 |
ЛИ_ |
(10,_) |
|
24 |
ЛИПК |
(17,К) |
|
25 |
И_У |
(16,У) |
|
26 |
_ПА |
(8,А) |
|
27 |
ВЛ |
(3,Л) |
|
28 |
А_ |
(2,_) |
|
29 |
І_ |
(7,_) |
|
30 |
ПИ |
(1,И) |
|
31 |
ЛИПКА |
(24,А) |
|
32 |
. |
(0,.) |