Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка програми кодування файлів методом Хаффмана.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Системи автоматизованого проектуваня
Інформація про роботу
Рік:
2003
Тип роботи:
Курсова робота
Предмет:
Методи i засоби комп'ютерних інформаційних технологій
Група:
КН-3
Частина тексту файла (без зображень, графіків і формул):
Міністерство Освіти та Науки України
Національний Університет “Львівська Політехніка”
Кафедра Систем Автоматизованого Проектування
Пояснювальна записка
до курсової роботи
з дисципліни "Методи та засоби комп’ютерних та інформаційних технологій"
на тему “Розробка програми кодування файлів методом Хаффмана”
Львів•2003
Завдання до курсової роботи
1. Тема роботи: “Розробка програми кодування файлів методом Хаффмана”
2. Термін здачі студентом закінченої роботи:
3. Вихідні дані для роботи:
виконуваний файл курсової роботи
записка до курсової роботи
4. Зміст розрахунково-пояснювальної записки:
розробка програми
5. Перелік графічного матеріалу
6. Дата видачі завдання: 16.03.03
Анотація
Загарюк Р.В., “ Розробка програми кодування файлів методом Хаффмана ”. Курсова робота. - НУ “Львівська політехніка”, каф.: САП, дисципліна: “Методи та засоби комп’ютерних та інформаційних технологій”, 2003.
Курсова робота складається з 22 сторінок, 9 рисунків, 1 додатку.
У даній курсовій роботі розроблено програму кодування файлів методом Хаффмана.
Зміст
Вступ
По формі представлення в каналі передачі розрізняють послідовні і паралельні коди. При послідовних кодах елементарні сигнали, що передають кодову комбінацію посилаються в канал передачі послідовно в часі. Вони можуть бути розділені часовим інтервалом або опитуватися в певні моменти часу (наприклад, як у послідовному інтерфейсі RS - 232 C).
Для паралельних кодів потрібні багатопровідні канали, тому при передачі інформації на значну відстань вони використовуються рідко через великі затрати (наприклад, паралельний інтерфейс Centronics). Паралельне представлення найчастіше використовується коли потрібна висока швидкість передачі даних (Centronics – 80 – 120 Кбайт/сек, сучасні двонаправлені системи – до 250 Кбайт/сек).
По можливості виявлення та виправлення помилок розрізняють прості (примітивні) і коректуючі коди.
В простих кодах помилка у будь-якому елементі кодової комбінації приводить до неправильного прийому декодованого повідомлення.
Коректуючі коди дозволяють виявляти і усувати помилки у кодових комбінаціях.
По основних законах кодоутворення коди поділяються на комбінаторні (нечислові) і арифметичні (числові).
У даній роботі для кодування файлів використовується метод Хаффмана. Метод полягає в побудові кодового дерева Хаффмана, положення символа на якому визначається частотою (ймовірністю) його появи.
1. Теоретична частина
1.1. Різновидності кодів
По формі представлення в каналі передачі розрізняють послідовні і паралельні коди. При послідовних кодах елементарні сигнали, що передають кодову комбінацію посилаються в канал передачі послідовно в часі. Вони можуть бути розділені часовим інтервалом або опитуватися в певні моменти часу (наприклад, як у послідовному інтерфейсі RS - 232 C).
Для паралельних кодів потрібні багатопровідні канали, тому при передачі інфрмації на значну відстань вони використовуються рідко через великі затрати (наприклад, паралельний інтерфейс Centronics). Паралельне представлення найчастіше використовується коли потрібна висока швидкість передачі даних (Centronics – 80 – 120 Кбайт/сек, сучасні двонаправлені системи – до 250 Кбайт/сек).
По можливості виявлення та виправлення помилок розрізняють прості (примітивні) і коректуючі коди.
В простих кодах помилка у будь-якому елементі кодової комбінації приводить до неправильного прийому декодованого повідомлення.
Коректуючі коди дозволяють виявляти і усувати помилки у кодових комбінаціях.
По основних законах кодоутворення коди поділяються на комбінаторні (нечислові) і арифметичні (числові).
Комбінаторні коди будуються по законах теорії поєднань. Наприклад, код з m різних символів утворює кодові комбінації з n<m символів. Довжина коду постійна і рівна n, а можлива кількість кодових комбінацій
EMBED Equation.3 ;
Наприклад, комбінації з 3 по 2: a, b, c =>ab, ac, bc.
Арифметичні (числові, цифрові) коди базуються на системах числення і найчастіше використовуються в технічних системах.
1.2. Рівномірні прості цифрові коди.
Системи числення, на основі яких будуються цифрові коди, поділяються на позиційні і непозиційні.
В позиційних сисмтемах значення символа залежить від його позиції в ряду символів, що утворюють число. В непозиційних – ні. В позиційних системах значення кожного наступного розряду більше від попереднього в m раз (m – основа системи чиселення).
При цьому будь-яке n-розрядне число може бути представлене у вигляді суми
EMBED Equation.3
де: lі - значення і-го розрядного коефіцієнта.
Кількість можливих значень lі рівна m (від 0 до m-1).
Приклад: чотирьохрозрядне десяткове число 4752=4*103+7*102+5*101+2*100.
Максимальна кількість кодових комбінацій Nmax=mn.
На практиці в технічних системах найчастіше використовуються двійкові коди
EMBED Equation.3
де: li = 01; Nmax = 2n;
N=2010=0*25+1*24+0*23+1*22+0*21+0*20 (0101002)
Двійковий код зручний для обробки машиною, однак для оператора громіздкий, тому використовують вісімкову або шістнадцяткову системи з основою рівною 23 і 2 4 відповідно.
EMBED Equation.3
N=(0248)= (0000101002)
EMBED Equation.3
N=(01416)= (0000000101002)
Для запису шістнадцяткових чисел використовуються цифри 0-9 та букви А-F.
Складні коди.
Складні коди базуються на системах числення, що мають дві і більше основ. При такому кодуванні числа, задані в системі з основою q, записуються за допомогою цифр іншої системи числення з основою p<q.
Найбільш характерні двійково-десяткові коди. Вони використовуються як проміжні при переводі десяткових у двійкові та навпаки.
У двійково-десятковій системі числення основна система числення десяткова. Однак кожна цифра десяткового числа записується у вигляді чотирьохрозрядного двійкового числа.
Найбільш часто використовують чотирьохрозрядні двійкові вагові коди 8-4-2-1; 7-4-2-1; 5-1-2-1; 2-4-2-1. Так як з 16 комбінацій використовують 10, то код – надлишковий.
Приклад:
8 4 2 1 7 4 2 1 5 1 2 1 2 4 2 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
2 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0
3 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
4 0 1 0 0 0 1 0 0 0 1 1 1 0 1 0 0
5 0 1 0 1 0 1 0 1 1 0 0 0 1 0 1 1
6 0 1 1 0 0 1 1 0 1 0 0 1 1 1 0 0
7 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1
8 1 0 0 0 1 0 0 1 1 0 1 1 1 1 1 0
9 1 0 0 1 1 0 1 0 1 1 1 1 1 1 1 1
1.4. Рефлексні (відбиті) коди.
У простому (двійковому) коді при переході від одного числа до сусіднього може бути зміна цифр у кількох розрядах. Це може спричинити значні помилки при кодуванні неперервних повідомлень. Так, наприклад, кодування секторним перетворювачем кута при переході від 7 до 8 (1112 => 10002) тимчасово може дати значення 1111 (помилка у 2 рази).
Для усунення цього явища використовують спеціальні двійкові коди, у яких при переході від числа до числа міняється тільки один розряд. При цьому похибка за рахунок неоднозначності зчитування не буде перевищувати одиниці цього числа.
Одним з таких кодів є код Грея. Це непозиційний код, вага одиниці якого не визначається номером розряду. У цих кодах спостерігається симетричність відносно деякої осі відбиття – тобто ідентичність молодших розрядів. Звідси - “рефлексний код” (reflect – відбивати). У коді Грея вага одиниці у j-му розряді по абсолютній величині визначається формулою
Wj= EMBED Equation.3
Причому знак сумованих членів додатній для всіх непарних одиниць в числі (записаних у коді Грея зліва направо) і від’ємний для всіх парних
[1101101]г= EMBED Equation.3 - EMBED Equation.3 - EMBED Equation.3 + EMBED Equation.3 + EMBED Equation.3
=64+32+16+8+4+2+1-32-16-8-4-2-1-8-4-2-1+4+2+1+1=57
двійковий код код Грея двійковий код код Грея
0 0000 0000 8 1000 1100
1 0001 0001 9 1001 1101
2 0010 0011 10 1010 1111
3 0011 0010 11 1011 1110
4 0100 0110 12 1100 1010
5 0101 0111 13 1101 1011
6 0110 0101 14 1110 1001
7 0111 0100 15 1111 1000
1.5. Оптимальне (ефективне) кодування.
Ентропія джерела повідомлень визначається формулою
EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 EMBED Equation.3
де: EMBED Equation.3 - ймовірність появи xi з N символів алфавіту джерела. N – об’єм алфавіту джерела.
Теорема Шенона для каналу без завад: в каналі зв’язку без завад можна так перетворити послідовність символів джерела, що середня довжина символів коду буде як завгодно близька до ентропії джерела повідомлень.
Ентропія H(x) виступає кількісною мірою різноманітності повідомлень джерела і є його основною характеристикою. Ентропія джерела максимальна, якщо ймовірності повідомлень є рівними. Якщо одне повідомлення достовірне, а інші неможливі, то H(x)=0. Одиниця виміру ентропії – 1 біт. Це та невизначеність, коли джерело має однакову ймовірність двох можливих повідомлень (0 або 1).
Ентропія H(x) визначає середню кількість двійкових знаків, необхідних для кодування початкових символів джерела. Наприклад, для російських букв n=32=25. Якщо вони подаються рівномірно і незалежні між собою, то H(x)<5. Для російського літературного тексту H(x)=1.5 біт, для віршів H(x)=1 біт, а для телеграм H(x)=0.8 біт. Це означає, що при певному способі кодування на передачу букви може бути затрачено відповідно 1.5, 1, 0.8 двійкових символів.
Якщо символи нерівноімовірні і залежні, то ентропія буде менша від свого максимального значення Нmax(x)=log2N. При цьому можливе деяке більш економне (ефективне) кодування, при якому на кожен символ буде в середньому затрачено n*=H(x) символів коду. Коефіцієнт надлишковості визначається такою формулою
Кнадл=1-H(x)/Hmax(x)
Для характеристики досягнутого стиснення використовують коефіцієнт стиснення
Кстисн=Lпочат/Lстисн
Можна показати, що Кнадл>Кстисн.
Різні методи оптимального кодування базуються на зменшенні надлишковості викликаної неоднаковою апріорною ймовірностю символів або залежністю між порядком надходження символів.
В першому випадку для кодування використовується нерівномірний код - більш ймовірні символи мають коротший код, а менш ймовірні – довший.
В другому випадку переходять від кодування окремих символів до кодування їх груп. При цьому здійснюється укрупнення алфавіту джерела, через те N зростає. Загальна надлишковість укрупненого алфавіту при цьому не міняється. Однак, зменшення надлишковості обумовлене зменшенням різниці ймовірностей різних груп символів. Таким чином, процес кодування зводиться до двох операцій: укрупнення алфавіту і кодування оптимальним нерівномірним кодом.
Стиснення буває із втратами і без втрат. Втрати допустимі при стисненні аудіо-та відеоінформації (наприклад, MPEG - 20 до 1; MPEG3 - 100 до 1; TIFF - 10до 1 при 10% втрат, 100 до 1 при 20% втрат і т.д.).
1.6. Метод Хаффмана.
Метод полягає в побудові кодового дерева Хаффмана, положення символа на якому визначається частотою (ймовірністю) його появи. Реалізація методу здійснюється по таких кроках:
1. Всім символам ставиться у відповідність одна з вершин дерева.
2. Об’єднуємо дві вершини з мінімальними частотами і для нової вершини вказуємо сумарну частоту.
3. Переходимо на пункт 2, доки не об’єднаємо всі вершини.
4. Обходимо дерево і визначаємо розряди коду по такому правилу: перехід вліво – розряд =1, перехід вправо – розряд = 0 (рис.3).
Для програмної реалізації методу можна використати таку таблицю
c 22 22 22 26 32 42 58 100 01
e 20 20 20 22 26 32 42 00
h 16 16 16 20 22 26 111
l 16 16 16 16 20 110
a 10 10 16 16 100
k 10 10 10 1011
m4 6 10101
b 2 10110
0
1
1
0
1
1
0
0
1
1
1
0
a
k
m
b
e
c
h
l
58
32
16
16
42
22
20
26
10
16
10
6
4
2
100
Рис. 3.
2. Практична частина
Опис програмної реалізації
Алгоритм програмної реалізації можна подати у вигляді наступної блок-схеми:
SHAPE \* MERGEFORMAT Задання вхідного файлу.
Початок відліку таймера.
Кодування/декодування тексту
Відкриття файлу, зчитування вмістимого у буфер
Запис кодованого/декодованого тексту у вихідний файл
Кінець відліку таймеру
Рис. 2.1.1. Алгоритм програмної реалізації
Розглянемо ці п’ять частин програми детальніше:
1. Задання вхідного файлу. Початок відліку таймера.
На цьому етапі користувач безпосередньо взаємодіє із інтерфейсом програми, тобто він має змогу ввести ім’я вхідного файлу, а також опцію, для кодування/декодування файлу:
-e – якщо файл потрібно декодувати. Якщо файл потрібно кодувати, то додаткових опцій не потребується.
Для ведення статистики, запускаємо таймер, який буде працювати весь час роботи програми.
Відкриття файлу, зчитування вмістимого у буфер
спроба відкрити вказаний файл
якщо спроба вдала, то виділяється пам’ять під буфер та записується у нього вмістиме файлу.
Кодування/декодування тексту
якщо вказана опція декодування файлу, то викликається функція EncodeText
здійснюється перевірка чи файл дійсно кодований haf.exe
отримуємо попередню назву файлу
отримуємо довжину словника
зчитуємо словник
розкодовуємо текст
якщо файл треба розкодувати, то викликається функція CodeText
формуємо список символів із частотами
викликаємо функцію GetHC, яка закодовує кожен символ відповідним кодом Хаффмана
записуємо заголовок haf-файлу, попереднє ім’я файлу, довжину словнику, та власне сам словнику вихідний буфер
скануємо текст, та записуємо коди символів у вихідний буфер
Запис кодованого/декодованого тексту у вихідний файл
- вихідний буфер даних записуємо у вихідний файл. Якщо відбувалось кодування, то до назви файла додаємо розширення haf.
5. Кінець відліку таймеру
- виключаємо таймер, виводимо відповідні показники таймеру на екран
2.2. Числовий приклад
haf.exe sky.jpg
Begin time: 15:48:12.922
End time: 15:48:31.429
Вхідний файл – sky.jpg
Вхідний розмір файлу – 23978
Вихідний файл – sky.haf
Вихідний розмір файлу - 187440
haf.exe sky.haf /e
Begin time: 15:49:51.574
End time: 15:50:2.59
Вхідний файл – sky.haf
Вхідний розмір файлу – 187440
Вихідний файл – sky.jpg
Вихідний розмір файлу - 23978
haf.exe errlook.exe
Begin time: 16:0:14.39
End time: 16:0:47.948
Вхідний файл – errlook.exe
Вхідний розмір файлу – 36864
Вихідний файл – errlook.haf
Вихідний розмір файлу - 146334
haf.exe errlook.haf /e
Begin time: 16:2:44.916
End time: 16:2:53.48
Вхідний файл – errlook.haf
Вхідний розмір файлу – 146334
Вихідний файл – errlook.exe
Вихідний розмір файлу - 36864
haf.exe man.htm
Begin time: 16:4:49.15
End time: 16:8:18.897
Вхідний файл – man.htm
Вхідний розмір файлу – 99618
Вихідний файл – man.haf
Вихідний розмір файлу - 478824
haf.exe man.haf /e
Begin time: 16:10:1.244
End time: 16:10:36.14
Вхідний файл – man.haf
Вхідний розмір файлу – 478824
Вихідний файл – man.htm
Вихідний розмір файлу - 99618
2.3. Аналіз результатів
Час кодування – 18507 мс
Час декодування – 13016 мс
Розмір файлу - 23978
Коефіцієнт збільшення розміру – 7,8
Час кодування – 33552 мс
Час декодування – 8524 мс
Розмір файлу - 36864
Коефіцієнт збільшення розміру – 4,0
Час кодування – 209747 мс
Час декодування – 34996 мс
Розмір файлу - 99618
Коефіцієнт збільшення розміру – 4,8
3.Висновки
Темою даної курсової роботи є розробка програми для кодування файлів за допомогою метода Хаффмана. Метод полягає в побудові кодового дерева Хаффмана, положення символа на якому визначається частотою (ймовірністю) його появи. Код Хаффмана є нерівнозначним кодом, тобто, для розкодування послідовності бітів, яка є закодована кодом Хаффмана, недостатньо лише самої послідовності. Тобто це означає, що разом із самою послідовністю, потрібно передавати, або створений словник, який складається із символів, та відповідно їх кодів, або передавати кодове дерево. Передача готового словнику, як додаткової інформації є більш оптимальною з огляду, на швидкодію, оскільки, не треба по кодовому дереві формувати знову цей словник. Тобто раз сформувавши, ми вже користуємось ним. Також, якщо подивитися на довжину словника, та на довжину кодового дерева, яке по суті являє собою структуру даних, яка містить символи, та їх відповідні частоти, то виявиться, що довжина словника є не набагато меншою, за кодове дерево. Отже в цьому плані передача словника є більш ефективнішою.
4. Список використаної літератури
Цымбал В.П. Теория информации и кодирование.: - К.: Вища школа, 1992.
Лагутин О.И. Модемы. Справочник пользователя –СПб.:”Лань”,1997.
У.Титце, К. Шенк. Полупроводниковая схемотехника.: - М.: Мир, 1982..
Додаток
Файл haf.cpp
#include "lab2.h"
TCHAR szFileName[1024] = { 0 };
long lzi=0;
long *lpzc;
int nOTLen = 0;
// Кодування тексту
BOOL CodeText(TCHAR *szInputText, TCHAR *szOutputText, DWORD dwSize, TCHAR *szFileName, BOOL bCompress = FALSE) {
// Формування списку символів із частотами
long uiLen = dwSize;
sList *list = new sList[uiLen];
for (int i=0; i<uiLen; i++) {
list[i].cSymbol = szInputText[i];
list[i].uiIntens = 1;
}
for (i=0; i<uiLen; i++) {
if (list[i].uiIntens)
for (int j=0;j<uiLen; j++) {
if (list[j].uiIntens)
if (i!=j)
if (list[i].cSymbol == list[j].cSymbol) {
list[i].uiIntens++;
list[j].uiIntens = 0;
}
}
}
int n=0;
for (i=0;i<uiLen; i++) if (list[i].uiIntens > 0) n++;
sList *list2 = new sList[n];
int k=0;
for (i=0; i<uiLen; i++)
if (list[i].uiIntens > 0) {
list[i].cSymbol;
list2[k] = list[i];
k++;
}
// Отримуємо код кожного символу
STC *pStc = GetHC(list2, n);
// Записуємо заголовок haf-файлу: Н + ' ' + <ім'я файлу> + ' ' <довжина словнику> + ' ' + словник
lpzc = new long[dwSize];
if (bCompress) {
wsprintf(szOutputText, "P%s %c", szFileName, n-1);
for (i=0; i<n; i++) {
TCHAR szTemp[1024] = { 0 };
if (pStc[i].cSym == 0) {
lpzc[lzi++] = strlen(szOutputText);
wsprintf(szTemp, " %c%c", (unsigned char)BSToI(pStc[i].pcHC), (unsigned char)lstrlen(pStc[i].pcHC));
} else {
wsprintf(szTemp, "%c%c%c", pStc[i].cSym, (unsigned char)BSToI(pStc[i].pcHC), (unsigned char)lstrlen(pStc[i].pcHC));
}
lstrcat(szOutputText, szTemp);
}
// Записуємо закодований текст
TCHAR *szHC = new TCHAR[dwSize*20];
lstrcpy(szHC, "");
for (i=0; i<uiLen; i++) {
for (int j=0; j<n; j++) {
if (szInputText[i]==pStc[j].cSym) {
lstrcat(szHC, pStc[j].pcHC);
break;
}
}
}
DWORD z = (lstrlen(szHC)%8) ? 8-lstrlen(szHC)%8 : 0;
for (i=0; i<z; i++) lstrcat(szHC, "0");
DWORD nHCLen = lstrlen(szHC);
for (DWORD dwI=0; dwI<nHCLen; dwI+=8) {
TCHAR szTemp[9] = { 0 };
for (DWORD dwJ=dwI; dwJ<dwI+8;dwJ++) {
TCHAR szTemp2[2] = { 0 };
wsprintf(szTemp2, "%c", (unsigned char)szHC[dwJ]);
lstrcat(szTemp, szTemp2);
}
TCHAR szT[2] = { 0 };
wsprintf(szT, "%c", (unsigned char)BSToI(szTemp));
lstrcat(szOutputText, szT);
}
TCHAR szZ[2] = { 0 };
wsprintf(szZ, "%c", z);
lstrcat(szOutputText, szZ);
} else {
wsprintf(szOutputText, "H %s %d ", szFileName, n);
for (i=0; i<n; i++) {
TCHAR szTemp[1024] = { 0 };
if (pStc[i].cSym == 0) {
lpzc[lzi++] = strlen(szOutputText);
wsprintf(szTemp, " %s ", pStc[i].pcHC);
} else {
wsprintf(szTemp, "%c%s ", pStc[i].cSym, pStc[i].pcHC);
}
lstrcat(szOutputText, szTemp);
}
// Записуємо закодований текст
for (i=0; i<uiLen; i++) {
for (int j=0; j<n; j++) {
if (szInputText[i]==pStc[j].cSym) {
lstrcat(szOutputText, pStc[j].pcHC);
break;
}
}
}
}
return TRUE;
}
// Декодування тексту
BOOL EncodeText(TCHAR *szInputText, TCHAR *szOutputText, DWORD dwSize, BOOL bCompress = FALSE) {
// Перевірка чи файл дійсно кодований haf
if (szInputText[0] == 'H') {
// Отримуємо попередню назву файлу
int i=1;
TCHAR szT[1024] = { 0 };
for (int k=0; szInputText[i+1] != 32; k++, i++) szT[k] = szInputText[i+1];
lstrcpy(szFileName, szT);
// Отримуємо довжину словника
TCHAR szVocSize[1024] = { 0 };
for (k=0, i++; szInputText[i+1] != 32; k++, i++) szVocSize[k] = szInputText[i+1];
int nVS = atol(szVocSize);
STC *sVoc = new STC[nVS];
i++;
// Зчитуємо словник
for (int j=0; j<nVS; j++, i+=2) {
for (int l=0; l<200; l++) sVoc[j].pcHC[l] = '\0';
sVoc[j].cSym = szInputText[i+1];
for (int k=0; szInputText[i+2] != 32; k++, i++) sVoc[j].pcHC[k] = szInputText[i+2];
}
// Розкодовуємо текст
lpzc = new long[dwSize];
lstrcpy(szOutputText, "");
for (j=i+1; j<dwSize; j++) {
for (int k=0; k<nVS; k++) {
TCHAR szTemp[1024] = { 0 };
for (int p=0; p<strlen(sVoc[k].pcHC); p++) szTemp[p] = szInputText[j+p];
if (!lstrcmp(sVoc[k].pcHC, szTemp)) {
if (sVoc[k].cSym == 0) {
lpzc[lzi++] = nOTLen;
szOutputText[nOTLen] = 32;
} else szOutputText[nOTLen] = sVoc[k].cSym;
nOTLen++;
j+=p-1;
break;
}
}
}
} else if (szInputText[0] == 'P') {
// Отримуємо попередню назву файлу
int i=0;
TCHAR szT[1024] = { 0 };
for (int k=0; szInputText[i+1] != 32; k++, i++) szT[k] = szInputText[i+1];
lstrcpy(szFileName, szT);
// Отримуємо довжину словника
int nVS = int(szInputText[i+2])+257;
STC *sVoc = new STC[nVS];
i+=2;
// Зчитуємо словник
for (int j=0; j<nVS; j++) {
for (int l=0; l<200; l++) sVoc[j].pcHC[l] = '\0';
sVoc[j].cSym = szInputText[i++];
IToBS(szInputText[i++]+128, sVoc[j].pcHC);
}
TCHAR *szHC = new TCHAR[dwSize*20];
lstrcpy(szHC, "");
for (j=i; j<dwSize; j++) {
TCHAR szTemp[9] = { 0 };
IToBS(szInputText[j]+128, szTemp);
TCHAR szTemp2[9] = { 0 };
for (int y=0; y<8-lstrlen(szTemp);y++) lstrcat(szTemp2, "0");
lstrcat(szHC, szTemp2);
lstrcat(szHC, szTemp);
}
int z = int(szInputText[dwSize-1]);
DWORD dwHCLen = lstrlen(szHC);
// Розкодовуємо текст
lpzc = new long[dwSize];
lstrcpy(szOutputText, "");
for (j=0; j<dwHCLen-z; j++) {
for (int k=0; k<nVS; k++) {
TCHAR szTemp[1024] = { 0 };
for (int p=0; p<strlen(sVoc[k].pcHC); p++) szTemp[p] = szHC[j+p];
if (!lstrcmp(sVoc[k].pcHC, szTemp)) {
if (sVoc[k].cSym == 0) {
lpzc[lzi++] = nOTLen;
szOutputText[nOTLen] = 32;
} else szOutputText[nOTLen] = sVoc[k].cSym;
nOTLen++;
j+=p;
break;
}
}
}
} else {
cout << " Error: Specified file is not valid Haffmann-coded." << endl;
return FALSE;
}
return TRUE;
}
int main (int argc, TCHAR *argv[]) {
if (argc < 2 || argc > 3) {
cout << " haf.exe - program to code/encode files using Haffmann coding" << endl;
cout << " Copyright (C) 2003 by Roman Zaharjuk, Lviv" << endl;
cout << " Usage: haf.exe [FileName] [/e] [/p]" << endl;
cout << " [FileName] - name of file you want to code/encode" << endl;
cout << " [/e] - to encode the specified file" << endl;
cout << " [/p] - additional option: to compress/uncompress while coding/encoding" << endl;
return 0;
}
SYSTEMTIME stBeg = { 0 };
GetLocalTime(&stBeg);
// Відкриваємо вхідний файл
lstrcpy(szFileName, argv[1]);
HANDLE hFile = CreateFile(szFileName, GENERIC_READ, 0, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, 0);
if (hFile == INVALID_HANDLE_VALUE) {
cout << " Error: Cannot open specified file." << endl;
return 0;
}
DWORD dwSize = GetFileSize(hFile, 0);
TCHAR *szInputText = new TCHAR[dwSize];
if (!szInputText) {
cout << " Error: Cannot allocate memory." << endl;
return 0;
}
// Зчитуємо дані у буфер
DWORD dwRead = 0;
ReadFile(hFile, szInputText, dwSize, &dwRead, NULL);
CloseHandle(hFile);
TCHAR *szOutputText;
if (argc == 3) {
if (!lstrcmp(argv[2], "/e")) {
szOutputText = new TCHAR[dwSize*2];
if (!szOutputText) {
cout << " Error: Cannot allocate memory." << endl;
return 0;
}
if (EncodeText(szInputText, szOutputText, dwSize)) {
} else return 0;
} else
if (!lstrcmp(argv[2], "/p")) {
szOutputText = new TCHAR[dwSize*2];
if (!szOutputText) {
cout << " Error: Cannot allocate memory." << endl;
return 0;
}
if (CodeText(szInputText, szOutputText, dwSize, szFileName, TRUE)) {
wsprintf(strrchr(szFileName, TEXT('.')) + 1, "haf");
} else return 0;
} else {
cout << " Error: Invalid parameter " << argv[2] << "."<< endl;
return 0;
}
} else {
szOutputText = new TCHAR[dwSize*20];
if (!szOutputText) {
cout << " Error: Cannot allocate memory." << endl;
return 0;
}
if (CodeText(szInputText, szOutputText, dwSize, szFileName)) {
wsprintf(strrchr(szFileName, TEXT('.')) + 1, "haf");
} else return 0;
}
// Відкриваємо вихідний файл
HANDLE hOutFile = CreateFile(szFileName, GENERIC_WRITE, 0, NULL, CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, 0);
if (hOutFile == INVALID_HANDLE_VALUE) {
cout << " Error: Cannot create output file." << endl;
return 0;
}
// Записуємо отриманий буфер у файл
DWORD dwWrite;
if (!nOTLen) nOTLen = lstrlen(szOutputText);
WriteFile(hOutFile, szOutputText, nOTLen, &dwWrite, NULL);
CloseHandle(hOutFile);
// Проставляємо в файлі 0-ві символи
ofstream o_file(szFileName, ios::ate);
if (!o_file) {
cout << " Error: Cannot create output file." << endl;
return 0;
}
for (int i=0; i<lzi; i++) {
o_file.seekp(lpzc[i], ios::beg);
o_file << char(0);
}
SYSTEMTIME stEnd = { 0 };
GetLocalTime(&stEnd);
cout << " Begin time: " << stBeg.wHour << ":" << stBeg.wMinute << ":" << stBeg.wSecond << "." << stBeg.wMilliseconds << endl;
cout << " End time: " << stEnd.wHour << ":" << stEnd.wMinute << ":" << stEnd.wSecond << "." << stEnd.wMilliseconds << endl;
return (0);
}
файл haf.h
include <string.h>
#include <fstream.h>
#include <windows.h>
#include <math.h>
struct sList {
int cSymbol;
unsigned int uiIntens;
};
struct TREE {
TREE *pR;
TREE *pL;
char cSym;
char pcHC[200];
int iInten;
bool bCoded;
};
struct STC {
char cSym;
char pcHC[200];
};
int nSTCCount = 0;
void CopyTN(TREE *t1, TREE *t2) { // Ф-ія копіювання еементів дерева
t1->pL = t2->pL;
t1->pR = t2->pR;
t1->iInten = t2->iInten;
t1->cSym = t2->cSym;
t1->bCoded = t2->bCoded;
strcpy(t1->pcHC, t2->pcHC);
}
void STV(TREE *pTree, char *pcValue) { // Ф-ія формування коду
if (pTree->pR != NULL) STV(pTree->pR, pcValue);
if (pTree->pL != NULL) STV(pTree->pL, pcValue);
if (pTree->bCoded) strcat(pTree->pcHC, pcValue);
}
void GTV(TREE *pTree, STC *pStc) { // Ф -ія обходу дерева
if (pTree->pR != NULL) GTV(pTree->pR, pStc);
if (pTree->pL != NULL) GTV(pTree->pL, pStc);
if (pTree->bCoded) {
pStc[nSTCCount].cSym = pTree->cSym;
_strrev(pTree->pcHC);
strcat(pStc[nSTCCount].pcHC, pTree->pcHC);
nSTCCount++;
}
}
void GetTree(TREE **pTree, int n) {
if (n<2) return;
// Сортуємо активні елементи дерева
for (int i=0; i<n; i++) {
for (int j=0;j<n-1; j++) {
if (pTree[i]->iInten > pTree[j]->iInten) {
TREE *TT = new TREE;
CopyTN(TT, pTree[i]);
CopyTN(pTree[i], pTree[j]);
CopyTN(pTree[j], TT);
delete TT;
}
}
}
// Створюємо нову структуру TREE та присвоюємо їй значення передостаннього елементу
TREE *nTree = new TREE;
CopyTN(nTree, pTree[n-2]);
// Передостанній елемент TREE стає сумою передостаннбого та останнього
pTree[n-2]->pR = nTree;
pTree[n-2]->pL = pTree[n-1];
pTree[n-2]->cSym = '\0';
pTree[n-2]->iInten += pTree[n-1]->iInten;
pTree[n-2]->bCoded = FALSE;
strcpy(pTree[n-2]->pcHC, "");
// Елементам правої гілки до коду додається 1, а лівої - 0
STV(pTree[n-2]->pR, "1");
STV(pTree[n-2]->pL, "0");
// Будуємо дерево, доки не залишиться 1 елемент
n--;
GetTree(pTree, n);
}
STC *GetHC(sList *list, int n) {
TREE **pTree = new TREE*[n];
STC *pStc = new STC[n]; // Формуємо всі нижні гілки дерева
for (int i=0; i<n; i++) {
pTree[i] = new TREE;
pTree[i]->pL = pTree[i]->pR = NULL;
strcpy(pTree[i]->pcHC, "");
strcpy(pStc[i].pcHC, "");
pTree[i]->cSym = list[i].cSymbol;
pTree[i]->iInten = list[i].uiIntens;
pTree[i]->bCoded = TRUE;
}
GetTree(pTree, n); // Створюємо дерево
GTV(pTree[0], pStc); // Обходимо нижні гілки і переписуємо коди у вектор
return pStc;
}
int BSToI(char *szText) {
int iValue = 0;
int nLen = strlen(szText);
for (int i=0; i<nLen; i++)
iValue += pow(2, nLen-i-1)*(szText[i]-'0');
return iValue;
}
void IToBS(int iValue, char *szRes) {
int k=1;
for (int i=0; k<iValue; i++, k*=2);
for (int j=i; j!=0; j--) {
if (pow(2, j-1) <= iValue) {
iValue -= pow(2, j-1);
lstrcat(szRes, "1");
}else lstrcat(szRes, "0");
}
}
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора