[an error occurred while processing this directive][an error occurred while processing this directive][an error occurred while processing this directive]
— 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)
[an error occurred while processing this directive][an error occurred while processing this directive]