Курсовая работа: Сжатие данных методами Хафмана и Шеннона-Фано
//узнаем количество оригинальных
байтов
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;
CountBuf:=MainFile.Size
div Count;
LastBuf:=MainFile.Size
mod Count;
Buffer:='';
/////////////
CreateHead;
/////////////
for i:=1 to
countbuf do
Begin
BlockRead(FileToRead,buf,Count);
//////////////////////
For j:=1 to
count do
Begin
buffer:=buffer+ArrOfStr[buf[j]];
If
Length(buffer)>8*count
Then
WriteInFile(buffer);
Application.ProcessMessages;
End;
End;
If
lastbuf<>0
Then
Begin
BlockRead(FileToRead,buf,LastBuf);
For j:=1 to
lastbuf do
Begin
buffer:=buffer+ArrOfStr[buf[j]];
If
Length(buffer)>8*count
Then
WriteInFile(buffer);
Application.ProcessMessages;
End;
End;
WriteInFile_(buffer);
CloseFile(FileToRead);
CloseFile(FileToWrite);
Except
ShowMessage('Ошибка создания архива');
End;
End;
//главная процедура для
создания архивного файла
Procedure
CreateFile;
var
i: Byte;
Begin
With MainFile
do
Begin
{сортировка массива
байтов с частотами}
SortMassiv(Stat.massiv,stat.CountByte);
{поиск числа задействованных байтов
из таблицы возмжных символов. В count_byte будем хранить количество этох самых
байт }
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;//присваиваем
значение счётчика
//count_byte. Это
означает что в архивируемом файле
//используется такое
количество из 256 возможных
//символов. Будет
исползоватся для построения древа частот
{создание дерева частот.
Передаём в процедуру
начальные параметры Tree=nil-эта переменная будет содержать после работы
процедуры древо ,Stat.massiv-массив с символами и соответствующей им
статистикой,а так же указанием на правое и левой дерево, Stat. CountByte-количество используемых символов
в архивирумом файле }
CreateTree(Tree,Stat.massiv,Stat.CountByte);
//пишем сам файл
CreateArchiv;
//Удаляем уже ненужное
дерево
//DeleteTree(Tree);
//Инициализируем
статистику файла
MainFile.Stat.Create;
End;
End;
procedure
RunEncodeShan(FileName_: string);
begin
MainFile.Name:=FileName_;//передаём имя
//архивируемого файла в программу
StatFile(MainFile.Name);
//запускем процедуру создания
//статистики (частоты
появления того или иного символа)для файла
CreateFile; //вызов
процедуры созданя архивного файла
end;
procedure
RunDecodeShan(FileName_: string);
begin
MainFile.name:=FileName_;//передаём имя
//архивируемого файла в программу
ExtractFile;//Вызываем
процедуру извлечения архива
end;
end.
Приложение 2.
Реализация на
Delphi алгоритма сжатия Хафмана
unit Haffman;
interface
Uses
Forms,ComCtrls,
Dialogs;
const
Count=4096;
ArchExt='haf';
dot='.';
//две файловые переменные
для чтения исходного файла и для
//записи архива
var
FileToRead,FileToWrite:
File;
ProgressBar1:TProgressBar;
// Процедуры для работы с
файлом
// Первая - кодирование файла
procedure
RunEncodeHaff(FileName_: string);
// Вторая - декодирование файла
procedure
RunDecodeHaff(FileName_: string);
implementation
Type
{тип элемета для
динамической обработки статистики символов
встречающихся в файле}
TByte=^PByte;
PByte=Record
//Символ (один из
символв ASCII)
Symbol: Byte;
//частота появления
символа в сжимаемом файле
SymbolStat: Integer;
//последовательность
битов, в которые преобразуется текущий
//элемент после работы древа
(Кодовое слово) (в виде строки из "0" и "1")
CodWord: String;
//ссылки на левое и
правое поддеревья (ветки)
left, right: TByte;
End;
{массив из символов со
статистикой , т.е. частотой появления их в
архивируемом файле}
BytesWithStat = Array
[0..255] of TByte;
{объект, включающий в
себя:
массив элементов
содержащий в себе количество элементов,
встречающихся в файле
хотя бы один раз
процедура инициализации
объекта
процедура для увеличения
частоты i-го элемента}
TStat =Object
massiv:
BytesWithStat;
CountByte:
byte;
Procedure
Create;//процедура инициализации обьекта
Procedure
Inc(i: Byte);
End;
// процедура инициализации
объекта вызывается из процедуры StatFile
Procedure TStat.Create; //(291)
var
i: Byte;
Begin //создаём массив симолв
(ASCII), обнуляем статистику
//и ставим указатели в
положение не определено
CountByte:=255;
For i:=0 to
CountByte do
Begin
New(massiv[i]);//создаём
динамическую переменную
//и устанавливаем
указатель на неё
massiv[i]^.Symbol:=i;
massiv[i]^.SymbolStat:=0;
massiv[i]^.left:=nil;
massiv[i]^.right:=nil;
Application.ProcessMessages;//Высвобождаем ресурсы
//чтобы приложение не казалось
зависшим, иначе все ресуры процессора
//будут задействованы на
обработку кода приложения
End;
End;
{процедура для вычисления
частот появления
i-го элемента в сжимаемом
файле вызывается строка(310)}
Procedure TStat.Inc(i: Byte);
Begin //увеличиваем значение
статистики символа [i] наединицу
massiv[i]^.SymbolStat:=massiv[i]^.SymbolStat+1;
End;
Type
//объект включающий в
себя:
//имя и путь к
архивируемому файлу
//размер архивируемого
файла
//массив статистики
частот байтов
//дерево частот байтов
//функцию генерации по
имени файла имени архива
//функцию генерации по
имени архива имени исходного файла
//функцию для
определения размера файла без заголовка
//иными словами
возвращающую смещение в архивном файле
//откуда начинаются
сжатые данные
File_=Object
Name: String;
Size:
Integer;
Stat: TStat;
Tree: TByte;
Function
ArcName: String;
Function
DeArcName: String;
Function
FileSizeWOHead: Integer;
End;
// генерация по имени
файла имени архива
Function
File_.ArcName: String;
Var
i: Integer;
name_:
String;
Const
PostFix=ArchExt;
Begin
name_:=name;
i:=Length(Name_);
While
(i>0) And not(Name_[i] in ['/','\','.']) Do
Begin
Dec(i);
Application.ProcessMessages;
End;
If (i=0) or
(Name_[i] in ['/','\'])
Then
ArcName:=Name_+'.'+PostFix
Else
If
Name_[i]='.'
Then
Begin
Name_[i]:='.';
//
Name_[i]:='!';
ArcName:=Name_+'.'+PostFix;
End;
End;
// генерация по имени
архива имени исходного файла
Function
File_.DeArcName: String;
Var
i: Integer;
Name_:
String;
Страницы: 1, 2, 3, 4, 5, 6, 7, 8 |
