Описание программы кодирования Хаффмана

kol:=0;

while c<>'0' do //считываем  унарный код 

begin

read(f,c);

kol:=kol+1;

end; //q

q:=kol; //по считанному унарному коду определяем частное q

s_temp:='';

for i:=1 to b-1 do //считывание b-1битов кода

begin

read(f,c);

s_temp:=s_temp+c;

end;

b1:=BinToInt(s_temp); //считаем возможный остаток b1

read(f,c);

s_temp:=s_temp+c//считывание b битов кода

b2:=BinToInt(s_temp);// считаем возможный остаток b2

if (b2<=cutoff)or(b2-cutoff>=M)or(b2-cutoff<=cutoff-1) then //проверка

//условия формирования  кода остатка по методу Голомба

//в зависимости  от условия остатком является  либо b1, либо b2

result:=result+Code_table[q*M+b1]

else

begin

result:=result+Code_table[q*M+b2-cutoff];

read(f,c);

end;

end;

closefile(f); //закрываем  файл

end;

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

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

Первые теоретические  разработки в области сжатия информации относятся к концу 40-х годов. В  конце семидесятых появились работы Шеннона, Фано и Хафмана. К этому времени относится и создание алгоритма FGK (Faller, Gallager, Knuth), где используется идея "сродства", а получатель и отправитель динамически меняют дерево кодов.

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

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

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

 

1. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. – М.: ДИАЛОГ–МИФИ, 2009;

2. Вернер М. Основы кодирования. Учебник для ВУЗов. – М.: Техносфера, 2007;

3. Лидовский В. В. Теория информации: Учебное пособие. — М.: Компания Спутник+, 2010;

4. Набережнов Г. М., Пьянов И. П., Чугунов Е. Н., Шлеймович М. П. Компьютерная графика: Учебное пособие для студентов специальности «Автоматизированные системы обработки информации и управления» /Под общ. ред. к. т. н., доцента Набережнова Г. М. – 2 – е изд., доп. – Казань: ИСПО РАО, 2011;

5. Сэломон Д. Сжатие данных, изображений и звука. – М.: Техносфера, 2009;

6. Теория информации и кодирование/ Самсонов Б.Б., Плохов Е.М., Филоненков А.И., Кречет Т.В. – Ростов н/Д, 2008;

7. Шень А. Программирование: теоремы и задачи. – 2 – е изд., испр. и доп. – М.: МЦНМО, 2007.

8. Арапов Д. Пишем упаковщик //Монитор, 2009;

9. Балашов К. Ю. Сжатие информации: анализ методов и подходов. – Минск, 2009;

10.Дискретная математика и математические вопросы кибернетики. Т.1. /Ю.Л. Васильев, Ф. Я. Ветухновский, В. В. Глаголев, Ю. И. Журавлев, В. И. Левенштейн, С. В. Яблонский. Под общей редакцией С. В. Яблонского и О. Б. Лупанова. – М.: Главная редакция физико – математической литературы изд–ва «Наука», 1974;

11.Дмитриев В.И. Прикладная теория информации: Учеб. для студ. вузов по спец. «Автоматизированные системы обработки информации и управления». - М.: Высш.шк., 2009;

12.Игнатов В.А. Теория информации и передачи сигналов: Учебник для вузов. – 2-е изд., перераб. и доп. – М.: Радио и связь, 1991;

13.Кричевский Р. Е. Сжатие и поиск информации. – М.: Радио и связь, 1989;

14.Куликовский Л.Ф. и др. Теоретические основы информационных процессов. - М.: Высш.шк., 1987;

15.Мастрюков Д. Алгоритмы сжатия информации. Ч. 1. Сжатие по Хаффмену //Монитор, 2009;

16. Мастрюков Д. Алгоритмы сжатия информации. Ч. 2. Арифметическое кодирование //Монитор, 2010;

17.Мастрюков Д. Алгоритмы сжатия информации. Ч. 3. Алгоритмы группы LZ //Монитор, 2010;

18.Мастрюков Д. Алгоритмы сжатия информации. Ч. 3. Алгоритмы группы LZ //Монитор, 2010;

19.Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. -М.: Мир, 1976;

20.Ризаев И.С. Сборник задач по курсу “Теория информации и кодирование”, Казань, КАИ, 1976;

21.Семенюк В. В. Экономное кодирование дискретной информации. – СПб.: СПб ГИТМО (ТУ), 2009;

22.Смирнов М. А. Использование методов сжатия данных без потерь информации в условиях жестких ограничений на ресурсы устройства – декодера. //www.compression.ru

24.Смирнов М. А. Обзор применения методов безущербного сжатия данных в СУБД //www.compression.ru;

25.Темников Ф.Е. и др. Теоретические основы информационной техники. -М.: Энергия, 2005;

26.Фомин А. А. Основы сжатия информации. – СПб.: СПГТУ, 1998.

27.Хаффман Д.А. Метод построения кодов с минимальной избыточностью: Пер. с англ. //Кибернетический сборник. – М.: ИЛ, 1961. – Вып. 3. – С.79–87;