Стандартизован 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 стр) Фундаментальные алгоритмы и структуры данных в Delphi
http://www.delphiplus.org/fundamentalnie-algoritmy-i-struktury-dannih/szhatie-dannih.htmlС.В.Яблонский «Введение в дискретную математику». // М. «Наука», 1986
Раздел «Теория кодирования"Д.С.Ватолин «Сжатие статических изображений» // Открытые системы сегодня. Номер 8 (29) Апрель 1995Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин.
Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. — Диалог-МИФИ, 2002. —
С. 384. — ISBN 5−86 404−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−94 836−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/lec71.htmСеменов Ю. А. Сжатие данных с использованием преобразования Барроуза-Вилера
http://book.itep.ru/2/26/burv263.htmСжатие с потерями
http://mf.grsu.by/UchProc/livak/po/comprsite/theory_image01.htmlА.С.Климов «Форматы графических файлов» // НИПФ «Диа
Софт Лтд", 1995.В. Ю. Романов «Популярные форматы файлов для хранения графических изображений на IBM PC» // Москва «Унитех», 1992Д.С.Ватолин. Алгоритмы cжатия изображений. — М.:Издательский отдел факультета Вычислительной Математики и Кибернетики МГУ им.
М.В.Ломоносова, 1999 г. — 76 с. Фаронов В. В. Системы программирования Delphi. — СПб.:БХВ-Петербург, 2005. — 912 с. Культин Н. Б. Программирование на ObjectPascal. -
СПб.:БХВ-Петербург, 2002. — 528 с.
