98930

Сжатие бинарных файлов

Курсовая

Информатика, кибернетика и программирование

Все методы сжатия употребляют входным потоком информации малой единицей которой станет проявляться бит а наибольшей станет некоторое количество бит мало байт или сам байт. Целью процесса сжатия как правило является приобретение наиболее сжатого выходного потока информационных единиц из некого вначале несжатого входного потока при поддержке неких их конфигураций. Главными техническими чертами действий сжатия и итогов их работы являются: ступень сжатия или ассоциация размеров предоставленного и потоков дающих итог; скорость сжатия т....

Русский

2016-07-14

546.76 KB

2 чел.

МИНОБРНАУКИ РФ

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

«Поволжская государственная социально-гуманитарная академия»

Факультет математики, физики и информатики

Кафедра информатики, прикладной математики

и методики их преподавания

Сжатие бинарных файлов.

Курсовая работа

Студента 2 курса:

Гарафиевой Альмиры Айдаровны.

Научный руководитель:

к. п. н. доцент Пугач О.И.

Курсовая работа сдана:

«     » __________ 2013 г.

Подпись научного руководителя:

________________

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

«     » __________ 2013 г.

Оценка:____________

Подписи членов комиссии:

_________________________

Самара 2013

Содержание

  1.  Введение
  2.  Постановка задачи
  3.  Реализация задачи
  4.  Основная часть
  5.  Заключение
  6.  Библиография


Введение

Сжатие информации – трудная задача, имеющая  давнюю историю,  более давнюю, нежели история развития вычислительной техники.

Эта тема достаточно актуальна, потому что в современном мире многие люди используют сжатие для экономии места.

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

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

Главными техническими чертами действий сжатия и итогов их работы являются:

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

Алгоритм Шеннона — Фано — считается одним из первых алгоритмов сжатия, сформулированный впервые американскими учёными Шенноном и Фано (англ. Robert Fano). Исходный  способ сжатия имеет огромное сходство с алгоритмом Хаффмана, появившийся на мало лет позднее. Алгоритм употребляет коды переменной длины: символ, который часто встречается  кодируется кодом наименьшей длины, чрезвычайно изредка встречается символ, кодирующийся  кодом большей длины.

В отличие от алгоритма Шеннона — Фано, алгоритм Хаффмана остаётся всегда приемлемым и для вторичных алфавитов m2 с более чем двумя символами.


Постановка задачи

Разработать программу, реализующий алгоритмы Шеннона-Фано и Хаффмана по сжатию.

Реализация задачи

Для реализации поставленной задачи был выбран язык программирования Delphi. Программа представляет собой алгоритмы сжатия информации при помощи 2-х алгоритмов. Используются методы сжатия с минимальной избыточностью.

Среда разработки Delphi 

Источник истории создания Delphi уходит в далекие 60-е годы 20го века.

Язык Паскаль (который послужил основой для написания Delphi), разработал профессор Н.Вирт в конце 60-х годов намеренно для обучения студентов языку программирования. Ф.Каин и А.Хейлсберг были студентами этого выдающегося профессора в  Цюрихском университете. После Каин сделал корпорацию Borland. Под наблюдением данных 2-х студентов язык Паскаль превратился в массивное средство разработки программ любой трудности.

Среда разработки Delphi 1 была открыта для создания программ под Windows 3.1, и стала  первым продуктом Borland для семейства Windows.

Появление новейшей версии Delphi 2 значительно отличило среду разработки от предыдущих продуктов. Данная версия была изобретена уже под 32-разядные операционные системы Windows 95 и Windows NT 4.

Следующие версии Delphi (3, 4, 5, б, 7) являлись следствием постепенного развития среды разработки - улучшались имеющиеся составляющие, добавлялись новейшие возможности, огромный интерес уделялся программированию баз данных и программ для глобальной сети Internet. Так же можно сказать, что Delphi время от времени называют еще как и Object Pascal.

Так же одной из инноваций разрешено полагать интеграция в Delphi технологии .Net от Microsoft.

Казалось бы, что следующею версию Delphi разумно было бы именовать 9, а на самом деле она именуется Borland Delphi 2005. Давай те разберемся отчего. Из главных особенностей среды разработки Delphi 2005 можно отметить то, что новенькая среда разработки объединила в себе целый эксперимент программирования и создания специальных продуктов для разработки программного обеспечения. В Delphi 2005 можно формировать программы для платформы Win32, а можно создавать программы под перспективную платформу .Net. Кроме того, до седьмой версии использовался язык программирования основанный на языкеPascal. В новейшей версии осуществлена возможность разработки программ на нескольких языках (Delphi, C++, Java), что ранее не появлялось ни в одной аналогичной среде разработки. Если так же к вышеперечисленному добавить, что в Delphi 2005 добавлено не мало новых компонентов и инструментов, то становиться ясно почему новая версия вышла под таким специфичным заглавием.

Последней и самой развитой версией среды, изготовленной для платформы Win32, стала версия Delphi 7 (2001 год). В ней, в частности, появился компилятор для .NET, пока в консольном варианте. Добавилось множество компонентов и Мастеров,  которые автоматизируют создание сетевых приложений. Была продолжена поддержка кроссплатформной технологии создания программ на базе Delphi и Kylix.

Листинг программы с комментариями:

unit form_main;

interface

uses

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

 Dialogs, StdCtrls, ToolWin, ComCtrls, Grids, ExtCtrls, mat_code, XPMan;

type

 TFormMain = class(TForm)

   CoolBar1: TCoolBar;

   Panel6: TPanel;

   Label3: TLabel;

   edText: TEdit;

   memAnalyze: TMemo;

   Panel2: TPanel;

   PageControl1: TPageControl;

   TabSheet1: TTabSheet;

   sgShannonFano: TStringGrid;

   TabSheet2: TTabSheet;

   Label1: TLabel;

   memShannonFano: TMemo;

   sgHuffman: TStringGrid;

   memHuffman: TMemo;

   XPManifest1: TXPManifest;

   Panel1: TPanel;

   Panel3: TPanel;

   Panel4: TPanel;

   Panel5: TPanel;

   procedure FormCreate(Sender: TObject);

   procedure FormDestroy(Sender: TObject);

   procedure edTextChange(Sender: TObject);

 private

   FModeler: TMatModeler;

   FCoderShannonFano: TMatCoder;

   FCoderHuffman: TMatCoder;

   procedure CreateCoderInfo(Coder: TMatCoder; StringGrid: TStringGrid; Memo: TMemo);

 end;

var

 FormMain: TFormMain;

implementation

uses math;

{$R *.dfm}

procedure TFormMain.FormCreate(Sender: TObject);

begin

 FModeler := TMatModeler.Create;

 FCoderShannonFano := TMatCoderShannonFano.Create(FModeler);

 FCoderHuffman := TMatCoderHuffman.Create(FModeler);

 edText.OnChange(Self);

end;

procedure TFormMain.FormDestroy(Sender: TObject);

begin

 FModeler.Free;

end;

procedure TFormMain.edTextChange(Sender: TObject);

begin

 FModeler.Execute(edText.Text);

 FCoderShannonFano.Execute;

 FCoderHuffman.Execute;

 with memAnalyze, Lines, FModeler do

 begin

   Clear;

   Add(Format('Длина сообщения (символов): %d', [Length(FModeler.Text)]));

   Add(Format('Кол-во символов алфавита: %d',[CharsPerTable]));

   Add(Format('Длина символа при равномерном кодировании (бит): %d', [BitsPerChar]));

   Add(Format('Длина сообщения при равномерном кодировании (бит): %d', [BitsPerText]));

     end;

 CreateCoderInfo(FCoderShannonFano, sgShannonFano, memShannonFano);

 CreateCoderInfo(FCoderHuffman, sgHuffman, memHuffman);

end;

procedure TFormMain.CreateCoderInfo(Coder: TMatCoder; StringGrid: TStringGrid; Memo: TMemo);

var rc, k, i, ci: Integer;

   CharItem: PMatCharTableItem;

   CodeItem: PMatCodeTableItem;

begin

 with StringGrid, Coder do

 begin

   rc := FModeler.CharsPerTable + 1;

   if rc = 1 then

   begin

      Inc(rc);

      Rows[1].Clear;

   end;

   RowCount := rc;

   Cells[0, 0] := 'Символ';

   Cells[1, 0] := 'Вероятность';

   Cells[2, 0] := 'Код';

   for k := 0 to CodesPerTable-1 do

   begin

     ci := CodeIndex[k];

     CodeItem := CodeTable[ci];

     CharItem := FModeler.CharTable[CodeItem.CharItem.Value];

     Cells[0, k+1] := Format('"%s"', [Chr(CodeItem.CharItem.Value)]);

     Cells[1, k+1] := Format('%.5f', [CharItem.Probability]);

     Cells[2, k+1] := Format('%s', [CodeItem.Code]);

     for i := 1 to Length(CodeItem.Code) do Cells[2 + i, k+1] := CodeItem.Code[i];

     for i := Length(CodeItem.Code) + 1 to 32 do Cells[2 + i, k+1] := '';

   end;

 end;

 with Memo, Lines, Coder do

 begin

   Clear;

   Add(Format('Средняя длина кода: %.5f',[AvgCodeLength]));

   Add(Format('Коэффициент относительной эффективности: %.5f',[RatioEffective]));

   Add(Format('Коэффициент сжатия кода: %.5f',[RatioCompression]));

   Add(Format('Длина сжатого сообщения (бит): %d', [BitsPerText]));

 end;

end;

end.

Пример 1.

Исходный текст: собака сказала Гав

Рис. 1. Результат сжатия файла методом Шеннона-Фано

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

Рис. 2. Результат сжатия файла методом Хаффмана

Пример 2.

Исходный текст: летела ворона

Рис. 3. Результат сжатия файла методом Шеннона-Фано

Далее перейдём  на вкладку кода Хаффмана и посмотрим код

Рис. 4. Результат сжатия файла методом Хаффмана

Пример 3.

Исходный текст: мороженое 580 гр

Рис. 5. Результат сжатия файла методом Шеннона-Фано

        Далее перейдём  на вкладку кода Хаффмана и посмотрим

Рис. 6. Результат сжатия файла методом Хаффмана

Идеальной реализацией задачи разрешено полагать алгоритмы Шеннона — Фано, названное так по имени 2-х исследователей, которые одновременно и  каждый самостоятельно спроектировали этот алгоритм: Клода Шеннона и Р. М. Фано. Алгоритм исследует входные данные и на их базе строит бинарное дерево минимального кодирования. Используя это дерево, потом разрешено исполнить повторное считывание входных данных и закодировать их; и Хаффмана, который чрезвычайно подобен алгоритму сжатия Шеннона-Фано. Этот алгоритм был изобретен Девидом Хаффманом в 1952 году, и оказался еще наиболее успешным, чем алгоритм Шеннона-Фано. Это обусловлено тем, что алгоритм Хаффмана математически гарантированно формирует меньший по размеру код для каждого из символов исходных данных.

Алгоритм, который мы рассматриваем – кодирование Шеннона-Фано, назван в честь 2-х исследователей, которые сразу, каждый самостоятельно разработали данный способ сжатия данных. Алгоритм исследует входные данные и на их основе строит бинарное дерево минимального кодирования. Используя это дерево, потом разрешено исполнить повторное считывание входных данных и закодировать их.

Алгоритм Шеннона-Фано работает последующим образом:

  1.  На вход приходят упорядоченные по невозрастанию частот данные.
  2.  Находится середина, которая делит алфавит примерно на две части. Эти части (суммы частот алфавита) примерно равны. Для левой части присваивается "1", для правой "0", таким образом мы получим листья дерева

Шаг 2 повторяется до тех пор, пока мы не получим единственный элемент последовательности, т.е. листок.

Кодирование Хаффмана является обычным алгоритмом для построения кодов меняющейся длины, имеющих минимальную среднюю длину. Этот очень известный метод служит основой почти всех компьютерных программ сжатия текстовой и графической информации. Метод Хаффмана сжимает данные до их энтропии, ежели вероятности знаков буквально одинаковы отрицательным ступеням числа 2. Алгоритм затевает основывать кодовое древо снизу кверху, потом скользит книзу по дереву, чтоб выстроить любой личный код от самого младшего бита к самому старшему. Начиная с работ Д. Хаффмана 1952 года, этот алгоритм являлся предметом почти всех изучений.

Основа всех методов сжатия

В базе всех способов сжатия лежит обычная мысль: если изображать нередко применяемые составляющие короткими кодами, а изредка применяемые - длинными кодами, то для сохранения блока данных требуется наименьший объем памяти, чем если бы все составляющие представлялись кодами схожей длины.

Точная связь между вероятностями и кодами установлена в теореме Шеннона о кодировании источника, которая гласит, что элемент sh вероятность появления которого приравнивается p( s,), выгоднее только представлять - 1о& p(sj) битами. Если при кодировании величина кодов постоянно в точности выходит одинаковым -log2 p( s,) битам, то в этом случае длина закодированной последовательности станет малой для всех вероятных методик кодирования. Если расположение вероятностей f= {pis, } постоянно, и вероятности появления частей автономны, то мы можем отыскать среднюю длину кодов как среднее взвешенное.

Это смысл в том же духе именуется энтропией распределения вероятностей F или энтропией источника в данный момент времени. Ни один компрессор не может сжать любой файл. После отделки любым компрессором величина части файлов уменьшится, а оставшейся части - увеличится или остается постоянным. Данный факт разрешено обосновать исходя из неравномерности кодирования, т. е. разнообразной длины используемых кодов, но более прост для осмысливания последующий комбинаторный довод.

Существует 2л разных файла длины п бит, где л = 0, 1, 2,... Если величина всякого токового файла в итоге обработки уменьшается хотя бы на 1 бит, то 2л исходным файлам станет подходить  наибольшее 2л-1 различающихся сжатых файлов. Тогда, по крайней мере, одному архивному файлу будет подходить, некоторое количество различающихся исходных, и, следовательно, его декодирование без утрат информации нереально в принципе.

Кодирование по методу Хаффмана

Алгоритм основан на том, что некоторые символы из обычного 256-символьного комплекта в случайном тексте имеют все шансы пересекаться почаще среднего периода повтора, а остальные – реже. Следовательно, если для записи распространенных символов применять короткие последовательности бит, длиной меньше 8, а для записи редких символов – длинные, то суммарный объем файла уменьшится. В итоге выходит классификация данных в виде дерева («двоичное дерево»).

Алгоритм Хаффмана основан на данной идее только с тем различием, что он используется ко всем символам алфавита. Первым шагом определяются числа повторений (веса) всех символов. На следующем шаге строится дерево кодирования. Используются две структуры данных - массив и дерево, в массив заносятся все символы и их веса, дерево пусто. Потом обретаем два редчайших символов, которые исключаются из массива и добавляются в дерево (листья). Также формируется новый узел дерева с весом равным сумме весов найденных символов и содержащий ссылки на эти символы. Этот узел добавляется в массив. Процедура повторяется пока в массиве не останется один элемент. Третий шаг - собственно кодирование.

Сжатие Хаффмана – это статистический способ сжатия, который уменьшает среднюю длину кодового слова для символов алфавита. Код Хаффмана может быть построен по следующему алгоритму:

  1.  Выписываем в ряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте;
  2.  Последовательно соединяем два символа с меньшими вероятностями появления в новый составной символ, возможность появления которого полагается равной сумме вероятностей составляющих его символов; в итоге мы построим дерево, любой узел которого имеет суммарную вероятность всех узлов, находящихся ниже него;
  3.  Прослеживаем путь к каждому листу дерева помечая направление к каждому узлу (к пример, вправо - 0, влево - 1).


Заключение.

В предоставленной курсовой работе мне была поставлена задача создать программу для методов кодирования Хаффмана и Шеннона-Фано на языке Delphi.

Первым именно такой алгоритм был опубликован Дэвидом Хаффманом (David Huffman) в 1952 году. Алгоритм Хаффмана состоит из двух проходов. На главном проходе основывается частотный словарь и генерируются коды. На другом же проходе происходит, естественно, шифрование.

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

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

Суть представленного алгоритма содержится в построении двоичного дерева с узловыми элементами из символов входного алфавита. И чем больше возможность появления символа в тексте, тем поближе он к корню. Каждой ветви назначается «вес» — битовый нуль или единица. Кодирование всякого символа делается проходом по дереву и выбором одной из двух ветвей, которое начинается с корня дерева и заканчивается листом с необходимым символом.

Метод Хаффмана широко используется, постепенно удаляется арифметическим сжатием. Своё место в этом исполнило то, что закончились время операции патентов, которые ограничивают внедрение арифметического сжатия. Кроме того, алгоритм Хаффмана не является приемлемым. Он подводит условные частоты появления символа в потоке частотами, которые представляют собой отрицательные степени двойки, в то время как арифметическое сжатие дает лучшую степень приближения частоты.


Библиография.

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

2. Искусство дизассемблирования К.Касперски Е.Рокко, БХВ-Петербург 2008. -780 с.

3. Win32 API. Эффективная разработка приложений. – СПб.: Питер, 2007 – 572 с.: ил.

4. Жоголев Е.A. Ж.78 Технология программирования. – М., Научный Мир, 2004, 216 с.

5. Фундаментальные алгоритмы на C++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - К.: Издательство «ДиаСофт», 2001.- 688 с.

6.  Искусство программирования на Ассемблере. Лекции и упражнения: Голубь Н.Г. – 2-е изд., испр. и доп. – СПб: ООО «ДиаСофтЮП». 2002. – 656 с. Описание архиватора Narc фирмы Infinity Design Concepts, Inc

  1.  Чарльз Сейтер, 'Сжатие данных', "Мир ПК", N2 1991
  2.  Baтoлин Д., Ратушняк A., Смирнов M., Юкин B. "Методы сжатия данных" - 2003г.
  3.  Балашов K.Ю. "Сжатие информации: анализ методов и подходов" - Минск, 2000г.
  4.  Мастрюков Д. "Алгоритмы сжатия информации"
  5.  Потапов В.Н. "Арифметическое кодирование вероятностных сточников"
  6.  Потапов В.H. "Обзор методов неискажающего кодирования дискретных источников"
  7.  Методические указания для студентов, обучающихся на специальности 230700(Информационный сервис). Е.Р. Пантелеев, М.М. Хаджар, 2004, 25 с.
  8.  Семенова Ю.A. "Телекоммуникационные технологии"
  9.  Шелвин E. "Алгоритм арифметического кодирования"
  10.  Фомин  "Основы сжатия информации" Санкт-Петербург, 1997г.
  11.  Яблонский C.B. “Введение в дискретную математику”. // M. “Наука”, 1986. Раздел “Теория кодирования”.
  12.   Климов “Форматы графических файлов”- “ДиаСофт” 1995.
  13.   Ватолин Д.С. “Сжатие статических изображений” // Открытые системы сегодня. Номер 8 (29) Апрель 1995
  14.    Ватолин Д.C. “МРЕG - стандарт ISO на видео в системах мультимедиа” // Открытые системы. Номер 2. Лето 1995


 

А также другие работы, которые могут Вас заинтересовать

75002. Наше диво, калинове, кохана українська мово. Літературн-омузичне свято до Дня української мови й й писемності 71 KB
  Мова кожного народу – Неповторна і своя В ній гримлять громи в негоду В тиші трелі соловя. Берегти її плекати Буду всюди й повсякчас Бо ж єдина такяк мати Мова в кожного із нас В. Ведуча Скарбе мій єдиний Ведучий Це сьогодні на твою честь ми проводимо свято НАШЕ ДИВО КАЛИНОВЕ КОХАНА УКРАЇНСЬКА МОВО Виконання...
75003. Сценарій свята до Дня української писемності та мови 88 KB
  Найбільше і найдорожче добро в кожного народу це його мова ота жива схованка живого духу його багата скарбниця в яку народ складає і своє давнє життя і свої сподівання розум досвід почування. Українська мова в багатстві витонченості й гнучкості не поступається ані жодній із сучасних літературних мов слов’янства. З епохи Київської Русі можна говорити й про українську літературну мову та жива розмовна мова українського народу набагато давніша.
75004. Мова моя українська. Методична розробка виховного заходу для старшокласників 85.5 KB
  Мова це великий дар природи. І серед них – ніби запашна квітка в чудовому букеті – українська мова. У рідному домі завжди звучить найближча найзрозуміліша рідна мова бо бринить вона із ласкавих бабусиних вуст із дідусевої говірки із маминої пісні із батьківського слова часом суворого а часом жартівливого. Наша мова – українська тому що наша земля – Україна.
75005. Мова наша солов’їна, виховний захід 58 KB
  Показати дітям красу і багатство української мови за допомогою народної творчості, творів письменників і поетів. Викликати бажання вивчати рідну мову, милуватися її красою Виховувати любов до рідної мови, до своєї землі, свого народу.
75006. Мова моя українська чарівна. Виховний захід 40.5 KB
  Обладнання: зал прикрашений плакатами з крилатими висловами про мову прислів’ями плакати з назвами команд завдання загадки ребуси кросворди. І будемо зараз готові Полинути в країну рідного слова...
75007. Мово моя материнська, Сценарій свята 52 KB
  Чудова наша мова – міцне моє коріння А як же я без нього могла б на світі жить Тоді б мене чекало духовне зубожіння Бо мову і Вітчизну не можна розділить Пісня О мово моя муз. Мов солов’ї наша мова співуча. Вірте – не вірте Твердо я знаю: Мова – це вірність рідному краю...
75008. Хімічна мозаїка, Сценарій з хімії 61 KB
  Ведуча: Вогонь у темряву ночей Приніс на землю Прометей. Ведуча доторкаючись до вогню: Я стверджую категорично: Реакція екзотермічна дує на палець. Ведуча звертається до кухаря: За сіль ви не забули друже Її відсутність не байдужа...
75009. Музыкальный тайник, внеклассное мероприятие для 7 класса 199 KB
  Мотивация интереса к непопулярным» музыкальным жанрам; пробуждение у учащихся заинтересованность в изучении предмета; активизация мыслительной и речевой деятельности; развитие музыкальной эрудиции, логического мышления; воспитание музыкально-познавательных потребностей и интересов в приобретении основы музыкально – исторических знаний, лидерских и коммуникативных качеств личности.
75010. Мусор – глобальная проблема человечества. Урок для устойчивого развития по программе «Моя счастливая планета» в 3-А классе 59 KB
  Цель урока: познакомить учащихся с терминами экология экологическая безопасность формировать представления об источниках и способах утилизации бытового мусора научить выполнять правила личной экологической безопасности познакомить с экологическими проблемами современности и путями их решения формировать ответственное отношение к использованию природных ресурсов земли.