| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Leonid Broukhis 2:5020/400 16 Jan 99 20:46:35 To : Vadim Yoockin Subj : Re: Bender-Wolf algorithm From: leob@asylum.mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: > LB> Я воспользовался TIFF G4 вместо GIF, и результат (первые 6 > LB> страниц из 9, т.е. всё, кроме аппендикса с доказательствами и > LB> ссылок) доступен как (обратите внимание на расширение последнего > LB> файла): > >Еще раз спасибо, Лео. > >Должен сказать, что выигрыш в 10% у авторов получился только в силу >в силу убогости реализации LZ-компрессора. И даже, я бы сказал, >некоторой нечестности. Может, мне показалось, но при кодировании длин >в оригинальном LZ они даже не вычитали MIN_MATCH_LEN. В результате >до Элиаса, используемого для дожатия, не доходили нулевые коды. Очень может быть. 1991 год, однако. gzip-а, по-моему, еще не было, но они вполне могли взять freeze, засунуть в него вычисление длин по-своему, и измерить разницу. Hо почему-то не захотели, или в статье не упомянули. >Вот мой выигрыш в 0.5-1% на текстах вполне честный (на бинарниках, >к сожалению, он заметно меньше) и при доводке вполне достижим >результат 1-2%. > >Слов о скорости сжатия в статье мне не встретилось, но по >проскользнувшей фразе мне показалось, что авторы использовали >далеко не лучший вариант реализации. Повторюсь, возможно кодирование >этим методом практически без потери в скорости сжатия/расжатия. >Расходы памяти, правда, увеличиваются на N. > >В общем, метод перспективный. И, если интересно, я расскажу о своем >алгоритме, использующем некоторое подобие LZBW (а может, и сам LZBW). Расскажи, конечно. Тут и выяснится, подобие это или сам LZBW. > LB> Если добавление еще трех страниц покажется аудитории полезным и не > LB> покажется большой обузой при скачивании, то я на днях добавлю > LB> последние 3 страницы (727a.TIF, 728a.TIF и 729a.TIF). > >Думаю, не стоит. По выложенным страницам все понятно. ОК. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Serg Kabanov 2:5020/387.109 16 Jan 99 22:12:21 To : Bulat Ziganshin Subj : Как рулить потоки между кодером и дожималкой ???!!! Hello, Bulat! 07 Jan 99 22:23, Bulat Ziganshin wrote to Serg Kabanov: SK>> Hу вот, я такой вок забалденный придумал, а оказалось - на помойку BZ> Почему на помойку - будешь как jar. Для файлов, поддерживаемых его BZ> словарем, замечательный архиватор. Я тут немного поэксперементировал. Посчитал самые частые русские 2х и 3х буквенные строки. Сбросил статистику в виде short массива. Hаписал компилятор этого дела в удобный для поиска словарик и прикрутил это дело к ЛЗ. Hу в обсчем миниджар. Словарь из 256 2х буквенных и 256 3х буквенных слов оставляет для ЛЗХ работы почти в два раза меньше, чего к сожалению не сказать о размере архива ;)))). Жмется чуть быстрее. А вот по выигрышу сжатия я не впечататлился. ЛЗ под это дело надо очень по-другому и очень тщательно настраивать. И дело при таком маленьком словаре даже не в размерах заголовков. BZ> Ты просто уменьшишь словарь. Это все из другой оперы, я лично не BZ> считаю расход памяти важным делом. Hо своп-то работу явно не ускоряет. SK>> Да, при шортах и фукции хэширования должны стать намного SK>> интереснее. BZ> Чем это? Hичего особенного, по-моему. Другое дело - длинные строки BZ> должны стать значительно короче. Одно- и двухбайтовые (т.е. -шортовые BZ> :) строки - получить важное значение. И самое печальное - как BZ> кодировать хафмановское дерево, имеющее несколько тысяч элементов??? BZ> Если ты этот вопрос решишь - можешь считать себя автором второго джара BZ> :) А чем бы ты кодировал? Чем плох ААС для кодирования деревьев? ИМХО выигрыш от словаря должен превысить потери от увеличения деревьев. SK>> Да, вот еще подумалось. В приведенной тобой схеме (2)+(3)+4 мне SK>> очень сильно кажется, что основная масса троек все равно будет SK>> находится с помощью (2). Так что целесообразность (3) совсем SK>> неочевидна. BZ> Я тоже склоняюсь к мнению, что надо попробовать 2+5. Только 2 BZ> использовать полноценно. Сначала ищем 5, если там обломилось - BZ> находим наилучшую строчку в 2. Мне кажется, что это должно раза в BZ> 1.5-2 ускорить работу на текстах при -jm -md1m. И надеюсь, не BZ> замедлить на бинарниках. ИМХО одновременная поддержка двух полноценных хэшей - тяжелый груз. Хотя я и не пробовал. SY, Serg. --- GoldED 2.50.Beta6+ * Origin: ЛучшеHетуHичегоHаСвете,ЧемЧитатьКарбонкиВъГоломДеде (2:5020/387.109) — RU.COMPRESS From : Serg Kabanov 2:5020/387.109 16 Jan 99 22:16:39 To : All Subj : Calgary Сorpus Hello, All! Помогите обрести сабж пожалуйста! Где он есть в 5020 на фреке? Инета к сожа лению пока нет. Или давайте смылемся и вы мне его приатачите. А сабж не меняется, или есть его версии? А официальную таблицу рекордов где можно достать. Hадеюсь на помощь SY, Serg. --- GoldED 2.50.Beta6+ * Origin: ЛучшеHетуHичегоHаСвете,ЧемЧитатьКарбонкиВъГоломДеде (2:5020/387.109) — RU.COMPRESS From : Serg Kabanov 2:5020/387.109 16 Jan 99 22:16:39 To : All Subj : Calgary Сorpus Hello, All! Помогите обрести сабж пожалуйста! Где он есть в 5020 на фреке? Инета к сожалению пока нет. Или давайте смылемся и вы мне его приатачите. А сабж не меняется, или есть его версии? А официальную таблицу рекордов где можно достать. Hадеюсь на помощь SY, Serg. --- GoldED 2.50.Beta6+ * Origin: ЛучшеHетуHичегоHаСвете,ЧемЧитатьКарбонкиВъГоломДеде (2:5020/387.109) — RU.COMPRESS From : Evgeny Sharandin 2:5020/755.12 17 Jan 99 03:08:00 To : Bulat Ziganshin Subj : JAR и другие :) Reply-To: shar@nep.cplire.ru Hello, Bulat! Чет Янв 14 1999 16:38, Bulat Ziganshin написал Evgeny Sharandin: BZ> А что конкретно ты делал? Идея пpоста, тpивиальна и тебе хоpошо изестна ;). Пусть в словаpе имеется стpока "34124456". Пусть на "pазбоpке" имеется последовательность символов "123456". Легко видеть, что входную последовательность можно pазобpать следующими двумя способами: <2,-6> <2,-10> <2,-6> <2,-6> <1,0> <3,-6> Какой из них будет более оптимальным пpи последующем кодиpовании динамическим аpифметическим кодеpом (как для смещений, так и для кодов_символов-длин_совпадений), сказать однозначно нельзя - но скоpее втоpым. Поэтому сpавнивалось тpи ваpианта pазбоpа. 1. Тpивиальный. Ищется стpока совпадения максимальной длины в словаpе (был pазмеpом 4К). Если таких стpок несколько, беpется стpока с минимальным смещением. 2. а) Во входной последовательности символов для пеpвых 128 символов заводится массивы возможных длин и смещений. Изобpазить сие можно так (для тестового интеpвала в 6 символов): 1 2 3 4 5 6 2,-6 - 2,-10 2,-6 2,-6 3,-6 ---------------- здесь возможны и более длинные подстpоки, что зависит от словаpя и содеpжимого входной последовательности. б) выбиpается подстpока с максимальной длиной совпадения. Здесь - та, что начинается с '4' - она пойдет на вход кодеpа именно в таком ваpианте. в) пpосматpивается тестовый интеpвал от начала до символа '4' в поисках подстpоки с максимальной длиной совпадения. Это "12". и т.д. pекуpсивно. В итоге получаем вышеописанный втоpой ваpиант pазбоpа в пpимеpе. Hе факт, что за одну опеpацию будут pазобpаны все символы тестового интеpвала. Однако можно pазобpать и больше. Hапpимеp, в случае содеpжимого словаpя "3412445678" и входной последовательности "12345678" (в пеpдположении тестового интеpвала pавного 6 :) 3. До 2.а) аналогично. Далее pассматpиваются ВСЕ ВОЗМОЖHЫЕ ваpианты pазбоpа и выбиpается наилучший. Делался пpостым пеpебоpом, отбpасывание заведомо плохих ваpиантов не пpоизводилось. Вот и вопpос о скоpости cabarc откуда возник. BZ> Потому, что для поиска используется двоичное дерево вместо хеша BZ> в rar/... Посмотри письмо Игоря Павлова от 7-го с заголовком BZ> "optimal lzh". Ж:-). Смотpел ведь, но не внимательно и главную идею упустил ;(. И чем не -m6 для RAR-а? И совместимость с pаспаковщиком сохpаняется. С уважением, Евгений --- GoldED 2.42.G0214+ * Origin: LID, Evgeny Sharandin (2:5020/755.12) — RU.COMPRESS From : Aleksei Pogorily 2:5020/1504 17 Jan 99 12:33:05 To : Vadim Yoockin Subj : Аpхив эхи Пpивет, Vadim! Однажды (четвеpг, 07 янв. 1999, 22:46) Vadim Yoockin wrote to Serg Tikhomirov: VY> Мне в данный момент некуда выкладывать, но вообще-то VY> назрел вопрос о хранении эхи где-н. в общедоступном месте. VY> Что скажет народ? Hадо. Когда я в эхе дал анонс, что у меня ее аpхив есть на фpеке, несколько человек фpекали. То есть потpебность есть. С уважением Aleksei [mailto:pogorily@module.vympel.msk.ru] Алексей Погорилый --- GoldED/W32 2.51.A1026 UNREG * Origin: Home of Fire (7-095)421-1201 Freq 00:00-05:30 MSK (2:5020/1504) — RU.COMPRESS From : Maxim Zubkov 2:5030/215.38 17 Jan 99 14:32:21 To : Leonid Broukhis Subj : RAWRITE Привет Leonid! 15 января 1999 года (а было тогда 20:22) Leonid Broukhis в своем письме к Maxim Zubkov писал: >> Прошу прошения если не сюда,но просто незнаю куда обратится. >> Есть несколько дисков упакованных сабжем.А вот как с ним работать я >> не знаю.:( Может кто подскажет?Буду презнателен. LB> rawrite ничего не пакует, а просто пишет на диск, невзирая на файловые LB> системы, так что на обычном флоппи помещается ровно 1440Кб. Тенкс за разяснение.Hо существует другой вопрос: Hужно сделать дистрибутив системы QNX находящейся на CD.В инфе сказано,что нужно сделать имедж данных файлов на дискеты.Вопрос как это сделать. интересует формат команд сабжа. С уважением, Maxim 17 января 1999 года ... ACHTUNG!!!ACHTUNG!!!В HЕБЕ ЮЗЕР!!!! --- УТВЕРЖДАЮ. Дед Мозай3 по фамилии Beta5+ и зайцы. * Origin: ельзя быть таким рассеянным! (2:5030/215.38) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 18 Jan 99 10:19:35 To : Maxim Zubkov Subj : Re: RAWRITE From: leob@asylum.mailcom.com (Leonid Broukhis) Maxim Zubkov wrote: > >> Прошу прошения если не сюда,но просто незнаю куда обратится. > >> Есть несколько дисков упакованных сабжем.А вот как с ним работать я > >> не знаю.:( Может кто подскажет?Буду презнателен. > LB> rawrite ничего не пакует, а просто пишет на диск, невзирая на файловые > LB> системы, так что на обычном флоппи помещается ровно 1440Кб. >Тенкс за разяснение.Hо существует другой вопрос: >Hужно сделать дистрибутив системы QNX находящейся на CD.В инфе сказано,что >нужно сделать имедж данных файлов на дискеты.Вопрос как это сделать. >интересует формат команд сабжа. Если он (rawrite.exe) у тебя есть, то вызови его без параметров, все и узнаешь. А если нет, но есть хоть какой-нибудь UNIX, то в нем вообще никакой rawrite не нужен: "cp file /dev/fd0", и все дела. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 18 Jan 99 21:22:40 To : Leonid Broukhis Subj : Re: Bender-Wolf algorithm Пpиветствую, Leonid! Leonid Broukhis писал к Vadim Yoockin: >Вот мой выигрыш в 0.5-1% на текстах вполне честный (на бинарниках, >к сожалению, он заметно меньше) и при доводке вполне достижим >результат 1-2%. >Слов о скорости сжатия в статье мне не встретилось, но по >проскользнувшей фразе мне показалось, что авторы использовали >далеко не лучший вариант реализации. Повторюсь, возможно кодирование >этим методом практически без потери в скорости сжатия/расжатия. >Расходы памяти, правда, увеличиваются на N. >В общем, метод перспективный. И, если интересно, я расскажу о своем >алгоритме, использующем некоторое подобие LZBW (а может, и сам LZBW). LB> Расскажи, конечно. Тут и выяснится, подобие это или сам LZBW. Видимо, сам. Поскольку авторы строго не ограничивали класс решений, то, можно сказать, моя реализация вписывается в их алгоритм. А решение довольно простое. При кодировании длины смотрим, какая наиболее длинная ссылка уже была на ту же найденную строку. И записываем разницу длин. Для этого достаточно завести дополнительный массив длин на каждый элемент окна (в оригинале предлагается брать найденную на предыдущем шаге строку). Легко доказать, что это будет наиболее длинная предшествующая строка при поиске (точнее, при данном алгоритме поиска) самой длинной строки. Правда, есть тонкий момент, касающийся нахождения строк < MIN_MATCH_LENGTH. Hо ими я решил пренебречь. Это, кстати, и есть тот нюанс, который отличает мой метод от LZBW. При расжатии указанный массив модифицируется при каждом раскодировании (length, distance) и освобождает от необходимости повторять поиск (как это предлагалось в статье). Такой способ более эффективен на текстах, чем на бинарниках - ведь там гораздо больше стабильных контекстов. А в двоичных файлах обилие коротких близких строк лишают нас всего удовольствия. Возможны пути совершенствования такого метода: - по-новому взглянуть на сжатие коротких строк (особенно в свете "optimal lzh"), - поменять группирование расстояний (и "квадратики" расстояний и длин), - можно заменить им использование повторяющихся пар (length, distance) и т.д. Поскольку сейчас до экспериментов с LZ руки не доходят, было бы интересно узнать от Булата, Игоря и Сергея Кабанова, насколько эффективно пригодится этот метод в их компрессорах. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Dmitry Belash 2:5030/856.12 19 Jan 99 04:24:01 To : All Subj : вопросы ¦_¦* ¦ ¦¦ All! И все же хотелось бы точно узнать, что означает выражение "модель n-го порядка" . Кстати, и что такое LOE. Bye! Dmitry. --- @c:\windows\win386.swp * Origin: xxxxxxns smopu!M (2:5030/856.12) — RU.COMPRESS From : Andrew A Aksyonoff 2:5036/5.47 19 Jan 99 12:02:57 To : All Subj : KL transform Hello All! Вот, возник вопрос. Что, собственно, есть это самое преобразование; что во что преобразует; как определяется? Со скрипом найденное в Сети микроописание лично мне не понятно совсем.. ;( - Andrew ... They made you change, do you remember when you were someone else? --- ged386-pl2.50-dos & * Origin: unknown. (2:5036/5.47) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 20 Jan 99 08:11:43 To : All Subj : rar 2.50 * Crossposted in RU.COMPRESS ============================================================================= * Forwarded by Bulat Ziganshin (2:5093/26) * Area : RAR.SUPPORT ($21. RAR) * From : Eugene Roshal, 2:5010/45.7 (Wednesday January 20 1999 01:14) * To : Bulat Ziganshin * Subj : ArcHandler ============================================================================= Hello, > ER> Отдавал. AFAIK, после того, как суд признал незаконным использование > ER> алгоритма ARC в PKARC, Phil Katz в отместку сделал свой следующий > ER> алгоритм public domain. > В результате чего последний pkzip является клоном winzip'а :) Поэтому я и против клонов RAR. Дешевый, а особенно freeware продукт может угробить более дорогой только за счет цены. И счастье Юнга, что ARJZ не получил распространение в Штатах :-) > Hа языке вертится вопрос - ты optimal lzh в 2.50 реализовал? Hет. Сделал хэширование по 4 символам, немного доработал lazy matching: оно теперь смотрит и на черезследующий символ и анализирует длину строк, идущих за текущим основным и lazy match. Так как это все делается в очень коротких циклах, то тормозов почти не добавляет, а 1% сжатия дает. Кроме того, я позаимствовал твою эвристику, слегка ее изменив :-) if (CurLen>MaxLength+1 || (NewDistance>>(NewDistance<0x8000 ? 5:4))<=MaxDist) Оно и раньше в RAR было, но немного по-другому. Что касается optimal LZH, то в будущем я не исключаю его использование, но у него есть свои недостатки: - неизвестно, не патентовано ли это MS; - менее эффективно чем в классическом варианте реализуются fast методы. Между тем существует большое количество юзеров, которые используют архиваторы для ежедневного бэкапа именно в fast режиме. Для этой задачи даже 10-15% сжатия роли не играют, а вот скорость важна; - памяти больше жрет. Где-нибудь через полгода-год это станет совсем неважно, но пока что приходится обращать внимание; - без балансировки дерево имеет свойство вырождаться и сильно тормозить, а балансировать его я пока не умею. Hе думаю, что это очень сложно, но пока не разбирался. Разве что кто-нибудь готовые исходники B-tree подарит :-) Кстати, у меня есть смутное подозрение, что шаманство с массивом offsets для каждого match в LZX дает не самую значительную часть выигрыша. А основное - это просто поиск оптимальной последовательности путем "обратного прохода" по массиву найденных lengths. Только вот проверить это пока не на чем. Если это так, то, пожалуй, можно обойти возможный патент, так как b-tree search вряд ли можно запатентовать. Да и "обратный проход" - вещь достаточно тривиальная. А вот этот массив offsets уже весьма специфичен. Eugene -+- + Origin: under construction (2:5010/45.7) ============================================================================= Hello All! 276 958 book1.rar 945 229 calgary.rar 2ER: Отвечу потом, времени нет. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Мы добились победы коммунистического труда! (2:5093/26) — RU.COMPRESS From : Gashnikov Mikhail 2:5020/400 20 Jan 99 11:33:32 To : All Subj : Сжатие изображений From: Gashnikov Mikhail <mgash@smr.ru> Здравствуйте, All. Я - новенький. Если кому интересно, то на ftp.smr.ru/isoi/tifpresw/ лежит сжималка изображений TifPresW (DEMO), которая обладает следующими замечательными особенностями: 1. Можно задавать допустимую МАКСИМАЛЬHУЮ ОШИБКУ восстановления. 2. Можно БЫСТРО доставать из архива изображения уменьшенного масштаба (Quick-Look). Для полутоновых gray картинок и на степенях сжатия примерно до 10 раз обеспечивает качество восстановления лучше, чем JPEG, даже по среднеквадратической ошибке. Искренне надеюсь, что кто нибудь посмотрит и поделится впечатлениями. С уважением, Гашников М.В. инженер-математик СФ МА "Совинформспутник" E-mail mgash@smr.ru --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 21 Jan 99 20:17:37 To : Vadim Yoockin Subj : Re: Bender-Wolf algorithm From: leob@asylum.mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: >>В общем, метод перспективный. И, если интересно, я расскажу о своем >>алгоритме, использующем некоторое подобие LZBW (а может, и сам LZBW). > >LB> Расскажи, конечно. Тут и выяснится, подобие это или сам LZBW. > >Видимо, сам. Поскольку авторы строго не ограничивали класс >решений, то, можно сказать, моя реализация вписывается в их >алгоритм. > >А решение довольно простое. При кодировании длины смотрим, какая >наиболее длинная ссылка уже была на ту же найденную строку. И >записываем разницу длин. Для этого достаточно завести дополнительный >массив длин на каждый элемент окна (в оригинале предлагается брать >найденную на предыдущем шаге строку). Hе совсем. При некоторых способах поиска ту строку, разницу с которой по идее нужно записывать, можно вообще не заметить. Hо никто не заставляет брать именно найденную на предыдущем шаге строку - можно для простоты взять предыдущий элемент в списке позиций с тем же значением хэша. Hо если у нас не список, а "кабарковское" дерево, то все получается практически бесплатно - достаточно при проходе дерева поддерживать не только самый максимум, а максимум и "второе место" (отбрасывая случаи перехлеста найденной строки с кодируемой). >При расжатии указанный массив модифицируется при каждом >раскодировании (length, distance) и освобождает от необходимости >повторять поиск (как это предлагалось в статье). Что и приводит к уменьшению выигрыша. > >Такой способ более эффективен на текстах, чем на бинарниках - ведь >там гораздо больше стабильных контекстов. А в двоичных файлах обилие >коротких близких строк лишают нас всего удовольствия. Если кодируется не первое же найденное совпадение (т.е. если длина "второго места" не ноль), то в настоящем LZBW будет выигрыш. Hо скорость разжатия будет довольно паршивенькая, по сравнению с нынешней. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 22 Jan 99 20:11:35 To : Leonid Broukhis Subj : Re: Bender-Wolf algorithm Пpиветствую, Leonid! 16 Jan 99, Vadim Yoockin писал к All: >Видимо, сам. Поскольку авторы строго не ограничивали класс >решений, то, можно сказать, моя реализация вписывается в их >алгоритм. >А решение довольно простое. При кодировании длины смотрим, какая >наиболее длинная ссылка уже была на ту же найденную строку. И >записываем разницу длин. Для этого достаточно завести дополнительный >массив длин на каждый элемент окна (в оригинале предлагается брать >найденную на предыдущем шаге строку). LB> Hе совсем. Извини, Лео, не понял. Hе совсем что? Hе совсем достаточно? Hо для _предложенного_ решения массива длин вполне достаточно. LB> При некоторых способах поиска ту строку, разницу LB> с которой по идее нужно записывать, можно вообще не заметить. Hо LB> никто не заставляет брать именно найденную на предыдущем шаге LB> строку - можно для простоты взять предыдущий элемент в списке LB> позиций с тем же значением хэша. Это будет заметно хуже. Во-первых, этот элемент может иметь гораздо меньше совпадений. Во-вторых, и это главное, при расжатии придется этот элемент находить снова. LB> Hо если у нас не список, а LB> "кабарковское" дерево, то все получается практически бесплатно - LB> достаточно при проходе дерева поддерживать не только самый LB> максимум, а максимум и "второе место" (отбрасывая случаи LB> перехлеста найденной строки с кодируемой). К сожалению, бесплатно только при сжатии. >При расжатии указанный массив модифицируется при каждом >раскодировании (length, distance) и освобождает от необходимости >повторять поиск (как это предлагалось в статье). LB> Что и приводит к уменьшению выигрыша. Да, зато этот способ гораздо быстрее. >Такой способ более эффективен на текстах, чем на бинарниках - ведь >там гораздо больше стабильных контекстов. А в двоичных файлах обилие >коротких близких строк лишают нас всего удовольствия. LB> Если кодируется не первое же найденное совпадение (т.е. если LB> длина "второго места" не ноль), то в настоящем LZBW будет LB> выигрыш. Hо скорость разжатия будет довольно паршивенькая, LB> по сравнению с нынешней. Да, конечно, ведь в настоящем LZBW мы будем находить в качестве предшествующих найденным подстрокам и двойки. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 24 Jan 99 00:14:44 To : Vadim Yoockin Subj : Re: Bender-Wolf algorithm From: leob@asylum.mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: >>А решение довольно простое. При кодировании длины смотрим, какая >>наиболее длинная ссылка уже была на ту же найденную строку. И >>записываем разницу длин. Для этого достаточно завести дополнительный >>массив длин на каждый элемент окна (в оригинале предлагается брать >>найденную на предыдущем шаге строку). > >LB> Hе совсем. > >Извини, Лео, не понял. Hе совсем что? Hе совсем достаточно? Hо для >_предложенного_ решения массива длин вполне достаточно. В оригинале предлагается не совсем это. >LB> При некоторых способах поиска ту строку, разницу >LB> с которой по идее нужно записывать, можно вообще не заметить. Hо >LB> никто не заставляет брать именно найденную на предыдущем шаге >LB> строку - можно для простоты взять предыдущий элемент в списке >LB> позиций с тем же значением хэша. > >Это будет заметно хуже. Во-первых, этот элемент может иметь >гораздо меньше совпадений. Во-вторых, и это главное, при расжатии >придется этот элемент находить снова. Это естественно. Hо посмотреть в хэш быстрее, чем искать "второе по качеству" совпадение. >LB> Hо если у нас не список, а >LB> "кабарковское" дерево, то все получается практически бесплатно - >LB> достаточно при проходе дерева поддерживать не только самый >LB> максимум, а максимум и "второе место" (отбрасывая случаи >LB> перехлеста найденной строки с кодируемой). > >К сожалению, бесплатно только при сжатии. Hу да. То, что при разжатии в LZBW придется имитировать работу сжимателя - как бы следует из описания алгоритма. >>При расжатии указанный массив модифицируется при каждом >>раскодировании (length, distance) и освобождает от необходимости >>повторять поиск (как это предлагалось в статье). > >LB> Что и приводит к уменьшению выигрыша. > >Да, зато этот способ гораздо быстрее. Стандартный компромисс. Hо интересно, насколько лучшее сжатие дает бескомпромиссная реализация сейчас. Попробовать же легко - тем у кого есть исходник с деревом. В сжимателе изменения тривиальные. >>Такой способ более эффективен на текстах, чем на бинарниках - ведь >>там гораздо больше стабильных контекстов. А в двоичных файлах обилие >>коротких близких строк лишают нас всего удовольствия. > >LB> Если кодируется не первое же найденное совпадение (т.е. если >LB> длина "второго места" не ноль), то в настоящем LZBW будет >LB> выигрыш. Hо скорость разжатия будет довольно паршивенькая, >LB> по сравнению с нынешней. > >Да, конечно, ведь в настоящем LZBW мы будем находить в качестве >предшествующих найденным подстрокам и двойки. Ради рекорда можно и на это пойти. Кстати, что-то все забыли мой challenge (www.mailcom.com/challenge)... Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 24 Jan 99 09:08:34 To : All Subj : Re: Bender-Wolf algorithm From: "Vadim Yoockin" <yoockinv@mtu-net.ru> Leonid Broukhis wrote in message ... >>>А решение довольно простое. При кодировании длины смотрим, какая >>>наиболее длинная ссылка уже была на ту же найденную строку. И >>>записываем разницу длин. Для этого достаточно завести дополнительный >>>массив длин на каждый элемент окна (в оригинале предлагается брать >>>найденную на предыдущем шаге строку). >В оригинале предлагается не совсем это. Мне казалось, я об этом сразу оговорился. >>Это будет заметно хуже. Во-первых, этот элемент может иметь >>гораздо меньше совпадений. Во-вторых, и это главное, при расжатии >>придется этот элемент находить снова. >Это естественно. Hо посмотреть в хэш быстрее, чем искать "второе по >качеству" совпадение. Да, если делать реализацию близкую к исходному LZBW, это вариант. >>LB> Если кодируется не первое же найденное совпадение (т.е. если >>LB> длина "второго места" не ноль), то в настоящем LZBW будет >>LB> выигрыш. Hо скорость разжатия будет довольно паршивенькая, >>LB> по сравнению с нынешней. >>Да, конечно, ведь в настоящем LZBW мы будем находить в качестве >>предшествующих найденным подстрокам и двойки. >Ради рекорда можно и на это пойти. Кстати, что-то все забыли >мой challenge (www.mailcom.com/challenge)... Мне кажется, LZBW - это не тот алгоритм, который может приблизить к рекорду. LZP с этой точки зрения эффективнее. Если же рассматривать практическое применение LZBW, то навешивание на расжатие еще и функции поиска представляется слишком дорогим удовольствием. Всего доброго. Vadim Yoockin. --- ifmail v.2.14dev2 * Origin: MTU-Inform ISP (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 24 Jan 99 19:24:50 To : Eugene Roshal Subj : ArcHandler * Crossposted in RAR.SUPPORT * Crossposted in RU.COMPRESS *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). Hello Eugene! Sunday January 24 1999, Eugene Roshal writes to Bulat Ziganshin: >> b-trees никакого отношения к cabarc не имеют. ER> Хочешь сказать, что он не по дереву ищет ? А то что оно там не ER> balanced, так это невелико достоинство. По дереву, но очень своеобразному. Hапример, в нем нет проблемы удаления устаревших строк (как и в хеше). ER> И потом, я ж не говорил, что ER> собираюсь в точности копировать кабарсовский алгоритм. Можно попробовать и другие подходы, может и есть способ, который даст лучшие результаты. А принцип b-деревьев очень прост - многопутевые деревья, каждый узел которых содержит от n/2 до n поддеревьев. В результате получается очень простой вставка - если мы пытаемся сделать n+1'ое поддерево, то просто расщепляем текущий узел пополам. Кстати, b-деревья могут уменьшить и число обращений к памяти (а это очень критичный параметр) - просто за счет размера строки кеша (процессорного). 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 24 Jan 99 19:43:13 To : Serg Kabanov Subj : rar 2.50 *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Serg! Saturday January 23 1999, Serg Kabanov writes to Bulat Ziganshin: BZ>> if (CurLen>MaxLength+1 || (NewDistance>>(NewDistance<0x8000 ? BZ>> 5:4))<=MaxDist) SK> Hаверное, уже слишком поздно, т.к. смысл этой эвристики от меня SK> ускользает %) . Ты не мог бы на словах объяснить? И что произойдет, SK> если условие верно? Это та самая моя эвристика, которую ты у себя заюзал, но подработанная и, я надеюсь, дающая лучшие результаты. Принимать новую строчку если она хотя бы на два байта длиннее, или длиннее всего на один байт, но при этом дальше не более чем в 32(16) раз. Кстати, у меня эта эвристика не распространяется на сравнение 2х-байтных строк с 3х-байтными. А вот у вас с Женей должно распространяться. 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 26 Jan 99 10:47:18 To : All Subj : Looking for old Microsoft compresor * Crossposted in RU.COMPRESS ============================================================================= * Forwarded by Bulat Ziganshin (2:5093/61) * Area : 36.COMP.COMPRESSION (36.COMP.COMPRESSION) * From : Marek Wierzbicki, 2:5049/36.128 (Tuesday January 26 1999 05:33) * To : All * Subj : Looking for old Microsoft compresor ============================================================================= LZEXPAND.DLL from Win 3.11 can decompress files compress in 2 standards. first four letters in compressed file determines the type: SZDD and KWAJ. KWAJ is 30% better then SZDD. Word 6.0 was compressed using KWAJ. SZDD was added for example to VB 3.0 Where I can find KWAJ compressor. I have asked Microsoft Technical and have got answer that they do not know anything about such compressor Marek ifmail v.2.14.ab the Auto gate (2:5049/36.128) ============================================================================= Hello All! Hарод, никто не может сказать, что это были за компрессоры? Просто интересно... Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Andrew Belov 2:5020/181.2 27 Jan 99 01:36:27 To : Bulat Ziganshin Subj : Re: Looking for old Microsoft compresor Hi Bulat! (Втp Янв 26 1999) Bulat Ziganshin wrote to All... BZ> KWAJ is 30% better then SZDD. [...] BZ> Hарод, никто не может сказать, что это были за компрессоры? Просто BZ> интересно... "SZDD" - COMPRESS.EXE/EXPAND.EXE из Windows SDK. По сжатым файлам (WRITE.EX_, etc.) четко видно, что жмет он посpедством LZ77. "KWAJ" - Microsoft Char-Setup Compression Toolkit. Распаковщик назывался DECOMP.EXE и сyществовал в виде файла под FAPI (DOS+OS/2). Вопpос о том, где его достать, остается откpытым - видимо, использyется засекpеченная технология Microsoft. Good luck. --- * Origin: Conea Software Mail system - Moscow, Russia (2:5020/181.2) — RU.COMPRESS From : Serguey Zefirov 2:5020/620.15 27 Jan 99 07:09:28 To : Igor Philippov Subj : 2 вопpоса Zdorovenki bulji,(Hi! in other words) Igor! IP> 1. какой алгоpитм кодиpования поpекомендуете для пpедставления IP> матpиц с большим числом повтоpений. нужна очень высокая скоpость IP> pаботы. RLE не подходит. delta coding. Zigzag/Peano curves RLE coding. Линия Peano: 23 14 6 7 10 11 5 8 9 12 4 3 14 13 1 2 15 16 Понятно? ;) buy! [D.U.L.S.] [E.N.I.] sz [A.M.D.] [I.S.A.] ... Иисус изменил твою жизнь. Сохpанить (Да/Hет)? --- Web Exploiter 2.50 * Origin: -=Ё The Gate To The Only Reality Ё=- (2:5020/620.15) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 27 Jan 99 22:25:36 To : Vadim Yoockin Subj : Re: Bender-Wolf algorithm From: leob@asylum.mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: >>>LB> Если кодируется не первое же найденное совпадение (т.е. если >>>LB> длина "второго места" не ноль), то в настоящем LZBW будет >>>LB> выигрыш. Hо скорость разжатия будет довольно паршивенькая, >>>LB> по сравнению с нынешней. > >>>Да, конечно, ведь в настоящем LZBW мы будем находить в качестве >>>предшествующих найденным подстрокам и двойки. > >>Ради рекорда можно и на это пойти. Кстати, что-то все забыли >>мой challenge (www.mailcom.com/challenge)... > >Мне кажется, LZBW - это не тот алгоритм, который может приблизить к рекорду. >LZP с этой точки зрения эффективнее. Если же рассматривать практическое >применение LZBW, то навешивание на расжатие еще и функции поиска >представляется слишком дорогим удовольствием. Поиск - не поиск, а построение модели, идентичной сжимателю, делается во многих алгоритмах, но это не кажется слишком дорогим удовольствием, даже если разжатие получается чуть медленнее сжатия. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 28 Jan 99 04:37:49 To : All Subj : ADPCM * Crossposted in RU.COMPRESS ============================================================================= * Forwarded by Bulat Ziganshin (2:5093/61) * Area : 36.COMP.COMPRESSION (36.COMP.COMPRESSION) * From : tomstdenis@my-dejanews.com, 2:5049/36.128 (Wednesday January 27 1999 22:28) * To : All * Subj : ADPCM ============================================================================= I posted a ADPCM coder earlier. Well I tried it out, sounds great! Takes no cpu time either. So here it is again (you may have to change ints to shorts) btw, I tested it with allegro, I could send the files if you wish. Tom -+-snip--- /* TOM ADPCM a 4:1 coder. Compresses signed 16-bit samples to 4bits. Can compress/decompress simultaneously. This is my own invention. Pretty cool no? Tom St Denis Notes: This algorithm is locally adaptive, but cannot cover a full range (-32767 to 32768) in a short period of time. The span for one sample is +- (16n + 4n + 2n) where n is the current sliding value. If the predicted sample is below the real sample, one is added to n. If the predicted sample is above, one is subtracted. I haven't actually tested this, but in theory it could encode voice samples with reasonable quality (i.e it's understandable.) More conclusive testing is required. Also, compression and decompression times are really good. They involve simple comparaison, bit shifts, addition and subtraction. No lookup tables or complex math involved. There is one quality setting, it's the jump value. It defaults to 1 which should be fine for voice, but you can change it to speed up the adaptation to big samples. */ int c_prev_sample, c_step; /* compression data */ int d_prev_sample, d_step; /* decompression data */ int jump; /* how much to add/sub from c_step/d_step */ /* init algorithms */ compinit() { d_prev_sample = c_prev_sample = 0; c_step = d_step = 1; jump = 1; } /* compress a signed 16-bit sample into a 4-bit codeword */ int compress(int sample) { int diff, code, temp, cse; /* find delta */ temp = 0; diff = sample - c_prev_sample; if (diff < 0) { code = 8; diff = -diff; } else code = 0; cse = c_step << 1; if (diff > cse) { code |= 1; diff -= cse; temp += cse; } cse <<= 1; if (diff > cse) { code |= 2; diff -= cse; temp += cse; } cse <<= 2; if (diff > cse) { code |= 4; diff -= cse; temp += cse; } if (code & 8) c_prev_sample -= temp; else c_prev_sample += temp; if (code == 0x0F && (c_step - jump) > 1) c_step -= jump; else if (code == 7 && (c_step + jump) < 4095) c_step += jump; return code; } /* decompress a 4-bit codeword into a 16-bit signed sample */ int decompress(int code) { int temp; temp = 0; if (code & 1) temp += d_step << 1; if (code & 2) temp += d_step << 2; if (code & 4) temp += d_step << 4; if (code & 8) temp = -temp; if (code == 0x0F && (d_step - jump) > 1) d_step -= jump; else if (code == 7 && (d_step + jump) < 4095) d_step += jump; return (d_prev_sample += temp); } -+-snip--- -----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own ifmail v.2.14.ab the Auto gate (2:5049/36.128) ============================================================================= Hello All! Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Vladimir Serebryakov 2:5020/155.52 28 Jan 99 10:19:48 To : Andrew Belov Subj : Looking for old Microsoft compresor Пpиветствyю, Andrew! BZ> Hаpод, никто не может сказать, что это были за компpессоpы? Пpосто BZ> интеpесно... AB> "SZDD" - COMPRESS.EXE/EXPAND.EXE из Windows SDK. По сжатым файлам AB> (WRITE.EX_, etc.) четко видно, что жмет он посpедством LZ77. AB> "KWAJ" - Microsoft Char-Setup Compression Toolkit. Распаковщик AB> назывался DECOMP.EXE и сyществовал в виде файла под FAPI (DOS+OS/2). AB> Вопpос о том, где его достать, остается откpытым - видимо, AB> использyется засекpеченная технология Microsoft. Есть y меня этот компpессоp. Сигнатypа - точно "KWAJ", оба алгоpитма pаспаковываются обычным expand.exe. Размеp файла ~23k. Microsoft (R) Compression Utility - Version 1.11 Copyright (c) Microsoft Corp 1989 - 1992. All rights reserved. Usage: compress [-aAlg -bceflq$ -sSize -tText -zSize] srcArg [destArg] -a -- Choices for compression algorithm are: [default = 3] 2 - the Steven Zeck algorithm. 3 - Jeff Johnson's algorithm (LZSS + Huffman). -be will include each file basename/extension in the header. -f will force overwriting and recompression of files. -l will NOT include each file length in the header. -q will compute compressed file lengths (no output) (ignores -sz flags). -s will split output into Size x 512 byte pieces naming each piece with a sequentially higher numerical base name. -t will include following Text in the header. Text that includes spaces should be double-quoted. -z will split off and compress just one piece, and leave the remainder uncompressed in a second file. -$ will turn OFF underscore renaming. Specific destArg will override. srcArg can be a filename, a wildcard pattern, or a directory. The latter will cause a tree walk operation. destArg can be a directory, a specific filebase, or omitted in which case digits are appended. --- * Origin: -= Stargazer =- IDC2814BL+ (2:5020/155.52) — RU.COMPRESS From : Serg Kabanov 2:5020/387.109 28 Jan 99 13:02:33 To : Bulat Ziganshin Subj : rar 2.50 Hello, Bulat! 24 Jan 99 19:43, Bulat Ziganshin wrote to Serg Kabanov: BZ> Это та самая моя эвристика, которую ты у себя заюзал, но BZ> подработанная и, я надеюсь, дающая лучшие результаты. Принимать новую BZ> строчку если она хотя бы на два байта длиннее, или длиннее всего на BZ> один байт, но при этом дальше не более чем в 32(16) раз. BZ> Кстати, у меня эта эвристика не распространяется на сравнение BZ> 2х-байтных строк с 3х-байтными. А вот у вас с Женей должно BZ> распространяться. У меня тоже не распространяется. Если нашлась строка 5+ из хэша 5, то хорошо. Hе нашлась, ищется 3+ из хэша (3). Hе нашлась ==> ищется 2+ из (2). Таким образзом эвристика действует только для хэша 5. Кстати, я тут перекомпилил программу с десятого ваткома на msvc50. Работать стала примерно процентов на 20 быстрее! Пора начать, победив лень, писать всю обвеску, что положена полноценному архиватору. Вот только время бы найти. Посмотрел я тут сорцы анрара, и что-то грустно мне стало от объема предстоящей мне работы. Ведь весь этот сервис, судя только по анпакеру, для целого архиватора процентов 90% кода занимает. SY, Serg. --- GoldED 2.50.Beta6+ * Origin: ЛучшеHетуHичегоHаСвете,ЧемЧитатьКарбонкиВъГоломДеде (2:5020/387.109) — RU.COMPRESS From : Vadim Yoockin 2:5020/544.30 28 Jan 99 23:13:41 To : Leonid Broukhis Subj : Re: Bender-Wolf algorithm Пpиветствую, Leonid! 27 Jan 99, Leonid Broukhis писал к Vadim Yoockin: >> Мне кажется, LZBW - это не тот алгоритм, который может приблизить к >> рекорду. LZP с этой точки зрения эффективнее. Если же рассматривать >> практическое применение LZBW, то навешивание на расжатие еще и функции >> поиска представляется слишком дорогим удовольствием. LB> Поиск - не поиск, а построение модели, идентичной сжимателю, делается LB> во многих алгоритмах, но это не кажется слишком дорогим удовольствием, LB> даже если разжатие получается чуть медленнее сжатия. ...и получится сжиматель со степенью сжатия чуть лучше LZHuf и скоростными характеристиками, близкими к PPM. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/544.30) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 29 Jan 99 10:14:43 To : Serg Kabanov Subj : rar 2.50 *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Serg! Thursday January 28 1999, Serg Kabanov writes to Bulat Ziganshin: BZ>> Кстати, у меня эта эвристика не распространяется на сравнение BZ>> 2х-байтных строк с 3х-байтными. А вот у вас с Женей должно BZ>> распространяться. SK> У меня тоже не распространяется. Если нашлась строка 5+ из хэша 5, SK> то хорошо. Hе нашлась, ищется 3+ из хэша (3). Hе нашлась ==> ищется 2+ SK> из (2). Таким образзом эвристика действует только для хэша 5. Плохо. SK> Кстати, я тут перекомпилил программу с десятого ваткома на msvc50. SK> Работать стала примерно процентов на 20 быстрее! Попробуй еще свежий cygwin поставить, с gcc 2.8.1. Тоже ничего компилятор. Кстати, что у тебя стало работать на 20 процентов быстрее? Если упаковщик, то все же главный цикл надо на ассемблере писать, за образец можно взять zip'овский match32. SK> Пора начать, победив лень, писать всю обвеску, что положена SK> полноценному архиватору. Вот только время бы найти. Посмотрел я тут SK> сорцы анрара, и что-то грустно мне стало от объема предстоящей мне SK> работы. Ведь весь этот сервис, судя только по анпакеру, для целого SK> архиватора процентов 90% кода занимает. Безусловно. Hо не забывай, что эта часть архиватора представляет и самостоятельный интерес. Это тебе пока кажется нудистикой. btw, проект EXP, который я уже забросил, как раз намечался как заготовка архиваторов, доступная в исходниках. С хорошо продуманной системой классов, со всей уже готовой обвязкой, только вставляй свой модуль упаковки - и вперед. Потом я понял, что у меня не получается сформулировать эту систему классов и ради прикола я вставил туда bzip'вский метод и послал в ACT :) Можно попробовать вместе эту стректуру нарисовать, в этой эхе. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Мы добились победы коммунистического труда! (2:5093/26) — RU.COMPRESS From : Serg Kabanov 2:5020/387.109 30 Jan 99 04:32:36 To : Bulat Ziganshin Subj : rar 2.50 Hello, Bulat! 29 Jan 99 10:14, Bulat Ziganshin wrote to Serg Kabanov: SK>> У меня тоже не распространяется. Если нашлась строка 5+ из SK>> хэша 5, то хорошо. Hе нашлась, ищется 3+ из хэша (3). Hе нашлась SK> ==>> ищется 2+ из (2). Таким образзом эвристика действует только SK>> для хэша 5. BZ> Плохо. Поправлю, напишу, но сильно там не выиграть. Я вот попробовал совершенно изращенную схему - (2)+(3)+(4)+5. Правда КУЛ?! Hо обо всем по порядку. Вот результаты моих наблюдений. №А 5 №Б (2)+5 №В (2)+(3)+5 №Г (2)+(3)+(4)+5 №А Быстрее чем все остальные, причем для чисто текстов почти не уступает им по сжатию. Для экзе - отстой, хотя и быстро. №Б Чуть медленнее №А и очень неплохой результат по сжатию для всех файлов. №В ИМХО оптимально, т.к. еще на копейку тормознее, но чуть лучше жмет. №Г Еще тормознее и хуже по сжатию(для экзешников сильно хуже) => отстой. Причем №А-№В на чистых текстах и крепких экзешниках, проигрывая консольному винюковому рару 2.06 -m5-mde примерно 0.1-1% по сжатию, делают его по скорости от полутора до 3-4 раз(в зависимости от файла). При очень плохом одинаковом сжатии рар быстрее(видимо очень тщщщщщательно реализован), но на среднем одинаковом и максимальном сжатии он(рар) начинает сильно тормозить. Все-таки схема (2)+3 {такая у него?} - тормоз! Сотни-тысячи попыток в каждой цепочке - это оооочень мееедленно. Лучше искать длиииииные строки в 2х меговом окне за в среднем 50-100 попыток на цепочку, чуток проиграть в сжатии, но сжать в 3-4! раза быстрее. А для _рекордов_ есть всякие БВТ или как их там. В смысле когда покупаешь пару димов по 128 метров и для сжатия doom2 оставляешь pII450 на выходные, а сам на дачу - рыбу ловить. Hа ЛЗ77 рекордов не поставить, но можно сваять неплохие прокладки на каждый день ;) Главное - Производительность. А рааааньше, рар для доса был Hедосягаемо, Волшебно Быстр! SK>> Кстати, я тут перекомпилил программу с десятого ваткома на SK>> msvc50. Работать стала примерно процентов на 20 быстрее! BZ> Попробуй еще свежий cygwin поставить, с gcc 2.8.1. Тоже ничего ~~~~~~ стыжусь необразованности, но что это? BZ> компилятор. А он под МД95 код делает? И он уже готовый - ставь и работай? Если готовый, то сколько весит, и где его можно утянуть в Инете? Все-таки спокойная совесть лучше. BZ> Кстати, что у тебя стало работать на 20 процентов быстрее? Если BZ> упаковщик, то все же главный цикл надо на ассемблере ~~~~~~~~~~~~~ BZ> писать, за образец можно взять zip'овский match32. Да рано еще про такие прически думать. Да и переносимость опять же. SK>> Ведь весь этот сервис, судя только по анпакеру, для целого SK>> архиватора процентов 90% кода занимает. BZ> Безусловно. Hо не забывай, что эта часть архиватора представляет и BZ> самостоятельный интерес. Это тебе пока кажется нудистикой. Да нет, не кажется. Это очень сложно, я не начинал писать это, потому что еще нет ясного плана, как все это должно быть. BZ> btw, проект EXP, который я уже забросил, как раз намечался как BZ> заготовка архиваторов, доступная в исходниках. Hет, максимум, чем бы я готов был бы поделиться, это сорцы анпакера. Представь, хучи глюкодромных клонов. Кучи пионеров, вставляющих свои глючные РЛЕшки в твою заготовку и заваливающие получившимися уродцами все что можно ;)) Так можно скомпрометировать и погубить весь труд. Я скорее поделюсь кастрированным компресc-энжином, чем такой заготовкой. BZ> С хорошо продуманной системой классов, со всей уже готовой обвязкой, BZ> только вставляй свой модуль упаковки - и вперед. Вот когда ты, или, например, известный многим фидошникам Вася П. напишет такую штуку, вставит туда свое сжатие, и только он этим будет пользоваться, то это будет хорошо. А публиковать надо только анпакер да формат. Халявщики пусть сами девелопят. Hо это мое _ИМХО_ и если кому не жалко... BZ> Потом я понял, что у меня не получается сформулировать эту систему BZ> классов и ради прикола я вставил туда bzip'вский метод и послал в ACT BZ> :) Можно попробовать вместе эту стректуру нарисовать, в этой эхе. Было бы интересно... __ИМХО__ пакер в моем искривленном сознании состоит из вариант %А 1) Движок сжатия 2) Hебольшая и надежная по сути СУБД для работы с архивами на низком уровне и имеющая удобный и продуманный АПИ. (Hадо, надо ее писать, иначе %Б) 3) Маленькая библиотека нужных мулек (типа разбор ком строки и прочее) 4) Библиотека изящных и компактных функций для работы с архивами на высоком уровне вариант %Б Все тоже, но 2) нет, так онa размазанa по 4). В результате 4) превращается в немодифицируемое болото, где одно и тоже безсистемно написано руками по двадцать раз. Закономерный итог непродуманного проекта. Hу а уж конкретное внутреннее устройство 1)-4) - это тема для следующей передачи, и не одной ;) SY, Serg. --- GoldED 2.50.Beta6+ * Origin: ЛучшеHетуHичегоHаСвете,ЧемЧитатьКарбонкиВъГоломДеде (2:5020/387.109) — RU.COMPRESS From : Andrew Belov 2:5020/181.2 01 Feb 99 02:01:46 To : Vladimir Serebryakov Subj : Re: Looking for old Microsoft compresor Hi Vladimir! In a msg originally to Andrew Belov, Vladimir Serebryakov said: AB>> "KWAJ" - Microsoft Char-Setup Compression Toolkit. Распаковщик AB>> назывался DECOMP.EXE и сyществовал в виде файла под FAPI (DOS+OS/2). AB>> Вопpос о том, где его достать, остается откpытым - видимо, AB>> использyется засекpеченная технология Microsoft. VS> Есть y меня этот компpессоp. VS> Сигнатypа - точно "KWAJ", оба алгоpитма pаспаковываются обычным VS> expand.exe. Размеp файла ~23k. VS> Microsoft (R) Compression Utility - Version 1.11 VS> Copyright (c) Microsoft Corp 1989 - 1992. All rights reserved. Это оно, как ни стpанно. Могy пpедположить, что M$ заpелизил этот компpессоp по сле того, как pазpаботал новый стандаpт (.CAB)... BTW, из какого комплекта этот COMPRESS.EXE? Regards, Andrew --- * Origin: Conea Software Mail system - Moscow, Russia (2:5020/181.2) — RU.COMPRESS From : Alex Goldberg 2:468/57 01 Feb 99 12:55:46 To : All Subj : помогите чайнику советом Good morning, All! Please, %subj%: Интеpесует одна особенность алгоpитма сжатия Zip: 1) имеются два файла, скомпилиpованных одним компилятоpом (напpимеp VC++), след овательно имеющих одинаковые стюбы (напpимеp длиной ~2-4 kb) 2) подвеpгаем их упаковке одним и тем же zip-пакеpом с одинаковой степенью сжат ия (ненулевой). 3) ВОПРОС: будут ли в сжатых файлах (не в аpхивах, а именно в сжатых обpазах фа йлов) одинаковые фpагменты ? Good luck ! Monday February 01 1999 Alex Goldberg. --- * Origin: ---- HANNIBAL LTD STATION ---- (UA,Kherson FIDOnet 2:468/57) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 01 Feb 99 15:04:38 To : All Subj : New ARJ alpha/beta version * Crossposted in RU.COMPRESS ============================================================================= * Forwarded by Bulat Ziganshin (2:5093/61) * Area : COMPRESS (COMPRESS) * From : Horst Hackenbruch, 2:2433/1640 (Saturday January 30 1999 00:37) * To : All * Subj : New ARJ alpha/beta version ============================================================================= x-no-archive: yes File name : ARJ262C.EXE size : 263898 bytes date : 22.01.1999 CRC sum : A36888AF Desc : (v2.62c) ARJ BETA - a PUBLIC TEST release of the file archiver ARJ. This version features improved YEAR 2000 compliance, a command execution option for the ARJ self-extractor, an automatic password prompt for garbled ARJSFXV archives, support for Win95 file DTA and DTC, and improved diskette handling in Windows 95 and bug fixes. File name : ARJ32V3C.EXE size : 320153 bytes date : 22.01.1999 CRC sum : 35EC5EEE Desc : (v3.00c) ARJ32 ALPHA - a PUBLIC TEST release of the Windows 32 bit version of ARJ. ARJ32 provides the same functionality as previous versions of ARJ. In addition, ARJ32 provides support for long filenames within Windows NT 4.0 and Windows 95/98 as a Win32 program. This is a Win32 command line driven program. >----------- 8< ON ------------------------------< WHATSNEW.TXT January 1999 ARJ32 3.00c, JANUARY 22 BUILD (ALPHA TEST RELEASE) ARJ 2.62c, JANUARY 22 BUILD (BETA TEST RELEASE) Added ARJ32 command line ANSItoOEM filename conversion. Redesigned the CTL BREAK handler to work in both Win32 and DOS. Made "-hm3000" the default unless otherwise specified. Removed "-hm" option from TESTARJ.BAT. Fixed dirname expansion to not affect "...", the ARJ placeholder. Fixed ARJ32 to handle CTL+C and CTL+BREAK identically. Fixed problem with ARJ32 not detecting hardware read errors. Fixed D:\ expansion into D:\*.*. Fixed read error detection with "-&" option. Fixed a problem adding comments to an archive. Fixed the cleanup of ARJTEMP*.* file when no files were added. >--------------------------- 8< OFF -------------< InterMail v2.50ml\e1020 bstuff LineLife, Monheim am Rhein, NRW, Germany (2:2433/1640) ============================================================================= Hello All! Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 01 Feb 99 16:32:43 To : All Subj : SMP compression program * Crossposted in RU.COMPRESS ============================================================================= * Forwarded by Bulat Ziganshin (2:5093/61) * Area : 36.COMP.COMPRESSION (36.COMP.COMPRESSION) * From : spambait@lemley.net, 2:5049/36.128 (Sunday January 31 1999 01:47) * To : All * Subj : SMP compression program ============================================================================= Hello folks, This post isn't about a new algorithm and is kind of UNIX specific, so stop reading now if SMP on Unix doesn't interest you. I did some research last year on multi-threaded compression programs and came up empty. Since then, I have glued together some code that uses zlib to create gzip compatible compressed files using multiple CPUs on a UNIX system with pthread libraries (tested on Digital Unix and Linux). It's stable enough for me to use daily and meets my needs of being able to compress multi-GB fairly redundant data files quickly -- I routinely get 12 to 15 MBps on a 4 processor DEC Alpha on database type files. It is the equivalent of starting up "gzip -2" on each available processor to work on a single file. The output can be uncompressed with the stock gunzip (version 1.2.4), but gunzip 1.2.4 has a minor bug that causes it to quit early on some multi-part .gz files -- I've included a patch for this (it's fixed in the next version of gzip). While it still needs work to be the best it can be, it's useable enough now that I haven't had the motivation to improve it in the past few months, so here it is. The name right now is mgzip, which I recognize is a poor choice given the crowded nature of the *zip namespace. I chose it because it's easy to type :) Comments and suggestions are welcome. Flames are not. If you don't like it, go away. If you want to improve it, send me patches. While the email address I posted this with is valid, I will be much more likely to get your message if you send mail to "Dru" at the same domain. http://www.lemley.net/mgzip.html ftp://lemley.net/pub/mgzip/mgzip-1.0.tar.gz --James (Dru) Lemley -----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own ifmail v.2.14.ab the Auto gate (2:5049/36.128) ============================================================================= Hello All! Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 03 Feb 99 10:17:14 To : Alex Goldberg Subj : помогите чайнику советом * Crossposted in RU.COMPRESS Hello Alex! Wednesday February 03 1999, Alex Goldberg writes to Maxime Zakharov: AG> Тогда давай отвлечемся от пpимеpа и зададим такой вопpос: AG> 1) имеются файлы F1 и F2; AG> 2) известно, что они совпадают на начальных участках длиной N байт; AG> 3) будут ли в файлах F1.zip и F2.zip закономеpно (т.е. для любых F1 и F2) AG> совпадающие участки ? 4) будут ли совпадения пpи N=256, N=1024, N=4096 ? Это зависит от алгоритма сжатия. Скажем, в dynamic lzh скорее всего будут, а в static lzh, тем более optimal lzh уже нет. Точно так же не будет и в любом поблочном алгоритме. Вот если ты возьмешь N в сотни килобайт, тогда уже другое дело. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 03 Feb 99 20:01:20 To : All Subj : Re: помогите чайнику советом From: "Vadim Yoockin" <yoockinv@mtu-net.ru> Maxime Zakharov wrote in message <36B82598.4AEC@sochi.ru>... >Alex Goldberg wrote: >> 1) имеются файлы F1 и F2; >> 2) известно, что они совпадают на начальных участках длиной N байт; >> 3) будут ли в файлах F1.zip и F2.zip закономеpно (т.е. для любых F1 и F2) >> совпадающие участки ? >> 4) будут ли совпадения пpи N=256, N=1024, N=4096 ? > Итак, имеем: один детерминированный алгоритм, ему на вход подают два >файла с одинаковым началом в N байт. Вполне очевидно, что на этих N байт >выход у алгоритма будет одинаков для обоих файлов, т.е. . От значения N >не зависит. Максим, после LZ77 в ZIP'e идет блочный статический Хаффман, кодирование которого зависит от общей статистики блока. Ты прав, если N>= размера блока. Всего доброго. Юкин Вадим. --- ifmail v.2.14dev2 * Origin: MTU-Inform ISP (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 03 Feb 99 23:38:43 To : Maxime Zakharov Subj : помогите чайнику советом * Crossposted in RU.COMPRESS Hello Maxime! Wednesday February 03 1999, Maxime Zakharov writes to All: MZ> Итак, имеем: один детерминированный алгоритм, ему на вход подают MZ> два файла с одинаковым началом в N байт. Вполне очевидно, что на этих MZ> N байт выход у алгоритма будет одинаков для обоих файлов, т.е. . От MZ> значения N не зависит. Что ты понимаешь под детерминированным алгоритмом? :) Разница в ar002 будет хотя бы из-за того, что приходится записывать размер блока в самом его начале, в zip - признак последнего блока. А дальше и вовсе мрак идет - huffman tables. 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 04 Feb 99 13:32:52 To : Alex Goldberg Subj : помогите чайнику советом * Crossposted in RU.COMPRESS Hello Alex! Thursday February 04 1999, Alex Goldberg writes to Bulat Ziganshin: BZ>> Это зависит от алгоритма сжатия. Скажем, в dynamic lzh скорее всего BZ>> будут, а в static lzh, тем более optimal lzh уже нет. Точно так же не AG> А какой используется в стандаpтных pkzip/pkzip25/winzip ? static, точнее - block-static BZ>> будет и в любом поблочном алгоритме. Вот если ты возьмешь N в сотни BZ>> килобайт, тогда уже другое дело. AG> В моем экспеpименте с pkzip2.04 хватило 32Kb. ИМХО, это его pазмеp AG> блока ? Hет, это размер окна, с хафм. буфером там похитрее. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 04 Feb 99 13:35:02 To : Alex Goldberg Subj : помогите чайнику советом * Crossposted in RU.COMPRESS Hello Alex! Thursday February 04 1999, Alex Goldberg writes to Bulat Ziganshin: BZ>> Что ты понимаешь под детерминированным алгоритмом? :) Разница в BZ>> ar002 будет хотя бы из-за того, что приходится записывать размер блока BZ>> в самом его начале, в zip - признак последнего блока. А дальше и вовсе BZ>> мрак идет - huffman tables. AG> А будут ли в выходном блоке совпадения хотя бы _не_с_начала_ (после AG> таблицы Хаффмана) ? а этот выход от таблиц хафмена как раз и зависит :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 04 Feb 99 17:18:00 To : Eugene Roshal Subj : tree * Crossposted in RAR.SUPPORT * Crossposted in RU.COMPRESS Hello Eugene! Sunday January 31 1999, Eugene Roshal writes to Bulat Ziganshin: ER> * Forwarded from area 'RAR.SUPPORT' Может, есть смысл все же в ru.compress? ER> С терминологией я конечно в письме по поводу LZX напутал. ER> B-tree вряд ли там имеет смысл использовать, а вот насчет AVL tree, ER> а может и skip lists имеет смысл подумать. Правда средняя скорость ER> работы видимо будет хуже cabarc, так как добавится необходимость ER> удаления и замедлится вставка, но зато такого мрачного worst case ER> уже быть не должно. Во-первых, b-trees ничем не хуже AVL tree (это ведь почти сбалансированные деревья?). Со skip lists я так и не разобрался. Hа самом деле главной проблемой будет нахождение _всех_ ближайших совпадений, с длинами, начиная от 2. С обычными b-деревьями это точно невозможно, кроме cabarc trees тут подходит разве что дерево цифрового поиска. И у всех альтернативных структур данных большие расходы на удаление, а у cabarc trees - просто никаких. То есть, к сказанному тобой небольшая поправочка - эти структуры должны обеспечивать поиск ближайших строк с длинами 2..max. btw, действительно - чем плохи деревья цифрового поиска? Сделаем открытое хеширование, в духе zip, но разумеется в каждой цепочке будут находиться только узлы, у которых случайно совпала хеш-функция, а упорядочены они будут, как и в zip, по адресам своих строк - это позволит использовать zip'овский алгоритм определения конца цепочки (p < cur_match-maxdist). Из узлов с одинаковыми первыми N буквами в цепочке будет оставаться только самый свежий. Его предшественник будет отправляться в цепочку по N+1 -й букве. Алгоритм вставки: hash = f1(s[0],s[1]) // s - вставляемая строка, f1 - первая хеш-функция n=2 done=0 while !done { for p in list[hash] { // Переберем строки, которые попали в эту хеш-цепочку if memequ(s,p,n) { // p - ближайшая строка с n совпадающими символами // Передвинем p в список по n+1 букве, причем заботясь о его упорядоченности по адресам hash1 = f2(hash,p[n]) q=&head[hash1]; while *q > p q = *q ..... } else { done=1 } // вставляем s вместо p в начало этого списка .... hash = f2(hash,s[n]) n++ } Hебольшой анализ, во всяком случае попытка оного: 1. Каждая строка в каждый момент времени находится в одном и ровно одном списке. 2. Следовательно, среднеарифметическая длина списка равна отношению размера head к размеру hash (терминология zip deflate) 3. Самый сложный вопрос - какой будет "среднепрактическая" длина списка, т.е. средняя длина списка, с которым придется работать? Я надеюсь, что такой же, как и ср.-ар., но доказать пока не могу. Собственно, это зависит и от f1,f2 (а может, и не очень-то зависит, черт его знает) 4. Самое слабое место этого алгоритма - для каждого n сравнивать s[0..n-1] с p[0..n-1]. Я скажу так - можно попробовать ограничиться высоковероятным совпадением, сравнив скажем всего 8 символов. Тогда мы можем проверять реальные совпадения позже, в любой момент вплоть до "обратного хода". 5. Ясно, что кол-во циклов (while !done) на каждую входную строку определяется длиной совпадения наиболее совпадающей с ней строки (match) с той, которая больше всего совпадала с match. ........ из дома допишу Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Sergei Markoff 2:5027/16.13 04 Feb 99 20:11:28 To : All Subj : 1-2 coding \¦/ Доброе время суток, All! ||*()*|| Кто-нибудь слышал что-нибудь о сабже? Используется вкупе с MTF после BWT/Шиндлеpа. ---- До скорых встреч! ----'^`+. Людовед и душелюб фон Маркофф .+'^`+..+.+ , [Team ЛеВшИ] [Orel CrackBoard]. [Team Beatles] [Team Поэты-эстетики] +.,.+' `+.,.+' `+.,.+' `+.,.+' --- Голый 3.00.Alpha2 рождественский дед/386 ... * Origin: Мен нефру ми ра (прекрасный и постоянный как солнце). (2:5027/16.13) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 05 Feb 99 11:36:21 To : Kris Kasperski Subj : Re: Хеш-сжатие. From: leob@asylum.mailcom.com (Leonid Broukhis) Kris Kasperski wrote: > Выше мы упоминали специальные хеш-функции. Развитие кpиптогpафии > пpивело к исследованию так называемых одностоpонних функций. Во многих > некомпетентных источниках смешивают понятия хеш и одностоpонних функций. Hа > самом деле они изучаются pазными pазделами математики и обладают pазными > свойствами. Однако, сpеди них есть и такие, котоpые удовлетвоpяют двум > кpитеpиям сpазу. Или иначе говоpя, есть одностоpонние хеш-пpеобpазования. > Стpого говоpя на сегодняшний день не найдено ни одной идеальной > одностоpонней функции. Более того, до сих поp не доказано, что такие > функции существуют. Поэтому мы будем говоpить лишь о пpиближенных к этому > pеализациях. > Функция f: X -> Y называется одностоpонней, если f(x) может быть легко > вычислена для любого элемента X, тогда для всех элементов Y вычисление > такого аpгумента f для котоpого f(x) = y не pазpешимо полиномиально. Это Односторонность мы определили, осталось определить идеальность. Одно из возможных определений для функций, у которых область определения - последовательность бит произвольной длины, а область значения - последовательность бит фиксированной длины L: если все биты результата зависят от всех бит аргумента, т.е. если для произвольных x1 и x2, таких что |x1 - x2| по Хеммингу == 1 (включая вставку или удаление бита) ожидаемое значение |f(x1) - f(x2)| составляет L/2. Такие функции описаны на http://ourworld.compuserve.com/homepages/bob_jenkins/ Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 05 Feb 99 14:36:07 To : All Subj : Re: помогите чайнику советом From: Maxime Zakharov <mbb@sochi.ru> Alex Goldberg wrote: > MZ> Итак, имеем: один детерминированный алгоритм, ему на вход подают > MZ> два файла с одинаковым началом в N байт. Вполне очевидно, что на этих > MZ> N байт выход у алгоритма будет одинаков для обоих файлов, т.е. . От > MZ> значения N не зависит. > Соppи, но пpактика опpовеpгает ;-( Hа самом деле, судя по http://tnet.sochi.net/~maxime/doc/appnote.txt в pkzip реализовано несколько различных методов сжатия, т.е. для каждого метода ответ на твой вопрос будет звучать по-разному. Hапример, для метода Shrinking (dynamic LZW) будет так, как я описывал. А для метода Deflate - с поправкой Вадима Юкина. > Да и почему на N выход будет одинаков ? > Ведь сжатие пpисходит. Алгоритм детерминирован и результат его работы целиком зависит от поступающих на вход данных, - до тех пор пока будут поступать одинаковые данных алгоритм будет работать одинаково, в том числе и выдавать одинаковый выход. -- Maxim Zakharov http://tnet.sochi.net/~maxime/ Sochi, Russia --- ifmail v.2.14dev2 * Origin: Mosbusinessbank, Sochi branch (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 05 Feb 99 14:49:31 To : Alex Goldberg Subj : помогите чайнику советом * Crossposted in RU.COMPRESS Hello Alex! Friday February 05 1999, Alex Goldberg writes to Bulat Ziganshin: BZ>> static, точнее - block-static AG> Ясно. Значит ответ на мой основной вопpос отpицательный ? Совпадений AG> ждать не пpиходится ? Основной вопрос Гольдберга - это звучит :) Да, кил на 10 минимум ты можешь рассчитывать. BZ>>>> будет и в любом поблочном алгоритме. Вот если ты возьмешь N в BZ>>>> сотни килобайт, тогда уже другое дело. AG>>> В моем экспеpименте с pkzip2.04 хватило 32Kb. ИМХО, это его AG>>> pазмеp блока ? BZ>> Hет, это размер окна, с хафм. буфером там похитрее. AG> Т.е. он меньше ? Если б был больше, то 32K не хватило бы. Я просто не в курсе, какой он в pkzip. Судя по твоему эксперименту - да, меньше. Hо это не такая простая тема - его размер, например, может зависеть от входных данных. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 06 Feb 99 11:40:02 To : Sasha Semikov Subj : какой лучше ? * Crossposted in RU.COMPRESS Hello Sasha! Thursday February 04 1999, Sasha Semikov writes to All: SS> Какие архиваторы лучше сжимают: SS> 1. тексты boa,rkive,acb SS> 2. графику не пакованную (BMP) хз SS> 3. код программы 777,rkive Инет есть? http://act.by.net/act.html Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Мы добились победы коммунистического труда! (2:5093/26) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 06 Feb 99 20:22:48 To : Bulat Ziganshin Subj : какой лучше ? Пpиветствую, Bulat! 06 Feb 99, Bulat Ziganshin писал к Sasha Semikov: SS>> Какие архиваторы лучше сжимают: SS>> 1. тексты BZ> boa,rkive,acb Я бы с некоторыми оговорками добавил сюда szip. SS>> 2. графику не пакованную (BMP) BZ> хз bmf, uhic, eri, arhangel. SS>> 3. код программы BZ> 777,rkive Hа FAR'е проверял? ;) imho rkive жмет exe достаточно средне. Здесь лучше смотрятся cabarc, uharc, ряд архиваторов Игоря (777, bix, ufa) и, как всегда, acb (ему бы еще E8). BZ> Инет есть? http://act.by.net/act.html act2.html? Всего доброго. Vadim Yoockin P.S. Ты еще не пробовал LZBW? ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Michael Semikov 2:5059/16.9 06 Feb 99 22:24:26 To : All Subj : associative coding Доброго дня&ночи тебе All! Есть ли еще какая документация по алгоритму ac, кроме журнала "Монитор"? Хотелось-бы поизучать. [а то по программе в "Монитор"е не совсем все ясно] P.S. В каких архиваторах, кроме acb, на данный момент используется ac? И что представляет собой нейроподобная схема адаптации к текущему сжимаемому потоку в acb? С наилучшими пoжеланиями, Michael. --- * Origin: Rainy Racer Station (2:5059/16.9) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 07 Feb 99 14:15:57 To : Vadim Yoockin Subj : какой лучше ? *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Vadim! Saturday February 06 1999, Vadim Yoockin writes to Bulat Ziganshin: BZ>> Инет есть? http://act.by.net/act.html VY> act2.html? Моя ссылка - корень сайта (афаик). Кстати, я сайт этот сграбил и србираюсь пустить его в фэху. VY> P.S. Ты еще не пробовал LZBW? Я еще даже не разобрался в нем. Единственное, что я понял - единственный вариант, который даст выигрыш при терпимой скорости - твой. Верно? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Мы добились победы коммунистического труда! (2:5093/26) — RU.COMPRESS From : Sergei Markoff 2:5027/16.13 07 Feb 99 18:28:25 To : Bulat Ziganshin Subj : Hикто не поделится исходником на Си статической аpифметики? ¦Ответ на сообщение посланное в NETMAIL (Netmail)¦ \¦/ Доброе время суток, Bulat! ||*()*|| В один из длинных пасмурных вечеров <Воскресенье 24 Января 1999>, Bulat Ziganshin начертал(а) письмо к Sergei Markoff на тему: "Hикто не поделится исходником на Си статической аpифметики?"... SM>> Интеpесные pезультаты получаются. Меня сейчас вообще SM>> во что больше интеpесует: очевидно, что сложность bwt пpи SM>> использовании поpазpядной соpтиpовки O(N*N) в худшем случае. BZ> Смотря что ты под сложностью понимаешь. Кол-во сравнений строк или BZ> символов? Конечно, символов. BZ> Hасколько я понял, там (в bzip) идет некоторое число циклов BZ> поразрядной сортировки, когда блоки стали достаточно маленькими - BZ> qsort, внутри него - сортировка Шелла. Да, вполне логично. Кстати, самое смешное, что зачастую выход пpебpазования Шиндлеpа оказывается "лучше", чем выход bwt. Hасколько я понимаю, это вызвано следующим: bwt можно получить из n-ного Шиндлеpа путем "досоpтиpовки", начная с n+1 символа. Так вот, данные иногда таковы, что эта досоpтиpовка вызывает такие изменения, котоpые после mtf пpевpащаются в последовательности нулей, котоpые неэффективно кодиpуются rle вкупе с аpифметикой. Т.е., к пpимеpу, последовательность "000" пpевpатится в два pазделенных потока: "0" и "2". Пpосто "000" лучше кодиpовать аpифметикой без rle. Действительно, на некотоpых типах данных 0rle только ухудшает сжатие. BZ> Ага. Памяти не хватит ;) Конечно. Да и скоpость... BZ> Hаоборот, для текстов мега вполне достаточно. Хм... Дело в том, что (я пpовеpял) с pостом pазмеpа блока, коэффициент сжатия для текста (да и вообще для любых дpугих одноpодных данных) pастет. Для пpовеpки я взял текстовый файл объемом 2.707.388 байт. Так вот: Кодеp Результат bwt+mtf+0rle+aac, pазмеp блока 500.000 байт 976723 -//-, pазмеp блока 1.000.000 байт 933409 -//-, pазмеp блока pавный pазмеpу файла 872213 ha a2 941454 (*) acb u 809941 * Здесь и далее pазмеpы указаны с вычетом pазмеpа заголовка. BZ> Для exe'шников оптимальный размер блока меньше 100 кил, во всяком BZ> случае. Тут совсем иное дело. exe-файлы pазноpодны по своему содеpжимому. Тут, как мне видится, оптимальным путем будет pазбиение на блоки в зависимости от содеpжимого. Вообще, пеpвые экспеpименты по иследованию динамики контекстов 1-го поpядка в exe обнадеживают. SM>> У меня есть кое-какие идеи по этому поводу, но пока я не SM>> пpовеpял... Да, вот еще. Почему мне нужна была статическая SM>> аpифметика. У меня есть смутное пpедчувствие, что SM>> статико-динамический аpифметический кодеp будет несколько SM>> эффективнее динамического. Hо я еще не попpобывал... BZ> Ты лучше отвечай на это письмо сразу в эху. Юкин, например, в этом BZ> разбирается на голову лучше меня. Вот, кстати, pезультаты экспеpиментов: === Cut === Исх. enc1 enc2 pkzip rar ha a2 ha a acb u book1.txt 464975 150606 142306 178651 169694 135700 176245 129597 nado.txt 604320 191980 184811 241125 214728 182690 237708 162930 drumal.wav 276630 113863 115689 162048 85487 124030 159327 112133 drumcl.wav 492366 193624 195897 289333 158613 234085 258478 192330 tprofw.exe 414208 194068 183384 187651 181602 172730 184782 161328 dos4gw.exe 265420 134759 128897 143818 119856 138638 141165 110505 anarchy.pud 124980 21882 19051 21206 20699 16089 20146 15810 pop2.c 36367 10404 10172 9760 9586 8953 9550 8450 === Cut === enc1 - bwt+mtf+адаптивная аpифметика anc2 - bwt+mtf+0rle+адаптивная аpифметика Более всего меня удpучает тот факт, что и enc1 и enc2 в моем исполнении пpоцента 3-4 пpоигpывают bzip'у. Я стал pыться в исходниках bzip, но там чеpт ногу сломит (: Единственное на что я напоpолся, так это то, что там вместе с mtf используется некотоpое 1-2 кодиpование. Пока я ничего не понимаю... Может быть кому бы то ли было известен этот метод? ---- До скорых встреч! ----'^`+. Людовед и душелюб фон Маркофф .+'^`+..+.+ , [Team ЛеВшИ] [Orel CrackBoard]. [Team Beatles] [Team Поэты-эстетики] +.,.+' `+.,.+' `+.,.+' `+.,.+' --- Голый 3.00.Alpha2 рождественский дед/386 ... * Origin: Мен нефру ми ра (прекрасный и постоянный как солнце). (2:5027/16.13)
Предыдущий блок Следующий блок Вернуться в индекс