Author |
Message |
b2m
Devil
Joined: 26 May 2003 06:57 Posts: 870
|
Может я чего-то упустил, но зачем делать одинаковое количество бит -8-8-? Какая последовательность используется, если надо 8-ми битный размер закодировать?
_________________Страничка эмулятора наших компьютеров
http://bashkiria-2m.narod.ru/
|
21 Oct 2013 23:03 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22730 Location: Silicon Valley
|
А вот что будет если младшую ветку тоже понастраивать:
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 тут тоже повторяется
Last edited by Shaos on 22 Oct 2013 01:13, edited 3 times in total.
|
22 Oct 2013 00:07 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22730 Location: Silicon Valley
|
Это не для размеров, а для смещений:
1100xx (2) - три спец-кода и -1
1101xxxxxx (6) - от -2 до -65
11100xxxxxxxx (8) - от -66 до -321
111010xxxxxxxx (8) - от -322 до -577
111011xxxxxxxxxx (10) - от -578 до -1601
1111xxxxxxxxxxxxxx (14) - от -1602 до -16383
Last edited by Shaos on 22 Oct 2013 14:03, edited 4 times in total.
|
22 Oct 2013 00:12 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22730 Location: Silicon Valley
|
Если предпоследнее кол-во кодирующих бит равно пред-пред-последнему, то схема вырождается в более простую: 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
Last edited by Shaos on 22 Oct 2013 14:04, edited 2 times in total.
|
22 Oct 2013 01:19 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22730 Location: Silicon Valley
|
| | | | Shaos wrote: Пожалуй выберу тогда 2-6-8-8-10-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 байт
|
22 Oct 2013 06:31 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22730 Location: Silicon Valley
|
| | | | Shaos wrote: Если предпоследнее кол-во кодирующих бит равно пред-пред-последнему, то схема вырождается в более простую: 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:
Можно ещё переносить самую частую дистанцию наверх вместо -1 (которая не всегда самая частая) - вопрос лишь в том стоит ли копья ломать ради выгоды в несколько байт?...
|
23 Oct 2013 15:21 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22730 Location: Silicon Valley
|
| | | | Shaos wrote: Если предпоследнее кол-во кодирующих бит равно пред-пред-последнему, то схема вырождается в более простую: 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):
|
23 Oct 2013 19:03 |
|
|
alone
Writer
Joined: 06 Sep 2007 07:05 Posts: 19 Location: 212.26.238.228
|
Кодирование самого длинного куска не гарантирует оптимальность. Ибо, например, вместо ссылки из 10 байт там могли быть, например, две ссылки по 7 в другие места. Вот так:
...1234567890AB...
Ты кодируешь
..."1""2"<ссылка>"A""B"...
А могло быть
...<ссылка><ссылка>...
Для Хаффманов ситуация может быть ещё интереснее: код ссылки из 10 байт может использоваться только в одном месте файла и будет впустую занимать коды в дереве, так что выгоднее будет закодировать 9 + литерал. Это тоже учитывает "оптимальный LZH" в 7zip за счёт настраиваемого количества проходов.
|
23 Oct 2013 20:46 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22730 Location: Silicon Valley
|
я забыл как это называется (в курсе 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. я даже с ходу не могу придумать алгоритм как такие неоптимальности выявлять...
|
24 Oct 2013 00:56 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22730 Location: Silicon Valley
|
Решил было попробовать новый алгоритм SHAFFv1i со схемой 2-6-7-7-10-14 и заменой -1 на самую частую дистанцию, но сравнив с SHAFFv1h (числа это размер сжатых данных без учёта отдельных байтов): решил не заморачиваться - без замены -1 на самое частое выгоды практически нет (а иногда и вообще ущерб), а с заменой -1 на -256 или другую часто попадающуюся дистанцию повышается сложность архиватора и разархиватора, так что наверное остановлюсь на SHAFFv1h... P.S. У меня ещё есть много мест для оптимизации т.к. сжимает SHAFFv1h оооочень долго :)
Замеры делались на Intel Core Duo 2008 года...
|
24 Oct 2013 16:19 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22730 Location: Silicon Valley
|
Вобщем планирую выкатить архиватор в исходниках под GPL и "Public Domain" разархиваторы (в виде исходников без копирайта) на разных языках (C,JS,Hope,RW1) и ассемблерах (z80,8080,8086,PIC,6502,68K)
|
27 Oct 2013 18:24 |
|
|
Lavr
Supreme God
Joined: 21 Oct 2009 08:08 Posts: 7777 Location: Россия
|
А ты сам-то как считаешь, такого количества "подопытных" достаточно для статистических оценок?
Может стОит разочек "прогнать" тесты на совершенно другом наборе?
_________________ iLavr
|
28 Oct 2013 02:55 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22730 Location: Silicon Valley
|
Я исхожу из предположения, что Z80-код не сильно разнообразен у разных авторов - поэтому выбрав программки очень старые (chess, cybotron) и очень новые (buzzsaw, bozxle) плюс добавив пару тяжеловесных игр (exolon, tomahawk) я как бы покрыл весь диапазон возможностей...
|
28 Oct 2013 06:27 |
|
|
Lavr
Supreme God
Joined: 21 Oct 2009 08:08 Posts: 7777 Location: Россия
|
Shaos, я что-то неожиданно вот какой мыслью озадачился, а архиватор
может же выбрать оптимальную стратегию сжатия?
Ну, скажем, особенность метода или размер словаря?
Поскольку от архиватора не требуется сжимать быстро, то, возможно, он
может осуществить прикидку несколькими методами, не сжимая реально,
а потом сжать наиболее эффективным.
Разархиватор же обычно узнает метод сжатия их самогО файла.
_________________ iLavr
|
28 Mar 2014 16:18 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22730 Location: Silicon Valley
|
Ну архиваторы многие так и работают
P.S. Чего-то замотался я и окончательную сжимающе-разжимающую версию так и не выкатил - там осталось буквально на вечер-два работы...
|
28 Mar 2014 17:39 |
|
|