Курсовая работа: Сжатие данных методами Хафмана и Шеннона-Фано
После этого будет вызвана
процедура вставки байта, после возвращения из которой мы текущую точку опять
устанавливаем на корень}
If (Buf[j] and (1 shl
(8-k)))<>0
Then
CurrentPoint:=CurrentPoint^.right
Else
CurrentPoint:=CurrentPoint^.left;
if
(CurrentPoint^.left=nil) or (CurrentPoint^.right=nil)
Then
Begin
MainBuffer.InsertByte(CurrentPoint^.Symbol);
CurrentPoint:=MainFile.Tree;
End;
Application.ProcessMessages;
End;
Application.ProcessMessages;
End;
End;
If LastBuf<>0
Then
Begin//работа этого
блока программы аналогична предидущему
BlockRead(FileToRead,Buf,LastBuf);
for j:=1 to
LastBuf do
Begin
for k:=1 to 8
do
Begin
If (Buf[j]
and (1 shl (8-k)))<>0
Then
CurrentPoint:=CurrentPoint^.right
Else
CurrentPoint:=CurrentPoint^.left;
if
(CurrentPoint^.left=nil) or (CurrentPoint^.right=nil)
Then
Begin
MainBuffer.InsertByte(CurrentPoint^.Symbol);
CurrentPoint:=MainFile.Tree;
End;
Application.ProcessMessages;
End;
Application.ProcessMessages;
End;
End;
MainBuffer.FlushBuf;
End;
//процедура чтения
заголовка архива
Procedure
ReadHead;
var
b: Integer_;
// исходный размер
файла
SymbolSt:
Integer;//статистика символа
count_,
SymbolId, i: Byte;//SymbolId=Symbol просто
чтобы
// не путать глобальную переменную с
локальной
Begin
try
//узнаем исходный размер
файла
BlockRead(FileToRead,b,4);
ByteToInteger(b,MainFile.size);
//узнаем количество
оригинальных байтов
BlockRead(FileToRead,count_,1);
{}{}{Вызываем процедуру
инициализации объекта}
MainFile.Stat.create;
MainFile.Stat.CountByte:=count_;
//загоняем частоты в
массив
for i:=0 to MainFile.Stat.CountByte
do
Begin
BlockRead(FileToRead,SymbolId,1);
MainFile.Stat.massiv[i]^.Symbol:=SymbolId;
BlockRead(FileToRead,b,4);
ByteToInteger(b,SymbolSt);
MainFile.Stat.massiv[i]^.SymbolStat:=SymbolSt;
End;
//вызываем процедуру создания дерева
CreateTree(MainFile.Tree,MainFile.stat.massiv,MainFile.Stat.CountByte);
/////////////
//Вызываем процедуру
распаковки файла
CreateDeArc;
//////////////
//Вызываем процедуру
уничтожения дерева
DeleteTree(MainFile.Tree);
except
ShowMessage('архив испорчен!');
End;
End;
//процедура извлечения архива
Procedure
ExtractFile;
Begin
AssignFile(FileToRead,MainFile.Name);
//соединяем наш файл файловй
переменой передэтим
//вызываем метод
получения имени разархивированого файла
AssignFile(FileToWrite,MainFile.DeArcName);
try
Reset(FileToRead,1);
Rewrite(FileToWrite,1);
//процедура чтения
шапки файла
ReadHead;
Closefile(FileToRead);
Closefile(FileToWrite);
Except
ShowMessage('Ошибка распаковки файла');
End;
End;
//вспомогательная
процедура для создания архива
Procedure CreateArchiv;
var
buffer: String;//строка
в которой будет формироватся
//последовательность из
кодовых слов
ArrOfStr: Array [0..255] of String;
i,j: Integer;
//////////////
buf: Array
[1..count] of Byte;//массив в который
//будем считывать данные
из архивируемого файла
CountBuf, LastBuf: Integer;
Begin
Application.ProcessMessages;
AssignFile(FileToRead,MainFile.Name);
AssignFile(FileToWrite,MainFile.ArcName);
Try
Reset(FileToRead,1);
Rewrite(FileToWrite,1);
//Инициализируем массив строк
в котором будут
//хранится кодовые слова
For i:=0 to 255 Do
ArrOfStr[i]:='';
//Загоням в массив строк
кодовые слова соответсвующие
//своим символам
For i:=0 to
MainFile.Stat.CountByte do
Begin
ArrOfStr[MainFile.Stat.massiv[i]^.Symbol]:=
MainFile.Stat.massiv[i]^.CodWord;
Application.ProcessMessages;
End;
//узнаём какое целое
количество буферов по 4 кбайт будет содержатся в
//сжимаемом файле
CountBuf:=MainFile.Size
div Count;
//Сколько останется байт
для записи не вошедших в ранее
//определённое значение
CountBuf
LastBuf:=MainFile.Size
mod Count;
Buffer:='';//обнуляем
буфер
/////////////
CreateHead; //вызываем
процедуру создания заголовка файла
/////////////
//фрмируем буфер кодовых слов
for i:=1 to
countbuf do
Begin
//считываем из файла по 4
кбайт
BlockRead(FileToRead,buf,Count);
//////////////////////
For j:=1 to
count do
Begin
//растим буфер из кодовых
слов
buffer:=buffer+ArrOfStr[buf[j]];
//если длина buffer
превысит значеие 8*4096 (это означает
//превысит размер
выходного буфера размер которого 4096байт)
//мы вызываем процедуру
записи в файл
If Length(buffer)>8*count
Then
WriteInFile(buffer);
Application.ProcessMessages;
End;
//
ProgressBar1.Position:=100 div countbuf;
End;
//Запись оставшейся
цепочки байт
If lastbuf<>0
Then
Begin
//считываем в массив из
файла оставшиеся байты
BlockRead(FileToRead,buf,LastBuf);
//растим buffer строку из
кодовых слов
For j:=1 to lastbuf do
Begin
buffer:=buffer+ArrOfStr[buf[j]];
If Length(buffer)>8*count
//если его размер
превысит значение 8*4096 (а это может иметь
//место), то вызываем
процедуру записи в файл
Then
WriteInFile(buffer);
Application.ProcessMessages;
End;
End;
//выываем процедуру
записи оставшейся цепочки кодовых слов
WriteInFile_(buffer);
CloseFile(FileToRead);
CloseFile(FileToWrite);
Except
ShowMessage('Ошибка создания архива');
End;
End;
//главная процедура для
создания архивного файла
Procedure
CreateFile; //(802)
var
i: Byte;
Begin
With MainFile do
Begin
{сортировка массива
байтов с частотами (192)}
SortMassiv(Stat.massiv,stat.CountByte);
{поиск числа задействованных байтов
из массива
(ACSII) возмжных
символов. В CountByte будем хранить
количество этох самых
символов }
i:=0;//обнуляем счётчик
While
(i<Stat.CountByte) //до тех пор пока счётчик
//меньше количества
задействовнных байт CountByte
//и статистика байта
(частота появления в файле)
//не равна нулю делаем
and
(Stat.massiv[i]^.SymbolStat<>0) do
Begin
Inc(i); //увеличиваем
счётчик на единицу
End;
//////////////////////
If
Stat.massiv[i]^.SymbolStat=0 //если дошли до символа
//с нулевой встречаемостью в файле то
Then
Dec(i); //уменьшаем
счётчик на единицу тоесть возвращаемся
//назад это будет
последний элемент
//////////////////////
Stat.CountByte:=i;{присваиваем
значение счётчика
CountByte. Это означает что
в архивируемом файле используется такое количество из 256
возможных символов. Будет исползоватся для
построения древа частот}
{создание дерева частот.
Передаём в процедуру начальные параметры
Tree=nil-эта переменная будет содержать после
работы процедуры древо ,Stat.massiv-массив с символами и соответствующей им статистикой,а так же указанием на правое и левой дерево,Stat. CountByte количество используемых символов в архивирумом файле (230)} CreateTree(Tree,Stat.massiv,Stat.CountByte); {запускаем в работу дерево с помощью его нахадим
соответствующие кодовые слова. Суть алгоритма
вызываем функцию SymbolToCodWord(Tree:TByte(указатель
на корень дерева. Он у нас выработался в
результате работы процедуры CreateTree, Symbol:byte):
String функция вернёт нам
строку содержащую кодовое слово ()}
for i:=0 to
Stat.CountByte do
Stat.massiv[i]^.CodWord:=SymbolToCodWord(Tree,stat.massiv[i]^.Symbol);
//пишем сам файл
CreateArchiv;
//Удаляем уже ненужное
дерево
DeleteTree(Tree);
//Инициализируем
статистику файла
MainFile.Stat.Create;
End;
End;
//Основная процедура
сжатия файла
procedure
RunEncodeHaff(FileName_: string);
begin
MainFile.Name:=FileName_;//передаём имя
//архивируемого файла в программу
StatFile(MainFile.Name);
//запускем процедуру создания
//статистики (частоты
появления того или иного символа)
//для файла (строка 274)
CreateFile; //вызов
процедуры созданя архивного файла (737)
end;
//Основная процедура
разархивирования файла
procedure
RunDecodeHaff(FileName_: string);
begin
MainFile.name:=FileName_;//передаём имя
//архивируемого файла в программу
ExtractFile;//Вызываем
процедуру извлечения архива
end;
end.
|
