Новинки:

Сайт подключен к Orphus. Если вы заметили опечатку, выделите слово и нажмите Ctrl+Enter. Спасибо!

Универсальные алгоритмы сжатия данных:

Методы Хаффмана и Шеннона-Фано

>> Русские материалы | Английские материалы | Исходные тексты компрессоров

Смотрите также материалы:
- Методы Хаффмана и Шеннона-Фано
- Арифметическое сжатие
- Кодирование целых чисел
- Обзоры универсальных алгоритмов сжатия данных
- Книга "Методы сжатия данных". Раздел 1 "Методы сжатия без потерь"



>> Русские материалы | Английские материалы | Исходные тексты компрессоров
Авторы Название Описание Рейтинг
Jones G. Кодирование с минимальной избыточностью по методу Хаффмэна. Описание и реализация статического и адаптивного алгоритмов кодирования по Хаффману.
Из книги: Г. Джоунз. Программирование на языке оккам. - М.: Мир,1989.
TXT.RAR  15 кбайт
5
Александров О.Е., Попков В.И. Компрессия данных или измерение и избыточность информации. Метод Хаффмана Методичка к лабораторной работе. Краткий обзор способов сжатия, изучение метода Хаффмана. Вроде как статический алгоритм рассмотрен хорошо.
Авторская страница
Методические указания к лабораторной работе /О. Е. Александров. Екатеринбург: УГТУ, 2000. 52с.
PDF.RAR  458 кбайт
Исходники на Pascal, прилагаемые к методичке:
скачать  54 кбайт
5
Симаков А. Код Хаффмана Хорошее описание идеи метода Хаффмана и алгоритма кодирования-декодирования статических кодов. См. также реализацию SHCODEC ниже.
Сыктывкарский Государственный Университет, Кафедра Прикладной Математики, октябрь 2002.
HTML  60 кбайт
HTML.RAR  28 кбайт
5
tiger Кодирование Шеннона-Фано Краткое описание метода Шеннона-Фано с демонстрационном примером реализации.
2002. Авторская страница: http://aforge.ibd.lv/?8
HTML  15 кбайт
HTML.RAR  3 кбайт
Пример реализации на C++  26 кбайт
?
Самойлов М.Ю., Самойлова Т.А. Использование матричных операций при построении дерева Хаффмена На примере широко известного метода кодирования, основанного на построении дерева Хаффмена, рассмотрена возможность параллельных вычислений с использованием матричного представления данных и специально определяемой операции матричного умножения над ними. Получены временные оценки наиболее трудоемких по вычислительной сложности этапов кодирования при их реализации на суперкомпьютерах.
Математическая морфология. Электронный математический и медико-биологический журнал. Русская версия 2.0. -Том 2. -Вып.2.-1997.-246 с.-Смоленск:СГМА
HTML.RAR  42 кбайт
?
Мастрюков Д. Сжатие по Хаффмену Описание адаптивного алгоритма сжатия по Хаффману.
Алгоритмы сжатия информации. Часть 1. Сжатие по Хаффмену. //Монитор, 1993. - N7-8.
PDF  190 кбайт
DOC.RAR  40 кбайт
Часть статьи:
HTML.RAR  27 кбайт
Исходник на C к статье:
скачать  6 кбайт
5
Невесенко Н.В. Хаффман в плане минимизации программы Дается практическое описание кодирования по Хаффману. Описываются алгоритмы сжатия и распаковки, позволяющие минимизировать размер кодера и декодера. Приводятся иллюстрации реализации на Ассемблере.
22.10.2002
Авторская страница
Текст в HTML
?
Янковой М. Динамическое сжатие методом Хаффмана Неформальное описание динамического (адаптивного) алгоритма. К тексту прилагаются исходники на Visual Basic + Asm.
HTML
RTF.RAR  33 кбайт
исходный код реализации  29 кбайт
4
Кошкин Г.М. Энтропия и информация Содержит краткое неформальное описание кодирования Шеннона-Фано на конкретном примере. Также рассмотрены основные свойства энтропии и информации для дискретных случайных объектов.
Соросовский образовательный журнал, 2001, N 11, с. 122–127.
PDF.RAR  90 кбайт
3


>> Русские материалы | Английские материалы | Исходные тексты компрессоров
Huffman D. A Method for the Construction of Minimum-Redundancy Codes
Оригинальная статья Хаффмана
An optimum method of coding an ensemble of messages consisting of a finite number of members is developed. A minimum-redundancy code is one constructed in such a way that the average number of coding digits per message is minimized.
Proceedings of IRE, vol.40, N9, pp.1098-1101, September 1952.
PDF  332 кбайт
5
Gallager R. Variations on a Theme by Huffman Хорошее описание канонических кодов Хаффмана. Оригинальное описание алгоритма построения адаптивных кодов.
IEEE Transactions on Information Theory, Vol. IT-24, No. 6, Nov. 1978. pp. 668-674.
PDF.RAR  133 кбайт
5
Hirschberg D., Lelewer D. Efficient decoding of prefix codes Хорошее описание нескольких способов декодирования кодов Хаффмана.
Communications of the ACM, vol.33, No.4, 1990, pp.449-459.
PDF.RAR  108 кбайт
PS.RAR  47 кбайт
5
Abrahams J. Huffman Code Trees and Variants Краткий обзор литературы, посвященной кодам Хаффмана.
DIMACS, Rutgers University.
PDF.RAR  44 кбайт
5
De Prisco R., De Santis R. On the Data Expansion of the Huffman Compression Algorithm Доказано, что верхняя граница (худший случай) увеличения длины закодированной по алгоритму Хаффмана последовательности равна 1.256 битам на каждый исходный символ.
The Computer Journal, Volume 41, No. 3, 1998, pp. 137-144.
PDF.RAR  77 кбайт
PS.RAR    56 кбайт
3
Schindler M. Practical Huffman coding Описание основных приемов для эффективной реализации кодирования по Хаффману.
Сайт "Data Compression Consulting", Aug., Oct. 1998.
HTML.RAR  11 кбайт
5
Moffat A., Turpin A. On the Implementation of Minimum Redundancy Prefix Codes Описание приемов эффективного кодирования и декодирования кодов Хаффмана.
IEEE Transactions on Communications, Vol. 45, No. 10, pp.1200-1207, Oct. 1997.
PDF.RAR  175 кбайт
5
Milidiu R., Pessoa A., Laber E. Three Space-Economical Algorithms for Calculating Minimum-Redundancy Prefix Codes ...we present the Fast LazyHuff (F-LazyHuff), the Economical LazyHuff (E-LazyHuff), and the Best LazyHuff (B-LazyHuff) algorithms. F-LazyHuff runs in O(n) time but requires O(min{H^2, n}) additional space (H is the length of the greatest codeword). On the other hand, E-LazyHuff runs in O(n + n log(n/H)) time, requiring only O(H) additional space. Finally, B-LazyHuff asymptotically overcomes the previous algorithms, requiring only O(n) time and O(H) additional space...
IEEE Transactions on Information Theory, Vol. 47, No. 6, pp.2185-2198, Sep. 2001.
PDF.RAR  322 кбайт
?
Long D., Jia W. Optimal Maximal Prefix Coding and Huffman Coding ...Novel maximal prefix coding different from the Huffman coding is introduced. Relationships between the Huffman coding and optimal maximal prefix coding are discussed... Comparing with the Huffman coding, maximal prefix coding is a more flexible compression method.
Proceedings of The Seventh International Conference on Distributed Multimedia Systems, Taipei, Taiwan, Sept. 26-28, 2001, pp. 101-107.
PDF.RAR  246 кбайт
PS.RAR    187 кбайт
?
Chowdhury R.A., Kaykobad M. An Efficient Decoding Technique for Huffman Codes We present a new data structure for Huffman coding in which in addition to sending symbols in order of their appearance in the Huffman tree one needs to send codes of all circular leaf nodes (nodes with two adjacent external nodes), the number of which is always bounded above by half the number of symbols...
Information Processing Letter, Vol. 81, N. 6, pp.305--308, March 2002
PDF.RAR  99 кбайт
PS.RAR    80 кбайт
?
Fraenkel A.S., Klein Sh.T. Bidirectional Huffman Coding Under what conditions can Huffman codes be efficiently decoded in both directions? The usual decoding procedure works also for backward decoding only if the code has the affix property, i.e., both preffix and suffix properties. Some affix Huffman codes are exhibited, and necessary conditions for the existence of such codes are given. An algorithm is presented which, for a given set of codeword lengths, constructs an affix code, if there exists one. Since for many distributions there is no affix code giving the same compression as the Huffman code, a new algorithm for backward decoding of non-affix Huffman codes is presented...
August 1989
PDF.RAR  262 кбайт
PS.RAR    114 кбайт
?
Bookstein A., Klein Sh.T. Is Huffman Coding Dead? In recent publications about data compression, arithmetic codes are often suggested as the state of the art, rather than the more popular Huffman codes. While it is true that Huffman codes are not optimal in all situations, we show that the advantage of arithmetic codes in compression performance is often negligible. Referring also to other criteria, we conclude that for many applications, Huffman codes should still remain a competitive choice.
1998
PDF.RAR  231 кбайт
PS.RAR    103 кбайт
?


>> Русские материалы | Английские материалы | Исходные тексты компрессоров >> C/C++ | Pascal/Delphi | Assembler | Прочие языки

>> Исходные тексты компрессоров >> C/C++ | Pascal/Delphi | Assembler | Прочие языки
Павлов И. ARG Архиватор, использующий статический алгоритм Хаффмана.
Язык: C
версия 1.00.001 BETA  16 кбайт
?
Мастрюков Д. Huffman Компрессор, использующий адаптивный алгоритм Хаффмана.
Язык: C
Из статьи "Алгоритмы сжатия информации. Часть 1. Сжатие по Хаффмену"// Монитор, N7-8, 1993.
скачать  6 кбайт
4
MacDonald J. Dynamic Huffman Coding Реализация адаптивного алгоритма Хаффмана в соответствии со статьей Кнута "Dynamic Huffman Coding" в J. of ACM, vol.6. Сам алгоритм реализован в виде библиотеки.
Язык: C
скачать  16 кбайт
5
Vinokur A. n-ary Huffman Template Algorithm Шаблон для реализации кодирования по Хаффману. Кодовые слова могут быть n-арными. Веса могут быть, строго говоря, нечисловыми. Есть примеры использования.
Язык: C++
Сайты проекта: на SourceForge и страница с детальным описанием
версия 2.3  90 кбайт
?
Симаков А. SHCODEC и компания Реализация статического кодирования по Хаффману. Используется так называемое каноническое декодирование.
Язык: C
Страница проекта
SHCODEC, версия 1.0.1:
    ZIP  45 кбайт
    TAR.GZ  15 кбайт
Библиотека SHCLIB, производящая сжатие и распаковку данных в памяти:
    TAR.GZ без DLL  6 кбайт
    ZIP с DLL  47 кбайт
Утилита SHSFX превращает файлы, закодированные SHCODEC, в самораспаковывающиеся архивы (sfx):
    скачать  29 кбайт
?


>> Исходные тексты компрессоров >> C/C++ | Pascal/Delphi | Assembler | Прочие языки
VVS Soft Group ArcHaf "Лобовая" реализация статического метода Хаффмана без всяких затей.
1992
Язык: Pascal
версия 1.0  4 кбайт
2


>> Исходные тексты компрессоров >> C/C++ | Pascal/Delphi | Assembler | Прочие языки
Михеев А. Huffman Компрессор, использующий статический алгоритм Хаффмана.
Язык: Asm
версия 1.00  6 кбайт
4


>> Исходные тексты компрессоров >> C/C++ | Pascal/Delphi | Assembler | Прочие языки
Янковой М. DynamicHuffman Компрессор, реализующий динамический алгоритм сжатия по Хаффману. Имеется описание алгоритма.
Язык: Visual Basic, Asm
исходный код  29 кбайт
Описание:
HTML
RTF.RAR  33 кбайт
?

Смотрите также материалы:
- Методы Хаффмана и Шеннона-Фано
- Арифметическое сжатие
- Кодирование целых чисел
- Обзоры универсальных алгоритмов сжатия данных
- Книга "Методы сжатия данных". Раздел 1 "Методы сжатия без потерь"


наверх