nedoPC.org

Electronics hobbyists community established in 2002
Atom Feed | View unanswered posts | View active topics It is currently 28 Mar 2024 04:55



Reply to topic  [ 117 posts ]  Go to page Previous  1, 2, 3, 4, 5, 6 ... 8  Next
Недоархиватор SHAFF 
Author Message
Devil

Joined: 26 May 2003 06:57
Posts: 859
Reply with quote
Post 
Shaos wrote:
можно делать общее дерево 2-6-8-8-10-14, назвав его SHAFFv1h...

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

_________________
Страничка эмулятора наших компьютеров
http://bashkiria-2m.narod.ru/


21 Oct 2013 23:03
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Post 
А вот что будет если младшую ветку тоже понастраивать:

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 тут тоже повторяется :)

_________________
:dj: https://mastodon.social/@Shaos


Last edited by Shaos on 22 Oct 2013 01:13, edited 3 times in total.



22 Oct 2013 00:07
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Post 
b2m wrote:
Shaos wrote:
можно делать общее дерево 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

_________________
:dj: https://mastodon.social/@Shaos


Last edited by Shaos on 22 Oct 2013 14:03, edited 4 times in total.



22 Oct 2013 00:12
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Post 
Shaos wrote:
А вот что будет если младшую ветку тоже понастраивать:

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

_________________
:dj: https://mastodon.social/@Shaos


Last edited by Shaos on 22 Oct 2013 14:04, edited 2 times in total.



22 Oct 2013 01:19
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Post 
Shaos wrote:
Пожалуй выберу тогда 2-6-8-8-10-14:
Code:
   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 байт

_________________
:dj: https://mastodon.social/@Shaos


22 Oct 2013 06:31
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Post 
Shaos wrote:
Shaos wrote:
А вот что будет если младшую ветку тоже понастраивать:

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:
   1100xx (2)
   1101xxxxxx (6)
   11100xxxxxxx (7)
   111010xxxxxxx (7)
   111011xxxxxxxxxx (10)
   1111xxxxxxxxxxxxxx (14)

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

_________________
:dj: https://mastodon.social/@Shaos


23 Oct 2013 15:21
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Post 
Shaos wrote:
Shaos wrote:
А вот что будет если младшую ветку тоже понастраивать:

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:
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

_________________
:dj: https://mastodon.social/@Shaos


23 Oct 2013 19:03
Profile WWW
Writer

Joined: 06 Sep 2007 07:05
Posts: 19
Location: 212.26.238.228
Reply with quote
Post 
Кодирование самого длинного куска не гарантирует оптимальность. Ибо, например, вместо ссылки из 10 байт там могли быть, например, две ссылки по 7 в другие места. Вот так:

...1234567890AB...

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

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

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


23 Oct 2013 20:46
Profile
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Post 
я забыл как это называется (в курсе 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. я даже с ходу не могу придумать алгоритм как такие неоптимальности выявлять...

_________________
:dj: https://mastodon.social/@Shaos


24 Oct 2013 00:56
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Post 
Shaos wrote:
Shaos wrote:
Shaos wrote:
А вот что будет если младшую ветку тоже понастраивать:

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:
   1100xx (2)
   1101xxxxxx (6)
   11100xxxxxxx (7)
   111010xxxxxxx (7)
   111011xxxxxxxxxx (10)
   1111xxxxxxxxxxxxxx (14)

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


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

_________________
:dj: https://mastodon.social/@Shaos


24 Oct 2013 16:19
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Post 
Вобщем планирую выкатить архиватор в исходниках под GPL и "Public Domain" разархиваторы (в виде исходников без копирайта) на разных языках (C,JS,Hope,RW1) и ассемблерах (z80,8080,8086,PIC,6502,68K)

_________________
:dj: https://mastodon.social/@Shaos


27 Oct 2013 18:24
Profile WWW
Supreme God
User avatar

Joined: 21 Oct 2009 08:08
Posts: 7777
Location: Россия
Reply with quote
Post 
Shaos wrote:
По последним данным среднестатистически удачной последовательностью на моём тестовом наборе снапшотов будет...

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

_________________
iLavr


28 Oct 2013 02:55
Profile
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Post 
Я исхожу из предположения, что Z80-код не сильно разнообразен у разных авторов - поэтому выбрав программки очень старые (chess, cybotron) и очень новые (buzzsaw, bozxle) плюс добавив пару тяжеловесных игр (exolon, tomahawk) я как бы покрыл весь диапазон возможностей...

_________________
:dj: https://mastodon.social/@Shaos


28 Oct 2013 06:27
Profile WWW
Supreme God
User avatar

Joined: 21 Oct 2009 08:08
Posts: 7777
Location: Россия
Reply with quote
Post 
Shaos, я что-то неожиданно вот какой мыслью озадачился, а архиватор
может же выбрать оптимальную стратегию сжатия?
Ну, скажем, особенность метода или размер словаря?

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

_________________
iLavr


28 Mar 2014 16:18
Profile
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Post 
Ну архиваторы многие так и работают

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

_________________
:dj: https://mastodon.social/@Shaos


28 Mar 2014 17:39
Profile WWW
Display posts from previous:  Sort by  
Reply to topic   [ 117 posts ]  Go to page Previous  1, 2, 3, 4, 5, 6 ... 8  Next

Who is online

Users browsing this forum: No registered users and 25 guests


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

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software.