Чернега В.С. Сжатие информации в компьютерных сетях. Учебное пособие для вузов

Приложения

199

begin

ptr_table^[i].code_value:=-1;

i:=i+1;

end;

i:=0;

{-----------------------------------------------------}

read(inn,ch); {ввод символа}

string_code:=ord(ch); {string_code=коду символа}

WHILE not eof(inn) do {пока входной файл не пуст, делать:}

begin

{ввод символа и присвоение его кода переменной character}

read(inn, ch); character:=ord(ch);

inc(count);

if (count mod 1000)=0 then write('*');

{рассчитать индекс из строки string_code и символа character}

index:=find_match(string_code,character);

{если поля записи заняты, то string_code=коду строки,

которой занята запись}

if ptr_table^[index].code_value<>-1 then

string_code:=ptr_table^[index].code_value

else begin

{иначе: если таблица строк не заполнена, то занести строку

и ее код в таблицу}

if next_code<=MAX_CODE then

begin

ptr_table^[index].code_value:=next_code;

next_code:=next_code+1;

ptr_table^[index].prefix_code:=string_code;

ptr_table^[index].append_character:=character;

end;

write(out, string_code); {вывести код string_code в вых. файл}

string_code:=character;

end;

write(out, string_code); {вывести код string_code в вых.файл}

i:=MAX_VALUE-1;{ BITS двоичных единий - признак конца }

write(out, i); {занести в вых. файл признак конца сжатых данных}

i:=0;

write(out,i);

writeln;

{-------------------------------------------------------------}

{получить текущее время окончания компрессии }

Сжатие информации в компьютерных сетях

200

GetTime(chas2, min2, sek2, sot2);

writeln; {рассчитать время окончания компрессии }

write('Файл сжат за : '); Time; writeln;

close(inn); {закрыть файлы}

close(out);

dispose(ptr_table); {освободить память в "куче"}

{расчет коэффициента сжатия}

assign(v, input_file);

assign(b, out_file);

reset(v); reset(b);

c:=filesize(b)/filesize(v);

c:=(1-c)*100;

vbn:=round(c); {округление до целого}

{печать размеров файлов до и после сжатия и коэффициент сжатия}

writeln('Размер файла до сжатия : ', filesize(v),' b');

writeln('Размер файла после сжатия: ', filesize(b),' b');

if vbn>0 then

begin

vbn:=100-vbn;

writeln('Процент сжатия : ', vbn, ' %');

end

{если файл стал больше, чем был- печать сообщения об этом}

else begin

writeln;

writeln(' Невозможно сжать файл ', input_file); writeln;

writeln(' Размеp файла-pезультата больше, чем pазмеp исходного

файла.');

write(' Его уничтожить? (Y/N)');

ch:=readkey;

if (ch='y') or (ch='Y') then erase(out);

end;

writeln; writeln('Для выхода нажмите любую клавишу...'); writeln;

writeln('------------------------------------------------------------');

repeat until keypressed;

close(v); close(b);

End.

Приложения

201

Приложение 4

Программа декомпрессии файлов методом LZW

program Expand;

uses crt, dos;

{константы для hash-функции}

const BITS =13; {разрядность кодов строк }

TABLE_SIZE =9029; {max размер таблицы- больше 2^bits}

HASHING_SHIFT=BITS-8;

MAX_VALUE =1 shl BITS;

MAX_CODE =MAX_VALUE-2;

type

compress_type=0..MAX_CODE+1; {коды BITS разрядные }

{ Запись из двух полей:

каждая строка сохранена как prefix_code+append_character}

par=record

prefix_code : word;

append_character : byte;

end;

massiv_par=array [0..TABLE_SIZE] of par;

var

b,v : file of char;

count, c: word;

{next_code-равен коду, который будет присвоен следующей строке,

заносимой в таблицу; new_code-код символа только введенного

из входного файла; old_code-код строки, сформированный ранее}

new_code,old_code: compress_type;

{string_ - массив для декодирования строки}

string_ : array [0..4000] of word; {массив, имитирующий стек}

ind_buf,i : integer; {индекс массива string_}

s : char;

inn : file of compress_type;

out : text;

ptr_table : ^massiv_par; {указатель на запись par}

next_code, character_: word;

input_file, out_file : pathstr;

chas1, min1, sek1, sot1: word; {переменные для хранения текущего }

chas2, min2, sek2, sot2: word; {времени начала и конца компрессии }

{---------------------------------------------}

{процедура делит Code на prefix_code и append_character,

Сжатие информации в компьютерных сетях

202

затем append_character выводит в массив string_;

процесс повторяется до тех пор, пока code не станет <256

(пока он код строки, а не символа); когда он станет <256,

он заносится в массив и - выход. }

procedure decode_string(code: compress_type);

var i: integer;

begin

i:=1;

while code>255 do begin

string_[ind_buf]:=ptr_table^[code].append_character;

code:=ptr_table^[code].prefix_code;

inc(ind_buf);

if ind_buf>=4000 then

begin

writeln('Переполнение буфера стека...'); {переполнение буфера

стека}

halt(0);

end;

string_[ind_buf]:=code;

end;

{--------------------------------------------}

procedure Time; {процедура определения времени процесса}

{ Рассчитывается вычитанием времени начала процесса

(chas1, min1, sek1, sot1) из времени окончания

процесса (chas2, min2, sek2, sot2) }

begin

if sot2 < sot1 then

begin

sot2:=sot2+100;

dec(sek2);

end;

if sek2 < sek1 then

begin

sek2:=sek2+60;

dec(min2);

end;

if min2 < min1 then

begin

min2:=min2+60;

dec(chas2);

end;

Приложения

203

chas1:=chas2-chas1;

min1 := min2-min1;

sek1 := sek2-sek1;

sot1 := sot2-sot1;

if chas1<>0 then write(chas1, 'час.');

if min1 <>0 then write(min1, 'мин.');

write(sek1,'.', sot1, 'сек.');

End;

{---------------------------------------------}

Begin

{Ввод имен файлов и открытие их}

clrscr;

writeln('-------Программа декомпрессии файлов-----версия 3.0--------');

writeln;

case ParamCount of

0: begin

writeln ('expand [ Имя_декомпрессируемого_файла [ Имя_файла-

результата]]'); writeln;

write('Введите имя декомпрессируемого файла (*.lzw) : ');

readln(input_file);

write('Введите имя файла-результата (*.*): ');

readln(out_file); writeln;

if (length(input_file)=0) or (length(out_file)=0) then halt(0);

end;

1: begin

input_file:=ParamStr(1);

write('Введите имя файла-результата (*.*): ');

readln(out_file); writeln;

if (length(out_file)=0) then halt(0);

end;

2: begin

input_file:=ParamStr(1);

out_file:=ParamStr(2);

end;

else

begin

writeln ('expand [ Имя_декомпрессируемого_файла

[ Имя_файла-результата]]');

writeln;

halt(0);

end;

Сжатие информации в компьютерных сетях

204

count:=1;

assign(inn, input_file);

{$i-}

reset(inn);

{$i+}

if ioresult<>0 then

begin

writeln('Ошибка открытия файла ', input_file);

halt(0);

end;

assign(out, out_file);

{$i-}

rewrite(out);

{$i+}

if ioresult<>0 then

begin

writeln('Ошибка открытия файла ', out_file);

halt(0);

end;

writeln(' Декомпессия файла ', input_file);

{выделение места для массива в "куче", теперь обращение к

его записям возможно только через указатель}

New(ptr_table);

{получить текущее время начала декомпрессии }

GetTime(chas1, min1, sek1, sot1);

{-----------------------------------------------------}

next_code:=256; {исходная установка next_code}

read(inn,old_code); {ввод кода old_code}

character_:=old_code;

s:=chr(old_code); {преобразование кода в символ и печать его}

write(out, s);

repeat

{Выполнять ниже перечисленные действия, пока на входе есть коды

из сжатого файла}

begin

read(inn, new_code); nc(count); {ввод кода new_code}

if (count mod 1000)=0 then write('*');

IF new_code<>MAX_VALUE-1 THEN

begin

ind_buf:=1;

if new_code>=next_code then

begin

Приложения

205

{если new_code не определен в таблице, то декодировать в строку код

old_code}

decode_string(old_code);

string_[0]:=character_; {по алгоритму: string=string+character

т.е. добавить character к строке справа, т.к. в массиве строка

сохранена в обратном порядке, то мы ставим его крайним слева}

end

else

begin

{если код new_code определен в таблице,

то декодировать его в строку}

decode_string(new_code);

string_[0]:=0; {т.к. в этом случае ничего к строке

добавлять не надо, пишем туда 0}

end;

i:= ind_buf;

{вывести содержимое массива string_, содержащего

декодированную строку, в обратном порядке}

while ind_buf>0 do

begin

s:=chr(string_[ind_buf]);

write(out,s);

dec(ind_buf);

end;

if string_[0]<>0 then

begin {если=0? то этого элемента нет и его выводить не надо}

s:=chr(string_[0]);

write(out, s);

end;

character_:=string_[i]; {character равен первому символу

декодированной строки (последнему занятому в массиве)}

if next_code<MAX_CODE then

begin {если в таблице строк еще есть место, то

вносим в нее строку в виде old_code+character_}

ptr_table^[next_code].prefix_code:=old_code;

ptr_table^[next_code].append_character:=character_;

inc(next_code); {расчет кода для cтроки , которую надо будет

вносить в таблицу строки}

end;

old_code:=new_code;

END

ELSE i:=30000; {если new_code=BITS единиц, то конец декомпрессии}

Сжатие информации в компьютерных сетях

206

end;

until (i=30000);

{-------------------------------------------------------------}

writeln; {получить текущее время окончания декомпрессии }

GetTime(chas2, min2, sek2, sot2);

{определить время декомпрессии}

write('Время декомпрессии файла :'); Time; writeln;

close(inn); {закрыть файлы}

close(out); writeln;

dispose(ptr_table); {освободить память в куче}

{вывод объема файлов до и после декомпрессии}

assign(v, input_file);

assign(b, out_file);

reset(v); reset(b);

writeln('Размер файла до декомпрессии : ', filesize(v),' b');

writeln('Размер файла после декомпрессии : ', filesize(b),' b');

writeln; writeln('Для выхода нажмите любую клавишу...');

writeln;

writeln('------------------------------------------------------------');

repeat until keypressed;

close(v); close(b);

End.

Приложения

207

Пpиложение П5

Таблица модифициpованного кода Хаффмена

Длина

Завеpшающие кодовые слова

сеpии Белые сеpии Чеpные сеpии

0 0011 0101 0000 1110 11

1 0001 11 010

2 0111 11

3 1000 10

4 1011 011

5 1100 0011

6 1110 0010

7 1111 00011

8 10011 000101

9 10100 000100

10 00111 0000100

11 01000 0000101

12 0010 00 0000 111

13 0000 11 0000 0110

14 1101 00 0000 0111

15 1101 01 0000 1100 0

16 1010 10 0000 0101 11

17 1010 11 0000 0110 00

18 0100 111 0000 0010 00

19 0001 100 0000 1100 111

20 0001 000 0000 1101 000

21 0010 111 0000 1101 100

22 0000 011 0000 1101 111

23 0000 100 0000 1101 000

24 0101 000 0000 0010 111

25 0101 011 0000 0011 000

26 0010 011 0000 1100 1010

27 0100 100 0000 1100 1011

28 0011 000 0000 1100 1100

29 0000 0010 0000 1100 1101

30 0000 0011 0000 0110 1000

31 0001 1010 0000 0110 1001

32 0001 1011 0000 0110 1010

33 0001 0010 0000 0110 1011

Сжатие информации в компьютерных сетях

208

Пpиложение П5 (продолжение)

Длина Завершающие кодовые слова

серий Белые серии Черные серии

34 0001 0011 0000 1101 0010

35 0001 0100 0000 1101 0011

36 0001 0101 0000 1101 0100

37 0001 0110 0000 1101 0101

38 0001 0111 0000 1101 0110

39 0010 1000 0000 1101 0111

40 0010 1001 0000 0110 1100

41 0010 1010 0000 0110 1101

42 0010 1011 0000 1101 1010

43 0010 1100 0000 1101 1011

44 0010 1101 0000 0101 0100

45 0000 0100 0000 0101 0101

46 0000 0101 0000 0101 0110

47 0000 1010 0000 0101 0111

48 0000 1011 0000 0110 0100

49 0101 0010 0000 0110 0101

50 0101 0011 0000 0101 0010

51 0101 0100 0000 0101 0011

52 0101 0101 0000 0010 0100

53 0010 0100 0000 0011 0111

54 0010 0101 0000 0011 1000

55 0101 1000 0000 0010 0111

56 0101 1001 0000 0010 1000

57 0101 1010 0000 0101 1000

58 0101 1011 0000 0101 1001

59 0100 1010 0000 0010 1011

60 0100 1011 0000 0010 1100

61 0011 0010 0000 0101 1010

62 0011 0011 0000 0110 0110

63 0011 0100 0000 0110 0111

Чернега В.С. Сжатие информации в компьютерных сетях. Учебное пособие для вузов

Подождите немного. Документ загружается.