3. Выбор и обоснование решения задачи

 

4. Теоретическое обоснование метода Лавинского

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

Сам метод состоит в следующем. Пусть имеем некоторое количество чисел М и максимальное по длине число L. Очевидно, что для хранения в натуральном виде этих чисел необходимо следующее количество ячеек

Q = M * log 2 L (1)

Лавинский предложил множество М разбить на N интервалов. Интервалы между собой равные и тогда очевидно, что для хранения самих чисел необходим следующий объем памяти

Q’ = M * log 2 (L / N) (2)

И нам необходимо хранить информацию об этих самых границах

Q” = (M – 1) * log 2 (N - 1) (3)

В целом объем памяти необходимый для самих чисел и памяти будет следующим

Q = Q’ + Q” (4)


Взяв производную из (4), для нахождения оптимального разбиения последовательности и приравняв ее нулю, получим

N ОПТ = М / ln M (5)

Формула (5) определяет оптимальное количество интервалов. Для определения величины самого интервала мы все количество возможных вариантов относим к количеству самого интервала, то есть для определения количества символов в интервале используем следующую формулу

C = 2 [log2 N] / N (6)

Для нахождения самого интервала (номер границы) используем следующее отношение

К = Х / С (7),

где Х – искомое число в натуральном виде.

После этого само число записывается, как порядковый отсчет этой границы и определяет экономию памяти как

D Q = QИСХ – QОПТ (8)

Пусть интервал 128, Х = 200, тогда К = 1.56. К лежит 2> K> 1, значит код числа составит 200 – 127 = 73.


5 Программная реализация

Для разработки программы был выбран язык программирования высокого уровня Delphi 5.0 (Object Pascal).

Он весьма полно выражает идеи структурного программирования. Это проявляется в том, что Delphi может успешно использоваться для записи программ на разных уровнях ее детализации, не прибегая к помощи блок-схем или специального языка проектирования программ. Средства языка Delphi позволяют осуществлять достаточный контроль правильности использования данных различных типов и программных объектов как на этапе трансляции, так и на этапе ее выполнения.

Delphi позволяет без особых трудностей реализовать удобный пользовательский интерфейс, не пребегая к написанию низкоуровневого кода.

В программе есть так же возможность считать данные для кодирования из файла.


Заключение

В ходе выполнения курсовой работы были закреплены знания, полученные в ходе изучения дисциплины «Кодирование и защита информации». Работа выполнена в соответствии с постановкой задачи на курсовое проектирование.

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


Библиографический список

Конспект лекций по дисциплине “Кодирование и защита информации”.

Березюк Н. Т., Андрющенко А. Г., Мощинский С. С. и др. Кодирование информации – Харьков: Выща школа, 1978. – 252 с.

Кузьмин И. В., Кедрус В. А. Основы теории информации и кодирования. – Киев: Выща школа, 1977. – 280 с.

Цымбал В. П. Теория информации и кодирование. Киев, ”Вища школа”, 1997, 288 с.


Приложение А



uses

Forms,

Kizi in 'Kizi.pas' {Main};

{$R *.res}

begin

Application.Initialize;

Application.CreateForm(TMain, Main);

Application.Run;

end.

unit Kizi;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls,math;

type

TMain = class(TForm)

Button1: TButton;

Button2: TButton;

Button3: TButton;

fOpen: TOpenDialog;

fSave: TSaveDialog;

procedure Button3Click(Sender: TObject);

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Main: TMain;

f,f1:textfile;

i1:integer; // счетчик элементов (чисел) в файле

massivelementov: array [0..24]of longint;// сжимаемый массив

massivelementov1: array[0..3,0..4] of longint; //рабочий массив разбитый на интервалы

kolelementovfila:real;//количество элементов М

maxchislo:integer;// Максимальное число из М

chisloposled:integer; //Количество элементов в интервале

Interval:integer;//количество интервалов

kolmetok:integer;// количесьво меток

k:real;//флаг опред метки

polovina:real;//половина интервала

nomer:integer; // порядковый номер массива

granica:array of integer;//порядковый номер границы от нуля

mm:integer;

implementation

{$R *.dfm}

function DecToBin(dec:integer):string;

var

bin:string;

i:integer;

begin

bin:='';

for i:=1 to 8 do

begin

bin:=inttostr(dec mod 2)+bin;

dec:=dec div 2;

end;

DecToBin:=bin;

end;

function Bin24ToDec24(bin:string):integer;

var

i:integer;

dec:integer;

begin

if strlen(pchar(bin))<24 then

for i:=strlen(pchar(bin))+1 to 24 do

bin:='0'+bin;

dec:=0;

for i:=0 to 23 do

dec:=dec+trunc(strtoint(copy(bin,24-i,1))*intpower(2,i));

Bin24ToDec24:=dec;

end;

function Dec24ToBin24(dec:integer):string;

var

bin:string;

i:integer;

begin

bin:='';

for i:=1 to 24 do

begin

bin:=inttostr(dec mod 2)+bin;

dec:=dec div 2;

end;

Dec24ToBin24:=bin;

end;

procedure TMain.Button3Click(Sender: TObject);

begin

Main.close;

end;

procedure TMain.Button1Click(Sender: TObject);

var

c:char;

g,i,j:integer;

fileperem:array [0..9999] of char;

fileperem1:array [0..9999] of string;

flag1:integer;// счетчик символов в файле

flag2:integer;// счетчик элементов массива fileperem1

flag3:integer;//флаг содержания буквы в фмйле

flag4:integer;// флаг выхода из блока чтения из файла

flag5:integer;// условие увеличения флага flag2

metca:integer;//для определения значения интервла

outBuf: array[1..3] of Char;

outf: file of char;

outpos:integer;

outcomb:string;

tmp:char;

k:integer;

begin

// Чтение из файла

//---------------------------------------

fopen.Filter:='Текстовые файлы | *.txt';

fsave.Filter:='Архивированные файлы | *.arhi';

While flag4<>1 do

begin

i:=0;

flag4:=1;

if fopen.Execute then

begin

flag3:=0;

assignfile(f,fopen.filename);

reset(f);

for i:=0 to 9999 do fileperem[i]:=' ';

i:=0;

while (not eof(f)) and (i<100000) do

begin

read(f,c);

if (c<>' ')and((c<'0')or(c>'9'))and(c<>'-')and (c<>'+')and (c<>#13)and

(c<>#10 ) then

begin

if MessageDlg('Фаил содержит буквенный символ. Указать другой фаил?',

mtconfirmation,[mbYes,mbno],0) =mryes

then flag3:=1 else flag3:=11;

i:=1000000;

end else

begin

fileperem[i]:=c;

i:=i+1;

if i>99999 then

begin

showmessage('Фаил слишком большой');

flag3:=1;

i:=1000000;

end;

end;

end;

end;

if flag3=1 then

begin

flag3:=12;

flag4:=0;

end;

end;

//---------------------

// Забивка рабочего массива

//------------------------------

flag1:=0;

flag2:=0;

if (flag3=0) or (flag3=1) and (flag3<>11) then

begin

if flag3<>1 then

begin

while flag1<=i do

begin

while (fileperem[flag1]<>#13)and(fileperem[flag1]<>' ')and

(fileperem[flag1]<>#10) do

begin

fileperem1[flag2]:=fileperem1[flag2]+fileperem[flag1];

flag1:=flag1+1;

flag5:=1;

end;

flag1:=flag1+1;

if flag5=1 then

begin

flag2:=flag2+1;

flag5:=0;

end;

end;

kolelementovfila:=flag2;

{SetLength(massivelementov, trunc(kolelementovfila));

SetLength(massivelementov1, trunc(kolelementovfila));}

maxchislo:=strtoint(fileperem1[0]);

for i:=0 to trunc(kolelementovfila)-1 do

begin

massivelementov[i]:= strtoint(fileperem1[i]);

if maxchislo< massivelementov[i] then maxchislo:=massivelementov[i];

end;

end;

end;

//---------------------------------

// алгоритм кодирования

//---------------------------------

// определение колличества интервалов и числа символов в них

//---------------------------------

if (flag3=0) or (flag3=1) and (flag3<>11) then

begin

chisloposled:={trunc(kolelementovfila/trunc(ln(kolelementovfila)))+1}5;

Interval:={trunc(kolelementovfila/chisloposled)+1}5;

kolmetok:=trunc(Interval)-1;

SetLength(granica,kolmetok);

metca:=0;

for i:=0 to kolmetok-1 do

begin

granica[i]:=i;

end;

i:=0;

j:=0;

nomer:=0;

//кодирование

while J<=kolmetok-1 do

begin

massivelementov1[j,i]:=massivelementov[nomer]-trunc(granica[j])*150;

nomer:=nomer+1;

i:=i+1;

if i=chisloposled then

begin

{nomer:=0;}

J:=J+1;

i:=0;

end;

end;

closefile(f);

if fsave.Execute then

begin

AssignFile(outf,fsave.filename+'.arhi');

Rewrite(outf);

outpos:=0;

for i:=0 to kolmetok-1 do

for j:=0 to Interval-1 do

begin

tmp:=chr(granica[i]);

write(outf,tmp);

inc(outpos);

seek(outf,outpos);

outcomb:=dec24tobin24(massivelementov1[i,j]);

for k:=1 to 3 do

outbuf[k]:=chr(bin24todec24(copy(outcomb,k*8-7,8)));

for k:=1 to 3 do

begin

write(outf,outbuf[k]);

inc(outpos);

seek(outf,outpos);

end;

end;

CloseFile(outf);

end;

end;

end;

procedure TMain.Button2Click(Sender: TObject);

var inf: file of char;

outf:textfile;

inbuf:array[1..3] of char;

temp:string;

k:integer;

inpos:integer;

tmp:char;

massive,chislo,granica:integer;

begin

fopen.Filter:='Архивированные файлы | *.arhi';

fsave.Filter:='Текстовые файлы | *.txt';

if fopen.execute and fsave.execute then

begin

AssignFile(inf,fopen.Filename);

Reset(inf);

inpos:=0;

AssignFile(outf,fsave.Filename);

Rewrite(outf);

inpos:=0;

while not(eof(inf)) do

begin

read(inf,tmp);

inc(inpos);

Seek(inf,inpos);

granica:=ord(tmp);

for k:=1 to 3 do

begin

read(inf,inbuf[k]);

inc(inpos);

Seek(inf,inpos);

end;

temp:='';

for k:=1 to 3 do

temp:=temp+dectobin(ord(inbuf[k]));

massive:=bin24todec24(temp);

chislo:=massive+granica*150;

write(outf,inttostr(chislo),' ');

end;

closefile(outf);

closefile(inf);

end;

end;

end.


Приложение Б

Руководство пользователя

 

Для начала пользователь должен предварительно подготовить текстовый файл исходных данных (*.txt), в котором должен находиться массив чисел.

После за пуска программы(KiZI.ехе) на экране появится панель на которой находится три кнопки:

· Архивация

· Деархивация

· Выход

При нажатии кнопки «Архивация» появится окно «Открыть файл для архивации», где пользователю предложено выбрать текстовый файл с входными данными, если пользователем в файл с входными данными будет записан другой символ кроме числа, то программа выдаст ошибку: «Файл содержит буквенный символ. Указать другой файл?»

· при нажатии кнопки «Yes» пользователю будет предложено выбрать другой файл;

· при нажатии кнопки «No» пользователь будет возвращен в начальное меню;

Если файл, выбранный пользователем содержит корректные входные данные (числа), то программа предложит пользователю окно «Сохранить заархивированный файл», где пользователю нужно только выбрать папку куда файл нужно сохранить и ввести имя файла, расширение программа добавит сама (*.arhi). В этот файл программа запишет заархивированную информацию.

При нажатии кнопки «Деархивация» появится окно «Открыть файл для архивации», где пользователю предложено выбрать архивный файл, затем пользователю программа предложит окно «Сохранить заархивированный файл», где пользователю нужно выбрать только папку, куда нужно сохранить файл и ввести имя файла, расширение программа добавит сама (*.txt). В этот файл программа запишет разархивированную информацию.

При нажатии кнопки «Выход» программа заканчивает свою работу и происходит выход в операционную систему.

Программа производит сжатие информации примерно на 14%.


Информация о работе «Методы сжатия цифровой информации. Метод Лавинского»
Раздел: Информатика, программирование
Количество знаков с пробелами: 21170
Количество таблиц: 2
Количество изображений: 6

0 комментариев


Наверх