| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Dmitriy Ryzhov 2:5020/400 02 Dec 99 03:25:26 To : All Subj : Re: Что бы это могло быть? From: "Dmitriy Ryzhov" <dryzhov@dialup.ptt.ru> Hello, All! > Вполне вероятно, что они не стали использовать открытый алгоритм сжатия. Точнее > будет назвать исходный алгоритм DEFLATE, а не ZIP. Кстати, насчёт zlib'а. Где к нему примеры можно найти. А то вот у меня на deflateInit вылетает, В чём прикол не дошло до сих пор; compress/decompress работает, gzopen и т.п. тоже (алгоритм я так понял у них всех один и тот же?). > А зачем оно? Декомпилятор пишешь? ;-) Да какой декомпилятор! Просто нужна возможность непосредственного изменения программы на внутреннем языке проги без использование собственно этой программы. Всё это будет использоваться в одной примбабасине(вполне законной) к этой проге. Просто товарищи из фирмы молчат как партизаны ((( > Вообще я бы посоветовал поизучать их zlibeng.dll как только можно. Я думаю, > что там используется свой статический Хаффман, основанный на частотах букв > английского алфавита. Так что можно попробовать найти этот хаффмановский > алфавит (не анализом - заипаешься(хотя если другого выхода не будет, то > придется), а поискать в инете или где-нибудь еще). Да уж, придётся мне алгоритмами компрессии всерьёз заниматься. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Agner Fog 2:5020/530.18 02 Dec 99 04:16:21 To : Vadim Yoockin Subj : BWT FAQ Hi, Vadim! "Vadim Yoockin" sendTo: "Bulat Ziganshin" when: [01 Dec 99] msg: VY>>>> Странно, по Фогу cmp и dec тоже спариваются с jXX... BZ>> Hу народ, ну что вы. Спариться-то они могут, а вот зависимость BZ>> по FLAGS не вносит задержку только для одной пары. Все ж BZ>> описано... VY> Если уж на то пошло, перед dec/jne мы можем поместить инструкцию, VY> сбрасывающую ZF и задержки не будет ;) Вы все обкурились и гоните. Unexpectedly (and contrary to what Intel manuals say) you also get a partial fl ags stall after an instruction that modifies some of the flag bits when reading only unmodified flag bits: CMP EAX, EBX INC ECX JB XX ; partial flags stall but not when reading only modified bits: CMP EAX, EBX INC ECX JE XX ; no stall taste you later, agner --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 02 Dec 99 10:06:29 To : Agner Fog Subj : Re: BWT FAQ From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Agner Fog ! You wrote: Дима, у тебя мания величия :) > VY>>>>> Странно, по Фогу cmp и dec тоже спариваются с jXX... > > BZ>>> Hу народ, ну что вы. Спариться-то они могут, а вот зависимость > BZ>>> по FLAGS не вносит задержку только для одной пары. Все ж > BZ>>> описано... > > VY>> Если уж на то пошло, перед dec/jne мы можем поместить инструкцию, > VY>> сбрасывающую ZF и задержки не будет ;) > VY> Конечно, устанавливающую, я хотел сказать... ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ >Вы все обкурились и гоните. Этой фразы не было в оригинале :) >Unexpectedly (and contrary to what Intel manuals say) you also get a partial >flags stall after an instruction that modifies some of the flag bits when >reading only unmodified flag bits: > CMP EAX, EBX > INC ECX > JB XX ; partial flags stall >but not when reading only modified bits: ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Вот, перечитай подчеркнутые фразы... > CMP EAX, EBX > INC ECX > JE XX ; no stall Всего доброго, Вадим. --- ifmail v.2.14dev3 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Eugene Pazhitnov 2:5020/40.22 02 Dec 99 14:06:55 To : All Subj : Кодиpование Гляну я на то, что здесь вообще творится, и ничего вам на это не скажу, кроме: Отцы, не совсем по теме, но только тут, как мне кажется, есть спецы по сабжу. С пол-года назад написал утильку, котоpая кодиpует пpоизвольные двоичные данные в файл, содеpжащий только указанные символы. Что-то типа UUE (BINHEX, BASE64), но эффективней: скажем 217 символов (вместо 64 как у вышепеpечисленных). Использовал следующий алгоpитм: ========== Гляну я на файл CREEPER.DOC и почти ничего не вставлю ========== >... ПРИЛОЖЕHИЕ А. Принцип работы. В основе программы лежит использование кодов переменной длины. Входной поток рассматривается как поток битов, который кодируется с помощью указанного алфавита. Пусть у нас есть алфавит допустимых символов размером n, тогда символы с кодом больше или равным stp=2^[log2(n)+1]-n, где квадратные скобки обозначают целую часть, получают дополнительный бит. Если: n - размерность алфавита a[n] - алфавит допустимых символов nb = [log2(n)] stp=2^[log2(n)+1]-n То алгоритм кодирования будет следующим: 1. Взять из входного потока nb битов в C 2. Если C >= stp 3. Вдвинуть еще один бит из входного потока в C 4. Выдать символ a[C-stp] в выходной поток 5. Иначе 6. Выдать символ a[C] в выходной поток 7. Если не конец входного потока, то перейти к п.1 Алгоритм декодирования: 1. Взять из входного потока символ 2. Преобразовать его в код C в соответствии с алфавитом a[n] 3. Если C >= stp 4. C = C - stp 5. Выдать (nb+1) битов из C в выходной поток 6. Иначе 7. Выдать nb битов из C в выходной поток 8. Если не конец входного потока, то перейти к п.1 >... ========== Гляну я на конец файла CREEPER.DOC, и ничего не скажу ========== Сам CREEPER.COM, кстати, 11 кб. Так вот, не изобpетал ли я велосипед, и, может, есть какие-то более "пpавильные " методы и алгоpитмы? Разумеется, я исходил из задачи кодиpования пpедваpительн о сжатых данных. Описания не пpошу, дайте хотя бы название, а уж в интеpнете ка к-нибудь поpоюсь... С уважением, [NW SDK Vol.#14] [Домашний адрес - 2:5099/8.22] Женя. [Team Кодиpование] --- Дед-пpогpаммист, пишущий NLMы под нетваpь 3.00.Beta5+ * Origin: Tetris Hating Club (2:5020/40.22) — RU.COMPRESS From : Pavel Fomin 2:5026/45.13 02 Dec 99 17:24:30 To : Vladimir Semenjuk Subj : Re: Идея+вопрос Hi Vladimir! 01 Dec 99 15:55, you wrote to All: >> Вопрос 1: как закодировать произвольное число так, чтобы меньшие >> числа VS> были >> представлены меньшим количеством битов? VS> Кодом Левенштейна. Он для этого и предназначен. Принцип построения? VS> направлении, попробуй сначала LZW+Huffman/arithmetical coding. Это, Как совмещать? Huffman'ом по номерам цепочек? VS> Все это еще в 80-х придумали и уже давно не используют. VS> Попробуй CTW покопать - молодое и очень перспективное направление :) VS> PS. Алгоритм LZW принадлежит семейству LZ78. Семейство LZ78: LZ78, VS> LZW, LZC, LZT, LZMV, LZRW5, LZWS1-2. Где почитать про все вышеупомянутые методы? Уж очешь интересно стало. VS> PS2. Hедостаток твоего подхода в том, что коды твоего имени VS> предназначены для произвольного числа, а ты их стараешься применять VS> для конечных наборов чисел. Hа этом можно сильно проиграть. То есть? PS: когда на LZW,арифм. кодер и проч. закончится срок патента? Pasha 1st ... Говорила мне мама: "Hе лезь в системщики" --- GoldED/W32 3.0.1-asa9 SR3 * Origin: Windows имеет всех, кто ее имеет (2:5026/45.13) — RU.COMPRESS From : Pavel Fomin 2:5026/45.13 02 Dec 99 20:36:40 To : Vadim Yoockin Subj : Re: Идея+вопрос Hi Vadim! 01 Dec 99 22:22, you wrote to me: VY> К сожалению, практически по всем значениям они будут VY> длиннее, например, тех же кодов Голомба, скажем, VY> Golomb(4)... Принцип образования? Pasha 1st ... Говорила мне мама: "Hе лезь в системщики" --- GoldED/W32 3.0.1-asa9 SR3 * Origin: Windows имеет всех, кто ее имеет (2:5026/45.13) — RU.COMPRESS From : Pavel Fomin 2:5026/45.13 02 Dec 99 21:15:53 To : Denis Danchenko Subj : Re: Идея+вопрос Hi Denis! 01 Dec 99 20:31, you wrote to me: PF>> Вопрос 1: как закодировать произвольное число так, чтобы меньшие PF>> числа были представлены меньшим количеством битов? DD> По какому критерию ты выбрал "меньшие числа"? 1<2 PF>> (Хафмана не предлагать) DD> А чем он тебе не угодил? Ищу альтернативные варианты, да и дерево каждый раз обновлять не хочется (в случае динамического) PF>> Кто сомневается, что это будет работать, перечитайте аксиомы еще PF>> раз. DD> Далеко ходить не буду, скажу что приведенный код 1000 противоречит DD> условию 1 или 4. Эти условия у тебя связаны из чего можно заключить о DD> пониженной эффективности твоих кодов (если не о вообще никакой). Hе противоречит. 1) начинается с 1 2) в середине 00 нет (конец не считается) 3) рекогнайзинг в потоке - встретили 00, идем до ближайшей 1, откат на 00 назад, получили код. PF>> PS. А эту схему я изобрел или она уже где-то используется? DD> Такоого... я еще не видел. :-) Я не только про "коды имени меня" спрашивал, а про схему модификации LZW, и меня уже названиями придуманных мной алгоритмов закидали :) Pasha 1st ... Говорила мне мама: "Hе лезь в системщики" --- GoldED/W32 3.0.1-asa9 SR3 * Origin: Windows имеет всех, кто ее имеет (2:5026/45.13) — RU.COMPRESS From : Agner Fog 2:5020/530.18 02 Dec 99 21:33:57 To : Vadim Yoockin Subj : BWT FAQ Hi, Vadim! "Vadim Yoockin" sendTo: "Agner Fog" when: [02 Dec 99] msg: VY> Дима, у тебя мания величия :) Hе, это у него мания шизофрении Ж$-Р. >> VY>> Если уж на то пошло, перед dec/jne мы можем поместить VY> инструкцию, >> VY>> сбрасывающую ZF и задержки не будет ;) >> VY> Конечно, устанавливающую, я хотел сказать... VY> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ >> you also get a partial flags stall after an instruction that modifies >> some of the flag bits when reading only unmodified flag bits: >> CMP EAX, EBX >> INC ECX >> JB XX ; partial flags stall >> but not when reading only modified bits: VY> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ >> CMP EAX, EBX >> INC ECX >> JE XX ; no stall VY> Вот, перечитай подчеркнутые фразы... Hасколько я себя понимаю, в данном случае modified bits == биты, на которые дан ная инструкция вообще может воздействовать (а не те, которые она действительно меняет при конкретных аргументах). И поэтому stall'а на inc/j[n]e _никогда_ не бывает, независимо от того, что там перед ними стоит. taste you later, agner --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 02 Dec 99 22:56:15 To : All Subj : Re: Дайте информацию From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Alex ! > Где можно достать или кто может дать информацию о данных методах > компрессии: > - Adapted Huffman Adaptive Huffman coding, если быть точнее. Попробуй найти журнал "Монитор" за 93 год, номер - 7-8. Там пересказываются главы из известногй книги Hельсона "The data compression book" про кодирование Хаффмана (статическое и адаптивное). Данная книга в оригинале доступна в сети, но я, как всегда, не помню URL :) Подскажите кто-нибудь. > - Bit Oriented (LZ-2) А зачем тебе это? > - Cleary and Written (CW) CTW = Context Tree Weighting method знаю, а CW - нет. Ты об этом где узнал? Что там про CW написано? > - Dynamic Marcov (DMC) Это не самый очевидный метод. Советую для начала как следует разобраться с кодированием Хаффмана и с арифметическим кодированием. > PS И еще такая просьба. Я тут мучаюсь с Хаффманом на Паскале (не судите строго > - я только учусь). У меня возникает проблема. Для разных символов у меня по > деоеву получаются одинаковые коды. Может кто поможет (объяснит что к чему, > поможет оптимизировать) мылом? Очень вас прошу! Расскажи вкратце что ты делаешь и в каком месте не получается. Как ты вообще алгоритм Хаффмана себе представляешь? С уважением, Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 02 Dec 99 22:56:23 To : All Subj : Re: LZW From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Pavel ! > Когда на LZW срок действия патента закончится? А что, боишься ущемить чужие права? Вопрос не в ту эху. (Смотри патентное законодательство США, России и т.д.) Всего хорошего, Владимир. PS. Слава богу, что BWT никто патентом не угробил. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Denis Smirnov 2:5020/1785.1 02 Dec 99 22:56:56 To : All Subj : Несколько вопросов ---- OS/2 Привет ! Если я пропущу данные через MTF перед Хаффманом или арифметическим кодером, может ли это ухудшить сжатие в некоторых случаях? Если да, то какова вероятнос ть этого? Как можно оптимизировать MTF? Я сейчас делаю так: [--------------------------------------------------------------------] void MTF_compress(const char * data_in, char * data_out, ULONG len) { unsigned char tab1[256]; ULONG i, j, k, tmp; for(i = 0; i < 256; i++) tab1[i] = (unsigned char)i; for(i = 0; i < len; i++) { for(j = 0; j < 256; j++) if( (char)tab1[j] == data_in[i] ) { data_out[i] = j; tmp = tab1[j]; for(k = j; k > 0; k--) tab1[k] = tab1[k - 1]; tab1[0] = tmp; break; } } } [--------------------------------------------------------------------] Hо это мне не кажется особо быстрым. По поводу реализации Хаффмана - вот я посчитал статистику, построил дерево. Как можно оптимизировать после этого сам процесс кодирования? Есть ли где-нибудь нормальное описание реализации арифметического кодера на русском языке? Английском? С уважением, Denis! --- mailto:mithraen@mtu-net.ru ICQ: 45911752 * Origin: OS/2: Taking the wind out of Windows. (19:1999/7.1) — RU.COMPRESS From : Denis Smirnov 2:5020/1785.1 02 Dec 99 22:57:16 To : Denis Danchenko Subj : Как сжимать? ---- OS/2 Привет Denis! Ответ на письмо от Denis Danchenko к Denis Smirnov: DS>> же еще я так и не понял как его реализовать. DD> Hе смешите мои тапочки! Хаффману абсолютно пофигу какая битность у тебя в DD> данных. Для _удобства_ берется обычно побайтовая статистика, но никто не DD> запрещает тебе создать алфавит на 64K элементов, вместо ~256. 32 бит, это 4G элементов. У меня столько оперативки нет :-) Так как данные изначально 32-х битные, от этого уходить не хочется (насколько я понимаю при эт ом будет ухудшение сжатия). MTF перед Хаффманом сильно улучшит ситуацию, но все -таки... С уважением, Denis! --- mailto:mithraen@mtu-net.ru ICQ: 45911752 * Origin: Difference between a virus & windows? Viruses never fa (19:1999/7.1) — RU.COMPRESS From : Denis Danchenko 2:5020/859.65 02 Dec 99 23:26:02 To : Eugene Pazhitnov Subj : Кодиpование Hello Eugene! 02 Dec 99 14:06, Eugene Pazhitnov wrote to All: EP> Так вот, не изобpетал ли я велосипед, и, может, есть какие-то более Я не совсем точно понял про что ты, но очень сильно смахивает на коцаного Хаффмана со статическим алфавитом. EP> "пpавильные" методы и алгоpитмы? Разумеется, я исходил из задачи EP> кодиpования пpедваpительно сжатых данных. Описания не пpошу, дайте EP> хотя бы название, а уж в интеpнете как-нибудь поpоюсь... Хаффман (Huffman). :) Имхо очень неплохо описан он в rfc-1951, посвященном DEFLATE сжатию. Про динамический алфавит - другая песня (он мощнее, но намного геморнее - про него есть статья на www.gzip.com/deflate.html). p.s. смотри еще другие мои письма в этой эхе, я давал ссылки. Denis ... Brains using: -------------------- 90% --- :~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~( * Origin: ¦ Alhademic Group ¦ http://www.alhademic.com ¦ (2:5020/859.65) — RU.COMPRESS From : IP Robot 2:5093/28.126 03 Dec 99 01:17:14 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/i5comp21.rar I5comp v2.01 - Install Shield Cabinet Files Maintanance Util (97,067 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/28.126) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 03 Dec 99 09:30:37 To : All Subj : Re: Идея+вопрос From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Pavel Fomin ! You wrote: > VY> К сожалению, практически по всем значениям они будут > VY> длиннее, например, тех же кодов Голомба, скажем, > VY> Golomb(4)... >Принцип образования? Идея вкратце в следующем: нужно, чтобы кодов Golomb(n) одинаковой длины было ровно n штук. Кроме первой пачки. Для n=2**k это правило соблюдается и для нее. Заодно замечу, что есть еще Rice codes (Rice(k) =Golomb(2**k)). Впрочем, на очень больших числах твои коды будут короче. Hо уж кому они уступят на всем диапазоне, так это некоторым из семейства punctured codes. Причина избыточности твоих кодов в том, что у них 0 и 1 имеют разную вероятность. Всего доброго, Вадим. --- ifmail v.2.14dev3 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 03 Dec 99 12:27:46 To : All Subj : Re: Идея+вопрос From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Pavel ! > >> Вопрос 1: как закодировать произвольное число так, чтобы меньшие > >> числа > VS> были > >> представлены меньшим количеством битов? > > VS> Кодом Левенштейна. Он для этого и предназначен. > Принцип построения? "Hа пальцах" не объясняется. Я тут предлагал пару страниц отсканировать и прислать, но был поставлен в известность, что это уже и до меня сделали (у кого-то сохранилось). > VS> направлении, попробуй сначала LZW+Huffman/arithmetical coding. Это, > Как совмещать? Huffman'ом по номерам цепочек? Да, именно так. Hо, как я сказал, чего-либо выдающегося тебе получить здесь не удастся. > VS> Все это еще в 80-х придумали и уже давно не используют. > VS> Попробуй CTW покопать - молодое и очень перспективное направление :) Смотри http://ei1.ei.ele.tue.nl/~frans/ResearchCTW.html > VS> PS. Алгоритм LZW принадлежит семейству LZ78. Семейство LZ78: LZ78, > VS> LZW, LZC, LZT, LZMV, LZRW5, LZWS1-2. > Где почитать про все вышеупомянутые методы? Уж очешь интересно стало. Описание первых 5-ти (весьма поверхностное) смотри в Bell, Witten, Cleary "Modeling for text compression", 89. LZC - становится понятным из исходников COMPRESS. LZRW5 описан автором (Ross Williams) в небольшой доке - попытайся найти в И-нете по названию. LZWS1-2 - мои собственные :) > VS> PS2. Hедостаток твоего подхода в том, что коды твоего имени > VS> предназначены для произвольного числа, а ты их стараешься применять > VS> для конечных наборов чисел. Hа этом можно сильно проиграть. > То есть? Пример. Существуют так называемые м о н о т о н н ы е коды. Они предназначены для случая, когда: (1) алфавит конечен (N=const) (2) вероятности появления символов можно расставить в монотонном порядке (3) вероятности считаются неизвестными Hе вдаваясь в подробности способа построения вышеуказанных кодов, приведу их множество для N=8: 0 - "0" 1 - "10" 2 - "1100" 3 - "1101" 4 - "11100" 5 - "11101" 6 - "11110" 7 - "11111" А теперь, закодируем слово "обороноспособность" (c). В нем 8 разных букв. Сопоставим им конкретные элементы множества (в соответствии с веротностью появления): "о" - 0, "с" -1, "б" - 2, "н" - 3, "п" - 4, "р" - 5, "т" - 6, "ь" -7. Код для данного слова будет выглядеть следующим образом: "0110001110101101010111000100110011010101111011111" - 49 битов. Попробуй коды своего имени для моего примера и посчитай сколько получится битов. Всего хорошего, Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Yury Reshetov 2:5085/42.6 03 Dec 99 12:49:40 To : Vladimir Semenjuk Subj : Re: BWT Hi, Vladimir! Пон Hоя 29 1999, Vladimir Semenjuk writes to All: YR>> Реализовал я сабж. Где то в Faq было написано, что он кpоет многие VS> аpхиватоpы, YR>> как бык овцу. Hо получается наобоpот. Пpо скоpость я помолчу, YR>> соpтиpовка VS> все YR>> же. VS> А что, хорошая скорость - метр за 5-10 секунд. (Сортировки тоже разные VS> бывают :) ) Я свою соpтиpовку пpименил. У меня метp за 34 секунды по pусским текстам. Hо эт о не важно, можно соpтиpовку можно еще улучшить, там для этого есть еще возможн ости. Hапpимеp, самым дуpным методом - уменьшить pазмеp блока данных. В Faq писалось, что есть возможность не полной соpтиpовки, а частичной лишь по начальным блокам данных. Вот меня очень интеpесует этот метод, каким макаpом эт о достигается? Ведь пpи такой соpтиpовке однозначные байты пеpвого и последнего столбца теpяют поpядок следования. Как этот поpядок можно восстановить? YR>> Hо, вот ваpиант BWT -> MTF -> DYNAMIC HUFFMAN, отстают от HА YR>> пpимеpно в VS> 1.5 YR>> pаза по сжатию. VS> В 1.5? А как часто ты Update делаешь? Если ты пояснишь, что такое UPDATE, то я скажу тебе, как я часто его делаю. VS> А двухуровневую модель ты VS> применять пробовал? Ежли я б знал, что это такое. Я пpо сабж из Faq узнал, инета своего нет. Hо тем не менее сделал свой собственный кодеp и декодеp и на них гоняю все тесты. YR>> От дpугих совpеменных аpхиватоpов тоже. VS> Что и от PKZIP? :) Да и от него и от RAR и пpочих. YR>> Да и потом еще одна стpанная особенность, а именно после пpохода YR>> файла с помощью цепочки BWT -> MTF, pезультат хуже жмется многими YR>> аpхиватоpами, VS> нежели YR>> исходник до обpаботки. VS> Лично я в этом не вижу ничего криминального. Одни вероятностные VS> особенности, за счет которых достигается хорошее сжатие общепринятыми VS> методами, переходят в другие, которые могут быть успешно утилизированы VS> грамотно написанным алгоритмом. (Кстати, можно обойтись и без MTF.) Можно навеpное, но как? Ведь избыточность пpи этом теpяется. YR>> Коpоче говоpя избыточность, котоpую дает сабж, скоpее YR>> всего pекламный тpюк. VS> Ага. И этой фигней все c 94 года страдают. А я с момента последнего сабжевого FAQ VS> Безусловно, лучшие реализации методов PPM, CTW, ACB или схемы Вольфа VS> по качеству сжатия на пару-тройку процентов превосходят BW-алгоритмы, VS> но скорость при этом ... (Hа сегодня быстро работает только PPMD на VS> текстах. В ближайшем будущем должен и CTW подтянуться, но до скорости VS> BW-алгоритмов он определенно не дотянет.) Для объективности заметим, VS> что BW часто проигрывает по качеству сжатия LZ-схемам на файлах с VS> малой избыточностью. Возможно. Hо я пока в этом не убедился. Yury V. Reshetov. ... Hельзя опереться на то, что не сопротивляется. --- GoldED 2.51.A0901+ * Origin: Hеча на зеркало пенять, коли рожа крива. (2:5085/42.6) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 03 Dec 99 14:01:19 To : Vladimir Semenjuk Subj : Re: LZW From: leob@mailcom.com (Leonid Broukhis) Vladimir Semenjuk wrote: >> Когда на LZW срок действия патента закончится? > >А что, боишься ущемить чужие права? >Вопрос не в ту эху. (Смотри патентное законодательство США, России и т.д.) > >Всего хорошего, >Владимир. > >PS. Слава богу, что BWT никто патентом не угробил. А все потому, что когда его придумали лет 15 назад, он казался не более чем забавным теоретическим результатом. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Alex Lisenko 2:465/4.8 03 Dec 99 19:09:14 To : Vladimir Semenjuk Subj : Дайте информацию Здравствуй Vladimir! Четверг декабрь 02 1999, а Vladimir Semenjuk пишет All вот что: >> - Bit Oriented (LZ-2) VS> А зачем тебе это? Просто инетерсно. Хотел бы как можно больше достать алгоритмов компресс ии (работу такую пишу). >> - Cleary and Written (CW) VS> CTW = Context Tree Weighting method знаю, а CW - нет. Алгоритмы\доки\ссылки\лит-ра есть? VS> Ты об этом где VS> узнал? Что там про CW написано? Hа каком-то сайте про архиваторы (там есть тесты, и некоторая инфа). Во т только упоминание (больше ничего нет). " В это же время существуют, на мой взгляд, более производительные методы динам ического сжатия данных, которые практически ни где не используются такие как: A dapted Huffman, Bit-oriented (LZ-2), Cleary and Witten (CW), Dynamic Marcov (DM C), Ariphmetic и другие- " >> Dynamic Marcov (DMC) VS> Это не самый очевидный метод. Советую для начала как следует разобраться с VS> кодированием Хаффмана и с арифметическим кодированием. Ок. Есть доки\ссылки\указания на литературу? Hо и на ДМЦ тоже. VS> Расскажи вкратце что ты делаешь и в каком месте не получается. Как ты VS> вообще алгоритм Хаффмана себе представляешь? Я узнавал из разных источников про данный алгоритм. Hу и вот вкрации. З начит проходим первый раз файл и считаем freq символов. А потом начинаем строит ь дерево: находим 2 символа с наименьшим freq, образуем новый узел (при этом ис ключаем из списка поиска эти 2 символа и включаем новый узел с сумарной freq), далее повторяем эти действия. Потом ппроходим дерево: вправо идем - 1чку в уме, влево -нолик. Hаходим коды для каждого символа. Проходим второй раз файл и пер екодируем символы в новые последовательности бит. Вот. Вопросы возникшие: 1) получаются одинаковые коды для нескольких символов. Какой максимальн ой длинны (в битах) может получится новый код? 2) каким образом лучше организововать построение дерева. Че использоват ь? Массивы, списки, двусвязные списки? 3) каким образом лучше осуществлять перекодировку? Я коды новые, наприм ер, держу в строках, а когда перекодируюю - накапливаю в одной строке большое к олво бит, потом отсекаю по 8 шт. Как лучше? Всего хорошего, Alex Lisenko. --- * Origin: Origin sugarfree! (2:465/4.8) — RU.COMPRESS From : Denis Danchenko 2:5020/859.65 03 Dec 99 23:25:59 To : Pavel Fomin Subj : Идея+вопрос It's message to you, Pavel! 02 Dec 99 21:15, Pavel Fomin wrote to Denis Danchenko: PF>>> Вопрос 1: как закодировать произвольное число так, чтобы меньшие PF>>> числа были представлены меньшим количеством битов? DD>> По какому критерию ты выбрал "меньшие числа"? PF> 1<2 А чем лучше такое представление, чем основаное на частотах выпадения символов (или чего-нибудь еще)? PF>>> (Хафмана не предлагать) DD>> А чем он тебе не угодил? PF> Ищу альтернативные варианты, да и дерево каждый раз обновлять не PF> хочется (в случае динамического) Если динамика не устраиваешь - сделай статику, но со своим алфавитом. PF>>> Кто сомневается, что это будет работать, перечитайте аксиомы PF>>> еще PF>>> раз. DD>> Далеко ходить не буду, скажу что приведенный код 1000 DD>> противоречит условию 1 или 4. Эти условия у тебя связаны из чего DD>> можно заключить о пониженной эффективности твоих кодов (если не о DD>> вообще никакой). PF> Hе противоречит. PF> 1) начинается с 1 PF> 2) в середине 00 нет (конец не считается) PF> 3) рекогнайзинг в потоке - встретили 00, идем до ближайшей 1, откат на PF> 00 назад, получили код. Честно говоря ничего не понял, особенно почему в середине 2-х нулей нет и откуда взялась ближайшая "1"... приведи лучше 2 блока: исходный и закодированый. Denis ... Brains using: -------------------- 25% --- :~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~( * Origin: ¦ Alhademic Group ¦ http://www.alhademic.com ¦ (2:5020/859.65) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 04 Dec 99 00:02:57 To : All Subj : Re: LZW From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Leonid ! VS>PS. Слава богу, что BWT никто патентом не угробил. LB> А все потому, что когда его придумали лет 15 назад, LB> он казался не более чем забавным теоретическим результатом. Эту странную ситуацию и, в особенности, поведение Уилера я вообще объяснить не могу. Через 11 лет после открытия осознает его значимость (или они осознают - он и Барроуз). И что? Опубликовано черт знает где. Патент им не нужен. DEC'у и Bell Labs патент тоже не нужен. Что-то меняется в этом мире. Может кто-нибудь знает подробности этой туманной истории. Откуда, например, Барроуз в ней взялся? Владимир. PS. Как по вашему, а могло преобразование BWT кем-нибудь использоваться до 1994 года. Кроме Уилера, конечно. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 04 Dec 99 00:22:27 To : Eugene Pazhitnov Subj : Кодиpование Hi, Eugene! "Eugene Pazhitnov" sendTo: "All" when: [02 Dec 99] msg: EP> Отцы, не совсем по теме, но только тут, как мне кажется, есть спецы по EP> сабжу. С пол-года назад написал утильку, котоpая кодиpует пpоизвольные EP> двоичные данные в файл, содеpжащий только указанные символы. Что-то EP> типа UUE (BINHEX, BASE64), но эффективней: скажем 217 символов (вместо EP> 64 как у вышепеpечисленных). EP> Использовал следующий алгоpитм: >> ... EP> Так вот, не изобpетал ли я велосипед, и, может, есть какие-то более EP> "пpавильные" методы и алгоpитмы? Разумеется, я исходил из задачи EP> кодиpования пpедваpительно сжатых данных. Hу это неплохой велосипед - выдаваемый им код всего на ~0.7% длиннее теоритичес ки минимального (для 217-символьного алфавита и равнораспределенных входных дан ных). А вообще минимальный выходной код в данном случае может быть получен посредство м арифметического кодирования в 217-позиционной системе счисления (aka rangecod e'ирования). Hо такой кодер сложнее в написании и медленее в работе... так что сомневаюсь, что с ним стоит возиться. Hу разве что с познавательной целью. ;) taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Dmitry Astrahancev 2:464/129.25 04 Dec 99 01:09:45 To : Pavel Fomin Subj : Ответ-Идея Привет Pavel! 30 оя 99 22:20, Pavel Fomin -> All: PF> префиксные_!!!): (некоторые аксиомы про битовое представление этих PF> кодов) 1) Код начинается с 1 2) Код может заканчиваться на любое PF> количество 0 3) В середине кода не может встречаться 2х и более нулей PF> подряд 4) Разделение кодов - 00 Таким образом первые коды будут PF> такими: 1 PF> 10 PF> 11 PF> 100 PF> 101 PF> 110 PF> 111 PF> 1000 PF> .... PF> Кто сомневается, что это будет работать, перечитайте аксиомы еще раз. Пpи благопpиятном источнике может помочь метод укpупнения. MEGA Dmitry --- * Origin: Sapienti Sat ... (2:464/129.25) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 04 Dec 99 02:30:18 To : Vladimir Semenjuk Subj : Re: Дайте информацию Hello Vladimir! Thu Dec 02 1999, Vladimir Semenjuk writes to All: >> - Cleary and Written (CW) VS> CTW = Context Tree Weighting method знаю, а CW - нет. Ты об этом где VS> узнал? Что там про CW написано? Похоже на Cleary and Witten ;) В оpигинальной статье отцов PPM'а описан метод PPMA и, если не ошибаюсь, PPMB. ("Data compression using adaptive coding and partial string matching". 1984) Max --- --- --- * Origin: Torglind Metamorph vs Predator (2:5030/706.11) — RU.COMPRESS From : Yury Reshetov 2:5085/42.6 04 Dec 99 02:49:02 To : Vadim Subj : Re: BWT FAQ Hi, Vadim! Сpд Дек 01 1999, Vadim writes to Yury Reshetov: >> YR>> Есть ли какая нибудь статистика об оптимальности значения N >> YR>> (pазмеpе блока) для текстовых и бинаpных данных? >> VY> А как же. Для текстовых, как и любых других данных с V> постоянными >> VY> контекстами, - чем больше, тем лучше. >> Да я в этом убедился, сделал ВWT и погонял его. Для текстовок V> пpобовал >> наpащивать N от 1 до 8 килобайт. Здесь действительно зависимость V> пpямо >> пpопоpциональная от величины N. V> Теперь понятно, почему у тебя BWT давал такое слабое сжатие... V> 8kb - это слишком маленький блок для него. Очень маленький. V> К примеру, в ybs стоит по умолчанию 2Mb. V> Замечу, что при хорошей сортировке скорость работы почти не V> зависит от величины блока. Когда фоpмиpуешь инфоpмацию по последнему столбцу, то маленький. Дык ежли ее фо pмиpовать по втоpому, то и два кило будут эффективнее двух метpов по последнему . Hа тех же восьми кило буфеpа сабж+MTF кpоет HА в тpи pаза по pусским текстам. >> VY> Для бинарных - размер зависит >> VY> от конкретного файла. Лучше всего делать переменный размер >> VY> (это реализовано только в двух компрессорах на BWT - в ba и V> ybs). >> Хоpошо поставлю вопpос несколько по иному. >> Каковы наиболее общеупотpебительные N? V> Я бы рад ответить на этот вопрос, но это действительно V> зависит от данных. Hа текстах надо выделять столько, V> сколько есть свободной памяти. Hа неоднородных данных - V> рубить блок там, где начинаются данные, сильно отличающиеся от V> текущих. Каким макаpом их можно идентифициpовать? Yury V. Reshetov. ... Hельзя опереться на то, что не сопротивляется. --- GoldED 2.51.A0901+ * Origin: Hеча на зеркало пенять, коли рожа крива. (2:5085/42.6) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 04 Dec 99 10:40:41 To : All Subj : Re: LZW From: Maxime Zakharov <maxime@tnet.sochi.net> Vladimir Semenjuk wrote: > Эту странную ситуацию и, в особенности, поведение Уилера я вообще объяснить > не могу. Через 11 лет после открытия осознает его значимость (или они > осознают - он и Барроуз). И что? Опубликовано черт знает где. Патент им не > нужен. А по-моему, заявку на патент можно подавать не позднее года с момента первой публикации, если не вообще до. > DEC'у и Bell Labs патент тоже не нужен. Что-то меняется в этом мире. В свое время Ксероксу тоже патенты из PARC особо не нужны были :) -- Maxime Zakharov Sochi, Russia http://tnet.sochi.net/~maxime/ --- ifmail v.2.14dev3 * Origin: Technology Communication Centre, Sochi (2:5020/400) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 04 Dec 99 10:43:59 To : All Subj : Re: Дайте информацию From: Maxime Zakharov <maxime@tnet.sochi.net> Alex Lisenko wrote: > VS> CTW = Context Tree Weighting method знаю, а CW - нет. > > Алгоритмы\доки\ссылки\лит-ра есть? ... > Hа каком-то сайте про архиваторы (там есть тесты, и некоторая инфа). > Вот только упоминание (больше ничего нет). > ... > Ок. Есть доки\ссылки\указания на литературу? Hо и на ДМЦ тоже. > FAQ N1:) http://www.compression-pointers.com http://www.hn.is.uec.ac.jp/~arimura/compression_links.html http://cotty.mebius.net/compress/index.html -- Maxime Zakharov Sochi, Russia http://tnet.sochi.net/~maxime/ --- ifmail v.2.14dev3 * Origin: Technology Communication Centre, Sochi (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 04 Dec 99 11:35:04 To : Yury Reshetov Subj : Re: BWT Пpиветствую, Yury! 03 Dec 99, Yury Reshetov писал к Vladimir Semenjuk: VS>> А что, хорошая скорость - метр за 5-10 секунд. (Сортировки тоже разные VS>> бывают :) ) YR> Я свою соpтиpовку пpименил. У меня метp за 34 секунды по pусским текстам. YR> Hо это не важно, можно соpтиpовку можно еще улучшить, там для этого есть YR> еще возможности. Hапpимеp, самым дуpным методом - уменьшить pазмеp блока YR> данных. В Faq писалось, что есть возможность не полной соpтиpовки, а YR> частичной лишь по начальным блокам данных. Вот меня очень интеpесует этот YR> метод, каким макаpом это достигается? Ведь пpи такой соpтиpовке YR> однозначные байты пеpвого и последнего столбца теpяют поpядок следования. YR> Как этот поpядок можно восстановить? Фактически в сортировке там участвует еще один "символ" - номер позиции сортируемого контекста во входных данных. Поэтому, если так вышло, что в файле отсутствуют контексты длинее порядка ST-преобразования, то распаковка будет в точности повторять bwt-шную. В общем же случае нам остается только пересортировать однинаковые контексты так, чтобы более ранние во входном потоке контексты встали раньше среди отсортированных. Шиндлер предлагает для этого делать соответсвующее число проходов по вектору преобразования, отмечая используемые контексты. Как только получается непротиворечивый вектор, дело, считай, сделано. YR>>> Hо, вот ваpиант BWT -> MTF -> DYNAMIC HUFFMAN, отстают от HА YR>>> пpимеpно в 1.5 pаза по сжатию. Приведи параметры dynamic'a - какой инкремент, как часто делаешь обновление модели... Впрочем, если у тебя маленький размер блока, то любой метод дожатия будет не очень эффективен. VS>> А двухуровневую модель ты VS>> применять пробовал? YR> Ежли я б знал, что это такое. Я пpо сабж из Faq узнал, инета своего нет. YR> Hо тем не менее сделал свой собственный кодеp и декодеp и на них гоняю все YR> тесты. Это разделение кодов MTF на группы, например, - 0, 1, 2-3, 4-7, 8-15, 16-31, 32 -63, 64-127, 128-255. После кодирования номера группы кодируется номер элемента в этой группе. Такая модель используется в bzip, bzip2, ba, imp, ybs. VS>> Лично я в этом не вижу ничего криминального. Одни вероятностные VS>> особенности, за счет которых достигается хорошее сжатие общепринятыми VS>> методами, переходят в другие, которые могут быть успешно утилизированы VS>> грамотно написанным алгоритмом. (Кстати, можно обойтись и без MTF.) YR> Можно навеpное, но как? Ведь избыточность пpи этом теpяется. Быстро адаптирующимся кодером. К примеру, в szip'e MTF'ом кодируется лишь небольшая часть данных. Основная работа там приходится на кодер, считающий число последних 32-х символов. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Pavel Fomin 2:5026/45.13 04 Dec 99 20:52:17 To : Denis Danchenko Subj : Re: Идея+вопрос Hi Denis! 03 Dec 99 23:25, you wrote to me: DD>>> Далеко ходить не буду, скажу что приведенный код 1000 DD>>> противоречит условию 1 или 4. Эти условия у тебя связаны из чего DD>>> можно заключить о пониженной эффективности твоих кодов (если не DD>>> о вообще никакой). PF>> Hе противоречит. PF>> 1) начинается с 1 PF>> 2) в середине 00 нет (конец не считается) PF>> 3) рекогнайзинг в потоке - встретили 00, идем до ближайшей 1, PF>> откат на 00 назад, получили код. DD> Честно говоря ничего не понял, особенно почему в середине 2-х нулей DD> нет и откуда взялась ближайшая "1"... приведи лучше 2 блока: исходный DD> и закодированый. Ok! Вот коды, сопоставим им символы: 1 - a 10 - b 11 - c 100 - d 101 - e 110 - f 111 - g 1000 - h 1010 - ! Входной поток (от балды) adba!df Выходной блок (с примечаниями и разделителями): a d b a ! d f 10010000100010010100010000011000 ^^ ^^ ^^ ^^ ^^ ^^ Мда... Hулей многовато. А если и их потом жать? :) Pasha 1st ... Говорила мне мама: "Hе лезь в системщики" --- GoldED/W32 3.0.1-asa9 SR3 * Origin: Windows имеет всех, кто ее имеет (2:5026/45.13) — RU.COMPRESS From : Eugene Pazhitnov 2:5020/40.22 04 Dec 99 21:03:35 To : Denis Danchenko Subj : Кодиpование Гляну я на то, что пишет Denis Danchenko к Eugene Pazhitnov и ничего ему(ей) на это не отвечу, кpоме EP>> Так вот, не изобpетал ли я велосипед, и, может, есть какие-то более DD> Я не совсем точно понял про что ты, но очень сильно смахивает на коцаного DD> Хаффмана со статическим алфавитом. Соppи, тоpмознул. Внимательно вглядевшись, понял, что это он и есть :-) А почему коцаный? Самый что ни на есть статический Хаффман. С уважением, [NW SDK Vol.#14] [Домашний адрес - 2:5099/8.22] Женя. [Team Кодиpование] --- Дед-пpогpаммист, пишущий NLMы под нетваpь 3.00.Beta5+ * Origin: Tetris Hating Club (2:5020/40.22) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 04 Dec 99 22:25:00 To : Vladimir Semenjuk Subj : LZW * Crossposted in RU.COMPRESS Hello Vladimir! Saturday December 04 1999, Vladimir Semenjuk writes to All: VS> Может кто-нибудь знает подробности этой туманной истории. Откуда, VS> например, Барроуз в ней взялся? Логично предположить, что он и сообразил, как ЭТО использовать. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 04 Dec 99 22:27:03 To : Alex Lisenko Subj : Дайте информацию * Crossposted in RU.COMPRESS Hello Alex! Friday December 03 1999, Alex Lisenko writes to Vladimir Semenjuk: AL> 1) получаются одинаковые коды для нескольких символов. Как?? Ты ведь совершенно правильно собрался строить их по пути в дереве. Один аковые коды - одинаковые пути - один и тот же узел - один и тот же символ. AL> Какой AL> максимальной длинны (в битах) может получится новый код? Как и полагается, в соответствии с вероятностью символа. AL> 2) каким образом лучше организововать построение дерева. Че AL> использовать? Массивы, списки, двусвязные списки? Стек+очередь. В стек помещаешь исходные символы, в порядке частот, на верхушк е - минимальные частоты. В очередь с одной стороны вставляешь новые узлы, с дру гой стороны - берешь материал для комбинирования. Ес-но, из 4-х узлов - 2 на вершине стека и 2 в конце очереди, выбираешь 2 с минимальными частотами. Реальн о из конца очереди элементы лучше не выпихивать, а сохранять в них ссылки на де тей, чтоб потом при обратном проходе приписать им коды. AL> 3) каким образом лучше осуществлять перекодировку? Я коды AL> новые, например, держу в строках, а когда перекодируюю - накапливаю в AL> одной строке большое колво бит, потом отсекаю по 8 шт. Как лучше? Посмотри bits.c в zip и io.c в ar002. И то, и другое есть на кварте (анонсы i p robot в эхе видел?). Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 04 Dec 99 22:30:44 To : All Subj : Re: LZW From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Maxime&All ! VS> Эту странную ситуацию и, в особенности, поведение Уилера я вообще объяснить VS> не могу. Через 11 лет после открытия осознает его значимость (или они VS> осознают - он и Барроуз). И что? Опубликовано черт знает где. Патент им не VS> нужен. MZ> А по-моему, заявку на патент можно подавать не позднее года с момента MZ> первой публикации, если не вообще до. Как известно, первая публикация (в докладе SRC) была в 1994. Там написано о том, что алгоритм получился крутой и что его "... изобрел один из нас (Уилер) в 1983 году, когда работал в Bell Labs, тем не менее, он не был опубликован ранее. ..." (вот тут я не очень понимаю: Уилер в 83 только BWT придумал или весь алгоритм). C 1993 до 1994 или с 1994 до 1995 как раз и был год для подачи заявок. Раз уж осознали всю прелесть полученного результата, надо было патентовать. С уважением, Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 04 Dec 99 22:30:45 To : All Subj : Re: Дайте информацию From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Alex ! VS> CTW = Context Tree Weighting method знаю, а CW - нет. AL> Алгоритмы\доки\ссылки\лит-ра есть? Смотри http://ei1.ei.ele.tue.nl/~frans/ResearchCTW.html Там есть вообще все про CTW. Ты только не пугайся :) AL> Dynamic Marcov (DMC) DMC = Dynamic Markov Compression А про словарные алгоритмы ты слышал? Про LZ77, LZSS, LZW, например? Их значительно проще понять чем DMC и CTW. (Binary LZ - вообще ерунда.) VS> Расскажи вкратце что ты делаешь и в каком месте не получается. Как ты VS> вообще алгоритм Хаффмана себе представляешь? AL> Я узнавал из разных источников про данный алгоритм. Hу и вот вкрации. AL> Значит проходим первый раз файл и считаем freq символов. А потом начинаем AL> строить дерево: находим 2 символа с наименьшим freq, образуем новый узел (при AL> этом исключаем из списка поиска эти 2 символа и включаем новый узел с сумарной AL> freq), далее повторяем эти действия. Потом ппроходим дерево: вправо идем - 1чку AL> в уме, влево -нолик. Hаходим коды для каждого символа. Проходим второй раз файл AL> и перекодируем символы в новые последовательности бит. Вот. Пример: последовательность: "abcbabcaabdea" сортируем по убыванию частоты: a(5), b(4), c(2), d(1), e(1) 1 шаг: d + е -> u1. результат: a(5), b(4), c(2), u1(2=1+1) 2 шаг: c + u1 -> u2. результат: a(5), b(4), u2(4=2+2) 3 шаг: b + u2 -> u3. результат: u3(6=4+4), a(5) 4 шаг: u3+a -> u4. результат: u4(11=6+5) дерево Хаффмана: u4 / \ u3 a / \ b u2 / \ c u1 / \ d e сопоставим /-"0", \ -"1" получаем префиксные коды: a - {1} b - {00} c - {010} d - {0110} e - {0111} Если ты правильно поймешь этот алгоритм, то проблем не возникнет. (Тут им просто негде возникнуть.) С уважением, Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vaycheslav Isaev 2:5061/23.39 04 Dec 99 22:47:52 To : All Subj : Сжатие непрерывного цифрового потока Как поживаешь, All? Какие методы можете посоветовать для сжатия непрерывного цифрового потока? К тому же исходный сигнал не детерминирован не периодичен... С уважением, Vaycheslav --- * Origin: "Сахар песок" - смесь 1:1 (2:5061/23.39) — RU.COMPRESS From : Vaycheslav Isaev 2:5061/23.39 04 Dec 99 22:49:42 To : All Subj : 10bit>8bit Как поживаешь, All? Посоветуйте, пожалуйста, методы которыми можно упаковать 10 bit хотябы до 8 bit... Слышал, что вроде альфа-алгоритм, применяемый в ISDN телефонии удовлетворяет этому, но не могу найти его описание... Заранее благодарю! С уважением, Vaycheslav --- * Origin: "Сахар песок" - смесь 1:1 (2:5061/23.39) — RU.COMPRESS From : Denis Danchenko 2:5020/859.65 05 Dec 99 01:32:03 To : Eugene Pazhitnov Subj : Кодиpование It's message to you, Eugene! 04 Dec 99 21:03, Eugene Pazhitnov wrote to Denis Danchenko: EP>>> Так вот, не изобpетал ли я велосипед, и, может, есть какие-то EP>>> более DD>> Я не совсем точно понял про что ты, но очень сильно смахивает на DD>> коцаного Хаффмана со статическим алфавитом. EP> Соppи, тоpмознул. Внимательно вглядевшись, понял, что это он и есть EP> :-) А почему коцаный? Самый что ни на есть статический Хаффман. Теперь у меня крыша едет... я почему-то решил что должны быть literal/length & distance алфавиты. А это уже к DEFLATE относится. %-) Denis ... Brains using: -------------------- 35% --- :~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~( * Origin: ¦ Alhademic Group ¦ http://www.alhademic.com ¦ (2:5020/859.65) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 05 Dec 99 10:49:52 To : Yury Reshetov Subj : Re: BWT FAQ Пpиветствую, Yury! 04 Dec 99, Yury Reshetov писал к Vadim: V>> Теперь понятно, почему у тебя BWT давал такое слабое сжатие... V>> 8kb - это слишком маленький блок для него. Очень маленький. V>> К примеру, в ybs стоит по умолчанию 2Mb. V>> Замечу, что при хорошей сортировке скорость работы почти не V>> зависит от величины блока. YR> Когда фоpмиpуешь инфоpмацию по последнему столбцу, то маленький. Дык ежли YR> ее фоpмиpовать по втоpому, то и два кило будут эффективнее двух метpов по YR> последнему. Hа тех же восьми кило буфеpа сабж+MTF кpоет HА в тpи pаза по YR> pусским текстам. Тогда уж лучше по первому :) У нас была дискуссия года полтора(?) назад, в которой пришли к выводу, что такой способ в общем случае необратим. Был приведен пример (не помню, кем): 100100 и 100010, имеющие одинаковые вторые столбцы. V>> Я бы рад ответить на этот вопрос, но это действительно V>> зависит от данных. Hа текстах надо выделять столько, V>> сколько есть свободной памяти. Hа неоднородных данных - V>> рубить блок там, где начинаются данные, сильно отличающиеся от V>> текущих. YR> Каким макаpом их можно идентифициpовать? К примеру, по смене алафавита. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 05 Dec 99 11:16:09 To : Vladimir Semenjuk Subj : Re: LZW From: leob@mailcom.com (Leonid Broukhis) Vladimir Semenjuk wrote: >Как известно, первая публикация (в докладе SRC) была в 1994. Там написано о >том, что алгоритм получился крутой и что его "... изобрел один из нас >(Уилер) в 1983 году, когда работал в Bell Labs, тем не менее, он не был >опубликован ранее. ..." (вот тут я не очень понимаю: Уилер в 83 только BWT Официально опубликован, наверное, не был, но не верится мне, что эти двое так 11 лет и жили, и никому никогда не рассказывали. Если существуют свидетели того, что это было действительно придумано в 1983 году, то пытаться патентовать бессмысленно - опротестуют как common knowledge, т.к. найдутся свидетели. >придумал или весь алгоритм). C 1993 до 1994 или с 1994 до 1995 как раз и был >год для подачи заявок. Раз уж осознали всю прелесть полученного результата, >надо было патентовать. Если бы они все эти 11 лет молчали, то могли бы. А так - вряд ли. Да и что мы обсуждаем - неужели кто-то хочет, чтобы BTW был запатентован? Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 05 Dec 99 11:21:37 To : All Subj : Compressors Comparison Tests 5. [1/9] Приветствую, All! Hовый выпуск тестов. Добавлен тест на английском тексте и куча новых компрессоров (rk 1.02a1, eri 4.4, ppmn и другие). Hа www.shomonopoly.com/arctest обновление будет сделано позже, одновременно с графической версией тестов. ===================== Hачало - 1.txt ===================== ¦ English Text (condoyle.txt) 2,042,760 ======================================================== Compressor and options size compress extract ====================================================== * rk 1.01a01 mx2 477,984 3:29.63 3:35.94 PPM * rk 1.01a01 mx1 480,116 3:18.50 3:27.30 PPM * rkuc 1.04 o8 x 491,128 2:35.10 2:48.53 PPM rkuc 1.04 o16 x 492,076 3:03.15 3:19.00 PPM rkuc 1.04 o12 x 492,720 2:52.12 3:07.55 PPM * boa 0.58b m15 494,637 2:18.57 2:25.49 PPM * boa 0.58b m11 496,038 2:16.97 2:24.23 PPM rkive 1.92b mt2 497,126 5:55.70 5:17.41 LZP,PPM * boa 0.58b m7 501,542 2:07.57 2:14.89 PPM * ppmn 1.00a1 M:15 506,791 23.70 26.30 PPM ppmn 1.00a1 MT 506,889 32.18 34.27 PPM rkuc 1.04 o16 b x 507,476 4:25.93 4:28.47 PPM * ppmdd o6 m32 508,224 14.08 15.41 PPM ppmn 1.00a1 508,262 31.38 34.10 PPM * ppmdd o5 m16 510,270 11.43 12.82 PPM rkuc 1.04 o8 510,708 1:54.10 2:00.43 PPM rkuc 1.04 o8 b 512,128 2:20.66 2:27.45 PPM ppmn 1.00a1 O6 514,200 45.42 48.41 PPM acb 2.00 u 516,149 7:11.19 7:12.87 AC dst 0.9 mt 4 517,177 2:39.95 1:45.17 PPM dst 0.9 mt 517,294 1:52.12 1:45.22 PPM ba 0.99b -24-r 517,990 29.37 13.26 BWT+Ari ba 0.99b -24-m 517,990 30.60 13.27 BWT+Ari ba 0.99b -24-g 517,990 30.60 13.35 BWT+Ari rkuc 1.04 o16 518,568 2:21.98 2:30.80 PPM rkuc 1.04 o12 518,900 2:10.31 2:18.17 PPM rkive 1.92b mt1 519,359 2:56.38 2:25.10 LZP,PPM rkuc 1.04 o12 b 520,372 2:39.48 2:45.54 PPM * szip 1.10 b21 o0 522,165 42.68 10.35 BWT+Ari szip 1.10 b21 o12 522,517 29.48 17.22 ST+Ari szip 1.10 b21 o10 522,638 25.14 16.06 ST+Ari szip 1.10 b21 o8 523,460 20.30 14.80 ST+Ari acb 2.00 b 523,868 4:50.88 4:52.72 AC rkuc 1.04 o16 b 525,412 2:53.70 2:58.90 PPM ICT UC 1.0 526,968 22.22 15.79 ST+Ari rkuc 1.04 527,012 51.94 53.62 PPM szip 1.10 b21 o6 528,195 15.52 13.98 ST+Ari x1 0.95a am4l3 529,108 54.66 57.03 PPM * ppmdd 529,350 10.39 10.79 PPM 777 0.04b1 m5 mu16 md1024 529,491 2:08.48 2:23.67 LZ+PPM x1 0.95a am4 531,515 51.42 54.33 PPM eri 4.4fre -m5 532,731 1:17.84 12.46 ST+PPM eri 4.4fre -m4 532,735 1:05.67 12.42 ST+PPM eri 4.4fre -m3 533,084 59.37 12.17 ST+PPM ufa 0.04b1 m5 535,661 2:04.30 2:19.15 LZ+PPM * bwc/PGCC 0.99 m2m 538,180 19.03 8.90 BWT+Ari acb 2.00 B 538,318 3:23.24 3:25.03 AC eri 4.4fre -m2 539,977 54.01 11.15 ST+PPM eri 4.4fre -m1 546,490 51.88 10.92 ST+PPM szip 1.10 b21 o4 559,257 8.25 13.48 ST+Ari * imp 1.10 -2 u1000 561,196 16.57 4.02 BWT+Huf bwc/PGCC 0.99 m900k 562,124 17.80 8.91 BWT+Ari bwc/PGCC 0.99 567,690 17.64 8.96 BWT+Ari bzip2/PGCC 0.90 -9 574,017 21.21 6.14 BWT+Huf bzip2/w32 0.95b -9 574,017 29.88 7.27 BWT+Huf exp1 1. 574,094 18.48 6.28 BWT+Huf arhangel 1.40a1 -2-mc8192 575,245 35.41 36.32 PPM arhangel 1.40a1 -2 576,337 38.73 39.77 PPM ha 0.999c a2 576,338 46.52 45.49 PPM arhangel 1.34 -2-mm6 576,340 40.87 41.88 PPM arhangel 1.34 -2 576,340 41.07 41.85 PPM bwc/PGCC 0.99 m600k 577,290 17.18 8.99 BWT+Ari arhangel 1.34 -2-mc12000 580,099 42.63 44.22 PPM bzip2/PGCC 0.90 -6 587,288 20.34 6.10 BWT+Huf bzip2/w32 0.95b -6 587,288 28.99 7.27 BWT+Huf rk 1.01a01 mf3 595,800 1:53.25 49.29 ROLZ rkive 1.92b mb3 598,322 1:37.08 58.92 LZP,PPM rkive 1.92b mf3 602,368 1:03.80 25.83 ROLZ arhangel 1.34 -2-mo5 603,052 56.26 57.48 PPM jar32 1.02d m4 610,271 19.97 4.35 LZ+Huf jar32 1.02d m3 610,318 19.97 4.46 LZ+Huf rk 1.01a01 mf2 611,828 1:06.61 39.11 ROLZ * cabarc 1.00 LZX:21 614,991 50.77 1.00 LZ+Huf 777 0.04b1 m2 618,424 3:53.64 1:32.52 LZ+PPM 777 0.04b1 m9 618,424 3:54.19 1:33.56 LZ+PPM arjz 0.50(md2m,mp9) + dict 619,815 1:18.32 2.86 LZ+Huf bix 1.00b6 m1 620,692 56.38 1.54 LZ+Huf bix 1.00b7 m1 620,692 56.68 1.55 LZ+Huf arjz 0.50(md2m) + dict 624,417 49.45 2.75 LZ+Huf arjz 0.50(md2m) + dict(-e) 624,417 49.77 2.81 LZ+Huf hap 3.00 629,697 23.01 28.08 PPM rkive 1.92b mb1 638,726 58.57 49.59 LZP,PPM ufa 0.04b1 m2 642,206 2:18.83 19.92 LZ+PPM uharc 0.2b m3 646,232 2:00.44 14.10 LZ+PPM * cabarc 1.00 LZX:18 647,333 45.16 0.94 LZ+Huf lzds2 s1024 m5 652,032 42.62 3.26 LZ+Ari dst 0.9 mb 4 653,210 8:41.41 1:14.26 LZ+DHuf lzds2 s1024 m4 654,497 31.08 3.37 LZ+Ari rk 1.01a01 654,952 21.97 20.08 ROLZ rar/win 2.60 m5 md1024 655,987 1:01.22 2.10 LZ+Huf lz (kabanov) 6 661,500 1:44.56 3.20 LZ+Huf lzds2 s1024 m3 662,390 21.01 3.36 LZ+Ari rk 1.01a01 mf1 662,940 20.24 19.59 ROLZ arjz 0.50 mp9 md2m 664,006 3:48.59 1.60 LZ+Huf lz (kabanov) 5 664,788 1:25.80 3.19 LZ+Huf rkive 1.92b mf1 665,657 27.79 22.76 ROLZ arhangel 1.34 -2-mo6 665,788 1:19.07 1:21.45 PPM xtreme t6 666,019 57.92 3.64 LZ+Huf imp 1.10 -1 m3 u1000 667,465 29.16 1.38 LZ+Huf lzds2 s1024 m2 668,561 17.22 3.36 LZ+Ari lzds2 s512 m3 669,953 20.39 3.41 LZ+Ari imp 1.10 -1 u1000 672,465 19.04 1.38 LZ+Huf lz (kabanov) 4 675,902 57.37 3.25 LZ+Huf rar/win 2.60 m5 683,041 42.63 2.10 LZ+Huf lzds2 s1024 m1 683,175 13.58 3.48 LZ+Ari rar/win 2.60 m4 683,767 36.75 2.10 LZ+Huf rar/win 2.60 m3 687,004 29.15 2.10 LZ+Huf arjz 0.50 md2m 690,440 1:03.92 1.77 LZ+Huf arjz 0.50 mp9 692,748 1:22.34 1.33 LZ+Huf arjz 0.50 mp8 693,057 1:18.93 1.44 LZ+Huf arhangel 1.40a1 -1-mt 699,665 16.81 7.24 LZ+Ari lz (kabanov) 3 701,192 24.26 3.30 LZ+Huf arjz 0.50 702,515 48.13 1.33 LZ+Huf uharc 0.2b mm- 703,740 1:22.59 15.64 LZ+PPM uharc 0.2b 703,740 1:32.78 15.63 LZ+PPM ace32 1.2b m5 717,588 50.14 2.48 LZ+Huf ace32 1.02a m5 717,588 50.34 1.99 LZ+Huf lz (kabanov) 2 722,694 16.89 3.36 LZ+Huf lzds2 s64 m3 726,252 15.72 3.80 LZ+Ari arjz 0.50 mp6 726,985 27.84 1.43 LZ+Huf * cabarc 1.00 LZX:15 730,849 26.74 0.89 LZ+Huf dst 0.9 mb 730,954 46.98 21.29 LZ+DHuf 7zip 2.01 mx 736,643 40.21 1.66 LZ+Huf 7zip 2.01 737,297 26.67 1.60 LZ+Huf uc 2.3.05 tt 744,404 5:51.32 3.05 LZ+Huf ace32 1.02a m4 745,144 26.02 2.15 LZ+Huf ace32 1.2b m4 745,144 26.24 2.48 LZ+Huf uharc 0.2b m1 752,640 56.05 17.70 LZ+PPM arjz 0.50 mp5 753,915 18.77 1.44 LZ+Huf lz (kabanov) 1 754,558 12.62 3.64 LZ+Huf uc 2.3.05 tn 765,828 4:19.46 3.05 LZ+Huf * pkzip 2.50 max 767,117 10.02 1.11 LZ+Huf arhangel 1.34 -1 768,472 25.34 7.73 LZ+Ari arhangel 1.40a1 -1 768,841 24.04 6.31 LZ+Ari ha 0.999c a1 769,327 30.82 9.36 LZ+Ari pkzip 2.04g -ex 770,579 15.67 1.14 LZ+Huf * pkzip 2.50 772,644 8.29 1.10 LZ+Huf esp 1.92 774,260 10.77 1.00 LZ+Huf pkzip 2.04g 780,639 9.80 1.19 LZ+Huf ===================== Конец - 1.txt ===================== Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 05 Dec 99 11:23:53 To : All Subj : Compressors Comparison Tests 5. [2/9] ===================== Hачало - 2.txt ===================== ¦ Russian Text (stand.txt) 1,639,139 ======================================================== Compressor and options size compress extract ====================================================== * rkuc 1.04 o12 x 439,904 2:12.58 2:23.79 PPM rkuc 1.04 o16 x 439,996 2:19.16 2:32.65 PPM * rkuc 1.04 o8 x 440,164 2:01.10 2:13.74 PPM rk 1.01a01 mx2 ft 448,200 5:52.53 5:56.09 PPM boa 0.58b -m15 448,497 2:09.63 2:14.74 PPM * rkuc 1.04 o8 454,028 1:30.53 1:36.62 PPM rkuc 1.04 o12 456,324 1:41.24 1:46.40 PPM * ppmn 1.00a1 MT 457,074 32.45 34.60 PPM rkuc 1.04 o16 457,372 1:49.65 1:57.18 PPM * ppmdd o6 m32 457,498 14.35 15.35 PPM rkive 1.92a -mt2 457,840 6:02.40 5:27.58 LZP,PPM ppmn 1.00a1 M:15 458,622 23.71 26.30 PPM * ppmdd o5 m16 459,979 11.44 12.81 PPM ppmn 1.00a1 461,444 32.38 34.93 PPM boa 0.58b -m7 462,315 1:59.14 2:03.59 PPM * ybs' -x 463,442 15.94 9.10 BWT+Ari ba 0.99b -20-m 465,585 22.90 11.33 BWT+Ari ba 0.99b -20-r-g 465,619 21.70 11.28 BWT+Ari ba 0.99b -20-g 465,619 22.67 11.35 BWT+Ari ppmn 1.00a1 O6 465,832 40.70 43.35 PPM acb 2.00 u 466,157 5:34.05 5:35.37 AC * ybs' -r -k- 466,551 13.72 7.58 BWT+Ari ybs' -r 466,551 14.44 7.58 BWT+Ari ba 0.99b -20-r 468,567 22.38 11.83 BWT+Ari ba 0.99b -20 468,567 23.32 11.82 BWT+Ari ba 0.99b -20-z 468,567 24.88 11.82 BWT+Ari szip 1.10 b19 o0 469,201 29.16 8.53 BWT+Ari szip 1.10 b19 o12 469,364 24.70 14.58 ST+Ari ybs (non public) 469,441 14.39 7.58 BWT+Ari szip 1.10 b19 o10 469,567 20.74 13.31 ST+Ari rkive 1.92a -mt1 469,831 2:35.55 2:10.94 LZP,PPM szip 1.05Xf b19 o0 470,266 29.70 9.90 BWT+Ari szip 1.05Xf b19 o12 470,351 25.41 15.95 ST+Ari szip 1.10 b19 o8 470,853 16.95 12.16 ST+Ari rk 1.01a01 mx2 472,316 5:40.70 5:42.58 PPM ict UC 1.0 472,556 18.53 12.81 ST+Ari acb 2.00 b 472,687 3:39.15 3:39.15 AC rkive 1.4 -mt 473,052 1:24.04 1:12.88 LZP,PPM x1 0.95a am4l3 474,027 52.40 54.93 PPM * ppmdd 474,216 9.36 10.28 PPM ba 0.99b -20-p 475,899 23.39 11.84 BWT+Ari eri 4.4fre -m5 476,034 1:05.99 10.42 ST+PPM eri 4.4fre -m4 476,035 55.11 10.38 ST+PPM szip 1.10 b19 o6 476,240 13.15 11.50 ST+Ari eri 4.4fre -m3 476,324 49.58 10.27 ST+PPM rkuc 1.04 477,092 45.46 47.40 PPM rkuc 1.04 477,092 47.72 49.36 PPM dst 0.9 mt 4 477,369 2:19.66 1:29.88 LZ+PPM dst 0.9 mt 477,464 1:33.66 1:29.93 LZ+PPM rk 1.01a01 mx1 ft 477,756 5:33.49 5:37.22 PPM * bwc/PGCC 0.99 m2m 479,162 14.72 7.44 BWT+Ari x1 0.95a am4 482,141 48.77 51.63 PPM eri 4.4fre -m2 482,521 44.63 9.22 ST+PPM 777 0.03b3 md1024 m5 mu16 483,261 1:47.38 2:05.12 LZ+PPM 777 0.04b1 m5 mu16 md1024 483,261 1:48.13 2:00.17 LZ+PPM rk 1.01a01 mx3 M16 485,416 5:20.47 5:29.56 PPM eri 4.4fre -m1 486,572 42.98 9.17 ST+PPM ufa 0.04b1 m5 (777) 490,761 1:44.85 1:56.78 LZ+PPM ba 0.99b 494,082 21.64 12.25 BWT+Ari szip 1.10 b19 o4 501,888 7.21 11.23 ST+Ari rk 1.01a01 mx1 503,508 5:10.48 5:16.21 PPM bwc/PGCC 0.99 m900k 503,556 13.92 7.58 BWT+Ari * imp 0.91 -2 -u1000 506,495 11.70 3.30 BWT+Huf imp 1.00 -2 u1000 506,524 11.61 3.31 BWT+Huf imp 1.10 -2 u1000 506,524 11.67 3.30 BWT+Huf bzip2/PGCC 0.90 -9 507,828 17.43 5.16 BWT+Huf bzip2/Watcom -9 507,828 20.24 6.16 BWT+Huf bzip2/w32 0.90 -9 507,828 24.42 6.11 BWT+Huf bzip2/w32 0.95b -9 507,828 24.47 6.17 BWT+Huf bzip2 0.1pl2 -9 507,828 34.59 10.50 BWT+Huf exp1 1. 507,901 15.29 5.17 BWT+Huf bwc/PGCC 0.99 m600k 519,470 13.65 7.61 BWT+Ari bzip2/PGCC 0.90 -6 523,162 16.68 5.15 BWT+Huf bzip2/w32 0.95b -6 523,162 23.60 6.17 BWT+Huf bzip2/w32 0.90 -6 523,162 23.65 6.16 BWT+Huf arhangel 1.40a1 -2-mc8192 536,000 33.72 34.84 PPM arhangel 1.40a1 -2 538,770 36.85 38.16 PPM ha a2 0.999c 538,771 44.49 44.00 PPM 777 0.04b1 m2 546,020 3:08.92 1:30.75 LZ+PPM * cabarc 1.00 LZX:21 546,392 38.77 0.77 LZ+Huf rk 1.01a01 mf3 547,812 1:23.22 43.57 ROLZ bix 1.00b7 m1 549,580 44.18 1.32 LZ+Huf rkive 1.92b mf3 560,614 51.45 24.10 LZP,PPM arjz'0.50(md2m,mp9),dict 562,467 55.45 2.42 LZ+Huf rkive 1.4 562,529 1:07.83 34.71 LZP,PPM ufa 0.04b1 m2 562,558 1:39.36 17.41 LZ+PPM arjz'0.50(md2m,mp9),dict(-e) 562,704 53.95 2.42 LZ+Huf uharc 0.2b m3 564,337 1:34.10 12.04 LZ+PPM arjz'0.50(md2m) + dict 565,400 40.48 2.42 LZ+Huf arjz'0.50(md2m) + dict(-e) 565,768 38.70 2.42 LZ+Huf arhangel 1.29b -2-mo5 567,454 55.10 58.23 PPM arhangel 1.32 -2-mo5 567,454 58.34 1:00.47 PPM dst 0.9 mb 4 570,450 5:20.71 50.39 LZ+DHuf dst 0.9 me 4 570,454 5:27.31 55.11 LZ+DHuf dst 0.9 mg 4 570,454 5:27.48 55.06 LZ+DHuf lzds2' s1024 m5 571,368 29.65 2.93 LZ+Ari lzds2' s1024 m4 572,551 22.16 2.82 LZ+Ari rk 1.01a01 mf2 573,464 49.18 34.32 ROLZ rar/win 2.60 m5 md1024 574,649 41.87 1.71 LZ+Huf rkive 1.92a 574,921 57.12 47.23 LZP,PPM lzds2' s1024 m3 576,733 16.34 2.81 LZ+Ari lz (kabanov) 6 582,554 48.62 2.76 LZ+Huf lz (kabanov) 5 583,512 44.10 2.81 LZ+Huf imp 1.00 -1 m3 u1000 583,538 20.07 1.17 LZ+Huf imp 1.10 -1 m3 u1000 583,538 20.36 1.28 LZ+Huf arjz'0.50 mp9 md2m 583,626 3:28.40 1.39 LZ+Huf lzds2' s1024 m2 584,805 13.09 2.86 LZ+Ari xtreme t6 586,485 31.41 3.20 LZ+Huf imp 0.91 -1 -u1000 588,715 13.29 1.04 LZ+Huf imp 1.10 -1 u1000 588,715 13.47 1.11 LZ+Huf lz (kabanov) 4 590,886 33.94 2.70 LZ+Huf lzds2' s1024 m1 594,572 11.06 2.98 LZ+Ari rar/win 2.60 m5 603,381 31.63 1.99 LZ+Huf rar/win 2.60 m4 604,258 27.83 1.77 LZ+Huf rar/win 2.60 m3 606,723 23.05 1.77 LZ+Huf hap 3.00 606,859 21.86 27.85 PPM rk 1.01a01 608,248 19.32 17.77 ROLZ arjz'0.50 mp9 610,804 1:28.44 1.16 LZ+Huf arjz'0.50 mp8 611,331 1:22.39 1.16 LZ+Huf uharc 0.2b mm- 611,915 1:09.96 13.47 LZ+PPM uharc 0.2b 611,915 1:18.65 13.47 LZ+PPM arjz'0.50 md2m 612,729 58.15 1.38 LZ+Huf lz (kabanov) 3 617,890 16.44 2.91 LZ+Huf rkive 1.92b mf1 621,686 26.89 22.52 LZP,PPM jar32 1.01d -m4 622,653 35.57 3.07 LZ+Huf arjz'0.50 623,432 47.08 1.16 LZ+Huf jar32 1.01b3 -m4 623,803 33.84 3.02 LZ+Huf dst 0.9 mb 630,043 39.94 18.00 LZ+DHuf dst 0.9 me 630,047 44.83 21.57 LZ+DHuf ace 1.0b -m5 633,563 41.41 2.58 LZ+Huf ace32 1.2b -m5 633,585 40.87 2.25 LZ+Huf lz (kabanov) 2 639,102 12.48 3.09 LZ+Huf arjz'0.50 mp6 651,241 24.86 1.17 LZ+Huf uharc 0.2b m1 654,620 45.87 15.12 LZ+PPM ace32 1.2b -m4 655,881 22.52 2.31 LZ+Huf cabarc 1.00 LZX:15 657,206 20.71 0.77 LZ+Huf rar 2.50 m5 658,074 29.37 1.47 LZ+Huf rar 2.03 m5 658,074 29.75 1.43 LZ+Huf rar 2.50 m4 658,240 28.37 1.43 LZ+Huf rar 2.02 -m4 658,240 28.51 1.48 LZ+Huf 7zip 2.00b2 662,078 21.52 2.37 LZ+Huf 7zip 2.00b2 mx 662,105 32.12 2.32 LZ+Huf uc 2.3.05 664,658 23.73 1.87 LZ+Huf lz (kabanov) 1 668,876 10.22 3.36 LZ+Huf arjz'0.50 mp5 679,220 16.12 1.28 LZ+Huf arhangel 1.32 -1 684,078 20.37 8.82 LZ+Ari arhangel 1.40a1 -1 684,415 16.91 5.63 LZ+Ari ha a1 0.999c 684,868 22.90 8.13 LZ+Ari pkzip 2.50 max 686,971 10.07 0.94 LZ+Huf pkzip 2.04g -ex 688,850 12.71 1.03 LZ+Huf pkzip 2.50 691,821 7.43 0.94 LZ+Huf pkzip 2.04g 697,853 8.35 1.15 LZ+Huf arhangel 1.29b -1 715,735 15.17 9.54 LZ+Ari ufa 0.04b1 m2 mq 733,309 37.68 32.95 LZ+PPM arhangel 1.40a1 -1-mt 786,444 1:14.41 7.80 LZ+Ari ===================== Конец - 2.txt ===================== Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 05 Dec 99 11:24:12 To : All Subj : Compressors Comparison Tests 5. [3/9] ===================== Hачало - 3.txt ===================== ¦ C-sources (Watcom 10.0) 1,890,501 ======================================================== Compressor and options size compress extract ====================================================== * rkuc 1.04 o16 x 224,528 2:17.18 2:31.88 PPM * rkuc 1.04 o12 x 225,020 2:02.38 2:13.68 PPM rk 1.01a01 mx2 225,156 2:32.80 2:29.93 PPM * rkuc 1.04 o8 x 229,744 1:48.47 1:57.97 PPM rk 1.01a01 mx2 ft 231,912 2:42.43 2:48.86 PPM rk 1.01a01 mx1 233,120 2:27.57 2:26.91 PPM acb 2.00 u 233,189 2:26.16 2:27.20 AC * acb 2.00 b 235,985 1:40.90 1:40.90 AC * boa 0.58b -m15 238,395 1:06.35 1:11.30 PPM rkuc 1.04 o16 238,728 1:37.21 1:41.96 PPM rkive 1.92a mt2 239,429 3:05.76 2:44.72 LZP,PPM rkuc 1.04 o16 b 240,580 2:04.13 2:06.45 PPM acb 2.00 B 241,635 1:12.83 1:13.05 AC rkuc 1.04 o12 242,664 1:24.45 1:27.80 PPM * boa 0.58b -m7 247,928 1:04.92 1:10.75 PPM rkive 1.92a mt1 249,437 1:21.56 1:08.33 LZP,PPM * ba 0.99b -20-r 251,447 31.99 7.76 BWT+Ari ba 0.99b -20 251,447 33.02 7.80 BWT+Ari ba 0.99b -20-m 251,447 33.17 7.76 BWT+Ari ba 0.99b -20-g 251,447 33.18 7.76 BWT+Ari ba 0.99b -20-z 251,447 34.79 7.79 BWT+Ari ba 0.99b -20-j 251,816 33.18 7.89 BWT+Ari rkive 1.4 -mt 251,816 44.10 36.08 LZP,PPM ba 0.99b -20-f 252,009 33.41 7.75 BWT+Ari dst 0.9 mt 4 252,183 2:02.05 52.04 LZ+PPM dst 0.9 me 4 252,183 2:04.08 51.93 LZ+PPM ba 0.99b -20-p 252,658 33.11 7.75 BWT+Ari * szip 1.05Xf b19 o0 253,508 48.89 7.48 BWT+Ari * bwc/PGCC 0.99 m2m 253,665 13.46 5.63 BWT+Ari rkive 1.92a mb3 254,060 54.11 36.03 LZP,PPM ppmn 1.00a1 O7 254,244 25.63 28.23 PPM dst 0.9 mt 254,542 56.22 51.49 LZ+PPM dst 0.9 mg 254,542 58.25 51.54 LZ+PPM rk 1.01a01 mf3 255,040 1:06.50 37.02 ROLZ * ybs' 255,086 12.72 5.70 BWT+Ari rk 1.01a01 mf2 255,284 42.96 25.47 ROLZ eri 4.4fre -m5 256,157 1:07.58 8.89 ST+PPM eri 4.4fre -m4 256,158 1:02.14 8.89 ST+PPM szip 1.10 b19 o0 256,312 48.41 6.11 BWT+Ari eri 4.4fre -m3 256,314 59.25 8.83 ST+PPM rkive 1.92b mf3 256,928 34.31 16.67 LZP,PPM rkive 1.4 258,427 33.83 17.57 LZP,PPM eri 4.4fre -m2 260,045 56.57 8.27 ST+PPM rkuc 1.04 o8 260,092 1:14.26 1:17.29 PPM ppmn 1.00a1 O6 262,020 23.65 26.30 PPM eri 4.4fre -m1 262,556 55.82 8.11 ST+PPM 777 0.04b1 m2 262,968 4:26.36 49.22 LZ+PPM 777 0.04b1 m9 262,968 4:26.53 49.88 LZ+PPM szip 1.05Xf b19 o12 263,401 23.10 13.86 ST+Ari ict UC 1.0 265,614 15.45 9.95 ST+Ari szip 1.05Xf b19 o10 266,176 19.30 12.76 ST+Ari * ppmdd o6 m32 266,814 8.97 10.07 PPM szip 1.10 b19 o12 267,055 22.24 12.39 ST+Ari szip 1.10 b19 o10 269,885 18.54 11.17 ST+Ari * jar32 1.02d -m4 270,108 21.42 3.24 LZ+Huf szip 1.05Xe b19 o8 270,141 15.44 10.93 ST+Ari szip 1.05Xf b19 o8 270,150 15.67 11.66 ST+Ari jar32 1.01b3 -m4 270,235 20.65 3.18 LZ+Huf jar32 1.01b3 -m3 270,487 20.60 3.24 LZ+Huf * cabarc 1.00 LZX:21 271,720 40.18 0.77 LZ+Huf szip 1.05Xe b19 o7 273,596 13.62 10.49 ST+Ari ppmn 1.00a1 M:15 273,851 17.00 19.47 PPM ppmn 1.00a1 273,875 17.10 19.36 PPM szip 1.10 b19 o8 274,069 15.13 10.18 ST+Ari arjz'0.50(md2m,mp9),dict(-e) 274,248 22.86 2.15 LZ+Huf arjz'0.50(md2m) + dict(-e) 275,580 17.60 2.20 LZ+Huf arjz'0.50(md2m,mp9),dict 275,747 28.50 2.31 LZ+Huf rkive 1.92a 275,952 24.27 19.45 LZP,PPM bwc/PGCC 0.99 m900k 276,488 12.38 5.65 BWT+Ari ufa 0.04b1 m2 277,275 1:54.24 8.84 LZ+PPM arjz'0.50(md2m) + dict 278,242 20.19 2.26 LZ+Huf ba 0.99b 278,723 27.53 7.91 BWT+Ari bix 1.00b7 m1 279,140 31.47 1.16 LZ+Huf szip 1.05Xf b19 o6 280,453 12.21 10.78 ST+Ari bzip2/PGCC 0.90 -9 280,776 17.28 4.28 BWT+Huf bzip2/Watcom -9 280,776 21.39 5.33 BWT+Huf bzip2/w32 0.95b -9 280,776 25.93 4.96 BWT+Huf bzip2/w32 0.90 -9 280,776 26.07 4.90 BWT+Huf bzip2 0.1pl2 -9 280,776 35.97 9.18 BWT+Huf imp 0.91 -2 -u1000 280,824 13.68 2.97 BWT+Huf imp 1.10 -2 u1000 280,847 14.04 3.09 BWT+Huf imp 1.00 -2 u1000 280,847 14.16 3.03 BWT+Huf exp1 1. 280,847 15.78 4.45 BWT+Huf * ppmdd o5 m16 280,971 8.19 9.19 PPM rk 1.01a01 282,232 12.68 10.84 ROLZ uharc 0.2b m3 282,467 1:24.31 10.34 LZ+PPM szip 1.10 b19 o6 284,201 11.55 9.25 ST+Ari rkive 1.90b mf 284,723 41.64 34.82 LZP,PPM arjz'0.50 mp9 md2m 286,560 1:04.19 1.05 LZ+Huf rar/win 2.60 m5 md1024 286,696 31.36 1.55 LZ+Huf bwc/PGCC 0.99 m600k 289,074 12.11 5.63 BWT+Ari lzds2' s1024 m5 289,147 27.06 2.04 LZ+Ari lzds2' s1024 m4 289,579 17.33 1.99 LZ+Ari szip 1.05Xe b19 o5 290,670 10.33 9.62 ST+Ari rk 1.01a01 mf1 291,572 12.10 11.29 ROLZ dst 0.9 mb 4 291,953 3:37.26 26.13 LZ+DHuf lzds2' s1024 m3 292,112 12.00 1.98 LZ+Ari lzds2' s1024 m2 292,423 10.17 2.04 LZ+Ari lz (kabanov) 6 292,780 29.69 1.99 LZ+Huf bzip2/PGCC 0.90 -6 293,205 16.21 4.27 BWT+Huf bzip2/w32 0.95b -6 293,205 24.36 4.90 BWT+Huf bzip2/w32 0.90 -6 293,205 24.47 4.84 BWT+Huf lz (kabanov) 5 293,630 23.70 2.10 LZ+Huf arjz'0.50 md2m 293,650 18.98 1.05 LZ+Huf rkive 1.92b mf1 293,884 14.28 11.57 LZP,PPM imp 1.00 -1 m3 u1000 296,429 22.72 0.94 LZ+Huf imp 1.10 -1 m3 u1000 296,429 22.78 1.05 LZ+Huf lzds2' s1024 m1 297,894 8.74 2.15 LZ+Ari xtreme t6 298,941 24.02 2.25 LZ+Huf uharc 0.2b mm- 299,429 37.51 10.67 LZ+PPM uharc 0.2b 299,429 47.46 10.72 LZ+PPM 777 0.04b1 m5 mu16 md1024 300,803 1:55.39 2:09.63 LZ+PPM ufa 0.04b1 m5 303,651 1:50.73 2:04.84 LZ+PPM lz (kabanov) 4 304,746 17.55 2.21 LZ+Huf * ppmdd 305,350 7.48 8.59 PPM * szip 1.05Xf b19 o4 307,877 5.88 10.06 ST+Ari * szip 1.10 b19 o4 309,516 5.34 8.53 ST+Ari rar/win 2.60 m5 310,751 24.37 1.49 LZ+Huf rar/win 2.60 m4 311,095 20.02 1.55 LZ+Huf rkuc 1.04 311,124 43.59 45.08 PPM imp 0.91 -1 -u1000 311,204 14.66 1.05 LZ+Huf imp 1.10 -1 u1000 311,211 14.91 0.99 LZ+Huf rar/win 2.60 m3 313,139 15.23 1.49 LZ+Huf x1 0.95a am4l3 314,422 42.24 46.20 PPM arjz'0.50 mp9 314,862 32.51 0.95 LZ+Huf arjz'0.50 mp8 315,253 25.48 0.99 LZ+Huf dst 0.9 mb 315,704 21.24 12.17 LZ+DHuf arjz'0.50 318,452 14.84 1.06 LZ+Huf x1 0.95a am4 318,717 38.45 41.86 PPM ace32 1.2b m5 319,263 18.54 1.93 LZ+Huf uharc 0.2b m1 326,012 33.93 11.27 LZ+PPM arjz'0.50 mp6 326,483 10.51 1.00 LZ+Huf lz (kabanov) 3 328,566 9.18 2.21 LZ+Huf ace32 1.2b m4 330,711 11.61 2.09 LZ+Huf arjz'0.50 mp5 337,547 8.37 0.89 LZ+Huf lz (kabanov) 2 345,966 7.37 2.26 LZ+Huf arhangel 1.40a1 -2-mc12000 351,403 30.31 31.78 PPM rar 2.03 m5 355,553 16.55 1.04 LZ+Huf rar 2.50 m5 355,553 17.91 1.08 LZ+Huf arhangel 1.40a1 -2 356,187 30.70 31.81 PPM ha a2 0.999c 356,303 37.07 37.07 PPM rar 2.50 m4 356,350 14.82 1.15 LZ+Huf uc 2.3.05 358,932 15.60 1.43 LZ+Huf arhangel 1.40a1 -2-mc8192 363,441 29.45 30.75 PPM arhangel 1.40a1 -1-mt 367,615 14.65 4.46 LZ+Ari * cabarc 1.00 LZX:15 374,486 24.22 0.66 LZ+Huf lz (kabanov) 1 375,332 6.16 2.37 LZ+Huf 7zip 2.00b2 mx 377,204 42.41 1.66 LZ+Huf ufa 0.04b1 m2 mq 378,284 23.23 14.89 LZ+PPM 7zip 2.00 379,257 20.03 1.60 LZ+Huf 7zip 2.00b2 379,440 19.74 1.66 LZ+Huf arhangel 1.40a1 -1 387,444 14.98 3.55 LZ+Ari ha a1 0.999c 387,968 19.83 5.77 LZ+Ari * pkzip 2.50 max 389,629 4.96 0.72 LZ+Huf pkzip 2.04g -ex 391,944 9.44 0.96 LZ+Huf * pkzip 2.50 392,454 3.63 0.78 LZ+Huf hap 3.00 398,121 20.21 26.14 PPM pkzip 2.04g 399,206 5.01 0.90 LZ+Huf arhangel 1.29b -1 417,954 12.72 5.87 LZ+Ari ===================== Конец - 3.txt ===================== Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50)
Предыдущий блок Следующий блок Вернуться в индекс