Просмотр полной версии : Архивирование, сжатие, упаковка.
Вот здесь вместе с витамином мы поговорили, он сказал что это будет интересно.
В общем все знают, какие типы (основные) упаковки есть: RLE, Huffman, LZW. При этом есть подозрение, что LZW является модификацией Huffman, но более знающие меня подправят.
Общая задача сжатия информации ставится следующим образом:
Имеется, информация (точнее данные), которая имеет вложенную избыточность. Упаковщик должен найти способ уменьшить эту избыточность.
Т.о. каждый из методов по сути отличается путём поиска избыточности.
RLE - самый простой и самый известный и понятный метод - заменяет повторяющиеся последовательности только последовательностью и символом количества повторения
этих последовательностей. Т.е. 01 01 01 01 01 он заменит 05 01 отсюда следует и узкое место данного метода:
множественные единичные интервалы (т.е. без повторов) такой упаковщик съест с увеличением:
01 02 03 04 05 -> 01 01 01 02 01 03 01 04 01 05
Метод Хаффмана тоже ищет избыточность но несколько иного плана: он строит дерево частот вхождения конкретных последовательностей
(т.е. это могут быть как отдельные биты, байты так и их комбинации). Самое часто встречаемое значение подменяется
симоволом 0. Следующе по частоте 10. Следующее 110 и т.д.
Т.е. символы 01 02 01 02 01 он запакует в последовательность бит: 0 10 0 10 0 - как всё просто? :)
Но этот метод имеет свои недостатки: для последовательностей, где нет ярко выраженных лидеров частот (т.е. после частотного анализа
все значения лежат более-менее в одной категории), этот метод даст увеличение конечного файла относительно
исходного.
Во избежания этого отрицательного эффекта используется модифицированный алгоритм, когда для кодировки самых быстрых (самых чатсовстречающихся)
символов используются неоднобитные последовательности, например, для первых 15 символов (по частоте отсортированных в таблице) выделяется 4 бита, тогда все остальные будут аналогично оригинальному
методу Хаффмана идти по увеличению, но особенностью будет жертвование самым быстрым символом (1 бит) в угоды менее быстрым, зато не придётся для этих менее быстрых выделять в среднем около 8 бит на символ. Т.о. то, какое количество бит выделяется на кодирование частых значений тоже является задачой и требует рассмотрения.
Но вот вопрос, каким образом описать заданный сжимаемый файл, чтобы отталкиваясь от этого описания можно было по крайней мере математически сформулировать задачу поиска решения (т.е. как надо упаковывать, чтобы упаковать наиболее оптимально)?
В поисках этого описания (видимо это должно быть какое то уравнение - целевая функция) я сделал некоторые предположения и поставил задачи:
1) Принципиально все методы сжатия более или менее могут (не)сжать любую информацию: будь это видео, текст и т.д.
2) Тогда в результате упаковки должен получится файл как минимум незначительно превышающий исходный (в худшем случае) т.е. не более нескольких байт, и имеющий значительно меньший размер (лучший случай)
Следствия: Если файл СОВСЕМ не сжимается, то он может быть представлен следующим образом:
Служебные данные - DEFW NN ;длина области, в которой сохранены несжимаемые данные
Исходные данные - DEFB A1,A2, .... ANN
без учёта индексных областей и т.д. это просто увеличение упаковываемого файла на 2 байта.
Если файл МАКСИМАЛЬНО сжимаем, то получим
Служебные данные - DEFW KK ;количество повторов сжимаемой информации
Исходные данные - DEFB A1, A2, A3, ... , AN
Если файл содержит как области максимально сжимаемые, так и области максимально не сжимаемые, то будем иметь по сути набор областей:
Служебные данные - DEFB ....
Исходные данные - DEFB ....
(Примечание: терминология относительная, рассматривается в контексте)
Т.о. при прочих равных НАИБОЛЕЕ эффективным будет именно тот упаковщик, который сможет
А) Найти представления исходных данных, при котором в конечном (упакованном файле) исходные данные занимают максимально мало места
Б) Найти представление для служебных данных, при котором служебные данные занимают максимально мало места
Надо отдавать отчёт, что вообще говоря это две задачи прямо противоположные: чем меньше занимают исходные данные, тем больше занимают служебные данные и наоборот.
Это не функциональная, а кореляционная зависимость, поэтому даже в этом случае имеются возможности лавировать: если имеется априорная информация о том, что у нас хранится в исходных данных, то к ним могут быть применены какие-либо специализированные алгоритмы, учитывающие природу этих данных.
Например, есть специализированные алгоритмы, которые могут для речи давать коэффициенты сжатия порядка 1:100, причём эти алгоритмы совершенно не способны сжимать звуковые данные другой природы (например, музыку).
Вообще этот путь развития достаточно популярен в определённых кругах, поэтому имеет право на существование.
Однако более общая задача сжатия решается путём уменьшения именно служебных данных, т.к. не имеется какой-либо информации о том, какова природы сжимаемых данных.
Например, имеется последовательность
01 02 01 02 01 02
тогда метод хаффмана заводит 1 бит для этих данных + таблица дерева данных
Служебные данные - DEFB 01, 02 ; 2 байта
Исходные данные - 0 1 0 1 0 1 ; 1 байт
однако для последовательности
01 02 01 02 01 03
такой способ представления данных просто неприменим. Поэтому суммарно упакованные данные будут выглядеть так:
Служебные данные - DEFB 01, 02, 03 ; 2 байта
Исходные данные - 0 10 0 10 0 110 ; 2 байта (10 бит)
Если же таким же способом представлять данные для первой последовательности, то аналогично будет увеличение файла до тех же 4 байт (2 + 2)
Т.о. из приведённых примеров очевидно, что представление служебных данных явно будет определять их конечный размер а значит рахмер упакованных данных.
Я использовал следующий хитрый приём: вообще то, нас мало волнует какие данные чаще всего повторяются.
Зато нас волнует то, каким образом эти повторяющиеся данные представить.
Например, по статистике, наиболее часто встречается последовательность одного повтора, например, FF FF.
Тогда очевидно, что наиболее часто встречаемый повтор надо кодировать чем-то коротким (например, битом 0 в служебных данных).
Я использовал модифицированный алгоритм Хаффмана для представления этих служебных данных (опять же подразумевается, что я ДАЖЕ НЕ ПЫТАЮСЬ каким то образом изменить представление исходных данных).
Строится дерево частот для ПОВТОРОВ и НЕПОВТОРОВ (например, встречается последовательность неповторяемых данных длиной 5 символов, она тоже отображается в таблице частот соответствующим образом).
Итого в результате работы анализатора (препроцессора) получается следующая таблица (отсортированная по частоте или количеству вхождения этих значений):
[X11,X21] == Z[1]
[X12,X22] == Z[2]
[X13,X23] == Z[3]
[X14,X24] == Z[4]
и т.д.
причём значения X1i - определяют повтор это или нет (1 бит)
X2i - определяют количество символов (для повторов это количество поторов, для неповторов - количество символов идущих из исходных данных)
Z[i] - частота.
Z[1]>=Z[2]>=Z[3]>=...>=Z[n]
Более конкретно все элементы служебных данных можно представить следующим образом:
[0,x] - количество элементов повторения
[1,y] - количество символов в безповторной последовательности
Т.е. мы предполагаем, что имеется вообще говоря всегда одинаковая таблица исходных данных, и таблица служебных данных, для которой мы меняем представление.
Однако сама по себе эта таблица частот малоинформативна и не говорит о том, какая у нас будет таблица служебных данных.
Она только даёт возможность выбрать наиболее оптимальный путь сжатия.
Результирующийц размер таблицы служебных данных определяется следующим образом:
Имеются коэффициенты C[1], C[2], ... C[N], которые определяют группы вхождения (их значения определяют количество бит на группу):
Если С[1]=1 и С[2]=8, то это будет говорить что у нас создаётся следующее дерево Хаффмана:
- 0 - самое частое вхождение
- 1XXXXXXXX (к первому биту добавляются ещё 8) - все остальные.
Итого возможно 1+256=257 элементов дерева - часть из них будет невостребованными
Если С[1]=2 С[2]=3 и С[3]=6, то
-XX - первые три самых частых значения (первая группа)
-11XXX - следующая группа из семи значений
-11111XXXXXX - последняя группа, может содержать до 64 значений
Итого возможно 3+7+64=74 элементов дерева
Сами значения даются (обязательно, т.к. здесь в дереве указывается только их номер) в отдельной таблице (в дереве).
Ясно, что "умный" упаковщик эти значения должен подбирать для организации наиболее эффективного сжатия.
Далее я попытаюсь показать, каким образом может быть получена целевая функция и укажу её особенности.
Здесь формулы будут описаны текстом, они плохо вопринимаются, лучше их переписать на бумагу в порядке их появления, тогда многое станет понятным
Каждый коэффициент C[i] осуществляет группировку нескольких Z[i]. Причём каждая C[i] осуществляет группировку
N = (-1+2^C[i]) (формула 1)
значений Z[i].
Одно значение (-1 в формуле 1) резервируется для последующих значений C[i] (групп Z[i])
Последняя группа такой резерв не имеет (он не нужен):
N = 2^C[i] (формула 2)
Тогда каждый элемент i-ой группы будет занимать следующее место в служебной таблице:
S[j] = Z[j]*(С[1]+С[2]+...+C[i]) (формула 3)
где j - абсолютный номер коэффициента, соответстущий принадлежности группе i.
Пусть внутри группы идёт нумерация (+h) (счёт от начинается с 1)
j = (-1+2^C[1]) + (-1+2^C[2]) + ... + (-1+2^C[i-1])+h (формула 4)
или
j = 2^C[1] + 2^C[2] + ... + 2^C[i-1] - i + 1 + h (формула 5).
Причём
1 <= h <= -1+2^C[i] (формула 6).
Тогда совокупное место, занимаемое i-ой группой будет
от j = 2^C[1] + 2^C[2] + ... + 2^C[i-1] - i + 1
сумма Z[j]*(С[1]+С[2]+...+C[i]) (формула 7)
до j = 2^C[1] + 2^C[2] + ... + 2^C[i-1] - i + 2^C[i]
Тогда суммарное место, занимаемое всеми группами будет идти в виде сумм мест, занимаемых каждой из групп
от i=1 ( от j = 2^C[1] + 2^C[2] + ... + 2^C[i-1] - i + 1 )
сумма ( сумма Zj*(С[1]+С[2]+...+C[i] ) (формула 8)
до i=n ( до j = 2^C[1] + 2^C[2] + ... + 2^C[i-1] - i + 2^C[i] )
В этой формуле не учитывается тот момент, что последняя группа имеет большее количество элементов (на 1)
Тогда с учётом этого нюанса формула 8 преобразится следующим образом:
от i=1 ( от j = 2^C[1] + 2^C[2] + ... + 2^C[i-1] - i + 1 )
сумма ( сумма Z[j]*(С[1]+С[2]+...+C[i] ) + Z[ 2^C[1] + 2^C[2] + ... + 2^C[i] - i + 1 ]*(С[1]+С[2]+...+C[i]) (формула 9)
до i=n ( до j = 2^C[1] + 2^C[2] + ... + 2^C[i-1] - i + 2^C[i] )
Если брать это выражение в качество целевой функции и пытаться решить её классическими методами оптимизации, то здесь вас постигнет разочарование:
дело в том, что эта функция НЕЛИНЕЙНАЯ. Коэффициенты разложения C[i] в классической задаче оптимизации являются координатами радиус-вектора, причём его плавное перемещение в классической задаче последовательно ведёт к решению.
Здесь же такой подход неприменим изза нелинейности системы (т.е. изменение одной из координат может привести от близкого к оптимуму решения к совершенно неоптимальному, это связано с перегрупировкой коэффцициентов,
именно поэтому как я уже говорил, такая задача решается численными методами, каждый из которых является Ноу-Хау авторов,
или методом последовательного перебора коэффцициентов, что, естественно, возможно когда обрабатывается не очень большой фрагмент данных, т.к. затраты на такой метод выбора коэффициентов просто колоссальны)
И ещё, в классической задаче подразумевается плавность изменения коэффцициентов C[i], здесь же осуществить плавный переход не является возможным, хотя, возможно, что если пробовать решать эту задачу в такой форме, используя, скажем, интерполяцию значений C[i] и Z[i], то может быть возможно будет получить какие-нить осмысленные значения.
Теперь от чистой теории к не совсем чистой практике :)
Я написал (интереса ради) программу, которая методом перебора будет подыскивать коэффициенты C[i] для...
...для файлов размером 6912 байт :)
Проще говоря я сделал вот такой анализатор экранных файлов.
И вот какие получились результаты:
- Для подавляющего большинства картинок имеет место следующий расклад:
C[1]=1,
C[2]=3...5
C[3]=остальное
Глядя на эти цифры и их контекст у меня возникло смутное подозрение, что эти цифры я где-то видел.
Чисто физически это обозначает вот что:
одним битом мы кодируем неповтор и следующий за ним байт длины последовательности.
Остальные C[i] характеризуют количество бит, используемых для счётчика повторов. Эти коэффициенты в принципе меняются, но C[1] очень устойчиво остаётся равным 1, причём на разных типах картинок:
от полученных с помощью Error Difusion (цвета в виде скопища точек) так и чисто рисованных на ZX.
Тогда я заглянул в ZX-Review'96 (в форуме статья про модифицированный алгоритм RLE), там как раз автор предлагал ввести (он конечно не говорил о кэффициентах, там было несколько другое описание) такой метод RLE с такими коэффициентами! Т.е. по сути я (методом сбора и анализа коэффициентов от разных картинок) и автор этого предложения (методом научного тыка по-видимому) пришли к одному результату!
Т.е. эта формула имеет серьёзную практическую подоплеку, что не может не радовать, а значит то математическое исследование, которое я провёл, помогло создать математические основы сжатия информации.
Я поспрашивал у своих коллег, которые занимаются вопросами оптимизации, каким образом можно решить эту задачу. И вот, после некоторого времени, один из них сказал мне, что видел эту формулу в одной книге. Сама эта книга
была о базисных функциях сетей и правилах передачи информации, но суть в том, что эта формула там действительно встречалась, хотя несколько в другой форме, также она давалась как формула Хаффмана для оптимального решения задачи устранения избыточности.
Т.о. я и Хаффман (хотя это его формула, я разрабатывал её независимо от него) пришли к одному результату.
Теперь такой нюанс: для картинок, на самом деле, можно изменить представление исходных данных (почти все знают как):
я сжимал картинку как простой файл, здесь же я несколько модифицировал алгоритм для того, чтобы подсчёт шёл не по линиям,
а по знакоместам. Т.о. реально при таком подходе удавалось увеличить коэффициент сжатия.
И ещё, я сравнивал как работает мой упаковщик (ещё раз напомню, что он методом перебора искал САМОЕ оптимальное решение),
и то, как работют другие упаковщики и архиваторы.
В целом, результаты оказались весьма даже похожи (т.е. мой метод, WinRAR и Laser Compact), но в некоторых случаях мой упаковщик ОТСТАВАЛ (показывал меньший коэффициент сжатия).
После анализа этих программ, я сделал следующие выводы:
- Выбранный в моей программе минимальный элемент повтора равен максимальному элементу повтора = 1 байт.
- В указанных программах длина элемента повтора может варьироваться (от 1 байта до нескольких килобайт).
- Возможно, WinRAR использует некратнобайтовые длины последовательностей (например, 17 бит).
Возможные улучшения этого метода:
- Использование некратнобайтовых последовательностей может существенно повысить коэффициент сжатия (например, последовательность бит 01 в Error Difusion картинках).
- Использование алгоритмов интерполяции для C[i] и Z[i] и простейших методов градиентного спуска позволит (возможно) упростить задачу и решать её уже не перебором
- Таблица исходных данных может подвергаться неплохому сжатию методом Huffman'а.
- Таблица значений дерева Huffman'а (таблица (не)повторов) также может хорошо сжиматься самим методом Huffman'a.
- Мой метод сжатия (поиск оптимального значения коэффцициентов C[i]) может быть применим и для таблицы (не)повторов
я не виноват, формулы съехали, так они были хотя бы чуток понятней, но если внимательно прочитать, эти формулы можно вывести и самостоятельно.
Так же я могу привести исходник для программы на паскале, которая осуществляет поиск самого оптимального решения.
я не виноват, формулы съехали, так они были хотя бы чуток понятней, но если внимательно прочитать, эти формулы можно вывести и самостоятельно.
Так же я могу привести исходник для программы на паскале, которая осуществляет поиск самого оптимального решения.
А теперь ассемблерный код релоцируемых распаковщиков и соответствующий упаковщик в студию!
GriV, оптимальнее статьи цеплять аттачем. тогда и формулы не сьедут, тема быстро загрузится, просматривать будет удобнее и сохранять быстрее и проще.
Corpsegrinder
22.02.2005, 17:27
А теперь ассемблерный код релоцируемых распаковщиков и соответствующий упаковщик в студию!
Ага, может тебе ещё и ключ от квратиры, где девки лежат?
Здесь приведены теоретические основы, есть желание пордолжить и поддержать исследование, дополняй статью и выдвигай предложения, нет - ну и зачем же лезть в эту тему?
По существу, в RAR'e там вообще могут быть многобайтовые повторы, которые копируются из уже распакованого текста, если я не ошибаюсь.
А вообще в InfernoGuide предпоследнем довольно большой обзор упаковщиков с форматами хранения данный представлен.
Здесь приведены теоретические основы, есть желание пордолжить и поддержать исследование, дополняй статью и выдвигай предложения, нет - ну и зачем же лезть в эту тему?
Ну и зачем теоретические основы в разделе про программирование на спектруме? Этой теории - тонны, и доступ к ней из интернета - тривиален. Логично предположить, что уж если автор начал заикаться на тему алгоритмов компрессии в тематическом форуме, то наверное у него есть какие-то наработки на соответствующей платформе.
Иначе какой-то сopy & paste получается...
Ну и зачем теоретические основы в разделе про программирование на спектруме? Этой теории - тонны, и доступ к ней из интернета - тривиален. Логично предположить, что уж если автор начал заикаться на тему алгоритмов компрессии в тематическом форуме, то наверное у него есть какие-то наработки на соответствующей платформе.
Иначе какой-то сopy & paste получается...
прикол в том что это и есть его наработки. в качестве практической реализации имеется прога на пасквиле для анализа исходных данных и оценки степени компрессии.
сложна, хотя я сам всё это выводил, мне пришлось довольно сильно поломать голову над тем, что бы как минимум понятно объяснить что было и что стало. Даже после этого, в тесном контакте с указанным Vitamin'ом мне пришлось ему объяснять те изюминки которые даёт этот подход, а именно: имеется голое, но чрезвычайно оптимальное RLE, которое (между прочим) оставляет возможность затем применить и huffman, LZ* и т.д. (кому что в голову придёт).
Я здесь несколько неверно указал, спасибо Vitamin'у и его статьям от A. Coder'а, в которых раскрывается суть алгоритмов LZ*. LZW по сути является командным языком, который используется для формирования рассжатия - т.е. идёт команда "возьми_байт" затем "повтори_его_20_раз" и т.д. и т.п.
RAR и подавляющее большинство других архиваторов используют именно этот подход, в то время как такой RLE не используется вообще.
Что касается конкретных программ, да, естьпрограмма на паскале (ДОСовский вариант), там она написана так, что чёрт ногу сломит, и между прочим работает она (видимо именно изза того что это не С) достаточно долго (до нескольких часов над одним Спек-экраном), причём он не создаёт ФАЙЛ, он только даёт конечный размер файла с учётом всего и вся, однако, понятно, что нужно написать (попробовать) ещё и упаковшик, распаковщик провести сравнительное исследование, право, на это надо и нервы и время.
Смысл же состоит в том, что найдётся какой нибудь программист (тот же Vitamin выразил заинтересованность), который реализует это в мягком (в виде SoftWare), благодаря чему у нас появится очередной матёрский упаковщик, глядя на который все будут облизываться :)
В данный момент я думаю над алгоритмом решения этой задачи оптимизации за счёт интерполяции - это позволит внедрить классические методы решения многомерных задач и в зависимости от результата, возможно, я предоставлю иходник для именно такого варианта.
а я их набирал ваще в FAR'e, даже после этого оны выглядят так, что от одного их вида становится не очень хорошо.
Поэтому там есть ремарка, что стоит повторять вывод формул на бумаге (если конечно это кого-то интересует), тогда всё будет более или менее понятно.
Я могу дать исходный файл как есть, однако уверяю что этого оно всё равно не красиво ;)
А никто не пробовал арифметическое сжатие построить ?
Пусть даже и получится плохо. Но интересно было бы посмотреть...
А никто не пробовал арифметическое сжатие построить ?
Пусть даже и получится плохо. Но интересно было бы посмотреть...
я пробовал. результат смотри в одном из номеров InfoGuide (6 кажется)
исходные файлы жмет хуже чем обычные паковщики (hrust, hrip) но позволяет неплохо дожимать их (за исключением раров). недостаток- очень медленная скорость упаковки/распаковки
Привет!
Сейчас посмотрел - нет в IG6 arif16m.H. Только статья. Страшный монстр на асме получился? Какой длины? Как я понял, в твоей реализации количество кодов -256. Пробовал уменьшить их до 32, например? Как это бы повлияло на твою реализацию (скорость работы, длина программы)?
Дожимать выход именно LZ не пробовал?
Пока. Дима.
которая формирует конкретные данные, релизующие указанный метод сжатия (правда на Pascal на PC), так вот первые результаты не могут не радовать: действительно, таблица исходных данных хорошо жмётся (всем кроме RLE :) ), это было видно на RAR, HA, ZIP и т.д., суммарно (т.е. исходя из размеров полученных таблиц с исходными даннымии служебными данными), получается прирост коэффициента сжатия на 10% (в среднем, сравнивается файлы от LC), однако если даже написать указанный пакер на Спектруме, то он будет слишком медленным: во-первых, задача подбора коэффициентов C[i], во-вторых, распаковка в битовом потоке, в-третьих, битовое представление дерева (не-)повторов. И наконец, распаковка исходных данных, что подразумевает либо метод Huffmana (изначально медленный, так как тоже битовый) либо LZ* (частично в битовом представлении).
во-вторых, распаковка в битовом потоке, в-третьих, битовое представление дерева (не-)повторов. И наконец, распаковка исходных данных, что подразумевает либо метод Huffmana (изначально медленный, так как тоже битовый) либо LZ* (частично в битовом представлении).
если не ошибаюсь все это есть в Rip, тормозит конечно, но вполне терпимо
во всяком случае из описания я так понял, RLE там не пахнет
Привет!
Сейчас посмотрел - нет в IG6 arif16m.H. Только статья. Страшный монстр на асме получился? Какой длины? Как я понял, в твоей реализации количество кодов -256. Пробовал уменьшить их до 32, например? Как это бы повлияло на твою реализацию (скорость работы, длина программы)?
Дожимать выход именно LZ не пробовал?
Пока. Дима.
там архив есть sources.rar ищи там.
монстр не сильно страшный- я его сначала писал внаглую с сишного исходника (который в свою очередь выдрал из связки LZSS+Arifm) а потом проводил жестокую оптимизацию, успешно продолженую алко.
число кодов уменьшить можно. надо уменьшить размер таблицы частот и изменить счетчик битов чтобы он пустые нули не учитывал при сжатии
пробовал дожимать файлы после хрипа. выигрыш- от 5 до 20% получался.
Но этот метод имеет свои недостатки: для последовательностей, где нет ярко выраженных лидеров частот (т.е. после частотного анализа
все значения лежат более-менее в одной категории), этот метод даст увеличение конечного файла относительно исходного.
Сорри что я тут встреваю. Но вообще-то Хафманское и арифметическое сжатие, это методы которые не дают потерь. И в худшем случае размер данных никогда не увеличивают. Если не считать того что приходится хранить таблицу (на практике я в этом сам убеждался, немного сжимаются даже случайные данные).
В Хафмане дерево строится так. Берутся символы считается число их вхождений в файл. Допустим если у нас есть 4 символа A,b,c,d которые появляются в файле 10 33 45 99 раз. Мы составляем таблицу в которой находим два самых редких символа и суммируем их числа. В итоге получается как бы их общее число вхождений которые мы вставляем в таблицу вместо этих двух(в соотвествующее место). Затем делаем тоже самое, в двумя самыми редкими элементами и так пока не останется два элемента....
В итоге (см. картинку символы будут кодироваться так) -
A - 0, B - 11, C - 100, D - 101
В итоге весь файл длиной 191 байт у нас умещается в 64 байта...
Саму систему составления кодов можно сделать ввиде односвязного списка в котором нужно выделить максимум 512 элементов. На спектруме особых проблем с памятью и скоростью упаковки не возникает....
Надеюсь что я изложил достаточно понятно. (не могу сейчас как следует свои слова обдумать, потому что из дома надо уходить, т.к. опаздываю)
как я описал скрещённый метод Хаффмана и RLE и к тому же привёл полное доказательство теоремы Хаффмана, если получается что я метод Хаффмана не знаю? :D
Каждый из методов имеет ДОСТОИНСТВА и НЕДОСТАТКИ.
т.о. суммарно (полностью итоговые данные) каждый из методов может как давать компрессию (сжатие), так и увеличение в конечном файле.
Чем сложней метод сжатия, тем меньше вероятность возникновения такого случая, но он всегда есть:
- Для самого простого RLE это просто очевидно
- Для Хаффмана это не так видно, но оно обязательно есть
- Для других методов на простейших примерах можно показать что так оно и будет, потому что ВСЕГДА можно найти последовательность, когда упаковищку придётся сохранить всю эту последовательность плюс ещё служебные данные.
В спектруме одна тока неприятность. Данные по размеру слишком малы чтобы давать эеффект. А так у хафмана сжатие есть почти всегда и таблица картины не портит. Можно ещё динамическую таблицу применять, тогда её хранить не придётся, но там уже теория от потерь не защищает и они иногда появляются.
Ещё хафмана хорошо вместе с LZ методом применять. LZ это же по сути повторения областей, т.е. смещения и размеры памяти вот их хорошо кодировать по хафману... Работает эффектно и не нужно ломать голову над сложными методами.......
данных достаточно, чтобы сжимать.
К тому же все существующие методы сжатия (на всех машинах) рассчитаны на обработку кратнобайтовых последовательностей, а как показал Иван Рощин, зачастую просто преобразовав бит в байт можно сжатие значительно улучшить.
Стоит отметить, что ни один из существующих методов не постулирует размер последовательностей и их кратность (все методы можно применять как для байтового сжатия, так и для битового)
Всерьёз этим вопросом никто не занимался, так как получается значительное замедление процесса сжатия.
Интереса ради можно попробовать написать (де-)скрамблер, которые будет указанное бит->байт преобразование делать, тогда и увидеть можно будет насколько вырастает эффективность сжатия.
Сжимать последовательность битов. Модет быть такие наивные методы как RLE дадут какой-то результат. Сомневаюсь что ARI даст какой-нибудь положительный результат, и Хафман не даст тем более. На 2-символьный алфавит они никак не расчитаны. (это можно на бумаге проверить). Да упаковке программ тоже никого толка не выдет никаким способом. Можно только на картинках через LZ методы какой-то толк извлечь (и то если с умом применять).
недавно, перечитавшись статей alco и ковыряясь с переводом спековского депакера LC на пц, проникся духом сжимательства %) и написал упаковщик (пока картинок). упрощенное дерево, окно поиска в 256 байт. и тем не менее, на некоторых картинках (с большими повторяющимися площадями) настолько рвал LC, что я по три раза перепроверял результаты. что бы это могло быть? :?
недавно, перечитавшись статей alco и ковыряясь с переводом спековского депакера LC на пц, проникся духом сжимательства %) и написал упаковщик (пока картинок). упрощенное дерево, окно поиска в 256 байт. и тем не менее, на некоторых картинках (с большими повторяющимися площадями) настолько рвал LC, что я по три раза перепроверял результаты. что бы это могло быть? :?
А если картинку в памяти вертикально разместить - улучшается ещё?
Сжимать последовательность битов. Модет быть такие наивные методы как RLE дадут какой-то результат. Сомневаюсь что ARI даст какой-нибудь положительный результат, и Хафман не даст тем более. На 2-символьный алфавит они никак не расчитаны. (это можно на бумаге проверить). Да упаковке программ тоже никого толка не выдет никаким способом. Можно только на картинках через LZ методы какой-то толк извлечь (и то если с умом применять).
как раз RLE здесь мало чего решит. Имеется в виду не однобитные последовательности, а длинные последовательности из нескольких бит.
Специально в целях исследования этой темы написал скрамблер и дескрамблер, который делает конверт бит->байт и наоборот. Так вот для разных файлов наблюдалась разная картина - был как прирост (на одних файлах) так и наоборот ухудшение результата (относительно конечно же того, что получалось без скремблирования) в других случаях.
Так что получается, что говорить о том, что такой подход даёт вообще говоря значительный прирост нельзя.
2Vitamin> чтото тебя не видно, я тебе могу исходник своего паковщика дать (на паскале только), посмотри как твой пакер работать будет на том, что остаётся несжатым.
2lvd> сжатие картинок невертикальным линейным методом не осуществляется
недавно, перечитавшись статей alco и ковыряясь с переводом спековского депакера LC на пц, проникся духом сжимательства %) и написал упаковщик (пока картинок). упрощенное дерево, окно поиска в 256 байт. и тем не менее, на некоторых картинках (с большими повторяющимися площадями) настолько рвал LC, что я по три раза перепроверял результаты. что бы это могло быть? :?
в LC алгоритм тривиальный как оказалось, delc5.2 переписанный на си должен появиться в одной из следующих публикаций AlCo. если кому интересно увидеть его раньше - напишите хрумер'у, у него есть :)
алгоритм может быть и тривиальный. да вот реализация неплохо сделана. сам видел депакер %)
Cheburashka
22.07.2019, 12:16
Доброго здоровья всем! Решился наконец протестировать, прокомментировать и выложить здесь доработанный мной распаковщик знаменитого формата apack (или aplib) Йоргена Ибсена. (текст, импортирован из ALASM).
69635
По моим замерам, скорость распаковки превосходит скорость распаковщика Hrust1 (209 байт) на 8-11 процентов.
Теперь насчет степени сжатия: недавно появился на свет оптимизированный упаковщик по методу apack, который близко подобрался по степени сжатия к оптимизированному упаковщику oh1c (hrust1).
Вот ссылка: http://www.amstrad.es/forum/download/file.php?id=4907&sid=ee546a899a44e6fa3273bc4fdc8ca836
Думаю, в некоторых случаях, применение этой "пары" может иметь смысел.
На форум захожу редко, так что извиняйте за молчание!
перемудрили с 32б и 64б. - файлы одинаковые
Powered by vBulletin® Version 4.2.5 Copyright © 2024 vBulletin Solutions, Inc. All rights reserved. Перевод: zCarot