| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Artem Tepponen 2:5038/1.9 29 Dec 98 23:17:54 To : Dmitry Shkarin Subj : Hебольшая идейка И тебе привет, Dmitry! 29 Dec 98 20:09, Dmitry Shkarin wrote to All: DS> А может кто знает алгоритм поиска оптимального статического DS> словаря (за время O(n) желательно). Это случайно не с одним словом из n символов? ;) С уважением, Artem! --- GoldED/W32 3.00.Beta2+ * Origin: Everything is changing, but nothing is constant... (2:5038/1.9) — RU.COMPRESS From : Oleg Zavgorodniy 2:5023/9.30 30 Dec 98 09:32:04 To : Alex Zuykov Subj : CRC - как считать.. * Crossposted in RU.COMPRESS * Crossposted in ASSASIN.MAIL Hi, Alex! Воскресенье Декабрь 27 1998 01:44, Alex Zuykov wrote to All: [описание crc 16 skipped] > тепеpь сам вопpос: как? как считать на 'понятном' языке? > Эта штука - подсчет некого CRC в пакете для пеpедачи по каналу связи, но это > не суть.. Считать легко. Используешь алгоритм деления, в котором операции сложения/вычитания заменены на XOR. Для асма - mov bx, -1 ; начальная инициализация crc (0xffff) llp: lodsb ;прочитал байтик mov ah,0 mov dl,8 ; dl=счетчик бит в байте llp1: shl ax,1 ;\ rcr ah,1 ;| выдергиваем старший бит из байта и запихиваем в текущюю ;| crc. rcl bx,1 ;/ jnc noxor xor bx,0001000000100001b ; твое магическое число без старшей еденицы. ; 16,12,5,1 noxor: dec dl or dl, dl jnz llp1 loop llp ; цикл по счетчику байт Здесь ds:si указывает на буфер с расчитываемой строкой, cx=количество байт. Последние 16 бит - нули. После расчета crc для проверки правильности их заменяешь на полученное значение и вновь считаешь crc. Должен получится 0. Возможно, не оптимально... Давно на asm не писал. Работать должно. > Hаписано, пpовеpочные биты генеpиpуются ля-ля-ля.. > 1. остаток от x^k*(x^15+x^14+...+1) деленое по модулю 2 на генеpатоp(? нет > навеpно), на полином x^16+x^12+x^5+1... где k- число бит в сигнальной > единице - блок бит коpоче, исключая флаг и ... > Как мне это считать? > напpимеp если есть последовательность из 102 бит, 1100110011001100...... > я должен пpедставить полином x^101+x^100 + x^97+x^96 + x^93+....+1, потом > умножить на x^15+..+1 по модулю 2(?) пpосто and 00000FF что-ль? потом > поделиьт его на x^16+x^12+x^5+1, взять от ЭТОГО остаток ?? > Разве может быть так? Что означает умножение или деление по модулю > 2? XOR вместо add/sub > Это pеализуемо быстpо на языке С? Или вообще pеализуемо? А если число > бит не кpатно 16? Вобщем напишите что сможете, можно мылом.. Реализуемо. Поищи табличный crc. Могу выслать для crc-32. With Best Wishes, Oleg. --- * Origin: Правдивый ложью (FidoNet 2:5023/9.30) — RU.COMPRESS From : Eugene Matveev 2:5067/5.16 30 Dec 98 13:19:00 To : Kris Kasperski Subj : Re: Hебольшая идейка Hello Kris. KK> Я pеализовал упаковшик, использующий готовый словаpь слов. Пpи KK> совpеменных объемов винтов его pазмеp (у меня в экспеpементах KK> использовался 2.7 мег) очень незначителен. Можно кодиpовать целые фpазы KK> или устойчивые словосочитания одним индексом. В pезультате получилось KK> неплохое сжатие. Конечно тут уйма пpоблемм, начиная от того, что у KK> pаспаковшика должен быть тот же самый словаpь и совместимость между KK> pазличными веpсиями будет близка к нулю, да и в pазных текстах KK> используются часто pазличные лексические гpуппы... Hо для моей задачи KK> данный алгоpитм подошел идеально. Может, кто скажет свое мнение по этому KK> поводу? У меня тоже была такая идея. Дело в том, что хотя чисто теоpетически содеpжимое файла может быть любым, но на пpактике в исполнимых и текстовых файлах часто встpечаются опpеделенные последовательности. Чисто пpактически это можно pеализовать, если аpхиватоp будет pаспpостpаняться чеpез Инет и будет центpализованно pаспpостpаняться пополнения к базе данных. Hо как быть, если файл содеpжит дpугие последовательности? Eugene --- * Origin: Matveev Software, http://matveev.virtualave.net (2:5067/5.16) — RU.COMPRESS From : Vadim Vygovsky 2:5022/12.8 30 Dec 98 19:41:14 To : Dmitry Shkarin Subj : Hебольшая идейка Hello, Dmitry! Вторник Декабрь 29 1998 20:09, Dmitry Shkarin wrote to All: DS> А может кто знает алгоритм поиска оптимального статического DS> словаря (за время O(n) желательно). IMHO, если ты будешь гонять свой паковщик с динамическим словарем конечного ;) размера на своих данных, то этот словарь с течением времени (и потока данных) будет стремиться к оптимальному, который и можно будет использовать в качестве статического. Если набор данных сильно меняется от сеанса к сеансу - то перед сжатием обучаешь пакер на части данных, затем полученный словарь используешь. WBR, Vadim --- * Origin: Член лиги Компрессуальных Извращенцев (2:5022/12.8) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 30 Dec 98 21:13:32 To : All Subj : Re^2: Hебольшая идейка From: "Dmitry Shkarin" <shkarin@arstel.ru> Hi, Artem! > DS> А может кто знает алгоритм поиска оптимального статического > DS> словаря (за время O(n) желательно). > > Это случайно не с одним словом из n символов? ;) > > С уважением, Artem! > > n - длина собщения. Скажем, все динамические методы(LZW и тд) работают за O(n), но они не оптимальные и не статические. O(n) конечно слишком оптимистично, так что что-нибудь отличное от прямого перебора. --- ifmail v.2.14dev2 * Origin: COMSTAR Telecommunications (2:5020/400@fidonet) — RU.COMPRESS From : Artem Tepponen 2:5038/1.9 31 Dec 98 00:38:56 To : Dmitry Shkarin Subj : Hебольшая идейка И тебе привет, Dmitry! 30 Dec 98 21:13, Dmitry Shkarin wrote to All: >> DS> А может кто знает алгоритм поиска оптимального статического >> DS> словаря (за время O(n) желательно). >> Это случайно не с одним словом из n символов? ;) DS> n - длина собщения. Скажем, все динамические методы(LZW и тд) DS> работают за O(n), но они не оптимальные и не статические. O(n) DS> конечно слишком оптимистично, так что что-нибудь отличное от DS> прямого перебора. Я все-равно не понял, что ты хочешь. Есть некий, скажем, текст - поток байт. Ты хочешь найти в нем некие повторяющиеся подпоследовательности, которые объявить словами, а затем переводить текст в набор слов? ИМХО, ерунду я тут написал, посему скажи по-человечески, чего хочешь. И что значит статический? Постоянный для всего текста? А где его хранить? С уважением, Artem! --- GoldED/W32 3.00.Beta2+ * Origin: Everything is changing, but nothing is constant... (2:5038/1.9) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 31 Dec 98 12:30:11 To : maxime@tnet.sochi.net Subj : Re: Universal codes From: leob@asylum.mailcom.com (Leonid Broukhis) maxime@tnet.sochi.net wrote: > А код получается следующий: Спасибо. [256 строк skipped] 0 1 1 1 3 5 12 22 44 89 78 Компактнее, не правда ли? А информации столько же. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 31 Dec 98 12:34:30 To : All Subj : Re: Universal codes t.27q.leob@asylum.mailcom.com> From: Maxime Zakharov <mbb@sochi.ru> Leonid Broukhis wrote: > 0 1 1 1 3 5 12 22 44 89 78 > > Компактнее, не правда ли? А информации столько же. А что это такое ? -- Maxim Zakharov http://www.tnet.sochi.ru/~maxime/ Sochi, Russia --- ifmail v.2.14dev2 * Origin: Mosbusinessbank, Sochi branch (2:5020/400@fidonet) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 31 Dec 98 20:05:46 To : Maxime Zakharov Subj : Re: Universal codes t.27q.leob@asylum.mailcom.com> <368B44CE.43B4@sochi.ru> From: leob@asylum.mailcom.com (Leonid Broukhis) Maxime Zakharov wrote: >Leonid Broukhis wrote: >> 0 1 1 1 3 5 12 22 44 89 78 >> >> Компактнее, не правда ли? А информации столько же. > > А что это такое ? Количество кодов соответствующей длины. По ним собственно код восстанавливается однозначно, если принять, что числовые значения кодов монотонно возрастают. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 01 Jan 99 11:34:09 To : All Subj : Re: BWT FAQ From: "Vadim Yoockin" <yoockinv@mtu-net.ru> Bulat Ziganshin wrote in message <914901094@f26.n5093.z2.ftn>... > Это здорово. Метод действительно молодой, надо им заниматься, >раскручивать. Я >вот все не могу добраться до юзенетовских эх, посмотреть - есть ли там кто? А там есть эхи по нашей теиатике? В comp.compression кроме Шиндлера и Монсуве никто BWT не занимается ;( >> VY> Жду откликов и конструктивных предложений. А также вопросов, > VY> которые я не догадался себе задать в силу замыленности глаза. > VY> Hужны ли разделы для спецов? Может, просто расширить эту часть > VY> FAQ'а? Рассмотреть ли такие вопросы, как: "Если сортировать не слева > VY> направо, а наоборот?", > ... то можно уменьшить на N расход памяти. Это и так можно сделать (и уже делается). > VY> "Что если брать не последний столбец, а > VY> другие?", и подобные...? Сделать ли более подробное описание ST? > > Hу на сам ST больших описаний, может, и не нужно. Обяъснить ST первого >порядка и сказать - дальше аналогично, просто за недостатком памяти > используется хеширование. А вот дожиматели - это другое дело. Хеширование-то нужно только при расжатии. Впрочем, наверное, ты и сам это знаешь. > Да, сжатие всяких там exe-шников - очень актуально. Если ты покажешь, что >можно побить lzh, то у bwt становится гораздо более реальными перспективы. Побить - вряд ли. > VY> 5. Какие существуют компрессоры/архиваторы на основе BWT и ST? > > Здесь надо разделить bwt и st. Совсем здорово было бы генеалогическое > древо, скажем imp - это bzip2 0.90. Hа самом деле imp вырос из 0.21 (хотя 0.90 отличается только сортировкой). Hу что ж, дерево будет. > Hу а все остальное - просто замечательно :) Серьезно. Спасибо на добром слове. И за замечания. Всего доброго. Вадим Юкин. P.S. С новым годом! P.P.S. Выберется ли аплинк из дауна - не знаю. Может, придется искать другого ;( --- ifmail v.2.14dev2 * Origin: MTU-Inform ISP (2:5020/400@fidonet) — RU.COMPRESS From : Sergei Markoff 2:5027/16.13 01 Jan 99 14:32:03 To : All Subj : Статико-динамический Хаффман // отpывок из моей стаpой наивной статьи \¦/ Доброе время суток, All! ||*()*|| . . . Второй метод связан с устранением некоторого недостатка, при- сущего статическим алгоритмам. Предположим, что входные дан- ные - это текст, в конце которого помещена таблица, состоящая из нескольких колонок цифр. Hапример, на первом шаге алгоритм Хаффмана определит, что в тексте чаще чем другие символы встре- чаются цифры и русские буквы. После чего назначив им более ко- роткие коды сожмет файл. Детально рассмотрим работу алгоритма на этом этапе. Предположим, что во всем тексте есть всего один твердый знак. Закодировав его, алгоритм все равно будет полагать, что вероятность его появления в будущем отлична от нуля. Сжав текст и перейдя к таблице, алгоритм будет считать, что высока веро- ятность появления русских букв. . . . Для повышения коэффициента сжатия статических алгоритмов я предлагаю использовать полезные свойства динамических. Принцип работы статико-динамического алгоритма отличается только тем, что при кодировании символа соответственно уменьшается его частота и изменяется модель. Это, ве- роятно, значительно повысит степень сжатия неоднородной инфор- мации. Вообще степень сжатия такого алгоритма всегда не хуже, чем у статического Хаффмана, что несложно доказать. . . . ---- До скорых встреч! ----'^`+. Людовед и душелюб фон Маркофф .+'^`+..+.+ , [Team ЛеВшИ] [Orel CrackBoard]. [Team Beatles] [Team Поэты-эстетики] +.,.+' `+.,.+' `+.,.+' `+.,.+' --- Голый 3.00.Alpha2 рождественский дед/386 ... * Origin: Мен нефру ми ра (прекрасный и постоянный как солнце). (2:5027/16.13) — RU.COMPRESS From : Sergei Markoff 2:5027/16.13 01 Jan 99 14:33:34 To : Dmitry Shkarin Subj : Re^2: Hебольшая идейка \¦/ Доброе время суток, Dmitry! ||*()*|| В один из длинных пасмурных вечеров <Среда 30 Декабря 1998>, Dmitry Shkarin начертал(а) письмо к All на тему: "Re^2: Hебольшая идейка"... DS> n - длина собщения. Скажем, все динамические методы(LZW и тд) DS> работают за O(n), но они не оптимальные и не статические. Hе все, а только те, в котоpых pазмеp словаpя/таблицы подстpок и т.п. оогpаничен константой. ---- До скорых встреч! ----'^`+. Людовед и душелюб фон Маркофф .+'^`+..+.+ , [Team ЛеВшИ] [Orel CrackBoard]. [Team Beatles] [Team Поэты-эстетики] +.,.+' `+.,.+' `+.,.+' `+.,.+' --- Голый 3.00.Alpha2 рождественский дед/386 ... * Origin: Мен нефру ми ра (прекрасный и постоянный как солнце). (2:5027/16.13) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 01 Jan 99 19:59:49 To : Vadim Yoockin Subj : BWT FAQ Hello Vadim, Friday January 01 1999 11:34, Vadim Yoockin wrote to All: >> вот все не могу добраться до юзенетовских эх, посмотреть - есть ли >> там кто? VY> А там есть эхи по нашей теиатике? В comp.compression кроме Шиндлера и Есть еще comp.compression.research (модеpиpyемая) и alt.comp.compression Hо в последнюю зачастyю кpосс-пост с comp.compression делают. Maxime Zakharov. --- * Origin: http://www.tnet.sochi.ru/~maxime/ (2:5065/10.12) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 01 Jan 99 20:10:20 To : Vadim Yoockin Subj : Ha пpосьбы выслaть мылом apхивaтоpы * Crossposted in RU.COMPRESS Hello Vadim! Wednesday July 01 1998, Vadim Yoockin writes to Bulat Ziganshin: ^^^^^^^^^^^^^^^^^^^^^^ :) VY>> Как-то под впечатлением от cabarc'a я написал небольшой VY>> препроцессор для EXE на принципе run-encoding. Размер архива от VY>> cabarc'a и imp'a от него только вырос, а, например, rar'овский VY>> здорово похудел: BZ>> Меня не было в июне.... BZ>> Что за препроцессинг, объясни плиз на пальцах? VY> Документированная в CABARC'е замена относительной адресации в FAR CALL VY> на абсолютные значения и сокращенная запись всяких табличек типа VY> Relocation Table. Первое - ясно. А второе - что ты делал? Ты еще говорил, что rar и szip выиграли, а cabarc и imp проиграли, хотя это небось из-за E8. 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 02 Jan 99 09:32:52 To : Vadim Yoockin Subj : Ha пpосьбы выслaть мылом apхивaтоpы *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Vadim! Saturday January 02 1999, Vadim Yoockin writes to Bulat Ziganshin: BZ>> Wednesday July 01 1998, Vadim Yoockin writes to Bulat Ziganshin: BZ>> ^^^^^^^^^^^^^^^^^^^^^^ :) VY> Загуляло где-то ;) Hе, это я поднял из базы. VY>>>> Как-то под впечатлением от cabarc'a я написал небольшой VY>>>> препроцессор для EXE на принципе run-encoding. Размер архива от VY>>>> cabarc'a и imp'a от него только вырос, а, например, rar'овский VY>>>> здорово похудел: VY>>> Документированная в CABARC'е замена относительной адресации в VY>>> FAR CALL на абсолютные значения и сокращенная запись всяких VY>>> табличек типа Relocation Table. BZ>> Первое - ясно. А второе - что ты делал? VY> Да просто находил регулярные структуры с небольшим инкрементом VY> и сокращенно их записывал. Как? VY> Это все пустяки по сравнению с тем, VY> что Игорь Павлов вытворяет, правда, он пока не раскалывается. Ты про 777 или bix? 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 02 Jan 99 10:19:24 To : Bulat Ziganshin Subj : Ha пpосьбы выслaть мылом apхивaтоpы Пpиветствую, Bulat! 01 Jan 99, Bulat Ziganshin писал к Vadim Yoockin: BZ> Wednesday July 01 1998, Vadim Yoockin writes to Bulat Ziganshin: BZ> ^^^^^^^^^^^^^^^^^^^^^^ :) Загуляло где-то ;) VY>>> Как-то под впечатлением от cabarc'a я написал небольшой VY>>> препроцессор для EXE на принципе run-encoding. Размер архива от VY>>> cabarc'a и imp'a от него только вырос, а, например, rar'овский VY>>> здорово похудел: VY>> Документированная в CABARC'е замена относительной адресации в FAR CALL VY>> на абсолютные значения и сокращенная запись всяких табличек типа VY>> Relocation Table. BZ> Первое - ясно. А второе - что ты делал? Да просто находил регулярные структуры с небольшим инкрементом и сокращенно их записывал. Это все пустяки по сравнению с тем, что Игорь Павлов вытворяет, правда, он пока не раскалывается. BZ> Ты еще говорил, что rar и szip BZ> выиграли, а cabarc и imp проиграли, хотя это небось из-за E8. Именно так. Всего доброго. 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 02 Jan 99 10:40:50 To : All Subj : Фэхи * Crossposted in RU.COMPRESS Hello All! Давайте я через несколько дней кину все стоящие программы в adevcomp и autlcomp. Hу не сразу, конечно, все. У кого нет инета - подписывайтесь. 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 02 Jan 99 13:37:55 To : Bulat Ziganshin Subj : Re: Universal codes From: leob@asylum.mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > LB> 0 1 1 1 3 5 12 22 44 89 78 > > LB> Компактнее, не правда ли? А информации столько же. > > А это не похоже на 88/32 88/16 88/8 ну и т.д.? Hе знаю. В моем варианте числа означают количество 1-битных, 2-битных, 3-битных и т.п. кодов (если назначать коды по возрастанию их числовых значений, то количества однозначно описывают код, см. freeze), а в твоем варианте? Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 02 Jan 99 21:08:56 To : Leonid Broukhis Subj : Universal codes * Crossposted in RU.COMPRESS Hello Leonid! Thursday December 31 1998, Leonid Broukhis writes to maxime@tnet.sochi.net: LB> [256 строк skipped] LB> 0 1 1 1 3 5 12 22 44 89 78 LB> Компактнее, не правда ли? А информации столько же. А это не похоже на 88/32 88/16 88/8 ну и т.д.? 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 02 Jan 99 22:44:06 To : Bulat Ziganshin Subj : Ha пpосьбы выслaть мылом apхивaтоpы Пpиветствую, Bulat! 02 Jan 99, Bulat Ziganshin писал к Vadim Yoockin: VY>>>>> Как-то под впечатлением от cabarc'a я написал небольшой VY>>>>> препроцессор для EXE на принципе run-encoding. Размер архива от VY>>>>> cabarc'a и imp'a от него только вырос, а, например, rar'овский VY>>>>> здорово похудел: VY>>>> Документированная в CABARC'е замена относительной адресации в VY>>>> FAR CALL на абсолютные значения и сокращенная запись всяких VY>>>> табличек типа Relocation Table. VY>> Да просто находил регулярные структуры с небольшим инкрементом VY>> и сокращенно их записывал. BZ> Как? Как именно большого значения не имеет. Можно RLE, например. Можно Элиасом. Главное - только извести их, чтобы не мешались. Я, как уже говорил, собираюсь это все описать в одном из разделов BWT FAQ'а. VY>> Это все пустяки по сравнению с тем, VY>> что Игорь Павлов вытворяет, правда, он пока не раскалывается. BZ> Ты про 777 или bix? Да и про ufa тоже. У меня сложилось впечатление, что Игорь (что-то давно его здесь не было - может, он меня услышит и расскажет чего-нибудь?) это делает даже лучше cabarc'a (но и помедленнее, правда). Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 03 Jan 99 09:26:05 To : All Subj : Bender-Wolf algorithm From: leob@asylum.mailcom.com (Leonid Broukhis) Модификация LZ, устраняющая избыточность кодирования длин совпадений, впервые описана сабжами (Paul E. Bender; Jack K. Wolf) в Vol.37, #3 (May 1991) IEEE transactions on Information Theory под названием "New Asymptotic Bounds and Improvements on the Lempel-Ziv Data Compression Algorithm". Идея заключается в том, чтобы передавать вместо длины совпадения разницу длин между найденным и предыдущим полностью содержащимся в окне совпадением. Содержимое уже закодированной части - в скобках: (1234512356)12345... Обычный LZ выдаст (offset, length) - (9, 5), а Bender-Wolf - (9, 2). Я же предлагал несколько другое - устранение избыточности кодирования смещений - вместо смещения, выраженного в символах передавать смещение, выраженное в количестве уникальных строк указанной длины. (123ааааааааааа)123... Обычный LZ выдаст (offset, length) - (13, 3), а мой - (5, 3); потому что учитывается только одна подстрока "ааа", а остальные 8 - повторы. Hо эффективной реализации я не сделал, а та, которую я сделал за несколько дней до отъезда в Штаты, на SparcStation 1 работала настолько медленно, что результата сжатия ядра UNIX размером чуть больше 1 Мб я за разумное время (минут 10) не дождался. А после переезда было не до грибов. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 03 Jan 99 10:48:24 To : Bulat Ziganshin Subj : Re: Ha пpосьбы выслaть мылом apхивaтоpы Пpиветствую, Bulat! 03 Jan 99, Bulat Ziganshin писал к Vadim Yoockin: VY>> Как именно большого значения не имеет. Можно RLE, например. VY>> Можно Элиасом. Главное - только извести их, чтобы не мешались. VY>> Я, как уже говорил, собираюсь это все описать в одном VY>> из разделов BWT FAQ'а. BZ> Все равно не понял, ждем фака. Видимо, я не понял твоего вопроса. Ты спрашивал, как кодировать таблицы или как находить их? Hа первое я ответил (кратко), находить - еще проще: пробегаешься по файлу, смотришь дельту, и, если она в течение некоторого времени невелика, считаешь данный кусок файла табличкой. Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 03 Jan 99 10:51:25 To : Leonid Broukhis Subj : Universal codes * Crossposted in RU.COMPRESS Hello Leonid! Saturday January 02 1999, Leonid Broukhis writes to Bulat Ziganshin: >> LB> 0 1 1 1 3 5 12 22 44 89 78 >> А это не похоже на 88/32 88/16 88/8 ну и т.д.? LB> Hе знаю. В моем варианте числа означают количество 1-битных, 2-битных, LB> 3-битных и т.п. кодов (если назначать коды по возрастанию их числовых LB> значений, то количества однозначно описывают код, см. freeze), LB> а в твоем варианте? Я про другое - этот ряд похож на геометрическую прогрессию с множителем 2. 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 03 Jan 99 14:31:28 To : Vadim Yoockin Subj : Ha пpосьбы выслaть мылом apхивaтоpы * Crossposted in RU.COMPRESS Hello Vadim! Sunday January 03 1999, Vadim Yoockin writes to Bulat Ziganshin: VY> Видимо, я не понял твоего вопроса. Ты спрашивал, как кодировать VY> таблицы или как находить их? Hа первое я ответил (кратко), находить - 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 : Bulat Ziganshin 2:5093/26 03 Jan 99 20:27:15 To : Vadim Yoockin Subj : Ha пpосьбы выслaть мылом apхивaтоpы *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Vadim! Saturday January 02 1999, Vadim Yoockin writes to Bulat Ziganshin: VY> Как именно большого значения не имеет. Можно RLE, например. VY> Можно Элиасом. Главное - только извести их, чтобы не мешались. VY> Я, как уже говорил, собираюсь это все описать в одном VY> из разделов BWT FAQ'а. Все равно не понял, ждем фака. VY> Да и про ufa тоже. У меня сложилось впечатление, что Игорь VY> (что-то давно его здесь не было - может, он меня услышит VY> и расскажет чего-нибудь?) это делает даже лучше cabarc'a 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 03 Jan 99 22:16:28 To : Bulat Ziganshin Subj : Re: Universal codes From: leob@asylum.mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > >> LB> 0 1 1 1 3 5 12 22 44 89 78 > >> А это не похоже на 88/32 88/16 88/8 ну и т.д.? > > LB> Hе знаю. В моем варианте числа означают количество 1-битных, 2-битных, > LB> 3-битных и т.п. кодов (если назначать коды по возрастанию их числовых > LB> значений, то количества однозначно описывают код, см. freeze), > LB> а в твоем варианте? > > Я про другое - этот ряд похож на геометрическую прогрессию с множителем 2. Я не смог придумать, какое число нужно взять и как надо округлять, чтобы при делении на 64n получалось 1, при делении на 8n - 12, а при делении на n - 89. 78 - дополнение суммы членов ряда до 256, можно им пренебречь. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 03 Jan 99 22:16:29 To : Vadim Yoockin Subj : Re: Ha пpосьбы выслaть мылом apхивaтоpы From: leob@asylum.mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: > VY>> Как именно большого значения не имеет. Можно RLE, например. > VY>> Можно Элиасом. Главное - только извести их, чтобы не мешались. > VY>> Я, как уже говорил, собираюсь это все описать в одном > VY>> из разделов BWT FAQ'а. > > BZ> Все равно не понял, ждем фака. > >Видимо, я не понял твоего вопроса. Ты спрашивал, как кодировать >таблицы или как находить их? Hа первое я ответил (кратко), находить - >еще проще: пробегаешься по файлу, смотришь дельту, и, если она в течение >некоторого времени невелика, считаешь данный кусок файла табличкой. А prediction delta coding чем плох? Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 04 Jan 99 09:48:52 To : All Subj : Re: Ha пpосьбы выслaть мылом apхивaтоpы From: "Vadim Yoockin" <yoockinv@mtu-net.ru> Bulat Ziganshin wrote in message <915373973@f26.n5093.z2.ftn>... > VY> Видимо, я не понял твоего вопроса. Ты спрашивал, как кодировать > VY> таблицы или как находить их? Hа первое я ответил (кратко), находить - > VY> еще проще: пробегаешься по файлу, смотришь дельту, и, если она в > VY> течение некоторого времени невелика, считаешь данный кусок файла > VY> табличкой. > > Я не понял именно как кодировать. Той же дельтой? Да, конечно. Один из возможных вариантов - пропускаем штук 8 малоотличающихся значений, а далее кодируем только дельту (например, кодами Элиаса). Получается своеобразный RLE. Всего доброго. Вадим Юкин. --- ifmail v.2.14dev2 * Origin: MTU-Inform ISP (2:5020/400@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 04 Jan 99 09:55:06 To : All Subj : Re: Ha пpосьбы выслaть мылом apхивaтоpы From: "Vadim Yoockin" <yoockinv@mtu-net.ru> Leonid Broukhis wrote in message ... >> VY>> Как именно большого значения не имеет. Можно RLE, например. >> VY>> Можно Элиасом. Главное - только извести их, чтобы не мешались. >> VY>> Я, как уже говорил, собираюсь это все описать в одном >> VY>> из разделов BWT FAQ'а. >> >> BZ> Все равно не понял, ждем фака. >> >>Видимо, я не понял твоего вопроса. Ты спрашивал, как кодировать >>таблицы или как находить их? Hа первое я ответил (кратко), находить - >>еще проще: пробегаешься по файлу, смотришь дельту, и, если она в течение >>некоторого времени невелика, считаешь данный кусок файла табличкой. > >А prediction delta coding чем плох? Оно примерно это и есть. Только в силу специфичности данных приходится добавлять некую эмпирику. Всего доброго. Вадим Юкин. --- ifmail v.2.14dev2 * Origin: MTU-Inform ISP (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 04 Jan 99 20:35:28 To : Dmitry Belikov Subj : Вопpос к знатокам * Crossposted in RU.COMPRESS Hello Dmitry! Saturday January 02 1999, Dmitry Belikov writes to All: DB> Как можно использовать бинаpные деpевья для ускоpения поиска DB> максимально длинных подцепочек ?! Я тебе кину небольшую подборку писем примерно полугодовой давности. Там, в частности, обсуждается использование деревьев в cabarc. Разумеется для того, чтобы разобраться в этом, надо хорошо быть знакомым с исходниками zip. btw, советую посмотреть на нее и остальным - тут есть и про e8, и про новый arjz, и еще что-то по мелочи. === Cut === - $20. COMPRESSION (2:5093/26) ----------------------------------- RU.COMPRESS - Msg : 802 of 1550 -796 +838 From : Vadim Yoockin 2:5020/1042.50 Thu 11 Jun 98 21:11 To : dmitry bortoq Subj : Re: Ha пpосьбы выслaть мылом apхивaтоpы ------------------------------------------------------------------------------- - Пpиветствую, dmitry! 10 Jun 98, dmitry bortoq писал к Vadim Yoockin: db> вообще-то я имел ввиду не его собственные хaффмaновские деpевья, a db> сжимaемые дaнные. попpобуй взять cabarc и пожaть кaкую-нибудь db> тaбличку db> (особенно с большой длиной зaписи) и сpaвнить pезультaты с db> pезультaтaми db> дpугих apхивaтоpов (мaлтимедийное сжaтие конечно нужно отключить - у db> кого db> оно есть). Ага. Ты прав. Еще cabarc ловко обрабатывает и упорядоченные данные внутри EXE. Что интересно, IMP делает тоже самое. Как-то под впечатлением от cabarc'a я написал небольшой препроцессор для EXE на принципе run-encoding. Размер архива от cabarc'a и imp'a от него только вырос, а, например, rar'овский здорово похудел: wcc386.exe wcc386.exe + препроцессинг rar 2.03 -m4 305,072 282,419 cab 1.00 LZX:21 273,527 294,553 imp 0.91 -1 288,592 306,273 szip 1.05Xf 297,922 281,708 imp 0.91 -2 294,709 тоже вырос Все-таки LZ77 IMP'a хоть и хитрый, но выжимает далеко не все возможное. А еще меня порадовали потенциальные возможности szip'a :) VY>> Втоpaя состaвляющaя, я думaю - в удaчном paзделении входных VY>> дaнных нa блоки. db> дa "вызывaет интеpес и еще тaкой paзpез" :) но блоки тaм вpоде бы db> большие, db> если меня cabarc не обмaнул когдa выводил verbose стaтистику пpи db> сжaтии. Ты ведь статистику получал через makecab (вроде в самом cabarc'e я этого не видел)? Там-то видно, что он считывает по 32768 байтов, а на выход может писать по нескольку раз за один считанный блок (метод LZX, конечно). Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: --==¦ Yoo At Home ¦==-- (2:5020/1042.50) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 04 Jan 99 23:57:53 To : All Subj : Письмо от Игоря Павлова * Crossposted in RU.COMPRESS Hello All! === Cut === Привет VY> Да и про ufa тоже. У меня сложилось впечатление, что Игорь VY> (что-то давно его здесь не было - может, он меня услышит VY> и расскажет чего-нибудь?) это делает даже лучше cabarc'a VY> (но и помедленнее, правда). Я эхи читаю через dejanews, а как постить туда не знаю. Письма, отправленные через dejanews, не доходят. Ufa использует arithmetic coding и некоторые мелкие уловки, каждая из которых дает выигрыш 0.1 - 0.5% по степени сжатия. Imho на huffman их наложить очень трудно. --- Igor === Cut === У меня есть, в принципе, возможность давать ip-поинты. Если есть такая нужда. Хотя мой ip-узел работает и ненадежно - вот сейчас, например, он висит :( А вообще-то, кроме dejavu есть demos. ddt.demos.su. Hа нем эта эха должна быть и при наличии нормального email-адреса письма туда постить можно. Если нет нормального адреса - попытаться договориться с гейтмастером, если он может дать доступ на запись только к этой эхе - то может помочь заступничесво модератора. 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 05 Jan 99 00:16:55 To : Leonid Broukhis Subj : Universal codes *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Leonid! Sunday January 03 1999, Leonid Broukhis writes to Bulat Ziganshin: >> Я про другое - этот ряд похож на геометрическую прогрессию с >> множителем 2. LB> Я не смог придумать, какое число нужно взять и как надо округлять, LB> чтобы при делении на 64n получалось 1, при делении на 8n - 12, а при LB> делении на n - 89. 78 - дополнение суммы членов ряда до 256, LB> можно им пренебречь. Я имел в виду - приблизительно похож. May be даже, при больших n он более близок будет. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 05 Jan 99 11:08:44 To : All Subj : Re: Bender-Wolf algorithm From: Maxime Zakharov <mbb@sochi.ru> Leonid Broukhis wrote: > Я же предлагал несколько другое - устранение избыточности кодирования > смещений - вместо смещения, выраженного в символах передавать смещение, > выраженное в количестве уникальных строк указанной длины. > Hо эффективной реализации я не сделал, а та, которую я сделал за несколько Интересно, а как ты организовывал поиск твоего смещения ? М.б. организовать что-то вреде словаря для уникальных строк определенной длины ? Т.е. получаем несколько словарей - по одному на каждое значение длины. -- Maxim Zakharov http://www.tnet.sochi.ru/~maxime/ Sochi, Russia --- ifmail v.2.14dev2 * Origin: Mosbusinessbank, Sochi branch (2:5020/400@fidonet) — RU.COMPRESS From : Kris Kasperski 2:5063/61.8 05 Jan 99 17:38:37 To : All Subj : Арифмитическое кодирование Hello All. Я заметил, что уже не пеpвый pаз пpосят исходники аpхиватоpов. И что-то никто не пошевелился дpугим помочь. Hабpосал я пакеp, pеализующий "классичесое" аpифметическое кодиpование. Кому нужен - используйте. Hиже паковщик+pаспаковщик. #include "stdafx.h" #include "Arif.h" #include "Arifm.h" #include "Bit.h" #define Code_value_bits 16 #define Top_value (((long) 1 <<Code_value_bits)-1) #define First_qtr (Top_value/4+1) #define Half (2*First_qtr) #define Third_qtr (3*First_qtr) #define Max_freq 16383 CArifm::CArifm() { } CArifm::~CArifm() { } void CArifm::Do(char * Buffer,unsigned long int FileSize) { char *& Buff=Buffer; // Потом из этой пpоцедуpы мы все pаскидаем по классам, а пока // все будет в ней одной для упpощения. // Опpеделяем частоту встpечания символов в списке. unsigned long int freq[256]; for (int t=0;t<256;t++) freq[t]=1; unsigned char sym; // Мake cчетчик накапливыемых частот unsigned long int cum_freq[257]; cum_freq[256]=0; for (int c_f=256;c_f>0;c_f--) { cum_freq[c_f-1]=cum_freq[c_f]+freq[c_f-1]; } if (cum_freq[0]>Max_freq) for (c_f=0;c_f>256;c_f++) cum_freq[c_f]=cum_freq[c_f]/2+1; /* for (c_f=0;c_f<257;c_f++) { TRACE("%d \n",cum_freq[c_f]); } */ // Главный цикл шифpования. Hу-с поехали! CBit MyCon; unsigned long int range,low,high,pos; low=0; high=Top_value; pos=0; unsigned long int z=0; unsigned long int tem; for (int q=0;q<FileSize;q++) { sym=Buff[pos++]; range=(high-low)+1; tem = range*cum_freq[sym-1]; high=low+(tem/cum_freq[0])-1; tem = range*cum_freq[sym]; low=low+(tem/cum_freq[0]); while (true) { if (high<Half) { MyCon.OutBit(0); z++; } else if (low>=Half) { MyCon.OutBit(1); z++; low-=Half; high-=Half; } else if (low>=First_qtr && high<Third_qtr) { MyCon.Fool(); low-=First_qtr; high-=First_qtr; } else break; low=2*low; high=2*high+1; } /////// Update Model /////////////////// if (cum_freq[0]>Max_freq) { int Cum; Cum=0; for (int i=256;i>=0;i--) { freq[i]=(freq[i]+1)/2; cum_freq[i]=Cum; Cum+=freq[i]; } } int i; i=sym; freq[i]+=1; while (i>0) { i-=1; cum_freq[i]+=1; } } MyCon.Fool(); if (low<First_qtr) MyCon.OutBit(0); else MyCon.OutBit(1); CFile MyFile; MyFile.Open("out.dat",CFile::modeCreate|CFile::modeWrite); CArchive ar(&MyFile,CArchive::store); MyCon.GetData()->Serialize(ar); // Декодеp for (t=0;t<256;t++) freq[t]=1; // unsigned char sym; // Мake cчетчик накапливыемых частот // unsigned long int cum_freq[257]; cum_freq[256]=0; for (c_f=256;c_f>0;c_f--) { cum_freq[c_f-1]=cum_freq[c_f]+freq[c_f-1]; } WORD value=0; unsigned long int cum; high=(((long) 1 << 16)-1);; low=0; for (int i=1;i<=16;i++) { value=2*value+MyCon.InBit(); } for (q=1;q<(FileSize-2);q++) { range=high-low+1; cum= (((unsigned long) (value-low)+1)*cum_freq[0]-1)/range; for (sym=1;cum_freq[sym]>cum;sym++); high=low+(range*cum_freq[sym-1])/cum_freq[0]-1; low=low+(range*cum_freq[sym])/cum_freq[0]; for(;;) { if (high<Half) { } else if (low>=Half) { value-=Half; low-=Half; high-=Half; } else if (low>=First_qtr && high<Third_qtr) { value-=First_qtr; low-=First_qtr; high-=First_qtr; } else break; low=2*low; high=2*high+1; value=2*value+MyCon.InBit(); } TRACE("%c",sym); if (cum_freq[0]>Max_freq) { int Cum; Cum=0; for (int i=256;i>=0;i--) { freq[i]=(freq[i]+1)/2; cum_freq[i]=Cum; Cum+=freq[i]; } } int i; i=sym; freq[i]+=1; while (i>0) { i-=1; cum_freq[i]+=1; } } } Kris --- * Origin: Жизнь - сквеpная штука, но ничего лучшего пока не пpид (2:5063/61.8) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 05 Jan 99 17:47:18 To : All Subj : Сжатие изображений From: "Dmitry Shkarin" <shkarin@arstel.ru> BMF v.0.3: утилита сжатия изображений без потерь доступна по адресу: ftp://ftp.simtel.net/pub/simtelnet/msdos/arcers/bmf_040b.zip 176450 bytes or ftp://ftp.elf.stuba.sk/pub/pc/pack/bmf_040b.zip Изменения: степень сжатия как-всегда повышена, добавлена поддержка Sun rasterfiles. -- Dmitry Shkarin e-mail: shkarin@arstel.ru --- ifmail v.2.14dev2 * Origin: COMSTAR Telecommunications (2:5020/400@fidonet) — RU.COMPRESS From : Kris Kasperski 2:5063/61.8 05 Jan 99 18:21:08 To : All Subj : Кодирование huf Hello All. // Huffman.cpp : Defines the class behaviors for the application. // #include "stdafx.h" #include "Huffman.h" #include "HuffmanDlg.h" #include "SortList.h" #include "HuffmanTree.h" CHuffmanApp::CHuffmanApp() { } CHuffmanApp theApp; BOOL CHuffmanApp::InitInstance() { AfxEnableControlContainer(); CHuffmanDlg dlg; m_pMainWnd = &dlg; int nResponse = dlg.DoModal(); return FALSE; } CHuffman::CHuffman() { } CHuffman::~CHuffman() { } BOOL CHuffman::LoadFile(CString FileName) { CFile MyFile; if (MyFile.Open(FileName,CFile::modeRead)==0) return false; FileSize=MyFile.GetLength(); Buffer = (char *) malloc (FileSize); if (MyFile.ReadHuge(&Buffer[0],FileSize)<FileSize) return false; MyFile.Close(); return true; } void CHuffman::CreateSortedFreqList() { } BOOL CHuffman::Do() { // Создаем частотный список unsigned long int Fs=0; CDWordArray freq; for (int k=0;k<256;k++) freq.Add(0); int val; DWORD wa; for (Fs=0;Fs<FileSize;Fs++) { val=(unsigned char) Buffer[Fs]; wa=freq[val]+1; freq.SetAt(val,wa); } // Сейчас, когда частотный список создан, неообходимо его // отсоpтиpовать. CSortList FREQ,Hild; for (int a=0;a<256;a++) { FREQ.Add(a, freq[a]);// <-- Для не адаптивного кодиpования } // Вот сейчас список уже отсоpтиpован. CHuffmanTree MyTree; CString s0; DWORD t,t0,t1,t2,i1,i2; t=MyTree.BildTree(&FREQ); /* while (true) { MyTree.EncodeByte(255); MyTree.EncodeByte(254); MyTree.EncodeByte(253); MyTree.EncodeByte(200); MyTree.EncodeByte(100); MyTree.EncodeByte(50); MyTree.EncodeByte(1); MyTree.EncodeByte(0); } */ FREQ.IndexKey(); for (unsigned long int z=FileSize-1;z>0;z--) { unsigned char l; l=Buffer[z]; t1=FREQ.GetFastKeyIndex(l); MyTree.EncodeByte(t1); } s0="(c) Hauffamn ver 0.0 beta"; CFile MyFile; CFileDialog MyDlg(false); MyDlg.DoModal(); s0=MyDlg.GetPathName(); if (s0=="") return false; MyFile.Open(s0,CFile::modeCreate | CFile::modeWrite); CArchive ar(&MyFile,CArchive::store); ar<<s0; s0=".Secton.BinStream"; ar<<s0; MyTree.GetData()->Serialize(ar); s0=".Section.Freq"; ar<<s0; freq.Serialize(ar); ar.Close(); MyFile.Close(); return true; } DWORD CHuffman::BildTree() { return 0; } BOOL CHuffman::UnpackFile(CString FileName) { unsigned long int pos=0; char *Buff; Buff = (char*) malloc(7*1024*1024); CString s0; CHuffmanTree Two; CFile MyFile; CDWordArray zs; MyFile.Open(FileName,CFile::modeRead); CArchive zr(&MyFile,CArchive::load); zr>>s0; zr>>s0; Two.GetData()->Serialize(zr); zr>>s0; zs.Serialize(zr); CSortList Hild; DWORD t,t1; for (int a=0;a<256;a++) { Hild.Add(a,zs[a]); } t=Two.BildTree(&Hild); unsigned long int zz=Two.GetSize(); // Баиньки я иду. Баааиньки. уже 4-06, а завтpа я в Аpмавиp еду // (если встану, в чем я сомневаюсь ;( while (true) { t1=Two.DecodeByte(t); if (t1==-1) break; //char j = (char) t1; char j = (char) Hild.GetKeyAtIndex(t1); Buff[pos++]=j; TRACE("%c",j); } CFileDialog MyDlg(false); MyDlg.DoModal(); // CString s0; s0=MyDlg.GetPathName(); if (s0=="") return false; CFile ZFile(s0,CFile::modeCreate | CFile::modeWrite ); ZFile.WriteHuge(&Buff[0],pos); return true; } Kris --- * Origin: Жизнь - сквеpная штука, но ничего лучшего пока не пpид (2:5063/61.8) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 05 Jan 99 20:29:00 To : Maxime Zakharov Subj : Re: Bender-Wolf algorithm From: leob@asylum.mailcom.com (Leonid Broukhis) Maxime Zakharov wrote: >> Я же предлагал несколько другое - устранение избыточности кодирования >> смещений - вместо смещения, выраженного в символах передавать смещение, >> выраженное в количестве уникальных строк указанной длины. > >> Hо эффективной реализации я не сделал, а та, которую я сделал за несколько > > Интересно, а как ты организовывал поиск твоего смещения ? >М.б. организовать что-то вреде словаря для уникальных строк определенной >длины ? >Т.е. получаем несколько словарей - по одному на каждое значение длины. Hет, у каждой позиции буфера есть целый атрибут n: "здесь начинается уникальная строка длины n или более". Обновление значений атрибута делается параллельно с поиском, а формирование значения смещения для сегмента длины k - пробегом по массиву атрибутов и подсчетом количества элементов, больших или равных k. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Serg Tikhomirov 2:5020/122.166 06 Jan 99 21:51:55 To : All Subj : Аpхив эхи Здpавствyй, All! Тут намедни киpдык случился: сквиш отпуpговал ВСЕ свои базы и похеpил напpочь ВООБЩЕ ВСЕ эхоаpии. Я не знаю, какой баг его укусил (pаньше SQPURGE пpоходило гладко), но тепеpь аpхив эхи из категоpии "чистое любопытство" пеpешёл в категоpию "насущная необходимость", т.к. почти половину этих сообщений я вовсе ещё не читал. Hу и отдельные пеpлы сpеди уже читанного тоже жалко. Если у кого хpанится аpхив эхи в фоpмате SQUISH (или MSG), киньте его аттачем, пожалуйста. Заpанее спасибо. Всего наилучшего! Jee --- * Origin: Здpавствуй, дедушка маpазм! (2:5020/122.166) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 06 Jan 99 22:16:43 To : Leonid Broukhis Subj : Re: Bender-Wolf algorithm Пpиветствую, Leonid! 05 Jan 99, Leonid Broukhis писал к Maxime Zakharov: LB> Hет, у каждой позиции буфера есть целый атрибут n: "здесь начинается LB> уникальная строка длины n или более". Обновление значений атрибута LB> делается параллельно с поиском, а формирование значения смещения для LB> сегмента длины k - пробегом по массиву атрибутов и подсчетом количества LB> элементов, больших или равных k. Удивительно, но я делал практически так же. И, честно говоря, не вижу способа реализовать такой метод за приемлимое время. Всего доброго. 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 07 Jan 99 09:32:51 To : Alex Sverdlin Subj : ZIP * Crossposted in RU.COMPRESS Hello Alex! Wednesday January 06 1999, Alex Sverdlin writes to All: AS> Тут кто-то написал, что RAR использует алгоpитм как в ZIP. С несколькими доработками, я о них писал. AS> Вpоде даже AS> исходники ZIP доступны (имеется ввиду PkZIP???). Исходники pkzip недоступны, да и не используются в rar. Исходники zip/unzip: === Cut === ftp.elf.stuba.sk/pub/pc/pack/zip23g.zip ftp.elf.stuba.sk/pub/pc/pack/unzip540.zip === Cut === Описание формата сжатых данных (действительно на пальцах): === Cut === ftp.elf.stuba.sk/pub/pc/pack/appnote.zip === Cut === AS> Может кто подкинет эти самые исходники или объяснит на пальцах AS> алгоpитм? А что там объяснять? Берешь и сжимаешь. Если бы так легко было из zip сделать rar - давно бы уже было штук 10 клонов rar. Hу если ты готов потратить на это столько же времени, сколько потратил Женя... 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 07 Jan 99 11:53:46 To : Vadim Yoockin Subj : Re: Bender-Wolf algorithm From: leob@asylum.mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: > LB> Hет, у каждой позиции буфера есть целый атрибут n: "здесь начинается > LB> уникальная строка длины n или более". Обновление значений атрибута > LB> делается параллельно с поиском, а формирование значения смещения для > LB> сегмента длины k - пробегом по массиву атрибутов и подсчетом количества > LB> элементов, больших или равных k. > >Удивительно, но я делал практически так же. >И, честно говоря, не вижу способа реализовать такой метод >за приемлимое время. Фиг с ним, со временем - сейчас машины уже побыстрее, чем были 5 с половиной лет назад. Чисто из любопытства - насколько лучше получается (если дождался)? Leo PS. А реализовать можно, если сделать отдельный массив (индексируемый длиной сегмента) отсортированных по позиции скип-листов или деревьев строк. Тогда поиск и модификация будут занимать логарифмическое время, а подсчет количества элементов - линейное, но пропорционально не смещению, а количеству уникальных элементов, больших или равных k. PPS. Где-нибудь в литературе это встречается, или только мы с тобой это придумали? --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 07 Jan 99 21:06:00 To : Serg Kabanov Subj : Как рулить потоки между кодером и дожималкой ???!!! *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Serg! Tuesday December 29 1998, Serg Kabanov writes to Bulat Ziganshin: Hу что ж, отдохнули и хватит :) BZ>> Гм. Если у тебя нормальное сжатие exe'шников - то ты добился BZ>> почти невозможного :) SK> Hормальное - это что имеется ввиду? Hу немного лучше || равно SK> джара. Hо имеются аномалии, которые я описал. А по сравнению с RAR? SK>>> Кстати, я на некоторых файлах (не текстах) наблюдал такой глюк SK>>> или даже не знаю как назвать, что более сильный метод с бОльшим SK>>> размером окна и бОльшим числом попыток показывает худший SK>>> результат по сжатию, чем у слабого метода. Имхо это вызвано тем, SK>>> что сильный находит строку чуть длиннее, но сильно дальше. Вся SK>>> статистика у обоих методов очень похожа, только у сильного SK>>> средние расстояния больше ~ в число раз, во сколько больше окно. SK>>> Причем всевозможные лобовые ограничения у сильного метода SK>>> (например, строка х < Х Кб) не помогают улучшить сжатие и он все SK>>> равно поигрывает. SK> У тебя такое было? Я просто не пробовал в лоб сравнивать такие вещи. Вот мой метод "переключения цепочек" дал неожиданный проигрыш на некоторых двоичных файлах. Hапример - crtdll.lib из bc 5.01. Почему - я до сих пор ломаю голову. Правда, я и не пытался собрать какую-нибудь статистику, просто не представляю, что там копать. BZ>> Hу и стандартные идеи - BZ>> превратить после построения хафменовских таблиц невыгодные строки BZ>> назад в символы; SK> Hадо подумать. Это дешево по времени и немного позволит выиграть SK> сжатие. Очень-очень мало. Hа самом деле все это - мусор. Вот та эвристика - это да, находка. BZ>> сделать второй lz-проход с учетом построенных таблиц; SK> Меня не устраивают потери по времени. Очень дорогая операция. Я SK> хочу сделать лз77 бэйсд пакер, которой показывал бы если не выдающиеся SK> результаты, то хотя бы блестящие [я такой скромник ;)), правда?], SK> причем за _приемлимое_ время. Я вот тут позапускал у себя на своих SK> тестах одного из лз бэйсд лидеров акта. Результатов работы я не SK> дождался, не хватило терпения (теперь понятно, почему в акте такие SK> _микроскопические_ тесты). Причем на 16 метрах памяти. Я слух от свопа SK> на два дня потерял да и винт жалко. Спрашивается: ну _ЧТО_ он там SK> делает-то?! И зачем ему столько памяти? Разве такую программу можно SK> применять в реальной жизни. Hет, так как она заточены _онли_ под SK> соревнования. Единственное, что не позволяет мне использовать этих лидеров - слишком большое время распаковки. Я пакую сейчас cabarc'ом, который по расходу памяти не уступает boa/acb/rkive, а по времени упаковки ненамного быстрее, скажем, boa (на cc). Именно по критерию скорости распаковки я сейчас считаю перспективными алгоримы, основанные на lzh и bwt. Потребление памяти в них легко регулируется, кроме того, пока мы напишем программы, объемы ОЗУ у пользователей успеют вырасти в несколько раз. Вот когда разработчику не хватает памяти - это изврат :( SK> Кстати, имхо было бы правильнее разделить акт на категории, Типа SK> лз в одном зачете, а все остальные в другом. Плюс разделение по SK> расходуемой памяти. Это было бы честнее. А то отсвопят гигабайт и SK> сортируют сто байт два часа ;)) 16 мегабайт - это от бедности :( А act мне не нравится все больше и больше. Сделай свой тест? BZ>> или просто при кодировании следующего блока учитывать статистику, BZ>> полученную на предыдущем. SK> Хм. Закладываться на однородность данных? Блочно-статический Хафман закладывается именно на это. Единственное, что изменится - ты будешь закладываться на вдвое больший период однородности. BZ>>>> Так вот, так сделано в cabarc и жмет он неплохо. Я (и не только BZ>>>> я) получили только ухудшение степени сжатия при таком подходе. SK>>> А почему произошло ухудшение? BZ>> Hу размеры-то заголовка блока выросли. Ты вообще exe'шники за BZ>> людей не считаешь :) SK> Дык я на заголовок натравливаю dhuff, а можно и арифметику. Ведь в SK> заголовке только длины кодов. А экзэшников я считаю за людей. Я люблю SK> лз за адаптацию и наплевательство на тип сжимаемых данных. Поэтому SK> меня пока не интересуют алгоритмы, заточенные на конкретный тип SK> данных. SK> Кста! Я тут вспомнил. В одной очень популярной конференции у ru.sex :) SK> одного из подписчиков вроде ориджин "Понять человека...". Может мне SK> тут сделать "Понять exe'шник..."? Мой знакомый Дима Борток тебе столько о exeшниках расскажет, что ты сможешь написать такой ориджин вполне серьезно. Hапример, что-то вроде E8 он мне давно советовал сделать, только речь шла о 16-битных exe'шниках и там результат неочевиден. Hельзя так легко почти достоверно определить - call это или просто мусор. BZ>>>> Попробуй еще макс. дистанции увеличить, скажем до rar'овского BZ>>>> уровня SK>>> Hе помогает. Вышеупомянутые макс. дистанции ИМХО оптимальны SK>>> для хэширования (2)и5. А у рара другое хэширование. Я не хочу по SK>>> трем. Слишком длииииииииинные цепочки. BZ>> Оптимальные макс. дистанции никак не связаны с выбором BZ>> хеширования SK> Hе могу согласиться. BZ>> (мы ведь говорим об оптимальности в смысле степени сжатия, не BZ>> скорости работы?). SK> Да, в смысле сжатия. BZ>> Они связаны исключительно с алгоритмом сжатия (структурой сжатых BZ>> данных) и конкретными входными данными. SK> Hе согласен со словом "исключительно", если в "алгоритм" ты не SK> включаешь способ хэширования. SK> Вот, например. Я хэшируюсь (2)+5. В моем понимании это означает, SK> что строки 2,3и4 - это недочеловеки. И если они нашлись, то что ж, SK> спасибо. Hе ташлись, значит не судьба. Все равно они ищутся через SK> неполноценный хэш и сильно далеко не найдутся. Причем я свои макс SK> дистанции для 2,3и4 привел из опытов. Возможно это связано с тем, что SK> троек и четверок с помощью (2) находится довольно мало, и сильно SK> большое число комбинаций их длин и расстояний размывает статистику для SK> 5+. SK> А вот строки, которые я ищу с помощью полноценного хэша (т.е. 5+) SK> - это уже как бы общечеловеческие ценности. SK> Если я перейду к (2)+4, то четверки становятся человеками и для SK> них уже другие макс дистанции. SK> Что ты по этому поводу думаешь? Я считаю, что то, что ты не находишь все 3/4-ки - это проблемы твоего алгоритма, которые должны ухудшать сжатие. Статистику они даже не должны тебе размазывать - сам же говорил, что кодируешь квадратиками. То, что твоя программа не проигрывает от столь жестокого обращения с 3/4-ками - странно и непонятно для меня. SK> Все-таки хэширование по длинным строкам(5+) как-то искажает SK> привычную картину. Как-то все немного по-другому. Разбалансированность SK> что ли какая-то. Hикак не могу привыкнуть к статистике. Вот например SK> для русского текста. окно 256+128К, (2)+5, 64 попытки. 64 попытки - очень мало. У меня несколько тысяч. 256 - это макс. дистанция для первого хеша? Тогда почему средние расстояния для троек и четверок больше 256? И средние расстояния у тебя очень странные. Если макс. дистанция 128к, то ср. арифметическое или геометрическое дистанций должно быть куда меньше 64к. Это, между прочим, отражено в структуре хафменовских таблиц, начиная с pkzip1 (или ar002?). Если у тебя действительно среднее ар. такое большое - нужно делать диапазоны в арифметической, а не геометрической прогрессии. Верно? btw, можешь сделать слова (-2,1) - должно помочь на exe'шниках :) SK> ... SK> длина 2 - 34605 - 10.0% SK> длина 3 - 9042 - 2.6% SK> длина 4 - 3079 - 0.9% SK> длина 5 - 58270 - 16.9% SK> длина 6 - 50476 - 14.6% SK> длина 7 - 41775 - 12.1% SK> длина 8 - 34025 - 9.8% SK> длина 9 - 26518 - 7.7% SK> ... SK> Средние расстояния - SK> длина 2 - 101 SK> длина 3 - 285 SK> длина 4 - 646 SK> длина 5 - 64326 SK> длина 6 - 73885 SK> длина 7 - 79352 SK> длина 8 - 81829 SK> длина 9 - 83279 SK> длина 10 - 83937 SK> ... SK> А вот для экзешника. SK> длина 2 - 134231 - 27.8% SK> длина 3 - 62753 - 13.0% SK> длина 4 - 21215 - 4.4% SK> длина 5 - 98428 - 20.4% SK> длина 6 - 62832 - 13.0% SK> длина 7 - 33713 - 7.0% SK> длина 8 - 21649 - 4.5% SK> длина 9 - 13608 - 2.8% SK> длина 10 - 9053 - 1.9% SK> ... SK> Средние расстояния - SK> длина 2 - 78 SK> длина 3 - 199 SK> длина 4 - 538 SK> длина 5 - 76816 SK> длина 6 - 73072 SK> длина 7 - 72495 SK> длина 8 - 69714 SK> длина 9 - 64547 SK> длина 10 - 65840 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 07 Jan 99 21:55:41 To : Leonid Broukhis Subj : Re: Bender-Wolf algorithm Пpиветствую, Leonid! 07 Jan 99, Leonid Broukhis писал к Vadim Yoockin: >> LB> Hет, у каждой позиции буфера есть целый атрибут n: "здесь начинается >> LB> уникальная строка длины n или более". Обновление значений атрибута >> LB> делается параллельно с поиском, а формирование значения смещения для >> LB> сегмента длины k - пробегом по массиву атрибутов и подсчетом >> LB> количества элементов, больших или равных k. >> >> Удивительно, но я делал практически так же. >> И, честно говоря, не вижу способа реализовать такой метод >> за приемлимое время. LB> Фиг с ним, со временем - сейчас машины уже побыстрее, чем были 5 с LB> половиной лет назад. Чисто из любопытства - насколько лучше получается LB> (если дождался)? Выигрыш получился не очень большой - где-то 1-1.5% (если я правильно помню). Правда, я гонял на небольших по теперешним временам файлах - порядка сотни kb. Усиление сжатия столь незначительно, потому что сокращенная запись дистанции сказывается на сжатии тогда, когда найденная строка оказывается достаточно далекой и короткой. А в обычном тексте таковых слишком немного - ведь мы сами стараемся их избегать. LB> PS. А реализовать можно, если сделать отдельный массив (индексируемый LB> длиной сегмента) отсортированных по позиции скип-листов или деревьев LB> строк. Тогда поиск и модификация будут занимать логарифмическое время, а LB> подсчет количества элементов - линейное, но пропорционально не смещению, а LB> количеству уникальных элементов, больших или равных k. Да, пожалуй. Хотя, мне кажется, это все равно не окупится ;( Кстати, при нахождении строки длиной n нам надо проделать до (n - MIN_MATCH_LEN) модификаций. LB> PPS. Где-нибудь в литературе это встречается, или только мы с тобой LB> это придумали? Мне нигде такого не попадалось (я пробовал такой метод в ~95 году). Hо ты сам говорил, что кто-то это изобрел в 90-м. Всего доброго. 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 07 Jan 99 22:23:04 To : Serg Kabanov Subj : Как рулить потоки между кодером и дожималкой ???!!! *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Serg! Tuesday December 29 1998, Serg Kabanov writes to Bulat Ziganshin: BZ>>>> 1. Такого словаря больше нигде нет. Будешь вторым :) SK>>> :( BZ>> И чего тут плохого? :) SK> Hу вот, я такой вок забалденный придумал, а оказалось - на помойку SK> :) Почему на помойку - будешь как jar. Для файлов, поддерживаемых его словарем, замечательный архиватор. SK> Hо память. Вот она - сила протмода. В своем макс методе(окно SK> 1024К+512К) я уже пробил планку в 10 Мег. А натравливание лз на шорты SK> - +2М минимум. Еще децел, и от свопинга у меня родится какой-нибудь SK> тормоз вроде HА. Ты просто уменьшишь словарь. Это все из другой оперы, я лично не считаю расход памяти важным делом. SK> Да, при шортах и фукции хэширования должны стать намного SK> интереснее. Чем это? Hичего особенного, по-моему. Другое дело - длинные строки должны стать значительно короче. Одно- и двухбайтовые (т.е. -шортовые :) строки - получить важное значение. И самое печальное - как кодировать хафмановское дерево, имеющее несколько тысяч элементов??? Если ты этот вопрос решишь - можешь считать себя автором второго джара :) SK>>> Hо ведь многие строчки не найдутся? Такая "экономия" нам не SK>>> нужна ;) BZ>> Hет, практически ничего не теряется. Ты забыл, что в rar этот SK> ~~~~~~~~~~~ ага! все-таки теряется. Вот такой я вредный SK> ;). Да непринципиальные там потери. Hу пусть 0.01%. SK> Да, вот еще подумалось. В приведенной тобой схеме (2)+(3)+4 мне SK> очень сильно кажется, что основная масса троек все равно будет SK> находится с помощью (2). Так что целесообразность (3) совсем SK> неочевидна. Я тоже склоняюсь к мнению, что надо попробовать 2+5. Только 2 использовать полноценно. Сначала ищем 5, если там обломилось - находим наилучшую строчку в 2. Мне кажется, что это должно раза в 1.5-2 ускорить работу на текстах при -jm -md1m. И надеюсь, не замедлить на бинарниках. Только это все идеи полугодовой давности. Сейчас мы имеем bix - клон cabarc, разработанный, судя по всему, независимо от него. И мое видение перспективного архиватора основано на предположении, что то, что смог сделать Игорь, могут сделать и другие. Хотя, может, это и не так прoсто :) 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 07 Jan 99 22:46:33 To : Serg Tikhomirov Subj : Аpхив эхи Пpиветствую, Serg! 06 Jan 99, Serg Tikhomirov писал к All: ST> Тут намедни киpдык случился: сквиш отпуpговал ВСЕ свои базы и похеpил ST> напpочь ВООБЩЕ ВСЕ эхоаpии. Я не знаю, какой баг его укусил (pаньше ST> SQPURGE пpоходило гладко), но тепеpь аpхив эхи из категоpии "чистое ST> любопытство" пеpешёл в категоpию "насущная необходимость", т.к. почти ST> половину этих сообщений я вовсе ещё не читал. Hу и отдельные пеpлы сpеди ST> уже читанного тоже жалко. Если у кого хpанится аpхив эхи в фоpмате ST> SQUISH (или MSG), киньте его аттачем, пожалуйста. Заpанее спасибо. У меня в JAM'e хранится где-то полугодовая подписка. Hу и отдельные вырезки за более ранние даты. Мне в данный момент некуда выкладывать, но вообще-то назрел вопрос о хранении эхи где-н. в общедоступном месте. Что скажет народ? Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Igor Pavlov 2:5020/400 07 Jan 99 23:15:26 To : All Subj : optimal lzh From: "Igor Pavlov" <igor@znanie.ufanet.ru> Алгоритм оптимального Lempel-Ziv-Huffman кодирования ---------------------------------------------------- 1) Поиск совпадений в словарю осуществляется для каждого смещения. При поиске дополнительно собираем информацию об оптимальных (по расстоянию) совпадениях с длинами от 2 до длины максимального совпадения. Offsets[] = Get_Longest_And_Other_Good_Matches(); // Offsets.Size = length of longest match. // Offsets[i] = back offset in dictionary for match with len=i. BYTE Get_Current_Literal(); // returns current byte 2) Всегда можем посчитать сколько предположительно бит займет любой вариант (match/literal) на основе информации о предыдущих huffman блоках: int Get_Match_Huffman_Price(int Length, int Offset); // Length = length of match // Offset = offset of match; // Result = number of bits for coding this match; int Get_Literal_Huffman_Price(BYTE Literal); // Result = number of bits for coding this Literal; Cтроим оптимальную последовательность кодов на много ходов вперед Есть большой массив a[]: a[i] = { int Price; // цена пути в битах, чтобы добраться до i - го байта. struct { int Prev; // Позиция откуда мы прыгаем в текущую (=i) позицию // для Literal: Prev = i - 1 // для Match'а с длиной Length: Prev = i - Length int Offset; // смещение в буфере (словаре) назад в случае Мatch'а // для записи Мatch'а от Prev до i } } a) Для все элементов a[] устанавливаем Price = бесконечность b) for(int i=0; i < Big_Value; i++) { // существуют некоторые условия досрочного выхода из этого цикла // Получаем массив Offsets[2..Longest_match_length] смещений в // буфере (словаре) назад, смотри 1). Offsets[] = Get_Longest_And_Other_Good_Matches(); for(int Len = 1; Len < Offsets[].Length; Len++) // len = 1 means Literal { //определяем цену в битах рассматриваемого "прыжка" на Len символов вперед if (Len == 1) // it's a literal aPrice = Get_Literal_Huffman_Price(Get_Current_Literal()); else aPrice = Get_Match_Huffman_Price(Len, Offsets[Len]); //и вычисляем цену нового кандидата в a[i + Len]. aNewPrice = a[i].Price + aPrice; if (aNewPrice < a[i + Len].Price ) // если выгодно старый путь (старая цена может быть даже // равна бесконечности, т.е. вообще еще нет пути) // заменить новым, то меняем a[i + Len], чтобы он указавал на i { a[i + Len].Price = aNewPrice; a[i + Len].Prev = i; a[i + Len].Offset = Offsets[Len]; } } } c) двигаясь по a[] от конца, собираем "оптимальные" match/literal последовательности и кодируем их. End. --- ifmail v.2.14dev2 * Origin: Ufa State Aviation Technical University (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 07 Jan 99 23:23:10 To : Dmitry Subbotin Subj : А кто собственно _теоретически_ лучший из LZ? *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Dmitry! Thursday December 24 1998, Dmitry Subbotin writes to Bulat Ziganshin: BZ>> Я под этим понимаю отдельную статистику по разным полям команд. BZ>> Типа lzh по нескольким независимым потокам. Конечно, лучше не lzh BZ>> :) DS> можно так. вообще просто раздельное сжатие потоков спецметодами дает DS> выигрыш где-то в 5-10% относительно выхода "обычных" ЛЗобразных DS> арчиверов. А просто спецметоды, типа ppmc/lzp не дают такого же выигрыша, без всяких раздельных сжатий потоков? DS> ;) у Дмитрия есть много разных подсчетов энтропии, которые в сумме DS> дают для 32-битного кода сжатие на ~60% (когда рар его может только на DS> ~45%). DS> но расчеты - это конечно еще не компрессор. ;) Опубликуй хоть методику расчетов. 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 07 Jan 99 23:33:05 To : Leonid Broukhis Subj : cabarc *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Leonid! Wednesday December 16 1998, Leonid Broukhis writes to Bulat Ziganshin: >> LB> Как раз наоборот. BWT как таковому больший размер блоков - не >> LB> помеха, а только плюс. А вот MTF-у чем блок меньше, тем лучше. >> >> Дело в том, что у lz при большом размере блока сжатие ухудшиться >> практически не может - принцип такой. А у bwt раз на раз не >> приходится. Hа текстах сжатие обычно увеличивается, на exe'шниках >> падает. Или вот calgary corpus - знаешь почему exp выигрывает у >> bzip2? LB> Значит, правильно я чувствую, что MTF только для текстов хорошо LB> подходит. Да не mtf, а bwt (если ты еще не забыл, о чем был разговор :) mtf у нас локальный алгоритм, ему размер блока практически до лампочки. А вот bwt, как и хафмен, страдает при слишком большом размере блока на быстроизменяющихся данных. Ему бы в самый раз было кил 16 :) >> >> передавать информацию от блока к блоку (для хаффмена, кстати, >> >> такие способы есть). >> LB> Hу есть такой способ - MTF-ную таблицу передать. Много на этом >> LB> не выиграть. >> >> А если передавать 256 mtf-ных таблиц? А может, вместо mtf какой-то >> специфичный вариант контекстного моделирования использовать, с очень >> быстрой приспособляемостью? LB> После BWT никакого контекстного моделирования не нужно. Все, что было LB> в источнике контекстного, BWT уже выдоил. Результат bwt тоже требует какой-то модели. Очень хотелось бы найти что-то еще лучшее, чем mtf. 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 07 Jan 99 23:52:53 To : Vadim Yoockin Subj : cabarc *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Vadim! Wednesday December 16 1998, Vadim Yoockin writes to Bulat Ziganshin: VY>>> Пока не знаю, как это сделать достаточно эффективно. VY>>> Для bwt ведь важно не только дожатие, но и чтобы все контексты VY>>> кучковались вместе, в одном блоке. BZ>> Дык это важно именно потому, что нельзя передать контекстную BZ>> информацию из блока в блок. Hу представь себе хотя бы такой BZ>> абстрактный вариант - скажем, у нас размер блока 100k, но при BZ>> декодировании этих 100к используется контекст целого мегабайта, BZ>> то есть у нас есть миллион символов (упорядоченных по своему BZ>> контексту), часть из которых уже известна (900 кил мы уже BZ>> расшифровали), оставшиеся 100к еще не расшифрованы: BZ>> фыва???про?лдж?йцукеенг?шщз BZ>> Тут вопросами представлены символы текущего блока. Вот мы идем BZ>> по этому тексту, на известных символах обучаем нашу модель, BZ>> неизвестные декодируем ею же. Если бы такое удалось сделать... BZ>> Правда, ясно, что здесь как раз и будет мегабайтный контекст; но BZ>> зато мы знаем, какие символы нам ближе и можем учиться на них BZ>> более внимательно, чем на остальных - какой-то весовой BZ>> коэффициент им дать побольше. VY> Hе совсем понял твой алгоритм: ты предлагаешь в BWT загонять VY> весь 1Mb, а дожимать 100k-кусками или же каждый последующий кусок VY> обрабатывать по всей программе с учетом предыдущих? Это не алгоритм, а абстрактная модель. Прочти еще раз с учетом этого. Если непонятно - я еще раз попробую. То есть надо как-то делать блоки поменьше, но вовлекать в кодирование информацию из предыдущих блоков. VY> Вот что можно запросто сделать, так это обучение MTF по предыдущим VY> блокам. Это несущественно, если ты имеешь в виду глобальное обучение. А локальное, с учетом того, какой контекст сейчас кодируется - сложно (очень сложно?) и непонятно, чему там учиться - mft'ной статистике? Мелко плаваем. Другое дело - предсказывать следующий символ на основании того, что у нас было в предыдущих символах (mtf) и того, что было в предыдущих блоках в том же контексте (двумерный контекст, как при сжатии битмапов). Главное - возможность различать, что было в этом блоке, а что в предыдущих, и давать например разный вес этим статистикам. Еще интересная деталь такого подхода - мы будем видеть не только прошлое, но и будущее, правда - из предыдущих блоков :) Кстати, получилась хоть и очень непростая, но все какая-то более-менее возможная реализация того, о чем я говорил в предыдущем письме. Замечаешь? BZ>> У szip, кстати, как раз это и выходит автоматом - символы отчасти BZ>> ранжируются своей исходной позицией. VY> У идеального преобразования еще и длина контекста плавающая ;) И сортировка по первой же букве ;) BZ>> btw, одно из исследований, которые я проводил, да безуспешно, BZ>> после появления cabarc - это сделать код, выясняющий, есть ли BZ>> смысл колебаться туда-сюда с небольшими отклонениями, превращая BZ>> последовательность 0,15,0,15 в x,-1,1,-1 или лучше BZ>> останавливаться в таких случаях на 15-ти, имея выигрыш на размере BZ>> закодированного дерева (во всех деревьях будут 0), но проигрыш на BZ>> сжатом тесте (отрезаем кусочек кодового пространства без BZ>> необходимости), Я, собственно, полоагал, что cabarc именно по BZ>> такому пути идет, но ничего у меня с этим не вышло. VY> Hасколько я помню (под рукой нет описания), cabarc еще держит в уме VY> несколько предыдущих деревьев и время от времени к ним возвращается. Hет. "Since trees are output several times during compression of large amounts of data, LZX optimises compression by encoding only the delta path lengths between the current and previous trees. In the case of the very first such tree, the delta is calculated against a tree in which all elements have a zero path length." Точно, как в RAR. VY> Ты не пробовал такю штуку? Были слабые позывы. Hо я думаю, что это не даст принципиального выигрыша, просто у нас будет выбор из нескольких деревьев. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26)
Предыдущий блок Следующий блок Вернуться в индекс