Простенький архиватор.

← →
MegaVolt © (2004-04-05 12:52) [0]

Предложите простенький архиватор. Он нужен для сжатия файла и последующего его расжатия в микроконтроллере. Т.е. алгоритм по максимуму простой. Было бы хорошо если бы была реализация его на PC чтобы оценить результат :)

Заранее благодарен :)

← →
MBo © (2004-04-05 13:04) [1]

Какого характера данные?

← →
han_malign © (2004-04-05 13:13) [2]

Проще Хафмана еще ничего не придумали, если статистический характер данных известен, таблица может быть статической...
(Вроде не перепутал - Хеминг это контроль и коррекция с избыточностью, или наоборот?)
Реализация на PC - практически все архиваторы, за исключенем основанных на косинус преобразовании(mp3,jpeg)...

← →
MegaVolt © (2004-04-05 13:15) [3]

Вот кусок: стандартные архиваторы жмут файл в 30-35 раз.

0003cb10h: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FE ; 0003cb20h: 6F FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF ; 0003cb30h: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF ;
0003cb40h: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF ;
0003cb50h: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF ;
0003cb60h: F3 7F FF FF FF FF FF FF FF FF FF FF FF FF FF FF ;
0003cb70h: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF ;
0003cb80h: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF ;
0003cb90h: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF ;
0003cba0h: FF 99 FF FF FF FF FF FF FF FF FF FF FF FF FF FF ;
0003cbb0h: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF ;
0003cbc0h: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF ;
0003cbd0h: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF ;
0003cbe0h: FF F8 DF FF FF FF FF FF FF FF FF FF FF FF FF FF ;
0003cbf0h: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF ;
0003cc00h: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF ;
0003cc10h: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF ;
0003cc20h: FF FF E6 BF FA FF AF FA FF AF FA FF AF FA FF AF ;
0003cc30h: FA FF AF FE BF EB FE BF EB FE BF EB FE BF EB FE ;
0003cc40h: BF EB FF EB FE BF EB FE BF EB FE BF EB FE BF EB ;
0003cc50h: FE BF FA FF AF FA FF AF FA FF AF FA FF AF FA FF ;
0003cc60h: AF FF FD 37 FF FF FF FF FF FF FF FF FF FF FF FF ;
0003cc70h: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF ;
0003cc80h: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF ;

← →
MBo © (2004-04-05 13:20) [4]

Если весь файл будет такой, чистый хаффман раз в 5 сожмет, но с предварительным RLE или нуль-сериями(в данном случае FF-сериями) будет гораздо лучше.

← →
MegaVolt © (2004-04-05 13:24) [5]

А где почитать алгоритм? И 5 раз как то маловато :( Я думал достаточно просто было бы раз в 15 :(

В интернете есть описание.
Хаффман основан на том, что часто встречающиеся символы заменяются короткой последовательностью битов (FF будет кодироваться одним нулевым битом, скорее всего) - т.е. максимум в 8 раз.
Однако длинные серии FF можно предварительно сжать Run-Length Encoding

А в нормальных архиваторах заменяют нулём 4 байта? Т.е. FF FF FF FF заменяется но 0?

нет. LZ (ZIP)семейство вообще на других принципах основано (составление словаря повторяющихся строк разной длины), а хаффман/арифметическое кодирование работает обычно с байтами, чтобы дерево было неглубокое.

>заменяют нулём 4 байта
не нулем, а нулевым БИТОМ, который в дереве кодирования будет, скорее всего, соответствовать наиболее часто встречающемуся БАЙТУ.

Простенький архиватор. Найти похожие ветки