Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
МЕТОДИ ОПТИМАЛЬНОГО КОДУВАННЯ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра САПР
Інформація про роботу
Рік:
2007
Тип роботи:
Звіт про виконання лабораторної роботи
Предмет:
Проблемно-орієнтовані методи та засоби комп’ютерних інформаційних технологій
Група:
КН-316
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Кафедра САПР
ЗВІТ
про виконання лабораторної роботи №2
на тему:
«МЕТОДИ ОПТИМАЛЬНОГО КОДУВАННЯ»
З курсу «Проблемно-орієнтовані методи та засоби
комп’ютерних інформаційних технологій»
МЕТА РОБОТИ
Мета роботи – отримати практичні навики використання методів оптимального кодування.
КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Метод Шеннона-Фано
В цьому методі для кожного символа формується бітовий код, довжина якого залежить від частоти появи символа. Чим менша частота, тим довший код. Визначення частоти (ймовірності) символа буває статичне (на основі таблиці даних) та динамічне (коли відомості про ймовірність появи символів визначаються на основі обробки потоку даних). Статичний варіант використовується в архіваторах ARK, PKZIP.
Кодування здійснюється таким чином (рис. 1):
Всі символи записуються в таблицю по зменшенню їх частоти. Потім вони поділяються на дві групи так, щоб суми частот для отриманих груп були максимально близькі. Для першої групи перший біт коду встановлюється рівним 1, а для другої – 0.
Потім групи знову поділяємо на дві і визначаємо наступні розряди коду. Процес продовжується поки в групі не залишиться тільки один символ.
Номер Символ Частота Код
1 a 10 11
2 b 8 10
----------------------------- ----------------------------
3 c 6 011
4 d 5 010
5 e 4 001
6 f 3 000
Рис. 1.
Кодування Шеннона-Фано неоднозначне. В залежності від варіанту поділу на групи (при однаковій різниці частот між ними) будуть отримані різні коди для символів (рис. 2).
Символ Частота Код Символ Частота Код
с 22 11 с 22 11
e 20 101 e 20 10
h 16 100 --------------------------------------------
----------------------------------------------- h 16 011
i 16 011 і 16 010
a 10 010 a 10 001
k 10 001 k 10 0001
m 4 0001 m 4 00001
b 2 0000 b 2 00000
Рис. 2.
Можливий варіант програмної реалізації методу базується на формуванні і обробці такої таблиці
Nгр
Np
Nk
S
Код
1
1
2
18
1
3
6
18
0
2
1
1
10
11
2
2
8
10
3
3
4
11
01
5
6
7
00
4
3
3
6
011
4
4
5
010
5
5
5
4
001
6
6
3
000
Ця таблиця забезпечує зручний запис алгоритму поділу на підгрупи і формування кодів. Перша група (Nгр=1) складається з двох підгруп: перша - починається з першого символа (Np=1) і закінчується другим (Nк=2), друга – починається з третього символа (Nр=3) і закінчується шостим (Nк=6). Сума частот першої підгрупи S=18, другої S=18. Друга група (Nгр=2) формується в результаті поділу першої підгрупи з першої групи і складається теж з двох підгруп: перша – починається з першого символа (Nр=1) і ним закінчується (Nк=1), друга – починається другим символом (Nр=2) і ним закінчується (Nк=2). Третя група описує процес поділу другої підгрупи з першої групи. Процуес продовжується до тих пір поки кожна підгрупа не буде складатися тільки з одного символа (Nр=Nк). Відповідний новий біт коду кожної групи визначається таким чином: для першої підгрупи він встановлюється рівним одиниці, а для другої підгрупи – нулю.
Метод Хаффмана.
Метод полягає в побудові кодового дерева Хаффмана, положення символа на якому визначається частотою (ймовірністю) його появи. Реалізація методу здійснюється по таких кроках:
Всім символам ставиться у відповідність одна з вершин дерева.
Об’єднуємо дві вершини з мінімальними частотами і для нової вершини вказуємо сумарну частоту.
Переходимо на пункт 2, доки не об’єднаємо всі вершини.
Обходимо дерево і визначаємо розряди коду по такому правилу: перехід вліво – розряд =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
Індивідуальне завдання:
Варіант
2
Частота a
35
Частота b
35
Частота c
10
Частота d
8
Частота e
5
Частота f
5
Частота g
2
Текст програми:
#include <math.h>
#include <string.h>
#include <conio.h>
#include <stdio.h>
#include <iostream.h>
#define bool unsigned char
#define true 1
#define false 0
FILE *F;
long FileLength;
char Vux_f[20], Vx_f[20];
class TSymbol
{
public:
unsigned long Freq;
unsigned char Ch, NumBits;
bool Bits[256];
void Init(void)
{
Freq = 0;
NumBits = 0;
for(int i = 0;i < 256;i++) Bits[i] = 0;
Ch = 0;
}
TSymbol & operator =(TSymbol &S)
{
Freq = S.Freq;
NumBits = S.NumBits;
for(int i = 0;i < 256;i++) Bits[i] = S.Bits[i];
Ch = S.Ch;
return *this;
}
void SetBit(bool bit)
{
Bits[NumBits] = bit;
NumBits++;
}
}*Alph[256];
struct THaffmanNode
{
public:
THaffmanNode *Parent;
unsigned long Freq;
bool Bit;
THaffmanNode(int f = 0)
{
Parent = NULL;
Freq = f;
Bit = false;
}
THaffmanNode *Merge(THaffmanNode *N)
{
if(Freq > N->Freq){ Bit = true; N->Bit = false;}
else { Bit = false; N->Bit = true;}
Parent = new THaffmanNode(Freq + N->Freq);
N->Parent = Parent;
return Parent;
}
};
unsigned char b;
int NumSymbols;
void CalcFreqs(void)
{
int i,j;
NumSymbols = 0;
fseek(F,0,0);
for(i = 0;i < FileLength;i++)
{
fread(&b, 1,1, F);
for(j = 0;j < NumSymbols;j++)
if(b == Alph[j]->Ch)
{
Alph[j]->Freq++;
break;
}
if(j >= NumSymbols)
{
Alph[j] = new TSymbol();
Alph[j]->Init();
NumSymbols++;
Alph[j]->Ch = b;
Alph[j]->Freq++;
}
}
bool Sorted = false;
TSymbol Temp;
while(!Sorted)
{
Sorted = true;
for(i = 1;i < NumSymbols;i++)
if(Alph[i-1]->Freq < Alph[i]->Freq)
{
Temp = *Alph[i];
*Alph[i] = *Alph[i-1];
*Alph[i-1] = Temp;
Sorted = false;
}
}
}
void CodeHuffman(void)
{
THaffmanNode *Tree[550], *Min1, *Min2, *Curr;
int i,j,t, NumNodes = NumSymbols;
for(i = 0;i < NumSymbols;i++) Tree[i] = new THaffmanNode(Alph[i]->Freq);
for(;;)
{
Min1 = Min2 = NULL;
for(i = 0;i < NumNodes;i++)
if(Tree[i]->Parent == NULL)
{
if(Min1 == NULL || Tree[i]->Freq < Min1->Freq)
{
if(Min2 == NULL || Min1->Freq < Min2->Freq) Min2 = Min1;
Min1 = Tree[i];
}else if(Min2 == NULL || Tree[i]->Freq < Min2->Freq) Min2 = Tree[i];
}
if(Min2 == NULL)
{
if(Min1) Min1->Bit = true;
break;
}
Tree[NumNodes++] = Min1->Merge(Min2);
}
for(i = 0;i < NumSymbols;i++)
{
Alph[i]->NumBits = 0;
Curr = Tree[i];
do{
Alph[i]->SetBit(Curr->Bit);
Curr = Curr->Parent;
}while(Curr->Parent);
for(j = 0;j < Alph[i]->NumBits/2;j++)
{
t = Alph[i]->Bits[j];
Alph[i]->Bits[j] = Alph[i]->Bits[Alph[i]->NumBits-j-1];
Alph[i]->Bits[Alph[i]->NumBits-j-1] = t;
}
}
for(i = 0;i < NumNodes;i++) if(Tree[i]) delete Tree[i];
}
void CodeShenoFano(int Up, int Down)
{
if(Down-Up <= 1) return;
int i,j;
long CurrSum, HalfSum;
HalfSum = 0;
for(i = Up;i < Down;i++) HalfSum += Alph[i]->Freq;
HalfSum /= 2;
CurrSum = 0;
for(i = Up;i < Down;i++)
{
CurrSum += Alph[i]->Freq;
if(CurrSum > HalfSum)
{
if(abs(HalfSum - (CurrSum - Alph[i]->Freq)) < abs(HalfSum - CurrSum)) i--;
i++;
for(j = Up;j < i;j++)
Alph[j]->SetBit(true);
CodeShenoFano(Up, i);
for(j = i;j < Down;j++) Alph[j]->SetBit(false);
CodeShenoFano(i, Down);
break;
}
}
}
void Compress(void)
{
int i,j,k,N,t, HeaderOffset;
unsigned char mask, byte;
FILE *OF = fopen(Vux_f, "wb+");
if(OF == NULL)
{
perror(Vux_f);
return;
}
fseek(OF,0,0);
fwrite(&FileLength, sizeof(long),1,OF);
fwrite(&NumSymbols, 1,1,OF);
for(j = 0;j < NumSymbols;j++)
{
fwrite(&Alph[j]->Ch, 1,1,OF);
fwrite(&Alph[j]->NumBits, 1,1,OF);
N = (Alph[j]->NumBits > 0) ? Alph[j]->NumBits : 256;
if(N%8) N = ((int)(N/8)*8) + 8;
b = 0; t = 0;
for(i = 0;i < N;i++)
{
b <<= 1; if(Alph[j]->Bits[i]) b |= 1;
t++;
if(t >= 8)
{
fwrite(&b, 1,1,OF);
t = 0; b=0;
}
}
if(t > 0) fwrite(&b, 1,1,OF);
}
HeaderOffset = ftell(OF);
mask = 1;
byte = 0;
fseek(F,0,0);
for(i = 0;i < FileLength;i++)
{
fread(&b, 1,1, F);
for(j = 0;j < NumSymbols;j++)
if(Alph[j]->Ch == b)
{
for(k = 0;k < Alph[j]->NumBits;k++)
{
if(mask == 0){ mask = 1; fwrite(&byte, 1,1,OF);byte = 0;}
if(Alph[j]->Bits[k]) byte |= mask;
mask <<= 1;
}
break;
}
if(j >= NumSymbols)
{
printf("\nPomulka pru kodyvanni faily");
fclose(OF);
return;
}
}
fwrite(&byte, 1,1, OF);
fseek(OF,0,2);
printf("\nFail zakodovano");
}
void Decompress(void)
{
int i,j,k,n,NumBits;
bool SymbolFound;
FILE *OF = fopen(Vux_f, "wb+");
if(OF == NULL)
{
perror(Vux_f);
return;
}
fseek(F,0,0);
long NewFileLength;
fread(&NewFileLength, sizeof(long),1,F);
fread(&NumSymbols, 1,1,F);
NumSymbols = (NumSymbols > 0) ? NumSymbols : 256;
for(j = 0;j < NumSymbols;j++)
{
if(!Alph[j]) Alph[j] = new TSymbol();
fread(&Alph[j]->Ch, 1,1,F);
fread(&Alph[j]->NumBits, 1,1,F);
n = Alph[j]->NumBits / 8;
if(Alph[j]->NumBits % 8) n++;
for(i = 0;i < n;i++)
{
fread(&b, 1,1,F);
for(k = 0;k < 8;k++)
{
if(b & 1) Alph[j]->Bits[i*8+7-k] = true;
else Alph[j]->Bits[i*8+7-k] = false;
b >>= 1;
}
}
}
bool Buffer[512];
fseek(OF,0,0);
NumBits = 0;
for(i = ftell(F);i < FileLength;i++)
{
// Читання 8 бітів
fread(&b, 1,1, F);
for(j = NumBits;j < NumBits+8;j++)
{
if(b & 1) Buffer[j] = true;
else Buffer[j] = false;
b >>= 1;
}
NumBits += 8;
// пошук символа
while(NumBits >= 256)
{
for(j = 0;j < NumSymbols;j++)
{
SymbolFound = true;
for(k = 0;k < Alph[j]->NumBits;k++)
if(Alph[j]->Bits[k] != Buffer[k]){SymbolFound = false; break;}
if(SymbolFound)
{
for(k = 0;k < NumBits-Alph[j]->NumBits;k++)
Buffer[k] = Buffer[k+Alph[j]->NumBits];
NumBits -= Alph[j]->NumBits;
fwrite(&Alph[j]->Ch, 1,1, OF);
break;
}
}
if(j >= NumSymbols)
{
printf("Pomulka pru rozkodyvanni faily");
fclose(OF);
return;
}
}
}
while(NumBits >= 0 && NewFileLength > ftell(OF))
{
for(j = 0;j < NumSymbols;j++)
{
SymbolFound = true;
for(k = 0;k < Alph[j]->NumBits;k++)
if(Alph[j]->Bits[k] != Buffer[k]){SymbolFound = false; break;}
if(SymbolFound)
{
for(k = 0;k < NumBits-Alph[j]->NumBits;k++)
Buffer[k] = Buffer[k+Alph[j]->NumBits];
NumBits -= Alph[j]->NumBits;
fwrite(&Alph[j]->Ch, 1,1, OF);
break;
}
}
if(j >= NumSymbols)
{
printf("\nPomulka pru rozkodyvanni faily");
fclose(OF);
return;
}
}
printf("\nFail rozkodovano");
fclose(OF);
}
chactotu()
{
FILE *fp;
char buf[10000],cumvol[256];
char c;
int cum_kil[256],kil_c,i=0,j,e,por=1,r;
if ((fp=fopen(Vx_f,"r"))==NULL)
{
perror(Vx_f);
return 1;
}
while ((c=getc(fp))!=EOF)
{
i++;
buf[i]=c;
kil_c=i;
}
fclose(fp);
for (i=1;i<256;)
{
cumvol[i]=0;
cum_kil[i]=0;
i++;
}
cout <<"\nkilkict cumvoliv v faili "<<kil_c<<"\n";
i=1;
while (i<=kil_c)
{
e=0;
for (j=1;j<=256||e>1;)
{
if (buf[i]==cumvol[j])
{
e=1;
r=j;
}
j++;
}
if (e==0)
{
cumvol[por]=buf[i];
cum_kil[por]=cum_kil[por]+1;
por++;
}
else
{
cum_kil[r]=cum_kil[r]+1;
}
i++;
}
int b,d;
for (i=1;i<por-1;i++)
for (j=i+1;j<por;j++)
if (cum_kil[i]<cum_kil[j])
{
b=cum_kil[i];
d=cumvol[i];
cum_kil[i]=cum_kil[j];
cumvol[i]=cumvol[j];
cum_kil[j]=b;
cumvol[j]=d;
}
cout <<"cumvol i kilkict povtoren: ";
for (i=1;i<por;i++)
printf(" %c %d,",cumvol[i],cum_kil[i]);
cout <<"\nkilkict riznux cumvoliv "<<por-1<<"\n";
getch();
return 0;
}
void main(void)
{
clrscr();
printf("Vxidnui fail: ");
gets(Vx_f);
printf("\nVuxidnui fail: ");
gets(Vux_f);
for(int i = 0;i < 256;i++) Alph[i] = NULL;
printf("\nKodyvannia - 1");
printf("\nDekodyvannia - 2\n");
if(getche() == '1')
{
chactotu();
F = fopen(Vx_f,"rb");
if(F == NULL)
{
perror(Vx_f);
return;
}
fseek(F,0,2);
FileLength = ftell(F);
CalcFreqs();
printf("\nVubir metody kodyvannia:");
printf("\nShenona Fano - 1");
printf("\nXafmana - 2\n");
if(getche() == '1') CodeShenoFano(0, NumSymbols);
else CodeHuffman();
Compress();
}
else
{
F = fopen(Vx_f,"rb");
if(F == NULL)
{
perror(Vx_f);
return;
}
fseek(F,0,2);
FileLength = ftell(F);
Decompress();
}
fclose(F);
for(i = 0;i < 256;i++) if(Alph[i]) delete Alph[i];
getch();
}
Результати виконання:
Вміст вхідного файлу а.txt (91 Б)
аbabfcabccabcabcdefgdefgdefgabcbcaaaabcbcbcfgeeeabcffabcabcabdcadbccbadcdbdgacbdeabdebcca
Вміст файлу закодованого методом Шеннона-Фано (62 Б)
[bАcЂa`d@efgЮcѕ|>Ў€PDи;Ыѕ;„$}€>џWЦµ•t‹^ј
Вміст файлу закодованого методом Хаффмана (62 Б)
[bЂc@adрeаfАgШРФD#)IюНю›э7›LЂМњ}wдIТЛ§с~ї±?ъKYV
Висновок:
На даній лабораторній роботі я отримав практичні навики використання методів оптимального кодування, написав програму яка закодовує файли методами Хаффмана і Шеннона-Фано, а також розкодовує їх.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора