Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Завдання
Предмет:
Інформаційні технології
Частина тексту файла (без зображень, графіків і формул):
Анотація:
В даній курсовій роботі реалізується програма, яка стискає текстову інформацію з деякого вхідного файлу, і записує її у новий файл , при цьому займаючи менше місця на диску. Крім того, дана програма розпаковує стиснений нею файл і записує отриману інформацію у вихідний файл. Стиск інформації проводився згідно алгоритму Лемпеля-Зіва-Велча.
На прикладі даної програми мною вивчалася можливість створення компресора - завдання, реалізація якого є достатньо потрібною на сучасному етапі розвитку інформаційних технологій.
ЗМІСТ
Вступ…………………………………………………………………………...3
Методи стиску………………………………………………………………...4
Стиснення інформації способом кодування серій (RLE)…………..….4
Арифметичне кодування………………………………………………....4
Алгоритм Лемпеля-Зіва-Велча (Lempel-Ziv-Welch - LZW)………….....5
Стиснення даних кодом Хафмана……………………………………....5
Принцип роботи алогритму Лемпеля-Зіва-Велча……………………...….6
2.1Варіанти удосконалення………………………………………………….8
Опис програми………………………………………………………………..9
Опис процедур програми ……………………………………….…………...9
4.1 Процедура стиску.…………………………….………………………...10
4.2 Процедура хешування....……………………….………………………...11
4.3 Процедура розпакування..…………………….………………………....12
4.4.Процедура декодування…………….……………………….…………...14
4.5.Процедура вводу коду змінної довжини………………………….…….15
4.6.Процедура виводу коду змінної довжини…….………………………...15
Висновок………………………………………………………………………16
Список літератури……………………………………………………………17
Додаток А…………………………………………………………………......18
Додаток В……………………………………………………………………..24
Вступ
Характерною особливістю більшості типів даних є їх надлишковість. Для людини надлишковість даних часто пов'язана з якістю інформації, оскільки надлишковість, як правило, покращує зрозумілість та сприйняття інформації. Однак, коли мова йде про зберігання та передачу інформації засобами комп'ютерної техніки, то надлишковість відіграє негативну роль, оскільки вона приводить до зростання вартості зберігання та передачі інформації. Особливо актуальною є ця проблема у випадку необхідності обробки величезних обсягів інформації при незначних об'ємах носіїв даних. У зв'язку з цим постійно виникає проблема позбавлення надлишковості або стиснення даних.
Основний принцип, на якому базується стиснення даних, полягає в економічному описі повідомлення, згідно якому можливе відновлення початкового його значення з похибкою, яка контролюється.
Існує багато методів стиску інформації, кожен з яких має свої особливості, але ми розглянемо алгоритм Лемпеля-Зіва-Велча, у якому є таблиця перетворення рядків, так званий словник. Цей алгоритм будує словник саме під час опрацювання тексту, що дозволяє йому бути універсальним алгоритмом і не приносити додаткових затрат на збереження єдиного великого словника для всіх стиснутих файлів.
1.Методи стиску
1.1Стиснення інформації способом кодування серій (RLE):
Найбільш відомий, простий підхід і алгоритм стиснення інформації оборотним шляхом - це кодування серій послідовностей (Run Length Encoding - RLE). Суть методів даного підходу полягає в заміні ланцюжків або серій байтів що повторюються або їх послідовностей на один лічильник, що кодує байт і числа їх повторень.
Приклад: 44 44 44 11 11 11 11 11 01 33 FF 22 22 - вихідна послідовність 03 44 04 11 00 03 01 03 FF 02 22 – послідовність після стиснення.
Перший байт вказує скільки раз потрібно повторити наступний байт. Якщо перший байт рівний 0, то потім пишеться лічильник, що показує скільки за ним йде неповторюваних даних. Даний метод, як правило, досить ефективний для стиснення графічних зображень. Недоліком методу RLE є досить низька ступінь стиснення.
1.2Арифметичне кодування:
Арифметичне кодування є методом, що дозволяє стиснути символи вхідного алфавіту без втрат за умови, що відомий розподіл частот цих символів і є найбільш оптимальним, тому що досягається теоретична межа ступені стиснення. Передбачувана необхідна послідовність символів, при стисненні методом арифметичного кодування розглядається як деякий двійковий дріб з інтервалу [0, 1). Результат стиснення записується як послідовність двійкових цифр із запису цього дробу. Ідея методу полягає в наступному: вихідний текст розглядається як запис цього дробу, де кожний вхідний символ є "цифрою" з вагою, пропорційним імовірності його появи. Цим пояснюється інтервал, що відповідає мінімальної і максимальної ймовірностям появи символу в потоці.
1.3Алгоритм Лемпеля-Зіва-Велча (Lempel-Ziv-Welch - LZW):
Даний алгоритм відрізняється високою швидкістю роботи як при архівуванні, так і при розархівуванні, досить малі вимоги до пам'яті та проста апаратна реалізація. Недолік - низький ступінь стиснення у порівнянні зі схемою двоступінчастого кодування. Припустимо, що в нас є словник, який зберігає рядки тексту і тримаючи від 2-х до 8-мі тисяч пронумерованих слотів. Записується в перші 256 слотів рядки, що складаються з одного символу, номер якого дорівнює номеру слоту. Алгоритм переглядає вхідний потік, розбиваючи його на підстроки і додаючи нові слоти у кінець словника. Прочитаємо кілька символів у рядок s і знайдемо в словнику рядок t - самий довгий префікс s. Нехай він знайдений у слоті з номером n. Виведемо число n у вихідний потік, перемістимо покажчик вхідного потоку на length(t) символів уперед і додамо в словник новий слот, що містить рядок t+c, де с - черговий символ на вході (відразу після t). Алгоритм перетворить потік символів на вході в потік індексів слотів словника на виході. При практичній реалізації цього алгоритму слід врахувати, що будь-який слот словника, крім найперших, що містять односимвольні ланцюжки, зберігає копію деякого іншого слоту, до якого в кінець приписано один символ. Внаслідок цього можна обійтися простою обліковою структурою з одним зв'язком.
1.4Стиснення даних кодом Хафмана:
Стискаючи файл по алгоритму Хафмана перше що треба зробити - це прочитати файл повністю і підрахувати скільки раз зустрічається кожний символ з розширеного набору ASCII. Якщо будуть враховуватися всі 256 символів, то не буде різниці в стисканні текстового чи EXE файлу. Після підрахунку частоти входження кожного символу, необхідно переглянути таблицю кодів ASCII і сформувати бінарне дерево. Код є префіксним, тобто початок коду не може співпасти з більш коротким кодом (до кожного повідомлення на графі веде тільки один шлях). Ця властивість забезпечує зворотність кодування. Найбільшу
великих файлів, що зрозуміло, оскільки до закодованого файлу треба додавати таблицю кодування. В такому випадку ефективно діють модифіковані коди Хафмана, де кількість символів обмежена (наприклад, довжина відрізка до 512 ел. зобр., а більш довгі послідовності представляються як комбінація декількох відрізків максимальної довжини з відповідними кодами продовження та закінчення), але тоді не треба додавати таблицю.
Основні принципи:
попередній статистичний аналіз джерела інформації (документа), щоби визначити ймовірності окремих символів (повідомлень);
найбільш ймовірні символи представляють найбільш короткими кодовими послідовностями, а найменш ймовірні – більш довгими;
ієрархічна структура кодових послідовностей додається до стиснутого документу або використовується певна модифікація з усередненою структурою кодових послідовностей, що дає субоптимальний результат з точки зору стиснення.
2.Принцип роботи алогритму Лемпеля-Зіва-Велча.
Даний алгоритм при стиску (кодуванні) динамічно створює таблицю перетворення рядків: певним послідовностям символів (словам) ставляться в відповідність групи бітів фіксованої довжини (зазвичай 12-бітні). Таблиця ініціалізується всіма 1-символьними рядками (в випадку 8-бітних символів — це 256 записів). По мірі кодування, алгоритм проглядає текст символ за символом, і зберігає кожний новий, унікальний 2-символьний рядок в таблицю в вигляді пари код/символ, де код посилається на відповідний перший символ. Після того як новий 2-символьний рядок збережений в таблиці, на вихід передається код першого символа. Коли на вході читається наступний символ, для нього по таблиці знаходиться вже знайомий рядок максимальної довжини, після чого в таблиці зберігається код цього рядка з наступним символом вході; на вихід подається код цього рядка, а наступний символ використовується в якості початку наступного рядка. Алгоритму декодування на вході потрібно лише закодований текст, оскільки він може відновити існуючу таблицю перетворення безпосередньо по закодованому тексту.
Приклад: ABCABCABCABCABCABC - 1 2 3 4 6 5 7 8 9
1
A
2
B
3
C
4
AB
5
BC
6
CA
7
ABC
8
CAB
9
BCA
Дерево Лемпеля-Зіва виглядає так:
2.1Варіанти удосконалення: Могутні архіватори зазвичай роблять попередню оцінку початкового файлу і до кожного файлу (або до великих частин одного файлу) здійснюють індивідуальний підхід. Наприклад, перед кожним великим фрагментом стислої коди вказується його об'єм і тип стискування для цього досить 3 байти, які не псують загальної якості компресії. Можливі багато варіантів удосконалень, не пов'язаних безпосередньо з характерними для Лемпеля-зіва ідеями. Важливий випадок, коли чисельна інформація набита цифрами. Наприклад: 132, -44.8, 555. Зрозуміло, що цифри можуть бути так перетасовані, що навіть однакові пари будуть украй рідкісні. Згадані методи не дають стиснення. Проте, якщо у фрагменті тексту використовуються всього 16 різних знаків, то кожен з них представляється чотирма бітами. А це вже двократне стиснення! Додаткові резерви можуть бути розкриті якщо текст - російською мовою і використовується не більше 64 знаків. Можна виділяти в початковому файлі нестискувані ділянки. Тоді збиток від кожного з них можна понизити до 3 байтів. А в представленому варіанті кожен перенесений без змін символ тягне за собою однобайтну ознаку, тобто збиток 12.5%!
3. Опис програми
Дана програма написана мовою C++, створена та скомпільована в середовищі Visual Studio 2005. Програму можна запускати декількома способами :
При простому запуску у програму слід ввести назву вхідного файлу та розширення. Якщо дані були введені коректно і вхідний файл існує, то програма опрацює інформацію і видасть стиснений файл з розширенням LZW, також вона видасть файл перевірки з розширенням OUT, який буде містити інформацію отриману після розпакування стисненого файлу.
4. Опис процедур програми
В програмі реалізовані наступні алгоритми :
- алгоритм стиску;
- алгоритм хешування;
- алгоритм розпакування;
- алгоритм декодування;
- алгоритми вводу/вводу коду змінної довжини.
Для реалізації цих алгоритм використовуються наступні процедури:
void compress(FILE *input, FILE *output)- процедура стикску, яка містить основний цикл, що послідовно опрацьовує кожну змінну вхідного файлу.
int find_match(int hash_prefix, unsigned int hash_character) – процедура хешування, яка працює з таблицею рядків.
void expand(FILE *input, FILE *output)- процедура розпакування, що зчитує інформацію з файлу з розширенням .LZW і розпаковує в вихідний файл.
char *decode_string(unsigned char *buffer,unsigned int code) – процедура декодування рядка з таблиці рядків, необхідна для розпакування.
int input_code(FILE *input)- процедура для керування вводу кодів.
void output_code(FILE *output, unsigned int code) – процедура для керування виводу кодів.
4.1 Процедура стиску
void compress(FILE *input, FILE *output) {
unsigned int next_code;
unsigned int character;
unsigned int string_code;
unsigned int index;
int i;
next_code = 256; //Next_code - наступний доступний код рядка
for (i = 0; i < TABLE_SIZE; i++)//Очистка таблиці рядків перед стартом
code_value[i] = -1;
i = 0;
cout << "Compressing...";
string_code = getc(input); //Отримуєм перший код
Основний цикл. Він здійснюється до тих пір, поки можливе читання вхідного потока. Він зупиняє заповнення таблиці рядків після того, як всі можливі коди були використані.
while ((character=getc(input)) != (unsigned)EOF) {
index = find_match(string_code, character);
/* Дивиться,Чи є рядок */
if (code_value[index] != -1)
/* в таблиці. якщо е, */
string_code = code_value[index];
/* отримує значення коду. */
else {
/* Якщо ні, добавляє рядок в таблицю */
if (next_code <= MAX_CODE) {
code_value[index] = next_code++;
prefix_code[index] = string_code;
append_character[index] = character;
}
output_code(output, string_code);
/* Коли виявляється, що */
string_code=character;
/* рядка немає в таблиці, */
}
/* виводиться останній рядок */
}
/* перед додаванням нового */
output_code(output, string_code);
/* Вивід останнього кода */
output_code(output, MAX_VALUE);
/* Вивід ознаки кінця потоку */
output_code(output, 0);
/* Очистка буфера виводу */
cout << " comressed.\n";
}
Під час виконання даної процедури здійснюється посимвольне зчитування інформації з вхідного файлу і стиснення за допомогою табличних кодів. Для того щоб позначити кінець стиснутої інформації записуємо ознаку кінця потоку.
4.2 Процедура хешування
int find_match(int hash_prefix, unsigned int hash_character) {
int index;
int offset;
index = (hash_character << HASHING_SHIFT) ^ hash_prefix;
if (index == 0)
offset = 1;
else
offset = TABLE_SIZE - index;
while (true) {
if (code_value[index] == -1)
return(index);
if (prefix_code[index] == hash_prefix && append_character[index] == hash_character)
return(index);
index -= offset;
if (index < 0)
index += TABLE_SIZE;
}
}
Процедура хешування пробує знайти співставлення для рядка префікс+символ в таблиці рядків. Якщо найдено, повертає індекс. Якщо ні, то повертає перший доступний індекс.
4.3 Процедура розпакування
Дана процедура є незалежною від попередніх даних і працює виключно з файлом з розширенням .LZW , не використовуючи жодних проміжних даних. Результат розпакування буде у файлі з розширенням .OUT
void expand(FILE *input, FILE *output) {
unsigned int next_code;
unsigned int new_code;
unsigned int old_code;
int character;
int counter;
unsigned char *string;
next_code = 256; //Наступний доступний код використовується при виводі на екран
counter = 0;
cout << "Expanding...";
old_code = input_code(input); /* Читається перший код, ініціалізується */
character = old_code; /* змінна character и відсилається перший */
putc(old_code, output); /* код в вихідний файл. */
Основний цикл розпакування. Читаються коди із LZW-файла до тих пір, поки не зустрінеться спеціальний код, що вказує на кінець даних.
while ((new_code = input_code(input)) != (MAX_VALUE)) {
/*
** Перевірка кода для спеціального випадку STRING+CHARACTER+STRING+CHARACTER+
** STRING, коли генерується невизначений код.
*/
if (new_code >= next_code) {
*decode_stack = character;
string = (unsigned char*)decode_string(decode_stack+1, old_code);
}
else //Інакше декодується новий код.
string = (unsigned char*)decode_string(decode_stack, new_code);
//Виводиться декодований рядок в зворотньому порядку.
character = *string;
while (string >= decode_stack)
putc(*string--, output);
//Якщо можливо, добавляється новий код в таблицю рядків
if (next_code <= MAX_CODE) {
prefix_code[next_code] = old_code;
append_character[next_code] = character;
next_code++;
}
old_code = new_code;
}
cout << " expanded.\n";
}
4.4 Процедура декодування
char *decode_string(unsigned char *buffer,unsigned int code) {
int i;
i = 0;
while (code > 255) {
*buffer++ = append_character[code];
code = prefix_code[code];
if (i++ >= 4094) {
cout << "Fatal error during code expansion.\n";
exit(1);
}
}
*buffer = code;
return((char*)buffer);
}
Дана процедура декодує рядок з таблиці рядків і записує у буфер. Цей буфер у зворотньому порядку потім використовується процедурою розпакування.
4.5 Процедура вводу коду змінної довжини
int input_code(FILE *input) {
unsigned int return_value;
static int input_bit_count = 0;
static unsigned long input_bit_buffer = 0L;
while (input_bit_count <= 24) {
input_bit_buffer |= (unsigned long) getc(input) << (24-input_bit_count);
input_bit_count += 8;
}
return_value = input_bit_buffer >> (32 - BITS);
input_bit_buffer <<= BITS;
input_bit_count -= BITS;
return(return_value);
}
Процедура необхідна для перетворення кодів стисненої інформації в нормальне представлення для подальшого опрацювання процедурою розпакування.
4.6 Процедура виводу коду змінної довжини
Дана процедура є протилежною за своїм призначенням, оскільки перетворює з нормального представлення в коди стисненої інформації.
void output_code(FILE *output, unsigned int code) {
static int output_bit_count = 0;
static unsigned long output_bit_buffer = 0L;
output_bit_buffer |= (unsigned long) code << (32 - BITS - output_bit_count);
output_bit_count += BITS;
while (output_bit_count >= 8) {
putc(output_bit_buffer >> 24,output);
output_bit_buffer <<= 8;
output_bit_count -= 8;
}
Висновок
В процесі виконання курсової роботи було виконано наступне:
Створено компресор, який стискає інформацію за алгоритмом Лемпеля-Зіва-Велча.
Створено декомпресор, який розпаковує стиснуту інформацію.
В результаті виконання даної курсової роботи було успішно засвоєно методи розробки та реалізації компонент системного програмного забезпечення.
Список використаної літератури:
Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. - М.: ДИАЛОГ-МИФИ, 2002. - 384 с.
Д. Соломон. Сжатие данных, изображений и звука. - М.: Мир. 2004. - 368 с.
Кричевский Р.Е. Сжатие и поиск информации. – М., Радио и связь, 1989.
Новосельский А. Алгоритмы шифрования // Компьютеры + программы 1996-№5.- С.70-77
www.wikipedia/TSTU WiKi - Web & Studing 2.0
ДОДАТОК А. Лістинг програми:
LZW.H
#ifndef __LZW_H_
#define __LZW_H_
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define BITS 12
#define HASHING_SHIFT BITS-8
#define MAX_VALUE (1 << BITS) - 1
#define MAX_CODE MAX_VALUE - 1
#if BITS == 14
#define TABLE_SIZE 18041 /* Розмір таблиці рядків повинен бути */
#endif /* простим числом, чуть большим, */
#if BITS == 13 /* ніж 2**BITS. */
#define TABLE_SIZE 9029
#endif
#if BITS <= 12
#define TABLE_SIZE 5021
#endif
void compress(FILE *input,FILE *output);
void expand(FILE *input,FILE *output);
char *decode_string(unsigned char *buffer, unsigned int code);
int find_match(int hash_prefix,unsigned int hash_character);
void output_code(FILE *output,unsigned int code);
int input_code(FILE *input);
int *code_value; /* Цей масив для значень кодів */
unsigned int *prefix_code; /* Цей масив містить префікси кодів */
unsigned char *append_character; /* Цей масив містить додадкові символи */
unsigned char decode_stack[4000]; /* Цей масив містить декодовані рядки */
#endif
LZW.CPP
#include "lzw.h"
int main(int argc, char *argv[]) {
FILE *input_file;
FILE *output_file;
FILE *lzw_file;
char input_file_name[81];
code_value = (int*)malloc(TABLE_SIZE*sizeof(unsigned int));
prefix_code = (unsigned int*)malloc(TABLE_SIZE*sizeof(unsigned int));
append_character = (unsigned char*)malloc(TABLE_SIZE*sizeof(unsigned char));
if (code_value == NULL || prefix_code == NULL || append_character == NULL) {
cout << "Fatal error allocating table space\n";
exit(1);
}
if (argc > 1)
strcpy(input_file_name, argv[1]);
else {
cout << "Input file name: ";
cin.getline(input_file_name, 81);
}
input_file = fopen(input_file_name, "rb");
lzw_file = fopen("result.lzw", "wb");
if (input_file == NULL || lzw_file == NULL)
{
cout << "Fatal error opening files\n";
exit(1);
}
//Стиск файла.
compress(input_file, lzw_file);
fclose(input_file);
fclose(lzw_file);
free(code_value);
//Відкриття файлів для розпакування.
lzw_file = fopen("result.lzw", "rb");
output_file = fopen("result.out", "wb");
if (lzw_file == NULL || output_file == NULL)
{
cout << "Fatal error opening files\n";
exit(1);
}
//Розпакування файла.
expand(lzw_file, output_file);
fclose(lzw_file);
fclose(output_file);
free(prefix_code);
free(append_character);
return 1;
}
// Процедура стиску.
void compress(FILE *input, FILE *output) {
unsigned int next_code;
unsigned int character;
unsigned int string_code;
unsigned int index;
int i;
next_code = 256; //Next_code - наступний доступний код рядка
for (i = 0; i < TABLE_SIZE; i++)//Очистка таблиці рядків перед стартом
code_value[i] = -1;
i = 0;
cout << "Compressing...";
string_code = getc(input); //Отримуєм перший код
/*
** Основний цикл. Він здійснюється до тих пір, поки можливе читання
** вхідного потока. Він зупиняє заповнення таблиці рядків
** після того,як всі можливі коди були використані.
*/
while ((character=getc(input)) != (unsigned)EOF) {
index = find_match(string_code, character); /* Дивиться, Чи є рядок */
if (code_value[index] != -1) /* в таблиці. якщо е, */
string_code = code_value[index]; /* отримує значення коду. */
else { /* Якщо ні, добавляє рядок в таблицю */
if (next_code <= MAX_CODE) {
code_value[index] = next_code++;
prefix_code[index] = string_code;
append_character[index] = character;
}
output_code(output, string_code);/* Коли виявляється, що */
string_code=character; /* рядка немає в таблиці, */
} /* виводиться останній рядок */
} /* перед додаванням нового */
output_code(output, string_code); /* Вивід останнього кода */
output_code(output, MAX_VALUE); /* Вивід ознаки кінця потоку */
output_code(output, 0); /* Очистка буфера виводу */
cout << " comressed.\n";
}
/*
** Процедура хешування. Процедура пробує найти співставлення для рядка
** префікс+символ в таблиці рядків. Якщо найдено, повертає індекс.
** Якщо ні, то повертає перший доступний індекс.
*/
int find_match(int hash_prefix, unsigned int hash_character) {
int index;
int offset;
index = (hash_character << HASHING_SHIFT) ^ hash_prefix;
if (index == 0)
offset = 1;
else
offset = TABLE_SIZE - index;
while (true) {
if (code_value[index] == -1)
return(index);
if (prefix_code[index] == hash_prefix && append_character[index] == hash_character)
return(index);
index -= offset;
if (index < 0)
index += TABLE_SIZE;
}
}
//Процедура розпакування. Читає файл LZW-формата і розпаковує його в вихідний файл.
void expand(FILE *input, FILE *output) {
unsigned int next_code;
unsigned int new_code;
unsigned int old_code;
int character;
int counter;
unsigned char *string;
next_code = 256; //Наступний доступний код використовується при виводі на екран
counter = 0;
cout << "Expanding...";
old_code = input_code(input); /* Читається перший код, ініціалізується */
character = old_code; /* змінна character и відсилається перший */
putc(old_code, output); /* код в вихідний файл. */
/*
** Основний цикл розпакування. Читаються коди із LZW-файла до тих пір,
** поки не зустрінеться спеціальний код, що вказує на кінець даних.
*/
while ((new_code = input_code(input)) != (MAX_VALUE)) {
/*
** Перевірка кода для спеціального випадку STRING+CHARACTER+STRING+CHARACTER+
** STRING, коли генерується невизначений код.
*/
if (new_code >= next_code) {
*decode_stack = character;
string = (unsigned char*)decode_string(decode_stack+1, old_code);
}
else //Інакше декодується новий код.
string = (unsigned char*)decode_string(decode_stack, new_code);
//Виводиться декодований рядок в зворотньому порядку.
character = *string;
while (string >= decode_stack)
putc(*string--, output);
//Якщо можливо, добавляється новий код в таблицю рядків
if (next_code <= MAX_CODE) {
prefix_code[next_code] = old_code;
append_character[next_code] = character;
next_code++;
}
old_code = new_code;
}
cout << " expanded.\n";
}
/*
** Процедура простого декодування рядка із таблиці рядків, що зберігає
** результат в буфер. Цей буфер потім може буть виведений в зворотньому
** порядку програмою розпакування.
*/
char *decode_string(unsigned char *buffer,unsigned int code) {
int i;
i = 0;
while (code > 255) {
*buffer++ = append_character[code];
code = prefix_code[code];
if (i++ >= 4094) {
cout << "Fatal error during code expansion.\n";
exit(1);
}
}
*buffer = code;
return((char*)buffer);
}
/*
** Наступні дві процедури керують вводом/виводом кодів змінної
** довжини.
*/
int input_code(FILE *input) {
unsigned int return_value;
static int input_bit_count = 0;
static unsigned long input_bit_buffer = 0L;
while (input_bit_count <= 24) {
input_bit_buffer |= (unsigned long) getc(input) << (24-input_bit_count);
input_bit_count += 8;
}
return_value = input_bit_buffer >> (32 - BITS);
input_bit_buffer <<= BITS;
input_bit_count -= BITS;
return(return_value);
}
void output_code(FILE *output, unsigned int code) {
static int output_bit_count = 0;
static unsigned long output_bit_buffer = 0L;
output_bit_buffer |= (unsigned long) code << (32 - BITS - output_bit_count);
output_bit_count += BITS;
while (output_bit_count >= 8) {
putc(output_bit_buffer >> 24,output);
output_bit_buffer <<= 8;
output_bit_count -= 8;
}
}
Додаток В. Тестування програми:
Рис.1. Ввід вхідного файлу.
Результат виконання стиснення(архівації) та декодування(розпакування) файлу:
Рис.2. Вхідний файл
Рис.3.Стиснутий файл
Рис.4. Декодований (розпакований) файл
18.04.2012 19:04-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора