Реализация: shcodec

Большинство идей, изложенных в этой статье, легли в основу программы SHCODEC (Static Huffman COder / DECoder). SHCODEC - является свободно-распространяемой программой (freeware). Программу, исходный код, документацию, а так же результаты испытаний можно найти тут: http://www.webcenter.ru/~xander

Приложение: биография д. Хаффмана

Дэвид Хаффман родился в 1925 году в штате Огайо (Ohio), США. Хаффман получил степень бакалавра электротехники в государственном университете Огайо (Ohio State University) в возрасте 18 лет. Затем он служил в армии офицером поддержки радара на эсминце, который помогал обезвреживать мины в японских и китайских водах после Второй Мировой Войны. В последствии он получил степень магистра в университете Огайо и степень доктора в Массачусетском Институте Технологий (Massachusetts Institute of Technology - MIT). Хотя Хаффман больше известен за разработку метода построения минимально-избыточных кодов, он так же сделал важный вклад во множество других областей (по большей части в электронике). Он долгое время возглавлял кафедру Компьютерных Наук в MIT. В 1974, будучи уже заслуженным профессором, он подал в отставку. Хаффман получил ряд ценных наград. В 1999 - Медаль Ричарда Хамминга (Richard W. Hamming Medal) от Института Инженеров Электричества и Электроники (Institute of Electrical and Electronics Engineers - IEEE) за исключительный вклад в Теорию Информации, Медаль Louis E. Levy от Франклинского Института (Franklin Institute) за его докторскую диссертацию о последовательно переключающихся схемах, Награду W. Wallace McDowell, Награду от Компьютерного Сообщества IEEE, Золотую юбилейную награду за технологические новшества от IEEE в 1998. В октябре 1999 года, в возрасте 74 лет Дэвид Хаффман скончался от рака.

Список литературы

[1]  D.A. Huffman, "A method for the construction of minimum-redundancy codes", Proc. Inst. Radio Engineers, vol. 40, no. 9, pp. 1098-1101, Sep. 1952. [Скачать]

[2]  E.S. Schwartz, B. Kallick, "Generating a canonical prefix encoding", Communications of the ACM, vol. 7, no. 3, pp. 166-169, Mar. 1964.

[3]  J.V. Leeuwen, "On the construction of Huffman trees", Proc. 3rd International Colloquium on Automata, Languages, and Programming, Edinburgh University, pp. 382-410 July 1976.

[4]  J. Katajainen, A. Moffat, "In-place calculation of minimum-redundancy codes", Proc. Workshop on Algorithms and Data Structures, pp. 393-402, Aug. 1995. [Скачать]

[5]  A. Moffat, A. Turpin, "On the implementation of minimum-redundancy prefix codes", IEEE Transactions on Communications, vol. 45, no. 10, pp. 1200-1207, June 1997. [Скачать]

[6]  R.L. Milidiu, E.S. Laber,"The warm-up algorithm: A Lagrangean construction of length restricted Huffman codes", TR-15, Departmento de Informatica, PUC-RJ, 1997. [Скачать]

[7]  R.L. Milidiu, A.A. Pessoa, E.S. Laber, "Efficient implementation of the warm-up algorithm for the construction of length-restricted prefix codes", Proc. of ALENEX (International Workshop on Algorithm Engineering and Experimentation), pp. 1-17, Springer, Jan. 1999. [Скачать]

[8]  R.L. Milidiu, A.A. Pessoa, E.S. Laber, "In-place length-restricted prefix coding", Proc. of SPIRE (String Processing and Information Retrieval), pp. 50-59, IEEE Computer Society, Jan. 1998. [Скачать]

[9]  D.S. Hirschberg, D.A. Lelewer, "Efficient decoding of prefix codes", Communications of the ACM, vol. 33, no. 4, pp. 449-459, Apr. 1990. [Скачать]

[10]  D.A. Lelewer, D.S. Hirschberg, "Data compression", Computing Surveys, vol. 19, no. 3, pp. 261-296, Sep. 1987. [Скачать]