Информационный сервер для программистов: Исходники со всего света. Паскальные исходники со всего света
  Powered by Поисковый сервер Яndex: Найдется ВСЁ!
На Главную Pascal Форум Информер Страны мира
   Архивы и Архиваторы    >>    archuf
   
 
 О методе упаковки Хаффмана  Vladimir Kononov 12.03.1993

В статье подробно рассматриваются алгоритмы, производящие сжатие без потерь, т.е. допускающие восстановление исходной информации "байт в байт": Running, LZW, Huffman. Приведен пример программы сжатия/распаковки по методу Хаффмана.



17k 
 

N.B. Здесь рассматриваются только алгоритмы производящие сжатие без потерь, т.е. допускающие восстановление исходной информации "байт в байт". Running - Это самый простой из методов упаковки информации. Предположите что Вы имеете строку текста, и в конце строки стоит 40 пробелов. Налицо явная избыточность имеющейся информации. Проблема сжатия этой строки решается очень просто - эти 40 пробелов ( 40 байт ) сжимаются в 3 байта с помощью упаковки их по методу повторяющихся символов (running)... LZW - История этого алгоритма начинается с опубликования в мае 1977 г. Дж. Зивом ( J. Ziv ) и А. Лемпелем ( A. Lempel ) статьи в журнале "Информационные теории" под названием "IEEE Trans". В последствии этот алгоритм был доработан Терри А. Велчем (Terry A. Welch) и в окончательном варианте отражен в статье "IEEE Compute" в июне 1984 . В этой статье описывались подробности алгоритма и некоторые общие проблемы с которыми можно столкнуться при его реализации. Позже этот алгоритм получил название - LZW (Lempel - Ziv - Welch)... Huffman - Сначала кажется что создание файла меньших размеров из исходного без кодировки последовательностей или исключения повтора байтов будет невозможной задачей. Но давайте мы заставим себя сделать несколько умственных усилий и понять алгоритм Хаффмана ( Huffman ). Потеряв не так много времени мы приобретем знания и дополнительное место на дисках...