|
nedoPC.orgElectronics hobbyists community established in 2002 |
|
Author |
Message |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22568 Location: Silicon Valley
|
Очевидно, что откусывание большей последовательности даёт наибольшую выгоду в не зависимости от способа кодирования (кодирование одной последовательности полюбому меньше чем двух и более меньших)...
|
13 Oct 2013 09:44 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22568 Location: Silicon Valley
|
Предварительные прикидки показывают, что tomahawk.sna может после такой "постобработки" уменьшиться с 35.6К до примерно 31К, т.е. после этого он сможет влезть в 32К! Напомню, что MegaLZ сжимает его лучше - 29К, однако если пройтись по моим данным Хаффманом, то будет ещё компактнее
P.S. Альтернативный вариант постобработки - прикладывать Хаффмана не только к отдельным байтам, но и двойкам и тройкам байт, тогда создание отдельного словаря "триад" не понадобится...
|
13 Oct 2013 10:50 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22568 Location: Silicon Valley
|
Подсмотрел в LZMA хитрость интересную - один из вариантов записи ссылки использует предыдущее значение смещения - это полезно например если повторяется строка, в середине которой отличается один символ, тогда первая половина идёт со смещением, потом отдельный байт (новый символ), потом оставшаяся строка со смещением, которое использовалось ранее. Решил посмотреть может ли дать какую бы то ни было выгоду использование этого момента (0), а также -1,-2,-3,+1,+2,+3 от предыдущего смещения. Вот какая статистика по tomahawk.sna:
1st block: 0:72 (58 with small size) +1:6 +2:4 +3:4 -3:6 -2:5 -1:6
2nd block: 0:107 (97 with small size) +1:6 +2:8 +3:3 -3:4 -2:7 -1:5
3rd block: 0:89 (68 with small size) +1:5 +2:5 +3:4 -3:2 -2:4 -1:5
По сути мелочь - полкило максимум это может дать, т.е. остаёмся в ранее оговоренном русле...
|
14 Oct 2013 16:46 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22568 Location: Silicon Valley
|
Экспериментирую ещё с одним способом представления - когда работаем на уровне битов, но попроще:
- если из стрима идёт один бит 0, то со следующими 7 битами он формирует значение байта от #00 до #7F;
- если из стрима идёт два бита 1 и 0, то следующие 7 битов задают значение байта от #80 до #FF;
- если из стрима идёт два бита 1 и 1, то это является командой (аналог #FF), за которой может идти от 2 до 4 байтов, задающих смещение и размер (чуть ранее описано каким образом задающих).
Пока получается несколько компактнее, чем оригинальный "байтовый" SHAFF - пробую прогнать все экспериментальные SNA-файлы (назвать это SHAFFv1c?).
P.S. Размер на самом деле в битовом потоке можно совсем гибко сделать (т.к. меньшие размеры чаще встречаются) - от 2 до 26 битов:
Last edited by Shaos on 15 Oct 2013 00:53, edited 2 times in total.
|
14 Oct 2013 23:51 |
|
|
b2m
Devil
Joined: 26 May 2003 06:57 Posts: 860
|
Если не учитывать команды, а байты равномерно распределены между интервалами от #00 до #7F и от #80 до #FF, то на обычные байты у тебя будет примерно полтора бита лишних.
Тогда как другие архиваторы используют такой метод: сначала идёт байт, указывающий, чем будут следующие 8 элементов (по биту на каждый, 0 - байт, 1 - команда), а затем сами байты/команды.
При таком методе лишним будет лишь один бит на байт. Да и скорость распаковки на 8-ми битных компах больше, т.к. не надо возиться с битовыми потоками данных.
_________________Страничка эмулятора наших компьютеров
http://bashkiria-2m.narod.ru/
|
15 Oct 2013 00:46 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22568 Location: Silicon Valley
|
почему полтора бита? полбита
|
15 Oct 2013 00:51 |
|
|
b2m
Devil
Joined: 26 May 2003 06:57 Posts: 860
|
Согласен. Проклятая инерционность мышления
_________________Страничка эмулятора наших компьютеров
http://bashkiria-2m.narod.ru/
|
15 Oct 2013 00:58 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22568 Location: Silicon Valley
|
На самом деле вариант с байтом, задающим типы следующих восьми единиц компрессии, кажется интересным - его тоже можно прикинуть, пользуясь теми данными, что у меня уже имеются. Думаю он будет лучше чем байтовопоточный SHAFF, но хуже чем битовопоточный SHAFF (соответственно сложность декодера тоже будет промежуточная). Пока размещаю результаты по битовому потоку на предыдущей странице под наименованием SHAFFv1c, пока он побеждает всех, кроме XZ (даже MegaLZ жмёт хуже)!
P.S. В расчёты закралась ошибка - в реальности побитовое представление даёт несколько худшие результаты (хуже чем Hrust, но лучше чем MegaLZ) - поправляю данные на предыдущей странице...
P.P.S. Результаты поправил - заодно добавил короткую команду использование смещения -1 и предыдущего смещения
Last edited by Shaos on 16 Oct 2013 23:25, edited 4 times in total.
|
15 Oct 2013 06:51 |
|
|
alone
Writer
Joined: 06 Sep 2007 07:05 Posts: 19 Location: 212.26.238.228
|
В ZXRar практически не дало выигрыша.
|
15 Oct 2013 07:26 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22568 Location: Silicon Valley
|
Ну мне вроде чего-то даёт:
Выше дана инфа по двум играм для ZX-16K (jswilly16k.sna и chess16k.sna) и снапшоте памяти спектрума (zx48k1.sna) с введённой одностроковой программкой на бейсике (10 PRINT "Hello"). SHAFFv0 - байтовый поток. SHAFFv1 - битовый поток где суффикс -128 означает, что все смещения дальше -128 представляются двумя байтами, а суффикс noshorts означает отсутствие спецкодов, задающих предыдущее смещение, смещение которое было до предыдущего и смещение -1. Как видим оно даёт выгоду порядка 60-70 байтов для таких маленьких игр...
P.S. Использованные версии архиваторов:
zip - Copyright (c) 1990-2008 Info-ZIP - Zip 3.0 (July 5th 2008)
7-Zip (A) [64] 9.20 Copyright (c) 1999-2010 Igor Pavlov 2010-11-18
P.P.S. Где бы ещё 300 байтов взять? Тогда я смогу победить Hrust
P.P.P.S. 17 октября добавил сюда результаты по SHAFFv1d (см. ниже)
P.P.P.P.S. 20 октября добавил сюда результаты по SHAFFv1e (см. ниже)
P.P.P.P.P.S. 21 октября добавил сюда результаты по SHAFFv1f и чуть позже - SHAFFv1g (см. ниже)
P.P.P.P.P.P.S. 22 октября добавляю результаты по SHAFFv1h у которого статистически подобранно кодирующее дерево для дистанций...
Last edited by Shaos on 23 Oct 2013 18:59, edited 15 times in total.
|
16 Oct 2013 18:08 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22568 Location: Silicon Valley
|
Ещё один трюк - короткая команда повторения последнего обработанного байта - даёт какую-то мелочь, но приятно
P.S. Вот последний вариант побитного представления (прототип SHAFFv1d), который показывает неплохие результаты и наверное именно его я и объявлю окончательной версией 1:
P.P.S. А вот аналогичное описание версии 0 (от более раннего отличает особое отношение к короткой записи дистанции -191, которое теперь означает последнюю использованную дистанцию дальше или равную 191):
|
17 Oct 2013 16:13 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22568 Location: Silicon Valley
|
Вот формат прототипа SHAFFv1e:
Хотел было его объявить финальным, но внезапно обнаружил ещё более компактное представление у которого дерево получается более сбалансированным (на примере одного 16К блока из tomahawk.sna)...
|
20 Oct 2013 17:54 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22568 Location: Silicon Valley
|
Вот более сбалансированный формат SHAFFv1f:
|
20 Oct 2013 21:52 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22568 Location: Silicon Valley
|
Вот ещё более сбалансированный формат SHAFFv1g (как минимум tomahawk.sna должен стать меньше):
|
21 Oct 2013 14:47 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22568 Location: Silicon Valley
|
Написал программку, которая вычисляет по итогам сжатия оптимальное дерево для кодирования дистанций (правда с заморозкой размера первой и последней ветви - соответственно 2 и 14 бит):
Вот какие результаты у меня получились: Min for 'zx48k1.sna' is 2-4-6-7-6-14 Min for 'jswilly16k.sna' is 2-5-6-7-9-14 Min for 'chess16k.sna' is 2-5-7-7-8-14 Min for 'chess.sna' is 2-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 2-5-7-7-9-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:
Вот так будет выглядеть статистика 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
по сравнению с SHAFFv1g:
5 6 8 10
k1=-2
k2=-34
k3=-98
k4=-354
k5=-1378
88793 bits (11099 bytes)
7182 bits for 1
15588 bits for 2
12133 bits for 3
19740 bits for 4
17392 bits for 5
16758 bits for 6
разница - 106 байт...
P.S. Проверим к примеру exolon.sna, у которого другое оптимальное дерево:
5 7 7 9
k1=-2
k2=-34
k3=-162
k4=-290
k5=-802
77377 bits (9672 bytes)
6240 bits for 1
14589 bits for 2
14928 bits for 3
7852 bits for 4
13140 bits for 5
20628 bits for 6
для дерева 2-6-8-8-10-14 оценки будут такими:
6 8 8 10
k1=-2
k2=-66
k3=-322
k4=-578
k5=-1602
77471 bits (9683 bytes)
6240 bits for 1
21140 bits for 2
18993 bits for 3
8330 bits for 4
8080 bits for 5
14688 bits for 6
как видим потеряли только 11 байт - так что можно делать общее дерево 2-6-8-8-10-14, назвав его SHAFFv1h...
|
21 Oct 2013 21:53 |
|
|
Who is online |
Users browsing this forum: No registered users and 37 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
|
|