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

[b2m]

можно делать общее дерево 2-6-8-8-10-14, назвав его SHAFFv1h...

Может я чего-то упустил, но зачем делать одинаковое количество бит -8-8-? Какая последовательность используется, если надо 8-ми битный размер закодировать?

[Shaos]

А вот что будет если младшую ветку тоже понастраивать:

Min for 'zx48k1.sna' is 2-4-6-7-6-14
Min for 'jswilly16k.sna' is 4-6-8-8-10-14
Min for 'chess16k.sna' is 3-6-7-6-8-14
Min for 'chess.sna' is 3-6-8-8-10-14
Min for 'cybotron.sna' is 2-6-8-8-10-14
Min for 'tomahawk.sna' is 2-6-8-8-10-14
Min for 'exolon.sna' is 3-6-8-8-10-14
Min for 'buzzsaw.sna' is 2-5-7-7-8-14
Min for 'bozxle.sna' is 2-7-7-9-10-14

Как видим волшебная последовательность 2-6-8-8-10-14 тут тоже повторяется

[Shaos]

можно делать общее дерево 2-6-8-8-10-14, назвав его SHAFFv1h...

Может я чего-то упустил, но зачем делать одинаковое количество бит -8-8-? Какая последовательность используется, если надо 8-ми битный размер закодировать?

Это не для размеров, а для смещений:

1100xx (2) - три спец-кода и -1
1101xxxxxx (6) - от -2 до -65
11100xxxxxxxx (8) - от -66 до -321
111010xxxxxxxx (8) - от -322 до -577
111011xxxxxxxxxx (10) - от -578 до -1601
1111xxxxxxxxxxxxxx (14) - от -1602 до -16383

[Shaos]

А вот что будет если младшую ветку тоже понастраивать:

Min for 'zx48k1.sna' is 2-4-6-7-6-14
Min for 'jswilly16k.sna' is 4-6-8-8-10-14
Min for 'chess16k.sna' is 3-6-7-6-8-14
Min for 'chess.sna' is 3-6-8-8-10-14
Min for 'cybotron.sna' is 2-6-8-8-10-14
Min for 'tomahawk.sna' is 2-6-8-8-10-14
Min for 'exolon.sna' is 3-6-8-8-10-14
Min for 'buzzsaw.sna' is 2-5-7-7-8-14
Min for 'bozxle.sna' is 2-7-7-9-10-14

Как видим волшебная последовательность 2-6-8-8-10-14 тут тоже повторяется :)

Если предпоследнее кол-во кодирующих бит равно пред-пред-последнему, то схема вырождается в более простую: 2-6-8-10-14 (с потерей порядка 20 байтов на одном SNA-файле):

1100xx (2) - три спец-кода и -1
1101xxxxxx (6) - от -2 до -65
11100xxxxxxxx (8) - от -66 до -321
11101xxxxxxxxxx (10) - от -322 до -1345
1111xxxxxxxxxxxxxx (14) - от -1346 до -16383

[Shaos]

Пожалуй выберу тогда 2-6-8-8-10-14:

Code: Select all

   1100xx (2)
   1101xxxxxx (6)
   11100xxxxxxxx (8)
   111010xxxxxxxx (8)
   111011xxxxxxxxxx (10)
   1111xxxxxxxxxxxxxx (14)

Вот так будет выглядеть статистика tomahawk.sna:

6 8 8 10
k1=-2
k2=-66
k3=-322
k4=-578
k5=-1602
87950 bits (10993 bytes)
7182 bits for 1
24980 bits for 2
21528 bits for 3
7896 bits for 4
11568 bits for 5
14796 bits for 6

tomahawk.sna сжался до 29570 байт

[Shaos]

А вот что будет если младшую ветку тоже понастраивать:

Min for 'zx48k1.sna' is 2-4-6-7-6-14
Min for 'jswilly16k.sna' is 4-6-8-8-10-14
Min for 'chess16k.sna' is 3-6-7-6-8-14
Min for 'chess.sna' is 3-6-8-8-10-14
Min for 'cybotron.sna' is 2-6-8-8-10-14
Min for 'tomahawk.sna' is 2-6-8-8-10-14
Min for 'exolon.sna' is 3-6-8-8-10-14
Min for 'buzzsaw.sna' is 2-5-7-7-8-14
Min for 'bozxle.sna' is 2-7-7-9-10-14

Как видим волшебная последовательность 2-6-8-8-10-14 тут тоже повторяется :)

Если предпоследнее кол-во кодирующих бит равно пред-пред-последнему, то схема вырождается в более простую: 2-6-8-10-14 (с потерей порядка 20 байтов на одном SNA-файле):

1100xx (2) - три спец-кода и -1
1101xxxxxx (6) - от -2 до -65
11100xxxxxxxx (8) - от -66 до -321
11101xxxxxxxxxx (10) - от -322 до -1345
1111xxxxxxxxxxxxxx (14) - от -1346 до -16383

По последним данным среднестатистически удачной последовательностью на моём тестовом наборе снапшотов будет 2-6-7-7-10-14:

Code: Select all

   1100xx (2)
   1101xxxxxx (6)
   11100xxxxxxx (7)
   111010xxxxxxx (7)
   111011xxxxxxxxxx (10)
   1111xxxxxxxxxxxxxx (14) 

Можно ещё переносить самую частую дистанцию наверх вместо -1 (которая не всегда самая частая) - вопрос лишь в том стоит ли копья ломать ради выгоды в несколько байт?...

[Shaos]

А вот что будет если младшую ветку тоже понастраивать:

Min for 'zx48k1.sna' is 2-4-6-7-6-14
Min for 'jswilly16k.sna' is 4-6-8-8-10-14
Min for 'chess16k.sna' is 3-6-7-6-8-14
Min for 'chess.sna' is 3-6-8-8-10-14
Min for 'cybotron.sna' is 2-6-8-8-10-14
Min for 'tomahawk.sna' is 2-6-8-8-10-14
Min for 'exolon.sna' is 3-6-8-8-10-14
Min for 'buzzsaw.sna' is 2-5-7-7-8-14
Min for 'bozxle.sna' is 2-7-7-9-10-14

Как видим волшебная последовательность 2-6-8-8-10-14 тут тоже повторяется :)

Если предпоследнее кол-во кодирующих бит равно пред-пред-последнему, то схема вырождается в более простую: 2-6-8-10-14 (с потерей порядка 20 байтов на одном SNA-файле):

1100xx (2) - три спец-кода и -1
1101xxxxxx (6) - от -2 до -65
11100xxxxxxxx (8) - от -66 до -321
11101xxxxxxxxxx (10) - от -322 до -1345
1111xxxxxxxxxxxxxx (14) - от -1346 до -16383

Вот наверное финальный вариант формата данных SHAFF0/1 (SHAFF1 формат соответствует результатам с пометкой SHAFFv1h):

Code: Select all

SHAFF header:

Bytes 0...5 - signature and version ("SHAFF0" or "SHAFF1")
Bytes 6,7 - offset to 1st block of data (big-endian)
Bytes 8,9 - number of 16K blocks (big-endian)
Bytes 10,11 - length of the last block (less or equal to 16384)
Then optional uncompressed data - for SNA format it is
Bytes 12...14 "SNA" - signature to identify SNA header
Bytes 15...41 - SNA 27-byte header itself

SHAFF0 data format:

XX - any byte other than #FF is a single data byte
#FF #00 - single byte #FF
#FF 0xxxxxxx size (distance -1...-127)
#FF 10xxxxxx size (distance -128...-191, but -191 means last distance longer or equal to -191)
#FF 11xxxxxx xxxxxxxx size (distance up to -16383)
special case without size:
#FF #C0 #00 - end of block (instead of distance -16384)

size 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 size after that)
110001 size (repeat last distance longer than -1 and not equal to previous)
110010 size (repeat previous last distance longer than -1)
110011 size (distance -1)
1101xxxxxx size (distance from -2 to -65)
11100xxxxxxxx size (distance from -66 to -321)
11101xxxxxxxxxx size (distance from -322 to -1345)
1111xxxxxxxxxxxxxx size (distance up to -16383)
special case without size:
111100000000000000 - end of block (instead of distance -16384)

size is a sequence of 2...26 bits:
0x - for 2 and 3
10xx - for 4, 5, 6, 7
110xxx - for 8...15
1110xxxx - for 16...31
11110xxxxx - for 32...63
111110xxxxxx - for 64...127
1111110xxxxxxx - for 128...254
11111110xxxxxxxx - for 255...511
111111110xxxxxxxxx - for 512...1023
1111111110xxxxxxxxxx - for 1024...2047
11111111110xxxxxxxxxxx - for 2048...4095
111111111110xxxxxxxxxxxx - for 4096...8191
1111111111110xxxxxxxxxxxxx - for 8192...16383

[alone]

Кодирование самого длинного куска не гарантирует оптимальность. Ибо, например, вместо ссылки из 10 байт там могли быть, например, две ссылки по 7 в другие места. Вот так:

...1234567890AB...

Ты кодируешь
..."1""2"<ссылка>"A""B"...

А могло быть
...<ссылка><ссылка>...

Для Хаффманов ситуация может быть ещё интереснее: код ссылки из 10 байт может использоваться только в одном месте файла и будет впустую занимать коды в дереве, так что выгоднее будет закодировать 9 + литерал. Это тоже учитывает "оптимальный LZH" в 7zip за счёт настраиваемого количества проходов.

[Shaos]

я забыл как это называется (в курсе AI проходили поиск кратчайшего пути на графе), но чтобы таких ситуаций не возникало, надо выбирать такие метрики, чтобы два раза по 7 не было короче чем один раз по 10, хотя - скажем если ссылка на 10 смотрит далеко (дальше чем -1346), а две ссылки на 7 смотрят близко (до -65), тогда ссылка на 10 будет выглядеть как 1111xxxxxxxxxxxxxx 110010 (18+6=24 бита) плюс 4 отдельно стоящих символа - в среднем 34 бита, т.е. всего 58, а две коротких ссылки по 7 будут 1101xxxxxx 1011 (10+4=14 битов) - или 28 за две, т.е. таки да - две ссылки будут длиннее, чем одна, но наличие отдельно стоящих байтов в случае одной ссылки усугубляют картину - с другой стороны такие ситуации не должны возникать часто...

P.S. я даже с ходу не могу придумать алгоритм как такие неоптимальности выявлять...

[Shaos]

А вот что будет если младшую ветку тоже понастраивать:

Min for 'zx48k1.sna' is 2-4-6-7-6-14
Min for 'jswilly16k.sna' is 4-6-8-8-10-14
Min for 'chess16k.sna' is 3-6-7-6-8-14
Min for 'chess.sna' is 3-6-8-8-10-14
Min for 'cybotron.sna' is 2-6-8-8-10-14
Min for 'tomahawk.sna' is 2-6-8-8-10-14
Min for 'exolon.sna' is 3-6-8-8-10-14
Min for 'buzzsaw.sna' is 2-5-7-7-8-14
Min for 'bozxle.sna' is 2-7-7-9-10-14

Как видим волшебная последовательность 2-6-8-8-10-14 тут тоже повторяется :)

Если предпоследнее кол-во кодирующих бит равно пред-пред-последнему, то схема вырождается в более простую: 2-6-8-10-14 (с потерей порядка 20 байтов на одном SNA-файле):

1100xx (2) - три спец-кода и -1
1101xxxxxx (6) - от -2 до -65
11100xxxxxxxx (8) - от -66 до -321
11101xxxxxxxxxx (10) - от -322 до -1345
1111xxxxxxxxxxxxxx (14) - от -1346 до -16383

По последним данным среднестатистически удачной последовательностью на моём тестовом наборе снапшотов будет 2-6-7-7-10-14:

Code: Select all

   1100xx (2)
   1101xxxxxx (6)
   11100xxxxxxx (7)
   111010xxxxxxx (7)
   111011xxxxxxxxxx (10)
   1111xxxxxxxxxxxxxx (14) 

Можно ещё переносить самую частую дистанцию наверх вместо -1 (которая не всегда самая частая) - вопрос лишь в том стоит ли копья ломать ради выгоды в несколько байт?...

Решил было попробовать новый алгоритм SHAFFv1i со схемой 2-6-7-7-10-14 и заменой -1 на самую частую дистанцию, но сравнив с SHAFFv1h (числа это размер сжатых данных без учёта отдельных байтов):

Code: Select all

Filename       Most  Adaptive optimal         SHAFFv1i*      SHAFFv1i      SHAFFv1h
                                            2-6-7-7-10-14  2-6-7-7-10-14  2-6-8-10-14
zx48.sna       -256  2-4-4-5-8-14  -> 139      147 (+8)      152 (+5)      152 (0)
zx48k1.sna     -1    2-4-6-7-6-14  -> 156      162 (+6)      162 (0)       163 (+1)
jswilly16k.sna -4    2-5-6-7-9-14  -> 2360    2372 (+12)    2384 (+12)    2394 (+10)
chess16k.sna   -256  2-5-6-6-7-14  -> 1262    1275 (+13)    1291 (+16)    1298 (+7)
chess.sna      -1    2-5-7-7-10-14 -> 3199    3200 (+1)     3200 (0)      3206 (+6)
cybotron.sna   -1    2-5-7-7-9-14  -> 1947    1952 (+5)     1952 (0)      1951 (-1)
tomahawk.sna   -256  2-6-8-9-10-14 -> 10533  10537 (+4)    10610 (+73)   10616 (+6)
exolon.sna     -3    2-5-7-7-9-14  -> 9072    9089 (+17)    9093 (+4)     9125 (+32)
buzzsaw.sna    -32   2-5-5-6-8-14  -> 6444    6478 (+34)    6607 (+129)   6647 (+40)
bozxle.sna     -256  2-6-7-7-10-14 -> 6766    6766 (0)      6913 (+147)   6966 (+53)

a.scr          -256  2-6-8-9-10-14 -> 917      923 (+6)     1004 (+81)     999 (-5)
b.scr          -256  2-7-8-7-10-14 -> 1670    1696 (+26)    1744 (+48)    1734 (-10)
c.scr          -1    2-6-8-7-6-14  -> 514      535 (+21)     535 (0)       529 (-6)

* with most frequently used distance instead of -1

решил не заморачиваться - без замены -1 на самое частое выгоды практически нет (а иногда и вообще ущерб), а с заменой -1 на -256 или другую часто попадающуюся дистанцию повышается сложность архиватора и разархиватора, так что наверное остановлюсь на SHAFFv1h...

P.S. У меня ещё есть много мест для оптимизации т.к. сжимает SHAFFv1h оооочень долго :)

Code: Select all

zx48.sna        2 min
zx48k1.sna      2 min
jswilly16k.sna 35 min
chess16k.sna   21 min
chess.sna      47 min
cybotron.sna   28 min
tomahawk.sna  158 min  
exolon.sna    141 min  
buzzsaw.sna    93 min
bozxle.sna    102 min

Замеры делались на Intel Core Duo 2008 года...

[Shaos]

Вобщем планирую выкатить архиватор в исходниках под GPL и "Public Domain" разархиваторы (в виде исходников без копирайта) на разных языках (C,JS,Hope,RW1) и ассемблерах (z80,8080,8086,PIC,6502,68K)

[Lavr]

По последним данным среднестатистически удачной последовательностью на моём тестовом наборе снапшотов будет...

А ты сам-то как считаешь, такого количества "подопытных" достаточно для статистических оценок?
Может стОит разочек "прогнать" тесты на совершенно другом наборе?

[Shaos]

Я исхожу из предположения, что Z80-код не сильно разнообразен у разных авторов - поэтому выбрав программки очень старые (chess, cybotron) и очень новые (buzzsaw, bozxle) плюс добавив пару тяжеловесных игр (exolon, tomahawk) я как бы покрыл весь диапазон возможностей...

[Lavr]

Shaos, я что-то неожиданно вот какой мыслью озадачился, а архиватор
может же выбрать оптимальную стратегию сжатия?
Ну, скажем, особенность метода или размер словаря?

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

[Shaos]

Ну архиваторы многие так и работают

P.S. Чего-то замотался я и окончательную сжимающе-разжимающую версию так и не выкатил - там осталось буквально на вечер-два работы...