Mar 05

Семестр начался просто офигенно. Целая куча предметов по программированию и целая куча лабораторных, причем некоторые из них довольно сложные. Вчера вот (точнее уже сегодня) всю ночь делал одну из них, а именно архиватор. Задали вот нам написать, предложили ~10-15 вариантов кодирования. Мне пришлось взять один из 3-го (и последнего) уровня сложности (т. к. экзамен писать не охота, а для тех, кто делает не 1-й уровень имеются “поблажки” :) ).

Собственно - адаптивный (или динамический) алгоритм кодирования хаффмана или алгоритм FGK (Faller, Gallager, Knuth). О самом алгоритме можно почитать здесь.

Я же скажу несколько слов об организации всего этого хозяйства:

  1. По-моему использовать нормальный класс дерева в данном случае - бред. Хотя если дерево построено на массиве и у k-го элемента сыновья 2k и 2k+1 - тогда что-то попробовать можно.
  2. От дерева требуется быстрый обход в ширину.
  3. Дереву не обязателен быстрый поиск.Хотя и желателен.

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

PS. Побольше бы таких лаб. Если бы еще не было других - неинтересных, но тоже забирающих на себя кучу времени…

written by fxposter \\ tags: ,


2 Responses to “Adaptive Huffman Coding”

  1. 1. Андрей Says:

    Такая же лаба по ТКИ (теория кодирования информации) – за образец взял код отсюда: http://www.gotdotnet.com/Community/UserSamples/Details.aspx?SampleGuid=c8bc181b-5ddf-4969-aeca-a508374f1282 оч грамотно написан – мелкософт как никак :-)

  2. 2. FX Poster Says:

    Я свой наваял и уже забыл о нем. :)

Leave a Reply