Войти
ПрограммированиеФорумОбщее

Архиватор текста с минимум кода

Страницы: 1 2 Следующая »
#0
16:15, 30 сен. 2017

Когда-то давно встречал "поделку" в виде минимального кода для архивации текста, написаную на C.
Может кто-то подскажет, или у кого есть?
Важно что бы это было очень мало кода.

Спасибо


#1
20:24, 30 сен. 2017

IROV..
попробуй паковщики для демок в духе 4K посмотреть

#2
4:27, 1 окт. 2017

Что подразумевается под минимумом кода? Бинарного или исходного?
https://github.com/nothings/single_file_libs#compression
http://blog.gamedeff.com/?p=371 -> https://web.archive.org/web/20110817175714/http://www.everfall.co… ?o3ug124i2l7p

#3
4:57, 1 окт. 2017

Если просто "мало кода", без требований к качеству архивации, можно вообще ничего не делать. Совсем нет кода - идеальный вариант - задача решена.

#4
7:51, 1 окт. 2017

Zab
Кода то на сжатие или расжатие? Я просто где-то видел статический Huffman на асме с кодом разжатия в 42 байта, например.

#5
12:38, 1 окт. 2017

IROV..
Любая реализация базового алгоритма сжатия достаточно мала, будь то Хаффман или LZW. Уже по описанию мне хватало той реализации которая у меня получалась в результате.
Кроме того статический код Хаффмана не предполагает алгоритма сборки статистики частот, что очень упрощает алгоритм.

#6
13:01, 1 окт. 2017

foxes
Вот примерно то что нужно и да это или хофман или лыза.
https://github.com/NordicSemiconductor/puck-central-ios/blob/mast… kCentral/lz.c
https://github.com/andyherbert/lz1/blob/master/lz.c

#7
14:04, 1 окт. 2017

foxes
> статический код Хаффмана не предполагает алгоритма сборки статистики частот, что очень упрощает алгоритм
Алгоритм как раз не упрощает. Вместо того, чтобы собрать таблицу, приходится ее статически забивать. Объем кода больше становится.
Зато итоговый файл меньше, если исходник нужной тематики, если попали в статистику. Если не попали - лучше бы и не пытались сжимать таким способом, скорее всего объем "сжатого" файла будет больше, чем не сжатого.

#8
14:25, 1 окт. 2017

Zab
> Вместо того, чтобы собрать таблицу, приходится ее статически забивать. Объем
> кода больше становится.
То есть, если я сделаю статическую таблицу весов, а точнее даже не таблицу, а логику формирования бит то кода будет больше? Есть алгоритм который используется в jpg кодировании, Хаффман там очень простой и короткий, все что требуется это прераспределить последовательность кодируемых значений от 0..255 в "#32,A,O,И,Е..." - это таблица даже меньше 256 байт вместо алгоритма. Последовательность из мягких знаков конечно же сожмется хуже.

#9
14:46, 1 окт. 2017

Формирование таблицы - несколько строчек дополнительного кода. Еще по несколько строчек - сохранение и загрузка таблицы.
По объему бинарника может быть и так, и эдак, по усилиям программиста - точно дешевле будет динамическую таблицу сделать. Эффективность сжатия зависит от тематики текстов. Если мы заранее не знаем точно тематику, статическая таблица будет давать худший эффект.

Использование только хафмана - плохой выбор. Даже в лучшем случае получишь сжатие на проценты, а не в разы. Этот алгоритм комбинируют с другими обычно.

#10
15:23, 1 окт. 2017

Zab
Я думаю на опробовать это уже будет маньше SDK стандартного архиватора. К тому же сжимает в 2 раза в среднем. Тематика текста тут вообще не причем, так как сжимаются символы, тем более если ты хочешь динамически формировать таблицу весов. Даже банальное урезание бит за не надобностью уже дает процент сжатия.
А как развитие логики сжатия Хаффмана можно взять арифметическое кодирование, тут вообще всем потребностям удовлетворяет. Хранение таблицы частот после сжатия отпадает, как для динамического хаффмана. А код уже меньше некуда.

#11
16:36, 1 окт. 2017

foxes
Сравнимо со старым zip будет если использовать lzw + хафмана. Не дотянешь по zip, но приблизишься. В zip еще три алгоритма используются, помимо этих двух.
Тематика текста очень даже при чем, важна частота встречаемости тех или иных букв. Часть символов меньше 8 бит занимать начинает, а часть больше, проиграть очень даже легко.
С динамической таблицей проиграть сложнее, но тоже можно. Представь полностью рандомный файл, таблица для него даст все символы восьмибитные, как в несжатом, но надо хранить еще и заголовок, включающий в себя таблицу.

#12
17:34, 1 окт. 2017

Zab
> Представь полностью рандомный файл
За чем мне рандомный файл представлять, если я уже хаффманом обычный текст сжимал вполне успешно. Если это только английский текст то даже рандомные символы дают усечение каждого до 7 бит на символ, благодоря равномерному распределению среди a-z A-Z. Это 64 символа, кодируются 0XXXXXX, остальное отсутствующее это 10XXXXXX и 11XXXXXXX. При том что это уже используется без таблиц и лишних алгоритмов. То есть при самом худшем варианте текста сжатие все равно будет.
А уж арифметическое кодирование это алгоритм используемый в UPX единственное добавление это алгоритм предсказания символов, уже себя показал. Также как и LZW без каких либо приблуд.

Zab
> В zip еще три алгоритма используются, помимо этих двух.
и еще тонны кода.

#13
19:13, 1 окт. 2017

foxes
> А как развитие логики сжатия Хаффмана можно взять арифметическое кодирование, тут вообще всем потребностям удовлетворяет.
Арифметическое кодирование, к слову, уже устарело. Вместо него стоит использовать ANS.

#14
19:21, 1 окт. 2017

}:+()___ [Smile]
И насколько это будет проще для реализации? по сути то, те же грабли.

Страницы: 1 2 Следующая »
ПрограммированиеФорумОбщее

Тема в архиве.