Предыдущий блок Следующий блок Вернуться в индекс
 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)
 Предыдущий блок Следующий блок Вернуться в индекс