Теоретическое обоснование метода Лавинского
Данный метод предполагает сжатие последовательности чисел путём разбиения последовательности на равномерные интервалы и отыскание числа не в его натуральном виде путем перебора всех подряд, а с помощью порядкового номера отсчета от ближайшей границы.
Сам метод состоит в следующем. Пусть имеем некоторое количество чисел М и максимальное по длине число 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.
Программная реализация
Для разработки программы был выбран язык программирования высокого уровня 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.
Приложение Б