Міносвіти Росії
Федеральне державне бюджетне освітня установа вищої професійної освіти
Московський державний технічний університет радіотехніки, електроніки та автоматики
МГТУ МІРЕА
Факультет інформаційних технологій (ІТ)
Кафедра інформатики та інформаційних систем (ІВС)
ЗВІТ по практичній роботі
з дисципліни
«Теорія інформаційних процесів і систем»
на тему
«Методи стиснення інформації»
Виконав студент групи ЗТ - 1-10
Шерстнева А.А
Прийняв старший викладач
Миронов А.А
Практична робота виконана «16» Квітень 2014р.
Москва, 2 014
Методи стиску інформації
Методи стиснення даних мають досить довгу історію розвитку, яка почалася задовго до появи першого комп'ютера. У цій статті буде проведена спроба дати короткий огляд основних теорій, концепцій ідей та їх реалізацій, що не претендує, однак, на абсолютну повноту. Більш докладні відомості можна знайти, наприклад, в Кричевський Р.Е. [1989], Рябко Б.Я. [1980], Witten I.H. [1987], Rissanen J. [1981], Huffman DA [1 952], Gallager RG [1978], Knuth D.E. [1985], Vitter J.S. [1986] та ін.
Стиснення інформації - проблема, що має досить давню історію, набагато давнішу, ніж історія розвитку обчислювальної техніки, яка (історія) зазвичай йшла паралельно з історією розвитку проблеми кодування і шифровки інформації. Всі алгоритми стиснення оперують вхідним потоком інформації, мінімальною одиницею якої є біт, а максимальної - кілька біт, байт або декілька байт. Метою процесу стиснення, як правило, є отримання більш компактного вихідного потоку інформаційних одиниць з деякого спочатку некомпактного вхідного потоку за допомогою деякого їх перетворення. Основними технічними характеристиками процесів стиснення і результатів їх роботи є:
ступінь стиснення (compress rating) або відношення (ratio) обсягів вихідного і результуючого потоків;
швидкість стиснення - час, що витрачається на стиск деякого обсягу інформації вхідного потоку, до отримання з нього еквівалентного вихідного потоку;
якість стиснення - величина, що показує на скільки сильно упакований вихідний потік, за допомогою застосування до нього повторного стиснення з цього ж або іншому алгоритму.
Існує кілька різних підходів до проблеми стиснення інформації. Одні мають вельми складну теоретичну математичну базу, інші засновані на властивостях інформаційного потоку і алгоритмічно досить прості. Будь-який спосіб підхід і алгоритм, що реалізує стиснення або компресію даних, призначений для зниження обсягу вихідного потоку інформації в бітах за допомогою її оборотного або необоротного перетворення.
Я розгляну методи стиснення без втрати інформації. До таких методів належать:
· Алгоритм Хафмана
· Арифметичне кодування
· Контекстне кодування (PPM - Prediction by Partial Matching)
· Алгоритм Зива-Лемпеля (-Welch)
· Алгоритм Барроуза-Веллера
Повне число алгоритмів стиснення даних без втрат інформації істотно більше десяти.
Пропускна спроможність каналів зв'язку більш дорогий ресурс, ніж дисковий простір, з цієї причини стиснення даних до або під час їх передачі ще більш актуально. Тут метою стиснення інформації є економія пропускної здатності і в кінцевому підсумку її збільшення. Всі відомі алгоритми стиснення зводяться до шифрування вхідної інформації, а приймаюча сторона виконує дешифровку прийнятих даних.
Існують методи, які припускають деякі втрати вихідних даних, інші алгоритми дозволяють перетворити інформацію без втрат. Стиснення з втратами використовується при передачі звукової або графічної інформації, при цьому враховується недосконалість органів слуху і зору, які не помічають деякого погіршення якості, пов'язаного з цими втратами. Більш детально ці методи розглянуті в розділі Перетворення, кодування й передача інформації .
Стиснення інформації без втрат здійснюється статистичними кодуванням або на основі попередньо створеного словника. Статистичні алгоритми (напр., Схема кодування Хафмана) привласнюють кожному вхідному символу певний код. При цьому найбільш часто використовуваному символу присвоюється найбільш короткий код, а найбільш рідкісного - довший. Роз...
