303913 (Сжатие данных методами Хафмана и Шеннона-Фано), страница 5

//размера сжимаемого файла деаем

if GeneralCount

Then

Begin

inc(ByteCount); //увеличиваем соответствующие

//счётчики на единицу

inc(GeneralCount);

ArrOfByte[ByteCount]:=a;//загоняем в массив ArrOfByte

//значение полученное в переменной а

//////////////////////////

if ByteCount=MaxCount //если ByteCount=MaxCount

//то записываем содержимое массива в разархивируемый файл

Then

Begin

BlockWrite(FileToWrite,ArrOfByte,ByteCount);

ByteCount:=0;

//Form1.ProgressBar1.Position:=form1.ProgressBar1.Position+1;

End;

End;

End;

////////////////////////////

Procedure Buffer_.FlushBuf;

//Процедура записи остаточной цепочки байт

Begin

If ByteCount<>0

Then

BlockWrite(FileToWrite,ArrOfByte,ByteCount);

End;

//создание деархивированного файла

Procedure CreateDeArc;

var

i,j: Integer;

k: Byte;

//////////////

Buf: Array [1..Count] of Byte;

CountBuf, LastBuf: Integer;

MainBuffer: buffer_;

CurrentPoint: TByte;

Begin

//определяем сколько целых буферов по 4 кбайт в сжатом

//файле без заголовка

CountBuf:=MainFile.FileSizeWOHead div count;

//определяем сколько останеся байт не вошедших

//в целые буферы по 4 кбайт в сжатом файле без заголовка

LastBuf:=MainFile.FileSizeWOHead mod count;

MainBuffer.CreateBuf;//иициализируем переменные

CurrentPoint:=MainFile.Tree;//присваиаем текущую

//позицию на корень дерева

//начинаем расаковку

For i:=1 to CountBuf do

Begin//считываем из сжатого файла данные в буфер

BlockRead(FileToRead,buf,count);

for j:=1 to Count do //по байтно начинаем

//просматривать буфер

Begin

for k:=1 to 8 do//просматриваем биты от 1 до 8

//выеленного байта

Begin {Выделяем байт в массиве. По циклу от 1 до 8просматриваем значения его бит с 7 до 0. Для этого используетсяоперация битового сдвига влево shl и логиеская операция and.

В цикле всё происходит следующим образом: Сначала просматриваетсястарший бит (8-к)=1 и производится логическая операция and,если бит равен 1 то (1 and 1)=1 и программа установит текущую позицию поиска в дереве на правый узел, если же бит равен 0 то (0 and 1)=0 и программа установит текущую позицию поиска в дереве на левый узел. так будет продолжатся до тех пор пока не выполнится условие, которое ознчает нахождение искомого символа ((CurrentPoint^.left=nil) or (CurrentPoint^.right=nil))

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

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

//меньше количества задействовнных байт 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.