Кодирование (сжатие) данных

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Московский государственный институт электроники и математики (технический университет)

Кафедра «Математическое обеспечение систем обработки информации и управления»

Отчет к курсовой работе

по дисциплине «Теория информации и основы криптографии»

Работу выполнила

студентка группы М-82

Работу проверила

О.Л. Зуйкова

Москва 2011 г.



1. Задание

программа кодирование информация

Пусть источник информации (ИИ) генерирует тексты на английском языке. Считать, что буквы появляются независимо друг от друга с вероятностями, заданными в таблице 1. Выбрать для работы файл, содержащий английский текст объемом 3-5 страниц. Большие и малые буквы считать одинаковыми символами; символы, не встречающиеся в таблице, заменить пробелами.

Таблица 1. Таблица вероятностей английских букв

Пробел	е	т	а	о	n	i	s	r
0.180	0.097	0.076	0.064	0.062	0.057	0.056	0.052	0.047
h	l	d	с	u	f	m	w	y
0.040	0.031	0.028	0.025	0.018	0.018	0.017	0.016	0.015
b	g	v	k	q	x	j	z	p
0.013	0.013	0.007	0.039	0.002	0.002	0.001	0.001	0,018

Рассчитать (написать программу) методом Шеннона-Фано оптимальные двоичные коды сообщений данного источника информации. Таблицу кодов хранить в отдельном файле.

Для полученного кода рассчитать:

энтропию и избыточность ИИ,

среднее число символов кода на один символ алфавита ИИ,

избыточность кода,

ожидаемый коэффициент сжатия данных как отношение энтропии ИИ к энтропии кода в пересчете на один двоичный символ в памяти компьютера.

Написать программы, выполняющие кодирование и декодирование с помощью полученной таблицы кодов. Исходное сообщение берется из файла, результат также должен быть сохранен в файле. Для того, чтобы программа выполняла реальное сжатие, необходимо, чтобы каждый символ кода (0 или 1) занимали 1 бит памяти.

Выполнить кодирование (сжатие) данных для двух различных файлов: того, по которому считались вероятности и другого файла, содержащего подобный текст. В каждом случае сравнить объемы полученных файлов и определить практическую степень сжатия как отношение размеров полученного файла к исходному, сравнить ее с теоретической.

2. Таблицы кодов

Используя алгоритм двоичного кодирования по методу Шеннона-Фано, составим таблицу кодов для заданного алфавита ИИ:

xk	P(xk)	Подгруппы и их вероятности	коды
Пробел	0,180	0.691	0.353	0.180		000
E	0,097			0.173		0010
T	0,076					0011
A	0,064		0.338	0.183	0.064		0100
O	0,062				0.119		01010
N	0,057						01011
I	0,056			0.155	0.056		0110
S	0,052				0.099		01110
R	0,047						01111
H	0,040	0.664	0.163	0.079		1000
K	0,039					1001
L	0,031			0.084	0.031		1010
D	0,028				0.053		10110
C	0,025						10111
U	0,018		0.141	0.071	0.036		11000
P	0,018						11001
F	0,018				0.035		11010
M	0,017						11011
W	0,016			0.07	0.031		11100
Y	0,015						11101
B	0,013				0.039	0.026		111100
G	0,013							111101
V	0,007					0.013	0.007		111110
Q	0,002						0.006	0.004	0.002	11111100
X	0,002								0.002	11111101
J	0,001							0.002	0.001	11111110
Z	0,001								0.001	11111111

Полученная таблица будет записана в файл table.txt, который будут использовать кодер и декодер.

3. Результаты расчетов

Энтропия и избыточность ИИ

Пусть мы имеем источник информации Х с алфавитом:

Сообщения источника независимы, и появляются с вероятностями

Энтропия H(x) равна:

Максимальная энтропия равна:

Избыточность источника информации R:



Среднее число символов кода на один символ алфавита ИИ

Среднее число символов кода, необходимых для кодирования одного сообщения. Оно равно математическому ожиданию длины кодового слова.

,

где - длина кодового слова для сообщения

Избыточность кода

4. Ожидаемый коэффициент сжатия данных

Для записи одного символа ИИ используется n_и=8 двоичных - при кодировке ASCII. Тогда количество информации на один двоичный символ ИИ:

а количество информации на один двоичный символ кода:

Тогда коэффициент сжатия будет равен



Итак, мы получили теоретический коэффициент сжатия.

5. Тестовый пример кодирования и декодирования короткого сообщения

Имеется файл с таблицей кодов table.txt, в котором приведены коды всех символов русского языка в алфавитном порядке

Имеется файл с исходным текстом source.txt, содержание которого приведено в кавычках ниже:

«”Look at me, up in the tree”, said Tom»

В результате кодирования данного файла, мы получаем следующую последовательность нулей и единиц, разбитую по байтам:

00010100

10100101

01001000

01000011

00011011

00100000

00110001

10010000

11001011

00000110

11110010

00100000

00000011

10010001

10101100

00001101

01011011

Закодированный файл result.txt будет иметь следующий вид:

«hsиAЧА»ЏЧxЋЦ .…В3;». Здесь каждой восьмерке нулей и единиц соответствует один символ ASCII.

Декодер, использующий закодированный файл, восстанавливает информацию и создает файл restored.txt следующего содержания:

«look at me up in the tree said tom»

Как мы видим, большие буквы были заменены на маленькие, знаки препинания - на знак пробела.

Оценим результаты сжатия файла.

Исходный файл source.txt: 37 байт.

Закодированный файл result.txt 20 байт.

Восстановленный файл restored.txt 39 байт (два лишних пробела).

Итак, реальный коэффициент сжатия

Таким образом, данный пример демонстрирует правильность наших расчетов.

6. Результаты сравнения объемов исходных файлов и файлов после кодировки

Для того чтобы более точно определить реальный коэффициент сжатия файлов, рассмотрим еще два примера.

Пример 1.

Агата Кристи «Evil under the Sun»

Результаты сжатия:

Исходный файл 87896 байт

Закодированный файл 45956 байта

Реальный коэффициент сжатия превышает теоретический. Это можно объяснить наличием большого числа знаков препинания в обоих произведениях. Все знаки препинания кодируются лишь тремя двоичными битами.

Тем не менее, реальные коэффициенты сжатия все равно достаточно близки к теоретическому.



Заключение

В данной работе были рассчитаны оптимальные двоичные коды сообщений для заданного алфавита источника информации, написаны программы, реализующие кодирование и декодирование по этим кодам. Также было произведено сравнение практических результатов с теоретическими.

Полученный код является малоизбыточным. Данная избыточность возникает вследствие того, что сообщения источника невозможно разделить на абсолютно равновероятные группы.

Уменьшить избыточность можно, применив блочное кодирование. Однако это не принесет значительного увеличения коэффициента сжатия, хотя сильно усложнит таблицу кодов.



Приложение А

Кодер. Текст программы.

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <assert.h>

#pragma warning(disable: 4996)

typedef union

{

char symbol;

struct

{

unsigned bit0:1;

unsigned bit1:1;

unsigned bit2:1;

unsigned bit3:1;

unsigned bit4:1;

unsigned bit5:1;

unsigned bit6:1;

unsigned bit7:1;

}

bit;

}

code;

char ** codes = NULL;

code * result = 0;

int max_size = 0;

int result_i = 0, result_j = 0;

int code_num(char sym)

{

int num = 0;

if(sym == 'a' || sym == 'A')

num = 1;

else if(sym == 'b' || sym == 'B')

num = 2;

else if(sym == 'c' || sym == 'C')

num = 3;

else if(sym == 'd' || sym == 'D')

num = 4;

else if(sym == 'e' || sym == 'E')

num = 5;

else if(sym == 'f' || sym == 'F')

num = 6;

else if(sym == 'g' || sym == 'G')

num = 7;

else if(sym == 'h' || sym == 'H')

num = 8;

else if(sym == 'i' || sym == 'I')

num = 9;

else if(sym == 'j' || sym == 'J')

num = 10;

else if(sym == 'k' || sym == 'K')

num = 11;

else if(sym == 'l' || sym == 'L')

num = 12;

else if(sym == 'm' || sym == 'M')

num = 13;

else if(sym == 'n' || sym == 'N')

num = 14;

else if(sym == 'o' || sym == 'O')

num = 15;

else if(sym == 'p' || sym == 'P')

num = 16;

else if(sym == 'q' || sym == 'Q')

num = 17;

else if(sym == 'r' || sym == 'R')

num = 18;

else if(sym == 's' || sym == 'S')

num = 19;

else if(sym == 't' || sym == 'T')

num = 20;

else if(sym == 'u' || sym == 'U')

num = 21;

else if(sym == 'v' || sym == 'V')

num = 22;

else if(sym == 'w' || sym == 'W')

num = 23;

else if(sym == 'x' || sym == 'X')

num = 24;

else if(sym == 'y' || sym == 'Y')

num = 25;

else if(sym == 'z' || sym == 'Z')

num = 26;

else

num = 0;

return num;

}

int rar_symbol(char sym)

{

int sym_num;

int i = 0;

char digit;

sym_num = code_num(sym);

while((digit = codes[sym_num][i]) != ' ')

{

switch(result_j)

{

case 0:

{

if(digit == '0')

result[result_i].bit.bit0 = 0;

else

result[result_i].bit.bit0 = 1;

result_j ++;

break;

}

case 1:

{

if(digit == '0')

result[result_i].bit.bit1 = 0;

else

result[result_i].bit.bit1 = 1;

result_j ++;

break;

}

case 2:

{

if(digit == '0')

result[result_i].bit.bit2 = 0;

else

result[result_i].bit.bit2 = 1;

result_j ++;

break;

}

case 3:

{

if(digit == '0')

result[result_i].bit.bit3 = 0;

else

result[result_i].bit.bit3 = 1;

result_j ++;

break;

}

case 4:

{

if(digit == '0')

result[result_i].bit.bit4 = 0;

else

result[result_i].bit.bit4 = 1;

result_j ++;

break;

}

case 5:

{

if(digit == '0')

result[result_i].bit.bit5 = 0;

else

result[result_i].bit.bit5 = 1;

result_j ++;

break;

}

case 6:

{

if(digit == '0')

result[result_i].bit.bit6 = 0;

else

result[result_i].bit.bit6 = 1;

result_j ++;

break;

}

case 7:

{

if(digit == '0')

result[result_i].bit.bit7 = 0;

else

result[result_i].bit.bit7 = 1;

result_i ++;

result_j = 0;

break;

}

}

if(i < max_size-1)

i ++;

else

break;

}

return 0;

}

int main(void)

{

int current_size = 0, i = 0, k = 0, count = 0, result_size;

char c = ' ';

FILE * fp;

int cint = 0;

fp = fopen("table.txt", "rt");

while((c = fgetc(fp)) != EOF)

{

current_size ++;

if(c == '\n')

{

current_size = 0;

i ++;

}

if(current_size > max_size)

{

max_size = current_size;

k = i;

}

}

printf("Max size: %d(on %d string)\n", max_size, k + 1);

codes = malloc(32*sizeof(char*));

assert(codes);

for(i = 0; i < 32; i ++)

{

codes[i] = malloc(max_size*sizeof(char));

assert(codes[i]);

memset(codes[i], ' ', max_size);

}

fclose(fp);

fp = fopen("table.txt", "rt");

i = 0;

k = 0;

while((cint = fgetc(fp)) != EOF)

{

c = (char)cint;

if(c == '\n')

{

i ++;

k = 0;

}

else

{

codes[i][k] = c;

k ++;

}

}

fclose(fp);

fp = fopen("source.txt", "rb");

while((cint = fgetc(fp)) != EOF)

{

c = (char)cint;

//if(c != '\n')

count ++;

}

fclose(fp);

printf("Size of file: %d\n", count);

result_size = (int)(count*9)/8 + 1;

printf("Result size: %d\n", result_size);

result = malloc((int)sizeof(code)*result_size);

assert(result);

for(i = 0; i < result_size; i ++)

{

result[i].symbol = 0;

}

fp = fopen("source.txt", "rb");

while((cint = fgetc(fp)) != EOF)

{

c = (char)cint;

rar_symbol(c);

}

fclose(fp);

fp = fopen("binary.txt", "wt");

for(i = 0; i < result_i+1; i ++)

{

c = (char)(result[i].bit.bit0 + 48);

fputc(c, fp);

c = (char)(result[i].bit.bit1+48);

fputc(c, fp);

c = (char)(result[i].bit.bit2+48);

fputc(c, fp);

c = (char)(result[i].bit.bit3+48);

fputc(c, fp);

c = (char)(result[i].bit.bit4+48);

fputc(c, fp);

c = (char)(result[i].bit.bit5+48);

fputc(c, fp);

c = (char)(result[i].bit.bit6+48);

fputc(c, fp);

c = (char)(result[i].bit.bit7+48);

fputc(c, fp);

c = '\n';

fputc(c, fp);

}

fclose(fp);

fp = fopen("result.txt", "wb");

for(i = 0; i < result_i+1; i ++)

{

c = result[i].symbol;

fputc(c, fp);

}

fclose(fp);

return 0;

}



Приложение B

Декодер. Тексты программы

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <assert.h>

#pragma warning(disable: 4996)

typedef union

{

char symbol;

struct

{

unsigned bit0:1;

unsigned bit1:1;

unsigned bit2:1;

unsigned bit3:1;

unsigned bit4:1;

unsigned bit5:1;

unsigned bit6:1;

unsigned bit7:1;

}

bit;

}

code;

char ** codes = NULL;

code * result = 0;

int max_size = 0;

int result_i = 0, result_j = 0;

char find_symbol(char *buffer, int length)

{

int i = 0, j = 0, flag = 1, sym_num = -1;

char symbol = 0;

for(i = 0; i < 32; i ++)

{

flag = 1;

j = 0;

while(codes[i][j] != ' ' && j < max_size)

{

if(j > length)

{

flag = -1;

}

else

{

if(codes[i][j] != buffer[j])

{

flag = -1;

}

}

if(flag)

j ++;

else

break;

}

if(flag == 1)

{

sym_num = i;

if(sym_num == 1)

symbol = 'a';

else if(sym_num == 2)

symbol = 'b';

else if(sym_num == 3)

symbol = 'c';

else if(sym_num == 4)

symbol = 'd';

else if(sym_num == 5)

symbol = 'e';

else if(sym_num == 6)

symbol = 'f';

else if(sym_num == 7)

symbol = 'g';

else if(sym_num == 8)

symbol = 'h';

else if(sym_num == 9)

symbol = 'i';

else if(sym_num == 10)

symbol = 'j';

else if(sym_num == 11)

symbol = 'k';

else if(sym_num == 12)

symbol = 'l';

else if(sym_num == 13)

symbol = 'm';

else if(sym_num == 14)

symbol = 'n';

else if(sym_num == 15)

symbol = 'o';

else if(sym_num == 16)

symbol = 'p';

else if(sym_num == 17)

symbol = 'q';

else if(sym_num == 18)

symbol = 'r';

else if(sym_num == 19)

symbol = 's';

else if(sym_num == 20)

symbol = 't';

else if(sym_num == 21)

symbol = 'u';

else if(sym_num == 22)

symbol = 'v';

else if(sym_num == 23)

symbol = 'w';

else if(sym_num == 24)

symbol = 'x';

else if(sym_num == 25)

symbol = 'y';

else if(sym_num == 26)

symbol = 'z';

else if(sym_num == 0)

symbol = ' ';

return symbol;

}

}

return symbol;

}

int main(void)

{

int current_size = 0, i = 0, j = 0, k = 0, result_size = 0;

char c = ' ';

short int cint = 0;

char * buffer;

FILE * fp;

fp = fopen("table.txt", "rt");

assert(fp);

while((c = fgetc(fp)) != EOF)

{

current_size ++;

if(c == '\n')

{

current_size = 0;

i ++;

}

if(current_size > max_size)

{

max_size = current_size;

k = i;

}

}

codes = malloc(32*sizeof(char*));

assert(codes);

for(i = 0; i < 32; i ++)

{

codes[i] = malloc(max_size*sizeof(char));

assert(codes[i]);

memset(codes[i], ' ', max_size);

}

fclose(fp);

fp = fopen("table.txt", "rt");

i = 0;

k = 0;

while((c = fgetc(fp)) != EOF)

{

if(c == '\n')

{

i ++;

k = 0;

}

else

{

codes[i][k] = c;

k ++;

}

}

fclose(fp);

fp = fopen("result.txt", "rb");

assert(fp);

while((cint = fgetc(fp)) != EOF)

{

result_size ++;

}

fclose(fp);

result = malloc(sizeof(code)*result_size);

assert(result);

buffer = malloc(max_size);

memset(buffer, 0, max_size);

fp = fopen("result.txt", "rb");

assert(fp);

i = 0;

while((cint = fgetc(fp)) != EOF)

{

c = (char)cint;

result[i].symbol = c;

i ++;

}

fclose(fp);

fp = fopen("restored.txt", "wt");

k = 0;

for(i = 0; i < result_size; i ++)

{

for(j = 0; j < 8; j ++)

{

switch(j)

{

case 0:

{

if(result[i].bit.bit0 == 0)

buffer[k] = '0';

else

buffer[k] = '1';

break;

}

case 1:

{

if(result[i].bit.bit1 == 0)

buffer[k] = '0';

else

buffer[k] = '1';

break;

}

case 2:

{

if(result[i].bit.bit2 == 0)

buffer[k] = '0';

else

buffer[k] = '1';

break;

}

case 3:

{

if(result[i].bit.bit3 == 0)

buffer[k] = '0';

else

buffer[k] = '1';

break;

}

case 4:

{

if(result[i].bit.bit4 == 0)

buffer[k] = '0';

else

buffer[k] = '1';

break;

}

case 5:

{

if(result[i].bit.bit5 == 0)

buffer[k] = '0';

else

buffer[k] = '1';

break;

}

case 6:

{

if(result[i].bit.bit6 == 0)

buffer[k] = '0';

else

buffer[k] = '1';

break;

}

case 7:

{

if(result[i].bit.bit7 == 0)

buffer[k] = '0';

else

buffer[k] = '1';

break;

}

}

if((c = find_symbol(buffer, k+1)) != 0)

{

fputc(c, fp);

memset(buffer, 0, max_size);

k = 0;

}

else if(k < 9)

k ++;

if(k >=9)

break;

}

}

fclose(fp);

return 0;

}



Приложение С

Таблица кодов table.txt

000

0100

111100

10111

10110

0010

11010

111101

1000

0110

11111110

1001

1010

11011

01011

01010

11001

11111100

01111

01110

0011

11000

111110

11100

11111101

11101

11111111 Размещено на Allbest.ru

...