Алгоритмы сжатия данных

Оглавление
Введение
1. Сжатие данных
1.1. Основные понятия и определения
1.2. Классификация методов сжатия
2. Алгоритмы сжатия данных без потерь
2.1. Вероятностные методы сжатия
2.1.1. По алгоритму Хаффмана
2.1.2. По алгоритму Шеннона-Фано
2.2. Арифметические методы
2.3. Адаптивный алгоритм сжатия
2.4. Сжатие данных с использованием преобразования Барроуза-Вилер
2.5. Алгоритм Зива-Лемпеля
3. Алгоритмы сжатия данных с потерями
3.1. Алгоритм JPEG
3.2. Рекурсивный (волновой) алгоритм
4. Практическая часть
Заключение
Список литературы

Стандартизован JPEG в 1991 году. Но уже тогда существовали алгоритмы, сжимающие сильнее при меньших потерях качества. Дело в том, что действия разработчиков стандарта были ограничены мощностью существовавшей на тот момент техники [19].3.2. Рекурсивный (волновой) алгоритмРекурсивный алгоритм сжатия называется на английском языке wavelet, то есть волновое сжатие или сжатие с использованием всплесков. Этот вид архивации основан на использовании идеи когерентности областей. Ориентирован алгоритм на цветные и черно-белые изображения с плавными переходами. Он идеально подходит для изображений типа рентгеновских снимков. Коэффициент сжатия задается и варьируется в пределах 5-100. При попытке задать больший коэффициент на резких границах, особенно проходящих по диагонали, проявляется "лестничный эффект" – ступеньки разной яркости размером в несколько пикселей.Идея алгоритма заключается в том, что сохраняется в файл разница – число между средними значениями соседних блоков в изображении, которая обычно принимает значения, близкие к 0.Достоинствами данного алгоритма является легкость реализации возможности постепенного "проявления" изображения при передаче изображения по сети. Кроме того, поскольку в начале изображения фактически хранится его уменьшенная копия, упрощается показ "огрубленного" изображения по заголовку [20].4.Практическая частьВ практической части работы разработана программа, реализующая алгоритм Хаффмана.Для разработки программы использован язык Delphi 7[21, 22, 23].На рисунке 4.1. показано окно разработанной программы.Рисунок 4.1. Программа, реализующие алгоритм кодирование ХаффманаПрограмма работает следующим образом:1. Пользователь вводит в окно "Текст сообщение", информацию, которую необходимо закодировать по алгоритму Хаффмана.2. Пользователь нажимаете на кнопку "кодировать"3. В окно "закодированное сообщение" выводится код полученый по алгоритму Хаффмана (рисунок 4.2).Рисунок 4.2. Работа программыДля декодирования сообщения, отображаемого в окне "закодированное сообщение" необходимо нажать на кнопку "Декодировать" и в окно "декодированное сообщение" будет выведен результат (рисунок 4.3).Рисунок 4.3. Работа программыПервый модуль содержит две процедуры обработки нажатия кнопок "Кодирование" и "Декодирование" (листинг 1). Листинг 1unithufftest;interfaceuses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, Huffman, StdCtrls;type TForm1 = class(TForm) Memo1: TMemo; Memo2: TMemo; Memo3: TMemo; Button1: TButton; Button2: TButton; Label1: TLabel; Label2: TLabel; Label3: TLabel; procedure Button2Click(Sender: TObject); procedure Button1Click(Sender: TObject);private { Private declarations } public { Public declarations } end;var Form1: TForm1; huffTree: PhtTree; huffTable: PhlTable;implementation{$R *.dfm}procedure TForm1.Button1Click(Sender: TObject);begin huffTree:= BuildTree(PAnsiChar(Memo1.Text)); huffTable:= BuildTable(huffTree); Memo2.Clear; Memo2.Text:= Encode(huffTable, Memo1.Text);end;procedure TForm1.Button2Click(Sender: TObject);begin Memo3.Clear; Memo3.Text:= Decode(huffTree, Memo2.Text);end;end.Основной модуль приведен на листинге 2.Листинг 2unit Huffman;interfaceusesWindows, Queue;typePhtNode = ^htNode;htNode = recordsymbol: AnsiChar;left: PhtNode;right: PhtNode;end;PhtTree = ^htTree;htTree = recordroot: PhtNode;end;PhlNode = ^ hlNode;hlNode = recordsymbol: AnsiChar;code: PAnsiChar;next: PhlNode;end;PhlTable = ^hlTable;hlTable = recordfirst: PhlNode;last: PhlNode;end;function BuildTable(huffmanTree: PhtTree): PhlTable;function BuildTree(InputStr: PAnsiChar): PhtTree;function Encode(hTable: PhlTable; EncodeString: String): String;function Decode(hTree: PhtTree; DecodeString: String): String;implementationfunction StrLCopy(Dest: PChar; const Source: PChar; MaxLen: Cardinal): PChar; assembler;asm PUSH EDI PUSH ESI PUSH EBX MOV ESI,EAX MOV EDI,EDX MOV EBX,ECX XOR AL,AL TEST ECX,ECX JZ @@1 REPNE SCASB JNE @@1 INC ECX@@1: SUB EBX,ECX MOV EDI,ESI MOV ESI,EDX MOV EDX,EDI MOV ECX,EBX SHR ECX,2 REP MOVSD MOV ECX,EBX AND ECX,3 REP MOVSB STOSB MOV EAX,EDX POP EBX POP ESI POP EDIend;procedure TraverseTree(treeNode: PhtNode; Table: PhlTable; k: Integer; Code: PAnsiChar); {обработка ветвей полученного дерева}var l: Integer;aux: PhlNode;beginif (treeNode^.Left= nil) and (treeNode^.Right = nil) then begincode[k]:= #0; l:= Length(code);GetMem(aux, SizeOf(hlNode)); if l<>0 then begin GetMem(aux^.code, Length(code)); StrLCopy(aux^.code, code, Length(code)); end else begin GetMem(aux^.code, 1); aux^.code:= '0'; end;aux.symbol:= treeNode.symbol;aux.next:= nil;if (table^.first = nil) then begintable^.first:= aux;table^.last:= aux;end else begintable^.last^.next:= aux;table^.last:= aux;end;end;if (treeNode^.left <> nil) then begincode[k]:= '0';TraverseTree(treenode^.left, table, k+1, code);end;if (treeNode^.right <> nil) then begincode[k]:= '1';TraverseTree(treeNode^.right, table, k+1, code);end;end;function BuildTable(huffmanTree: PhtTree): PhlTable; {процедура построения таблицы кодирования}varcode: array [0..255] of Char;k: Integer;beginGetMem(Result, SizeOf(hlTable));Result^.first:= nil;Result^.last:= nil;FillChar(code[0], 256, 0);k:= 0;TraverseTree(huffmanTree^.root, Result, k, code);end;function BuildTree(InputStr: PAnsiChar): PhtTree; {процедура построения дерева}varproability: array [0..255] of Longint;i, priority: Integer;huffmanQueue: PQueue;aux, left, right, newNode: PhtNode;beginfor i:= 0 to 255 doproability[i]:= 0;for i:= 0 to Length(InputStr)-1 doInc(proability[Byte(InputStr[i])]);InitPQueue(huffmanQueue);for i:=0 to 255 do beginif proability[i]<>0 then beginGetMem(aux, SizeOf(htNode));aux^.left:= nil;aux^.right:= nil;aux.symbol:= Char(i);AddPQueue(huffmanQueue, aux, proability[i]);end;end;while (huffmanQueue^.size <> 1) do beginpriority:= huffmanQueue^.first^.priority+huffmanQueue^.first^.next^.priority;left:= GetPQueue(huffmanQueue);right:= GetPQueue(huffmanQueue); GetMem(newNode, SizeOf(htNode));newNode^.left:= left;newNode^.right:= right;AddPQueue(huffmanQueue, newNode, priority);end;GetMem(Result, SizeOf(htTree));Result^.root:= getPQueue(huffmanQueue);end;function Encode(hTable: PhlTable; EncodeString: String): String; {процедура кодирования}var i, l: Integer; trv: PhlNode;beginResult:= ''; l:= Length(EncodeString); i:= 1; repeat trv:= hTable^.first; while trv^.symbol<>EncodeString[i] do trv:= trv^.next; Result:= Result+trv^.code+' '; Inc(i); until i>l;end;function Decode(hTree: PhtTree; DecodeString: String): String; {процедура декодирования}var i, l: Integer; trv: PhtNode;begin trv:= hTree^.root; i:= 1; l:= Length(DecodeString); repeat if (DecodeString[i]=' ') then begin inc(i); Continue; end; if (trv^.left=nil)and (trv^.right=nil) then begin Result:= Result+trv^.symbol; trv:= hTree^.root; end; if (DecodeString[i]='0')and(trv^.left <> nil) then trv:= trv^.left; if (DecodeString[i]='1')and(trv^.right <> nil) then trv:= trv^.right; Inc(i); until i>l; if (trv^.left=nil)and (trv^.right=nil) then Result:= Result+trv^.symbol;end;end. ЗаключениеСжатием данных (data compression) называется алгоритм эффективного кодирования информации, при этом она должна занять объем памяти меньше, чем у исходного сообщения. Таким образом, происходит избавление от избыточности (redundancy), т.е. удаляются из физического представления данных биты, которые не несут смысловой нагрузки и в действительности не требуются, при этом остается такое кол только количество битов, которое обязательно для представления информации в соответствии со значением энтропии.В работе рассмотрено понятие сжатия данных, постоянна классификация алгоритмов сжатия данных. Все алгоритмы разделены на две большие группы с не искажающие (без потерь) и искажающие с потерями. Подробно рассмотрены наиболее распространенные алгоритмы сжатия информации из каждой группы. В практической части разработана программа кодирования информации по алгоритму Хаффмана. Для разработки программы использован язык Delphi 7Список литературыЮ.А.Семенов, Алгоритмы телекоммуникационных сетей Бином. Интернет университет Информационных технологий, Москва, 2007, (трехтомник ~1900 стр)Фундаментальные алгоритмы и структуры данных в Delphihttp://www.delphiplus.org/fundamentalnie-algoritmy-i-struktury-dannih/szhatie-dannih.htmlС.В.Яблонский “Введение в дискретную математику”. // М. “Наука”, 1986. Раздел “Теория кодирования”Д.С.Ватолин “Сжатие статических изображений” // Открытые системы сегодня. Номер 8 (29) Апрель 1995Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. — Диалог-МИФИ, 2002. — С. 384. — ISBN 5-86404-170-X 3000 экз.Артюшенко В. М., Шелухин О. И., Афонин М. Ю. Цифровое сжатие видеоинформации и звука. Издательство: Дашков и Ко, 2004. - 426 с.Алгоритмы архивации данных http://www.structur.h1.ru/arch.htmИнформатика. Базовый курс. / Под ред. С.В.Симоновича. - СПб., 2000 г.Т.О. Сундукова, Г.В. Ваныкина Структуры и алгоритмы компьютерной обработки данных http://www.intuit.ru/department/algorithms/staldata/41/2.html Метод Xаффмана и родственные методы http://mindspring.narod.ru/alg/huffman.htmlД. Сэломон. Сжатие данных, изображения и звука. — М.: Техносфера, 2004. — С. 368. — ISBN 5-94836-027-X 3000 экзС. Зелинский В цифровых тискахhttp://bessarab.ucoz.ru/publ/fizikam/szhatie_dannykh/2-1-0-6А. М. Яглом, И. М. Яглом. Вероятность и информация. — М.: «Наука», 1973.Семёнов Ю.А. Локально адаптивный алгоритм сжатия book.itep.ruРабота со сжатыми данными http://ndo.sibsutis.ru/bakalavr/sem2/course85/lec7_1.htmСеменов Ю.А. Сжатие данных с использованием преобразования Барроуза-Вилера http://book.itep.ru/2/26/burv_263.htmСжатие с потерями http://mf.grsu.by/UchProc/livak/po/comprsite/theory_image_01.htmlА.С.Климов “Форматы графических файлов” // НИПФ “ДиаСофт Лтд”, 1995.В.Ю.Романов “Популярные форматы файлов для хранения графических изображений на IBM PC” // Москва “Унитех”, 1992Д.С.Ватолин. Алгоритмы cжатия изображений. - М.:Издательский отдел факультета Вычислительной Математики и Кибернетики МГУ им. М.В.Ломоносова, 1999 г. — 76 с.Фаронов В.В. Системы программирования Delphi. – СПб.:БХВ-Петербург, 2005. – 912 с.Культин Н.Б. Программирование на ObjectPascal. – СПб.:БХВ-Петербург, 2002. – 528 с.