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