Упаковка данных (сжатие данных)

[satnettv]

делаю для себя, контроллер atmega128, пишу на Code Vision.

Задача в следующем:

требуется простой пример упаковки (сжатия) данных (например, строку из 80 символов сжимать до 30) на каком-нибудь примере, написанном на Си. Пишу на code vision, с ассемблером не в ладах.

[Serega]

Самый распространенный алгоритм - Хаффмана
http://www.codenet.ru/progr/alg/huffcode.php

[ARV]

а с математикой в ладах? сжатие - математическая процедура...

80 символов до 30 тебе и rar не сожмет - если строка из действительно случайных символов (а не одинаковых, например).
алгоритм LZW довольно сложен, но эффективен, более простые алгоритмы дают меньшее сжатие... зачем это для МК? это не праздный вопрос, просто от ответа могут зависить советы например, для "упаковки" знакогенератора для ЖКИ алгоритм LZW вовсе необязательно применять - и без этого можно добиться уменьшения до 50%...

[satnettv]

а с математикой в ладах? сжатие - математическая процедура...

80 символов до 30 тебе и rar не сожмет - если строка из действительно случайных символов (а не одинаковых, например).
алгоритм LZW довольно сложен, но эффективен, более простые алгоритмы дают меньшее сжатие... зачем это для МК? это не праздный вопрос, просто от ответа могут зависить советы например, для "упаковки" знакогенератора для ЖКИ алгоритм LZW вовсе необязательно применять - и без этого можно добиться уменьшения до 50%...

Не обязательно сжимать с 80 до 30. требуется просто организовать определенное сжатие данных, пускай по минимому. Это делается для того, чтобы не забивать всю память, а также, чтобы передавать пакеты меньшие по объему.

[ARV]

умение задать вопрос - тоже своего рода умение, порой, очень важное...
ищи описание алгоритма LZW (Лемпеля-Зива-Велча), как уже говорили - Хаффмана, есть и другие... как правило, их легко найти в статьях по обработке изображений - GIF, TIFF, PCX, BMP - самые простые... больше ничего сказать не могу.

[Serega]

Ну уж про BMP ты загнул! Хотя некоторые действительно считают что бмп - это формат со сжатием. Потому что упрямо продолжают слать нам схемы и фотки в этом формате...

Короче, три основных типа сжатия:
- хаффмана - с бинарными деревьями
- лзв - основан на замене повторяющихся участков данных на ссылки
- не помню как называется, короче алгоритм, который юзают в ГИФах: замена строки повторяющихся символов на символ и длину строки

можно применить их все последовательно. Для обычного текста наиболее эффективны первые два

[ARV]

Serega, в тебе сразу видно программиста php (по меньшей мере не прикладника Windows) !

BMP имет предусмотренную возможность хранения сжатой информации как минимум в одном из 2-х (известных мне) форматах - так называемых 4-х и 8-и пиксельных последовательностей битов (RLE)... по-моему, число поддерживаемых форматов на сегодня больше, но ручаться не стану...

в GIF-ах юзают как раз LZW в одной из его реализаций. А тот, который неизвестен - я думаю, что это как раз RLE (см. выше про BMP), а его применение началось в стандарте PCX.

Добавим, что пока речь идет о "неразрушающем" сжатии .