Добрый вечер. Интересует взгляд тех, кто знает матан лучше деЛайта (тоесть всех желающих). Скорее всего бред, но тем не менее... Собственно, introduction. Пусть есть буфер размерностью в 255 байт. Имеется две функции, которыми задается его содержимое, для простоты так: buf[k] = F0(k) = 0x00 0 <= k <= 255 buf[k] = F1(k) = k 0 <= k <= 255 buffer 1: 00 00 00 00 00 ... entropy == e1 buffer 2: 01 02 03 04 05 ... entropy == e2 Очевидно, что e2>e1. e2 хочется снизить. Все, что придумано сейчас - добавление однородных данных, как результат - размер увеличивается, энтропия снижается. Тоесть функция, снижающая энтропию: buf_ = F_low_0(buf), такой, например, где после каждого байта исходных данных добавлен 0x00. И вот, очевидно, что для нашего второго буфера намного выгоднее задать buf_[k] = F_low_1(buf, k) = buf[k] - k, тоесть просто вычитаем из k-го элемента его же индекс. На выходе тот же результат - все элементы одинаковы и равны 0x00, энтропия снижена, но размер не изменился. На практике это означает то, что выиграли на размере буфера, при условии что размер реализации функи F_low_..., снижающей энтропию, будет меньше, чем "выигранный размер" данных. В нашем случае F_low_1 выглядеть будет как-то так: Код (Text): 01001110 B9 FF000000 MOV ECX,0FF 01001115 BE 00800001 MOV ESI, buffer_addr 0100111A 290C31 SUB DWORD PTR DS:[ECX+ESI],ECX 0100111D E2 FB LOOPD SHORT 0100111A Итого всего +15 байт, которые дают существенное снижение энтропии. Думаю ясно о чем речь. Мне интересно, есть ли универсальная методика составления подобных функций? Пусть это даже будет какой-то вид брутфорса для блоков данных определенного размера, не суть важно, главное результат. Thx.
Как у вас закручено, но действительно место мало требуется. А не подскажете каким образом вы шифруете ориг файл. Многие берут байт разбивают по 4 бита их ксорят, получают размер в 2 раза выше. Другие используют алфавит. Тупой ксор вообще уже не расматриваю. Как вы делаете ?
365 Не обязательно шифруется. Просто кусок данных жмется, к примеру, LZ77 (zlib). Решение я представляю как что-то аналогичное ГПСЧ, начальное состояние которого мы подбираем. Он выдает последовательность, поксорив которую с нашим буфером мы получаем энтропию ниже. Соответственно распаковщик генерит тот же паттерн, xor, получили в исходном виде.
Все зависит и от данных и, особенно, от их размера. Из универсальных фильтров - MTF, BWT, ST. Посмотрите статьи на http://www.compression.ru/download/, обычно, это называется препроцессинг (трансформация, не меняющая размера). Перспективное направление http://www.compression.ru/download/grammar.html P.S. Если, вдруг, допустимо lossy compression, то смотрите в сторону фрактального сжатия.
Да в общем то нет, дело в том что если Вы считаете что последовательность 00 00 00 00 00 00 00 00 - последовательность равновероятных случайных величин то энтропия максимальна. Вы берете за вероятность - индекс частоты (причем для одного символа) а на самом деле в жизни используются модели k-го приближения... биграфы, триграфы и т.д... Советую Алферова почитать. К тому же случайные величины ДОЛЖНЫ БЫТЬ НЕЗАВИСИМЫ!!!
h0t Остались вопросы. > последовательность 00 00 00 00 00 00 00 00 - последовательность равновероятных случайных величин то энтропия максимальна. Предполагаем, что появление того или иного символа алфавита не зависит от предыдущих. H("aaaaaa") = -(1*log2(1)) = 0 H("aabcad") = 1,79 В чем ошибаюсь? Соответствующим образом определяется и "упакованность" данных различными packer detector'ами. Пожали - энтропия увеличилась. Я использую именно в таком контексте. gazlan > MTF, BWT, ST ... препроцессинг Не то. (: Я плохо объяснил что требуется. Цель препроцессинга - увеличить коэфф. сжатия в дальнейшем, как я понял. Мне нужно уменьшить энтропию уже сжатых данных. Нужен алгоритм генерации вот таких фильтров, видимо уже постпроцессинг. 2all: за линки, литературу - спасибо.
откуда вы знаете что вероятность a=1? вы посчитали частоту, а она не совсем вероятность. Советую Яглома и Алферова почитать! Вы меняете частоты а это не вероятность! (вероятность более общее понятие)
Гм. Если данные в самом деле сжаты (энтропия близка к предельной), то единственный способ ее уменьшить - это "разжать" их. Как "разжимать" - зависит от целей. Для модели нулевого порядка подойдет Huffman итд. Размер при этом, неизбежно, увеличится, тем больше, чем лучше выбранный вами метод компрессии. Смысл этих действий мне недоступен, но идеи и технику можно посмотреть здесь: http://bijective.dogma.net/
