Алгоритм Хаффмана. Алгоритм Шеннона-Фано. Алгоритм KWE.
В основі алгоритму Хафмана лежить ідея кодування бітовими групами. Спочатку проводиться частотний аналіз вхідної послідовності даних, тобто встановлюється частота входження кожного символу, що зустрічається у ній. Після цього символи сортуються по спаданню частоти входження.
Основна ідея полягає в наступному: чим частіше зустрічається символ, тим меншою кількістю біт він кодується. Результат кодування зводиться в словник, що необхідний для декодування.
Алгоритм Хаффмана (на прикладі)
А – 0,35
Б – 0,15
В – 0,4
Г – 0,1
Розміщуємо в порядку зменшення ймовірностей
В – 0,4 0
А – 0,35 1 0
Б – 0,15 1 1 0
Г – 0,1 1 1 1
Алгоритм Шеннона-Фано
- розмістити повідомлення в порядку зменшення їх ймовірностей
- список розбивається на рівноймовірні розділи (2 для двійкового коду, 3 – для тріскового…)
- призначити 0 першій частині списку, 1 – другій
- процес виконувати до тих пір, поки не залишиться не пронумерованих розділів
Алгоритм KWE – це алгоритм символів, що формує словник ключових слів.
В основі алгоритму стиснення за ключовими словами покладено принцип кодування лексичних одиниць групами байт фіксованої довжини. Прикладом лексичної одиниці може бути звичайне слово. На практиці, в ролі лексичних одиниць вибираються послідовності символів, що повторюються, які кодуються ланцюжком символів (кодом) меншої довжини. Результат кодування зводиться в таблицю, утворюючи так званий словник.
20. Алгоритм RLE. Алгоритм LZW. Пригнічення нулів
В основі алгоритму RLE лежить ідея виявлення послідовностей даних, що повторюються, та заміни цих послідовностей більш простою структурою, в якій вказується код даних та коефіцієнт повторення.
Алгоритм RLE (перемінна довжина рядка) на прикладі
0, 0, 0, 0, 12, 12, 0, 100, 100, 100
Символ к-ть повторень
0 4
12 2
0 1
100 3
0,4,12,2,0,1,100,3
Ефективність – 0,8
Алгоритм LZW (Лемпела-Зіва-Велча) для стиснення текстової та графічної інформації (зменшення на 20-25%). При цьому стиснення даних здійснюється за рахунок заміни записів відповідними кодами із словника. Словником в даному алгоритмі є потенційно нескінченний список фраз. Алгоритм починає роботу з майже пустого словника, що містить тільки один закодований рядок, так званий NULL-рядок. Коли зчитується черговий символ вхідної послідовності даних, він додається до поточного рядка. Процес продовжується доти, поки поточний рядок відповідає якій-небудь фразі з словника.
Пригнічення нулів (кодування джерел з пам’яттю) – один найбільш повторюваний символ замінюється лексемою (символ, що представляє сам себе і кількість повторів), інші символи передаються без змін. Зазвичай в якості такого символу використовується 0.
21.Системи числення позиційні та непозиційні
Сукупність прийомів та правил найменування й позначення чисел називається системою числення. Звичайною для нас і загальноприйнятою є позиційна десяткова система числення. Як умовні знаки для запису чисел вживаються цифри.
Система числення, в якій значення кожної цифри в довільному місці послідовності цифр, яка означає запис числа, не змінюється, називається непозиційною. Система числення, в якій значення кожної цифри залежить від місця в послідовності цифр у записі числа, називається позиційною.
15. Поняття стиснення інформації
Стиснення – це процес та метод кодування інформації, що слугує для переведення її у стан, що потребує менше місця для зберігання інформації.
Будь-яка інформація має певний ступінь надлишковості: 1) з так званим зберіганням інформації (кодування надлишковості негативне); 2) зі сприйняттям інформації (надлишковість є позитивною)
Стисненню підлягають файли, папки та диски.
1) Стиснення файлів відбувається для зменшення розмірів з метою передачі носіями малої ємності
2) Стиснення папок відбувається для архівації даних перед тривалим зберіганням
3) Стиснення дисків відбувається для підвищення ефективності використання їх робочого простору
3 способи стиснення: 1)зміна змісту (необоротне, призводить до втрати інформації); 2)зміна структури даних; 3) зміна змісту і структури.
22. Двійкова, шістнадцяткова та вісімкова системи числення.
Найпоширенішою для подання чисел у пам'яті комп'ютера є двійкова система числення. Для зображення чисел у цій системі необхідно дві цифри: 0 і 1, тобто достатньо двох стійких станів фізичних елементів. Ця система є близькою до оптимальної за економічністю.
Вісімко́ва систе́ма чи́слення — позиційна цілочисельна система числення з основою 8. Для представлення чисел в ній використовуються цифри 0 до 7.
Вісімкова система часто використовується в галузях, пов'язаних з цифровими пристроями. Характеризується легким переводом вісімкових чисел у двійкові і назад, шляхом заміни вісімкових чисел на триплети двійкових. Раніше широко використовувалася в програмуванні і взагалі комп'ютерної документації, проте в наш час майже повністю витіснена шістнадцятковою. У вісімковій системі вказуються права доступу для команди chmod в Unix-подібних операційних системах.
Шістнадцяткова систе́ма чи́слення — це позиційна система числення, кожне число в якій записується за допомогою 16-ти символів. Цю систему часто називають також Hex (початкові літери англ. hexadecimal — шіснадцятковий). Спочатку планувалось вживати латинське sexa замість hexa, проте це слово сприймалось неоднозначно. Для запису чисел в цій системі окрім 10 арабських цифр (від 0 до 9) використовують 6 літер латинської абетки: A, B, C, D, E, F.
23. Переведення чисел у різні системи числення
Для переведення чисел із системи числення з основою p в систему числення з основою q, використовуючи арифметику нової системи числення з основою q, потрібно записати коефіцієнти розкладу, основи степенів і показники степенів у системі з основою q і виконати всі дії в цій самій системі.
Для переведення чисел із системи числення з основою p в систему числення з основою q з використанням арифметики старої системи числення з основою p потрібно:
для переведення цілої частини:
послідовно число, записане в системі основою p ділити на основу нової системи числення, виділяючи остачі. Останні записані у зворотному порядку, будуть утворювати число в новій системі числення;
для переведення дробової частини:
послідовно дробову частину множити на основу нової системи числення, виділяючи цілі частини, які й будуть утворювати запис дробової частини числа в новій системі числення.
24. Арифметичні дії з числами у двійковій системі числення
У двійковій системі: коли число в розряді сягає двох - розряд обнуляється і одиниця додається до старшого розряду. Тобто: 1+1=10. Зверніть увагу, "10" у цьому записі - двійкове число, у десятковій системі це число записується як "2". А десяткове 9+1=10 у двійковій системі буде виглядати так: 1001+1=1010 (після додавання одиниці число в останньому розряді дорівнює двом, тож розряд обнуляється і одиниця додається до передостаннього(старшого) розряду).
26. Основи алгебри логіки
Алгебра логіки – це розділ математичної логіки, що вивчає вислови, які розглядаються з боку їх логічних значень (істинності або помилковості) і логічні операції над ними.
Змінні булевої алгебри і логіки приймають значення 1 або 0.
Базовими елементами алгебри логіки є висловлювання. Висловлювання будуються над множиною {B, , , , 0, 1}, де B — булева множина, над елементами якої визначені три математичні операції:
заперечення (унарна операція), кон'юнкція (бінарна), диз'юнкція (логічна) (бінарна),
(константи — логічний нуль 0 та логічна одиниця 1.)
Ця система застосовується для вирішення широкого спектру проблем математичної логіки та теорії множин, та особливо конструювання цифрової електроніки (початок використання алгебри логіки для синтезу перемикальних (релейних) схем був покладений в 1938 році роботами відомого американського вченого Клода Шеннона).