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

[satnettv]

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

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

[bzx]

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

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

1. Хотьи старо, но рекомендую потратить время и почитать что-нибудь о “сжатии без потерь”, либо погуглить.
2. Алгоритмы сжатия зависят от типа информации. Я так понимаю, что у тебя в качестве данных текстовая информация. Это намного упрощает. Самый простой и тупой способ - замена одинаковых подряд идущих символов на количество повторов. Например, имеется строка
7892222222222368
после сжатия
789[at][10]268
[at] – управляющий символ
[10] – число в двоичном виде, количество символов повтора, для данного примера это десять двоек.

[Guest_=AVR=_*]

Примитивное сжатие типа посоветованного выше обычно называется RLE - Run-Length Encoding. Алгоритм хорошо ложится на АВР, но результат будет очень сильно зависеть от типа входных данных - иногда экономия может оказаться нулевой

[zltigo]

требуется простой пример

"Простые" не жмут абстрактые текстовые строки почти в три раза.
Да и сложные тоже без всяких гарантий. Попробуйите кучку Ваших реальных строк пожать, например, RAR-ом который совсем не прост и даже словарь которого ни в какую AVR не влезет.
Где-то шансы есть при явном ограничении набора символов, их перекодировке в соответствии с вероятностью использования с последующим сжатием чем-то простым классическим зипообразным.

[mse]

есть такой алгоритм - RADIX-50, по-мойму. Упаковывает 3 ASCII символа басурманских, в 2. На заре юности реализовывал. На СМ-ках использовался. BRU, была такая ленточная сисьтемка. Щас, ессно, реализаццыю не вспомню. Гуголь рулит...

[zltigo]

Упаковывает 3 ASCII символа басурманских, в 2

Ну это очевидно. Вопрошающий хотел 3 в ОДИН и "басурманскими" ограничиваться не обещал...

[mse]

Ну это очевидно. Вопрошающий хотел 3 в ОДИН и "басурманскими" ограничиваться не обещал...

А это, в общем случае, фигня. На 80-символьной строке даже нормальный алгоритм сжатия больше 30-40% не даст, для случайной последовательности.

[SpyBot]

Да, и кстати есть небольшая но очень интересная книга
http://www.compression.ru/book/

[SasaVitebsk]

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

Выводы следующие:
1) Если использовать метод заполнения словаря, то вам потребуется не менее 2К озу под словарь.
Если использовать предустановленный словарь, то вам придётся выполнить серьёзный предварительный анализ ваших данных для формирования словаря.
2) Декомпрессия выполняется достаточно просто и CPU загружает не очень сильно. Компрессия значительно загружает проц. И в том и в другом случае применение AVR всётаки не оправдано. Если только очень медленные процессы.

Здесь, наверное уместен какой-нибудь ARM.

[scifi]

А это, в общем случае, фигня. На 80-символьной строке даже нормальный алгоритм сжатия больше 30-40% не даст, для случайной последовательности.

Случайная последовательность байтов (независимых и с равномерным распределением) не может быть сжата никаким алгоритмом. Ни на 30%, ни на 1%, нисколько.

[ReAl]

есть такой алгоритм - RADIX-50, по-мойму. Упаковывает 3 ASCII символа басурманских, в 2.
...
Гуголь рулит...

Может, я на что сгожусь? (заместо гуглы )
Он же не "сжимал", а "упаковывал". Три символа из очень ограниченного набора - большие латинские буквы, цифры и ещё несколько знаков (вот тут уже гуглу спрашивайте) - всего вместе 40 символов - упаковывались в 16-битное слово.
40*40*40 = 64000 возможных комбинации, в аккурат в 65536 влазит.

p.s. RADIX-50.... 50oct = 40dec, в 16 бит записывалось 3-значное число "по основанию 40"

[SasaVitebsk]

Случайная последовательность байтов (независимых и с равномерным распределением) не может быть сжата никаким алгоритмом. Ни на 30%, ни на 1%, нисколько.

Должна сжаться примерно в два раза. Это и подтверждается на упаковщиках.

Всё сжимается до каких то пределов. Критерии несжимаемости файлов не байтовые, а битовые. Вводится понятие энтропии и т.д. Понятие "равномерное распределение байтов" не совсем корректно, что значит "независимый байт" - убей не знаю. Я думаю на любом двоичном файле вы получите распределение близкое к равномерному. Имеет значение не само распределение, а последовательность следования. Также вы не учитываете "предустановленный словарь". Иными словами если словарь будет передаваться в самих данных, то это одно, а если он не будет передаваться, то совсем другое.

[aaarrr]

Да??? Сожмите-ка эту случайную последовательность:  512k.txt ( 64 килобайт ) Кол-во скачиваний: 210


UPD: Это был ответ на пост выше, но его уже исправили. Мне вот что интересно: кто успел скачать эту бредятину 4 раза за 10 минут?

Я думаю на любом двоичном файле вы получите распределение близкое к равномерному.

Отнюдь нет.
Большинство современных упаковщиков работают в два этапа: на первом данные упаковываются каким-нибудь LZ-подобным алгоритмом, затем Хаффманом.

[SasaVitebsk]

Да??? Сожмите-ка эту случайную последовательность:  512k.txt ( 64 килобайт ) Кол-во скачиваний: 210


UPD: Это был ответ на пост выше, но его уже исправили. Мне вот что интересно: кто успел скачать эту бредятину 4 раза за 10 минут?
Отнюдь нет.
Большинство современных упаковщиков работают в два этапа: на первом данные упаковываются каким-нибудь LZ-подобным алгоритмом, затем Хаффманом.

1. Эту бредятину продолжают качать и качать. Насколько я понимаю аналогичную легко получить любым упаковщиком.
2. Не буду с вами спорить потому, что нет времени аргументировать. По моему файл заполненный примерно так 0,1,2,3....ff,0,1,2.. и так раз 10 даст равномерное распределение. При этом сожмётся как положено.
3. Ваш файл можно сжать и соответственно разжать без потери информации. Правда, естественно, если вы сгенерируете другой с помощью того же упаковщика возможно он разбухнет. Я просто уточнял, что всё не так просто. И для однозначного ответа не достаточно информации.

[aaarrr]

1. Эту бредятину продолжают качать и качать. Насколько я понимаю аналогичную легко получить любым упаковщиком.

Можно упаковщиком. Бредятина создана генератором случайных чисел.

2. Не буду с вами спорить потому, что нет времени аргументировать. По моему файл заполненный примерно так 0,1,2,3....ff,0,1,2.. и так раз 10 даст равномерное распределение. При этом сожмётся как положено.

Ага, LZ отработает со свистом. Вот только у "любого" файла распределение бывает, как правило, неравномерным.

3. Ваш файл можно сжать и соответственно разжать без потери информации.

Сжать? У меня вот не получается, не знаю, как у других

[SasaVitebsk]

Сжать? У меня вот не получается, не знаю, как у других

Если использовать свой упаковщик, с предустановленной таблицей ориентированной на ваш файл. Так чтобы таблица не передавалась.

Хотя понятно что это не нужно. Но я говорю о принципе. Если данные идут несжимаемые, но предсказуемые (например известен механизм их формирования), то формируется таблица исходя из этих данных.

[proba]

использую LZW для передачи текстовои информации с логгера в PC. данные накопляются в датафлеш и передаются одним сеансом связи. сотнощение 3 : 1 . пример, данных 10120 б, в сжатом виде 3231 б.
алгоритм несложныи но требуется порядка 32K RAM.
при коротком строке вряд ли зaметного сжатия будет.

[SasaVitebsk]

использую LZW для передачи текстовои информации с логгера в PC. данные накопляются в датафлеш и передаются одним сеансом связи. сотнощение 3 : 1 . пример, данных 10120 б, в сжатом виде 3231 б.
алгоритм несложныи но требуется порядка 32K RAM.
при коротком строке вряд ли зaметного сжатия будет.

А словарь по ходу формируешь?
В смысле каждый сеанс с пустого словаря начинаешь?
Или взял предустановленный?

И что-то 32к многовато получилось. У меня что-то около 10 выходило.

Алгоритм несложный, но самое главное - поиск.

[proba]

посмотрел код, деиствительно RAM нужен 20k а не 32к.
каждыи раз начинаю с пустого словаря.
обьем его 4099 слов - почему то с 2048 были проблемы ( может даже в приемнои стороне в PC ).
алгоритм требует 5x (обьем словаря) баит RAM. т.е. в моем случае 20KB.
исползовал исходники от Mark Nelson.