Универсальные алгоритмы сжатия данных:
Методы Хаффмана и Шеннона-Фано
>> Русские материалы | Английские материалы | Исходные тексты компрессоровСмотрите также материалы:
- Методы Хаффмана и Шеннона-Фано
- Арифметическое сжатие
- Кодирование целых чисел
- Обзоры универсальных алгоритмов сжатия данных
- Книга "Методы сжатия данных". Раздел 1 "Методы сжатия без потерь"
|
>> Русские материалы | Английские материалы | Исходные тексты компрессоров |
|||
| Авторы | Название | Описание | Рейтинг |
| Jones G. | Кодирование с минимальной избыточностью по методу Хаффмэна. | Описание и реализация статического и адаптивного алгоритмов кодирования по Хаффману.
Из книги: Г. Джоунз. Программирование на языке оккам. - М.: Мир,1989. TXT.RAR 15 кбайт |
|
| Александров О.Е., Попков В.И. | Компрессия данных или измерение и избыточность информации. Метод Хаффмана | Методичка к лабораторной работе. Краткий обзор способов сжатия, изучение метода Хаффмана. Вроде как статический алгоритм рассмотрен хорошо.
Авторская страница Методические указания к лабораторной работе /О. Е. Александров. Екатеринбург: УГТУ, 2000. 52с. PDF.RAR 458 кбайт Исходники на Pascal, прилагаемые к методичке: скачать 54 кбайт |
|
| Симаков А. | Код Хаффмана | Хорошее описание идеи метода Хаффмана и алгоритма кодирования-декодирования статических кодов. См. также реализацию SHCODEC ниже. Сыктывкарский Государственный Университет, Кафедра Прикладной Математики, октябрь 2002. HTML 60 кбайт HTML.RAR 28 кбайт |
|
| 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 кбайт |
|
| Невесенко Н.В. | Хаффман в плане минимизации программы | Дается практическое описание кодирования по Хаффману.
Описываются алгоритмы сжатия и распаковки, позволяющие минимизировать размер
кодера и декодера. Приводятся иллюстрации реализации на Ассемблере.
22.10.2002 Авторская страница Текст в HTML |
|
| Янковой М. | Динамическое сжатие методом Хаффмана | Неформальное описание динамического (адаптивного) алгоритма.
К тексту прилагаются исходники на Visual Basic + Asm.
HTML RTF.RAR 33 кбайт исходный код реализации 29 кбайт |
|
| Кошкин Г.М. | Энтропия и информация | Содержит краткое неформальное описание кодирования
Шеннона-Фано на конкретном примере. Также рассмотрены основные свойства энтропии и
информации для дискретных случайных объектов.
Соросовский образовательный журнал, 2001, N 11, с. 122–127. PDF.RAR 90 кбайт |
|
|
>> Русские материалы | Английские материалы | Исходные тексты компрессоров |
|||
| Huffman D. | A Method for the Construction of Minimum-Redundancy Codes | Proceedings of IRE, vol.40, N9, pp.1098-1101, September 1952. PDF 332 кбайт |
|
| 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 кбайт |
|
| 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 кбайт |
|
| Abrahams J. | Huffman Code Trees and Variants | Краткий обзор литературы, посвященной кодам Хаффмана.
DIMACS, Rutgers University. PDF.RAR 44 кбайт |
|
| 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 кбайт |
|
| Schindler M. | Practical Huffman coding | Описание основных приемов для эффективной реализации кодирования по Хаффману.
Сайт "Data Compression Consulting", Aug., Oct. 1998. HTML.RAR 11 кбайт |
|
| 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 кбайт |
|
| 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 кбайт |
|
| MacDonald J. | Dynamic Huffman Coding | Реализация адаптивного алгоритма Хаффмана в соответствии со статьей Кнута "Dynamic Huffman Coding" в J. of ACM, vol.6. Сам алгоритм реализован в виде библиотеки.
Язык: C скачать 16 кбайт |
|
| 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 кбайт |
|
|
>> Исходные тексты компрессоров >> C/C++ | Pascal/Delphi | Assembler | Прочие языки | |||
| Михеев А. | Huffman | Компрессор, использующий статический алгоритм Хаффмана.
Язык: Asm версия 1.00 6 кбайт |
|
|
>> Исходные тексты компрессоров >> C/C++ | Pascal/Delphi | Assembler | Прочие языки | |||
| Янковой М. | DynamicHuffman | Компрессор, реализующий динамический алгоритм сжатия по Хаффману. Имеется
описание алгоритма.
Язык: Visual Basic, Asm исходный код 29 кбайт Описание: HTML RTF.RAR 33 кбайт |
|
Смотрите также материалы:
- Методы Хаффмана и Шеннона-Фано
- Арифметическое сжатие
- Кодирование целых чисел
- Обзоры универсальных алгоритмов сжатия данных
- Книга "Методы сжатия данных". Раздел 1 "Методы сжатия без потерь"
наверх