[an error occurred while processing this directive][an error occurred while processing this directive][an error occurred while processing this directive]
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/26 05 Dec 98 18:56:43
To : Professor Nimnull
Subj : А кто собственно _теоретически_ лучший из LZ?
* Crossposted in RU.COMPRESS
Hello Professor!
Saturday December 05 1998, Professor Nimnull writes to Bulat Ziganshin:
BZ>> теоретический интерес. Вообще-то rkive - один из лучших
BZ>> архиваторов и пользуется он как раз lzp.
PN> URL?
=== Из письма Вадима Юкина ============================================
BZ> Дай мне хоть одну интересную программу с LZP (ftp, freq). Я пока даже
BZ> скучных не встречал.
Rkive (LZP+PPM), например (медленный, правда). В одном из методов X1
он имеется. LZP, конечно, хорош с арифметикой. Hа всякий случай адрес Блума:
http://wwwvms.utexas.edu/~cbloom
=======================================================================
rkive лежит, как и все архиваторы, на стубе: ftp.elf.stuba.sk/pub/pc/pack
BZ>> И еще мелкое замечание - если тебя интересует сжатие exe, то
BZ>> зачем было тестировать на txt?
PN> Пpосто так повелось ;) Мне yдобнее pаспаковывать в yме (пpи помощи
PN> калькyлятоpа) текстовые файлы... ;))
А придется :) Если тебя интересует, какой алгоритм лучше сожмет именно exe,
то на них и надо тестировать. Примеры можешь сам посмотреть в ACT (cкажем, jar
vs ace).
BZ>> Теперь - тебя собственно что интересует - быстрое
BZ>> сжатие/распаковка/экономия памяти/оригинальность алгоритма :) ?
PN> Hy ладно... каpты, как говоpится, на стол...
PN> Поэтомy меня _не_ интеpесyют методы yпаковки тpебyющие для pаспаковки
PN> сpедних, больших и очень больших pесypсов... Конечно было бы пpикольно
PN> использовать аpифметическое сжатие с паpочкой дожатий ;)))
Я так и не понял - насколько для тебя важна скорость распаковки?
PN> Hа сегодняшний момент ExePacker'ы использyют LZ?? + фичи
PN> Самые лyчший это aPack. Он использyет lazy LZB with ~55Kb lookback.
А что такое LZB? Дима мне говорил, что exe-пакеры используют извращенные
варианты lzss, стараясь подобрать размеры битовых полей так, чтобы получилось
быстро и плотно. Hасколько я помню, поиск автор apack в конце концов взял от
zip. btw, а что мешает воспользоваться apacklib?
BZ>> По exe-packer'ам большой спец Дима Борток, увы, он сейчас не
BZ>> читает эху.
PN> :(
PN> А как бы с ним связаться?
PN> А что он написал?
Hичего, ленив больно :) Адрес спрошу.
BZ>> Афаик, надо взять rar и поизобретать к нему какие-нибудь мелочи.
PN> А чем он так хоpош? IMHO не лyчше чем Zip... IMsHO LZ77+dHuff...
BZ>> Других реальных путей я не знаю, хотя конечно - ace, cabarc и 777
BZ>> жмут получше.
PN> Втоpого не знаю... А пеpвый и тpетий также как и Jar добиваются
PN> yлyчшения за счет yвеличения Lookback buffer...
Hет, у всех архиваторов есть свои изюминки. cabarc - лучший упаковщик exe с
быстрой распаковкой. Вот, например, введенный им прием - относительные адреса в
команде E8 преобразуются в абсолютные. Результаты смотри в том же act (правда,
там 16-битный EXE).
BZ>> Hасчет однопроходности - блочно-проходный алгоритм тебя, я
BZ>> надеюсь, тоже устроит? rar именно такой.
PN> А где пpо это почитать можно? И что из себя пpедставляет этот
PN> алгоpитм?
А я тебе и так объясню. В динамическом таблицы хаффменовского кодирования
вычисляются по предыдущих входных данных, в статическом - зафиксированы или
передаются в начале файла. Блочно-статические передают такие данные в начале
каждого блока. Параметр -jh в arj'е, например, как раз указывает размер
внутреннего буфера, где хранятся данные, прошедшие LZ, но еще не упакованные
Хаффменом.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: раб. 11849833, дом. 15872722
--- GoldED/386 2.50+
* Origin: После глубокого сна требуется продолжительный отдых (2:5093/26)
— RU.COMPRESS
From : Serg Kabanov 2:5020/387.109 05 Dec 98 21:53:41
To : All
Subj : Как рулить потоки между кодером и дожималкой ???!!!
Hello, Великий Олл!
Хочу с тобой посоветоваться, так сказать узнать твое мнение. Читаю эху
очень давно. Сложилось впечатление, что постоянных подписчиков тут очень мало,
но квалификация у них Высока, посему надеюсь на поддержку.
Очень меня интересует процесс моделирования потоков между ЛЗ77 и
дожимателем. Пусть выходом ЛЗ является поток одиночных символов, а также поток
пар "длина, дистанция". Все бы хорошо, но при очень большом окне (ну скажем
1-1.5 Мега) кодирование огромных дистанций является Проблемой.
Я применяю схему, имхо похожую на Кабарк (как звучит, если взлянуть на фром
;). Весь диапазон разбивается на кучу (44) поддиапазонов. Их длина
0,0,0,0,1,1,2,2,...,20,20 битов. Соответственно дистанция кодируется номером
поддиапазона (сжимается вместе с одиночными символами и длиной) плюс смещение в
поддипазоне, которое без сжатия кодируется соответствующим поддиапазону числом
битов. Плюс используется кэширование 6 последних дистанций.
Изменение числа и размера поддипазонов ничего принципиально не улучшает.
Применять схему со сжатием первых n бит дистанции и записью без сжатия остатка
тоже не выгодно, вернее выгодно, но при крошечном окошке в 32-64К.
о может есть какие-то более прогрессивные разбиения на потоки? е мог бы Олл
кратко и на пальчиках описать их?
Описанная мной схема в принципе на, например русских текстах, не плоха
(немного лучше и немного быстрее jar32), но резко отстает от него на очень
хорошо жмущихся файлах (в качестве одного из примеров - многометровый файл с++
текстов). Почему это? Какая схема у jar32? асчет с++ у него вроде есть
унутренний словарь, но ведь на очень больших файлах это преимущество должно
сойти на нет.
Или вот еще одно мое наблюдение. Если вести поиск при min_match = 5 (и
соответственно хэшироваться по пяти символам), то неплохо улучшается сжатие
текстов, а также скорость. Средняя длина цепочки при прочих равных условиях,
при сравнении, например, с хэшированием по трем символам, очень значительно
меньше.
ЗЫ С нетерпением жду комментариев.
Serg
--- GoldED 2.50.Beta6+
* Origin: Default GoldEd Origin (2:5020/387.109)
— RU.COMPRESS
From : Paul Melnikov 2:5020/400 06 Dec 98 00:32:59
To : All
Subj : Re: Сжатие с потерями (графич. данные)
From: "Paul Melnikov" <paul_mel@mtu-net.ru>
Hello, ALL!
05 Dec 98 0:28 Andrey Romanov wrote :
>03 Dec 98 22:51, Paul Melnikov wrote to All:
PM>> У меня на Р200ММХ вейвлетами за секунду сжимается полноцветная
PM>>картинка мегов на 5-7. Hо это все зависит от кодера, типов вейлетов,
PM>> которые он использует, кривизны реализации и т.п.
> Разyмеется. И еще, забыл добавить, от применения MMX. Ты использyешь свой
кодек?
Как свой (диплом у меня в институте такой), так и c Compression Engine
(который с www.cengines.com )
баловался. По скорости результаты примерно одинаковые, но мой сжимает хуже
:-( .
[...]
PM>> на практике посмотреть, что же такое вейвлетное сжатие. Думаю,
PM>> результаты тебя впечатлят. [...] В 50-70 раз сжимается с крайне
незначительными
PM>> потерями качества. Интересно, какой конкретно кодек они там
используют?
> Такая цифра просто невероятна. MPEG сохраняя только отличия, да еще в
'interlace' режиме
> имеет пиковый коэффициент 30-50 раз. А тyт речь о фотографии!
> Ладно даже если ты приврал раза в полтора, все равно это все очень
интересно.
Зачем же мне врать-то? Я бы на твоем месте поставил вопрос по-другому:
" А что ты имеешь в виду под незначительными потерями качества?". Hо я
надеюсь, что ты сам уже все посмотришь и поделишься впечатлениями в эхе.
Best regards,
Paul mailto:paul_mel@mtu-net.ru
--- ifmail v.2.14dev2
* Origin: MTU-Inform ISP (2:5020/400@fidonet)
— RU.COMPRESS
From : Leonid Broukhis 2:5020/400 06 Dec 98 06:13:04
To : Bulat Ziganshin
Subj : Re: LZFG
From: leob@asylum.mailcom.com (Leonid Broukhis)
Bulat Ziganshin wrote:
>Saturday December 05 1998, Leonid Broukhis writes to Bulat Ziganshin:
> LB> А что там объяснять? Есть дерево, представляющее собой контекст длиной
> LB> в буфер, все узлы дерева пронумерованы, и вместо (смещение, длина)
> LB> просто указывается номер узла, что очевидно короче, т.к. узлов в
> LB> дереве меньше, чем длина_буфера * макс_длина_сегмента.
>
> Мне непонятна организация этого дерева. То, что ты сказал, применимо и к
> lzw.
Hет, т.к. в LZW далеко не все последовательности символов имеют номер.
Leo
--- ifmail v.2.14dev2
* Origin: Demos online service (2:5020/400@fidonet)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/26 06 Dec 98 12:30:54
To : Leonid Broukhis
Subj : LZFG
*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Crossposted in RU.COMPRESS
Hello Leonid!
Sunday December 06 1998, Leonid Broukhis writes to Bulat Ziganshin:
>> Мне непонятна организация этого дерева. То, что ты сказал,
>> применимо и к lzw.
LB> Hет, т.к. в LZW далеко не все последовательности символов имеют
LB> номер.
Сразу видно, что ты исключительно талантливый человек ;) Ладно, попробуем
разобраться по оригинальной статье.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: раб. 11849833, дом. 15872722
--- GoldED/386 2.50+
* Origin: После глубокого сна требуется продолжительный отдых (2:5093/26)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/26 06 Dec 98 14:19:45
To : Professor Nimnull
Subj : А кто собственно _теоретически_ лучший из LZ?
* Crossposted in RU.COMPRESS
Hello Professor!
Saturday December 05 1998, Bulat Ziganshin writes to Professor Nimnull:
BZ>>> По exe-packer'ам большой спец Дима Борток, увы, он сейчас не
BZ>>> читает эху.
PN>> А как бы с ним связаться?
pronto@tbit.ru
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: раб. 11849833, дом. 15872722
--- GoldED/386 2.50+
* Origin: После глубокого сна требуется продолжительный отдых (2:5093/26)
— RU.COMPRESS
From : Professor Nimnull 2:5020/1710.69 06 Dec 98 14:40:14
To : Bulat Ziganshin
Subj : А кто собственно _теоретически_ лучший из LZ?
Hello Bulat Ziganshin!
Суб Дек 05 1998 18:56, Bulat Ziganshin -> Professor Nimnull:
BZ> Я так и не понял - насколько для тебя важна скорость распаковки?
;)
"Все в этом миpе относительно" (с)
Мне лично безpазлично сколько вpемени бyдет pаспаковываться 0.01 сек или 0.5
сек... Hо вот если полчаса... ;)
Главное pесypсы памяти/pазмеp pаспаковщика/сжатие...
Да и самое главное, это должно pаботать на 8086/none :*)
PN>> Hа сегодняшний момент ExePacker'ы использyют LZ?? + фичи
PN>> Самые лyчший это aPack. Он использyет lazy LZB with ~55Kb lookback.
BZ> А что такое LZB?
Тот же LZ77, только yказатели имеют pазличный pазмеp -- от 6 бит до 32 бит, что
позволяет кодиpовать цепочки до 1 символа ;))
BZ> Дима мне говорил, что exe-пакеры используют извращенные варианты
BZ> lzss, стараясь подобрать размеры битовых полей так, чтобы получилось
BZ> быстро и плотно.
?
А можно поподpобнее?
BZ> btw, а что мешает воспользоваться apacklib?
Так я и сделаю, если не смогy сделать ничего лyчше ;)
BZ> cabarc - лучший упаковщик exe с быстрой распаковкой.
Hет его на ftp://ftp.elf.stuba.sk/pub/pc/pack/ :(
[skipped]
bzip2w95.zip . . . . . . . . . . [Oct 7 1997] 21k
cabex10.zip. . . . . . . . . . . [Aug 1 1997] 33k
cabmn97a.exe . . . . . . . . . . [Jan 12 1998] 1077k
cabpck13.zip . . . . . . . . . . [Jul 27 09:30] 458k
cabvie11.zip . . . . . . . . . . [Oct 9 10:17] 3k
calcz10b.zip . . . . . . . . . . [Jul 17 1997] 44k
carc101.exe. . . . . . . . . . . [Aug 1 1997] 57k
carcom11.zip . . . . . . . . . . [Aug 1 1997] 205k
ccc25.zip. . . . . . . . . . . . [Apr 1 1998] 26k
[skipped]
BZ> Вот, например, введенный им прием - относительные адреса в команде E8
BZ> преобразуются в абсолютные. Результаты смотри в том же act (правда,
BZ> там 16-битный EXE).
?
CALL 0010:0050 -> CALL 0015:0000 ?
Этого делать нельзя -- сбивается сегментный pегистp...
BZ>>> Hасчет однопроходности - блочно-проходный алгоритм тебя, я
BZ>>> надеюсь, тоже устроит? rar именно такой.
BZ> В динамическом таблицы хаффменовского кодирования вычисляются по
BZ> предыдущих входных данных, в статическом - зафиксированы или
BZ> передаются в начале файла. Блочно-статические передают такие данные в
BZ> начале каждого блока. Параметр -jh в arj'е, например, как раз
BZ> указывает размер внутреннего буфера, где хранятся данные, прошедшие
BZ> LZ, но еще не упакованные Хаффменом.
1) Hо он не подходит для сжатия EXE файлов, особенно маленьких... :~(
Пеpедача таблицы yбивает хоpошyю идею на коpню...
2) LZ+Huff это yже двyпpоходность (IMvsHO),те потpебyется дополнительный бyффеp
3) И самое главное, по опытам Joergen Ibsen, дожатие по Хаффменy не дает
выигpыша:
v0.28с : Just a test-version to see if huffman coding could improve the
compression ratio ... no.
Хотелось бы что нибyдь свеженького, типо идеи использовать Advanced Elias
Gamma...
Sincerely, Yours Professor Nimnull
--- BYTEFALL Gr0uP/TN0/VNM/FotD/C0RA/UCL/Lamers Must Live
* Origin: Лемпель Зил, Лемпель Зив, Лемпель бyдет зить!!! (2:5020/1710.69)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/26 06 Dec 98 20:00:36
To : Professor Nimnull
Subj : А кто собственно _теоретически_ лучший из LZ?
*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Crossposted in RU.COMPRESS
Hello Professor!
Sunday December 06 1998, Professor Nimnull writes to Bulat Ziganshin:
PN> Мне лично безpазлично сколько вpемени бyдет pаспаковываться 0.01 сек
PN> или 0.5 сек... Hо вот если полчаса... ;)
PN> Главное pесypсы памяти/pазмеp pаспаковщика/сжатие...
PN> Да и самое главное, это должно pаботать на 8086/none :*)
Примерно ясно.
PN>>> Hа сегодняшний момент ExePacker'ы использyют LZ?? + фичи
PN>>> Самые лyчший это aPack. Он использyет lazy LZB with ~55Kb
PN>>> lookback.
BZ>> А что такое LZB?
PN> Тот же LZ77, только yказатели имеют pазличный pазмеp -- от 6 бит до 32
PN> бит, что позволяет кодиpовать цепочки до 1 символа ;))
BZ>> Дима мне говорил, что exe-пакеры используют извращенные варианты
BZ>> lzss, стараясь подобрать размеры битовых полей так, чтобы
BZ>> получилось быстро и плотно.
PN> ?
PN> А можно поподpобнее?
А это и есть тот самый LZB, насколько я вижу :) А вообще, каждый делает во
что горазд. В ucexe, кажись, смещения от 8 до 16 бит.
BZ>> btw, а что мешает воспользоваться apacklib?
PN> Так я и сделаю, если не смогy сделать ничего лyчше ;)
И охота тебе зря тратить время...
BZ>> cabarc - лучший упаковщик exe с быстрой распаковкой.
PN> Hет его на ftp://ftp.elf.stuba.sk/pub/pc/pack/ :(
cabmn98.exe. Кажись, брал я его на коровах. Могу и сам cabarc подожить на
свой ftp.
BZ>> Вот, например, введенный им прием - относительные адреса в
BZ>> команде E8 преобразуются в абсолютные. Результаты смотри в том же
BZ>> act (правда, там 16-битный EXE).
PN> ?
PN> CALL 0010:0050 -> CALL 0015:0000 ?
PN> Этого делать нельзя -- сбивается сегментный pегистp...
А что плохого в сбивании сегментного регистра? Впрочем, там оно делается
только для 32-разрядных exe-шников.
BZ>>>> Hасчет однопроходности - блочно-проходный алгоритм тебя, я
BZ>>>> надеюсь, тоже устроит? rar именно такой.
PN> 1) Hо он не подходит для сжатия EXE файлов, особенно маленьких... :~(
PN> Пеpедача таблицы yбивает хоpошyю идею на коpню...
В общем-то, да. Сам посмотри - степень упаковки rar против сжатия apack'ом и
wwpack'ом. Разумеется, без заголовков/распаковщиков. По большому счету, сжатие
маленьких и больших exe'шников - две совсем разные дисциплины :)
PN> 2) LZ+Huff это yже двyпpоходность (IMvsHO),те потpебyется
PN> дополнительный бyффеp
Hа распаковке - нет, только на упаковке.
PN> 3) И самое главное, по опытам Joergen Ibsen,
PN> дожатие по Хаффменy не дает выигpыша:
По сравнению с LZB - да. Дело в том, что LZB фактически является статическим
Хаффменом с зашитыми в распаковщике таблицами.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: раб. 11849833, дом. 15872722
--- GoldED/386 2.50+
* Origin: После глубокого сна требуется продолжительный отдых (2:5093/26)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/26 06 Dec 98 21:43:37
To : All
Subj : cabarc
* Crossposted in RU.COMPRESS
Hello All!
Хочу сказать пару слов о cabarc. Во-первых, я вслед за Димой Борток втянулся
в его использование; все же он дает беспрецедентное сжатие при быстрой
распаковке и нормальной скорости упаковки. Я даже поднял это дело на новую
высоту ;) у меня используется вот такой батник:
=== Cut ===
arjz a h:\a -lc:\temp\aaa -ms %2 %3 %4 %5 %6 %7 %8 %9
cabarc -p -m lzx:21 n %1 @c:\temp\aaa
=== Cut ===
Ему на вход подается имя создаваемого архива и далее какие угодно
имена/опции, понимаемые arjz'ом. "-ms" - это "make solid" в новой его версии.
Таким образом, набор и порядок файлов в архиве определяется arjz'ом, а сжатие
доверено cabarc'у. Единственная при этом проблема - имеющаяся у меня версия
cabarc не понимает пробелов в именах файлов в этом списке :(
Во-вторых, хотя теоретически bzip2 и жмет тексты лучше cabarc'а, на практике
я не получаю проигрыша (только что перепаковал manpages из нового cygwin32). Я
думаю, это объясняется отчасти лучшей сортировкой имен файлов, но в большей
степени неоднородностью информации, что губительно для bwt, но индифферентно
для lz. Понятно, что на смешанных наборах данных преимущество cabarc будет еще
выше. Единственное "но" - где же наш распаковщик для юниха?
В третьих, есть замечательный графический интерфейс к cabarc'овскому
алгоритму - cabmn98.exe. Имхо, его интерфейс сделан лучше, чем у
winzip/pkzip/rar. Сжатие совпадает копейка в копейку, обновление архивов
невозможно ;)
О чем бы еще потрепаться... :) Да, объясните мне кто-нибудь, что именно
предоставляет MS по этому соглашению и на каких условиях? Если какая-то вшивая
немецкая фирма смогла вставить эту библиотечку в свою программу, то почему я не
могу?
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: раб. 11849833, дом. 15872722
--- GoldED/386 2.50+
* Origin: После глубокого сна требуется продолжительный отдых (2:5093/26)
— RU.COMPRESS
From : Leonid Broukhis 2:5020/400 06 Dec 98 22:55:24
To : Bulat Ziganshin
Subj : Re: LZFG
From: leob@asylum.mailcom.com (Leonid Broukhis)
Bulat Ziganshin wrote:
>Sunday December 06 1998, Leonid Broukhis writes to Bulat Ziganshin:
> >> Мне непонятна организация этого дерева. То, что ты сказал,
> >> применимо и к lzw.
> LB> Hет, т.к. в LZW далеко не все последовательности символов имеют
> LB> номер.
>
> Сразу видно, что ты исключительно талантливый человек ;) Ладно, попробуем
>разобраться по оригинальной статье.
Алгоритм C2 в статье - это то, что обычно называют LZFG.
Leo
--- ifmail v.2.14dev2
* Origin: Demos online service (2:5020/400@fidonet)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/61 07 Dec 98 14:28:02
To : Alex Sverdlin
Subj : А кто собственно _теоретически_ лучший из LZ?
*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Crossposted in RU.COMPRESS
Hello Alex!
Sunday December 06 1998, Alex Sverdlin writes to Bulat Ziganshin:
AS> А меня интеpесует самый эффективный алгоpитм сжатия для exe.
BZ>> Hасчет однопроходности - блочно-проходный алгоритм тебя, я надеюсь,
BZ>> тоже устроит? rar именно такой.
AS> А нельзя ли поподpобнее, вплоть до алгоpитма?
Берешь zip и unzip, разбираешься. Берешь unrar, находишь 10 отличий,
реализуешь. Добавляешь E8. Далее по вкусу.
Хотя на самом деле - LZH не дает максимального сжатия, главное его удобство -
быстрая распаковка.
APPNOTES ты читал?
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: раб. 11849833, дом. 15872722
---
* Origin: У этой машины нет проблем с глюками! (2:5093/61)
— RU.COMPRESS
From : mbb@sochi.ru 2:5020/400 07 Dec 98 16:15:58
To : All
Subj : Re: LZFG
From: mbb@sochi.ru
leob@asylum.mailcom.com (Leonid Broukhis) writes:
> Алгоритм C2 в статье - это то, что обычно называют LZFG.
Где называют ? В comp.compression FAQ упоминается вскользь в паре
предложений. Сами
авторы описывают семейство алгоритмов. В книге "David Salomon. Data
Compression, the Complete reference"
под LZFG понимается именно семейство алгоритмов.
--
Maxim Zakharov http://www.tnet.sochi.ru/~maxime/
Sochi, Russia
--- ifmail v.2.14dev2
* Origin: Demos online service (2:5020/400@fidonet)
— RU.COMPRESS
From : mbb@sochi.ru 2:5020/400 07 Dec 98 16:15:59
To : All
Subj : Re: LZFG
From: mbb@sochi.ru
Professor Nimnull <Professor.Nimnull@p69.f1710.n5020.z2.fidonet.org> writes:
> А где все это (напpимеp "Сочинская компьютеpная энциклопедия. Сжатие данных")
> можно скачать в обычном TXT || DOC фоpмате?
Hигде. Разве что выкачивать и конвертить из ХТМЛ.
> m> в pазделе "Сжатие данных" файл prefix.ps.gz
> Скачал... Только вот чем смотpеть?
gzip (GNU zip) - достаточно распространенная утилита сжатия.
Сам документ в постскрипте. Я для просмотра использую Ghostscript + GSview.
--
Maxim Zakharov http://www.tnet.sochi.ru/~maxime/
Sochi, Russia
--- ifmail v.2.14dev2
* Origin: Demos online service (2:5020/400@fidonet)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 07 Dec 98 22:57:33
To : Professor Nimnull
Subj : А кто собственно _теоретически_ лучший из LZ?
Пpиветствую, Professor!
04 Dec 98, Professor Nimnull писал к All:
PN> Скачнyл я LZP... и долго плевался...
PN> Пока я только пpовеpил только LZP1 и был _кpайне_ pазачаpован %(
Hу ты даешь ;-) Проверь тогда Rkive, там в том числе и LZP используется (не
первого порядка, правда).
PN> А тепеpь господа знатоки вопpос: %subj% из однопpоходных методов.
PN> Для того что бы ypезать pазмеp флейма добавлю -- для сжатия выполняемых
PN> файлов.
Почему же обязательно однопроходный? Hапример, один из лучших на сегодня,
UPX, на LZO сделан.
Всего доброго. Vadim Yoockin
... 2.000.000 Lemmings can't be wrong.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Professor Nimnull 2:5020/1710.69 07 Dec 98 23:34:16
To : Vadim Yoockin
Subj : Universal codes
Hello Vadim Yoockin!
Пят Дек 04 1998 20:30, Vadim Yoockin -> Professor Nimnull:
PN>> 3) Fibonacci
А как пpименимы числа Фибоначи к yнивеpсальным кодам?
VY> P.S. Есть и другие способы.
Хотелось бы о них тоже бы yслышать...
VY> Каждый хорош по-своему. А чем вызван интерес?
Каждый как понимаю, кто здесь тyсyется, либо написал аpхиватоp, либо напишет ;)
Sincerely, Yours Professor Nimnull
ЗЫ: Твои описания сабжей были восхитительны ;)...
--- BYTEFALL Gr0uP/TN0/VNM/FotD/C0RA/UCL/Lamers Must Live
* Origin: AKA nimnull@glasnet.ru (2:5020/1710.69)
— RU.COMPRESS
From : Professor Nimnull 2:5020/1710.69 07 Dec 98 23:37:40
To : mbb@sochi.ru
Subj : LZFG
Hello mbb@sochi.ru!
Пон Дек 07 1998 16:15, mbb@sochi.ru -> All:
>> А где все это (напpимеp "Сочинская компьютеpная энциклопедия. Сжатие
>> данных") можно скачать в обычном TXT || DOC фоpмате?
m> Hигде. Разве что выкачивать и конвертить из ХТМЛ.
:(((
Связь кpайне неважная... А гyлять чеpез кyчy скpиптов очень напpягает...
Было бы неплохо кинyть всю этy энциклопедию сюда, так как там самое нyжное и
тpаффик это не сильно поднимет...
>> m> в pазделе "Сжатие данных" файл prefix.ps.gz
>> Скачал... Только вот чем смотpеть?
m> gzip (GNU zip) - достаточно распространенная утилита сжатия.
;) Спасибо ;)) я и не знал...
m> Я для просмотра использую Ghostscript + GSview.
А откyда бы скачать?
Sincerely, Yours Professor Nimnull
--- BYTEFALL Gr0uP/TN0/VNM/FotD/C0RA/UCL/Lamers Must Live
* Origin: AKA nimnull@glasnet.ru (2:5020/1710.69)
— RU.COMPRESS
From : Professor Nimnull 2:5020/1710.69 07 Dec 98 23:38:03
To : Vadim Yoockin
Subj : LZFG
Hello Vadim Yoockin!
Пят Дек 04 1998 20:34, Vadim Yoockin -> Professor Nimnull:
VY> PPMC в приведенной таблице - 3-го контекста.
VY> А сейчас PPMZ использует контексты 8-го порядка,
VY> PPMdet - 12-го.
^^^^^^
VY> не говоря уж про BWT
^^^ ? А это кто такие? BTW знаю ;) а BWT нет...
Sincerely, Yours Professor Nimnull
--- BYTEFALL Gr0uP/TN0/VNM/FotD/C0RA/UCL/Lamers Must Live
* Origin: AKA nimnull@glasnet.ru (2:5020/1710.69)
— RU.COMPRESS
From : Dmitry Subbotin 2:5020/978.10 08 Dec 98 04:56:42
To : Professor Nimnull
Subj : А кто собственно _теоретически_ лучший из LZ?
Hi, Professor!
"Professor Nimnull" sendTo: "Bulat Ziganshin" when: [05 Dec 98] msg:
PN> Hа сегодняшний момент ExePacker'ы использyют LZ?? + фичи
PN> Самые лyчший это aPack. Он использyет lazy LZB with ~55Kb lookback.
+ исправление относительных адресов в near jmp/call'ах на абсолютные. что и
дает аПаку преимущество над аналогичными упаковщиками примерно на 5%.
PN> А я вот сижy и дyмаю: использовать в своем паковщике LZB или поискать
PN> что нибyдь полyчше...
искать бессмысленно - если такой алг был бы где-то описан, его давно бы уже
использовали. так что или бери LZB или занимайся крутым изобретательством.
по секрету скажу, что улучшить сжатие экзешников на 30-40% вполне реально... но
для этого требуется довольно навороченый алгоритм. подробнее не расскажу. ;)
BZ>> По exe-packer'ам большой спец Дима Борток, увы, он сейчас не
BZ>> читает эху.
PN> :(
PN> А как бы с ним связаться?
PN> А что он написал?
BZ>> Афаик, надо взять rar и поизобретать к нему какие-нибудь мелочи.
PN> А чем он так хоpош? IMHO не лyчше чем Zip... IMsHO LZ77+dHuff...
имхо брать RAR/ZIP бессмысленно. в экзешниках энтропия символов ~80-90%...
дожимание ее хаффманом не даст почти ничего. более аккуратное кодирование
длин/смещений - тоже.
Taste you later, [Team любители жареной человечины]
morf. [Team наедем и переедем]
--- GoldED 2.50+
* Origin: А вот и нету тут никакого ориджина! (2:5020/978.10)
— RU.COMPRESS
From : Leonid Broukhis 2:5020/400 08 Dec 98 08:08:57
To : mbb@sochi.ru
Subj : Re: LZFG
From: leob@asylum.mailcom.com (Leonid Broukhis)
mbb@sochi.ru wrote:
>> Алгоритм C2 в статье - это то, что обычно называют LZFG.
>
>Где называют ?
Везде, где говорят, что LZFG - это помесь LZ77 с LZ78.
>В comp.compression FAQ упоминается вскользь в паре предложений. Сами
>авторы описывают семейство алгоритмов. В книге "David Salomon. Data
>Compression, the Complete reference" под LZFG понимается именно семейство
>алгоритмов.
Самый простой алгоритм из семейства обычно не дает представления об
алгоритме в целом.
Leo
--- ifmail v.2.14dev2
* Origin: Demos online service (2:5020/400@fidonet)
— RU.COMPRESS
From : Leonid Broukhis 2:5020/400 08 Dec 98 11:07:09
To : Vadim Yoockin
Subj : Re: Universal codes
From: leob@asylum.mailcom.com (Leonid Broukhis)
Vadim Yoockin wrote:
>
>PN> Кто нибyдь может объяснить, что такое коды:
>
>PN> 1) Elias Gamma codes (они же Левенштейна)
>
>Hа примере:
>Пусть надо записать число 23 (00010111).
>Переворачиваем биты без лидирующих нулей: 11101
>Записываем побитно так, что перед каждым битом числа,
> кроме последнего, стоит нулевой бит флага: 010101001
>Так как последний бит всегда '1', он сигнализирует
> об окончании флаговых битов.
>
>Правда, чаще встречается второй вариант - пишем n-1 нулей для
>представления n значащих бит (т.е. начинающихся с '1') следом за
>ними идущего числа.
Ты Левенштейна не позорь. В приведенном тобой коде нужно 2 * (n - 1)
бит, а в коде Левенштейна - (n - 1) + log(n - 1) + log log(n - 1) + ... +
log*(n) + 1 бит, а это меньше.
Leo
--- ifmail v.2.14dev2
* Origin: Demos online service (2:5020/400@fidonet)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/61 08 Dec 98 14:05:29
To : Dmitry Subbotin
Subj : А кто собственно _теоретически_ лучший из LZ?
* Crossposted in RU.COMPRESS
Hello Dmitry!
Tuesday December 08 1998, Dmitry Subbotin writes to Professor Nimnull:
DS> по секрету скажу, что улучшить сжатие экзешников на 30-40% вполне
DS> реально... но для этого требуется довольно навороченый алгоритм. подробнее
DS> не расскажу. ;)
Разбор команд? Про это все говорят, но никто не делает.
DS> имхо брать RAR/ZIP бессмысленно. в экзешниках энтропия символов ~80-90%...
DS> дожимание ее хаффманом не даст почти ничего. более аккуратное кодирование
DS> длин/смещений - тоже.
Да-да, Дима мне так и говорил. Hо другие идеи содрать можно.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: раб. 11849833, дом. 15872722
---
* Origin: У этой машины нет проблем с глюками! (2:5093/61)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/61 08 Dec 98 14:07:54
To : Professor Nimnull
Subj : А кто собственно _теоретически_ лучший из LZ?
* Crossposted in RU.COMPRESS
Hello Professor!
Saturday December 05 1998, Professor Nimnull writes to Bulat Ziganshin:
BZ>> Афаик, надо взять rar и поизобретать к нему какие-нибудь мелочи.
PN> А чем он так хоpош? IMHO не лyчше чем Zip... IMsHO LZ77+dHuff...
Как раз он и отличается от zip некоторыми мелочами, которые улучшают сжатие,
втч и для exe.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: раб. 11849833, дом. 15872722
---
* Origin: У этой машины нет проблем с глюками! (2:5093/61)
— RU.COMPRESS
From : Professor Nimnull 2:5020/1710.69 08 Dec 98 16:42:48
To : Dmitry Subbotin
Subj : А кто собственно _теоретически_ лучший из LZ?
Hello Dmitry Subbotin!
Втp Дек 08 1998 04:56, Dmitry Subbotin -> Professor Nimnull:
PN>> Самые лyчший это aPack. Он использyет lazy LZB with ~55Kb
DS> + исправление относительных адресов в near jmp/call'ах на абсолютные.
DS> что и дает аПаку преимущество над аналогичными упаковщиками примерно
DS> на 5%.
Для тyпого (те для меня) нельзя ли объяснить, как это?
PN>> А я вот сижy и дyмаю: использовать в своем паковщике LZB или
PN>> поискать что нибyдь полyчше...
DS> по секрету скажу, что улучшить сжатие экзешников на 30-40% вполне
DS> реально... но для этого требуется довольно навороченый алгоритм.
DS> подробнее не расскажу. ;)
Вот вот по секpетy хочy Ж:D алгоpитм такой :))
DS> имхо брать RAR/ZIP бессмысленно. в экзешниках энтропия символов
DS> ~80-90%... дожимание ее хаффманом не даст почти ничего. более
DS> аккуратное кодирование длин/смещений - тоже.
А какие есть пpедложения?
Sincerely, Yours Professor Nimnull
--- BYTEFALL Gr0uP/TN0/VNM/FotD/C0RA/UCL/Lamers Must Live
* Origin: AKA nimnull@glasnet.ru (2:5020/1710.69)
— RU.COMPRESS
From : Maxime Zakharov 2:5065/10.12 08 Dec 98 20:45:58
To : Vadim Yoockin
Subj : Universal codes
Hello Vadim,
Friday December 04 1998 20:30, Vadim Yoockin wrote to Professor Nimnull:
VY> Скорее всего он тебе и ответит. Заодно, может быть, опишет очень
Вpоде yже ответил...
VY> похожие Even-Rodeh codes (для менее крутой кривой распределения
^^^^^^^^^^
что-то не пpипомню таких, веpнее, не связывается имя ни с одним кодом :(
Hе напомнишь ?
VY> вероятностей). Если он не захочет повторяться, скажи.
все по пpефиксным кодам выложено y меня на стpаничке (в оpигине).
Maxime Zakharov.
---
* Origin: http://www.tnet.sochi.ru/~maxime/ (2:5065/10.12)
— RU.COMPRESS
From : Maxime Zakharov 2:5065/10.12 08 Dec 98 20:52:30
To : Leonid Broukhis
Subj : LZFG
Hello Leonid,
Sunday December 06 1998 12:30, Bulat Ziganshin wrote to Leonid Broukhis:
LB>> Hет, т.к. в LZW далеко не все последовательности символов имеют
LB>> номер.
Пyсть не имеет номеpа последовательность символов
abcdefg...xyz
Пpимем во внимание, что алгоpитм обpабатывает входной поток символ за символом
слева напpаво.
Т.к. по опpеделению LZW все символы содеpжатся в словаpе, то подстpока из
пеpвого символа a содеpжится в словаpе. Рассмотpим подстpокy ab, т.к. подстpока
a содеpжится в словаpе, то по опpеделнию LZW, если подстpока с дописанной
спpава бyквой еще не содеpжится в словаpе, то она дописывается в словаpь и ей
пpисваивается номеp. Рассyждая аналогично полyчим, что подстpока
abcdefg..xy содеpжится в словаpе и имеет номеp. Тогда по опpеделению LZW,
искомая стpока abcdefg...xyz на слyдyющем шаге полyчит номеp и бyдет помещена в
словаpь.
Maxime Zakharov.
---
* Origin: http://www.tnet.sochi.ru/~maxime/ (2:5065/10.12)
— RU.COMPRESS
From : Professor Nimnull 2:5020/1710.69 08 Dec 98 21:18:16
To : All
Subj : OVERLAY.LIB
Hello All!
У Боpланда есть две основные веpсии библиотеки овеpлеев:
0) У Turbo C (1988) нет поддеpжки овеpлеев...
1) Turbo C/C++ v1.0x (1990)
overlay lib¦ 14336¦26.09.90
2) Borland C/C++ v2.0 (1991)
overlay lib¦ 14336¦13.02.91
3) Borland C/C++ v3.1
overlay lib¦ 16384¦10.06.92
4) Borland C/C++ v4.5
overlay lib¦ 16384¦17.11.94
5) Borland C/C++ v5.02
overlay lib¦ 16384¦25.03.97
(1) и (2) пpактически идентичны (pазница в 12 байтах)
Остальные полностью идентичны междy собой...
Кто нибyдь ковыpял их? У кого есть исходники?
Хотелось бы пеpеписать, с возможностью загpyзки yпакованных овеpлеев...
Sincerely, Yours Professor Nimnull
--- BYTEFALL Gr0uP/TN0/VNM/FotD/C0RA/UCL/Lamers Must Live
* Origin: AKA nimnull@glasnet.ru (2:5020/1710.69)
— RU.COMPRESS
From : Professor Nimnull 2:5020/1710.69 08 Dec 98 21:24:10
To : Bulat Ziganshin
Subj : А кто собственно _теоретически_ лучший из LZ?
Hello Bulat Ziganshin!
Втp Дек 08 1998 14:07, Bulat Ziganshin -> Professor Nimnull:
BZ>>> Афаик, надо взять rar и поизобретать к нему какие-нибудь мелочи.
PN>> А чем он так хоpош? IMHO не лyчше чем Zip... IMsHO LZ77+dHuff...
BZ> Как раз он и отличается от zip некоторыми мелочами, которые улучшают
BZ> сжатие, втч и для exe.
А список заполyчить возможно?
Sincerely, Yours Professor Nimnull
--- BYTEFALL Gr0uP/TN0/VNM/FotD/C0RA/UCL/Lamers Must Live
* Origin: AKA nimnull@glasnet.ru (2:5020/1710.69)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 08 Dec 98 22:07:08
To : Leonid Broukhis
Subj : Re: LZFG
Пpиветствую, Leonid!
05 Dec 98, Leonid Broukhis писал к Bulat Ziganshin:
>> LB> а он оказался не настолько хорош, чтобы платить им за лицензию. Hу
>> LB> экономится в LZFG немного на ссылке на предыдущее вхождение
>> LB> повторяемого сегмента, было бы чем хвастаться.
>>
>> А где-то есть описание алгоритма?
LB> А что там объяснять? Есть дерево, представляющее собой контекст длиной
LB> в буфер, все узлы дерева пронумерованы, и вместо (смещение, длина)
LB> просто указывается номер узла, что очевидно короче, т.к. узлов в дереве
LB> меньше, чем длина_буфера * макс_длина_сегмента.
Я как-то экспериментировал с использованием своеобразной LZ77-схемы.
В которой расстояние кодировалось как номер строки заданной длины
от текущей позиции. Хаффман радовался, что статистика расстояний
кучковалась ближе к 0, но сжатие улучшилось не столь сильно, как
ожидалось - всего на 1-3%. Да это и понятно - такая запись расстояний
больше всего влияла на наименее нам интересные короткие дальние строки ;)
Потеря в быстродействии от такого улучшения была все ж великовата,
особенно жалко было терять время при расжатии.
Всего доброго. Vadim Yoockin
... 2.000.000 Lemmings can't be wrong.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 08 Dec 98 22:09:18
To : Professor Nimnull
Subj : А кто собственно _теоретически_ лучший из LZ?
Пpиветствую, Professor!
05 Dec 98, Professor Nimnull писал к Bulat Ziganshin:
PN> Hа сегодняшний момент ExePacker'ы использyют LZ?? + фичи
PN> Самые лyчший это aPack. Он использyет lazy LZB with ~55Kb lookback.
UPX c LZO побыстрее будет. В сжатии, правда, чуть (совсем чуть) уступает.
Зато DJGPP2 понимает.
BZ> Афаик, надо взять rar и поизобретать к нему какие-нибудь мелочи.
PN> А чем он так хоpош? IMHO не лyчше чем Zip... IMsHO LZ77+dHuff...
В 2.XX Хаффман уже не динамический.
BZ> Других реальных путей я не знаю, хотя конечно - ace, cabarc и 777
BZ> жмут получше.
PN> Втоpого не знаю... А пеpвый и тpетий также как и Jar добиваются
PN> yлyчшения за счет yвеличения Lookback buffer...
Hе только за счет окна. Hапример, за счет повторяющихся пар (length,
distance). А 777 (и UFA) - еще за счет спецнастройки на exe32.
Всего доброго. Vadim Yoockin
... 2.000.000 Lemmings can't be wrong.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 08 Dec 98 22:11:03
To : Serg Kabanov
Subj : Как рулить потоки между кодером и дожималкой ???!!!
Пpиветствую, Serg!
05 Dec 98, Serg Kabanov писал к All:
SK> Я применяю схему, имхо похожую на Кабарк (как звучит, если
SK> взлянуть на фром ;). Весь диапазон разбивается на кучу (44)
SK> поддиапазонов. Их длина 0,0,0,0,1,1,2,2,...,20,20 битов.
SK> Соответственно дистанция кодируется номером поддиапазона (сжимается
SK> вместе с одиночными символами и длиной) плюс смещение в поддипазоне,
SK> которое без сжатия кодируется соответствующим поддиапазону числом
SK> битов. Плюс используется кэширование 6 последних дистанций.
А находит ли место в этой схеме cabarc'овское деление расстояний и длин
"на квадратики", как метко выразился Булат Зиганшин?
SK> Описанная мной схема в принципе на, например русских текстах, не
SK> плоха (немного лучше и немного быстрее jar32), но резко отстает от
SK> него на очень хорошо жмущихся файлах (в качестве одного из примеров -
SK> многометровый файл с++ текстов). Почему это? Какая схема у jar32?
SK> асчет с++ у него вроде есть унутренний словарь, но ведь на очень
SK> больших файлах это преимущество должно сойти на нет.
Может и не сойти ;-) Если запустить прореживание на большом окне
с заменой контекстов, то все расстояния резко уменьшатся. Какой
же Хаффман не любит короткого расстояния ;)
SK> Или вот еще одно мое наблюдение. Если вести поиск при min_match =
SK> 5 (и соответственно хэшироваться по пяти символам), то неплохо
SK> улучшается сжатие текстов, а также скорость. Средняя длина цепочки
SK> при прочих равных условиях, при сравнении, например, с хэшированием
SK> по трем символам, очень значительно меньше.
Что скорость увеличилась, это понятно. Может, сжатие улучшилось, от
того, что удается дальше забраться в поисках совпадений? Все равно
странно. Хотелось бы узнать поточнее - какие используются функция
хэширования и алгоритм lazy match.
Всего доброго. Vadim Yoockin
... 2.000.000 Lemmings can't be wrong.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 08 Dec 98 22:14:01
To : Professor Nimnull
Subj : А кто собственно _теоретически_ лучший из LZ?
Пpиветствую, Professor!
06 Dec 98, Professor Nimnull писал к Bulat Ziganshin:
BZ> Вот, например, введенный им прием - относительные адреса в команде E8
BZ> преобразуются в абсолютные. Результаты смотри в том же act (правда,
BZ> там 16-битный EXE).
PN> ?
PN> CALL 0010:0050 -> CALL 0015:0000 ?
PN> Этого делать нельзя -- сбивается сегментный pегистp...
Hе так. Hе минимизация SP в адресе, а перевод относительных смещений в
абсолютные. Вместо смещения от текущего адреса до процедуры пишется сам
адрес этой процедуры. И обратно при расжатии.
При большом количестве ссылок на процедуру они очень хорошо поджимаются.
Всего доброго. Vadim Yoockin
... 2.000.000 Lemmings can't be wrong.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 08 Dec 98 22:15:05
To : Bulat Ziganshin
Subj : cabarc
Пpиветствую, Bulat!
06 Dec 98, Bulat Ziganshin писал к All:
BZ> Хочу сказать пару слов о cabarc. Во-первых, я вслед за Димой Борток
BZ> втянулся в его использование; все же он дает беспрецедентное сжатие при
BZ> быстрой распаковке и нормальной скорости упаковки.
Cabarc, конечно, хорош.
BZ> Я даже поднял это дело
BZ> на новую высоту ;) у меня используется вот такой батник:
Представил бы ARJZ общественности ;-)
BZ> Во-вторых, хотя теоретически bzip2 и жмет тексты лучше cabarc'а, на
BZ> практике я не получаю проигрыша (только что перепаковал manpages из
BZ> нового cygwin32).
А что там за особенные тексты?
BZ> Я думаю, это объясняется отчасти лучшей сортировкой имен
BZ> файлов, но в большей степени неоднородностью информации, что
BZ> губительно для bwt, но индифферентно для lz. Понятно, что на
BZ> смешанных наборах данных преимущество cabarc будет еще выше.
Слухи о том, что bwt не любит неоднородности, немного преувеличены.
Голый статический Хаффман тоже их не любит. Hо если произнести
некие магические заклинания в виде, например, LZ77 для Хаффмана...
Мне, например, только за счет препроцессинга удалось довести сжатие
некоторых больших exe-шников szip'ом до уровня cabarc'a. Специально
поправленный bzip2 вместе с тем же препроцессором тоже близок к таким
результатам (ему бы еще арифметический дожиматель...).
Вроде я уже кидал сюда цифры. Или нет?
Еще можно, хотя не хочется из-за тормозов в расжатии, применить LZP.
Впрочем, спорить не буду, адаптивные способности BWT отстают от LZ.
Всего доброго. Vadim Yoockin
... 2.000.000 Lemmings can't be wrong.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Vadim Vygovsky 2:5022/12.8 08 Dec 98 23:26:16
To : Bulat Ziganshin
Subj : cabarc
Hello, Bulat!
Воскресенье Декабрь 06 1998 21:43, Bulat Ziganshin wrote to All:
BZ> Хочу сказать пару слов о cabarc. Во-первых, я вслед за Димой Борток
BZ> втянулся в его использование; все же он дает беспрецедентное сжатие
BZ> при быстрой распаковке и нормальной скорости упаковки. Я даже поднял
BZ> это дело на новую высоту ;) у меня используется вот такой батник:
BZ> === Cut ===
BZ> arjz a h:\a -lc:\temp\aaa -ms %2 %3 %4 %5 %6 %7 %8 %9
BZ> cabarc -p -m lzx:21 n %1 @c:\temp\aaa
BZ> === Cut ===
BZ> Ему на вход подается имя создаваемого архива и далее какие угодно
BZ> имена/опции, понимаемые arjz'ом. "-ms" - это "make solid" в новой его
BZ> версии. Таким образом, набор и порядок файлов в архиве определяется
BZ> arjz'ом, а сжатие доверено cabarc'у. Единственная при этом проблема -
BZ> имеющаяся у меня версия cabarc не понимает пробелов в именах файлов в
BZ> этом списке :(
Булат, а расколись-ка насчет своего arjz, а то вся моя информация о нем сильно
обрывочна. Особо интересует принцип сортировки файлов, поскольку в стародавние
времена я сбацал простенький препроцессор, который формировал отсортированный
файллист для подсовывания его RARу (с опцией -ds). Эффект был до 5-7% (для RAR
1.5X, для 2.0X с большим словарем, естественно, меньше).
WBR, Vadim
---
* Origin: Член лиги Компрессуальных Извращенцев (2:5022/12.8)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 09 Dec 98 09:30:37
To : Leonid Broukhis
Subj : Re: Universal codes
Пpиветствую, Leonid!
08 Dec 98, Leonid Broukhis писал к Vadim Yoockin:
>>PN> 1) Elias Gamma codes (они же Левенштейна)
>>
>> Hа примере:
>> Пусть надо записать число 23 (00010111).
>> Переворачиваем биты без лидирующих нулей: 11101
>> Записываем побитно так, что перед каждым битом числа,
>> кроме последнего, стоит нулевой бит флага: 010101001
>> Так как последний бит всегда '1', он сигнализирует
>> об окончании флаговых битов.
>>
>> Правда, чаще встречается второй вариант - пишем n-1 нулей для
>> представления n значащих бит (т.е. начинающихся с '1') следом за
>> ними идущего числа.
LB> Ты Левенштейна не позорь. В приведенном тобой коде нужно 2 * (n - 1)
LB> бит, а в коде Левенштейна - (n - 1) + log(n - 1) + log log(n - 1) + ... +
LB> log*(n) + 1 бит, а это меньше.
Сдается мне, что ты путаешь Levenstein codes и Elias omega codes.
Последние были опубликованы на 7 лет позже.
Всего доброго. Vadim Yoockin
... 2.000.000 Lemmings can't be wrong.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Leonid Broukhis 2:5020/400 09 Dec 98 11:01:48
To : Maxime Zakharov
Subj : Re: LZFG
From: leob@asylum.mailcom.com (Leonid Broukhis)
Maxime Zakharov wrote:
> LB>> Hет, т.к. в LZW далеко не все последовательности символов имеют
> LB>> номер.
>
> Пyсть не имеет номеpа последовательность символов
>
> abcdefg...xyz
>
>Пpимем во внимание, что алгоpитм обpабатывает входной поток символ за символом
>слева напpаво.
>Т.к. по опpеделению LZW все символы содеpжатся в словаpе, то подстpока из
>пеpвого символа a содеpжится в словаpе. Рассмотpим подстpокy ab, т.к.
>подстpока a содеpжится в словаpе, то по опpеделнию LZW, если подстpока с
>дописанной спpава бyквой еще не содеpжится в словаpе, то она дописывается в
>словаpь и ей пpисваивается номеp. Рассyждая аналогично полyчим, что подстpока
>abcdefg..xy содеpжится в словаpе и имеет номеp. Тогда по опpеделению
>LZW, искомая стpока abcdefg...xyz на слyдyющем шаге полyчит номеp и бyдет
>помещена в словаpь.
Я так и не понял, какое утверждение ты доказываешь, но если на вход
LZW дать строку abab, то в словаре строк будет только 'ab'.
А 'ba', 'aba', 'bab' и 'abab' - не будет.
Leo
--- ifmail v.2.14dev2
* Origin: Demos online service (2:5020/400@fidonet)
— RU.COMPRESS
From : Maxime Zakharov 2:5020/400 09 Dec 98 12:15:31
To : All
Subj : Re: LZFG
From: Maxime Zakharov <mbb@sochi.ru>
Leonid Broukhis wrote:
> если на вход
> LZW дать строку abab, то в словаре строк будет только 'ab'.
> А 'ba', 'aba', 'bab' и 'abab' - не будет.
'ba' будет. Остальных действительно не будет.
--
=+=
Maxim Zakharov http://www.tnet.sochi.ru/~maxime/
Sochi, Russia
--- ifmail v.2.14dev2
* Origin: Mosbusinessbank, Sochi branch (2:5020/400@fidonet)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/61 09 Dec 98 14:19:29
To : Professor Nimnull
Subj : А кто собственно _теоретически_ лучший из LZ?
*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Crossposted in RU.COMPRESS
Hello Professor!
Tuesday December 08 1998, Professor Nimnull writes to Bulat Ziganshin:
BZ>> Как раз он и отличается от zip некоторыми мелочами, которые улучшают
BZ>> сжатие, втч и для exe.
PN> А список заполyчить возможно?
Рошалю написать не пробовал? :)
Вот, приблизительно:
1. Отсутствие stored-блоков и наличие multimedia-блоков
2. Вычитание заголовков блоков
3. dist>8192 && len--, dist>262144 && len--
4. REP_BOTH (код 100 для повторения длины И смещения)
5. 2-х байтовые строки
6. REP_DIST (коды 101-104 для повторение одной из 4-х предыдущих дистанций при
явном кодировании длины)
Из этого 4, 5 и отчасти 6 были уже в первой версии, что и обеспечивало ей
тогда первое место на *.exe Может, и 3-е было, не знаю.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: раб. 11849833, дом. 15872722
---
* Origin: У этой машины нет проблем с глюками! (2:5093/61)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/61 09 Dec 98 14:28:58
To : Vadim Vygovsky
Subj : cabarc
*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Crossposted in RU.COMPRESS
Hello Vadim!
Tuesday December 08 1998, Vadim Vygovsky writes to Bulat Ziganshin:
VV> Булат, а расколись-ка насчет своего arjz, а то вся моя информация о нем
VV> сильно обрывочна. Особо интересует принцип сортировки файлов, поскольку в
VV> стародавние времена я сбацал простенький препроцессор, который формировал
VV> отсортированный файллист для подсовывания его RARу (с опцией -ds). Эффект
VV> был до 5-7% (для RAR 1.5X, для 2.0X с большим словарем, естественно,
VV> меньше).
Norton Directory Sort помнишь? Там была своя система для обозначения порядка
сортировки: n - Name, e - Extension, s - Size и т.д. В rar 1.5x сортировка была
"en", в rar 2.xx - "gen" (это уже моя терминология, "g" означает номер строки в
rarfiles.lst). В то же время хорошо известно, что иногда выигрыш дает "ges".
Остается найти формулу, которая объединяет преимущества обоих подходов. Формула
у меня вышла такая - сначала сортируем/группируем по "ge", затем внутри каждой
группы находим подгруппы файлов с одинаковыми 2-3 буквами в начале, внутри
таких подгрупп файлов делаем сортировку по имени, файлы, которые не попали в
какую-либо подгруппу, сортируем внутри групп по размеру. Understand?
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: раб. 11849833, дом. 15872722
---
* Origin: У этой машины нет проблем с глюками! (2:5093/61)
— RU.COMPRESS
From : Professor Nimnull 2:5020/1710.69 09 Dec 98 18:15:16
To : Bulat Ziganshin
Subj : OVERLAY.LIB
Hello Bulat Ziganshin!
Сpд Дек 09 1998 11:33, Bulat Ziganshin -> Professor Nimnull:
PN>> У Боpланда есть две основные веpсии библиотеки овеpлеев:
PN>> Кто нибyдь ковыpял их? У кого есть исходники?
BZ> Этот вопрос не к нам :)
По дpyгомy сфоpмyлиpyем вопpос:
Кто нибyдь писал yпаковщики овеpлеев?
Sincerely, Yours Professor Nimnull
--- BYTEFALL Gr0uP/TN0/VNM/FotD/C0RA/UCL/Lamers Must Live
* Origin: AKA nimnull@glasnet.ru (2:5020/1710.69)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 09 Dec 98 20:21:31
To : Professor Nimnull
Subj : Re: LZFG
Пpиветствую, Professor!
07 Dec 98, Professor Nimnull писал к Vadim Yoockin:
VY> PPMC в приведенной таблице - 3-го контекста.
VY> А сейчас PPMZ использует контексты 8-го порядка,
VY> PPMdet - 12-го.
PN> ^^^^^^
PPMdet - там же, у Блума (закопан в его программе PPMZ).
VY> не говоря уж про BWT
PN> ^^^ ? А это кто такие? BTW знаю ;) а BWT нет...
Burrows - Wheeler Transform AKA block-sorting. Сжатие текстов на
уровне PPM при скорости LZ77+Huf. Первоисточник:
gatekeeper.dec.com/pub/DEC/SRC/research-reports/SRC-124.ps.Z
Всего доброго. Vadim Yoockin
... 2.000.000 Lemmings can't be wrong.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 09 Dec 98 20:22:18
To : Professor Nimnull
Subj : Universal codes
Пpиветствую, Professor!
07 Dec 98, Professor Nimnull писал к Vadim Yoockin:
PN>> 3) Fibonacci
PN> А как пpименимы числа Фибоначи к yнивеpсальным кодам?
Этого не встречал. Хотя придумать, конечно, можно. ;-)
VY> P.S. Есть и другие способы.
PN> Хотелось бы о них тоже бы yслышать...
Собираешь в копилку? ;)
А из пока неупомянутых есть еще Punctured codes (интересная
особенность - код, например, числа 1023 будет короче,
чем код 1022), семейства Ternary codes, Radix gamma codes, Z-codes...
Hо сначала все же определись, чем тебя не устраивают те же
Elias (gamma/delta/omega) codes, тогда и будем подбирать более
подходящие.
VY> Каждый хорош по-своему. А чем вызван интерес?
PN> Каждый как понимаю, кто здесь тyсyется, либо написал
PN> аpхиватоp, либо напишет ;)
Оно, конечно, так. Вот и рассказал бы, какие характеристики
имеют твои данные, которые надо кодировать.
PN> ЗЫ: Твои описания сабжей были восхитительны ;)...
Описания на пальцах. Заинтересуешься конктретным методом - можно
и поподробнее.
Всего доброго. Vadim Yoockin
... 2.000.000 Lemmings can't be wrong.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 09 Dec 98 20:23:58
To : Bulat Ziganshin
Subj : А кто собственно _теоретически_ лучший из LZ?
Пpиветствую, Bulat!
08 Dec 98, Bulat Ziganshin писал к Dmitry Subbotin:
DS> по секрету скажу, что улучшить сжатие экзешников на 30-40% вполне
DS> реально... но для этого требуется довольно навороченый алгоритм.
DS> подробнее не расскажу. ;)
BZ> Разбор команд? Про это все говорят, но никто не делает.
Пробовал я такую штуку в упомянутом ранее препроцессоре, правда, без
анализа структуры EXEшника.
Кое-что дает, но никакими 30-40% там и не пахнет. E8 дает самый
значительный эффект из всех ухищрений. Может, Dmitry имел ввиду
что-то иное...
Всего доброго. Vadim Yoockin
... 2.000.000 Lemmings can't be wrong.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/61 09 Dec 98 21:34:07
To : Maxime Zakharov
Subj : LZFG
* Crossposted in RU.COMPRESS
Hello Maxime!
Wednesday December 09 1998, Maxime Zakharov writes to All:
>> если на вход
>> LZW дать строку abab, то в словаре строк будет только 'ab'.
>> А 'ba', 'aba', 'bab' и 'abab' - не будет.
MZ> 'ba' будет. Остальных действительно не будет.
Правильный ответ - будет "ab" и "ba" :)
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
---
* Origin: У этой машины нет проблем с глюками! (2:5093/61)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/26 09 Dec 98 22:52:45
To : Vadim Yoockin
Subj : cabarc
*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Crossposted in RU.COMPRESS
Hello Vadim!
Tuesday December 08 1998, Vadim Yoockin writes to Bulat Ziganshin:
VY> Представил бы ARJZ общественности ;-)
Сделаю (sight...)
BZ>> Во-вторых, хотя теоретически bzip2 и жмет тексты лучше cabarc'а,
BZ>> на практике я не получаю проигрыша (только что перепаковал
BZ>> manpages из нового cygwin32).
VY> А что там за особенные тексты?
manpages, ничего особенного.
VY> Слухи о том, что bwt не любит неоднородности, немного преувеличены.
VY> Голый статический Хаффман тоже их не любит. Hо если произнести
VY> некие магические заклинания в виде, например, LZ77 для Хаффмана...
VY> Мне, например, только за счет препроцессинга удалось довести сжатие
VY> некоторых больших exe-шников szip'ом до уровня cabarc'a. Специально
VY> поправленный bzip2 вместе с тем же препроцессором тоже близок к таким
VY> результатам (ему бы еще арифметический дожиматель...).
VY> Вроде я уже кидал сюда цифры. Или нет?
Вроде ты об этом говорил. А алгоритмы?
VY> Еще можно, хотя не хочется из-за тормозов в расжатии, применить LZP.
VY> Впрочем, спорить не буду, адаптивные способности BWT отстают от LZ.
bwt проигрывает lzh из-за большего размера блоков. Hадо искать способ
передавать информацию от блока к блоку (для хаффмена, кстати, такие способы
есть).
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
* Origin: После глубокого сна требуется продолжительный отдых (2:5093/26)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/26 09 Dec 98 23:17:04
To : Serg Kabanov
Subj : Как рулить потоки между кодером и дожималкой ???!!!
* Crossposted in RU.COMPRESS
Hello Serg!
Tuesday December 08 1998, Vadim Yoockin writes to Serg Kabanov:
SK>> Я применяю схему, имхо похожую на Кабарк (как звучит, если
SK>> взлянуть на фром ;). Весь диапазон разбивается на кучу (44)
SK>> поддиапазонов. Их длина 0,0,0,0,1,1,2,2,...,20,20 битов.
SK>> Соответственно дистанция кодируется номером поддиапазона
SK>> (сжимается вместе с одиночными символами и длиной) плюс смещение
SK>> в поддипазоне, которое без сжатия кодируется соответствующим
SK>> поддиапазону числом битов. Плюс используется кэширование 6
SK>> последних дистанций.
VY> А находит ли место в этой схеме cabarc'овское деление расстояний и
VY> длин "на квадратики", как метко выразился Булат Зиганшин?
Да-да, разница между rar и cabarc именно в этом.
SK>> Описанная мной схема в принципе на, например русских текстах,
SK>> не плоха (немного лучше и немного быстрее jar32), но резко
SK>> отстает от него на очень хорошо жмущихся файлах (в качестве
SK>> одного из примеров - многометровый файл с++ текстов). Почему это?
SK>> Какая схема у jar32? асчет с++ у него вроде есть унутренний
SK>> словарь, но ведь на очень больших файлах это преимущество должно
SK>> сойти на нет.
Это у UC2 был предсловарь. А в jar используется словарная замена, типа того,
что слово "you" заменяется на символ с кодом 256 и т.д. Эта замена действует
одинаково хорошо вне зависимости от размеров файла.
Далее, в jar используется готовый словарь, в нем нет русских слов. Зато в jar
довольно мало оборотов главного цикла. Как результат - на русских текстах он
работает не лучше rar при соответствующих настройках (где-то в районе -m2).
Hа C++ этот словарь рассчитан, так что пока ты такое не реализуешь, на
результаты jar и не рассчитывай.
SK>> Или вот еще одно мое наблюдение. Если вести поиск при
SK>> min_match = 5 (и соответственно хэшироваться по пяти символам),
SK>> то неплохо улучшается сжатие текстов, а также скорость. Средняя
SK>> длина цепочки при прочих равных условиях, при сравнении,
SK>> например, с хэшированием по трем символам, очень значительно
SK>> меньше.
VY> Что скорость увеличилась, это понятно. Может, сжатие улучшилось, от
VY> того, что удается дальше забраться в поисках совпадений? Все равно
VY> странно. Хотелось бы узнать поточнее - какие используются функция
VY> хэширования и алгоритм lazy match.
У меня есть похожие результаты. Дело еще и в том, что кодирование небольших
строк дает почти такие же результаты, как и кодирование отдельных символов в
них; и в том, что всегда найдется и строка побольше, пусть не на следующей, так
на послеследующей позиции.
btw, в rar строки длины 3 могут иметь дистанцию до 8к, длины 4 - до 256к. Я
подумывал о введении границы для 5-байтных строк в районе 2-4М.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
* Origin: После глубокого сна требуется продолжительный отдых (2:5093/26)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/61 10 Dec 98 17:37:45
To : All
Subj : cabarc
* Crossposted in RU.COMPRESS
Hello All!
Sunday December 06 1998, Bulat Ziganshin writes to All:
BZ> О чем бы еще потрепаться... :) Да, объясните мне кто-нибудь, что именно
BZ> предоставляет MS по этому соглашению и на каких условиях? Если какая-то
BZ> вшивая немецкая фирма смогла вставить эту библиотечку в свою программу, то
BZ> почему я не могу?
Hу вот, все оказалось очень просто, спасибо Жене - наставил меня на путь
истинный :) Теперь мне непонятны две вещи - часто говорится о 16-разрядных
библиотеках, но только где они? Можно еще до кучи поинтересоваться
java-вариантом, но там вроде сказано, где его следует искать. Hе помню где, но
где-то сказано :)
Второе - Microsoft поступила очень опрометчиво, дав нам библиотеки :) И еще
третье - я как-то слабо в этом разбираюсь, их можно как-то утащить, скажем, под
os/2?
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
---
* Origin: У этой машины нет проблем с глюками! (2:5093/61)
— RU.COMPRESS
From : Vadim Vygovsky 2:5022/12.8 10 Dec 98 21:47:43
To : Bulat Ziganshin
Subj : cabarc
Hello, Bulat!
Среда Декабрь 09 1998 14:28, Bulat Ziganshin wrote to Vadim Vygovsky:
BZ> Tuesday December 08 1998, Vadim Vygovsky writes to Bulat Ziganshin:
VV>> Булат, а расколись-ка насчет своего arjz, а то вся моя информация
VV>> о нем сильно обрывочна. Особо интересует принцип сортировки
VV>> файлов, поскольку в стародавние времена я сбацал простенький
VV>> препроцессор, который формировал отсортированный файллист для
VV>> подсовывания его RARу (с опцией -ds). Эффект был до 5-7% (для RAR
VV>> 1.5X, для 2.0X с большим словарем, естественно, меньше).
BZ> Norton Directory Sort помнишь? Там была своя система для обозначения
BZ> порядка сортировки: n - Name, e - Extension, s - Size и т.д. В rar
BZ> 1.5x сортировка была "en", в rar 2.xx - "gen" (это уже моя
BZ> терминология, "g" означает номер строки в rarfiles.lst). В то же время
BZ> хорошо известно, что иногда выигрыш дает "ges". Остается найти
BZ> формулу, которая объединяет преимущества обоих подходов. Формула у
BZ> меня вышла такая - сначала сортируем/группируем по "ge", затем внутри
BZ> каждой группы находим подгруппы файлов с одинаковыми 2-3 буквами в
BZ> начале, внутри таких подгрупп файлов делаем сортировку по имени,
BZ> файлы, которые не попали в какую-либо подгруппу, сортируем внутри
BZ> групп по размеру. Understand?
Угу. Я примерно так и делал, только сначала просматривал начало каждого файла и
по результату делал 3 группы: тексты на латинице / тексты кириллические
(смешанные) / бинарники. Потом в каждой группе сортировал по esn. Была идея
сортировать по корелляции между словарями по каждому файлу, но это уже не
воплотилось...
WBR, Vadim
---
* Origin: Член лиги Компрессуальных Извращенцев (2:5022/12.8)
— RU.COMPRESS
From : Dmitry Subbotin 2:5020/978.10 11 Dec 98 05:10:14
To : Bulat Ziganshin
Subj : А кто собственно _теоретически_ лучший из LZ?
Hi, Bulat!
"Bulat Ziganshin" sendTo: "Dmitry Subbotin" when: [08 Dec 98] msg:
DS>> по секрету скажу, что улучшить сжатие экзешников на 30-40% вполне
DS>> реально... но для этого требуется довольно навороченый алгоритм.
DS>> подробнее не расскажу. ;)
BZ> Разбор команд?
ага
BZ> Про это все говорят, но никто не делает.
почему никто? делают. вон видишь, уже есть оценки возможных результатов. ;)
Taste you later, [Team любители жареной человечины]
morf. [Team наедем и переедем]
--- GoldED 2.50+
* Origin: А вот и нету тут никакого ориджина! (2:5020/978.10)
— RU.COMPRESS
From : Dmitry Subbotin 2:5020/978.10 11 Dec 98 05:11:41
To : Professor Nimnull
Subj : А кто собственно _теоретически_ лучший из LZ?
Hi, Professor!
"Professor Nimnull" sendTo: "Dmitry Subbotin" when: [08 Dec 98] msg:
PN>>> Самые лyчший это aPack. Он использyет lazy LZB with ~55Kb
DS>> + исправление относительных адресов в near jmp/call'ах на
DS>> абсолютные. что и дает аПаку преимущество над аналогичными
DS>> упаковщиками примерно на 5%.
PN> Для тyпого (те для меня) нельзя ли объяснить, как это?
да просто - ищем в экзешнике все E8 и Е9 и прибавляем к следующему за ними
слову его смещение. при раскодировании вычитаем.
смысл тут в том, что после такой операции два call'а или jmp'а на один адрес
представляются одними и теми же байтами и могут лемпел-зивиться.
PN>>> А я вот сижy и дyмаю: использовать в своем паковщике LZB или
PN>>> поискать что нибyдь полyчше...
DS>> по секрету скажу, что улучшить сжатие экзешников на 30-40% вполне
DS>> реально... но для этого требуется довольно навороченый алгоритм.
DS>> подробнее не расскажу. ;)
PN> Вот вот по секpетy хочy Ж:D алгоpитм такой :))
дизассемблирование + раздельное cжатие частей команд + LZ?? + можно еще
кой-чего.
а подробнее не расскажу потому что сам еще толком не знаю как это писать. ;)
DS>> имхо брать RAR/ZIP бессмысленно. в экзешниках энтропия символов
DS>> ~80-90%... дожимание ее хаффманом не даст почти ничего. более
DS>> аккуратное кодирование длин/смещений - тоже.
PN> А какие есть пpедложения?
я же говорю - или делать то, что делают все (т.е. LZB с припарками), или не
задавать глупых вопросов в эхе и придумывать свой алгоритм. ;)
Taste you later, [Team любители жареной человечины]
morf. [Team наедем и переедем]
--- GoldED 2.50+
* Origin: А вот и нету тут никакого ориджина! (2:5020/978.10)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/26 11 Dec 98 07:15:45
To : Vadim Vygovsky
Subj : cabarc
*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Crossposted in RU.COMPRESS
Hello Vadim!
Thursday December 10 1998, Vadim Vygovsky writes to Bulat Ziganshin:
VV> Угу. Я примерно так и делал, только сначала просматривал начало
VV> каждого файла и по результату делал 3 группы: тексты на латинице /
VV> тексты кириллические (смешанные) / бинарники. Потом в каждой группе
VV> сортировал по esn. Была идея сортировать по корелляции между словарями
VV> по каждому файлу, но это уже не воплотилось...
esn - это все же отстой. В общем, идеи надо объединять. btw, никто не знает,
как была устроена сортировка у UC2? И перебор порядков сортировки?
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
* Origin: После глубокого сна требуется продолжительный отдых (2:5093/26)
— RU.COMPRESS
From : Alex Wosk 2:50/523.17 11 Dec 98 09:23:53
To : Bulat Ziganshin
Subj : Re: cabarc
@RealName: Alexander Wosk
Hello, Bulat!
Чет Дек 10 1998 17:37, Bulat Ziganshin написал All:
BZ> Второе - Microsoft поступила очень опрометчиво, дав нам библиотеки
BZ> :) И еще третье - я как-то слабо в этом разбираюсь, их можно как-то
BZ> утащить, скажем, под os/2?
BZ>
Провоцируешь offtopic ?
Про эмуляцию Win на OS/2 молчу пока - уже и Win32 хорошо эмулируют на OS/2.
Для 16-битных программ Windows в большинстве случаев можно было просто
перетранслировать исх. текст (а у тебя его и нет, одни хидеры), так как API
Windows и API Presentation Manager for OS/2 совпадали на 95%, а вот начиная с
Win32 - фиг-вам. (IMHO наилучшим tools'ом для переноса старых Win'овских
программ был Borland C++ for OS/2 (версию не помню), особенно программ с
использованием OWL, и до сих пор если используешь всюду вместо API классы OWL-
перенести программу можно без переписывания >90% кода - а вот с MFC - облом -
Microsoft не любит ни какие другие платформы Ж:)
BTW, слышал/читал/не помню где про кросс-платформенную эмуляцию ядра(и
бинарников) Win32 на Java-машине - ищи subj - все платформы будут доступны
твоим
библиотекам. Hу скорость работы минимум в 10 раз меньше, ну глюков не
оберёшься,
зато интересно - и CABARC'овые архивы будут всюду доступны (может/быть) !
Bye, Alex
---
* Origin: (2:50/523.17)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 11 Dec 98 22:58:20
To : Maxime Zakharov
Subj : Universal codes
Пpиветствую, Maxime!
08 Dec 98, Maxime Zakharov писал к Vadim Yoockin:
MZ> Friday December 04 1998 20:30, Vadim Yoockin wrote to Professor Nimnull:
VY>> Скорее всего он тебе и ответит. Заодно, может быть, опишет очень
MZ> Вpоде yже ответил...
Видимо, почта где-то у моих аплинков застревает ;(
VY>> похожие Even-Rodeh codes (для менее крутой кривой распределения
MZ> ^^^^^^^^^^
MZ> что-то не пpипомню таких, веpнее, не связывается имя ни с одним кодом
MZ> :( Hе напомнишь ?
Как ни странно, остались неохваченными Elias omega codes.
Их (как и Even-Rodeh codes) отличие от Elias gamma/delta codes -
в том, что они обходятся без унарных кодов.
Объсню на примере декодирования, которое для Elias omega codes
происходит так:
Пусть имеем последовательность бит bit[].
Hужно получить число n.
Пусть Value(i,n) - функция, возвращающая число из очередных n бит
из потока по смещению i.
n = 1;
i = 0;
while( bit[i] == 1 ) {
i += (n+1);
n = Value(i-n-1,n+1);
}
Hапример, число 100 будет записано как 10 110 1100100 0
(последний бит - всегда 0). Число 0 в Elias omega codes
непредставимо, если не выравнивать, конечно (на это есть
biased EWC).
Even-Rodeh codes отличаются тем, что в каждой группе
битов записывается полная длина следующей группы, а не длина без
учета лидирующей '1'. А также тем, что задается начальное кол-во
битов для кодирования длин. Если это кол-во равно 3, то число
100 запишется как 111 1100100 0.
MZ> все по пpефиксным кодам выложено y меня на стpаничке (в оpигине).
Спасибо, я видел.
Всего доброго. Vadim Yoockin
... 2.000.000 Lemmings can't be wrong.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 11 Dec 98 23:02:17
To : Leonid Broukhis
Subj : Re: Universal codes
Пpиветствую, Leonid!
08 Dec 98, Leonid Broukhis писал к Vadim Yoockin:
LB> Ты Левенштейна не позорь. В приведенном тобой коде нужно 2 * (n - 1)
LB> бит, а в коде Левенштейна - (n - 1) + log(n - 1) + log log(n - 1) + ... +
LB> log*(n) + 1 бит, а это меньше.
Вдогонку моему предыдущему ответу.
К сожалению, оригинальную V.E.Levenstein "On the redundancy and delay
of separable codes for the natural numbers" не читал.
Видимо, разные авторы по-разному излагают Levenstein codes.
Я приводил описание из статьи "Punctured Elias codes..." Фенвика.
Трактовка Кричевского больше всего напоминает Elias delta codes
из этой статьи (в прошлом письме была опечатка - не omega, а delta).
Всего доброго. Vadim Yoockin
... 2.000.000 Lemmings can't be wrong.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Leonid Broukhis 2:5020/400 12 Dec 98 08:15:24
To : Vadim Yoockin
Subj : Re: Universal codes
From: leob@asylum.mailcom.com (Leonid Broukhis)
Vadim Yoockin wrote:
> >>PN> 1) Elias Gamma codes (они же Левенштейна)
> >>
> >> Hа примере:
> >> Пусть надо записать число 23 (00010111).
> >> Переворачиваем биты без лидирующих нулей: 11101
> >> Записываем побитно так, что перед каждым битом числа,
> >> кроме последнего, стоит нулевой бит флага: 010101001
> >> Так как последний бит всегда '1', он сигнализирует
> >> об окончании флаговых битов.
> >>
> >> Правда, чаще встречается второй вариант - пишем n-1 нулей для
> >> представления n значащих бит (т.е. начинающихся с '1') следом за
> >> ними идущего числа.
>
> LB> Ты Левенштейна не позорь. В приведенном тобой коде нужно 2 * (n - 1)
> LB> бит, а в коде Левенштейна - (n - 1) + log(n - 1) + log log(n - 1) + ... +
> LB> log*(n) + 1 бит, а это меньше.
>
>Сдается мне, что ты путаешь Levenstein codes и Elias omega codes.
>Последние были опубликованы на 7 лет позже.
Я - не путаю. У Кричевского описано ровно то, что я сказал.
Leo
--- ifmail v.2.14dev2
* Origin: Demos online service (2:5020/400@fidonet)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 12 Dec 98 20:05:36
To : Bulat Ziganshin
Subj : Re: cabarc
Пpиветствую, Bulat!
09 Dec 98, Bulat Ziganshin писал к Vadim Yoockin:
VY>> Мне, например, только за счет препроцессинга удалось довести сжатие
VY>> некоторых больших exe-шников szip'ом до уровня cabarc'a. Специально
VY>> поправленный bzip2 вместе с тем же препроцессором тоже близок к таким
VY>> результатам (ему бы еще арифметический дожиматель...).
VY>> Вроде я уже кидал сюда цифры. Или нет?
BZ> Вроде ты об этом говорил. А алгоритмы?
Алгоритм я тоже, кажется, вкратце описывал: E8, распознавание всякого
рода табличек, плавающий размер блоков... В принципе, я собираюсь это
дело предать гласности. Hадо только привести все в божеский вид.
VY>> Еще можно, хотя не хочется из-за тормозов в расжатии, применить LZP.
VY>> Впрочем, спорить не буду, адаптивные способности BWT отстают от LZ.
BZ> bwt проигрывает lzh из-за большего размера блоков.
Сильно уменьшить блок не стоит - сжатие bwt быстро ухудшается,
а sliding window в bwt не сделаешь.
BZ> Hадо искать способ передавать информацию от блока к блоку
Пока не знаю, как это сделать достаточно эффективно.
Для bwt ведь важно не только дожатие, но и чтобы все контексты
кучковались вместе, в одном блоке.
BZ> (для хаффмена, кстати, такие способы есть).
Знаю, что можно кодировать только изменения дерева, но сам
ни разу не пробовал это делать. Hе расскажешь в общих словах?
Всего доброго. Vadim Yoockin
... 2.000.000 Lemmings can't be wrong.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
[an error occurred while processing this directive][an error occurred while processing this directive]