Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2008
Тип роботи:
Курсова робота
Предмет:
Методи та засоби комп’ютерних інформаційних технологій
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
Кафедра ПЗ
Курсова робота
з курсу “ Методи і засоби комп’ютерних
інформаційних технологій ”
Стиснення інформації алгоритмом Лемпеля-Зіва
Львів – 2008
Анотація
Василів Ігор
“Стиснення інформації алгоритмом Лемпеля-Зіва”. Курсова робота – НУ “Львівська політехніка”, каф.: ПЗ, дисципліна: “Методи та засоби комп`ютерних інформаційних технологій”, 2007.
Курсова робота складається з 25 сторінок, містить 1 таблицю.
В даній курсовій роботі розроблено програму для стиснення інформації алгоритмом Лемпеля-Зіва. Під час роботи над програмою досліджено та проаналізовано сучасні алгоритми стиснення інформації без втрати даних. Проект забезпечує відкриття файлу для стиснення, збереження стисненого файлу за вказаним користувачем ім’ям та можливість розархівування файлу у вказану директорію.
Зміст
Анотація 2
Вступ 4
1. Аналітичний розділ 6
1.1. Способи стиснення інформації 6
1.2. Огляд алгоритмів стиснення інформації 7
1.3. Опис алгоритмів сімейства LZ 9
1.3.1. Алгоритм LZ77 9
1.3.2. Алгоритм LZSS 11
2. Постановка задачі та обґрунтування вибраного напряму проектування 14
3. Проектний розділ 15
3.1. Алгоритм стиснення 15
3.2. Програмна реалізація алгоритму 16
3.3. Проектування інтерфейсу 23
4. Дослідження роботи алгоритму і програми 24
4.1. Опис інтерфейсу 24
4.2. Оцінка роботи програми 26
Висновки 27
Література 28
Вступ
В наш час інформація відіграє все більшу і більшу роль в сучасному житті. Її об'єми постійно зростають і потрібні все більші носії інформації, все більш швидкі канали зв'язку для її передачі. Але в більшості випадків підвищення місткості носіїв і швидкості ліній передачі або неможливе технічно, або не виправдане економічно. Таким чином ми стикаємося з проблемою зменшення об’єму інформації не змінюючи її вмісту.
Стиснення інформації - проблема, яка має достатньо давню історію, набагато давнішу, ніж історія розвитку обчислювальної техніки, яка йшла паралельно з історією розвитку проблеми кодування і шифрування інформації. Всі алгоритми стиснення оперують вхідним потоком інформації, мінімальною одиницею якої є біт, а максимальною - декілька біт, байт або декілька байт. Метою процесу стиснення, як правило, є отримання компактнішого вихідного потоку інформаційних одиниць з деякого спочатку некомпактного вхідного потоку за допомогою деякого їх перетворення.
Значна частина інформаційних ресурсів суспільства зберігається на магнітних носіях. Але інформація на магнітних носіях може бути часткового або повністю втраченою в силу наступних причин:
фізичне псування носія в наслідок дії зовнішніх магнітних колів, старіння чи зношення магнітного покриття;
діяльність комп’ютерних вірусів
необачне знищення і т.д.
З метою забезпечення надійного збереження інформації створюють резервні копії даних. Процес створення резервних копій називають архівацією. Основний зміст архівації полягає у створенні таких резервних копій, які б займали би значно менше дискової пам’яті, ніж інформація у вихідному стані. Таким чином, сьогодні під архівацією слід розуміти процес перекодування деякої сукупності файлів з метою зменшення загального об’єму пам’яті, який вони займають. Архівацією ще називають процес стискування даних. Розроблено багать різних способів архівації. Усі вони ґрунтуються на базі різних підходів та методі, але в основі більшості з них лежить принцип заміни рівномірного двійкового коду на нерівномірний (кодоскоп).
Для архівації файлів використовують спеціальні програми, які називають архіваторами. Стиснуті файли поміщають у файл, який називають архівом. Текстові, графічні та інші файли даних можуть бути стиснені у 3-10 разів і занесені до файлу-архіву спеціальними програмами – архіваторами. Перші архіватори з’явилися ще у 1985 році.
Основними можливостями сучасних архіваторів є: занесення цілих груп файлів та підкаталогів в архів, поновлення архіву перегляд файлів в архіві, вилучення файлів з архіву, захист файлів від несанкціонованого доступу, перевірка цілісності архіву, створення багатотомних архівів, та архівів, які автоматично розкриваються. Сучасні архіватори дозволяють економити від 20 до 90% дискового простору.
Файлом, який міститься в архіві, можна скористатися лише після того, як він буде відновлений у початковому вигляді, тобто розархівований. Розархівацію виконують або ті ж самі архіватори, або окремі програми, які називають розрахіваторами. Найбільш відомими архіваторами (розархіваторами) є: RLZIP.EXE, RKUNZIP.EXE, ARI.EXE, LHARC.EXE.
При виборі конкретного типу архіватора (розархіватора) керуються декількома критеріями, найважливішими з яких є швидкість роботи архіватора та коефіцієнт стиснення даних.
Аналітичний розділ
Способи стиснення інформації
Основними технічними характеристиками процесів стиснення і результатів їх роботи є:
ступінь стиснення (compress rating) або відношення (ratio) об'ємів початкового і результуючого потоків;
швидкість стиснення - час, що витрачається на стиснення деякого об'єму інформації вхідного потоку, до отримання з нього еквівалентного вихідного потоку;
якість стиснення - величина, що показує на скільки сильно упакований вихідний потік, за допомогою застосування до нього повторного стиснення по цьому ж або іншому алгоритму.
Всі способи стиснення можна розділити на дві категорії: оборотне і необоротне стиснення. Під необоротним стисненням мають на увазі таке перетворення вхідного потоку даних, при якому вихідний потік, заснований на певному форматі інформації, представляє, з деякої точки зору, достатньо схожий по зовнішніх характеристиках на вхідний потік об'єкт, проте відрізняється від нього об'ємом. Ступінь схожості вхідного і вихідного потоків визначається ступенем відповідності деяких властивостей об'єкту (тобто стисненої і не стисненої інформації відповідно до деякого певного формату даних), що представляється даним потоком інформації. Такі підходи і алгоритми використовуються для стиснення, наприклад типи даних растрових графічних файлів з низьким ступенем повторюваності байтів в потоці. При такому підході використовується властивість структури формату графічного файлу і можливість представити графічну картинку приблизно схожу за якістю відображення (для сприйняття людським оком) декількома способами. Тому, крім ступеня або величини стиснення, в таких алгоритмах виникає поняття якості, оскільки початкове зображення в процесі стиснення змінюється, то під якістю можна розуміти ступінь відповідності початкового і результуючого зображення, оцінювана суб'єктивно, виходячи з формату інформації. Для графічних файлів така відповідність визначається візуально, хоча є і відповідні інтелектуальні алгоритми і програми. Необоротне стиснення неможливо застосовувати в областях, в яких необхідно мати точну відповідність інформаційної структури вхідного і вихідного потоків. Даний підхід реалізований в популярних форматах представлення відео і фото інформації, відомих як JPEG і GIF алгоритми і JPG і GIF формати файлів.
Оборотне стиснення завжди приводить до зниження об'єму вихідного потоку інформації без зміни його інформативності, тобто - без втрати інформаційної структури. Більше того, з вихідного потоку, за допомогою поновлюючого або декомпресуючого алгоритму, можна одержати вхідний, а процес відновлення називається декомпресією або розпаковуванням і лише після процесу розпаковування дані придатні для обробки відповідно до їх внутрішнього формату.
Огляд алгоритмів стиснення інформації
В даний час існує декілька алгоритмів стиснення без втрат, частково це відкриті алгоритми, частково комерційні алгоритми. Комерційні алгоритми не публікуються і познайомиться з ними неможливо, за виключенням ознайомлення з результатами роботи програм на базі цих алгоритмів. Відповідні програми (ZIP, ARJ, RAR, АСE і ін.) достатньо відомі і з ними можна познайомитися самостійно.
Алгоритми оборотного стиснення даних можна розділити на дві групи:
Алгоритми частотного аналізу - підрахунок частоти різних символів в даних і перетворення кодів символів з відповідності з їх частотою.
Алгоритми кореляційного аналізу - пошук кореляцій (у простому випадку точних повторів) між різними ділянками даних і заміна корелюючих даних на код(и), яка позволяє відновити дані на основі попередніх даних. У простому випадку точних повторів, кодом є посилання на початок попереднього входження цієї послідовності символів і довжина послідовності.
Крім такої класифікації можна підрозділити всі алгоритми стиснення даних на чотири наступні основні групи:
алгоритми кодування повторів;
методи вірогідності;
арифметичні методи;
"метод словників" (dictionary).
Можна відзначити наступні алгоритми оборотного стиснення даних з першої групи:
Метод Хаффмана - заміна коду рівної довжини для символів на коди нерівної довжини відповідно до частоти появи символів в даних, коди мінімальної довжини привласнюються тим, що найчастіше зустрічається символам. Якщо частоти появи символів є ступенем двійки(2n), то цей метод досягає теоретичної ентропійної межі ефективності стиснення для методів такого типу.
Метод Шеннона-Фано - схожий з методом Хаффмана, але використовує другий алгоритм генерації кодів і не завжди дає оптимальні коди (оптимальний код - код дає найбільше стиснення даних зі всіх можливих для даного типу перетворення).
Арифметичне кодування - удосконалення методу Хаффмана, який позволяє одержувати оптимальні коди для даних, де частоти появи символів не є ступенем двійки (2n). Цей метод досягає теоретичної ентропійної межі ефективності стиснення цього типу для будь-якого джерела.
Для другої групи можна назвати наступні алгоритми:
Метод Running (або RLE) - замінює ланцюжки символів, що повторюються на код символу і число повторів. Це приклад елементарного і дуже зрозумілого методу стиснення, але, на жаль, він не володіє достатньою ефективністю.
Методи Лемпеля-Зіва - це група алгоритмів стиснення об'єднана спільною ідеєю: пошук повторів фрагментів тексту в даних і заміна повторів посиланням (кодом) на перше (або попереднє) входження цього фрагмента в дані. Відрізняються один від одного методом пошуку фрагментів і методом генерації посилань (кодів).
В даний час, в різних модифікаціях і поєднаннях, двох алгоритмів - методу Хаффмана (або арифметичне кодування) і методу Лемпеля-Зіва складають основу всіх комерційних алгоритмів і програм.
Опис алгоритмів сімейства LZ
Основна ідея алгоритму Лемпеля-Зіва полягає в заміні фрагменту даних (групи байт) посиланням на попередню появу цього фрагмента. Існують два основних класи методів, названих в честь Якоба Зіва (Jakob Ziv) і Абрахама Лемпеля (Abraham Lempel), які вперше запропонували їх в 1977 (алгоритм LZ77) і 1978 роках (алгоритм LZ78). В курсовій роботі розглядаються алгоритми, які належать до першого класу.
Алгоритм LZ77
LZ77 використовує вже проглянену частину повідомлення як словник. Щоб стиснути інформацію, він намагається замінити черговий фрагмент повідомлення на вказівник на такай самий фрагмент у словнику.
Як модель даних LZ77 використовує "ковзаюче" по повідомленню вікно, розділене на дві нерівні частини. Перша, велика за розміром, включає вже проглянуту частину повідомлення. Друга, набагато менша, є буфером, що містить ще не закодовані символи вхідного потоку. Звичайно розмір вікна складає декілька кілобайт. Буфер набагато менший, не більше сто байтів. Алгоритм намагається знайти в словнику фрагмент, співпадаючий з вмістом буфера.
Алгоритм LZ77 видає коди, що складаються з трьох елементів:
зсув в словнику щодо його початку підрядка, співпадаючого з вмістом буфера;
довжина підрядка;
перший символ в буфері, наступний за підрядком.
Після цього алгоритм зрушує весь вміст вікна на довжину співпадаючого підрядка + 1 символ вліво і одночасно втягує відповідну кількість чергових символів повідомлення.
Якщо збіг не виявлений, то алгоритм видає код < 0, (0 - перший символ в буфері) і продовжує свою роботу. Хоча таке рішення неефективне, воно гарантує, що алгоритм зможе закодувати будь-яке повідомлення.
Декодування в LZ77 здійснюється ще простіше, оскільки не потрібно здійснювати пошук в словнику.
Очевидно, що швидкодія кодера LZ77 сильно залежить від того, яким чином здійснюватиметься пошук співпадаючого підрядка в словнику. Якщо шукати збіг повним перебором всіх можливих варіантів, то очевидно, що стиснення буде дуже повільним. Причому при збільшенні розмірів вікна для підвищення ступеня стиснення швидкість роботи пропорційно зменшуватиметься. Для декодера це неважливо, оскільки при декодуванні не здійснюється пошук збігу.
Швидкодія і кодера, і декодера залежить від того, як реалізовано “ковзання” вікна по вмісту повідомлення. Раціонально було б для роботи з вікном користуватися кільцевим буфером, організованим на фізично суцільній ділянці пам'яті, а не реальним зрушенням вмісту вікна. Хоча для підтримки кільцевого буфера необхідні додаткові витрати на збереження цілісності індексів в нім, в цілому це дає дуже істотний виграш тому, що відсутнє постійне зрушення великого блоку пам'яті. Якщо розмір кільцевого буфера рівний ступеню двійки, то стандартна для кільцевого буфера операція “зсув по модулю розмір”, може бути замінена побітовою логічною операцією, що ще більше підвищує ефективність.
Крім проблем з швидкодією, у алгоритму LZ77 виникають проблеми з самим стисненням. Вони з'являються, коли кодер не може знайти співпадаючий підрядок в словнику і видає стандартний 3-компонентний код, намагаючись закодувати один символ. Якщо словник має довжину 4к, а буфер - 16 байтів, то код (<0, 0, символ) займатиме 3 байти. Кодування одного байта в три має мало загального із стисненням і істотно знижує продуктивність алгоритму.
Алгоритм LZSS
Цей алгоритм отримав свою назву по іменах своїх розробників: Lempel, Ziv, Storer, Szimansky. Істотний внесок в розвиток алгоритму вніс Т. С. Bell.
LZSS є вдосконаленням LZ77 і прагне позбавитися від недоліків свого попередника. LZSS відрізняється від LZ77 тим, як підтримується ковзаюче вікно і які коди видає компресор.
LZSS, крім власне вікна з вмістом повідомлення, підтримує двійкове дерево для прискорення пошуку збігу. Кожен підрядок, що покидає буфер, додається в дерево пошуку, а підрядок, що покидає словник, віддаляється з дерева. Така організація моделі даних дозволяє добитися істотного збільшення швидкості пошуку збігу, яка, на відміну від LZ77, стає пропорційна не твору розмірів вікна і підрядка, а його двійковому логарифму. Це дозволяє експериментувати з великими вікнами, не втрачаючи в швидкості стиснення.
Кодер LZSS використовує однобітовий префікс, для того, щоб відрізняти незакодовані символи від пар (зсув, довжина). Такі коди дозволяють отримати істотний виграш у розмірі стислого повідомлення.
Як і в LZ77, в цьому алгоритмі використовується звичайний символьний буфер для зберігання вмісту вікна. В цілях підвищення ефективності “ковзання” вікна по вмісту повідомлення доступ до нього організований як до кільця, і розмір вікна кратний ступеню 2.
Деревом пошуку є двійкове лексикографічно впорядковане дерево. Кожен вузол в дереві соответствуєт1 одному підрядку словника і містить посилання на батька і двох дітей: “більшого” і “меншого” в сенсі лексикографічного порівняння символьних рядків.
Для того, щоб кодер міг почати працювати, необхідно завантажити буфер черговими символами повідомлення і проініціалізувати дерево. Для цього в дерево вставляється вміст буфера.
Алгоритм послідовно виконує наступні дії: - кодує вміст буфера;
прочитує чергові символи в буфер, видаляючи при необхідності найбільш “старі” рядки із словника;
вставляє в дерево нові рядки, відповідні ліченим символам.
Для того, щоб декодер зміг вчасно зупинитися, декодуючи стисле повідомлення, кодер поміщає в стислий файл спеціальний символ “КІНЕЦЬ ФАЙЛУ” після того, як він обробив всі символи повідомлення. Вся робота по пошуку розташування і встановленню довжини максимального збігу вмісту словника з буфером відбувається в процесі додавання в дерево нового рядка. При додаванні рядка в дерево алгоритм послідовно переміщається від кореня дерева до його листа, кожного разу здійснюючи лексикографічне порівняння нового рядка і вузла дерева. Залежно від результату порівняння вибирається більша або менша дитина цього вузла і запам'ятовується довжина збігу рядків і положення поточного вузла.
Якщо в результаті порівняння виявляється, що вміст буфера і рядок, на який посилається поточний вузол, в точності співпадають, то посилання в поточному вузлі оновлюються так, щоб вони указували на буфер, і процедура додавання рядка в дерево завершується.
Якщо дитина поточного вузла, вибрана для чергового кроку, відмічена як неіснуючий, залишається заповнити його відповідним посиланням і завершити роботу.
Потрібно відзначити, що при закінченні роботи процедурі додавання рядка відомі і зсув, і довжина найбільшого збігу, і для цього не було потрібно повний перебір всіх можливих варіантів збігу.
При видаленні вузла з дерева можливі два варіанти. Якщо вузол має не більш за одну дитину, то видалення вузла здійснюється простим виправленням посилань “батько-дитина”. Якщо вузол має двох дітей, то необхідні інші дії. Для цього знайдемо наступний менший вузол в дереві, видалимо його з дерева і замінимо ним поточний вузол, що видаляється. Наступний менший вузол знаходиться вибором меншої дитини і подальшим переміщенням від нього по дереву до листа по великих гілках.
Алгоритм LZSS, взагалі кажучи, є дуже асиметричним. Якщо процедура стиснення достатньо складна і здійснює великий об'єм роботи при обробці кожного символу повідомлення, що стискається, то декодер LZSS тривіально простий і може працювати з швидкістю, що наближається до швидкості процедури звичайного копіювання інформації.
Декодер читає один біт стислої інформації і вирішує - це символ або пара (зсув, довжина). Якщо це символ, то наступні 8 бітів видаються як розкодований символ і поміщаються в ковзаюче вікно. Інакше, якщо це не закодований кінець файлу, то відповідна кількість символів словника поміщається у вікно і видається в розкодованому вигляді.
Оскільки це все, що робить декодер, зрозуміло, чому процедура декодування працює так швидко.
Отже, не дивлячись на те що семантика цих алгоритмів краще всього розкривається на прикладі пакування текстової інформації, практика показує, що вони так само добре працюють з будь-якою, що в принципі стискається, інформацією. Ці алгоритми за своєю природою є адаптивними, що відразу знімає цілий ряд проблем. Оскільки описані алгоритми не є запатентованими, то будь хто може використовувати програму, яка базується на цих алгоритмах.
Постановка задачі та обґрунтування вибраного напряму проектування
Задачею даного курсового проекту є реалізувати алгоритм стиснення інформації методом Лемпеля-Зіва. Для виконання поставленої задачі необхідно використати метод LZ77, хоча LZSS є кращим за відсотком стисненням інформації. Засобом проектування програмного продукту є середовище розробки програмного забезпечення Borland C++ Builder 6. Цей вибір пояснюється тим, що це середовище є досить зручним для створення подібних проектів та дає змогу реалізувати зручний інтерфейс для користувача.
Основна увага повинна бути зосереджена на організації словника для методу Лемпеля-Зіва. В сутності, весь процес архівування та розархівування представляє собою безперервний пошук в словнику і заповнення словника, і чим швидше ці дві операції здійснюються, тим швидше буде працювати програма.
LZ77 використовує "ковзаюче" по повідомленню вікно, розділене на дві нерівні частини: перша, велика за розміром(словник), включає вже проглянуту частину повідомлення; друга, набагато менша, є буфером, що містить ще не закодовані символи вхідного потоку. Алгоритм видає коди, що складаються з трьох елементів:
зсув в словнику щодо його початку підрядка, співпадаючого з вмістом буфера;
довжина підрядка;
перший символ в буфері, наступний за підрядком.
В курсовій роботі застосовується наступна організація: на код виділяється 4 байти: 2 байти – зсув у словнику, 1 байт – довжина підрядка, 1 байт – наступний символ. Отже розмір словника не може перевищувати 65536 байт, розмір буфера – 256 байт, розмір ковзаючого вікна – 65792 байт.
Проектний розділ
Алгоритм стиснення
Суть алгоритму полягає в пошуку в словнику фрагменту, який співпадає з вмістом буфера. Якщо знайдено такий фрагмент алгоритм видає довжину співпадаючого фрагменту та зміщення в словнику, за яким знаходиться цей фрагмент. Якщо такого фрагменту не знайдено довжина фрагменту – 0. Після цього алгоритм зрушує весь вміст вікна на довжину співпадаючого підрядка + 1 символ вліво і одночасно втягує відповідну кількість чергових символів повідомлення.
Схема 3.1. Блок схема алгоритму Лемпеля-Зіва
Програмна реалізація алгоритму
Головною функцією в програмі, яка реалізовує алгоритм є функція пошуку в словнику найбільшого входження буфера – функція void FindBuf(int &Length, int &ShiftInDict), де Length – довжина знайденої стрічки(0, якщо нічого не знайдено), а ShiftInDict – зсув в словнику відносно його початку.
void CCoderLZ::FindBuf(int &Length, int &ShiftInDict)
{
int Shift, Shift1, Len, maxLen, StartPos;
Shift = 0;
maxLen = 0;
Len = 0;
Shift1 = 0;
if(DictStartPos != BufStartPos && BufSize > 1) // dictionary is not empty
{ // in buf is > 1 bytes
StartPos = DictStartPos;
while(1)
{
FindFirstBuf(Len, Shift1, StartPos);
if(Shift1 == 0 && Len == 0) // not found
{
break;
}
else // found
{
if(Len > maxLen)
{
maxLen = Len;
Shift = Shift1;
}
StartPos = Shift1 + 1;
}
}
}
ShiftInDict = Shift;
Length = maxLen;
}
Ця функція використовує функцію void FindFirstBuf(int &Length, int &Shift, int StartPos), де Length – довжина знайденої стрічки(0, якщо нічого не знайдено), Shift – зсув знайденої стрічки відносно початка словника, StartPos – початкова позиція в словнику, з якої починається пошук. Ця функція шукає перше входження буфера в словнику з вказаного зміщення, результатом є довжина знайденої стрічки і її зміщення відносно початку словника.
void CCoderLZ::FindFirstBuf(int &Length, int &ShiftInDict, int StartPos)
{
int posBuf, posDict;
int Shift = 0;
int Len = 0;
for(posDict = StartPos, posBuf = BufStartPos; posDict < BufStartPos && posBuf < BufStartPos + BufSize - 1; posDict++)
{
if(SlWindow[posDict] == SlWindow[posBuf])
{
if(posBuf == BufStartPos) // first buf letter
{
Shift = posDict;
}
Len++;
posBuf++;
}
else
{
if(posBuf != BufStartPos) // find not first letter?
{
break;
}
}
}
ShiftInDict = Shift;
Length = Len;
}
Функція int ReadByte() забезпечує читання даних з вхідного файлу(файлу, який пакується в “ковзаюче” вікно, який поділяється на словник(перша більша частина) та буфер(друга, набагато менша за першу частина). Функція повертає 0 якщо читання відбулося успішно та 1 якщо досягнуто кінця вхідного файлу. BufSize – поточний розмір буфера(0 – буфер порожній).
int CCoderLZ::ReadByte() // 1- file size is 0
{
unsigned char Byte;
int Error;
if(fread(&Byte, 1, 1, InputFile) == 1) // not end of file
{
ReadBytes++;
if(BufStartPos + BufSize == SlWindowSize) // buffer is full
{
ShiftSlWindow();
SlWindow[BufStartPos + BufSize] = Byte;
BufSize++;
return 0;
}
else // buffer is not full
{
SlWindow[BufStartPos + BufSize] = Byte;
BufSize++;
while(BufStartPos + BufSize < SlWindowSize)
{
if(fread(&Byte, 1, 1, InputFile) == 1)
{
SlWindow[BufStartPos + BufSize] = Byte;
BufSize++;
ReadBytes++;
}
else
{
break;
}
}
return 0;
}
}
else // end of file
{
if(BufSize == 0) // no bytes
{
return 1;
}
else
{
ShiftSlWindow();
if(BufSize == 0)
{
return 1;
}
else
{
return 0;
}
}
}
}
Попередня функція використовує функцію зсуву вікна на одну позицію вліво void ShiftSlWindow().
void CCoderLZ::ShiftSlWindow()
{
int i;
if(DictStartPos == 0) // dictionary is full
{
for(i = DictStartPos; i < BufStartPos + BufSize; i++)
{
SlWindow[i] = SlWindow[i + 1];
}
BufSize--;
}
else
{
for(i = DictStartPos - 1; i < BufStartPos + BufSize; i++)
{
SlWindow[i] = SlWindow[i + 1];
}
DictStartPos--;
BufSize--;
}
}
Функція пакування файлу int CCoderLZ::Pack(void), створює архів з відповідним ім’ям та записує в нього дані(зміщення в словнику підрядка, співпадаючого з вмістом буфера, довжину підрядка, перший символ в буфері, наступний за підрядком), знайдені функцією FindBuf.
int CCoderLZ::Pack(void) // 1 - error open input file
// 2 - output file exists
// 3 - error create output file
{
int Error, i;
int Element1, Element2;
DWORD FileSize;
if((InputFile = fopen(InputFN, "rb")) == NULL)
{
return 1;
}
/* if(FileExists(OutputFN))
{
fclose(InputFile);
return 2;
}
else*/
{
if((OutputFile = fopen(OutputFN, "wb")) == NULL)
{
fclose(InputFile);
return 3;
}
}
WriteCoderName();
WriteFileInfo();
FileSize = GetFileSize(CreateFile(InputFN, GENERIC_READ, FILE_SHARE_READ, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL), NULL);
BufSize = 0;
DictStartPos = BufStartPos;
ReadBytes = 0;
ProgressForm->LabelFileSize->Caption = FileSize;
while(1)
{
Application->ProcessMessages();
if(FileSize != 0)
{
ProgressForm->ProgressBar->Position = ProgressForm->ProgressBar->Max * ReadBytes / FileSize;
// ProgressForm->Update();
// MainForm->Update();
}
Error = ReadByte();
if(Error == 1) // file size is 0
{
break;
}
else // file size is not 0
{
FindBuf(Element1, Element2);
if(Element1 <= 1)
{
WriteOneCode(SavedByteID, Element2, SlWindow[BufStartPos]);
}
else
{
for(i = 0; i < Element1; i++)
{
ReadByte();
}
WriteOneCode(Element1, Element2, SlWindow[BufStartPos]);
}
}
}
fclose(InputFile);
fclose(OutputFile);
return 0;
}
Розпаковування файлу здійснює функція int ReadOneCode().
int CDecoderLZ::ReadOneCode() // 1 - end of input file
{
unsigned char Element1;
unsigned short Element2;
unsigned char Element3 = 0;
long offset;
char buf[1024];
if(fread(&Element1, sizeof(Element1), 1, InputFile) != 1)
{
return 1;
}
ReadBytes += sizeof(Element1);
switch(Element1)
{
case SavedByteID:
{
if(fread(&Element3, sizeof(Element3), 1, InputFile) != 1)
{
return 1;
}
ReadBytes += sizeof(Element3);
fwrite(&Element3, sizeof(Element3), 1, OutputFile);
return 0;
}
default:
{
if(fread(&Element2, sizeof(Element2), 1, InputFile) != 1)
{
return 1;
}
if(fread(&Element3, sizeof(Element3), 1, InputFile) != 1)
{
return 1;
}
ReadBytes += sizeof(Element3);
if(!(Element1 == 0 && Element2 == 0))
{
offset = 0 - (BufStartPos - Element2);
fseek(OutputFile, offset, SEEK_CUR);
fread(&buf, 1, Element1, OutputFile);
offset = 0 - offset - Element1;
fseek(OutputFile, offset, SEEK_CUR);
fwrite(&buf, 1, Element1, OutputFile);
}
fwrite(&Element3, sizeof(Element3), 1, OutputFile);
return 0;
}
}
}
Проектування інтерфейсу
Проект програми складається з чотирьох форм:
MainForm - головна форма програми. На ній розміщені компоненти DriveComboBox, DirectoryListBox, FileListBox, SaveDialog, BitBtn. DriveComboBox призначений для вибору диска, список директорій якого відображається в DirectoryListBox, а файли вибраної директорії останнього відображаються в компоненті FileListBox. SaveDialog призначений для відображення діалогу зберігання архіву, який викликається при обробником OnClick кнопки BitBtnPack. Кнопки BitBtnUnPack, BitBtnRefreshFileList та BitBtnAbout призначені для розпакування вибраного файлу, оновлення списку файлів в компоненті FileListBox та відображенні форми About відповідно;
ProgressForm – форма, на якій відображається статус процесу пакування чи розпакування файлу. Містить компоненти ProgressBar, який відображає статус обробки файлу програмою та Label – відображає розмір файлу, який пакується чи розпаковується;
DestForm – діалог запиту на вибір директорії, в яку буде розпакований архів. На ній розміщені компоненти DirectoryListBox, DriveComboBox(дозволяє вибрати диск, директорії якого будуть відображатися в DirectoryListBox), Button(OK – підтвердження вибраної директорій, Cancel – відміна розпаковки);
AboutBox – відображає інформацію про автора програми.
Оскільки програма призначена для пакування файлів, використовуючи алгоритм Лемпеля-Зіва, то вона отримала назву Packer LZ.
Дослідження роботи алгоритму і програми
Опис інтерфейсу
Програмний продукт володіє інтуїтивно-зрозумілим інтерфейсом, що дозволяє користувачу навчитись користуватись програмою без попереднього ознайомлення з її роботою. Головне вікно програми зображено на рисунку.
Рис. 4.1. Головне вікно програми
Для пакування файлу необхідно вибрати диск в компоненті DriveComboBox, на якому знаходиться файл, який потрібно запакувати, вибрати директорію зі списку зліва і потрібний файл зі списку файлів справа, після цього необхідно натиснути на кнопку Pack To – з’явиться вікно з запитом на збереження архіву, зображене на рисунку.
Рис. 4.2. Запит на збереження архіву
Після вибору файлу, в який буде проводитися пакування і натиснення на кнопку Save програма починає пакування:
Рис. 4.3. Процес пакування файлу
Для декомпресії необхідно вибрати потрібний файл і натиснути на кнопку UnPack To, після чого появляється діалогове вікно з запитом на вибір папки, в яку буде розпаковуватися архів.
Рис. 4.4. Запит на вибір папки для розпакування
Після вибору потрібної папки і натиснення на кнопку OK відбувається декомпресія архіву у вказану папку.
Оцінка роботи програми
Для оцінки роботи програми було проведено тестування програми на стиснення файлів різних розширень (текстових, графічних, exe - файлів) та об’ємів. Результати тестування містяться в таблиці:
Таблиця 4.1. Порівняння стискання файлів різного типу
Тип файлу
Об’єм файлу до стиснення, байт
Об’єм файлу після стиснення, байт
Відсоток стискання, %
cpp
648
380
41,4
html
22717
5554
75,6
ico
51262
42359
17,4
doc
49664
21921
55,9
exe
72585
66664
8,2
txt
9400
5462
41,9
Після цього було проведено розпакування запакованих файлів і порівняння їх вмісту з файлами, які пакувалися. Результати приведено на рисунку(зліва – файли які пакувалися, справа – розпаковані з архівів).
Рис. 4.5. Порівняння вмісту файлів
Отже за результатами тестування можна зробити висновок, що при пакуванні і розпакуванні файлів за допомогою даної програми вміст файлу не змінюється, програма є більш ефективною для стиснення файлів з розширенням txt, doc та html.
Висновки
В процесі виконання курсової роботи розроблено програму стиснення інформації, використовуючи алгоритм Лемпеля-Зіва, досліджено та проаналізовано сучасні алгоритми стиснення інформації без втрати даних. Програма забезпечує відкриття файлу для стиснення, збереження стисненого файлу за вказаним користувачем ім’ям та можливість розархівування файлу у вказану директорію.
До переваг програмного продукту можна віднести:
простий у користуванні та інтуїтивно зрозумілий інтерфейс користувача;
відсутнє відображення процесу архівування та розархівування;
модульний принцип проектування, що дає змогу легко доповнити та удосконалити програму.
До недоліків програми належать:
низький коефіцієнт стиснення файлів, що містять картинки, EXE файлів;
низька швидкість архівування.
Література
Кричевский Р. Е. Сжатие и поиск информации., Москва, 1989 г.
Кохманюк Д. Сжатие информации: как это делается., IndexPRO, Киев, №№1,2.
Ватолин Д., Ратушняк А., Смирнов М., Юкин В, Методы сжатия данных
Д. Мастрюков Алгоритмы сжатия информации
Кадач А. Эффективные алгоритмы неискажающего сжатия текстовой информации
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора