nedoPC.org - View topic - Недоархиватор SHAFF

...

Atom Feed | View unanswered posts | View active topics

It is currently 18 Jul 2018 21:41

Недоархиватор SHAFF

Moderator: Shaos

Page 1 of 7

[ 95 posts ]

Go to page 1, 2, 3, 4, 5 ... 7 Next

Previous topic | Next topic

Недоархиватор SHAFF

Author

Message

Shaos

Admin

Joined: 09 Jan 2003 00:22
Posts: 16708
Location: Colorado

Недоархиватор SHAFF

Задумал я тут недоархиватор, чтобы декодер был поменьше чем MegaLZ, степень сжатия не хуже, ну и само-собой опенсорц

Идея такая - сжатие на байтовом уровне (хаффмана могу попозже приделать) - байт #FF является ключевым (поэтому SHAFF ; ), после него идёт смещение до копии и длина повторяющегося блока. Если смещение/длина в диапазоне от 1 до 254, то ставим один байт, если больше - то #00 и далее два байта (т.е. всего будет три). Получается команда, начинающаяся с #FF, может занимать от 3 до 7 байт. Если встречается отдельно стоящий байт #FF, то он раздваивается - #FF #FF, чтобы декодер не принял его за начало команды. Некоторые последовательности можно объявить командами, например: #FF #00 #00 #00 #01 (смещение в виде #00 #00 #00 никогда не попадётся) может обозначать маркер конца блока. Повторяющиеся байты описываются последовательностью, которая ссылается сама на себя - например 16 нулей могут быть закодированы так: #00 #FF #01 #0F (сначала отдельный байт #00 далее команда копирования по смещению -1 блока длиной 15 байт).

Архиватор работает с блоками 16К - чтобы охватить все возможные варианты повторений строим в памяти буфер 32Мб, в котором располагаем автокорреляционную матрицу с шагом от 1 до 16383. И далее "жадным" алгоритмом откусываем самые большие куски, пока не останутся только маленькие (3 и менее повторяющихся байт). Жмёт долго, но зато оптимально

P.S. Обновление от 7 октября 2013:
Заголовок файла SHAFF может выглядеть примерно так:
0...5 "SHAFF1" - первые 6 байт сигнатура и версия
6,7 - смещение от начала файла до данных первого блока в сетевом формате (big-endian)
8,9 - количество блоков (тоже в сетевом формате)
10,11 - длина последнего блока (она может быть меньше 16K)

P.P.S. Обновление от 11 октября 2013:
Например можно смещение после #FF представлять иначе:
- если смещение равно нулю (#00), то это команда, заменяющая один символ #FF;
- если старший бит 0, то смещение занимает 1 байт и может принимать значения от -1 до -127 (представляемые величинами от #01 до #7F);
- если старшие два бита 1 и 0, то смещение занимает 1 байт и может принимать значения от -128 до -191 (представляемые величинами от #80 до #BF);
- если старшие два бита 1 и 1, то смещение занимает 2 байта и может принимать значения от -192/#FF40 до -16383/#C001 (величины #C000 и #FF41...#FFFF не используются).
Далее идёт размер блока - на нём также можно сэкономить, т.к. размеров больше 16383 (#3FFF) быть не может:
- если старший бит 1, то размер занимает один байт и задаёт значения от 4 до 131 ( представляемые величинами от #80 до #FF или S+124 );
- если старшие два бита 0 и 1, то размер занимает 1 байт и задаёт значения от 132 до 195 ( представляемые величинами от #40 до #7F или S-68 );
- если старшие два бита 0 и 0, то размер занимает 2 байта и может принимать значения от 196/#00С4 до 16383/#3FFF (величины #0000...#00С3 не используются).
В результате без особых усилий мы уменьшили максимальную длину FF-команды до 5 байтов (1+2+2).
Последовательность вида #FF #С0 #00 может являться маркером конца блока, а в будущем ещё и #FF #FF [#41...#FF] можно будет задействовать для задания спец-команд...

P.P.P.S. Обновление от 23 октября 2013 - окончательный формат для первой версии архиватора (добавил комментариев в январе 2017):


	Code: SHAFF header: Bytes 0...5 - signature and version ("SHAFF0", "SHAFF1" or "SHAFF2") Bytes 6,7 - offset to the 1st block of encoded data (big-endian) Bytes 8,9 - number of 16K blocks (big-endian) Bytes 10,11 - size of the last block (less or equal to 16384, also big-endian) Then optional uncompressed auxilary data, for example in case of SNA-file: Bytes 12...14 "SNA" - signature to identify SNA header Bytes 15...41 - SNA 27-byte header itself Then sequence of encoded 16KB blocks in chosen format: SHAFF0 data format: 1st byte in block defines prefix byte that should be used instead of #FF below XX - any byte other than #FF is a single data byte #FF #00 - single byte #FF #FF 0xxxxxxx LENGTH (distance 1...127) #FF 10xxxxxx LENGTH (distance 128...190 and 191 means last distance longer or equal to -191) #FF 11xxxxxx xxxxxxxx LENGTH (directly encoded distance from -191 to -16383) special case without LENGTH: #FF #C0 #00 - end of block (instead of distance -16384) LENGTH is 1 or 2 bytes: 1xxxxxxx - for 4...131 01xxxxxx - for 132..195 00xxxxxx xxxxxxxx - for up to 16383 SHAFF1 data format: 0xxxxxxx - single byte #00...#7F 10xxxxxxx - single byte #80...#FF 110000 - repeat last single byte (no LENGTH after that) 110001 LENGTH - repeat last distance longer than -1 and not equal to previous 110010 LENGTH - repeat previous last distance longer than -1 110011 LENGTH - distance -1 (that basically means copy of the last byte LENGTH times) 1101xxxxxx LENGTH - distance from -2 (000000) to -65 (111111) 11100xxxxxxxx LENGTH - distance from -66 (00000000) to -321 (11111111) 11101xxxxxxxxxx LENGTH - distance from -322 (0000000000) to -1345 (1111111111) 1111xxxxxxxxxxxxxx LENGTH - distance up to -16383 (directly encoded with prefix 11) special case without LENGTH: 111100000000000000 - end of block (after that last byte padded by zero bits) and anything above 111111101010111110 is reserved! LENGTH is a sequence of 2...26 bits that encode length of the copy: 0x - for 2 (encoded by 0) and 3 (encoded by 1) 10xx - for 4 (00), 5 (01), 6 (10), 7 (11) 110xxx - for 8...15 (000...111) 1110xxxx - for 16...31 (0000...1111) 11110xxxxx - for 32...63 (00000...11111) 111110xxxxxx - for 64...127 (000000...111111) 1111110xxxxxxx - for 128...255 (0000000...1111111) 11111110xxxxxxxx - for 256...511 (00000000...11111111) 111111110xxxxxxxxx - for 512...1023 (000000000...111111111) 1111111110xxxxxxxxxx - for 1024...2047 (0000000000...1111111111) 11111111110xxxxxxxxxxx - for 2048...4095 (00000000000...11111111111) 111111111110xxxxxxxxxxxx - for 4096...8191 (000000000000...111111111111) 1111111111110xxxxxxxxxxxxx - for 8192...16383 (0000000000000...1111111111111) SHAFF2 data format (FUTURE): 00... \ 01... - Huffman codes 10... / 11... - Reference that encoded the same way as in SHAFF1 above Optional Huffman table after "HUF" in header: #FF N - start section with codes with length N (1...254) XX ... - code for byte XX (Huffman code starts with most significant bit) #FF #00 ... - code for byte #FF #FF #FF - end of HUF table

P.P.P.P.S. Исходники тут: https://github.com/shaos/shaff (к 8 февраля 2017 реализовал оба метода SHAFF0 и SHAFF1, а 12 февраля 2017 добавил экспериментальную поддержку SHAFF2)


	Code: SHAFF v1.1 (C) 2013,2017 A.A.Shabarshin <me@shaos.net> Usage: shaff [options] filename Encoding options: -0 to use SHAFF0 file format (by default) -1 to use SHAFF1 file format -2 to use SHAFF2 file format (experimental) -b to save blocks as separate files -lN to limit length of matches (default value is 4 for SHAFF0 and 2 for SHAFF1/2) -xHH to set prefix byte other than FF (applicable only to SHAFF0 file format) -e to set default table for English (applicable only to SHAFF2 file format) Decoding options: -d to decode compressed SHAFF file to file -c to decode compressed SHAFF file to screen

_________________
:eugeek:

https://twitter.com/Shaos1973

Last edited by Shaos on 25 Oct 2013 17:53, edited 15 times in total.

07 Oct 2013 02:24

Shaos

Admin

Joined: 09 Jan 2003 00:22
Posts: 16708
Location: Colorado

Живой пример - файл chess.sna (49K), который обычный ZIP жмёт в 8.8K (MegaLZ должен жать примерно также). Разбиваем его на 3 блока по 16K и жмём с помощью SHAFF:


	Code: Estimated compression: 11% (16384 -> 1815) Estimated compression: 51% (16384 -> 8493) Estimated compression: 1% (16384 -> 228)

В итоге потратив 23 минуты на Pentium-4 получаем 10.5К - и это без Хаффмана

Другой пример - файл cybotron.sna (49K), который обычный ZIP жмёт в 5К (игра для 16К спектрума - большая часть снапшота это нули):


	Code: Estimated compression: 35% (16384 -> 5818) Estimated compression: 0% (16384 -> 27) Estimated compression: 1% (16384 -> 208)

За 19 минут на Pentium-4 получили 6К

P.S. Боюсь представить сколько это будет если сверху пройтись Хаффманом...

_________________
:eugeek:

https://twitter.com/Shaos1973

Last edited by Shaos on 11 Oct 2013 21:41, edited 3 times in total.

07 Oct 2013 02:33

vinxru

Retired

Joined: 27 Mar 2013 05:55
Posts: 588
Location: 62.192.229.16

Перед тем как мне дали в руки MegaLZ, я написал свой архиватор по алгоритму LZW (http://ru.wikipedia.org/wiki/LZW)

Скорость сжатия и распаковки получилась очень быстрой, раза в два медленнее обычного копирования память-память. И сжатие не сильно хуже MegaLZ.

Но алгоритм требовал место в памяти под словарь. Вроде бы 512 байт, я сейчас не помню точно.

У MegaLZ есть гигантское преимущество - он не требует доп памяти и исходный архив читает строго последовательно.

07 Oct 2013 02:36

Shaos

Admin

Joined: 09 Jan 2003 00:22
Posts: 16708
Location: Colorado

У меня тоже словаря нет - по сути это сильно упрощённый MegaLZ (а точнее что-то типа LZ77, но где "окно" никуда не "скользит", а растёт от начала кодируемого буфера), где убрана вся алхимия с битовыми последовательностями. Кстати я могу этот архиватор заставить опционально сохранять файл в формате MegaLZ...

_________________
:eugeek:

https://twitter.com/Shaos1973

07 Oct 2013 02:39

Shaos

Admin

Joined: 09 Jan 2003 00:22
Posts: 16708
Location: Colorado

Ещё примеры:

Файл tomahawk.sna (49K) - сжимается ZIP в 28.8K, а у нас:


	Code: Estimated compression: 74% (16384 -> 12269) Estimated compression: 80% (16384 -> 13123) Estimated compression: 64% (16384 -> 10587)

получилось 35.9К за 93 минуты.

Файл exolon.sna (49K) - сжимается ZIP в 25.6К, а у нас:


	Code: Estimated compression: 54% (16384 -> 9000) Estimated compression: 66% (16384 -> 10911) Estimated compression: 69% (16384 -> 11336)

получилось 31.2К за 67 минут.

Файл buzzsaw.sna (49K) - сжимается ZIP в 24.4К, а у нас:


	Code: Estimated compression: 54% (16384 -> 8856) Estimated compression: 72% (16384 -> 11861) Estimated compression: 47% (16384 -> 7763)

получилось 28.5К за 55 минут.

т.е. в 32К не влез только Tomahawk (надо попробовать Хаффманом по нему пройтись)...

P.S. зная вероятности появления символов можно прикинуть хаффмановскую таблицу в онлайне: http://planetcalc.com/2481/

_________________
:eugeek:

https://twitter.com/Shaos1973

07 Oct 2013 06:49

Shaos

Admin

Joined: 09 Jan 2003 00:22
Posts: 16708
Location: Colorado

Заголовок файла SHAFF может выглядеть примерно так:
0...5 "SHAFF1" - первые 6 байт сигнатура и версия
6,7 - смещение от начала файла до данных первого блока в сетевом формате (big-endian)
8,9 - количество блоков (тоже в сетевом формате)
10,11 - длина последнего блока (она может быть меньше 16K)
12,13... - далее 2-байтовые контрольные суммы по одной на блок
перед непосредственно данными может идти дополнительная информация, например содержимое регистров для снапшота и/или таблица кодирования по Хаффману...

P.S. Вот так выглядит процесс сжатия снапшота пустого бейсика (в алгоритме есть косяк - разбираюсь):


	Code: ./shaff zx48.sna Block 1: Cleaning 8388608 words... Cleaning Ok Reading 16384 bytes Analysis... Sequence 9010 bytes in #1CCF is identical to offset -1/#FFFF (estimation: 7379) Sequence 4320 bytes in #1CCE is identical to offset -7374/#E332 (estimation: 3066) Sequence 767 bytes in #1801 is identical to offset -1/#FFFF (estimation: 2304) Sequence 256 bytes in #1CCE is identical to offset -462/#FE32 (estimation: 2055) Sequence 255 bytes in #1B00 is identical to offset -2591/#F5E1 (estimation: 1805) Sequence 235 bytes in #15F5 is identical to offset -256/#FF00 (estimation: 1575) Sequence 231 bytes in #13FC is identical to offset -256/#FF00 (estimation: 1349) Sequence 230 bytes in #14FC is identical to offset -768/#FD00 (estimation: 1124) Sequence 229 bytes in #16FB is identical to offset -768/#FD00 (estimation: 900) Sequence 228 bytes in #16FC is identical to offset -256/#FF00 (estimation: 677) Sequence 228 bytes in #1B00 is identical to offset -1028/#FBFC (estimation: 454) Sequence 34 bytes in #1CCE is identical to offset -62/#FFC2 (estimation: 423) Sequence 31 bytes in #1B00 is identical to offset -799/#FCE1 (estimation: 397) Sequence 26 bytes in #1C90 is identical to offset -115/#FF8D (estimation: 374) Sequence 12 bytes in #1C90 is identical to offset -36/#FFDC (estimation: 365) Sequence 9 bytes in #1C6C is identical to offset -45/#FFD3 (estimation: 359) Sequence 6 bytes in #11FC is identical to offset -11/#FFF5 (estimation: 356) Sequence 5 bytes in #1C17 is identical to offset -8/#FFF8 (estimation: 354) Sequence 5 bytes in #1C3E is identical to offset -58/#FFC6 (estimation: 352) Sequence 4 bytes in #1C6C is identical to offset -15/#FFF1 (estimation: 351) Sequence 4 bytes in #1C0C is identical to offset -1/#FFFF (estimation: 350) Sequence 4 bytes in #1C63 is identical to offset -2/#FFFE (estimation: 349) Sequence 4 bytes in #1C04 is identical to offset -4/#FFFC (estimation: 348) Sequence 4 bytes in #1C53 is identical to offset -8/#FFF8 (estimation: 347) Sequence 4 bytes in #1CC5 is identical to offset -10/#FFF6 (estimation: 346) Estimated compression: 2% (16384 -> 346) Block 2: Cleaning 8388608 words... Cleaning Ok Reading 16384 bytes Analysis... Sequence 16383 bytes in #0001 is identical to offset -1/#FFFF (estimation: 6) Estimated compression: 0% (16384 -> 6) Block 3: Cleaning 8388608 words... Cleaning Ok Reading 16384 bytes Analysis... Sequence 16183 bytes in #0001 is identical to offset -1/#FFFF (estimation: 206) Sequence 7 bytes in #3F7F is identical to offset -8/#FFF8 (estimation: 202) Sequence 7 bytes in #3FDE is identical to offset -16/#FFF0 (estimation: 198) Sequence 6 bytes in #3FD5 is identical to offset -80/#FFB0 (estimation: 195) Sequence 5 bytes in #3FD7 is identical to offset -16/#FFF0 (estimation: 193) Sequence 5 bytes in #3F87 is identical to offset -32/#FFE0 (estimation: 191) Sequence 5 bytes in #3FBC is identical to offset -40/#FFD8 (estimation: 189) Sequence 5 bytes in #3FCC is identical to offset -40/#FFD8 (estimation: 187) Sequence 5 bytes in #3F91 is identical to offset -55/#FFC9 (estimation: 185) Sequence 4 bytes in #3FCF is identical to offset -112/#FF90 (estimation: 184) Sequence 4 bytes in #3FB2 is identical to offset -1/#FFFF (estimation: 183) Sequence 4 bytes in #3FF3 is identical to offset -1/#FFFF (estimation: 182) Sequence 4 bytes in #3FFA is identical to offset -1/#FFFF (estimation: 181) Sequence 4 bytes in #3FA5 is identical to offset -24/#FFE8 (estimation: 180) Sequence 4 bytes in #3F8D is identical to offset -32/#FFE0 (estimation: 179) Sequence 4 bytes in #3FE5 is identical to offset -56/#FFC8 (estimation: 178) Sequence 4 bytes in #3FD1 is identical to offset -110/#FF92 (estimation: 177) Estimated compression: 1% (16384 -> 177) Good bye!

P.S. Всё-таки надо постараться обойтись без Хаффмана - можно попробовать сильнее разнообразить способ представления аргументов команды #FF - не так разнообразно как в MegaLZ, но лучше чем только 1 vs 3 байта, как озвучено в первом посте этого топика - для этого можно проанализировать распределение размеров и смещений на нескольких реальных примерах, чтобы определить оптимальный битовый размер этих двух параметров...

_________________
:eugeek:

https://twitter.com/Shaos1973

07 Oct 2013 18:54

Shaos

Admin

Joined: 09 Jan 2003 00:22
Posts: 16708
Location: Colorado

Косяк исправил - вот правильное сжатие памяти ZX-48K:


	Code: SHAFF v1.0 (C) 2013, Alexander A. Shabarshin <ashabarshin@gmail.com> Block 1: Cleaning 8388608 words... Cleaning Ok Reading 16384 bytes Analysis... Sequence 9009 bytes from #1CCF is identical to offset -1/#FFFF (estimation: 7380) Sequence 4319 bytes from #0001 is identical to offset -1/#FFFF (estimation: 3066) Sequence 767 bytes from #1801 is identical to offset -1/#FFFF (estimation: 2304) Sequence 260 bytes from #16FC is identical to offset -1792/#F900 (estimation: 2051) Sequence 256 bytes from #1B00 is identical to offset -2848/#F4E0 (estimation: 1802) Sequence 255 bytes from #10E1 is identical to offset -256/#FF00 (estimation: 1554) Sequence 235 bytes from #15F5 is identical to offset -256/#FF00 (estimation: 1324) Sequence 231 bytes from #13FC is identical to offset -256/#FF00 (estimation: 1098) Sequence 230 bytes from #14FC is identical to offset -768/#FD00 (estimation: 873) Sequence 229 bytes from #12FB is identical to offset -256/#FF00 (estimation: 649) Sequence 228 bytes from #11FC is identical to offset -256/#FF00 (estimation: 426) Sequence 35 bytes from #1C8F is identical to offset -400/#FE70 (estimation: 396) Sequence 27 bytes from #1C1D is identical to offset -1111/#FBA9 (estimation: 374) Sequence 12 bytes from #1C6C is identical to offset -76/#FFB4 (estimation: 365) Sequence 10 bytes from #1C3F is identical to offset -1096/#FBB8 (estimation: 360) Sequence 7 bytes from #1C01 is identical to offset -4/#FFFC (estimation: 356) Sequence 6 bytes from #11F1 is identical to offset -23/#FFE9 (estimation: 353) Sequence 5 bytes from #1C0B is identical to offset -16/#FFF0 (estimation: 351) Sequence 5 bytes from #1C17 is identical to offset -8/#FFF8 (estimation: 349) Sequence 4 bytes from #1C5D is identical to offset -29/#FFE3 (estimation: 348) Sequence 4 bytes from #1C63 is identical to offset -2/#FFFE (estimation: 347) Sequence 4 bytes from #1C53 is identical to offset -8/#FFF8 (estimation: 346) Sequence 4 bytes from #1CC5 is identical to offset -10/#FFF6 (estimation: 345) Number of commands: 23 Estimated compression: 2% (16384 -> 345) Actual compression: 2% (16384 -> 345) Block 2: Cleaning 8388608 words... Cleaning Ok Reading 16384 bytes Analysis... Sequence 16383 bytes from #0001 is identical to offset -1/#FFFF (estimation: 6) Number of commands: 1 Estimated compression: 0% (16384 -> 6) Actual compression: 0% (16384 -> 6) Block 3: Cleaning 8388608 words... Cleaning Ok Reading 16384 bytes Analysis... Sequence 16183 bytes from #0001 is identical to offset -1/#FFFF (estimation: 206) Sequence 7 bytes from #3F7F is identical to offset -8/#FFF8 (estimation: 202) Sequence 7 bytes from #3FDE is identical to offset -16/#FFF0 (estimation: 198) Sequence 6 bytes from #3FFA is identical to offset -48/#FFD0 (estimation: 195) Sequence 6 bytes from #3FD5 is identical to offset -80/#FFB0 (estimation: 192) Sequence 5 bytes from #3FB4 is identical to offset -56/#FFC8 (estimation: 190) Sequence 5 bytes from #3F87 is identical to offset -32/#FFE0 (estimation: 188) Sequence 5 bytes from #3FBC is identical to offset -40/#FFD8 (estimation: 186) Sequence 5 bytes from #3FCC is identical to offset -40/#FFD8 (estimation: 184) Sequence 5 bytes from #3F91 is identical to offset -55/#FFC9 (estimation: 182) Sequence 4 bytes from #3FF3 is identical to offset -1/#FFFF (estimation: 181) Sequence 4 bytes from #3FA5 is identical to offset -24/#FFE8 (estimation: 180) Sequence 4 bytes from #3F8D is identical to offset -32/#FFE0 (estimation: 179) Sequence 4 bytes from #3FE6 is identical to offset -32/#FFE0 (estimation: 178) Sequence 4 bytes from #3FED is identical to offset -32/#FFE0 (estimation: 177) Sequence 4 bytes from #3FC7 is identical to offset -64/#FFC0 (estimation: 176) Sequence 4 bytes from #3FD1 is identical to offset -110/#FF92 (estimation: 175) Number of commands: 17 Estimated compression: 1% (16384 -> 175) Actual compression: 1% (16384 -> 175) 0x00;84 0x01;11 0x02;12 0x04;17 0x05;10 0x06;4 0x07;3 0x08;9 0x09;2 0x0A;2 0x0B;1 0x0C;3 0x0D;1 0x0F;2 0x10;23 0x12;1 0x15;4 0x17;3 0x18;3 0x1B;1 0x1C;6 0x1D;1 0x20;16 0x21;3 0x23;3 0x28;3 0x30;3 0x31;1 0x33;1 0x37;2 0x38;13 0x3B;1 0x3C;23 0x3E;5 0x3F;2 0x40;24 0x42;32 0x44;17 0x46;1 0x48;2 0x4A;2 0x4B;1 0x4C;1 0x4D;1 0x4E;1 0x50;4 0x52;3 0x53;1 0x54;1 0x57;1 0x58;1 0x5A;1 0x5B;1 0x5C;10 0x62;1 0x66;1 0x6E;1 0x70;2 0x78;7 0x7C;6 0x7E;5 0x7F;1 0x80;3 0x81;1 0x92;1 0x99;1 0xA1;1 0xA8;2 0xA9;1 0xB4;1 0xB6;2 0xB8;1 0xB9;1 0xC4;2 0xCA;1 0xCB;1 0xCC;2 0xCE;1 0xDB;2 0xDF;1 0xE0;1 0xE1;1 0xE4;1 0xE5;1 0xE6;1 0xE7;1 0xEB;2 0xF4;3 0xF9;1 0xFB;2 0xFC;1 0xFD;1 0xFE;2 0xFF;15 0x100;41 Good bye!

В конце видно таблицу вероятностей - по ней можно построить таблицу Хаффмана и прикинуть насколько оно ещё сожмётся:


	Code: 0x00 111 0x100 1100 0x42 1001 0x40 0100 0x3C 0001 0x10 0000 0x44 10110 0x04 10101 0x20 10100 0xFF 01100 0x38 01010 0x02 00101 0x01 110111 0x5C 110101 0x05 110100 0x08 101111 0x78 010110 0x7C 001101 0x1C 001100 0x7E 1101100 0x3E 1011101 0x50 1011100 0x15 0111101 0x06 0111100 0x80 11011011 0x52 11011010 0xF4 0101110 0x0C 0011111 0x07 0011110 0x18 0011101 0x17 0011100 0x23 0010011 0x21 0010010 0x30 0010001 0x28 0010000 0x37 10000111 0x0F 10000110 0x48 10000101 0x3F 10000100 0x0A 10000001 0x09 10000000 0xCC 01101111 0xC4 01101110 0xEB 01101101 0xDB 01101100 0x70 01101011 0x4A 01101010 0xB6 01101001 0xA8 01101000 0xFE 01011111 0xFB 01011110 0x4B 100011111 0x46 100011110 0x4D 100011101 0x4C 100011100 0x31 100011011 0x1D 100011010 0x3B 100011001 0x33 100011000 0x5A 100010111 0x58 100010110 0x62 100010101 0x5B 100010100 0x53 100010011 0x4E 100010010 0x57 100010001 0x54 100010000 0x0D 100000111 0x0B 100000110 0x1B 100000101 0x12 100000100 0xF9 011111111 0xE7 011111110 0xFD 011111101 0xFC 011111100 0xE4 011111011 0xE1 011111010 0xE6 011111001 0xE5 011111000 0x99 011101111 0x92 011101110 0xA9 011101101 0xA1 011101100 0x6E 011101011 0x66 011101010 0x81 011101001 0x7F 011101000 0xCE 011100111 0xCB 011100110 0xE0 011100101 0xDF 011100100 0xB8 011100011 0xB4 011100010 0xCA 011100001 0xB9 011100000

P.S. В таблице 0x100 это на самом деле команда #FF - просто я её отдельно от символа #FF учитываю, чтобы посмотреть имеет смысл её отдельно в Хаффмане считать или нет...

P.P.S. С раздельными FF получилось 526 без Хаффмана и 334 с Хаффманом. Теперь пробуем объединённые коды #FF (15 и 41 будет 2*15+41=71 для #FF):


	Code: 0x00 111 0xFF 101 0x42 1000 0x40 0011 0x10 11011 0x3C 0000 0x44 10011 0x04 10010 0x20 01011 0x38 01000 0x02 00011 0x01 110101 0x5C 110011 0x05 110010 0x08 110001 0x78 010011 0x7C 001001 0x1C 001000 0x7E 1101000 0x3E 1100001 0x50 1100000 0x15 0101001 0x06 0101000 0x80 11010011 0x52 11010010 0xF4 0100100 0x0C 0010111 0x07 0010110 0x18 0010101 0x17 0010100 0x23 0001011 0x21 0001010 0x30 0001001 0x28 0001000 0x37 01111111 0x0F 01111110 0x48 01111101 0x3F 01111100 0x0A 01111001 0x09 01111000 0xCC 01110111 0xC4 01110110 0xEB 01110101 0xDB 01110100 0x70 01110011 0x4A 01110010 0xB6 01110001 0xA8 01110000 0xFE 01001011 0xFB 01001010 0x0D 011110111 0x0B 011110110 0x1B 011110101 0x12 011110100 0x99 011011111 0x92 011011110 0xA9 011011101 0xA1 011011100 0x6E 011011011 0x66 011011010 0x81 011011001 0x7F 011011000 0xCE 011010111 0xCB 011010110 0xE0 011010101 0xDF 011010100 0xB8 011010011 0xB4 011010010 0xCA 011010001 0xB9 011010000 0x4B 011001111 0x46 011001110 0x4D 011001101 0x4C 011001100 0x31 011001011 0x1D 011001010 0x3B 011001001 0x33 011001000 0x5A 011000111 0x58 011000110 0x62 011000101 0x5B 011000100 0x53 011000011 0x4E 011000010 0x57 011000001 0x54 011000000 0xF9 010101111 0xE7 010101110 0xFD 010101101 0xFC 010101100 0xE4 010101011 0xE1 010101010 0xE6 010101001 0xE5 010101000

Подсчёт показывает те же 334 байта, т.е. выгоды в разделении команды #FF и символа #FF практически нет...

P.P.P.S. Кстати ZIP сжимает zx48.sna в 672 байта - выходит SHAFF даже без Хаффмана сжимает лучше

С другой стороны для Хаффмана ещё и таблицу надо хранить...

P.P.P.P.S. GZIP сжимает в 547, BZIP2 в 502, а XZ в 548...

_________________
:eugeek:

https://twitter.com/Shaos1973

10 Oct 2013 17:50

Shaos

Admin

Joined: 09 Jan 2003 00:22
Posts: 16708
Location: Colorado

А теперь попробуем пойти на маленькую хитрость - разрешим 3-байтовые последовательности, которые без Хаффмана не имеют смысла:


	Code: SHAFF v1.0 (C) 2013, Alexander A. Shabarshin <ashabarshin@gmail.com> Block 1: Cleaning 8388608 words... Cleaning Ok Reading 16384 bytes Analysis... Sequence 9009 bytes from #1CCF is identical to offset -1/#FFFF (estimation: 7380) Sequence 4319 bytes from #0001 is identical to offset -1/#FFFF (estimation: 3066) Sequence 767 bytes from #1801 is identical to offset -1/#FFFF (estimation: 2304) Sequence 260 bytes from #16FC is identical to offset -1792/#F900 (estimation: 2051) Sequence 256 bytes from #1B00 is identical to offset -2848/#F4E0 (estimation: 1802) Sequence 255 bytes from #10E1 is identical to offset -256/#FF00 (estimation: 1554) Sequence 235 bytes from #15F5 is identical to offset -256/#FF00 (estimation: 1324) Sequence 231 bytes from #13FC is identical to offset -256/#FF00 (estimation: 1098) Sequence 230 bytes from #14FC is identical to offset -768/#FD00 (estimation: 873) Sequence 229 bytes from #12FB is identical to offset -256/#FF00 (estimation: 649) Sequence 228 bytes from #11FC is identical to offset -256/#FF00 (estimation: 426) Sequence 35 bytes from #1C8F is identical to offset -400/#FE70 (estimation: 396) Sequence 27 bytes from #1C1D is identical to offset -1111/#FBA9 (estimation: 374) Sequence 12 bytes from #1C6C is identical to offset -76/#FFB4 (estimation: 365) Sequence 10 bytes from #1C3F is identical to offset -1096/#FBB8 (estimation: 360) Sequence 7 bytes from #1C01 is identical to offset -4/#FFFC (estimation: 356) Sequence 6 bytes from #11F1 is identical to offset -23/#FFE9 (estimation: 353) Sequence 5 bytes from #1C0B is identical to offset -16/#FFF0 (estimation: 351) Sequence 5 bytes from #1C17 is identical to offset -8/#FFF8 (estimation: 349) Sequence 4 bytes from #1C5D is identical to offset -29/#FFE3 (estimation: 348) Sequence 4 bytes from #1C63 is identical to offset -2/#FFFE (estimation: 347) Sequence 4 bytes from #1C53 is identical to offset -8/#FFF8 (estimation: 346) Sequence 4 bytes from #1CC5 is identical to offset -10/#FFF6 (estimation: 345) Sequence 3 bytes from #1C39 is identical to offset -26/#FFE6 (estimation: 345) Sequence 3 bytes from #1C7C is identical to offset -62/#FFC2 (estimation: 345) Sequence 3 bytes from #12F2 is identical to offset -1/#FFFF (estimation: 345) Sequence 3 bytes from #11EC is identical to offset -2/#FFFE (estimation: 345) Sequence 3 bytes from #1C5A is identical to offset -2/#FFFE (estimation: 345) Sequence 3 bytes from #12E6 is identical to offset -240/#FF10 (estimation: 345) Number of commands: 29 Estimated compression: 2% (16384 -> 345) Actual compression: 2% (16384 -> 345) Block 2: Cleaning 8388608 words... Cleaning Ok Reading 16384 bytes Analysis... Sequence 16383 bytes from #0001 is identical to offset -1/#FFFF (estimation: 6) Number of commands: 1 Estimated compression: 0% (16384 -> 6) Actual compression: 0% (16384 -> 6) Block 3: Cleaning 8388608 words... Cleaning Ok Reading 16384 bytes Analysis... Sequence 16183 bytes from #0001 is identical to offset -1/#FFFF (estimation: 206) Sequence 7 bytes from #3F7F is identical to offset -8/#FFF8 (estimation: 202) Sequence 7 bytes from #3FDE is identical to offset -16/#FFF0 (estimation: 198) Sequence 6 bytes from #3FFA is identical to offset -48/#FFD0 (estimation: 195) Sequence 6 bytes from #3FD5 is identical to offset -80/#FFB0 (estimation: 192) Sequence 5 bytes from #3FB4 is identical to offset -56/#FFC8 (estimation: 190) Sequence 5 bytes from #3F87 is identical to offset -32/#FFE0 (estimation: 188) Sequence 5 bytes from #3FBC is identical to offset -40/#FFD8 (estimation: 186) Sequence 5 bytes from #3FCC is identical to offset -40/#FFD8 (estimation: 184) Sequence 5 bytes from #3F91 is identical to offset -55/#FFC9 (estimation: 182) Sequence 4 bytes from #3FF3 is identical to offset -1/#FFFF (estimation: 181) Sequence 4 bytes from #3FA5 is identical to offset -24/#FFE8 (estimation: 180) Sequence 4 bytes from #3F8D is identical to offset -32/#FFE0 (estimation: 179) Sequence 4 bytes from #3FE6 is identical to offset -32/#FFE0 (estimation: 178) Sequence 4 bytes from #3FED is identical to offset -32/#FFE0 (estimation: 177) Sequence 4 bytes from #3FC7 is identical to offset -64/#FFC0 (estimation: 176) Sequence 4 bytes from #3FD1 is identical to offset -110/#FF92 (estimation: 175) Sequence 3 bytes from #3F96 is identical to offset -56/#FFC8 (estimation: 175) Sequence 3 bytes from #3FF7 is identical to offset -56/#FFC8 (estimation: 175) Sequence 3 bytes from #3FAE is identical to offset -80/#FFB0 (estimation: 175) Sequence 3 bytes from #3F9B is identical to offset -1/#FFFF (estimation: 175) Sequence 3 bytes from #3F68 is identical to offset -16/#FFF0 (estimation: 175) Sequence 3 bytes from #3FB1 is identical to offset -45/#FFD3 (estimation: 175) Number of commands: 23 Estimated compression: 1% (16384 -> 175) Actual compression: 1% (16384 -> 175) 0x00;68 0x01;13 0x02;14 0x03;12 0x04;17 0x05;10 0x06;4 0x07;3 0x08;6 0x09;2 0x0A;2 0x0B;1 0x0C;3 0x0D;1 0x0F;2 0x10;23 0x12;1 0x15;4 0x17;3 0x18;3 0x1A;1 0x1B;1 0x1C;6 0x1D;1 0x20;16 0x21;3 0x23;3 0x28;3 0x2D;1 0x30;3 0x31;1 0x33;1 0x37;2 0x38;12 0x3B;1 0x3C;22 0x3E;6 0x3F;2 0x40;20 0x42;28 0x44;17 0x46;1 0x48;2 0x4A;2 0x4B;1 0x4C;1 0x4D;1 0x4E;1 0x50;5 0x52;3 0x53;1 0x54;1 0x57;1 0x58;1 0x5A;1 0x5B;1 0x5C;8 0x62;1 0x66;1 0x6E;1 0x70;2 0x78;7 0x7C;6 0x7E;5 0x7F;1 0x80;3 0x81;1 0x92;1 0x99;1 0xA1;1 0xA8;2 0xA9;1 0xB4;1 0xB6;2 0xB8;1 0xB9;1 0xC4;2 0xCA;1 0xCB;1 0xCC;1 0xCE;1 0xDB;2 0xDF;1 0xE0;1 0xE1;1 0xE4;1 0xE5;1 0xE6;1 0xE7;1 0xEB;2 0xF0;1 0xF4;3 0xF9;1 0xFB;2 0xFC;1 0xFD;1 0xFE;2 0xFF;14 0x100;53 Good bye!

Хаффмановский калькулятор на это выдал вот такую табличку:


	Code: 0x00 101 0x100 001 0x42 0110 0x10 11110 0x3C 11101 0x40 11100 0x44 11001 0x04 11000 0x20 01111 0xFF 01011 0x02 01010 0x01 01001 0x38 111111 0x03 111110 0x05 110111 0x5C 110100 0x78 010001 0x7C 010000 0x08 000111 0x3E 000101 0x1C 000100 0x7E 1101101 0x50 1101100 0x15 1101010 0x06 0111001 0x07 11010111 0x17 0001101 0x0C 0001100 0x52 0000111 0x30 0000110 0xF4 0000101 0x80 0000100 0x21 0000011 0x18 0000010 0x28 0000001 0x23 0000000 0xFE 11010110 0x37 10011111 0x0F 10011110 0x48 10011101 0x3F 10011100 0x0A 10011001 0x09 10011000 0xDB 10010111 0xC4 10010110 0xFB 10010101 0xEB 10010100 0x70 10010011 0x4A 10010010 0xB6 10010001 0xA8 10010000 0x0D 100110111 0x0B 100110110 0x1A 100110101 0x12 100110100 0x81 100011111 0x7F 100011110 0x99 100011101 0x92 100011100 0x62 100011011 0x5B 100011010 0x6E 100011001 0x66 100011000 0xCA 100010111 0xB9 100010110 0xCC 100010101 0xCB 100010100 0xA9 100010011 0xA1 100010010 0xB8 100010001 0xB4 100010000 0x3B 100001111 0x33 100001110 0x4B 100001101 0x46 100001100 0x1D 100001011 0x1B 100001010 0x31 100001001 0x2D 100001000 0x57 100000111 0x54 100000110 0x5A 100000101 0x58 100000100 0x4D 100000011 0x4C 100000010 0x53 100000001 0x4E 100000000 0xE5 011101111 0xE4 011101110 0xE7 011101101 0xE6 011101100 0xDF 011101011 0xCE 011101010 0xE1 011101001 0xE0 011101000 0xF9 011100011 0xF0 011100010 0xFD 011100001 0xFC 011100000

Что даёт 341 байт - даже больше, где мы остановились на 4-байтовых комбинациях...

_________________
:eugeek:

https://twitter.com/Shaos1973

10 Oct 2013 20:04

Shaos

Admin

Joined: 09 Jan 2003 00:22
Posts: 16708
Location: Colorado

Итак с исправленным архиватором имеем (без Хаффмана):

zx48.sna - 0.5K


	Code: Estimated compression: 2% (16384 -> 345) Estimated compression: 0% (16384 -> 6) Estimated compression: 1% (16384 -> 175)

chess.sna - 10.5K


	Code: Estimated compression: 10% (16384 -> 1745) Estimated compression: 51% (16384 -> 8508) Estimated compression: 1% (16384 -> 227)

cybotron.sna - 6.1K


	Code: Estimated compression: 35% (16384 -> 5861) Estimated compression: 0% (16384 -> 25) Estimated compression: 1% (16384 -> 206)

Для примера захаффманим chess:


	Code: 0x100 000 0x00 11000 0x03 10110 0x88 00110 0x04 00100 0x20 111100 0x05 111000 0x06 110010 0x01 101000 0xFE 100001 0x21 011110 0x08 011101 0xCD 011001 0x07 010111 0x3A 010010 0x32 010001 0x10 001010 0x28 1111011 0x02 1110110 0x18 1110010 0x23 1101100 0x40 1101011 0x3E 1010101 0x11 1010010 0xDD 1000110 0xCB 1000101 0xFF 1000001 0x09 1000000 0x0A 0111110 0xA7 0111000 0x38 0110111 0xC9 0110110 0x0F 0110001 0x0E 0110000 0x80 0101100 0x7E 0101010 0x89 0101000 0x30 0100110 0x44 0011110 0xC0 0010110 0xAF 11111110 0x0D 11111101 0x36 11101000 0x22 11011101 0x0B 11011100 0xF1 11011011 0x78 11011010 0x19 11010001 0x42 11001111 0x2C 11001110 0xF0 11001100 0x1F 10111111 0xED 10111101 0xF8 10111010 0xE1 10111001 0x12 10111000 0xFB 10101001 0xF5 10101000 0xE6 10100111 0xE0 10100110 0xB0 10011101 0xFD 10011010 0xC1 10011001 0x6F 10011000 0x2A 10010111 0x3C 10010110 0x77 10001110 0xC3 01110010 0x13 01101001 0xFC 01011010 0xE5 01010111 0x2B 01010110 0x1E 01010011 0xCA 01010010 0x50 01000010 0x4E 01000001 0x16 01000000 0xAE 00111110 0x2D 111111111 0x0C 111111110 0x34 00101110 0xC5 111110011 0x31 111110010 0xF6 111110000 0x14 111101011 0xEB 111101001 0x72 111101000 0xA9 111010101 0x3F 111010100 0x29 111010011 0x47 111010010 0x52 110111111 0x79 110111101 0x73 110111100 0x35 110101011 0x1C 110101010 0x65 110101001 0x49 110101000 0x15 110100101 0xD5 110011011 0xC6 110011010 0xBE 101111100 0x41 101111001 0x3D 101111000 0x6C 101110111 0x60 101110110 0x5F 101011111 0x33 101011110 0xC8 101011101 0xB2 101011100 0x24 101011001 0x1A 101011000 0x4F 100111111 0x43 100111110 0x57 100111101 0x53 100111100 0x17 100111001 0x7B 100110111 0x7A 100110110 0x87 100101011 0x74 100101010 0x96 100101001 0x93 100101000 0x37 100100111 0x56 100100101 0x4B 100100100 0xF3 100011111 0xD1 100011110 0xFA 100010010 0x2E 100010001 0x1B 100010000 0x62 011111111 0x45 011111110 0x83 011111101 0x63 011111100 0xF9 011100111 0xA8 011100110 0x51 011010111 0xF2 011010101 0x5E 011010100 0x70 010011111 0x61 010011110 0x92 010011101 0x8D 010011100 0xE7 010000111 0x9F 010000110 0x55 001111111 0xF4 001111110 0x39 001110111 0x2F 001110110 0x4A 001110101 0x46 001110100 0x9D 001011111 0x4C 001011110 0xB1 1111110011 0xA0 1111110010 0xB7 1111110001 0xB4 1111110000 0x7C 1111101111 0x75 1111101110 0x9C 1111101101 0x8E 1111101100 0x4D 1111101011 0x3B 1111101010 0x67 1111101001 0x58 1111101000 0xE8 1111100011 0xB8 1111100010 0xDA 1111010100 0x98 1110111111 0x94 1110111110 0xAB 1110111101 0xA6 1110111100 0x71 1110111011 0x69 1110111010 0x90 1110111001 0x8F 1110111000 0x5C 1110101101 0x48 1110101100 0xA1 1110011111 0x6E 1110011110 0xDB 1110011101 0xC2 1110011100 0x26 1110011011 0x1D 1110011010 0x68 1110011001 0x5B 1110011000 0xEF 1101111100 0x54 1101001111 0x27 1101001110 0x7F 1101001101 0x6D 1101001100 0xA3 1101000011 0x81 1101000010 0xEC 1101000001 0xCC 1101000000 0xAA 1010110111 0xA5 1010110110 0xF7 1010110101 0xAC 1010110100 0x5D 1001110001 0xD9 1001110000 0x91 1001000111 0x8A 1001000110 0xD0 1001000101 0x9B 1001000100 0x5A 1001000011 0x82 1001000001 0x76 1001000000 0xD6 1000100111 0xD3 1000100110 0x84 0110101101 0x66 0110101100 0x97 0110100011 0x86 0110100010 0x9A 0110100001 0x99 0110100000 0xEA 0101101111 0xE2 0101101110 0x25 0101101101 0xBD 0011100111 0xA4 0011100110 0xD8 0011100101 0xCE 0011100100 0x85 0011100011 0xA2 0011100001 0x95 0011100000 0xD2 11110101010 0xB6 11101011111 0x9E 11101011110 0xC4 11101011101 0xBA 11101011100 0x7D 11011111011 0xEE 11011111010 0x8C 11010010011 0x6B 11010010010 0xBC 11010010001 0xB3 11010010000 0xD7 10111110111 0xCF 10111110110 0xE4 10111110100 0xBB 10010011011 0xB5 10010011010 0xDE 10010011001 0xDC 10010011000 0x8B 10010000101 0x64 10010000100 0x59 01011011001 0xE3 111101010111 0xDF 111101010110 0xE9 01011011000 0xB9 00111000101 0xAD 101111101011 0x6A 1011111010101 0xC7 001110001001 0xBF 001110001000 0xD4 1011111010100

C Хаффиманом получается 8.9К, т.е. почти как ZIP

_________________
:eugeek:

https://twitter.com/Shaos1973

10 Oct 2013 20:39

Shaos

Admin

Joined: 09 Jan 2003 00:22
Posts: 16708
Location: Colorado

Shaos wrote:

Итак с исправленным архиватором имеем (без Хаффмана):

zx48.sna - 0.5K


	Code: Estimated compression: 2% (16384 -> 345) Estimated compression: 0% (16384 -> 6) Estimated compression: 1% (16384 -> 175)

chess.sna - 10.5K


	Code: Estimated compression: 10% (16384 -> 1745) Estimated compression: 51% (16384 -> 8508) Estimated compression: 1% (16384 -> 227)

cybotron.sna - 6.1K


	Code: Estimated compression: 35% (16384 -> 5861) Estimated compression: 0% (16384 -> 25) Estimated compression: 1% (16384 -> 206)

Результаты по другим [недо]архиваторам:

zx48.sna (49K):


	Code: SHAFFv1b: Actual compression: 2% (16384 -> 342) Actual compression: 0% (16384 -> 8) Actual compression: 1% (16384 -> 178) Compressed file size: 570 bytes SHAFFv1c: Bitstream compression: 1% (16384 -> 281) Bitstream compression: 0% (16384 -> 7) Bitstream compression: 0% (16384 -> 138) Bitwise compressed file size (v1): 438 bytes SHAFFv1d: Bit-stream compression: 1% (16384 -> 277) Bit-stream compression: 0% (16384 -> 8) Bit-stream compression: 0% (16384 -> 142) SHAFF0 compressed file size: 561 bytes SHAFF1 compressed file size: 439 bytes SHAFFv1e: Bit-stream compression: 1% (16384 -> 271) Bit-stream compression: 0% (16384 -> 8) Bit-stream compression: 0% (16384 -> 139) SHAFF0 compressed file size: 555 bytes SHAFF1 compressed file size: 429 bytes SHAFFv1f: Bit-stream compression: 1% (16384 -> 277) Bit-stream compression: 0% (16384 -> 8) Bit-stream compression: 0% (16384 -> 138) SHAFF0 compressed file size: 555 bytes SHAFF1 compressed file size: 435 bytes SHAFFv1g: Bit-stream compression: 1% (16384 -> 272) Bit-stream compression: 0% (16384 -> 8) Bit-stream compression: 0% (16384 -> 136) SHAFF0 compressed file size: 555 bytes SHAFF1 compressed file size: 428 bytes SHAFFv1h: Bit-stream compression: 1% (16384 -> 273) Bit-stream compression: 0% (16384 -> 8) Bit-stream compression: 0% (16384 -> 138) SHAFF0 compressed file size: 555 bytes SHAFF1 compressed file size: 431 bytes

SHAFFv1h - 431
SHAFFv1g - 428
SHAFFv1f - 435
SHAFFv1e - 429
SHAFFv1d - 439
SHAFFv1c - 438
SHAFFv1b - 570
SHAFFv1a - 526
SHAFFv1a+Huffman - 333
MegzLZ - 1021
Hrum - 926
Hrust - 478
ZIP - 672
GZIP - 547
BZIP2 - 502
RAR 3.80 - 552
XZ (LZMA2) - 548

chess.sna (49K):


	Code: SHAFFv1b: Actual compression: 10% (16384 -> 1665) Actual compression: 51% (16384 -> 8427) Actual compression: 1% (16384 -> 228) Compressed file size: 10362 bytes SHAFFv1c: Bitstream compression: 8% (16384 -> 1330) Bitstream compression: 44% (16384 -> 7255) Bitstream compression: 1% (16384 -> 183) Bitwise compressed file size (v1): 8780 bytes SHAFFv1d: Bit-stream compression: 8% (16384 -> 1322) Bit-stream compression: 44% (16384 -> 7286) Bit-stream compression: 1% (16384 -> 188) SHAFF0 compressed file size: 10273 bytes SHAFF1 compressed file size: 8808 bytes SHAFFv1e: Bit-stream compression: 7% (16384 -> 1308) Bit-stream compression: 44% (16384 -> 7239) Bit-stream compression: 1% (16384 -> 184) SHAFF0 compressed file size: 9944 bytes SHAFF1 compressed file size: 8743 bytes SHAFFv1f: Bit-stream compression: 7% (16384 -> 1311) Bit-stream compression: 43% (16384 -> 7183) Bit-stream compression: 1% (16384 -> 183) SHAFF0 compressed file size: 9943 bytes SHAFF1 compressed file size: 8688 bytes SHAFFv1g: Bit-stream compression: 7% (16384 -> 1305) Bit-stream compression: 43% (16384 -> 7179) Bit-stream compression: 1% (16384 -> 181) SHAFF0 compressed file size: 9943 bytes SHAFF1 compressed file size: 8676 bytes SHAFFv1h: Bit-stream compression: 7% (16384 -> 1301) Bit-stream compression: 43% (16384 -> 7169) Bit-stream compression: 1% (16384 -> 183) SHAFF0 compressed file size: 9943 bytes SHAFF1 compressed file size: 8665 bytes

SHAFFv1h - 8.6K
SHAFFv1g - 8.6K
SHAFFv1f - 8.6K
SHAFFv1e - 8.7K
SHAFFv1d - 8.8K
SHAFFv1c - 8.7K
SHAFFv1b - 10.3K
SHAFFv1a - 10.5K
SHAFFv1a+Huffman - 8.9K
MegaLZ - 9.0K
Hrum - 8.9K
Hrust - 8.5K
ZIP - 8.8K
GZIP - 8.8K
BZIP2 - 9.3K
RAR 3.80 - 8.3K
XZ (LZMA2) - 8.0K

cybotron.sna (49K):


	Code: SHAFFv1b: Actual compression: 35% (16384 -> 5751) Actual compression: 0% (16384 -> 32) Actual compression: 1% (16384 -> 208) Compressed file size: 6033 bytes SHAFFv1c: Bitstream compression: 28% (16384 -> 4690) Bitstream compression: 0% (16384 -> 20) Bitstream compression: 1% (16384 -> 167) Bitwise compressed file size (v1): 4889 bytes SHAFFv1d: Bit-stream compression: 28% (16384 -> 4733) Bit-stream compression: 0% (16384 -> 20) Bit-stream compression: 1% (16384 -> 171) SHAFF0 compressed file size: 5968 bytes SHAFF1 compressed file size: 4935 bytes SHAFFv1e: Bit-stream compression: 28% (16384 -> 4690) Bit-stream compression: 0% (16384 -> 20) Bit-stream compression: 1% (16384 -> 168) SHAFF0 compressed file size: 5777 bytes SHAFF1 compressed file size: 4890 bytes SHAFFv1f: Bit-stream compression: 28% (16384 -> 4641) Bit-stream compression: 0% (16384 -> 21) Bit-stream compression: 1% (16384 -> 167) SHAFF0 compressed file size: 5777 bytes SHAFF1 compressed file size: 4840 bytes SHAFFv1g: Bit-stream compression: 28% (16384 -> 4632) Bit-stream compression: 0% (16384 -> 20) Bit-stream compression: 1% (16384 -> 166) SHAFF0 compressed file size: 5777 bytes SHAFF1 compressed file size: 4829 bytes SHAFFv1h: Bit-stream compression: 28% (16384 -> 4629) Bit-stream compression: 0% (16384 -> 21) Bit-stream compression: 1% (16384 -> 167) SHAFF0 compressed file size: 5777 bytes SHAFF1 compressed file size: 4828 bytes

SHAFFv1h - 4.8K
SHAFFv1g - 4.8K
SHAFFv1f - 4.8K
SHAFFv1e - 4.8K
SHAFFv1d - 4.9K
SHAFFv1c - 4.8K
SHAFFv1b - 6.0K
SHAFFv1a - 6.1K
MegaLZ - 5.2K
Hrum - 5.2K
Hrust - 4.7K
ZIP - 5.0K
GZIP - 4.9K
BZIP2 - 5.2K
RAR 3.80 - 4.7K
XZ (LZMA2) - 4.4K

И оставшиеся SNA-файлы:

tomahawk.sna (49K):


	Code: SHAFFv1a: Estimated compression: 75% (16384 -> 12298) Estimated compression: 80% (16384 -> 13185) Estimated compression: 65% (16384 -> 10711) SHAFFv1b: Actual compression: 74% (16384 -> 12194) Actual compression: 78% (16384 -> 12870) Actual compression: 64% (16384 -> 10496) Compressed file size: 35602 bytes SHAFFv1c: Bitstream compression: 63% (16384 -> 10350) Bitstream compression: 65% (16384 -> 10786) Bitstream compression: 53% (16384 -> 8831) Bitwise compressed file size (v1): 29979 bytes SHAFFv1d: Bit-stream compression: 63% (16384 -> 10376) Bit-stream compression: 66% (16384 -> 10842) Bit-stream compression: 53% (16384 -> 8840) SHAFF0 compressed file size: 35204 bytes SHAFF1 compressed file size: 30070 bytes SHAFFv1e: Bit-stream compression: 62% (16384 -> 10318) Bit-stream compression: 65% (16384 -> 10800) Bit-stream compression: 53% (16384 -> 8777) SHAFF0 compressed file size: 33938 bytes SHAFF1 compressed file size: 29906 bytes SHAFFv1f: Bit-stream compression: 62% (16384 -> 10252) Bit-stream compression: 65% (16384 -> 10680) Bit-stream compression: 53% (16384 -> 8736) SHAFF0 compressed file size: 33930 bytes SHAFF1 compressed file size: 29680 bytes SHAFFv1g: Bit-stream compression: 62% (16384 -> 10245) Bit-stream compression: 65% (16384 -> 10685) Bit-stream compression: 53% (16384 -> 8717) SHAFF0 compressed file size: 33935 bytes SHAFF1 compressed file size: 29659 bytes SHAFFv1h: Bit-stream compression: 62% (16384 -> 10218) Bit-stream compression: 65% (16384 -> 10654) Bit-stream compression: 53% (16384 -> 8704) SHAFF0 compressed file size: 33935 bytes SHAFF1 compressed file size: 29588 bytes

SHAFFv1h - 29.5K
SHAFFv1g - 29.6K
SHAFFv1f - 29.6K
SHAFFv1e - 29.9K
SHAFFv1d - 30.0K
SHAFFv1c - 29.9K
SHAFFv1b - 35.6K
SHAFFv1a - 36.2K
MegaLZ - 29.0K
Hrum - 29.2K
Hrust - 28.4K
ZIP - 28.8K
GZIP - 28.7K
BZIP2 - 30.1K
RAR 3.80 - 27.5K
XZ (LZMA2) - 25.6K

exolon.sna (49K):


	Code: SHAFFv1a: Estimated compression: 54% (16384 -> 9011) Estimated compression: 66% (16384 -> 10920) Estimated compression: 69% (16384 -> 11378) SHAFFv1b: Actual compression: 54% (16384 -> 8872) Actual compression: 66% (16384 -> 10917) Actual compression: 69% (16384 -> 11351) Compressed file size: 31182 bytes SHAFFv1c: Bitstream compression: 45% (16384 -> 7408) Bitstream compression: 56% (16384 -> 9311) Bitstream compression: 60% (16384 -> 9832) Bitwise compressed file size (v1): 26562 bytes SHAFFv1d: Bit-stream compression: 45% (16384 -> 7441) Bit-stream compression: 56% (16384 -> 9332) Bit-stream compression: 60% (16384 -> 9865) SHAFF0 compressed file size: 30810 bytes SHAFF1 compressed file size: 26649 bytes SHAFFv1e: Bit-stream compression: 44% (16384 -> 7367) Bit-stream compression: 56% (16384 -> 9287) Bit-stream compression: 59% (16384 -> 9772) SHAFF0 compressed file size: 29797 bytes SHAFF1 compressed file size: 26438 bytes SHAFFv1f: Bit-stream compression: 44% (16384 -> 7337) Bit-stream compression: 56% (16384 -> 9250) Bit-stream compression: 59% (16384 -> 9709) SHAFF0 compressed file size: 29776 bytes SHAFF1 compressed file size: 26307 bytes SHAFFv1g: Bit-stream compression: 44% (16384 -> 7331) Bit-stream compression: 56% (16384 -> 9241) Bit-stream compression: 59% (16384 -> 9706) SHAFF0 compressed file size: 29794 bytes SHAFF1 compressed file size: 26290 bytes SHAFFv1h: Bit-stream compression: 44% (16384 -> 7328) Bit-stream compression: 56% (16384 -> 9248) Bit-stream compression: 59% (16384 -> 9688) SHAFF0 compressed file size: 29794 bytes SHAFF1 compressed file size: 26276 bytes

SHAFFv1h - 26.2K
SHAFFv1g - 26.2K
SHAFFv1f - 26.3K
SHAFFv1e - 26.4K
SHAFFv1d - 26.6K
SHAFFv1c - 26.5K
SHAFFv1b - 31.2K
SHAFFv1a - 31.3K
MegaLZ - 25.7K
Hrum - 25.9K
Hrust - 25.1K
ZIP - 25.6K
GZIP - 25.5K
BZIP2 - 27.8K
RAR 3.80 - 24.5K
XZ (LZMA2) - 22.9K

buzzsaw.sna (49K):


	Code: SHAFFv1a: Estimated compression: 53% (16384 -> 8846) Estimated compression: 72% (16384 -> 11850) Estimated compression: 47% (16384 -> 7716) SHAFFv1b: Actual compression: 54% (16384 -> 8940) Actual compression: 71% (16384 -> 11789) Actual compression: 46% (16384 -> 7698) Compressed file size: 28469 bytes SHAFFv1c: Bitstream compression: 50% (16384 -> 8332) Bitstream compression: 66% (16384 -> 10888) Bitstream compression: 36% (16384 -> 6001) Bitwise compressed file size (v1): 25233 bytes SHAFFv1d: Bit-stream compression: 50% (16384 -> 8332) Bit-stream compression: 66% (16384 -> 10942) Bit-stream compression: 37% (16384 -> 6128) SHAFF0 compressed file size: 28290 bytes SHAFF1 compressed file size: 25414 bytes SHAFFv1e: Bit-stream compression: 50% (16384 -> 8307) Bit-stream compression: 66% (16384 -> 10894) Bit-stream compression: 36% (16384 -> 5970) SHAFF0 compressed file size: 27888 bytes SHAFF1 compressed file size: 25182 bytes SHAFFv1f: Bit-stream compression: 50% (16384 -> 8279) Bit-stream compression: 66% (16384 -> 10844) Bit-stream compression: 36% (16384 -> 5962) SHAFF0 compressed file size: 27878 bytes SHAFF1 compressed file size: 25097 bytes SHAFFv1g: Bit-stream compression: 50% (16384 -> 8274) Bit-stream compression: 66% (16384 -> 10841) Bit-stream compression: 36% (16384 -> 5953) SHAFF0 compressed file size: 27884 bytes SHAFF1 compressed file size: 25080 bytes SHAFFv1h: Bit-stream compression: 50% (16384 -> 8289) Bit-stream compression: 66% (16384 -> 10841) Bit-stream compression: 36% (16384 -> 5959) SHAFF0 compressed file size: 27887 bytes SHAFF1 compressed file size: 25101 bytes

SHAFFv1h - 25.1K
SHAFFv1g - 25.0K
SHAFFv1f - 25.0K
SHAFFv1e - 25.1K
SHAFFv1d - 25.4K
SHAFFv1c - 25.2K
SHAFFv1b - 28.5K
SHAFFv1a - 28.4K
MegaLZ - 24.3K
Hrum - 24.3K
Hrust - 23.1K
ZIP - 24.4K
GZIP - 24.2K
BZIP2 - 25.1K
RAR 3.80 - 15.1K
XZ (LZMA2) - 17.1K

bozxle.sna (49K):


	Code: SHAFFv1b: Actual compression: 41% (16384 -> 6808) Actual compression: 66% (16384 -> 10828) Actual compression: 41% (16384 -> 6843) Compressed file size: 24521 bytes SHAFFv1c: Bitstream compression: 32% (16384 -> 5300) Bitstream compression: 60% (16384 -> 9991) Bitstream compression: 31% (16384 -> 5184) Bitwise compressed file size (v1): 20486 bytes SHAFFv1e: Bit-stream compression: 31% (16384 -> 5222) Bit-stream compression: 60% (16384 -> 9969) Bit-stream compression: 32% (16384 -> 5260) SHAFF0 compressed file size: 23306 bytes SHAFF1 compressed file size: 20463 bytes SHAFFv1f: Bit-stream compression: 31% (16384 -> 5153) Bit-stream compression: 60% (16384 -> 9901) Bit-stream compression: 31% (16384 -> 5196) SHAFF0 compressed file size: 23279 bytes SHAFF1 compressed file size: 20262 bytes SHAFFv1g: Bit-stream compression: 31% (16384 -> 5193) Bit-stream compression: 60% (16384 -> 9945) Bit-stream compression: 31% (16384 -> 5196) SHAFF0 compressed file size: 23297 bytes SHAFF1 compressed file size: 20345 bytes SHAFFv1h: Bit-stream compression: 31% (16384 -> 5141) Bit-stream compression: 60% (16384 -> 9919) Bit-stream compression: 31% (16384 -> 5185) SHAFF0 compressed file size: 23299 bytes SHAFF1 compressed file size: 20257 bytes

SHAFFv1h - 20.2K
SHAFFv1g - 20.3K
SHAFFv1f - 20.2K
SHAFFv1e - 20.4K
SHAFFv1c - 20.4K
SHAFFv1b - 24.5K
MegaLZ - 20.1K
Hrum - 20.1K
Hrust - 19.5K
ZIP - 19.5K
GZIP - 19.3K
BZIP2 - 21.0K
RAR 3.80 - 18.9K
XZ (LZMA2) - 17.1K

Возникает вопрос - выкатывать архиватор в таком виде как версию 1 и думать над более компактным представлением в следующих версиях либо поресёрчить ещё?...

P.S. Например можно смещение после #FF представлять иначе:
- если смещение равно нулю (#00), то это команда, заменяющая один символ #FF;
- если старший бит 0, то смещение занимает 1 байт и может принимать значения от -1 до -127 (представляемые величинами от #01 до #7F);
- если старшие два бита 1 и 0, то смещение занимает 1 байт и может принимать значения от -128 до -191 (представляемые величинами от #80 до #BF);
- если старшие два бита 1 и 1, то смещение занимает 2 байта и может принимать значения от -192/#FF40 до -16383/#C001 (величины #C000 и #FF41...#FFFF не используются).
Далее идёт размер блока - на нём также можно сэкономить, т.к. размеров больше 16383 (#3FFF) быть не может:
- если старший бит 1, то размер занимает один байт и задаёт значения от 4 до 131 ( представляемые величинами от #80 до #FF или S+124 );
- если старшие два бита 0 и 1, то размер занимает 1 байт и задаёт значения от 132 до 195 ( представляемые величинами от #40 до #7F или S-68 );
- если старшие два бита 0 и 0, то размер занимает 2 байта и может принимать значения от 196/#00С4 до 16383/#3FFF (величины #0000...#00С3 не используются).
В результате без особых усилий мы уменьшили максимальную длину FF-команды до 5 байтов (1+2+2).

P.P.S. Последовательность вида #FF #С0 #00 может являться маркером конца блока, а в будущем ещё и #FF #FF [#41...#FF] можно будет задействовать для задания спец-команд...

P.P.P.S. Результаты подкорректированного алгоритма представления сжатых данных обозначены выше как SHAFFv1b (уже с учётом SNA-хедера и маркера конца блоков). Выгода по сравнению с SHAFFv1a есть, но не сильно существенная....

P.P.P.P.S. 15 октября добавил сюда результаты по битовопоточному SHAFF под названием SHAFFv1c - он даже MegaLZ бывает обгоняет, но вот Hrust похоже недосягаем...

P.P.P.P.P.S. 17 октября добавляю результаты SHAFFv1d - финальный прототип для версии 1. Хотя чего-то он худшие результаты показывает, чем SHAFFv1c - видимо надо подкорректировать формат ещё раз

P.P.P.P.P.P.S. 20 октября добавляю результаты SHAFFv1e - на этот раз точно финальный прототип для версии 1. Он обгоняет MegaLZ на данных, где есть много повторяющихся байтов, но отстаёт, если их мало. Но зато все имеющиеся SNA-файлы влезают в 32К...

P.P.P.P.P.P.P.S. 21 октября добавляю результаты SHAFFv1f - он чуть лучше, а затем и SHAFFv1g - он ещё лучше...

P.P.P.P.P.P.P.P.S. 24 октября добавил результаты по SHAFFv1h - он где-то лучше, а где-то хуже...

_________________
:eugeek:

https://twitter.com/Shaos1973

Last edited by Shaos on 24 Oct 2013 06:51, edited 33 times in total.

11 Oct 2013 06:09

alone

Writer

Joined: 06 Sep 2007 08:05
Posts: 19
Location: 212.26.238.228

А используется "оптимальный LZH" или хотя бы Lazy Evaluation? В MegaLZ "оптимальный LZH". От этого зависит сила сжатия.

12 Oct 2013 01:26

Shaos

Admin

Joined: 09 Jan 2003 00:22
Posts: 16708
Location: Colorado


	alone wrote: А используется "оптимальный LZH" или хотя бы Lazy Evaluation? В MegaLZ "оптимальный LZH". От этого зависит сила сжатия.

Это оптимальный LZ77-like, но не совсем оптимальное представление (без Хаффмана - с Хаффманом как раз всё хорошо)

_________________
:eugeek:

https://twitter.com/Shaos1973

12 Oct 2013 02:05

alone

Writer

Joined: 06 Sep 2007 08:05
Posts: 19
Location: 212.26.238.228

Оптимальный в том смысле, что из всех способов разбиения последовательности на литералы и ссылки выбирается самый оптимальный (идёт обсчёт всех путей, потом выбирается самый короткий).

12 Oct 2013 03:56

Shaos

Admin

Joined: 09 Jan 2003 00:22
Posts: 16708
Location: Colorado

У меня всегда выкусывается самая большая из оставшихся повторяющихся последовательностей - в этом смысле алгоритм "оптимален", однако представление информации, когда команда имеет в виде префикса целый байт #FF, не совсем годится для кодирования коротких последовательностей. Сейчас рассматриваю варианты "постобработки" без скатывания в побитовую алхимию (Хаффман и т.д.) - например после LZ77 (со "скользящим" окном) можно применить табличный LZ на оставшиеся непожатые данные, ищущий и кодирующий часто повторяющиеся "триады" (тройки байтов) одним байтом (для подстановки выбираются не встречающиеся или редко встречающиеся байты). Сейчас у меня задача любой SNA упаковывать в 32К (пока из тех что я пробую не уталкивается в 32К только файл tomahawk.sna).

_________________
:eugeek:

https://twitter.com/Shaos1973

Last edited by Shaos on 13 Oct 2013 10:45, edited 3 times in total.

13 Oct 2013 09:29

alone

Writer

Joined: 06 Sep 2007 08:05
Posts: 19
Location: 212.26.238.228

Самая большая - это не оптимальный алгоритм. Оптимальный учитывает и способ кодирования с точностью до бита. Это реально реализовано в 7zip и MegaLZ.

13 Oct 2013 09:45

Page 1 of 7

[ 95 posts ]

Go to page 1, 2, 3, 4, 5 ... 7 Next

Who is online

Users browsing this forum: No registered users and 1 guest

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum