Алгоритм сжатия данных LZ77

Задание

1. Теоретическая часть

2. Описание использованных структур данных

3. Описание процедур/функций

4. Описание структуры приложения и интерфейса пользователя

5. Результаты тестирования приложения на разных объемах данных

6. Анализ работы алгоритма LZ77 и выводы Список использованных источников ПРИЛОЖЕНИЕ

Задание

Написать программу, которая сжимает данные по алгоритму LZ77 с пошаговой визуализацией.

программа алгоритм сжатие данные lz77

1. Теоретическая часть

В этой работе реализован алгоритм сжатия данных LZ77.

Алгоритм LZ77 был опубликован в 1977 г. Разработан израильскими математиками Якобом Зивом (Ziv) и Авраамом Лемпелом (Lempel). Многие программы сжатия информации используют ту или иную модификацию LZ77. Одной из причин популярности алгоритмов LZ является их исключительная простота при высокой эффективности сжатия.

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

LZ77 использует «скользящее» по сообщению окно, разделенное на две неравные части. Первая, большая по размеру, включает уже просмотренную часть сообщения. Вторая, намного меньшая, является буфером, содержащим еще незакодированные символы входного потока. Обычно размер окна составляет несколько килобайт, а размер буфера — не более ста байт. Алгоритм пытается найти в словаре (большей части окна) фрагмент, совпадающий с содержимым буфера.

Алгоритм LZ77 выдает коды, состоящие из трех элементов:

* смещение в словаре относительно его начала подстроки, совпадающей с началом содержимого буфера;

* длина этой подстроки;

* первый символ буфера, следующий за подстрокой.

2. Описание использованных структур данных

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

VocPass, st, slov, buff: string;//строка, словарь, буфер

sizebf, sizesl, ind, shft: integer;//размер буфера, размер словаря, индекс буквы в словаре, сдвиг

3. Описание процедур и функций

function GetCount(x,y:string):byte;

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

procedure TForm1. Button1Click (Sender: TObject);

процедура заполнения словаря, буфера и кода.

procedure FillDict (var x, y: string;n:integer);

Процедура сдвига словаря при его заполнении на количество повторяющихся символов из буфера.

procedure FillBuff (var x: string;m:integer);

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

procedure TForm1.Button2Click(Sender: TObject);

Процедура очистка строки, слова, буфера и кода.

procedure TForm1. Button4Click (Sender: TObject);

Процедура предназначена для выход из программы.

procedure TForm1. Button3Click (Sender: TObject);

Данная процедура позволяет выбрать файл для работы из файловой системы Windows. При этом открывается диалоговое окно с каталогом. Делается это с помощью переменной типа TOpenDialog. Свойство Filter позволило создать ограничение на открытие файлов. Программа открывает только файлы с расширением .txt.

procedure TForm1. Button5Click (Sender: TObject);

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

4. Описание структуры приложения и интерфейса пользователя

Вид главного окна приложения (Рис. 4.1):

Рис. 4.1.Вид главного окна приложения.

Данное приложение состоит из одного модуля (Form1). Для работы с программой пользователю необходимо заполнить строку, что бы это сделатьнеобходимо в Edit1 записать нужный нам текст. Записать текст мы можем двумя способами:

1. Заполнить исходную строку вручную;

2. Импортировать данные из текстового файла.

В двух случаях последовательность элементов выведется в Str: TEdit. После выполнения кодировки результат сжатия выводится в KOD: TListBox.

Чтобы ввести текст самостоятельно, необходимо установить курсор в поле Str и напечатать необходимый текст. Для выполнения кодировки необходимо выставить счетчик количества букв словаря и буфера для дальнейшей работы программы. (Pис.4.2):

Рис. 4.2.Заполнение строки вручную.

Чтобы заполнить строку из текста необходимо вызвать OpenDialog (Open Открыть), где пользователь должен выбрать файл, из которого будут загружены данные вставки (Pис.4.3):

Рис. 4.3. OpenDialog

Программа оповестит пользователя об успешной загрузке данных (Pис.4.4), а в том случае если открытие прервано, программа выдает ошибку (Рис 4.5).

Рис. 4.4. Оповещение об успешной загрузке Рис. 4.5. Оповещение об ошибке

После этого пользователь может приступить к пошаговой кодировке. Кодировка осуществляется автоматически. Для запуска кодировки необходимо выбрать на форме кнопку «!!!». По завершению кодировки появится окно (Рис 4.6)

Рис. 4.6 Оповещение о завершении кодировки

Для сохранения закодированного текста, то он должен вызвать вызвать SaveDialog (Save), в котором можно создать файл, в который будет сохраняться результат (Рис. 4.7).

Рис. 4.7.SaveDialog

Программа оповестит пользователя об успешном сохранении данных, указав путь к файлу. (Рис. 4.8)

Рис. 4.8. Оповещение об успешном сохранении данных

Если после завершения кодировки пользователь вновь захочет закодировать текст, то ему необходимо будет очистить форму (Рис. 4.9) и выполнить все необходимые шаги, описанные выше. Очистить форму можно нажав на пункт «Clear».

Рис. 4.9. Очистка

Ограничения работы программы:

· Программа работает со строкой, длина которой не имеет превышений.

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

· Тестировалась на операционных системах семейства Windows NT (XP/7).

5. Результаты тестирования приложения на разных объемах данных

Результат тестирования программы.

6. Анализ работы алгоритма LZ77 и выводы

Рис. 6.1. График зависимости количества сравнений от количества элементов

Из данного графика видно, что увеличение количества элементов ведет к увеличению количества сравнений. Количество сравнений можно посчитать по формуле, где n — количество элементов.

В результате проделанной работы было изучено большое количество литературы, рассмотрены несколько алгоритмов сжатия. Написана программа для сжатия данных по алгоритму Лемпела-Зива LZ77.

Список использованных источников

1. Дж. Бакнел «Фундаментальные алгоритмы и структуры данных в Delphi" — СПб: ООО «ДиаСофтЮП», 2003.-560 с.

2. Д. Хопкрофт «Структуры данных и алгоритмы» Д. Хопкрофт: Уч.пос.- М.:"Вильямс", 2000.

3. Н. Вирт «Алгоритмы и структуры данных.» Н.Вирт.М.: Мир, 1989., 87с .

4. В. В. Фаронов «Delphi. Программирование на языке высокого уровня: Учебник для вузов» В. В. Фаронов.: Питер, 2009

5. Д. Райли «Абстракция и структуры данных». Вводный курс. Д. Райли — М.: Мир, 1993 г.

Приложение

unitUmain;

interface

uses

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

Dialogs, StdCtrls, ComCtrls, ExtDlgs;

type

TForm1=class (TForm)

Button1:TButton;

Str:TEdit;

Dict:TListBox;

Buffer:TListBox;

KOD:TListBox;

Edit1:TEdit;

Edit2:TEdit;

UpDown1:TUpDown;

UpDown2:TUpDown;

Button2:TButton;

Button4:TButton;

Memo1:TMemo;

Button3:TButton;

Button5:TButton;

procedureButton1Click (Sender:TObject);

procedureButton2Click (Sender:TObject);

procedureButton4Click (Sender:TObject);

procedureButton3Click (Sender:TObject);

procedureButton5Click (Sender:TObject);

private

{Privatedeclarations}

public

{Publicdeclarations}

end;

var

Form1:TForm1;

VocPass, st, slov, buff: string;

i, sizebf, sizesl, ind, shft: integer;

implementation

{$R*.dfm}

procedureTForm1.Button1Click (Sender:TObject);

vari, temp: integer;

s:string;

functionGetCount (x, y: string):byte;//определяемдлинусовпадения

vari, j, k:integer;

begin

j:=pos (y[1], x);

result:=1;

k:=2;

fori:=ktosizebfdo

ifx[i]=y[j+1]then

begin

inc (j);

inc (result);

end;

inc (result);

end;

procedureFillDict (varx, y: string;n:integer);//заполняемсловарьснова

vari, j, delta:integer;

begin

ifn+length (x)<=sizeslthen//есливловарьможнодописатьтопишем12 345придлине7->1 234 567

forI:=1tondo

x:=x+y[i]

else

begin

delta:=n+length (x)-sizesl;//определяемсколькосимволоввыталкиваем

fori:=1tosizesl-deltado

x[i]: =x[i+delta];//передвигаемвсебуквынадлинусмещения12 345сосдвигом2—>345

j:=1;

fori:=length (x)-delta+1tosizesldo

begin

x[i]:=y[j];//дописываемизбуфера

inc (j);

end;

end;

end;

procedureFillBuff (varx:string;m:integer);

vari, j: integer;

begin

fori:=1tolength (x)-mdo

x[i]:=x[i+m];//выталкиваемпроверенныебуквы

j:=length (x);

setlength (x, j-m);//устанавливаемновуюдлину

i:=length (x)+1;

while (i<=sizebf)and (ind

begin//еслистроканезакончиласьибуфернеполон

x:=x+st[ind+1];

inc (i);inc (ind);

end;

end;

begin

KOD.Clear;

Buffer.Clear;

Dict.Clear;

st:=Str.Text;

sizesl:=StrToInt (Edit1.Text);

sizebf:=StrToInt (Edit2.Text);

slov:='';

buff:='';

ind:=1;

fori:=1tosizebfdo

buff:=buff+st[i];

ind:=sizebf;

Buffer.Items.Add (buff);

Dict.Items.Add (slov);

whilebuff<>''do

begin

if (slov='')or ((ind=length (st))and (length (buff)=1))then//еслипоследняябукваилисловарьещепуст

begin

slov:=slov+buff[1];

KOD.Items.Add ('<'+'0'+','+'0'+','+buff[1]+'>');

FillBuff (buff, 1);

end

else

begin

ifpos (buff[1], slov)<>0then

begin

temp:=pos (buff[1], slov)-length (slov);;

shft:=GetCount (buff, slov);

s:=buff[shft];

FillDict (slov, buff, shft);

FillBuff (buff, shft);

KOD.Items.Add ('<'+inttostr (sizesl+temp)+','+inttostr (shft-1)+','+s+'>');

end

else

begin

FillDict (slov, buff, 1);

KOD.Items.Add ('<'+'0'+','+'0'+','+buff[1]+'>');

FillBuff (buff, 1);

end;

end;

shft:=0;

ifbuff<>''then

begin

Buffer.Items.Add (buff);

Dict.Items.Add (slov);

end;

end;

ShowMessage ('Готово!');

end;

procedureTForm1.Button2Click (Sender:TObject);

begin

Str.text:='';

dict.items.clear;

buffer.Items.Clear;

KOD.Items.Clear;

end;

procedureTForm1.Button4Click (Sender:TObject);

begin

Close;

end;

procedureTForm1.Button3Click (Sender:TObject);

varOpenDialog:TOpenDialog;

Tekst:TextFile;

FilePass, s: string;

begin

Memo1.Clear;

Memo1.Lines.Add ('');

openDialog:=TOpenDialog.Create (self);

openDialog.InitialDir:=GetCurrentDir;

//Тольк оразрешенные существующие файлымогут быть выбраны

openDialog.Options:=[ofFileMustExist];

//Разрешеновыбратьтолько.txtфайлы

openDialog.Filter:=

'TextFiles|*.txt';

//Показдиалоготкрытияфайла

ifopenDialog.Execute

then

begin

ShowMessage ('File:'+openDialog.FileName);

FilePass:=openDialog.FileName;

AssignFile (Tekst, FilePass);

Reset (Tekst);

whilenoteof (Tekst)do

begin

ReadLn (Tekst, s);

Memo1.Lines.Add (s);

end;

Memo1.Lines.Delete (0);

end

elseShowMessage ('Открытие файла остановлено');

Str.Text:=memo1.Text;

end;

procedureTForm1.Button5Click (Sender:TObject);

varSaveDialog:TSaveDialog;

begin

SaveDialog:=TSaveDialog.Create (self);

SaveDialog.InitialDir:=GetCurrentDir;

SaveDialog.Options:=[ofFileMustExist];

SaveDialog.Filter:='TextFiles|*.txt';

ifSaveDialog.Execute

then

begin

KOD.Items.SaveToFile (SaveDialog.FileName+'.txt');

ShowMessage ('File:'+SaveDialog.FileName);

end

elseShowMessage ('Сохранение файла остановлено');

end;

end.