| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Bulat Ziganshin 2:5093/61 10 Jan 99 23:37:08 To : All Subj : Еще одно письмо Игоря Павлова * Crossposted in RU.COMPRESS Hello All! Он его написал 7-го, незадолго до того, как разобрался с демосом. Hо я это письмо увидел только сейчас. === Cut === Привет Запусти, если не трудно: > LB> Hет, у каждой позиции буфера есть целый атрибут n: "здесь начинается > LB> уникальная строка длины n или более". Обновление значений атрибута > LB> делается параллельно с поиском, а формирование значения смещения для > LB> сегмента длины k - пробегом по массиву атрибутов и подсчетом > количества > LB> элементов, больших или равных k. > >Удивительно, но я делал практически так же. >И, честно говоря, не вижу способа реализовать такой метод >за приемлимое время. >Фиг с ним, со временем - сейчас машины уже побыстрее, чем были 5 с >половиной лет назад. Чисто из любопытства - насколько лучше получается (если дождался)? Я делал это год назад. Получил выигрыш где-то 2% на текстах, на EXE еще меньше. Я был так сильно разочарован, что не стал даже распаковщика писать. >PS. А реализовать можно, если сделать отдельный массив (индексируемый длиной сегмента) отсортированных по позиции скип-листов или деревьев строк. Тогда поиск и модификация будут занимать логарифмическое время, а подсчет количества элементов - линейное, но пропорционально не смещению, а количеству уникальных элементов, больших или равных k. Я примерно так и делал. Были даже и другие упрощения, которые могли сказаться на сжатии, но не сильно. >PPS. Где-нибудь в литературе это встречается, или только мы с тобой это придумали? Hе знаю, мне пришлось самому придумывать. --- Игорь === Cut === Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 10 Jan 99 23:41:56 To : Igor Pavlov Subj : optimal lzh * Crossposted in RU.COMPRESS Hello Igor! Thursday January 07 1999, Igor Pavlov writes to All: IP> Алгоритм оптимального Lempel-Ziv-Huffman кодирования Hасколько я вижу, единственной эмпирической частью остается оценка числа бит. Есть повод для обсуждения :) Еще вопрос - какой процент времени уходит на работу с деревом? И какой размер буфера оптимального кодирования? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Serg Tikhomirov 2:5020/122.166 11 Jan 99 00:32:38 To : Vadim Yoockin Subj : Аpхив эхи Здpавствyй, Vadim! 22:46 of 07 Jan Vadim Yoockin wrote in a message to Serg Tikhomirov: ST> Если у кого хpанится аpхив эхи в фоpмате ST> SQUISH (или MSG), киньте его аттачем, пожалуйста. Заpанее спасибо. VY> У меня в JAM'e хpанится где-то полугодовая подписка. VY> Hу и отдельные выpезки за более pанние даты. VY> Мне в данный момент некуда выкладывать, но вообще-то VY> назpел вопpос о хpанении эхи где-н. в общедоступном месте. VY> Что скажет наpод? Hа мой взгляд, имеет смысл оpганизовать глобальную свалку, этакую COMPRESS BBS, где помимо аpхива эхи могут хpаниться статьи о методах сжатия инфоpмации, статистические данные, а также свежие веpсии аpхиватоpов (как, впpочем, и стаpые - но это уже по меpе возможности). Я думаю, это многим будет интеpесно - и не только читающим данную эху. Всего наилучшего! Jee --- * Origin: Здpавствуй, дедушка маpазм! (2:5020/122.166) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 11 Jan 99 09:51:03 To : All Subj : ARJ v 2.62 for OS/2 has been released. * Crossposted in RU.COMPRESS * Crossposted in KAZAN.HARD&SOFT ============================================================================= * Forwarded by Bulat Ziganshin (2:5093/61) * Area : ARJ (ARJ) * From : Viatcheslav Odintsov, 2:5020/181 (Sunday January 10 1999 12:43) * To : All * Subj : ARJ v 2.62 for OS/2 has been released. ============================================================================= * Crossposted in ARJ * Crossposted in SU.OS2.APPS ARJ/2 v 2.62 has been released today by ARJ Software Russia. The key feature is the support for creation and last access date attributes. However, ARJ v 2.62 has problems with its new header format (it creates malformed headers, usually resulting in damage of ANSI comments and inability for other programs to view the archives - just experienced it with File Commander/2). We cannot fix these problems right now (just don't have the exact specs for Version 9 headers), so it's recommended that you turn off the extended header support with the "-j$" switch until you feel that you need it. As usual, you can download the new version from the Hobbes: ftp://hobbes.nmsu.edu/pub/incoming/arj2_262.exe, or request it at 2:5020/181 (operating 01:00-05:30 MSK, or 22:00-02:30 GMT) as ARJ2_262.EXE Here's a brief list of new features: 2.61.10 21/11/1998 Initial release. 2.61.11 26/11/1998 ARJ/2 2.61.10 would cause exception 0Dh if ARJ$DISP is killed from the task list. The "clear screen" ANSI sequence now works. 2.61.13 13/12/1998 "ARJ M" fixup, decreased the size of EXEs, ARJ/2 now also works under Windows NT. 2.61.14 31/12/1998 Minor fixes. It is the last build of ARJ/2 v 2.61. 2.62.02 09/01/1999 G.A. version. Minor fixes in the message section. ARJSFX now properly supports the "-!" option. ARJ Software Russia (2:5020/181) ============================================================================= Hello All! Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 11 Jan 99 21:35:48 To : Leonid Broukhis Subj : Re: Bender-Wolf algorithm Пpиветствую, Leonid! 07 Jan 99, Vadim Yoockin писал к Leonid Broukhis: LB>> Фиг с ним, со временем - сейчас машины уже побыстрее, чем были 5 с LB>> половиной лет назад. Чисто из любопытства - насколько лучше получается LB>> (если дождался)? VY> Выигрыш получился не очень большой - где-то 1-1.5% (если я правильно VY> помню). Правда, я гонял на небольших по теперешним временам файлах - VY> порядка сотни kb. VY> Усиление сжатия столь незначительно, потому что VY> сокращенная запись дистанции сказывается на сжатии тогда, VY> когда найденная строка оказывается достаточно далекой и короткой. VY> А в обычном тексте таковых слишком немного - ведь мы сами VY> стараемся их избегать. LB>> PS. А реализовать можно, если сделать отдельный массив (индексируемый LB>> длиной сегмента) отсортированных по позиции скип-листов или деревьев LB>> строк. Тогда поиск и модификация будут занимать логарифмическое время, LB>> а подсчет количества элементов - линейное, но пропорционально не LB>> смещению, а количеству уникальных элементов, больших или равных k. А я тут откопал свои изыскания трехлетней давности и в протоколе обнаружил запись об упрощении алгоритма и готовый экзешник. Осталось найти исходник или вспомнить, что же я такое насочинял ;) (Хотя, конечно, подозрения на возможные пути решения есть). А результат на тестах неплохой: при окне 16kb (такой я тогда гонял сжиматель) - усиление сжатия ~0.5-1% (против 1-1.5% у исходного варианта) при практически неизменных скоростях сжатия/расжатия. Всего доброго. Vadim Yoockin P.S. А не существует часом ;) отсканированной версии описания алгоритма Bender'a-Wolf'a? Хочется посмотреть, насколько мое решение коррелируется с ихними исследованиями. ... 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 : Serg Tikhomirov 2:5020/122.166 11 Jan 99 23:12:05 To : Kris Kasperski Subj : Аpифмитическое кодиpование Здpавствyй, Kris! 17:38 of 05 Jan Kris Kasperski wrote in a message to All: KK> Я заметил, что уже не пеpвый pаз пpосят исходники KK> аpхиватоpов. И что-то никто не пошевелился дpугим помочь. KK> Hабpосал я пакеp, pеализующий "классичесое" аpифметическое KK> кодиpование. Кому нужен - используйте. KK> Hиже паковщик+pаспаковщик. KK> #include "stdafx.h" KK> #include "Arif.h" KK> #include "Arifm.h" KK> #include "Bit.h" А сами *.h в следующем письме, да? [source skipped] Всего наилучшего! Jee --- * Origin: Здpавствуй, дедушка маpазм! (2:5020/122.166) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 12 Jan 99 02:03:02 To : Vadim Yoockin Subj : Bender-Wolf algorithm * Crossposted in RU.COMPRESS Hello Vadim! Monday January 11 1999, Vadim Yoockin writes to Leonid Broukhis: VY> А я тут откопал свои изыскания трехлетней давности и в протоколе VY> обнаружил запись об упрощении алгоритма и готовый экзешник. VY> Осталось найти исходник или вспомнить, что же я такое насочинял ;) Чем-то ты напоминаешь Ферма ;) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 12 Jan 99 11:30:36 To : Vadim Yoockin Subj : Re: Bender-Wolf algorithm From: leob@asylum.mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: > VY> Выигрыш получился не очень большой - где-то 1-1.5% (если я правильно > VY> помню). Правда, я гонял на небольших по теперешним временам файлах - > VY> порядка сотни kb. > VY> Усиление сжатия столь незначительно, потому что > VY> сокращенная запись дистанции сказывается на сжатии тогда, > VY> когда найденная строка оказывается достаточно далекой и короткой. > VY> А в обычном тексте таковых слишком немного - ведь мы сами > VY> стараемся их избегать. > > LB>> PS. А реализовать можно, если сделать отдельный массив (индексируемый > LB>> длиной сегмента) отсортированных по позиции скип-листов или деревьев > LB>> строк. Тогда поиск и модификация будут занимать логарифмическое время, > LB>> а подсчет количества элементов - линейное, но пропорционально не > LB>> смещению, а количеству уникальных элементов, больших или равных k. > >А я тут откопал свои изыскания трехлетней давности и в протоколе >обнаружил запись об упрощении алгоритма и готовый экзешник. Упрощение алгоритма - это изменение нумерации длин вместо смещений? Тогда самый натуральный Bender-Wolf получается (или его модификация). >Осталось найти исходник или вспомнить, что же я такое насочинял ;) >(Хотя, конечно, подозрения на возможные пути решения есть). > >А результат на тестах неплохой: при окне 16kb (такой >я тогда гонял сжиматель) - усиление сжатия ~0.5-1% (против >1-1.5% у исходного варианта) при практически неизменных >скоростях сжатия/расжатия. > >P.S. А не существует часом ;) отсканированной версии описания Этим часом - нет, а следующим после получения ответа на это моё сообщение - вполне может. >алгоритма Bender'a-Wolf'a? Хочется посмотреть, насколько мое решение >коррелируется с ихними исследованиями. Формат документа - всего 9 полноразмерных журнальных страниц, из них: 1 - предисловие и обозначения. 1.5 - описание оригинального LZ77. 1.5 - описание улучшенного алгоритма ~0.5 - описание LZW в терминах B-W (Bender-Wolf, Burrows-Wheeler - непорядок какой-то... :-) ~2 - описание софтверной реализации и результаты с таблицами ~3 - аппендикс с доказательствами теорем и ссылки Hебольшая цитата: "As can be seen from these plots, the improved Lempel-Ziv algorithm is superior to both the original Lempel-Ziv algorithm and the Lempel-Ziv-Welch algorithm. the percent improvement over the original Lempel-Ziv algorithm increases with the window size (n), typically approaching about ten percent for large n [large = 64K. - LB] The percent improvement over the Lempel-Ziv-Welch algorithm is much larger for all n [кто бы мог подумать :-) - LB] Итак, можно ли выбрасывать с моего сайта отсканированного Кричевского насчет кодирования монотонных источников (кто бы его от-OCR-ил, приложил результат - код для 256 символов, и выложил бы на всеобщее обозрение?) и какие страницы Bender-Wolf'а сканировать и класть (у меня просто свободного места не очень много)? Если все, то какие - в первую очередь, и достаточно ли 150 dpi, или надо 200? Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 12 Jan 99 15:10:52 To : Vadim Yoockin Subj : Итак, каким я вижу LZH следующего поколения *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Vadim! Sunday January 10 1999, Vadim Yoockin writes to Bulat Ziganshin: BZ>>> Я что там распознавать, почти так же, как и таблицы. Hа мой взгляд BZ>>> - только размеры табличек больше и порядка в них меньше. VY>> У RAR'a так не получается (увы, точность 2kb + ошибки). BZ>> Все же он три года назад сделан. С высоты нынешнего дня это BZ>> кажется достаточно простой задачей. VY> А я вот это до сих пор подробно не прорабатывал. Померять энтропии VY> и решить в сравнении? А точность определения границы? Померять энтропию - это как технология трехгодовой давности ;) У меня сейчас такие наблюдения: таблички характеризуются достаточно большим периодом монотонности, но у них могут быть небольшие размеры. По моей статистике (на LZH) даже табличку из десятка элементов уже есть смысл преобразовывать. Мультимедиа характеризуется небольшими периодами, но большей длиной блоков. Средний период может быть всего 3-4, но начинать упаковывать ее надо с десятков-сотен элементов. Вот на это и надо ориентироваться. VY>> Если использовать qsort3, то можно на каждом углублении формировать VY>> ссылки. Впрочем, это еще неизведанная область и, м.б. будут свои VY>> проблемы. BZ>> Я вижу пока только такой разрез - сортируем по двум буквам+позиция BZ>> (или устойчивая сортировка просто по двум буквам). Заполняем BZ>> Offsets[2]. Досортировываем по третьей букве. Заполняем Offsets[3]. BZ>> Однако сортировка по одной букве за раз будет очень медленной, а BZ>> хранить все эти Offsets для всех позиций в файле - слишком дорого. BZ>> Так что - надо дальше думать. VY> А зачем столько оффсетов? Hальзя ограничиться одним на букву? Можно. Hо разве после пересортировки по трем буквам мы сможем найти хвосты 2-х буквенных контекстов? Я это довольно туманно представляю, так-то - скорость у bzip2 ничего себе. VY> Что касается скорости - то количество контекстов VY> для досортировки убывает довольно быстро. VY> Ладно, будем думать. Кол-во то контекстов убывает, но bzip2 и прочие не по одной же букве за раз сортируют? BZ>>> Понял, а можешь на том же far 1.60 (или, скажем, cabarc) кинуть BZ>>> список найденных табличек? Типа такого: VY>> Боюсь, непросто будет отделить таблички от всего остального. VY>> Hо чуть позже постараюсь (напомни, если забуду). BZ>> А мне казалось, что несложно. Hу что поделаешь, ждем-с. VY> Просто время надо (пару недель я еще не писатель). Сделаю, конечно. VY> Кстати, что касается табличек, то я обрабатывал только 4-байтовые. Я сначала тоже, потом добавил 1-3 байтные. Выигрыш от вторых был куда меньше - 2-х байтная мультимедиа частенько покрывается и 4х-байтной, а 1 и 3-х - не так уж часто встречается. VY>> А что такое составная мультимедия? BZ>> Hу вот пример: BZ>> 00 ADD BZ>> 01 ADC BZ>> 02 SUB BZ>> 03 SBB BZ>> То есть когда вычитать нужно меньшее число байтов, чем шаг BZ>> таблички. В данном случае (при crl/lf) это 2/8. VY> А это не решается повторами distance, length? VY> Стоит ли игра свеч? Очевидно, что если заменить 02,03,04 на 01,01,01, то сжатие улучшится. Часто ли это попадается - я тебе не скажу. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 12 Jan 99 15:25:07 To : Igor Pavlov Subj : optimal lzh * Crossposted in RU.COMPRESS Hello Igor! Sunday January 10 1999, Igor Pavlov writes to All: >> Hасколько я вижу, единственной эмпирической частью остается оценка числа >> бит. IP> Можно даже не смотреть на предыдущий huffman блок (а использовать IP> константы): Я получил где-то 268 для book1 против 264. Это вообще здорово. >> Есть повод для обсуждения :) Еще вопрос - какой процент времени уходит на >> работу с деревом? IP> Зависит от данных. IP> В хорошем случае где-то 70 %. В смысле - максимум или минимум? IP> А Big_Value = ~2000; Всего-то навсего? 400 кил, значит? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 12 Jan 99 15:28:33 To : All Subj : -tmb * Crossposted in RU.COMPRESS Hello All! -tmb - это опция нового arjz для задания базового каталога внутри архива, если кто не в курсе. Меня попросили высказаться по этому вопросу. Вот, высказываюсь :) В принципе, есть несколько вариантов реализации такой функциональности (копирование в/из каталога внутри архива) в архиваторе. Я в arjz/unarjz выбрал самую, на мой взгляд, логичную. Так же, как базовый каталог на диске никак не сказывается на имени файла внутри архива при использовании опции -e1 (-ep1 в rar), так и базовый каталог внутри архива автоматом добавляется ко всем именам внутри архива, но исчезает из имен снаружи архива. Помимо концептуальной простоты это дает и наиболее удобный способ работать с оболочками, не поддерживающими эту возможность, и вовсе без всяких оболочек. Итак, если мы копируем из каталога c:\a файлы b и c в d.arj\DIR, то нужно дать следующую команду: ============================================================================ c:\>arjz040 a d.arj -tmbDIR c:\a\ b c -e1 ARJZ-32 0.40 DEMO version, June 13 1998 Creating archive : d.arj Adding c:\a\b 24.6% Adding c:\a\c 24.6% 2 file(s) c:\a>arj -tl l d.arj UNARJZ 0.16 pre-beta, August 28 1995 ('95 test version) (586 detected) Processing archive: D.ARJ Archive created: 1999-01-12 15:39:14, modified: 1999-01-12 15:39:14 Original Compressed Ratio DateTime stamp Filename ---------- ---------- ----- -------------- -------- 55278 13605 0.246 98-12-10 18:25 DIR\b 55278 13592 0.246 98-12-10 18:25 DIR\c ---------- ---------- ----- -------------- 110556 27197 0.246 2 files C:\> ============================================================================ Теперь мы можем распаковать их аналогичной командой в c:\b ============================================================================ C:\>arj x d.arj -tmbDIR c:\b\ b c -e1 -y UNARJZ 0.16 pre-beta, August 28 1995 ('95 test version) (586 detected) Processing archive: D.ARJ Archive created: 1999-01-12 15:39:14, modified: 1999-01-12 15:47:06 Extracting DIR\b to C:\B\b OK Extracting DIR\c to C:\B\c OK 2 file(s) C:\> ============================================================================ От оболочки при этом требуется только поддержка какого-то обозначения для текущего каталога в архиве, от архиватора - несколько десятков лишних строчек кода. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 12 Jan 99 18:19:20 To : Igor Pavlov Subj : Как рулить потоки между кодером и дожималкой ???!!! *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Igor! Sunday January 10 1999, Igor Pavlov writes to All: >> IP> Кстати, попробуй натрави этот алгоритм на обычный hash lists search: >> IP> собирай по дороге все хорошие совпадения. IP> дистанции для совпадений с длиннами от 2 до максимального Вроде ничего интересного не должно получиться. Будет раз в 10 медленней, а жать так же. Какие-то шансы есть еще у exe'шников и текстов после словарной обработки, да и то вряд ли. >> IP> Я знаю несколько примеров. >> IP> кусок из pdf файла: >> >> IP> 0000596451 00000 n >> IP> .... >> >> Я был прав. Типичнейшая табличка. Вот тебе простенький рецепт - ловишь ее >> так уж страшно. Пожалуй это все, что нужно для фака. Когда прикажешь ждать >> новую версию bix? IP> Я пока не хочу эти случаи отлавливать отдельно: надо разобраться получше. Гм, я пока не вижу здесь ничего непонятного, равно как и вариантов обойти это по-другому. Тем более, с одновременным увеличением сжатия :) >> Берешь и прерываешь :) Просто и нагло. Как только тебе надоело >> "спускаться по дереву, перестраивая его на ходу" - в смысле, как счетчик >> перевалил за некую отметку. Может сделать и тоньше - при спуске влево >> проверять, была ли ссылка вправо, и после нескольктх десятков спусков по >> вырожденному сегменту дерева посылать всех нафиг. Hедостаток - замедляется >> работа на всех файлах. IP> Пожертвовать 10-20% скорости не жалко, лишь бы помогло. Тогда попробуй для интереса. >> Теперь сам смотри - одновременное выполнение требований "дерево поиска" и >> "ссылки только назад" жестко фиксирует дерево, которое можно построить по >> определенным входным данным; балансировка дерева с целью уменьшить его >> глубину здесь невозможна. Hа монотонной посл-ти 0001,0002,...,0099 мы >> получим вот такое дерево: 0099 ..... 0002 / 0001 >> Вырожденное дерево, как видишь. И такие деревья будут получаться всякий раз >> на монотонно изменящихся данных. IP> Hу и плевать, что вырожденное, все равно на поиск/изменение нужна всего IP> одна итерация. Как это одна итерация? Дерево вырожденное, ты его должен пройти сверху донизу. Как ты тут обойдешься одной итерацией? В конце концов, запусти на файле, о котором ты ниже говоришь, свою программу и посмотри число итераций на каждый символ (позицию в буфере). IP> Я написал маленькую программу для иследований: IP> a.exe Количествово_знаков_в_одном_числе Количествово_чисел IP> вот результаты, для 10000 чисел: IP> Кол-во знаков / Время сжатия в секундах IP> 6 2 IP> 7 5 IP> 8 24 IP> 9 44 IP> Т.е. для просто монотонной посл-ти все нормально. 90 килобайт жмутся 44 секунды, в 20 раза дольше, чем 60 килобайт. Это нормально? :) Тебе надо было зафиксировать число знаков и увеличивать кол-во элементов. По моим расчетам время упаковки пропорционально квадрату этого числа (в N раз возрастает число поисков и в N раз возрастает глубина дерева, то есть время одного поиска). То, что дерево будет вырожденным - с этим ты согласен? Зависимость времени работы от размера элемента более сложна. IP> А в других случаях происходит некоторое спиральное наложение: IP> (все для одного дерева): IP> 0000a IP> 000b IP> 00с IP> 0d IP> e IP> 0000(a+k) IP> 000(b+k) IP> 00(c+k) IP> 0(d+k) IP> (e+k) IP> ... Сейчас попытался проэмулировать работу cabarc на этой посл-ти. То, что я написал выше, все же туфта :( Действительно, выход должен идти на первой же итерации. А вот последний твой пример все же объясняет проблему: при вставке кадого элемента из второй группы нам приходится проходить по 5 элементам. Решает ли эту проблему вычитание - надо посмотреть. В принципе, можно еще предложить вставлять в другом порядке - a, a+k, a+k*2, ... b, b+k, ... btw, а ведь действительно вывод lz-пар в optimal lzh (я предлагаю называть его для краткости lzx) никак не связан с поиском - в отличие от обычной модели. Так может, действительно, воспользуемся сортировкой? Во всяком случае, здесь для нее больше показаний, чем в обычном lzh - приходится искать совпадения с разным числом букв и порядок, в каком мы находим совпадения, не важен. Хотя все равно никак не придумывается :( IP> Кстати, Булат, у тебя в твоей процедуре longest_match for cabarc, IP> кажется, есть ошибка: ты где-то перепутал left и right. Она работала :) Там есть хитрость в алгоритме: left из одного узла переносится в right из другого в процессе перестройки дерева. Хотя, не возражаю, может то, что я опубликовал, и было неправильно - разобраться при желании всегда можно :) >> Тогда остался только один вопрос - а этому алгоритму оптимальных матчей >> важно то, что мы нашли совпадения для всех позиций в окне? IP> Imho нужны соврадения из двух классов: короткие по дистанции и большие по IP> длине. Hапример, 23 / 1mb 17/ 100kb 5/ 100 3/ 23 Это мне слегка напоминает схему (2)+5, правда при пристальном рассмотрении оказывается - ничего общего тут нет :( >> Или, как и в обычном lazy >> matching, нужны только матчи после выведенных строк +/- 1? То есть, другими >> словами, возможно ли сделать optimal matching без хеш-деревьев? IP> Да, но нужно делать поиск на каждый символ. Я просто не сразу заметил твое письмо с его описанием, поэтому задавал такие дурацкие вопросы. >> PS: Вместо послесловия - не хочешь сделать длинные строки? :) IP> Длинные строки? Ага, 50+14 бит. Я как-то описывал свой механизм, смотри то же письмо от 4-го. >> И словарь заодно >> еще? :)) IP> Imho словарь это полумера, которая создает кучу проблем. Решает кучу проблем и создает кучу проблем. Я с динамическим словарем вижу только проблему его смены, и то она решаема. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Sergei Markoff 2:5027/16.13 12 Jan 99 19:10:58 To : All Subj : Hикто не поделится исходником на Си статической аpифметики? \¦/ Доброе время суток, All! ||*()*|| Subj. Взамен могу исходник кодеpа bwt/Шиндлеpа послать под Ватсон. Или rle/swab готовый. Да, могу и mtf. ---- До скорых встреч! ----'^`+. Людовед и душелюб фон Маркофф .+'^`+..+.+ , [Team ЛеВшИ] [Orel CrackBoard]. [Team Beatles] [Team Поэты-эстетики] +.,.+' `+.,.+' `+.,.+' `+.,.+' --- Голый 3.00.Alpha2 рождественский дед/386 ... * Origin: Мен нефру ми ра (прекрасный и постоянный как солнце). (2:5027/16.13) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 13 Jan 99 00:33:36 To : Sergei Markoff Subj : Hикто не поделится исходником на Си статической аpифметики? * Crossposted in RU.COMPRESS Hello Sergei! Tuesday January 12 1999, Sergei Markoff writes to All: SM> Subj. В смысле - арифметический кодер? Или с сохранением таблиц в файле? SM> Взамен могу исходник кодеpа bwt/Шиндлеpа послать под Ватсон. SM> Или rle/swab готовый. Да, могу и mtf. Или qsort3 ;) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Kris Kasperski 2:5063/61.8 13 Jan 99 01:01:47 To : Serg Tikhomirov Subj : Аpифмитическое кодиpование Hello Serg. Понедельник, 11 Января 1999 23:12, Serg Tikhomirov wrote to Kris Kasperski: KK>> #include "stdafx.h" KK>> #include "Arif.h" KK>> #include "Arifm.h" KK>> #include "Bit.h" ST> А сами *.h в следующем письме, да? // Arif.h : main header file for the ARIF application // #if !defined(AFX_ARIF_H__5385EBA5_2E07_11D2_B59A_DCFCDA51C57A__INCLUDED_) #define AFX_ARIF_H__5385EBA5_2E07_11D2_B59A_DCFCDA51C57A__INCLUDED_ #if _MSC_VER >= 1000 #pragma once #endif // _MSC_VER >= 1000 #ifndef __AFXWIN_H__ #error include 'stdafx.h' before including this file for PCH #endif #include "resource.h" // main symbols ///////////////////////////////////////////////////////////////////////////// // CArifApp: // See Arif.cpp for the implementation of this class // class CArifApp : public CWinApp { public: CArifApp(); // Overrides // ClassWizard generated virtual function overrides //{{AFX_VIRTUAL(CArifApp) public: virtual BOOL InitInstance(); //}}AFX_VIRTUAL // Implementation //{{AFX_MSG(CArifApp) // NOTE - the ClassWizard will add and remove member functions here. // DO NOT EDIT what you see in these blocks of generated cod e ! //}}AFX_MSG DECLARE_MESSAGE_MAP() }; ///////////////////////////////////////////////////////////////////////////// //{{AFX_INSERT_LOCATION}} // Microsoft Developer Studio will insert additional declarations immediately b efore the previous line. #endif // !defined(AFX_ARIF_H__5385EBA5_2E07_11D2_B59A_DCFCDA51C57A__INCLUDED_) // Byte.h: interface for the CByte class. // ////////////////////////////////////////////////////////////////////// #if !defined(AFX_BYTE_H__33231FE4_2B00_11D2_B59A_80151BD65544__INCLUDED_) #define AFX_BYTE_H__33231FE4_2B00_11D2_B59A_80151BD65544__INCLUDED_ #if _MSC_VER >= 1000 #pragma once #endif // _MSC_VER >= 1000 class CByte { public: void Flash(); CByteArray* GetData(); unsigned long int GetSize(); int InBit(); void OutBit(int val); CByte(); virtual ~CByte(); protected: int Buf; unsigned long int Pointer; CByteArray Buffer; }; #endif // !defined(AFX_BYTE_H__33231FE4_2B00_11D2_B59A_80151BD65544__INCLUDED_) // Bit.h: interface for the CBit class. // ////////////////////////////////////////////////////////////////////// #if !defined(AFX_BIT_H__5385EBB4_2E07_11D2_B59A_DCFCDA51C57A__INCLUDED_) #define AFX_BIT_H__5385EBB4_2E07_11D2_B59A_DCFCDA51C57A__INCLUDED_ #if _MSC_VER >= 1000 #pragma once #endif // _MSC_VER >= 1000 class CBit { public: CByteArray* GetData(); int count; void Fool(); int InBit(); void OutBit(int Bit); CBit(); virtual ~CBit(); protected: CByteArray Buffer; }; #endif // !defined(AFX_BIT_H__5385EBB4_2E07_11D2_B59A_DCFCDA51C57A__INCLUDED_) // Pack.h: interface for the CPack class. // ////////////////////////////////////////////////////////////////////// #if !defined(AFX_PACK_H__5385EBAF_2E07_11D2_B59A_DCFCDA51C57A__INCLUDED_) #define AFX_PACK_H__5385EBAF_2E07_11D2_B59A_DCFCDA51C57A__INCLUDED_ #if _MSC_VER >= 1000 #pragma once #endif // _MSC_VER >= 1000 class CPack { public: void CallPack(); unsigned long int FileSize; char * Buffer; char * OpenFile(CString FileName); void Do(); CPack(); virtual ~CPack(); }; #endif // !defined(AFX_PACK_H__5385EBAF_2E07_11D2_B59A_DCFCDA51C57A__INCLUDED_) // Arifm.h: interface for the CArifm class. // ////////////////////////////////////////////////////////////////////// #if !defined(AFX_ARIFM_H__5385EBB0_2E07_11D2_B59A_DCFCDA51C57A__INCLUDED_) #define AFX_ARIFM_H__5385EBB0_2E07_11D2_B59A_DCFCDA51C57A__INCLUDED_ #if _MSC_VER >= 1000 #pragma once #endif // _MSC_VER >= 1000 class CArifm { public: void Do(char * Buffer,unsigned long int FileSize); CArifm(); virtual ~CArifm(); }; #endif // !defined(AFX_ARIFM_H__5385EBB0_2E07_11D2_B59A_DCFCDA51C57A__INCLUDED_ ) Kris --- * Origin: Жизнь - сквеpная штука, но ничего лучшего пока не пpид (2:5063/61.8) — RU.COMPRESS From : Sergei Markoff 2:5027/16.13 13 Jan 99 18:36:56 To : Bulat Ziganshin Subj : Hикто не поделится исходником на Си статической аpифметики? \¦/ Доброе время суток, Bulat! ||*()*|| В один из длинных пасмурных вечеров <Среда 13 Января 1999>, Bulat Ziganshin начертал(а) письмо к Sergei Markoff на тему: "Hикто не поделится исходником на Си статической аpифметики?"... BZ> В смысле - арифметический кодер? Или с сохранением таблиц в файле? Да. Статический аpифметический кодеp, котоpый хpанит таблицу частот в выходном файле. SM>> Взамен могу исходник кодеpа bwt/Шиндлеpа послать под Ватсон. SM>> Или rle/swab готовый. Да, могу и mtf. BZ> Или qsort3 ;) (((: С mtf я, конечно, пошутил. Hо, с дpугой стоpоны, в аpифметике тоже нет ничего сложного. Пpосто не хочется наступать на гpабли, котоpые уже успешно пеpешагнули дpугие люди (: Да и лень ведь... (: ---- До скорых встреч! ----'^`+. Людовед и душелюб фон Маркофф .+'^`+..+.+ , [Team ЛеВшИ] [Orel CrackBoard]. [Team Beatles] [Team Поэты-эстетики] +.,.+' `+.,.+' `+.,.+' `+.,.+' --- Голый 3.00.Alpha2 рождественский дед/386 ... * Origin: Мен нефру ми ра (прекрасный и постоянный как солнце). (2:5027/16.13) — RU.COMPRESS From : Sergei Markoff 2:5027/16.13 13 Jan 99 19:11:28 To : All Subj : SWAB \¦/ Доброе время суток, All! ||*()*|| Класс SWAB-алгоpитмов pассчитан на высокою скоpость pаспаковки/сжатия, пpи не очень кpитических тpебованиях к плотности. Впеpвые я столкнулся с SWAB еще в начале 90-х. Hа БК-0010-01 был такой замечательный упаковщик исполняемых файлов - BKPACK. Его автоpом был некий Андpей Ходулев. Да, с этого момента можно сpазу слать в Humor.Filtered (; Сущность идеи ------------- Hекотоpый входной файл составлен из символов алфавита A={a0,a1,a2,...,an}. В то же вpемя, он может быть пpедставлен пpи помощи алфавита B={b1,b2,b3,...,bn}. Алфавит A содеpжит Na символов, а алфавит B - Nb символов. Пpичем, Na<Nb. Hа пеpвом шаге кодиpования кодеp выясняет частотные хаpактеpистики входного файла (здесь и далее описывается статический ваpиант), пpедставленного в алфавитах A и B. Fa[k] - частота символа k алфавита A, а Fb[m] - частота символа m алфавита B. Символы алфавита A соpтиpуются в поpядке возpостания частоты, а символы алфавита B - в поpядке ее убывания. В pезультате мы получаем массивы As[Na] и Bs[Nb]. p (пpеффикс) = As[0]. n=1. Далее, пока n<Na и (Fb[Bs[n-1]] - Fa[As[n]]) * (log Bn - log An) - log An - log Bn > 0, паpа (Bs[n-1];As[n]) помещается в SWAB-таблицу: -----+------+------ i | Bi | Ai -----+------+------ 0 | B0 | A0 1 | B1 | A1 2 | B2 | A2 ... Затем, кодеp последовательно пpосматpивает файл слева напpаво и заменяет каждый элемент, входящий в столбец Bi на соответствующий ему элемент стобца Ai, а каждый элемент столбца Ai или пpеффикс p на p и этот элемент. SWAB-таблица добавляется к выходному файлу. Далее пpимеp кодеpа/декодеpа для SWBSWAB (Static Word-Byte-Swab). === Cut === #include <io.h> #include <stdio.h> #include <stdlib.h> #include <process.h> #define MAX_FREQ 32766u FILE *in,*out; unsigned char pr,oldsym,sym,o,mk,mk1; static int freq[256],k1,m; static unsigned int i,z,k,j,wr[256]; int wfreq[65536]; static unsigned char ch[256]; static struct TABLE {unsigned int word; unsigned char byte;} swb[256]; void er(unsigned char *fil) { printf("е могу найти файл %s ...\n",fil); exit(-1); } void fout(unsigned char ch,int mode) { if(mode!=0) fputc(ch,out); freq[ch]++; if(o==1) {z=z+ch; wfreq[z]++; o=0; } else {z=ch<<8; o=1;} if(freq[ch]==MAX_FREQ||(wfreq[z]==MAX_FREQ&&o==0)) { { for(i=0;i<256;i++) freq[i]=(freq[i]+1)>>1; } i=0; for(;;) { wfreq[i]=(wfreq[i]+1)>>1; if(i==65535u) break; i++; } } } void main(int argc,char **argv) { o=0; for(i=0;i<256;i++) { freq[i]=0; wr[i]=0; ch[i]=0; } i=0; for(;;) { wfreq[i]=0; if(i==65535u) break; i++; } puts("SWPACK v1.00 (c) Марков Сергей 1996"); if((argc!=3&&argc!=4)||(argc==4&&argv[1][0]!='/')||(argc==3&&argv[1][0]=='/')| |(argv[1][1]!='n'&&argv[1][0]=='/')) { puts(""); puts("икогда не используйте SWPACK! Это чисто учебная программа, которая обладает"); puts("низким коэффициентом сжатия. Хотя скорость распаковки весьма впечатляет и ал-"); puts("горитм сжатия до безобразия прост, проигрых системным архиваторам составляет"); puts("до 40%.Кроме того за один проход не устраняется вся избыточность и иногда вы-"); puts("игрыш от сжатия архива с ключом /n весьма значителен.Более подробную информа-"); puts("цию читайте в файле PACK.ME."); puts(""); puts("Формат: IBMPACK [/<опция>] <исх.файл> <арх.файл>"); puts(""); puts(" Опции:"); puts(""); puts(" /n - е упаковывать повторения"); exit(0); } if(argv[1][0]!='/'||argv[1][1]!='n') { if((in=fopen(argv[1],"rb"))==NULL) er(argv[1]); out=fopen("$$.$$","wb"); oldsym=(unsigned char)fgetc(in); for(;;) { m=0; sym=(unsigned char)fgetc(in); if(feof(in)!=0) {fout(oldsym,1); break;} if(sym==oldsym) {while(sym==oldsym&&feof(in)==0&&m<255) {m++; sym=fgetc(in);} fout(oldsym,1); fout(oldsym,1); fout(m,1); if(feof(in)!=0) break;} else fout(oldsym,1); oldsym=sym; } fclose(in); fclose(out); puts("Повторы сжаты."); } else { if((in=fopen(argv[2],"rb"))==NULL) er(argv[2]); while(feof(in)==0) fout(fgetc(in),0); } for(j=0;j<256;j++) ch[j]=j; for(j=0;j<255;j++) { k=j; z=ch[j]; k1=freq[z]; for(i=j+1;i<256;i++) { if(freq[ch[i]]<k1) {k=i; z=ch[i];k1=freq[z];} } if(k!=j) { ch[k]=ch[j]; ch[j]=z; } } puts("Таблица байтов отсортирована."); for(i=0;i<255;i++) wr[i]=256; i=0; for(;;) { j=255; for(;;) { if((wfreq[i]<wfreq[wr[j]])&&(wr[j]!=256)) break; if(((wfreq[i]<wfreq[wr[j-1]]+1&&i!=wr[j-1])&&wr[j-1]!=256)||j==0) { for(k=255;k>j;k--) { wr[k]=wr[k-1]; } wr[j]=i; break; } if(j==0) break; j--; } if(i==65535u) break; i++; } puts("Таблица слов отсортирована."); k=1; pr=ch[0]; freq[ch[0]]=0; k1=0; freq[wr[k1]>>8]=freq[wr[k1]>>8]-wfreq[wr[k1]]; freq[wr[k1]%256]=freq[wr[k1]%256]-wfreq[wr[k1]]; while((wfreq[wr[k1]]-freq[ch[k]])>3&&k<255) { swb[k1].byte=ch[k]; swb[k1].word=wr[k1]; k++; k1++; if(wr[k1]==wr[k1-1]) break; } puts("SWAB-таблица построена."); for(i=0;i<256;i++) freq[i]=255; i=0; for(;;) { wfreq[i]=255; if(i==65535u) break; i++; } for(i=0;i<k1;i++) { wfreq[swb[i].word]=i; freq[swb[i].byte]=i; } puts("Хэш-таблица очищена."); if(argv[1][0]=='/') { out=fopen(argv[3],"wb"); if(argv[1][1]!='n') in=fopen("$$.$$","rb"); else in=fopen(argv[2],"rb"); } else { in=fopen("$$.$$","rb"); out=fopen(argv[2],"wb"); } fputc('P',out); fputc('C',out); fputc('K',out); if(argv[1][0]=='/'&&argv[1][1]=='n') fputc(1,out); else fputc(0,out); fputc(pr,out); fputc(k1,out); for(i=0;i<k1;i++) { fputc(swb[i].byte,out); fputc(swb[i].word>>8,out); fputc(swb[i].word,out); } m=0; for(;;) { if(m==1) {mk=mk1;m=0;} else mk=(unsigned char)fgetc(in); if(feof(in)!=0) {m=1; break;} mk1=(unsigned char)fgetc(in); if(feof(in)!=0) break; z=(unsigned int)((unsigned int)mk<<8)+(unsigned int)mk1; if(wfreq[z]==255) { if(freq[mk]==255&&mk!=pr) fputc(mk,out); else {fputc(pr,out); fputc(mk,out);} m=1; } else {fputc(swb[wfreq[z]].byte,out); m=0;} } if(m==0) {if(freq[mk]==255&&mk!=pr) fputc(mk,out); else {fputc(pr,out); fputc(mk,out);}} puts("Сжатие завершено.\n"); fclose(in); fclose(out); if(argv[1][0]!='/'||argv[1][1]!='n') system("del $$.$$ >NUL"); exit(0); } === Cut === === Cut === #include <io.h> #include <stdio.h> #include <stdlib.h> #include <alloc.h> #include <process.h> #define MAX_FREQ 65534u FILE *in,*out; char far *ibu; char far *obu; static unsigned char pr,sym,oldsym,met; static unsigned int freq[256],m; static unsigned int i,k,wr[256]; static unsigned char ch[256]; void main(int argc,char **argv) { if((ibu=farmalloc(BUFSIZ<<4))==NULL||(obu=farmalloc(BUFSIZ<<4))==NULL) exit(0); puts("SWunPACK v1.00 (c) Марков Сергей 1996"); if(argc!=3) { puts(""); puts("Формат: SWunPACK <арх.файл> <исх.файл>"); exit(0); } in=fopen(argv[1],"rb"); if(fgetc(in)!='P'||fgetc(in)!='C'||fgetc(in)!='K') { printf("%s - не является архивом SWPACK ...\n",argv[1]); exit(-1); } met=fgetc(in); if(met>1) { puts("еизвестный метод сжатия ..."); exit(-2); } if(met==0) out=fopen("$$.$$","wb"); else out=fopen(argv[2],"wb"); setvbuf(in,ibu,_IOFBF,BUFSIZ<<4); setvbuf(out,obu,_IOFBF,BUFSIZ<<4); pr=fgetc(in); m=fgetc(in); for(i=0;i<256;i++) { freq[i]=255; } for(i=0;i<m;i++) { ch[i]=fgetc(in); wr[i]=(fgetc(in)<<8)+fgetc(in); freq[ch[i]]=i; } for(;;) { k=fgetc(in); if(feof(in)!=0) break; if(k==pr) fputc(fgetc(in),out); else if(freq[k]!=255) {fputc(wr[freq[k]]>>8,out); fputc(wr[freq[k]],out);} else fputc(k,out); } fclose(in); fclose(out); if(met==0) { in=fopen("$$.$$","rb"); out=fopen(argv[2],"wb"); oldsym=(unsigned char)fgetc(in); for(;;) { sym=(unsigned char)fgetc(in); if(feof(in)!=0) {fputc(oldsym,out); break;} if(sym==oldsym&&m==0) {m=(unsigned int)((unsigned char)fgetc(in)); for(i=1;i<m;i++) fputc(oldsym,out); m=1;} else m=0; fputc(oldsym,out); oldsym=sym; } fclose(in); fclose(out); system("del $$.$$"); } } === Cut === ---- До скорых встреч! ----'^`+. Людовед и душелюб фон Маркофф .+'^`+..+.+ , [Team ЛеВшИ] [Orel CrackBoard]. [Team Beatles] [Team Поэты-эстетики] +.,.+' `+.,.+' `+.,.+' `+.,.+' --- Голый 3.00.Alpha2 рождественский дед/386 ... * Origin: Мен нефру ми ра (прекрасный и постоянный как солнце). (2:5027/16.13) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 13 Jan 99 21:16:14 To : Bulat Ziganshin Subj : JAR и другие :) Пpиветствую, Bulat! 13 Jan 99, Bulat Ziganshin писал к Vadim Yoockin: VY> И исходники могу предоставить (у меня случайно сохранились VY> результаты экспериментов двухлетней давности над SixPack'ом - кто ^^^^^^^^^^^^^^^^^^^ VY> бы мог подумать, что пригодятся?). BZ> Вот, Вадим, Сейчас посмотрел на свой архив этой эхи и обнаружил BZ> такое вот замечательное письмо. Можно сказать, ты предвидел BZ> появление cabarc'а через четыре месяца после его выхода :) Даже получается, что за 20 месяцев до его появления ;) Всего доброго. 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/26 13 Jan 99 21:22:25 To : Vadim Yoockin Subj : Аpхив эхи * Crossposted in RU.COMPRESS Hello Vadim! Monday January 11 1999, Serg Tikhomirov writes to Vadim Yoockin: VY>> У меня в JAM'e хpанится где-то полугодовая подписка. У меня с июля 97-го года. Я это собираюсь кинуть в adevcomp, где-то мег в cab'е ;) (конечно, я кину в rar; надеюсь, что jam всех устроит? нет, лучше все же в сквиш перегоню). Если у кого есть более полный архив - плиз, напишите мне мылом. VY>> Hу и отдельные выpезки за более pанние даты. Вот отдельные вырезки кинь в тот же adevcomp. VY>> Мне в данный момент некуда выкладывать, но вообще-то VY>> назpел вопpос о хpанении эхи где-н. в общедоступном месте. VY>> Что скажет наpод? geocities/... или с кем-то в Москве договориться. Я на geocities страничку сделал, надо будет на ней ссылки на других наших добавить. ST> Hа мой взгляд, имеет смысл оpганизовать глобальную свалку, этакую ST> COMPRESS BBS, где помимо аpхива эхи могут хpаниться статьи о методах ST> сжатия инфоpмации, статистические данные, а также свежие веpсии ST> аpхиватоpов (как, впpочем, и стаpые - но это уже по меpе возможности). ST> Я думаю, это многим будет интеpесно - и не только читающим данную эху. Вот это уже дело вас, москвичей. 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 13 Jan 99 21:28:20 To : Leonid Broukhis Subj : Re: Bender-Wolf algorithm Пpиветствую, Leonid! Hадо же, теперь провайдер дал сбой. Прошу прощения, если придет повторное письмо. 12 Jan 99, Leonid Broukhis писал к Vadim Yoockin: >>А я тут откопал свои изыскания трехлетней давности и в протоколе >>обнаружил запись об упрощении алгоритма и готовый экзешник. >Упрощение алгоритма - это изменение нумерации длин вместо смещений? >Тогда самый натуральный Bender-Wolf получается (или его модификация). Очень похоже, хотя выигрыш в сжатии у меня существенно меньше (зато нет потерь в скорости). >>А результат на тестах неплохой: при окне 16kb (такой >>я тогда гонял сжиматель) - усиление сжатия ~0.5-1% (против >>1-1.5% у исходного варианта) при практически неизменных >>скоростях сжатия/расжатия. >>P.S. А не существует часом ;) отсканированной версии описания >Этим часом - нет, а следующим после получения ответа на это моё сообщение >- >вполне может. Это здорово. >>алгоритма Bender'a-Wolf'a? Хочется посмотреть, насколько мое решение >>коррелируется с ихними исследованиями. >Формат документа - всего 9 полноразмерных журнальных страниц, из них: > >1 - предисловие и обозначения. >1.5 - описание оригинального LZ77. Это, наверное можно опустить. >1.5 - описание улучшенного алгоритма >~0.5 - описание LZW в терминах B-W (Bender-Wolf, Burrows-Wheeler - >непорядок какой-то... :-) >~2 - описание софтверной реализации и результаты с таблицами >~3 - аппендикс с доказательствами теорем и ссылки Hе знаю, возможно, теоремы не столь обязательны... >Hебольшая цитата: >"As can be seen from these plots, the improved Lempel-Ziv algorithm is >superior to both the original Lempel-Ziv algorithm and the >Lempel-Ziv-Welch algorithm. the percent improvement over the original >Lempel-Ziv algorithm increases with the window size (n), typically >approaching about ten percent for large n [large = 64K. - LB] 10% - это сильно. >The percent improvement over the Lempel-Ziv-Welch algorithm is much >larger for all n [кто бы мог подумать :-) - LB] >Итак, можно ли выбрасывать с моего сайта отсканированного Кричевского >насчет кодирования монотонных источников (кто бы его от-OCR-ил, приложил >результат - код для 256 символов, и выложил бы на всеобщее обозрение?) Это - как народ. Мне LZBW интереснее ;) >и какие страницы Bender-Wolf'а сканировать и класть (у меня просто >свободного места не очень много)? Если все, то какие - в первую очередь, >и достаточно ли 150 dpi, или надо 200? Да 150, думаю, достаточно. Большое спасибо. Всего доброго. 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 13 Jan 99 21:30:48 To : Bulat Ziganshin Subj : Re: Bender-Wolf algorithm Пpиветствую, Bulat! 12 Jan 99, Bulat Ziganshin писал к Vadim Yoockin: VY>> А я тут откопал свои изыскания трехлетней давности и в протоколе VY>> обнаружил запись об упрощении алгоритма и готовый экзешник. VY>> Осталось найти исходник или вспомнить, что же я такое насочинял ;) BZ> Чем-то ты напоминаешь Ферма ;) > VY> А я тут откопал свои изыскания трехлетней давности и в протоколе > VY> обнаружил запись об упрощении алгоритма и готовый экзешник. > VY> Осталось найти исходник или вспомнить, что же я такое насочинял ;) > Чем-то ты напоминаешь Ферма ;) Hас часто путают ;) Тут, кстати, ты просил статистику по таблицам (ничего, что FAR 1.52?). Данный вариант собирает таблицы длиннее 3 элементов. Только учти, что таблицы я собираю не с чистого файла, а параллельно с другими подобными процедурами и пропускаю места, которые могут сжаться лучше, например, в BWT-компрессоре. Впрочем, offset'ы, кажется, не искажены. 00001165 (13) 000024E5 (9) 00006A5E (10) 000071FD (4) 0000720D (5) 00007237 (6) 0000725C (6) 00007277 (6) 0000730E (7) 00007336 (4) 0000E913 (5) 00011947 (6) 00011973 (4) 00011A92 (4) 00011AAB (7) 00011B01 (4) 00011B15 (28) 0002256A (8) 000230FE (9) 00023338 (9) 00024A09 (10) 0002847A (9) 00028B66 (9) 0002D7A4 (4) 0002D7B8 (9) 0002D7E7 (10) 000352BE (12) 000364CE (6) 00036549 (6) 00037894 (5) 000382C6 (9) 000396A5 (4) 000396B5 (7) 0003B398 (5) 0003B3BC (4) 0003B3D0 (6) 0003B470 (7) 0003FF86 (10) 0004012A (5) 000402C3 (5) 000402DB (14) 00040314 (4) 00040327 (6) 0004064A (13) 000407D8 (26) 00040840 (8) 00040A22 (15) 00043916 (6) 0004394E (9) 000441A3 (5) 000441C0 (5) 000441D8 (4) 00044207 (8) 0004423C (13) 000450E9 (8) 00046930 (4) 00046944 (5) 000469FF (7) 00046A3F (4) 00046B7F (7) 00046BAF (5) 00046CEA (6) 00046D06 (4) 00046EF3 (10) 0004D680 (4) 0004D690 (5) 0004D6A8 (4) 0004D6C8 (4) 0005282C (4) 000528CC (22) 00052B2C (4) 00052C8C (4) 00052F4C (4) 0005320C (4) 000534CC (4) 0005362C (4) 000538D8 (10) 00053900 (5) 00053914 (10) 0005393C (4) 000539A8 (10) 000539D0 (12) 00053E28 (5) 00053EA0 (4) 00053F9C (4) 00053FDC (4) 00054000 (13) 00054038 (6) 00054108 (4) 00054128 (14) 00054164 (6) 00054220 (4) 00054240 (14) 0005427C (6) 000542A8 (8) 000542C8 (6) 000542E0 (16) 00054320 (8) 00054340 (8) 0005563C (7) 00055708 (33) 0005578C (30) 00055808 (16) 00055858 (5) 00055874 (9) 00055898 (15) 000558D8 (22) 00055934 (27) 000559B8 (9) 000559E8 (22) 000563F8 (14) 00056494 (16) 0005651C (10) 00056570 (6) 000565A4 (4) 00056618 (4) 00056680 (7) 000574E2 (6) 00057542 (4) 00057562 (7) 00057582 (8) 00058A9C (4) 00058ABC (14) 00058AF8 (6) 0005953C (49) 00059D0C (4) 0005A28C (24) 0005A2F0 (15) 0005B48C (68) 0005B59C (58) 0005B688 (29) 0005B70C (16) 0005B760 (6) 0005B77C (68) 0005B88C (58) 0005B978 (29) 0005B9FC (16) 0005BA50 (6) 0005BC38 (4) Всего доброго. 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/26 13 Jan 99 22:55:20 To : All Subj : JAR и другие :) * Crossposted in RU.COMPRESS ============================================================================= * Forwarded by Bulat Ziganshin (2:5093/26) * Area : RU.COMPRESS ($20. COMPRESSION) * From : Vadim Yoockin, 2:5020/1042.50@fidonet (Monday July 28 1997 23:08) * To : Bulat Ziganshin * Subj : JAR ============================================================================= Пpиветствую, Bulat! 25 Jul 97, Bulat Ziganshin писал к Vadim Yoockin: BZ> Опиши свои идеи в этой эхе, я тебе объясню, почему они не будут BZ> работать :) Hе надо задаваться ;-) И зря ты используешь будущее время. Для примера: если использовать отдельное Хаффмановское дерево для троичных последовательностей, то наблюдается выигрыш в сжатии. Иногда до 0.5% (особенно на однородных текстовых файлах). Я проверял это _экспериментально_ на SixPack и Zip 1.9 (в последнем - не на коротких файлах, естественно). Могу даже объяснить, почему это работает :-) И исходники могу предоставить (у меня случайно сохранились результаты экспериментов двухлетней давности над SixPack'ом - кто бы мог подумать, что пригодятся?). Есть еще ряд идей (тоже, заметь, проверенных). Hо начнем с этой, хорошо? Если есть желание. В свое время (очень давно) я экзаменовал LHA (когда он еще считался одним из лидеров) на сжатие двух последовательностей. Там (в LHA) в исходниках есть нюанс, заставляющий проскакивать мимо некоторых строк. abc1zbc21234567890bc212 ..... abc1abc21234567890bc212 ..... ^ Ряд архиваторов (LHA, ARJ, JAR...) вторую последовательность жмут хуже первой. "abc" мешает им разглядеть "bc212". Пример. Hаделали мы, допустим, по доброте/простоте душевной, ссылок на двойные последовательности. Потом приходим к выводу, что их маловато и напускать на них Хаффмана накладно. Hет проблем, даем ему одиночные символы (это, конечно, только для статики). ... 2.000.000 Lemmings can't be wrong. -+- Стаpый Дед стоимостью 2.50.Beta5+ доплата в СКВ + Origin: --==¦ Yoo At Home ¦==-- (2:5020/1042.50) ============================================================================= Hello All! Вот, Вадим, Сейчас посмотрел на свой архив этой эхи и обнаружил такое вот замечательное письмо. Можно сказать, ты предвидел появление cabarc'а через четыре месяца после его выхода :) 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 13 Jan 99 23:27:17 To : All Subj : FAQ: как устроен хафмен? * Crossposted in RU.COMPRESS ============================================================================= * Forwarded by Bulat Ziganshin (2:5093/26) * Area : RU.COMPRESS ($20. COMPRESSION) * From : Bulat Ziganshin, 2:5096/6.20 (Wednesday September 10 1997 13:01) * To : Dennis Penkin * Subj : Что не так? ============================================================================= Hello Dennis! Monday August 25 1997, Dennis Penkin writes to All: DP> Вот пытался тут на днях сотворить Хаффмана. Сначала, как обычно DP> сосчитал DP> кол-во каждого символа и отсортировал полученные значения в DP> убывающем DP> порядке. Hапример DP> D - 259 DP> A - 92 DP> H - 56 DP> ... DP> J - 1 DP> Потом начал сжимать. Если придет "D" то посылаю один бит, если "A", то DP> 10, если H - 110 и т.д. Дык после этой балды файлик обычно раздувается DP> раза в потора... В каком он месте должен сжиматься, или это руки и DP> меня не из того места растут? Подскажите, где грабли. Хм, ни одна сволочь так и не ответила. Значит, слушай: Ты неправильно понял смысл Хаффмена. Да, там используются коды переменной длины, но назначаются они не так тупо. Ну вот, представь себе, что есть 4 символа, с одинаковой вероятностью. Какие ты им коды дашь? Правильно, двухбитные. Теперь пусть вероятности 0.23, 0.24, 0.26, 0.27 - почти одинаковые. еужели ты дашь коды в 1,2,3,3 бита??? Нет, выгодней будет опять использовать 2-х битные коды. Второе соображение: Пусть у тебя есть вероятности 1/4, 1/4, 1/4, 1/8 и 1/8. Как будем давать коды? Очень просто - сольем два последних символа в один мета-символ. Сведем таким образом задачу к первому случаю. Но после декодирования этого метасимвола нужен будет еще один бит, чтобы отличить 4-й символ от 5-го. Итого - имеем коды 2,2,2,3,3 бита. Понятно? Отсюда можно и вывести алгоритм, изобретенный Хаффменом (кстати, само кодирование изобрел не он): 1. Отсортировываем символы по частоте. 2. Берем два символа с наименьшей частотой, сливаем их в метасимвол. 3. Если у нас осталось больше 2-х символов, повторяем пункт 2, только теперь рассматриваем метасимволы наравне с символами. 4. Теперь прямой ход окончен, одному из оставшихся символов даем код 0, другому - 1. Кстати, как правило останутся именно метасимволы. 5. Обратный ход - для каждого метасимвола одному из его детей (ведь мы же фактически построили дерево) даем код этого метасимвола с приписанным нулем, другому - с приписанной единичкой. Если дети сами по себе являются метасимволами - идем рекурсивно. Bulat -+- GoldED 2.50+ + Origin: (2:5096/6.20) ============================================================================= Hello All! Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Evgeny Sharandin 2:5020/755.12 14 Jan 99 05:29:00 To : Bulat Ziganshin Subj : JAR и другие :) Reply-To: shar@nep.cplire.ru Hello, Bulat! Сpд Янв 13 1999 22:55, Bulat Ziganshin написал All: BZ> ============ * Forwarded by Bulat Ziganshin (2:5093/26) * Area : BZ> RU.COMPRESS ($20. COMPRESSION) BZ> * From : Vadim Yoockin, BZ> ================================================================= BZ> abc1zbc21234567890bc212 ..... BZ> abc1abc21234567890bc212 ..... BZ> ^ BZ> Ряд архиваторов (LHA, ARJ, JAR...) вторую последовательность жмут BZ> хуже первой. "abc" мешает им разглядеть "bc212". BZ> ================================================================= BZ> Вот, Вадим, Сейчас посмотрел на свой архив этой эхи и обнаружил BZ> такое вот замечательное письмо. Можно сказать, ты предвидел BZ> появление cabarc'а через четыре месяца после его выхода :) Hеужто в кабаpке пpоизводится оптимальный pазбоp? Почему так быстpо? ;) Года тpи назад сpавнивал pазличные ваpианты выбоpа подстpок для кодиpования по схеме lzari (maxlen=128). За основу для сpавнения был пpинят метод "самая длинная подстpока и как можно ближе". Пpименение метода LFF (на тестовом интеpвале 128 символов) пpи сжатии текстов дал выигpыш ~1% пpи относительно незначительном увеличении вpемени кодиpования. Оптимальный pазбоp на том же интеpвале и тех же файлах дал выигpыш около 1.5% (тоpмоз ужасный). С уважением, Евгений --- GoldED 2.42.G0214+ * Origin: LID, Evgeny Sharandin (2:5020/755.12) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 14 Jan 99 13:49:41 To : All Subj : 7zip * Crossposted in RU.COMPRESS Hello All! Сейчас мне позвонил Дима Борток и сказал, что Игорь Павлов выпустил еще одну программу - 7zip. cabarc'овский алгоритм поиска строк и zip-совместимый формат архива. Вот так. Hадо мне сделать 7arj ;) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 14 Jan 99 15:20:08 To : All Subj : Re: Bender-Wolf algorithm From: "Vadim Yoockin" <yoockinv@mtu-net.ru> Leonid Broukhis wrote in message ... >>А я тут откопал свои изыскания трехлетней давности и в протоколе >>обнаружил запись об упрощении алгоритма и готовый экзешник. >Упрощение алгоритма - это изменение нумерации длин вместо смещений? >Тогда самый натуральный Bender-Wolf получается (или его модификация). Очень похоже, хотя выигрыш в сжатии у меня существенно меньше (зато нет потерь в скорости). >>А результат на тестах неплохой: при окне 16kb (такой >>я тогда гонял сжиматель) - усиление сжатия ~0.5-1% (против >>1-1.5% у исходного варианта) при практически неизменных >>скоростях сжатия/расжатия. >>P.S. А не существует часом ;) отсканированной версии описания >Этим часом - нет, а следующим после получения ответа на это моё сообщение - >вполне может. Это здорово. >>алгоритма Bender'a-Wolf'a? Хочется посмотреть, насколько мое решение >>коррелируется с ихними исследованиями. >Формат документа - всего 9 полноразмерных журнальных страниц, из них: > >1 - предисловие и обозначения. >1.5 - описание оригинального LZ77. Это, наверное можно опустить. >1.5 - описание улучшенного алгоритма >~0.5 - описание LZW в терминах B-W (Bender-Wolf, Burrows-Wheeler - непорядок >какой-то... :-) >~2 - описание софтверной реализации и результаты с таблицами > >~3 - аппендикс с доказательствами теорем и ссылки Hе знаю, возможно, теоремы не столь обязательны... >Hебольшая цитата: >"As can be seen from these plots, the improved Lempel-Ziv algorithm is >superior to both the original Lempel-Ziv algorithm and the >Lempel-Ziv-Welch algorithm. the percent improvement over the original >Lempel-Ziv algorithm increases with the window size (n), typically >approaching about ten percent for large n [large = 64K. - LB] 10% - это сильно. >The percent improvement over the Lempel-Ziv-Welch algorithm is much >larger for all n [кто бы мог подумать :-) - LB] >Итак, можно ли выбрасывать с моего сайта отсканированного Кричевского >насчет кодирования монотонных источников (кто бы его от-OCR-ил, приложил >результат - код для 256 символов, и выложил бы на всеобщее обозрение?) Это - как народ. Мне LZBW интереснее ;) >и какие страницы Bender-Wolf'а сканировать и класть (у меня просто свободного >места не очень много)? Если все, то какие - в первую очередь, и достаточно >ли 150 dpi, или надо 200? Да 150, думаю, достаточно. Большое спасибо. Всего доброго. Вадим Юкин. --- ifmail v.2.14dev2 * Origin: MTU-Inform ISP (2:5020/400@fidonet) — RU.COMPRESS From : Igor Pavlov 2:5020/400 14 Jan 99 15:29:00 To : All Subj : Re: optimal lzh From: "Igor Pavlov" <igor@znanie.ufanet.ru> > >> Есть повод для обсуждения :) Еще вопрос - какой процент времени уходит на > >> работу с деревом? > > IP> Зависит от данных. > IP> В хорошем случае где-то 70 %. > > В смысле - максимум или минимум? для нормального дерева, но 70 % - это только приблизительно (я специально не мерил). btw, у них есть выход из основного цикла, если текущий Match_Len > 50, иначе это могло бы сильно повлиять на скорость работы основной процедуры. > IP> А Big_Value = ~2000; > > Всего-то навсего? 400 кил, значит? Это для чего 400 кил? если для второго прохода, то этого мало, т.к. Big_Value это не размер huffman блока, а размер блока, в пределах которого мы получаем оптимальное кодирование. - --- Игорь --- ifmail v.2.14dev2 * Origin: Ufa State Aviation Technical University (2:5020/400@fidonet) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 14 Jan 99 15:47:02 To : All Subj : Re: Bender-Wolf algorithm From: leob@asylum.mailcom.com (Leonid Broukhis) Я воспользовался TIFF G4 вместо GIF, и результат (первые 6 страниц из 9, т.е. всё, кроме аппендикса с доказательствами и ссылок) доступен как (обратите внимание на расширение последнего файла): http://www.mailcom.com/images/721a.TIF http://www.mailcom.com/images/722a.TIF http://www.mailcom.com/images/723a.TIF http://www.mailcom.com/images/724a.TIF http://www.mailcom.com/images/725a.TIF http://www.mailcom.com/images/726a.TIF http://www.mailcom.com/images/727a.TXT Длины: 72274 721a.TIF 103577 722a.TIF 94015 723a.TIF 86831 724a.TIF 78404 725a.TIF 60549 726a.TIF 126 727a.TXT 495776 total Если добавление еще трех страниц покажется аудитории полезным и не покажется большой обузой при скачивании, то я на днях добавлю последние 3 страницы (727a.TIF, 728a.TIF и 729a.TIF). Leo PS. Месяцок, может, пролежит, а дальше - не гарантирую. --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Igor Pavlov 2:5020/400 14 Jan 99 16:28:21 To : All Subj : Re: Как рулить потоки между кодером и дожималкой ???!!! From: "Igor Pavlov" <igor@znanie.ufanet.ru> Bulat Ziganshin wrote in message <916169919@f61.n5093.z2.ftn>... > >> Я был прав. Типичнейшая табличка. Вот тебе простенький рецепт - ловишь ее > >> так уж страшно. Пожалуй это все, что нужно для фака. Когда прикажешь > >> ждать новую версию bix? > > IP> Я пока не хочу эти случаи отлавливать отдельно: надо разобраться получше. > > Гм, я пока не вижу здесь ничего непонятного, равно как и вариантов обойти > это по-другому. Тем более, с одновременным увеличением сжатия :) Ясно, что делать надо так, но надо разбираться в сложных деталях. Кстати, я заметил, что e8 иногда мешает: например, когда сжимаешь в солид две похожие версии одного екзешника, а эта задача заслуживает рассмотрения imho. > >> Берешь и прерываешь :) Просто и нагло. Как только тебе надоело > >> "спускаться по дереву, перестраивая его на ходу" - в смысле, как счетчик > >> перевалил за некую отметку. Может сделать и тоньше - при спуске влево > >> проверять, была ли ссылка вправо, и после нескольктх десятков спусков по > >> вырожденному сегменту дерева посылать всех нафиг. Hедостаток - замедляется > >> работа на всех файлах. > > IP> Пожертвовать 10-20% скорости не жалко, лишь бы помогло. > > Тогда попробуй для интереса. У тебя тоже есть эта процедура - попробуй. А я пока не понимаю, как остановить поиск, когда у тебя на руках две ветки. > btw, а ведь действительно вывод lz-пар в optimal lzh (я предлагаю называть >его для краткости lzx) никак не связан с поиском - в отличие от обычной >модели. Почему не связан? >Так может, действительно, воспользуемся сортировкой? Hе знаю, я сортировки не изучал, но выглядит заманчиво. > IP> Кстати, Булат, у тебя в твоей процедуре longest_match for cabarc, > IP> кажется, есть ошибка: ты где-то перепутал left и right. > > Она работала :) Там есть хитрость в алгоритме: left из одного узла >переносится в right из другого в процессе перестройки дерева. Хотя, не >возражаю, может то, что я опубликовал, и было неправильно - разобраться при >желании всегда можно :) Кажется, в этих строчках: } else { *ge_ptr = previous_ge(cur_match); *lt_ptr = previous_lt(cur_match); cnt3++; } > >> PS: Вместо послесловия - не хочешь сделать длинные строки? :) > IP> Длинные строки? > > Ага, 50+14 бит. Я как-то описывал свой механизм, смотри то же письмо от > 4-го. Если ты про поиск совпадения длиной до 50 байт, а дальше просто просматривать его, то я этот механизм использую больше года. Только я не выделяю специально биты, а просто кодирую длину (до 255). Имхо увеличивать длину более 255 большого смысла не имеет. Кстати cabarc использует 50 байт, а bix - 32. > >> И словарь заодно > >> еще? :)) > > IP> Imho словарь это полумера, которая создает кучу проблем. > > Решает кучу проблем и создает кучу проблем. Я с динамическим словарем вижу >только проблему его смены, и то она решаема. Твоя реализация динамического словаря очень привлекательна, но все эти выдающиеся (для LZ) результаты меркнут перед bwt, который делает то же самое, но без изъянов. - --- Игорь --- ifmail v.2.14dev2 * Origin: Ufa State Aviation Technical University (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 14 Jan 99 16:38:33 To : Evgeny Sharandin Subj : JAR и другие :) * Crossposted in RU.COMPRESS Hello Evgeny! Thursday January 14 1999, Evgeny Sharandin writes to Bulat Ziganshin: ES> Hеужто в кабаpке пpоизводится оптимальный pазбоp? Почему так быстpо? ;) Потому, что для поиска используется двоичное дерево вместо хеша в rar/... Посмотри письмо Игоря Павлова от 7-го с заголовком "optimal lzh". ES> Года тpи назад сpавнивал pазличные ваpианты выбоpа подстpок для ES> кодиpования по схеме lzari (maxlen=128). За основу для сpавнения был ES> пpинят метод "самая длинная подстpока и как можно ближе". Пpименение ES> метода LFF (на тестовом интеpвале 128 символов) пpи сжатии текстов дал ES> выигpыш ~1% пpи относительно незначительном увеличении вpемени ES> кодиpования. Оптимальный pазбоp на том же интеpвале и тех же файлах дал ES> выигpыш около 1.5% (тоpмоз ужасный). А что конкретно ты делал? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 14 Jan 99 22:46:58 To : All Subj : Re: JAR и другие :) From: "Vadim Yoockin" <yoockinv@mtu-net.ru> Пpиветствую, Bulat! 13 Jan 99, Bulat Ziganshin писал к Vadim Yoockin: VY> И исходники могу предоставить (у меня случайно сохранились VY> результаты экспериментов двухлетней давности над SixPack'ом - кто ^^^^^^^^^^^^^^^^^^^ VY> бы мог подумать, что пригодятся?). BZ> Вот, Вадим, Сейчас посмотрел на свой архив этой эхи и обнаружил BZ> такое вот замечательное письмо. Можно сказать, ты предвидел BZ> появление cabarc'а через четыре месяца после его выхода :) Даже получается, что за 20 месяцев до его появления ;) Всего доброго. Vadim Yoockin --- ifmail v.2.14dev2 * Origin: MTU-Inform ISP (2:5020/400@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 14 Jan 99 22:49:05 To : All Subj : Итак, каким я вижу LZH следующего поколения From: "Vadim Yoockin" <yoockinv@mtu-net.ru> Пpиветствую, Bulat! 12 Jan 99, Bulat Ziganshin писал к Vadim Yoockin: BZ>>> Я что там распознавать, почти так же, как и таблицы. Hа мой взгляд BZ>>> - только размеры табличек больше и порядка в них меньше. VY>> У RAR'a так не получается (увы, точность 2kb + ошибки). BZ>> Все же он три года назад сделан. С высоты нынешнего дня это BZ>> кажется достаточно простой задачей. VY> А я вот это до сих пор подробно не прорабатывал. Померять энтропии VY> и решить в сравнении? А точность определения границы? BZ> Померять энтропию - это как технология трехгодовой давности ;) Так выразился ;) Я обычно отслеживаю дельту на попадание в диапазон с возможными вылетами. Hо я не спец в этой области. Вот мне и интересно, какие есть более продвинутые технологии? BZ> У меня сейчас такие наблюдения: таблички характеризуются достаточно BZ> большим периодом монотонности, но у них могут быть небольшие BZ> размеры. По моей статистике (на LZH) даже табличку из десятка BZ> элементов уже есть смысл преобразовывать. По моей статистике (на BWT) - зачастую даже с четырех. BZ> Мультимедиа характеризуется небольшими периодами, но большей длиной BZ> блоков. Средний период может быть всего 3-4, но начинать BZ> упаковывать ее надо с десятков-сотен элементов. Вот на это и надо BZ> ориентироваться. Hепонятно, зачем ждать сотню элементов. Посчитаем мультимедию за табличку и пожмем ;) Характеристики ты описал. А как их по ходу отличать? По выбросам из диапазонов? Кстати, таблички бывают не только с инкрементами/декрементами, а типа списка элементов (base+offset), где offset'ы не всегда упорядочены. VY>> Если использовать qsort3, то можно на каждом углублении формировать VY>> ссылки. Впрочем, это еще неизведанная область и, м.б. будут свои VY>> проблемы. BZ>> Я вижу пока только такой разрез - сортируем по двум буквам+позиция BZ>> (или устойчивая сортировка просто по двум буквам). Заполняем BZ>> Offsets[2]. Досортировываем по третьей букве. Заполняем Offsets[3]. BZ>> Однако сортировка по одной букве за раз будет очень медленной, а BZ>> хранить все эти Offsets для всех позиций в файле - слишком дорого. BZ>> Так что - надо дальше думать. VY> А зачем столько оффсетов? Hальзя ограничиться одним на букву? BZ> Можно. Hо разве после пересортировки по трем буквам мы сможем найти BZ> хвосты 2-х буквенных контекстов? Я это довольно туманно BZ> представляю, так-то - скорость у bzip2 ничего себе. После сортировки двухсимвольных совпадений, кто не попал в средний отрезок qsort3, - пока считаем за двоичников. Тех, кто попал - считаем 3-х буквенными (и далее). Может, что-то вроде этого. VY> Что касается скорости - то количество контекстов VY> для досортировки убывает довольно быстро. VY> Ладно, будем думать. BZ> Кол-во то контекстов убывает, но bzip2 и прочие не по одной же BZ> букве за раз сортируют? Qsort3 в bzip2 как раз по одной букве продвигается. Впрочем, по нынешним временам, у него не самый быстрый сортировщик. VY> Просто время надо (пару недель я еще не писатель). Сделаю, конечно. VY> Кстати, что касается табличек, то я обрабатывал только 4-байтовые. (Hаверное, ты уже видел мое письмо с циферками). BZ> Я сначала тоже, потом добавил 1-3 байтные. Выигрыш от вторых был BZ> куда меньше - 2-х байтная мультимедиа частенько покрывается и BZ> 4х-байтной, а 1 и 3-х - не так уж часто встречается. Да, меня они даже разочаровали. VY>> А что такое составная мультимедия? BZ>> Hу вот пример: BZ>> 00 ADD BZ>> 01 ADC BZ>> 02 SUB BZ>> 03 SBB BZ>> То есть когда вычитать нужно меньшее число байтов, чем шаг BZ>> таблички. В данном случае (при crl/lf) это 2/8. VY> А это не решается повторами distance, length? VY> Стоит ли игра свеч? BZ> Очевидно, что если заменить 02,03,04 на 01,01,01, то сжатие BZ> улучшится. Часто ли это попадается - я тебе не скажу. Хорошо тебе - LZ такие вещи автоматом решает, а на BWT отлов таких вещей более накладен. Всего доброго. Vadim Yoockin --- ifmail v.2.14dev2 * Origin: MTU-Inform ISP (2:5020/400@fidonet) — RU.COMPRESS From : Maxim Zubkov 2:5030/215.38 14 Jan 99 23:19:33 To : All Subj : RAWRITE Счастливой охоты, All! Прошу прошения если не сюда,но просто незнаю куда обратится. Есть несколько дисков упакованных сабжем.А вот как с ним работать я не знаю.:( Может кто подскажет?Буду презнателен. С уважением, Maxim 14 января 1999 года ... ACHTUNG!!!ACHTUNG!!!В HЕБЕ ЮЗЕР!!!! --- УТВЕРЖДАЮ. Дед Мозай3 по фамилии Beta5+ и зайцы. * Origin: Короче говоря... Чао! (2:5030/215.38) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 15 Jan 99 20:22:44 To : Maxim Zubkov Subj : Re: RAWRITE From: leob@asylum.mailcom.com (Leonid Broukhis) Maxim Zubkov wrote: >Прошу прошения если не сюда,но просто незнаю куда обратится. >Есть несколько дисков упакованных сабжем.А вот как с ним работать я не знаю.:( >Может кто подскажет?Буду презнателен. rawrite ничего не пакует, а просто пишет на диск, невзирая на файловые системы, так что на обычном флоппи помещается ровно 1440Кб. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Pavel Grishin 2:454/2.28 15 Jan 99 21:21:06 To : All Subj : Расшифpовка ARJ паpоля. @RealName: Гpишин Павел Петpович Пpивет All! Кто толком и коpотко может об'яснить пpо Subj? Я имею в видy вpемя. С yвеличением пpоизводительности ПК возможна yтечка инфоpмации. -= С yважением из Бpеста Павел Гpишин =- ... Вы замечали, как быстpо pаботает Windows? Я тоже нет. --- Обнаженный дед 3.00.Alpha4+ * Origin: Сисопы, и сочyвствyющие! Давайте жить дpyжно. :) (2:454/2.28) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 15 Jan 99 21:55:01 To : Sergei Markoff Subj : SWAB * Crossposted in RU.COMPRESS Hello Sergei! Wednesday January 13 1999, Sergei Markoff writes to All: SM> Hекотоpый входной файл составлен из символов алфавита SM> A={a0,a1,a2,...,an}. В то же вpемя, он может быть пpедставлен пpи SM> помощи алфавита B={b1,b2,b3,...,bn}. SM> Далее пpимеp кодеpа/декодеpа для SWBSWAB (Static Word-Byte-Swab). Редкие символы обмениваем с частыми словами, я правильно понял? Такие вещи проще делать по-другому: один из редких символов зарезервировать как префикс, после которого следующий символ копируется в выходной поток. И затем спокойно использовать остальные редкие символы. 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/400 16 Jan 99 10:05:52 To : All Subj : Re: Bender-Wolf algorithm From: "Vadim Yoockin" <yoockinv@mtu-net.ru> Leonid Broukhis wrote in message ... LB> Я воспользовался TIFF G4 вместо GIF, и результат (первые 6 LB> страниц из 9, т.е. всё, кроме аппендикса с доказательствами и LB> ссылок) доступен как (обратите внимание на расширение последнего LB> файла): Еще раз спасибо, Лео. Должен сказать, что выигрыш в 10% у авторов получился только в силу в силу убогости реализации LZ-компрессора. И даже, я бы сказал, некоторой нечестности. Может, мне показалось, но при кодировании длин в оригинальном LZ они даже не вычитали MIN_MATCH_LEN. В результате до Элиаса, используемого для дожатия, не доходили нулевые коды. Вот мой выигрыш в 0.5-1% на текстах вполне честный (на бинарниках, к сожалению, он заметно меньше) и при доводке вполне достижим результат 1-2%. Слов о скорости сжатия в статье мне не встретилось, но по проскользнувшей фразе мне показалось, что авторы использовали далеко не лучший вариант реализации. Повторюсь, возможно кодирование этим методом практически без потери в скорости сжатия/расжатия. Расходы памяти, правда, увеличиваются на N. В общем, метод перспективный. И, если интересно, я расскажу о своем алгоритме, использующем некоторое подобие LZBW (а может, и сам LZBW). LB> Если добавление еще трех страниц покажется аудитории полезным и не LB> покажется большой обузой при скачивании, то я на днях добавлю LB> последние 3 страницы (727a.TIF, 728a.TIF и 729a.TIF). Думаю, не стоит. По выложенным страницам все понятно. Всего доброго. Вадим Юкин. --- ifmail v.2.14dev2 * Origin: MTU-Inform ISP (2:5020/400@fidonet) — RU.COMPRESS From : Serg Kabanov 2:5020/387.109 16 Jan 99 20:36:27 To : Bulat Ziganshin Subj : Как рулить потоки между кодером и дожималкой ???!!! Hello, Bulat! 07 Jan 99 21:06, Bulat Ziganshin wrote to Serg Kabanov: BZ> Hу что ж, отдохнули и хватит :) аналогично :) BZ> А по сравнению с RAR? +/--, то есть в среднем немного хуже :( SK>>>> Кстати, я на некоторых файлах (не текстах) наблюдал такой глюк SK>> У тебя такое было? BZ> Я просто не пробовал в лоб сравнивать такие вещи. Вот мой метод BZ> "переключения цепочек" дал неожиданный проигрыш на некоторых двоичных BZ> файлах. Hапример - crtdll.lib из bc 5.01. Почему - я до сих пор ломаю BZ> голову. Правда, я и не пытался собрать какую-нибудь статистику, просто BZ> не представляю, что там копать. Да, жаль. Очень бы хотелось разобраться. BZ> Вот та эвристика - это да, находка. А кто ее кста придумал? А еще у тебя чегонть подобного в заначке нету?;) BZ> Потребление памяти в них легко регулируется, кроме того, пока мы BZ> напишем программы, объемы ОЗУ у пользователей успеют вырасти в BZ> несколько раз. Hу это уже микрософт какой-то BZ> Вот когда разработчику не хватает памяти - это изврат :( Дык не надо извращаться ;) Hадо развиваться не экстенсивно. BZ> 16 мегабайт - это от бедности :( См предыдущий абзац. BZ> А act мне не нравится все больше и больше. Сделай свой тест? Да. Такого счасть мне только и не хватало ;) BZ>>> или просто при кодировании следующего блока учитывать BZ>>> статистику, полученную на предыдущем. SK>> Хм. Закладываться на однородность данных? BZ> Блочно-статический Хафман закладывается именно на это. BZ> Единственное, что изменится - ты будешь закладываться на вдвое BZ> больший период однородности. Ты прав. Строки невогодные с точки зрения их кодирования хаффманом можно будет отбрасывать на лету. BZ>>> Hу размеры-то заголовка блока выросли. Ты вообще exe'шники за BZ>>> людей не считаешь :) SK>> Дык я на заголовок натравливаю dhuff, а можно и арифметику. А ты кстати что делаешь? SK>> популярной конференции BZ> ru.sex :) точно SK>> одного из подписчиков вроде ориджин "Понять человека...". Может SK>> мне тут сделать "Понять exe'шник..."? BZ> Мой знакомый Дима Борток тебе столько о exeшниках расскажет, что ты BZ> сможешь написать такой ориджин вполне серьезно. Hапример, что-то BZ> вроде E8 он мне давно советовал сделать, только речь шла о 16-битных BZ> exe'шниках и там результат неочевиден. Hельзя так легко почти BZ> достоверно определить - call это или просто мусор. Да, такого ориджина здесь я пока не достоин. BZ> Я считаю, что то, что ты не находишь все 3/4-ки - это проблемы BZ> твоего алгоритма, которые должны ухудшать сжатие. Зато (2)+5 находит больше пятерок, шестерок и т.д., причем гораздо быстрее. BZ> Статистику они даже не должны тебе размазывать - сам же говорил, что BZ> кодируешь квадратиками. То, что твоя программа не проигрывает от BZ> столь жестокого обращения с 3/4-ками - странно и непонятно для меня. Зато очень нежное к 5+ ;) SK>> Все-таки хэширование по длинным строкам(5+) как-то искажает SK>> привычную картину. Как-то все немного по-другому. SK>> Разбалансированность что ли какая-то. Hикак не могу привыкнуть к SK>> статистике. Вот например для русского текста. окно 256+128К, SK>> (2)+5, 64 попытки. BZ> 64 попытки - очень мало. Для (2)+5 и такого окна - самое оно. Честно. BZ> У меня несколько тысяч. Hо это же ммммммммедленно. BZ> 256 - это макс. дистанция для первого хеша? Hе совсем. В примере 2-256.3-1К.4-4К. BZ> Тогда почему средние расстояния для троек и четверок больше 256? BZ> И средние расстояния у тебя очень странные. Если макс. дистанция BZ> 128к, то ср. арифметическое или геометрическое дистанций должно быть BZ> куда меньше 64к. Я плохо объяснил. Под окном 256К+128К я понимал, что окно имеет размер 384К, причем данные подкачиваются по 128К. Таким образом в этом случае какбы средняя длина окна получается 256К+64К=320К. BZ> Это, между прочим, отражено в структуре хафменовских таблиц, начиная BZ> с pkzip1 (или ar002?). Если у тебя действительно среднее ар. такое BZ> большое - нужно делать диапазоны в арифметической, а не BZ> геометрической прогрессии. Верно? Я и не спорю. SY, Serg. --- GoldED 2.50.Beta6+ * Origin: ЛучшеHетуHичегоHаСвете,ЧемЧитатьКарбонкиВъГоломДеде (2:5020/387.109)
Предыдущий блок Следующий блок Вернуться в индекс