Мета лекції. вивчити основні види та алгоритми стиснення даних і навчитися вирішувати завдання стиснення даних за методом Хаффмана і за допомогою кодових дерев.
Основоположником науки про стиснення інформації прийнято вважати Клода Шеннона. Його теорема про оптимальне кодування показує, до чого потрібно прагнути при кодуванні інформації і наскільки та чи інша інформація при цьому стиснеться. Крім того, їм були проведені досліди за емпіричною оцінкою надмірності англійського тексту. Шенон пропонував людям вгадувати наступну букву і оцінював вірогідність правильного вгадування. На основі ряду дослідів він прийшов до висновку, що кількість інформації в англійському тексті коливається в межах 0,6 - 1,3 біта на символ. Незважаючи на те, що результати досліджень Шеннона були по-справжньому затребувані лише десятиліття потому, важко переоцінити їх значення.
Стиснення даних - це процес, що забезпечує зменшення обсягу даних шляхом скорочення їх надмірності. Стиснення даних пов'язано з компактним розташуванням порцій даних стандартного розміру. Стиснення даних можна розділити на два основних типи:
Алгоритм стиснення даних (алгоритм архівації) - це алгоритм. який усуває надмірність записи даних.
Введемо ряд визначень, які будуть використовуватися далі в викладі матеріалу.
Алфавіт коду - безліч всіх символів вхідного потоку. При стисненні англомовних текстів зазвичай використовують безліч з 128 ASCII кодів. При стисненні зображень безліч значень пікселя може містити 2, 16, 256 або іншу кількість елементів.
Кодовий символ - найменша одиниця даних, що підлягає стисненню. Зазвичай символ - це 1 байт. але він може бути бітом, тріть, або чим-небудь ще.
Кодове слово - це послідовність кодових символів з алфавіту коду. Якщо все слова мають однакову довжину (число символів), то такий код називається рівномірним (фіксованої довжини). а якщо ж допускаються слова різної довжини, то - нерівномірним (змінної довжини).
Код - повне безліч слів.
Токен - одиниця даних, що записується в стислий потік деяким алгоритмом стиснення. Токен складається з декількох полів фіксованою або змінною довжини.
Фраза - фрагмент даних, що поміщається в словник для подальшого використання в стисненні.
Кодування - процес стиснення даних.
Декодування - зворотний кодування процес, при якому здійснюється відновлення даних.
Ставлення стиснення - одна з найбільш часто використовуваних величин для позначення ефективності методу стиснення.
Значення 0,6 означає, що дані займають 60% від початкового об'єму. Значення більше 1 означають, що вихідний потік більше вхідного (негативне стиск, або розширення).
Коефіцієнт стиснення - величина, зворотна відношенню стиснення.
Значення більше 1 позначають стиснення, а значення менше 1 - розширення.
Середня довжина кодового слова - це величина, яка обчислюється як зважена можливостями сума довжин всіх кодових слів.
де - імовірності кодових слів;
Існують два основних способи проведення стиснення.
Статистичні методи - методи стиснення, які присвоюють коди змінної довжини символам вхідного потоку, причому більш короткі коди присвоюються символам або групам символів, які мають велику ймовірність появи у вхідному потоці. Кращі статистичні методи застосовують кодування Хаффмана.
Словникове стиснення - це методи стиснення, що зберігають фрагменти даних в "словнику" (деяка структура даних). Якщо рядок нових даних, що надходять на вхід, ідентична будь-якому фрагменту, вже знаходиться в словнику, в вихідний потік поміщається покажчик на цей фрагмент. Кращі словникові методи застосовують метод Зива-Лемпела.
Розглянемо кілька відомих алгоритмів стиснення даних більш докладно.
метод Хаффмана
Цей алгоритм кодування інформації був запропонований Д.А. Хаффманом в 1952 році. Хаффмановское кодування (стиснення) - це широко використовуваний метод стиснення, привласнює символам алфавіту коди змінної довжини, грунтуючись на можливостях появи цих символів.
Ідея алгоритму полягає в наступному: знаючи ймовірності входження символів у вихідний текст, можна описати процедуру побудови кодів змінної довжини, що складаються з цілого кількості бітів. Символам з більшою ймовірністю присвоюються коротші коди. Таким чином, в цьому методі при стисненні даних кожному символу присвоюється оптимальний префіксний код. заснований на ймовірності його появи в тексті.
Префіксний код - це код, в якому ніяке кодове слово не є префіксом будь-якого іншого кодового слова. Ці коди мають змінну довжину.
Оптимальний префіксний код - це префіксний код. має мінімальну середню довжину.
Алгоритм Хаффмана можна розділити на два етапи.
- Визначення ймовірності появи символів в початковому тексті.
Спочатку необхідно прочитати вихідний текст повністю і підрахувати ймовірності появи символів в ньому (іноді підраховують, скільки разів зустрічається кожен символ). Якщо при цьому враховуються всі 256 символів, то не буде різниці в стисканні текстового або файлу іншого формату.
Далі знаходяться два символу a і b з найменшими ймовірностями появи і замінюються одним фіктивним символом x. який має ймовірність появи, що дорівнює сумі ймовірностей появи символів a і b. Потім, використовуючи цю процедуру рекурсивно, знаходиться оптимальний префіксний код для меншого безлічі символів (де символи a і b замінені одним символом x). Код для вихідного безлічі символів виходить з кодів заміщають символів шляхом додавання 0 або 1 перед кодом заміщає символу, і ці два нових коду приймаються як коди замінних символів. Наприклад, код символу a буде відповідати коду x з доданим нулем перед цим кодом, а для символу b перед кодом символу x буде додана одиниця.
Коди Хаффмана мають унікальний префікс. що і дозволяє однозначно їх декодувати, незважаючи на їх зміну довжину.
Приклад 1. Програмна реалізація методу Хаффмана.
Алгоритм Хаффмана універсальний, його можна застосовувати для стиснення даних будь-яких типів, але він малоефективний для файлів малих розмірів (за рахунок необхідності збереження словника). В даний час даний метод практично не застосовується в чистому вигляді, зазвичай використовується як один з етапів стиснення в більш складних схемах. Це єдиний алгоритм. який не збільшує розмір вихідних даних в гіршому випадку (якщо не брати до уваги необхідність зберігати таблицю перекодування разом з файлом).