Разработка программы сжатия файлов с помощью блочного кода

Министерство образования  и науки РФ

Федеральное государственное  бюджетное образовательное учреждение высшего профессионального образования

 «Ярославский государственный  технический университет»

Кафедра «Информационные  системы и технологии»

 

 

 

Курсовая работа защищена

с оценкой (_________)

Руководитель

доцент, к.т.н

(________) Раухваргер А.Б.

“___”_________  2013 г.

                                                                     

 

 

 

РАЗРАБОТКА  ПРОГРАММЫ СЖАТИЯ ФАЙЛОВ С ПОМОЩЬЮ  БЛОЧНОГО КОДА

 

Расчетно-пояснительная записка к курсовой работе

по дисциплине “Теория информационных процессов и систем”

ЯГТУ 230201.65-21 КР

 

 

 

 

 

Нормоконтролер Работу выполнила

доцент, к.т.н студентка гр. ЭИС-44

(______) Раухваргер А.Б. (______) Паишева Е.В.

“___”________  2013 г.                                      “___”_________  2013 г. “__”___________2009

 

 

 

 

 

2013

Содержание

 

Задание            3

1 Краткое описание используемых  алгоритмов и архитектуры программы 

   1.1 Построение таблицы кодовых  слов       4

   1.2 Описание алгоритмов, используемых в программе    6

   1.3 Алгоритмы сжатия и  восстановления файлов     7

2 Краткая инструкция пользователю  по работе с программой   8

3 Результаты тестирования                   10

Заключение                  11       

Приложение А. Код программы                                          12

Приложение Б. Таблица  кодовых слов              18

 

Задание

 

Цель данной курсовой работы написать с помощью Delphi программу - блочные коды постоянного смещения. Блочные коды постоянного смещения задаются начальной длиной кодового слова и величиной, на которую увеличивается длина кодового слова в каждом блоке. Сжатие происходит при выполнении следующего условия: длина кодового слова в начальном блоке - 3; смещение – 2.

 

 

1 Краткое описание  используемых алгоритмов и архитектуры программы

 

 

1.1 Построение таблицы  кодовых слов

 

Для построения таблицы  кодовых слов я использовала алгоритм сжатия с помощью блочного кода с  постоянным смещением. Смысл данного  метода в том, что таблица кодовых  слов состоит из блоков слов постоянной длины; задана наименьшая длина кодового слова, а также смещение (увеличение длины кодового слова следующего блока по сравнению с предыдущим). Самыми короткими словами (словами начальной длины) кодируются наиболее частые байты сжимаемого файла (для этого байты файла сортируются по убыванию количества повторений).  Количество кодовых слов в блоке (n) определяется формулой n_k=2^l0-1+k(h-1), где k - порядковый номер блока, l₀ - начальная длина кодового слова, h - смещение.

Строю таблицу кодовых слов для своего варианта.

Начальная длина кодового слова  l₀= 3, смещение h=2.

n₀=2^3-1=4 - количество кодовых слов нулевого (начального) блока. Блок будет состоять из кодовых слов:

 

111

110

101

100

 

n₁=2^3-1+2-1=8 - количество кодовых слов следующего блока.  Начиная с этого блока кодовые слова, будут формироваться путем добавления нулей и единиц в начало и конец слов предыдущего блока, например:

 

01111

01101

01011

01001

…

Главное, чтобы начала кодовых слов в таблице не повторялись.

n₂=2^3-1+2=16 - количество кодовых слов следующего блока.

 

0011111

0011011

0010111

0010011

…   

n₃=2^3-1+3(2-1)=32 - количество слов следующего блока:

 

000111111

000111110

000111101

000111100

…

 

n₄=2⁶=64 - количество слов следующего блока:

 

00001111111

00001111110

00001111101

00001111100

….

 

n₅=2⁷=128 - количество слов следующего блока:

 

0000011111111

0000011111110

0000011111101

0000011111100

…

 

n₆=2⁸=256 - количество слов последнего блока, а так как мне требуется всего 256 кодовых слов (0-255), для кодирования байт файла я беру 4 первых строчки. Продолжаю строить таблицу кодовых слов.

 

000000111111111

000000111111110

000000111111101

000000111111100

Полную версию таблицы  кодовых слов можно посмотреть в  приложении Б.

 

1.2 Описание алгоритмов, используемых в программе

 

Алгоритмы преобразования строки в байт и обратно

 

Так как преобразования подобного типа с использованием арифметических операций (в частности  деления и умножения) сильно тормозит работу программы, я использую логические операции и сдвиги бит в байте.

 

Преобразование из string в byte: мне дано некоторое строковое значение бит байта. Беру нулевой байт (00000000), в цикле от 1 до 8 (в байте 8 бит) сдвигаю биты влево и сравниваем их поочередно с символами в строке с помощью логической операции or ("или", логическое сложение) - в логических операциях принимает участие только последний бит байта.

 

Преобразование из byte в string: мне дано некоторое значение байта. В цикле от 0 до 7 сравниваю заданный байт с единичным, который сдвигается на текущий шаг, при помощи логической операции and ("и", логическое умножение) - если результат сравнения равен 0, то в начало строкового буфера записывается '0', иначе '1'.

 

Алгоритм сортировки "Пузырек"

 

Сортировка простыми обменами, сортировка пузырьком — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов.

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно  сравниваются попарно и, если порядок  в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим наибольшим элементом, а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).

 

 

 

 

 

1.3 Алгоритмы сжатия  и восстановления файлов

 

Алгоритм с использованием блочного кода, в отличие от алгоритмов Шеннона и Хаффмана, имеет фиксированную  таблицу кодовых слов. Поэтому  удобно хранить ее непосредственно  в программе. В моем случае это организовано через компонент ListBox, в который таблица кодовых слов подгружается из текстового файла с таблицей, созданной заранее (слова упорядочены по возрастанию длины).

 

Краткое описание алгоритма  сжатия:

1.программа считывает  байты из файла (процедура blockread), подсчитываем количество повторений в файле для каждого байта;

2. с помощью алгоритма  сортировки данных "пузырек"  упорядочивает байты по количеству  повторений в файле (по убыванию);

3. байтам с наибольшей  частотой повторений будут соответствовать более короткие кодовые слова из таблицы, с помощью процедуры blockwrite записываем упорядоченную последовательность байт в файл (это необходимо для последующего восстановления файла, таким образом, у нас имеется в сжатом файле зарезервированная область данных объемом 256 байт);

4. формируется таблица  соответствий байтов кодовым  словам (реализовано с помощью  массива из записей типа TTable), сортируем записи с помощью "пузырька" по возрастанию номеров байт;

5. формируется строка  кодовых слов, заменяя байты файла соответствующими кодовыми словами;

6. далее программа  разбивает строку на восьмерки  символов и описанным ранее  методом перевода из строки  в байт записывает (процедура blockwrite),  новые байты в файл (последний байт "добивается нулями", если длина строки не кратна 8);

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

 

Краткое описание алгоритма  восстановления:

1. программа считывает  байты из файла (процедура blockread),;

2. формируется таблица  соответствий кодовых слов байтам исходного файла (используем первые 256 байт сжатого файла - сохраненную последовательность байт исходного);

3. определяется количество "нулей добивания" - это значение  последнего байта сжатого файла;

4. при помощи рассмотренного выше метода перевода из байта в строку формируется буферная строка кодовых слов;

5. в завершении с  помощью процедуры blockwrite записывается в файл последовательность байт, соответствующих кодовым словам в буферной строке

 

 

2 Краткая инструкция  пользователю по работе с  программой

 

После запуска программы  вы увидите:

 

Рисунок 1 – Интерфейс программы

 

Нажав на кнопку «Архивировать» откроется окно, в котором вы сможете  выбрать файл дл работы с ним.

 

Рисунок 2 – Открытие файла

 

После открытия файла  программа выполняет данную операцию:

 

Рисунок 3 – Архивируем файл

 

Рисунок 4 – Завершение архивации файла

 

Для восстановления требуется  нажать кнопку «Разархивировать», тогда  откроется окно, в котором вы сможете  выбрать файл для работы с ним.

 

Рисунок 5 – Окно завершения восстановления

 

Так же следует указать, что файлы после обработки  сохраняются в той же директории, в которой находились исходные  и будут иметь расширение *.blc .

 

 

    

 

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

 

Я протестировала свою программу на различных типах файлов, использовались разнообразные форматы, такие как: текстовые, графические, мультимедийные и другие.

 

Проведем сравнение файлов до и  после сжатия:

• .bmp: исходный – 201 кб, после сжатия – 123 кб, после разархивирования 201 кб;
• .doc: исходный – 232 кб, после сжатия – 131 кб, после разархивирования 232 кб;
• .txt: исходный – 75 кб, после сжатия – 57 кб, после разархивирования 75 кб;
• .exe: исходный – 397 кб, после сжатия – 364 кб, после разархивирования 397 кб;
• .pas: исходный – 13 кб, после сжатия – 10 кб, после разархивирования 13 кб;

 

Из полученных данных видим, что  некоторые форматы файлов сжимаются  лучше, некоторые хуже. Прежде всего, связано это с тем, что некоторые  форматы файлов имеют встроенное сжатие, а так же с тем, что в  некоторых форматах хранится однотипная информация, которая эффективно поддается сжатию.

 

 

 

 

 

 

Заключение

 

В ходе курсовой работы мной была разработана  программа для  сжатия и восстановления файлов, основой,  которой является алгоритм блочного кода с постоянным смещением, так же были составлены алгоритмы преобразования данных из типа string в тип byte и наоборот. Я провела тестирование программы и поняла, что использованный метод сжатия не является эффективным, так как данным методом можно успешно сжимать только текстовые файлы или мультимедийные файлы высокого качества без потерь, но коэффициенты сжатия при этом довольно низкие.

 

Приложение А. Код программы

 

unit Unit1;

 

interface

 

uses

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

  Dialogs, StdCtrls, ComCtrls;

 

type

  TForm1 = class(TForm)

    Button1: TButton;

    Button2: TButton;

    ProgressBar1: TProgressBar;

    ProgressBar2: TProgressBar;

    OpenDialog1: TOpenDialog;

    ListBox1: TListBox;

    Label1: TLabel;

    Label2: TLabel;

    procedure Button1Click(Sender: TObject);

    procedure Button2Click(Sender: TObject);

  private

    { Private declarations }

  public

    { Public declarations }

  end;

 

type TableByte=record

ind:byte;

code:string;

end;

 

var

  Form1: TForm1;

  filereading,filewriting:File;

  path, buffer, stroka, strbuffer, narstr:string;

  s,i,j,b2,b,k,dlina,proc,proc2,l,c,last,z:integer;

  buf, bt:byte;

  bytebase:array of byte;

  indexes:array [0..255] of byte;

  massiv:array [0..255] of integer;

  table:array [0..255] of TableByte;

 

implementation

 

{$R *.dfm}

 

procedure TForm1.Button1Click(Sender: TObject); //архивировать

begin

  if OpenDialog1.Execute then  //открытие файла

begin

for i:=0 to 255 do    // присвоение начальных значений массиву частот

begin

indexes[i]:=i;

massiv[i]:=0;

table[i].code:='';

end;

 

path:=OpenDialog1.FileName;    // привязка файла

assignfile(filereading,path); // связываем файл с файл.переменной

reset(filereading,1); //открываем файл для чтения по байтно

 

k:=0;          // обнуление счетчиков

proc:=0;

Progressbar1.Position:=0;  // начальные значения прогресс-баров

Progressbar2.Position:=0;

 

dlina:=filesize(filereading);   // задаем размерность массива fb

setlength(bytebase,dlina);

 

while not eof(filereading) do    // считываем байты, количество повторов(пока не конец файла)

begin

blockread(filereading,buf,1); //производим считывание  и запись из файла в буфер

bytebase[k]:=buf;

massiv[buf]:=massiv[buf]+1; //индекс в массиве равен значению считываемого файла

inc(k);

 

if proc<>100 then

proc:=((k*100) div dlina);  // описание прогреесс бара

ProgressBar1.Position:=proc;

end;

 

closefile(filereading); //закрываем