Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Стиснення інформації методом Хаффмана
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2007
Тип роботи:
Курсова робота
Предмет:
Методи та засоби комп’ютерних інформаційних технологій
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Кафедра ПЗ
Курсова робота
з курсу “Методи та засоби комп`ютерних інформаційних технологій”
Стиснення інформації методом Хаффмана
Керівник:
Львів - 2007
Завдання до курсової роботи
Тема курсової роботи: Стиснення інформації алгоритмом RLE.
Постановка задачі: Розробити програму для архівування та розархівування файлів алгоритмом RLE. Програмний продукт має надавати користувачу можливості архівувати файли, розархівовувати бути зручним та ефективним у використанні.
Анотація
“ Стиснення інформації алгоритмом RLE ”. Курсова робота. – НУ “Львівська політехніка”, каф.: ПЗ, дисципліна: “Методи та засоби комп`ютерних інформаційних технологій”, 2007.
Курсова робота складається з сторінок, таблиці, додатку.
В даній курсовій роботі спроектовано та розроблено програму для стиснення інформації алгоритмом RLE. Проект надає можливості архівування файлів та їх розархівування алгоритмом RLE.
Зміст
Завдання до курсової роботи .2
Анотація .3
Вступ .6
1. Аналітичний огляд ............................................................................7
1.1 Способи стиснення інформації.....................................................6
1.2 Огляд алгоритмів стиснення інформації .......................................7
1.2.1 Метод RLE……..................................................................8
1.2.2 Статичне кодування Хаффмана………………...................9
1.2.3 Арифметичне кодування…................................................9
1.2.4 Алгоритм Лемпеля-Зіва……............................................10
2. Постановка задачі та обгрунтування вибраного напряму проектування .............12
3. Проектний розділ.................................................................................13
4. Дослідницький розділ..........................................................................24
5. Технологічний розділ...........................................................................25
Висновки....................................................................................................27
Література.................................................................. ...............................28
Додаток 1....................................................................................................29
Вступ
Дані, вироблені різноманітними програмами, зберігаються на зовнішніх пристроях, що запам'ятовують, обсяг яких обмежений. При передачі даних через канали зв'язку, пропускна здатність каналу обмежена. Перебороти деякі з цих обмежень дозволяють алгоритми стиску. Дані, що зберігаються на ЗЗП, можна стискувати, тим самим як би збільшуючи ємкість ЗП. Це актуально при резервному копіюванні інформації. Пропускна здатність каналів зв'язку при використанні стиски також збільшується.
Основна ідея стиску інформації - використання того факту, що дані містять повторювані ланцюжки символів, а також нерівномірність статистичного розподілу алфавіту вихідних даних.
Методи стиску даних мають достатньо довгу історію. Існує ряд простих підходів до даної проблеми. Найбільше відомий - це кодування довжин ланцюжків (RLE). Суть методу: заміна ланцюжків повторюваних символів на один цей символ і лічильник повторення. Проблема складається в тому, щоб розпаковщик міг відрізнити в результуючому потоку таку кодовану серію від інших символів. Розв'язання очевидне - постачати всі такі ланцюжки деякими заголовками: Наприклад, використовувати перший бита як ознака кодованої серії або використовувати для цієї цілі який-небудь символ. Метод достатньо ефективний для графічних зображень.
1. Аналітичний відділ.
1.1 Способи стиснення інформації
Running - це найпростіший з методів упаковки інформації . Припустимо що маємо рядок тексту, і в кінці рядка коштує 40 пропусків. Проблема стиснення цього рядка вирішується дуже просто - ці 40 пробілів ( 40 байт ) стискаються в 3 байти за допомогою упаковки їх по методу символів, що повторюються (running). Перший байт, що стоїть замість 40 пропусків в стислому рядку, фактично буде являтися пробілом ( послідовність була з пробілів ) . Другий байт - спеціальний байт "прапорця" який вказує що ми повинні розвернути попередній в рядку байт в послідовність при відновленні рядка . Третій байт - байт рахунку ( у нашому випадку це буде 40 ). Кожний раз, коли ми маємо послідовність з більш 3-х однакових символів, замінювати їх вище описаною послідовністю, щоб на виході отримати блок інформації менший за розміром, але що допускає відновлення інформації в початковому вигляді.
В даному методі основною проблемою є вибір того самого байта "прапорця", оскільки в реальних блоках інформації як правило використовуються всі 256 варіантів байта і немає можливості мати 257 варіант - "прапорець".
LZW - Історія цього алгоритму починається з публікації в травні 1977 р. Дж. Зівом ( J. Ziv ) і А. Лемпелем ( A. Lempel ) статті в журналі " Інформаційні теорії " під назвою " IEEE Trans ". Надалі цей алгоритм був допрацьований Тері А. Велчем ( Terry A. Welch ) і в остаточному варіанті відбитий в статті " IEEE Compute " у червні 1984 . У цій статті описувалися подробиці алгоритму і деякі загальні проблеми з якими можна зіткнутися при його реалізації. Пізніше цей алгоритм отримав назву - LZW ( Lempel - Ziv - Welch ) .
Алгоритм LZW є алгоритмом кодування послідовностей неоднакових символів. Візьмемо для прикладу рядок " Об'єкт TSortedCollection породжений від TCollection.". Аналізуючи цей рядок ми можемо бачити, що слово "Collection" повторюється двічі. У цьому слові 10 символів - 80 біт. І якщо ми зможемо замінити це слово у вихідному файлі, в другому його включенні, на посилання на перше включення, то отримаємо стиснення інформації. Якщо розглядати вхідний блок інформації розміром не більш 64К і обмежиться довжиною кодованого рядка в 256 символів, то враховуючи байт "прапор" отримаємо, що рядок з 80 біт замінюється 8+16+8 = 32 бита. Алгоритм LZW ніби "навчається" в процесі стиснення файлу. Якщо існують рядки, що повторюються, у файлі, то вони будуть закодовані в таблицю. Перевагою алгоритму є те, що немає необхідності включати таблицю кодування в стислий файл. Іншою важливою особливістю є те, що стиснення по алгоритму LZW є однопрохідною операцією в протилежність алгоритму Хаффмана ( Huffman ), якому потрібно два проходи.
Стискаючи файл по алгоритму Хаффмана перше необхідно прочитати файл повністю і підрахувати скільки разів зустрічається кожен символ з розширеного набору ASCII. Якщо ми враховуватимемо все 256 символів, то для нас не буде різниці в стисненні текстового і EXE файлу. Після підрахунку частоти входження кожного символу, необхідно проглянути таблицю кодів ASCII і сформувати уявну компоновку між кодами по в напрямок зменшення. Тобто не змінюючи місцезнаходження кожного символу з таблиці в пам'яті відсортувати таблицю посилань на них в напрямку зменшення. Кожне посилання з останньої таблиці - "вузол".
1.2 Огляд алгоритмів стисення інформації
1.2.1 Метод RLE
Зміст методу – заміна ланцюжків символів, що повторюються, на один цей символ та лічильник повторювання. Проблема полягає в тому, щоб декодер міг відрізнити у вихідному потоці таку кодовану серію від інших символів. Розв’язок цієї проблеми очевидний – додавати до таких ланцюжків деякі заголовки (наприклад, використовувати перший біт як ознаку кодованої серії). Метод є досить ефективним для графічних зображень у форматі “байт на піксел” (наприклад, формат PCX використовує кодування RLE).
Недоліки методу RLE є очевидними: це, передусім, низька пристосованість до багатьох розповсюджених типів файлів, наприклад, текстових: у загальному випадку реально стиснути можна лише ланцюжки проміжків на початку абзаців. Саме тому цей метод можна ефективно використовувати лише у комбінації з вторинним кодуванням.
Цей підхід реалізовано в алгоритмі кодування факсів: спочатку зображення розбивається на чорні та білі крапки, що перетворюються алгоритмом RLE на потік довжин серій, а потім ці довжини серій кодуються за методом Хаффмена зі спеціально підібраним деревом.
1.2.2 Статичне кодування Хаффмана
Розглянемо статистичне кодування Хаффмена. Це кодування співставляє вхідним символам, що подаються ланцюжками бітів однакової довжини (наприклад, 8-бітовими байтами), ланцюжки бітів змінної довжини. Довжина коду пропорційна (з округленням до цілого) двійковому логарифму його частоти, взятому з оберненим знаком. Це кодування є префіксним, що дозволяє його легко декодувати однопрохідним алгоритмом. В префіксному кодуванні код будь-якого символа не є префіксом коду жодного іншого символа. Префіксний код зручно представляти у вигляді двійкового дерева, в якому символи знаходяться на листках, а ребра помічені 0 або 1. Тоді код символа можна задати як шлях від кореня дерева до листа, що містить цей символ.
При використанні адаптивного кодування Хаффмена необхідно постійно коректувати дерево у відповідності до статистики вхідного потоку, яка весь час змінюється. Під час реалізації, як правило, вимагаються значні витрати на балансування кодового дерева відповідно до нових частот символів на кожному кроці.
Перевагами методу Хаффмена є його досить висока швидкість і так само висока якість стискання. Цей алгоритм порівняно давно відомий і є на сьогодні дуже розповсюдженим: прикладами є програма compact OC UNIX (програмна реалізація), а також стандарт кодування факсів (апаратна реалізація).
Кодування Хаффмена має мінімальну надлишковість за умови, що кожний символ кодується окремим ланцюжком в алфавіті {0,1}.
Недоліком кодування Хаффмена є залежність коефіцієнту стискання від близькості імовірностей символів до від’ємних ступенів 2; це пов’язано з тим, що кожен символ кодується цілою кількістю біт. Найбільш помітно це під час кодування двосимвольного алфавіту: в цьому випадку стискання неможливе, незважаючи на відмінності імовірностей символів; алгоритм фактично “округляє” їх до 1/2!
Цю проблему можна частково вирішити за рахунок блокування вхідного потоку (тобто включення до розгляду нових символів вигляду “ab”, “abc”,..., де a, b, c – символи початкового алфавіту). Однак це не дозволяє повністю позбутися втрат (вони лише зменшуються пропорційно розміру блока) і призводить до стрімкого росту кодового дерева: якщо, наприклад, символами вхідного алфавіту є 8-бітові байти зі значеннями 0...255, то при блокуванні по два символи ми отримуємо алфавіт (і кодове дерево!) із 65536 символів, а при блокуванні по три – 16777216! Таким чином, зростають вимоги до пам’яті та час побудови дерева (а у випадку адаптивного кодування – і час поновлення дерева, а звідси і час стискання).
Втрати ж складатимуть у середньому 1/2 біт на символ при відсутності блокування, а за його наявності – 1/4 і 1/6 біт для блоків довжини 2 та 3 відповідно. Великий коефіцієнт стискання, що не залежить від близькості значень імовірностей символів до степенів 1/2, може дати так зване арифметичне кодування.
1.2.3 Арифметичне кодування
Арифметичне кодування – це метод, що дозволяє стискати символи вхідного алфавіту без втрат за умови, що відомий розподіл частот цих символів. Концепцію методу наведено у роботах Еліаса в 60-х роках. Пізніше метод було розвинено та значно модифіковано.
Арифметичне кодування є оптимальним, досягаючи теоретичної границі стискання – ентропії вхідного потоку.
Текст, який стиснено арифметичним кодером, розглядається як деякий двійковий дріб з інтервалу [0,1). Результат стискання можна подати як послідовність двійкових цифр із цього дробу.
Ідея методу полягає в наступному: початковий текст розглядається як запис цього дробу, де кожен вхідний символ є “цифрою” з вагою, що пропорційна ймовірності його появи. Пояснимо роботу кодера на прикладі.
Нехай алфавіт складається із двох символів: a та b з імовірностями відповідно 3/4 та 1/4. Як вже згадувалося вище, кодування Хаффмена не може стискати слова в даному алфавіті.
Розглянемо (відкритий справа) інтервал [0,1). Розіб’ємо його на частини, довжина яких пропорційна імовірностям символів. В нашому випадку це – [0, 3/4) i [3/4, 1). Принцип дії алгоритму полягає в наступному: кожному слову в початковому алфавіті відповідає певний підінтервал із [0,1). Порожньому слову відповідаю весь інтервал [0,1). Після отримання кожного наступного символу арифметичний кодер зменшує інтервал, обираючи ту його частину, яка відповідає символу, що надійшов. Кодом ланцюжка є інтервал, виділений після обробки всіх його символів, а точніше, двійковий запис координати будь-якої точки з цього інтервалу.
Таким чином, довжина отриманого інтервалу пропорційна ймовірності появи кодованого ланцюжка.
Під час реалізації цього методу виникають дві проблеми: по-перше, необхідно використовувати дійсну арифметику необмеженої точності, і по-друге, результат кодування стає відомим лише після закінчення вхідного потоку. Однак, досліди показали, що можна практично без втрат обмежитися цілочисельною арифметикою невеликої точності (16-32 розряди), а також домогтися покрокової (інкрементальної) роботи алгоритми: цифри коду можуть видаватися послідовно під час читання вхідного потоку.
1.2.4 Алгоритм Лемпеля-Зіва
Усі методи та моделі кодування, розглянуті вище, розглядали в якості вхідних даних ланцюжки символів (тексти) в деякому нескінченому алфавіті. При цьому залишалося відкритим питання про зв’язок цього вхідного алфавіту кодера з даними, що підлягають стисканню (і представлені у вигляді ланцюжків в (іншому) алфавіті, який зазвичай складається із 256 символів-байтів).
В найпростішому випадку можна використовувати в якості вхідного алфавіту саме ці символи (байти) вхідного потоку. Саме так працює метод squashing програми РКРАК (використане статичне кодування Хаффмена, двопрохідний алгоритм). Ступінь стискання при цьому відносно невеликий – близько 50% для текстових файлів.
Значно якісніше стискання можна отримати виділенням із вхідного потоку ланцюжків, що повторюються, і кодування посилань на ці ланцюжки.
Цей метод, про який піде мова, належить Лемпелю та Зіву і називається LZ77-compression (за роком публікації). Він полягає в наступному: компресор постійно зберігає певну кількість останніх оброблених символів у деякому буфері (який також називається ковзаючим словником – sliding dictionary). Назва “ковзаючий” зумовлена тим, що його довжина постійна: кожного разу, коли компресор кодує наступний ланцюжок, він дописує її в кінець словника та “відрізає” відповідну кількість символів на початку буфера. Під час обробки вхідного потоку символи, що надійшли, потрапляють у кінець буфера, зсуваючи попередні символи та витісняючи найстаріші.
Розміри цього буфера є різними в різних реалізаціях. Очевидно, що використання буфера більших розмірів дозволяє отримати якісніший результат. Алгоритм виділяє (шляхом пошуку в словнику) найдовший початковий підрядок вхідного потоку, що співпадає з одним із підрядків у словнику, і подає на вихід пару (length, distance), де length – довжина знайденого у словнику підрядка, а distance – відстань від нього до вхідного підрядка (тобто фактично індекс підрядка в буфері, віднятий від його розміру). В разі, коли такого підрядка не знайдено, до вихідного потоку просто копіюється черговий символ вхідного потоку.
У найпершій версії алгоритму пропонувалося виконувати найпростіший пошук по всьому словнику. Час стискання за такої реалізації був пропорційний добутку довжини вхідного потоку на розмір буфера, що не є придатним для практичного використання. Але потім було запропоновано використовувати двійкове дерево для пошуку в словнику, що дозволило на порядок збільшити швидкість роботи.
Таким чином, алгоритм Лемпеля-Зіва перетворює один потік вхідних символів на два паралельних потоки length та distance. Очевидно, що ці потоки є потоками символів в алфавітах L та D, і до них можна застосувати один із вищенаведених методів (RLE, кодування Хаффмена, арифметичне кодування). Це підводить нас до ідеї дворівневого кодування, найефективнішій серед усіх, що використовуються сьогодні на практиці. Під час реалізації цього методу необхідно домогтися узгодженого виводу обох потоків в один файл. Ця проблема зазвичай розв’язується шляхом почергового запису кодів символів із обох потоків.
2. Постановка задачі та обгрунтування вибраного напряму проектування
При виконанні курсової роботи переді мною була поставлена ціль реалізувати алгоритм стиснення інформації алгоритмом RLE..
Курсовий проект розроблявся в середовищі Borland C++ Builder 6. Це дозволило швидко реалізувати зручний користувацький інтерфейс, опрацювання відкривання та закривання файлів. Вхідними даними до даної програми є файл який користувач може вибрати, користуючись діалогом відкриття файлів.
3. Проектний розділ
Головними функціями розробленої програми є функції архівування та розархівування файлів:
Функція архівування файлу:
unsigned long __stdcall TCoderForm::RLE_compress(unsigned char *ori_source, unsigned char *ori_target, unsigned long source_size, unsigned long target_size)
{
unsigned long i, total_aaa;
unsigned long last_pointer = source_size - min_aaa;
unsigned long *source_pointer_long;
unsigned char *target = ori_target; // we only play with the pointer
unsigned char *source = ori_source; // we only play with the pointer
unsigned char *current_source_pointer;
unsigned char *last_source_pointer = ori_source + source_size; // for inner loop comparison
unsigned long total_read, total_write, current_total_read;
unsigned long last_read;
//make sure the target has enough size
if(target_size < source_size)
return(0);
fill_dictionary();
total_read = 0;
total_write = 0;
last_read = 0;
source_pointer_long = (unsigned long *)source; // first location
for(i = 0; i < last_pointer; i++)
{
if(dictionary[*source] == *source_pointer_long)
{
current_source_pointer = source;
for(source += min_aaa; source < last_source_pointer; source++)
{
if(*source != *current_source_pointer)
break;
}
//calculate total_aaa
total_aaa = (source - current_source_pointer) - min_aaa;
// calculate total read
current_total_read = (i - total_read) + min_aaa;
// save to target the different if any plus the aaaa value
memcpy(target, ori_source + last_read, current_total_read);
target += current_total_read;
// store the value in target and increase target pointer, set to the next slot
target += save_variable_length_value(total_aaa, (unsigned long*)target);
// increase total read
total_read += (current_total_read + total_aaa);
// update pointer
i = total_read - 1;
last_read = i + 1;
// get the next location
source_pointer_long = (unsigned long *)source;
}
else
{
// use asembly for
// 1. increase counter by one NOT by four if we use 'source_pointer_long++;' // because of the unsigned long size
// 2. indirectly we use optimization, DONT know if compiler optimizer can do this
__asm add source_pointer_long, 01h // increase one byte pointer
__asm add source, 01h // increase one byte pointer
}
}
// calculate total read, check whether the total read is equal to the source size or not
// if not that means some bytes are not read yet so read them and put in target
total_write = source_size - total_read;
if(total_write)
{
memcpy(target, ori_source + total_read, total_write);
target += total_write;
}
total_read = (target - ori_target);
return(total_read);
}
Функція розархівування файлу:
void TCoderForm::Unpack(AnsiString Source, AnsiString Dest)
{
in_content = NULL;
out_content = NULL;
// alocate memory before passing the pointer
in_content = get_file_content(Source.c_str(), &in_content_size);
if(in_content == NULL)
{
Application->MessageBoxA("Error, unable to open source file", "Error");
return;
}
// get original file size for reserve the right space
memcpy(&result, in_content, flagfilesize); // read 4 bytes
// reserve space for target which is equal to source
out_content_size = result;
out_content = (unsigned char *) malloc(out_content_size + 100); // plus additional space to prevent overlap
if(out_content == NULL)
{
Application->MessageBoxA("Error, cant allocate space for target", "Error");
return;
}
memset(out_content, 0, out_content_size); // reset
start = time(NULL); // start the stopwatch time
result = RLE_decompress(in_content + flagfilesize, out_content, in_content_size, out_content_size);
if(result == 0)
{
Application->MessageBoxA("Error, cant do RLE decompress", "Error");
return;
}
// show the elapsed time
fout = fopen(Dest.c_str(), "wb");
result = fwrite(out_content, 1, out_content_size, fout); // use out_content_size (the original)
if(result < out_content_size)
{
Application->MessageBoxA("Error, cant save to file", "Error");
return;
}
fclose(fout);
free(in_content);
free(out_content);
}
4. Дослідницький розділ
Для тестування працездатності програми, наглядно буде продемонструвати роботу програми над різними файлами, опис яких наведено в таблиці 1:
Таблиця 1.
Характеристика файлу
Об’єм файлу до стиснення, Кбайт
Об’єм файлу після стиснення, Кбайт
Якість стискання, %
файл *.txt
5827
5789
1,7
веб-сторінка без зображень
81416
81347
1,1
малюнок *.jpg
72099
72045
1,1
малюнок *.bmp
2359350
1074728
55,5
За результатами тестування можна зробити висновок, що розроблену програму можна ефективно використовувати для архівування bmp малюнків. При архівуванні інших файлів програма проявляє себе зовсім неефективно, тому що для в більшості файлів рідко зустрічаються великі послідовності однакових байтів 5. Технологічний розділ
Програмний продукт володіє інтуїтивно-зрозумілим інтерфейсом, що дозволяє користувачу користуватись програмою без попереднього ознайомлення.
Рисунок 5.1. Інтерфейс програми
Для архівування файлу слід вибрати, використовуючи кнопку Source файл, який потрібно запакувати та, використовуючи кнопку Dest файл в який потрібно проводити пакування. Архів буде створено відразу після натиснення на кнопку Pack.
Рисунок 5.2 Діалог запиту на збереження файлу
Для розархівування файлу треба вибрати файл, який потрібно розпакувати та файл, в який буде проведена розпаковка і натиснути на кнопку Unpack.
6. Висновки
Було створено програму пакування інформації за алгоритмом RLE.
До переваг програмного продукту можна віднести:
Простий у користуванні інтерфейс користувача;
Висока швидкість архівування та розархівування;
Невеликий розмір виконавчого файлу, що працює без додаткових бібліотек;
До недоліків програми належать:
Низька якість стиснення більшості файлів;
Під час архівування та розархівування великих файлів відсутня можливість роботи з програмою;
Література
1. Лагунов И. Кодирование
2. "A method for the construction of minimum-redundancy codes", Proc. Inst. Radio Engineers, vol. 40, no. 9, pp. 1098-1101, Sep. 1952..
3 R.L. Milidiu, E.S. Laber,"The warm-up algorithm: A Lagrangean construction codes", TR-15, Departmento de Informatica, PUC-RJ, 1997.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора