Важная информация

User Tag List

Страница 1 из 3 123 ПоследняяПоследняя
Показано с 1 по 10 из 29

Тема: Архивирование, сжатие, упаковка.

  1. #1
    Veteran Аватар для GriV
    Регистрация
    18.02.2005
    Адрес
    Набережные Челны
    Сообщений
    1,574
    Благодарностей: 104
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Question Архивирование, сжатие, упаковка.

    Вот здесь вместе с витамином мы поговорили, он сказал что это будет интересно.

    В общем все знают, какие типы (основные) упаковки есть: 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 ....

    (Примечание: терминология относительная, рассматривается в контексте)

  2. #1
    С любовью к вам, Yandex.Direct
    Размещение рекламы на форуме способствует его дальнейшему развитию

  3. #2
    Veteran Аватар для GriV
    Регистрация
    18.02.2005
    Адрес
    Набережные Челны
    Сообщений
    1,574
    Благодарностей: 104
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию продолжение (1)...

    Т.о. при прочих равных НАИБОЛЕЕ эффективным будет именно тот упаковщик, который сможет
    А) Найти представления исходных данных, при котором в конечном (упакованном файле) исходные данные занимают максимально мало места
    Б) Найти представление для служебных данных, при котором служебные данные занимают максимально мало места

    Надо отдавать отчёт, что вообще говоря это две задачи прямо противоположные: чем меньше занимают исходные данные, тем больше занимают служебные данные и наоборот.
    Это не функциональная, а кореляционная зависимость, поэтому даже в этом случае имеются возможности лавировать: если имеется априорная информация о том, что у нас хранится в исходных данных, то к ним могут быть применены какие-либо специализированные алгоритмы, учитывающие природу этих данных.
    Например, есть специализированные алгоритмы, которые могут для речи давать коэффициенты сжатия порядка 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] )

  4. #3
    Veteran Аватар для GriV
    Регистрация
    18.02.2005
    Адрес
    Набережные Челны
    Сообщений
    1,574
    Благодарностей: 104
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию Окончание....

    Если брать это выражение в качество целевой функции и пытаться решить её классическими методами оптимизации, то здесь вас постигнет разочарование:
    дело в том, что эта функция НЕЛИНЕЙНАЯ. Коэффициенты разложения 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]) может быть применим и для таблицы (не)повторов

  5. #4
    Veteran Аватар для GriV
    Регистрация
    18.02.2005
    Адрес
    Набережные Челны
    Сообщений
    1,574
    Благодарностей: 104
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Unhappy P.S.

    я не виноват, формулы съехали, так они были хотя бы чуток понятней, но если внимательно прочитать, эти формулы можно вывести и самостоятельно.
    Так же я могу привести исходник для программы на паскале, которая осуществляет поиск самого оптимального решения.

  6. #5
    Activist
    Регистрация
    19.01.2005
    Адрес
    Planet Earth
    Сообщений
    407
    Благодарностей: 17
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Talking

    Цитата Сообщение от GriV
    я не виноват, формулы съехали, так они были хотя бы чуток понятней, но если внимательно прочитать, эти формулы можно вывести и самостоятельно.
    Так же я могу привести исходник для программы на паскале, которая осуществляет поиск самого оптимального решения.
    А теперь ассемблерный код релоцируемых распаковщиков и соответствующий упаковщик в студию!
    Последний раз редактировалось dhau; 22.02.2005 в 08:14.

  7. #6
    Guru Аватар для diver
    Регистрация
    26.01.2005
    Адрес
    Пермь
    Сообщений
    2,522
    Благодарностей: 897
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    GriV, оптимальнее статьи цеплять аттачем. тогда и формулы не сьедут, тема быстро загрузится, просматривать будет удобнее и сохранять быстрее и проще.

  8. #7
    Member Аватар для Corpsegrinder
    Регистрация
    19.01.2005
    Адрес
    Chelyabinsk
    Сообщений
    110
    Благодарностей: 1
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от dhau
    А теперь ассемблерный код релоцируемых распаковщиков и соответствующий упаковщик в студию!
    Ага, может тебе ещё и ключ от квратиры, где девки лежат?
    Здесь приведены теоретические основы, есть желание пордолжить и поддержать исследование, дополняй статью и выдвигай предложения, нет - ну и зачем же лезть в эту тему?

    По существу, в RAR'e там вообще могут быть многобайтовые повторы, которые копируются из уже распакованого текста, если я не ошибаюсь.
    А вообще в InfernoGuide предпоследнем довольно большой обзор упаковщиков с форматами хранения данный представлен.

  9. #8
    Activist
    Регистрация
    19.01.2005
    Адрес
    Planet Earth
    Сообщений
    407
    Благодарностей: 17
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от Corpsegrinder
    Здесь приведены теоретические основы, есть желание пордолжить и поддержать исследование, дополняй статью и выдвигай предложения, нет - ну и зачем же лезть в эту тему?
    Ну и зачем теоретические основы в разделе про программирование на спектруме? Этой теории - тонны, и доступ к ней из интернета - тривиален. Логично предположить, что уж если автор начал заикаться на тему алгоритмов компрессии в тематическом форуме, то наверное у него есть какие-то наработки на соответствующей платформе.

    Иначе какой-то сopy & paste получается...

  10. #9
    Vitamin C++ Аватар для Vitamin
    Регистрация
    14.01.2005
    Адрес
    Таганрог, Россия
    Сообщений
    4,031
    Благодарностей: 1426
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от dhau
    Ну и зачем теоретические основы в разделе про программирование на спектруме? Этой теории - тонны, и доступ к ней из интернета - тривиален. Логично предположить, что уж если автор начал заикаться на тему алгоритмов компрессии в тематическом форуме, то наверное у него есть какие-то наработки на соответствующей платформе.

    Иначе какой-то сopy & paste получается...
    прикол в том что это и есть его наработки. в качестве практической реализации имеется прога на пасквиле для анализа исходных данных и оценки степени компрессии.

  11. #10
    Veteran Аватар для GriV
    Регистрация
    18.02.2005
    Адрес
    Набережные Челны
    Сообщений
    1,574
    Благодарностей: 104
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Red face Дело в том, что эта теория чрезвычайно

    сложна, хотя я сам всё это выводил, мне пришлось довольно сильно поломать голову над тем, что бы как минимум понятно объяснить что было и что стало. Даже после этого, в тесном контакте с указанным Vitamin'ом мне пришлось ему объяснять те изюминки которые даёт этот подход, а именно: имеется голое, но чрезвычайно оптимальное RLE, которое (между прочим) оставляет возможность затем применить и huffman, LZ* и т.д. (кому что в голову придёт).

    Я здесь несколько неверно указал, спасибо Vitamin'у и его статьям от A. Coder'а, в которых раскрывается суть алгоритмов LZ*. LZW по сути является командным языком, который используется для формирования рассжатия - т.е. идёт команда "возьми_байт" затем "повтори_его_20_раз" и т.д. и т.п.

    RAR и подавляющее большинство других архиваторов используют именно этот подход, в то время как такой RLE не используется вообще.

    Что касается конкретных программ, да, естьпрограмма на паскале (ДОСовский вариант), там она написана так, что чёрт ногу сломит, и между прочим работает она (видимо именно изза того что это не С) достаточно долго (до нескольких часов над одним Спек-экраном), причём он не создаёт ФАЙЛ, он только даёт конечный размер файла с учётом всего и вся, однако, понятно, что нужно написать (попробовать) ещё и упаковшик, распаковщик провести сравнительное исследование, право, на это надо и нервы и время.

    Смысл же состоит в том, что найдётся какой нибудь программист (тот же Vitamin выразил заинтересованность), который реализует это в мягком (в виде SoftWare), благодаря чему у нас появится очередной матёрский упаковщик, глядя на который все будут облизываться

    В данный момент я думаю над алгоритмом решения этой задачи оптимизации за счёт интерполяции - это позволит внедрить классические методы решения многомерных задач и в зависимости от результата, возможно, я предоставлю иходник для именно такого варианта.

Страница 1 из 3 123 ПоследняяПоследняя

Информация о теме

Пользователи, просматривающие эту тему

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •