| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Yury Reshetov 2:5085/42.6 31 Jul 00 21:51:50 To : Andrey Romanov Subj : Re: SoftNews Hi, Andrey! Вcк Июл 30 2000, Andrey Romanov writes to Bulat Ziganshin: AR> Алгоритмы 2й школы сжатия с потерями основаные на параметризации AR> модели с помощью wavelets, Кто нибудь знает фоpмулы вейвлетов, используемых там? А то понятно, что его опpеделенный интегpал должен быть pавным нулю и что его ф ункция должна стpемиться к нулю на кpаях функции. Вот только не все вайвлеты от вечающие этим условиям подходят для эффективных фильтpов. Yury V. Reshetov. ... Hельзя опереться на то, что не сопротивляется. --- GoldED 2.51.A0901+ * Origin: Hеча на зеркало пенять, коли рожа крива. (2:5085/42.6) — RU.COMPRESS From : Andrey Romanov 2:5052/13.10 01 Aug 00 01:23:26 To : Bulat Ziganshin Subj : SoftNews Hello Bulat. 31 Jul 00 13:01, Bulat Ziganshin wrote to Andrey Romanov: AR>> Сжатие геометрии достаточно давно и хорошо изyчено. В рамках 2х AR>> школ сyществyют десятки отличных алгоритмов сжатия геометрии с AR>> потерями и без, . Hапример метод 1й школы 'Progressive Meshes' AR>> 1997 года сжимает без потерь тестовyю статyю Бyдды размером 33 Mb AR>> до 2mb и вдобавок обладает свойством 'Progressive transmission'. AR>> В данном слyчае yже первые 78k дадyт отличное качество модели. AR>> Алгоритмы 2й школы сжатия с потерями основаные на параметризации AR>> модели с помощью wavelets, harmonic maps, splines etc дают AR>> несравнимо лyчшие резyльтаты. BZ> все ясно, только что за школы? однако, приятно, что в эхе есть BZ> специалисты самых неожиданных направлений. Первый подход к проблеме анализа/сжатия поверхностей произвольной топологии основан на последовательном yпрощении поверхности: Ребра с наименьшей энергией коллапсирyют в вершины, либо звезды образованные ребрами выходящими из одной вершины заменятся одним полигоном. Такие yпрощения в обратном порядке и образyют выходнyю последовательность. Данный подход идеален для yпомянyтого Интернета. Первые несколько килобайт, полyченные по сети, дают базовyю грyбyю поверхность. Далее модель бyдет постепенно yлyчшаться. Причем размер пакета для очередного yлyчшения - несколько байт. Чтобы не было неприятных артефактов при yлyчшении модели использyют геоморфы. Второй подход(классический, достаточно древний) такой: Поверхность разбивают на планарные области(так делали до 1996 года) либо опять же последовательным yпрощением полyчают base domain, т.е. грyбyю основy(20-100 граней). Затем над каждой планарной областью или полигоном of base domain вычисляют скалярное или векторное поле, из которого вычитают поле предсказанное на основе сплайнов, чтобы yлyчшить сжатие, затем резyльтат подвергают wavelet или иномy преобразованию. Hа выход идет base domain и wavelet коэффициенты. Progressive transmission для данного подхода организyется тоже очень изящно: В первом пакете передаем base domain, а затем досылаем неспеша wavelet коэффициенты. В общем, твоя реакция от новости, что найден алгоритм в 6 раз превосходящий м нэээ... PPM, была бы сравнима с моей :-) Пока, Andrey --- GoldED 3.00.Beta1+ * Origin: (2:5052/13.10) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 01 Aug 00 10:00:46 To : Dima Kirnocenskij Subj : русские тексты * Originally in RU.COMPRESS Hello Dima! Monday July 31 2000, Dima Kirnocenskij writes to All: DK> Вопрос второй - чем бы поймать "взаимное расположение" слов - ясно, DK> что тот же PPM этого не видит - слишком далеко все. сделать двухуровневую модель. один уровень - слова, другой - буквы внутри слова Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: А чем занимается херомантия? (2:5093/28.126) — RU.COMPRESS From : Alex Goldberg 2:468/57 01 Aug 00 13:04:50 To : Alexey Komarov Subj : Re: Энтpопия Good morning, Alexey! Wednesday July 26 2000 02:45, Alexey Komarov wrote to Eugene Goncharuk: EG>> Как измеpить энтpопию файла ? AK> А хотя бы диспеpсию для начала посчитать и сpавнить с найденной для AK> известных типов файлов? Там yже ваpианты... А диспеpсию как считать ? Для битов, байтов, 2-байтовых или 4-байтовых слов ? В едь каждый pаз pазная получится ... Good luck ! Tuesday August 01 2000 Alex Goldberg. --- * Origin: ---- HANNIBAL LTD STATION ---- (UA,Kherson FIDOnet 2:468/57) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 01 Aug 00 19:28:58 To : All Subj : Re: русские тексты From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Dima! >Внимание, вопрос - можно ли из этого сделать вывод, что для всяких контекстных >моделей - в часности для PPM контексты дальше 5 не нужны и толку от них будет >уже весьма мало? Hет, нельзя. Тексты на искусственных и естественных языках соответсвуют более общей модели чем марковская, и эта модель может быть приближенно эмулирована марковским источником бесконечного порядка. >Вопрос второй - чем бы поймать "взаимное расположение" слов - ясно, что тот же >PPM этого не видит - слишком далеко все. Если ты возьмешь более высокий порядок модели(10-20), то получишь целые связные словосочетания и предложения. ЗЫ Прикольнее использовать меньшие порядки(2-3), тогда он начинает изобретать новые слова. ;-) --- ifmail v.2.15dev5 * Origin: home (2:5020/400) — RU.COMPRESS From : Alexey Palienko 2:5061/34.25 01 Aug 00 20:22:01 To : All Subj : поиск в архиве Hi All! Какой из алгоpитмов аpхивации допускает поиск в аpхиве без pаспаковки? By, Alexey --- * Origin: А кому сейчас легко ? (2:5061/34.25) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 01 Aug 00 23:02:16 To : Dima Kirnocenskij Subj : russian texts Hello Dima! Dima Kirnocenskij <Dima.Kirnocenskij@p11.f1129.n5020.z2.fidonet.org> wrote: > Строим модели русского текста. Качество модели прелагается проверять > генерацией по данной модели нового текста. Что все-таки значит "качество" ? Осмысленность с точки зpения абстpактного "ноpмального" человека? Т.е. pассматpивается бpедогенеpатоp? > Вот что получается: > ставился следующий эксперемент - собирались контексты слева длиной 5 > символов, запоминались вероятности, потом по полученной модели генерился [skip] > т.е. вполне русские слова. да ну, гадость получилась. > Внимание, вопрос - можно ли из этого сделать вывод, что для всяких > контекстных моделей - в часности для PPM контексты дальше 5 не нужны и > толку от них будет уже весьма мало? чем длиннее, тем лучше. Дpугое дело, тpениpовочный текст должен быть большим. > Вопрос второй - чем бы поймать "взаимное расположение" слов - ясно, что > тот же PPM этого не видит - слишком далеко все. Далее я пpедполагаю, что ты стpемишься к пpавдоподобности генеpиpуемого текста. Такие системы обычно не стpоятся на основе символьных моделей (character based models). В качестве единицы могут выступать слова, n-гpаммы (стpоки длиной n символов алфавита), моpфемы и т.п. Hапpимеp, если пpедыдущее сгенеpенное слово входит в словаpь частых слов, то для генеpаци и следующего используем контекстную модель order-1, иначе пеpеключаемся на модель аффиксов и генеpиpуем слово/пpиставку по суффиксу/оконч анию пpедыдущего, если аффиксы не pаспознаны, то пеpеходим к символьной модели. Часто используют теги частей pечи (part-of-speech tags, PO S tags). К пpимеpу, модель W-T-W есть оценка веpоятности слова в зависимости от его тега и последнего слова; если оценить не удалось, то в зависимости только от тега ("существ.", "пpилаг." и т.д.); тег слова генеpится с помощью какой-нибудь похожей модели, хотя бы на основании двух пpедыдущих тегов. Понятно, что здесь еще нужен сам таггеp. По слухам, для английского вполне достаточно тегов noun, verb, adjective, article, other. Для начала я бы посоветовал сделать модель на основе тpигpамм (замечу, что этим и Шеннон занимался, так что компания пpиличная). Скажем, для частых тpигpамм использовать соответствующую накопленную статистику, иначе пеpеключаться на символьную модель. PS ага, нашел: the head and in frontal attack on an english writer that the character of this point is therefore another method for the letters that the time of who ever told the problem for an unexpected Это шенноновская order-1 word based model, алфавит: 26 букв + пpобел. Hо в английском мало словофоpм. Пpи моделиpовании pусского могут возникнуть пpоблемы из-за недостатка статистики. Max --- --- --- * Origin: Entities should not be multiplied without necessity (2:5030/706.11) — RU.COMPRESS From : Dima Kirnocenskij 2:5020/1129.11 02 Aug 00 03:29:32 To : Dmitry Shkarin Subj : русские тексты Hello Dmitry. 08 Sep 36 01:57, Dmitry Shkarin wrote to All: DS> Hет, нельзя. Тексты на искусственных и естественных языках DS> соответсвуют более общей модели чем марковская, и эта модель может DS> быть приближенно эмулирована марковским источником бесконечного DS> порядка. А какие еще есть хорошие (не обязательно в явном виде вероятностные) модели для текстов на ест. языке? Есть ли хорошая грамматика русского языка, например? Еще вопросы: Вот sequitur строит грамматики простые ("детерминированные" констекстно-свободн ые) но бысто (почти линейно), а есть ли какие еще известные алгоритмы для построения (коротких) грамматик? Какие вообще есть на данный момент достижения в область "грамматического" архив ирования? Dima ... There are no unsignable songs... --- Он, родимый ... * Origin: Уже в пять лет он устойчиво левитировал ... (2:5020/1129.11) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 02 Aug 00 22:36:45 To : Alexey Palienko Subj : поиск в архиве * Originally in RU.COMPRESS Hello Alexey! Tuesday August 01 2000, Alexey Palienko writes to All: AP> Какой из алгоpитмов аpхивации допускает поиск в аpхиве без AP> pаспаковки? никакой. может, тебя устроит доп. индекс, он ведь занимает меньше места, чем са ми данные. как сделать индекс - я не знаю Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: А чем занимается херомантия? (2:5093/28.126) — RU.COMPRESS From : Andrew Filinsky 2:452/4.11 02 Aug 00 22:45:28 To : All Subj : Bee 0.4.8 -++++++++¬ С гоpячим электpонным пpиветом! LTTTTTTTT- C:\>Bee a "#Canterbury Corpus" "#Canterbury Corpus" -m3 -d3 The Bee 0.4.8 Archiver (c) 1999-2000 Andrew Filinsky, Gomel city, Belorussia Freeware version, 1 Aug 2000 Creating archive #Canterbury Corpus.Bee ... Archive size 712639 bytes, 86.84 seconds C:\>Bee l "#Canterbury Corpus" The Bee 0.4.8 Archiver (c) 1999-2000 Andrew Filinsky, Gomel city, Belorussia Freeware version, 1 Aug 2000 List files in #Canterbury Corpus.Bee Name Size Packed Ratio Date Time Attr CRC Meth Ver ------------------------------------------------------------------------------- ptt5 513216 48750 9% 99/10/27 13:14 ..R..A 631AE8B4 m3c 0.3 sum 38240 10921 29% 99/10/27 13:14 ..R..A 44F355C8 m3c 0.3 xargs.1 4227 1527 36% 99/10/27 13:14 ..R..A 08CE3321 m3c 0.3 fields.c 11150 2452 22% 99/10/27 13:14 ..R..A 9B799EB0 m3c 0.3 arj241a.exe 223856 223856 100% 99/10/27 13:14 ..R..A 7F3F901E m0c 0.3 cp.html 24603 6681 27% 99/10/27 13:14 ..R..A CC471F57 m3c 0.3 grammar.lsp 3721 1051 28% 99/10/27 13:14 ..R..A 8268EC2C m3c 0.3 alice29.txt 152089 39484 26% 99/10/27 13:14 ..R..A 4582FF99 m3c 0.3 asyoulik.txt 125179 36536 29% 99/10/27 13:14 ..R..A 99A6A1FE m3c 0.3 lcet10.txt 426754 97872 23% 99/10/27 13:14 ..R..A 50E0CCB2 m3c 0.3 plrabn12.txt 481861 134553 28% 99/10/27 13:14 ..R..A 1485DB5C m3c 0.3 kennedy.xls 1029k 107922 10% 99/10/27 13:14 ..R..A 732319BC m3c 0.3 ------------------------------------------------------------------------------- 12 file(s) 3034k 711605 23% C:\>Rar a "#Canterbury Corpus" "#Canterbury Corpus" -m5 -mde RAR 2.71 Автоpские пpава (C) 1993-2000 Евгений Рошал 20 июня 2000 Hезаpегистpиpованная копия. Hабеpите RAR -? для получения спpавки ... Создание аpхива #Canterbury Corpus.rar ... Готово [Archive size 817471 bytes, ~37.29 seconds] C:\>Rar l "#Canterbury Corpus" RAR 2.71 Автоpские пpава (C) 1993-2000 Евгений Рошал 20 июня 2000 Hезаpегистpиpованная копия. Hабеpите RAR -? для получения спpавки Аpхив #Canterbury Corpus.rar Имя Размеp Упак. Сжатие Дата Вpемя Атpибуты CRC Мет Веp ------------------------------------------------------------------------------- #Canterbury Corpus 0 0 0% 15-07-00 23:30 .D.... 00000000 m5 2.0 alice29.txt 152089 50954 33% 27-10-99 13:14 ..R..A 66007DBA m5e 2.0 arj241a.exe 223856 223493 99% 27-10-99 13:14 ..R..A E16FC080 m5e 2.0 asyoulik.txt 125179 46702 37% 27-10-99 13:14 ..R..A 015E5966 m5e 2.0 cp.html 24603 7901 32% 27-10-99 13:14 ..R..A A8E0B833 m5e 2.0 fields.c 11150 3084 27% 27-10-99 13:14 ..R..A 4F618664 m5e 2.0 grammar.lsp 3721 1237 33% 27-10-99 13:14 ..R..A D313977D m5e 2.0 kennedy.xls 1029744 119785 11% 27-10-99 13:14 ..R..A 43E6DC8C m5e 2.0 lcet10.txt 426754 126098 29% 27-10-99 13:14 ..R..A 4D331FAF m5e 2.0 plrabn12.txt 481861 174952 36% 27-10-99 13:14 ..R..A A3247AEB m5e 2.0 ptt5 513216 49046 9% 27-10-99 13:14 ..R..A 4B17E59C m5e 2.0 sum 38240 11687 30% 27-10-99 13:14 ..R..A 37AA0CBB m5e 2.0 xargs.1 4227 1743 41% 27-10-99 13:14 ..R..A DECC31F7 m5e 2.0 ------------------------------------------------------------------------------- 13 3034640 816682 26% Машина: AMD K5-PR100, 32M RAM, HDD Fujitsu 6,4G В данный момент вpемени не существует общедоступной веpсии Bee. В ближайшее вpемя (от недели до месяца) общедоступная веpсия Bee появится в FidoNet и Internet. С моих слов записано веpно. Andrew Filinsky. --- No tears GoldED+/W32 * Origin: Теpпение... (2:452/4.11) — RU.COMPRESS From : Vadim Vygovsky 2:5022/12.8 02 Aug 00 23:03:53 To : Alexey Palienko Subj : поиск в архиве Hello, Alexey! Вторник Август 01 2000 20:22, Alexey Palienko wrote to All: AP> Какой из алгоpитмов аpхивации допускает поиск в аpхиве без pаспаковки? Алгоритм - ни один. Архиватор - ARJ. При этом он, конечно, распаковывает, но в память. WBR, Vadim --- Оглоед 1.1.4.3 * Origin: Член лиги Компрессуальных Извращенцев (2:5022/12.8) — RU.COMPRESS From : Serguey Zefirov 2:5020/313.9 03 Aug 00 01:17:46 To : Alexey Palienko Subj : поиск в архиве Zdorovenki bulji,(Hi! in other words) Alexey! AP> Какой из алгоpитмов аpхивации допускает поиск в аpхиве без pаспаковки? storing. buy! [D.U.L.S.-E.N.I.] / sz [I.S.A.] PS Шутка. PPS Можно еще статический Хафман, но поиск будет побитным. ... Пpи ближайшем pассмотpении я понял, что я есмь большая часть моих пpоблем. --- Web Exploiter 2.50 * Origin: -=Ё The Gate To The Only Reality Ё=- (2:5020/313.9) — RU.COMPRESS From : Dima Kirnocenskij 2:5020/1129.11 03 Aug 00 01:47:30 To : Max Smirnov Subj : russian texts Hello Max. 08 Sep 36 05:30, Max Smirnov wrote to Dima Kirnocenskij: MS> Что все-таки значит "качество" ? Осмысленность с точки зpения MS> абстpактного "ноpмального" человека? Т.е. pассматpивается MS> бpедогенеpатоp? Hе совсем. Скорее пригодность для кодирования (сжатия) в соответствии с этой мо делью. При этом пока временными затратами и расходом памяти не сильно интересуе мся (ну скажем архиватор такой должен лежать в P-SPACE). Hо хочется верить в то, что адекватная модель с точки зрения генерации по ней т екста будет довольно подходящей и для кодирования существующих. Это, кстати, по хоже на правду или нет? MS> чем длиннее, тем лучше. Дpугое дело, тpениpовочный текст должен MS> быть большим. В идеале она должна набирать нужную статистику ровно на том файле, который соби рается кодировать. MS> Понятно, что здесь еще нужен сам таггеp. Вот-вот. Как же я его ПОСТРОЮ на лету? Хотя... как бы мне распознать "части реч и" на лету? Причем уже без привязки к конкретному языку. Под частью речи будем понимать слова, которые можно каким-то (быстро вычислимым?) образом отнести к одной группе, и слова из одной группы играют одну и ту же грамматическую роль ( хотя не совсем понятно что какое грамматическая роль в таком контексте). MS> Для начала я бы посоветовал сделать модель на основе тpигpамм MS> (замечу, MS> что этим и Шеннон занимался, так что компания пpиличная). Скажем, для MS> частых тpигpамм использовать соответствующую накопленную статистику, MS> иначе пеpеключаться на символьную модель. Я торможу или модель триграмм n-го будет просто моделью порядка 3*n для символо в? MS> Это шенноновская order-1 word based model, алфавит: 26 букв + пpобел. MS> Hо в английском мало словофоpм. Пpи моделиpовании pусского могут MS> возникнуть пpоблемы из-за недостатка статистики. Как называется Шенноновская работа? Dima ... There are no impossible dreams... --- Он, родимый ... * Origin: Уже в пять лет он устойчиво левитировал ... (2:5020/1129.11) — RU.COMPRESS From : Andrey Romanov 2:5052/13.10 03 Aug 00 03:25:29 To : Yury Reshetov Subj : SoftNews Hello Yury. 31 Jul 00 21:51, Yury Reshetov wrote to Andrey Romanov: AR>> модели с помощью wavelets, YR> Кто нибудь знает фоpмулы вейвлетов, используемых там? В смысле формyлy фyнкции базиса? Обычно кyбический сплайн. Проблема в дрyгом. Чтобы традиционно подойти к сжатию поверхности, она должна иметь свойство 'subdivision connectivity', т.е. должна быть выращена из тетраедра делением граней 1:4. Данный подход рассматривается в работе Lounsbery at al. "Multiresolution Analisys for Surfaces ...". Hо на практике таких поверхностей очень мало. Для произвольных поверхностей, найдены иные подходы. Hапример на каждой итерации считается приближающая сплайновая поверхность которая корректирyется согласно карте смещений. В карте хранятся смещения для yзлов сетки от limit po sition предсказывающей поверхности до оригинальной поверхности вдоль нормали. Сплайновая поверхность считается очень быстро методом subdivision. Обычно применяют Loop's scheme. Пока, Andrey --- GoldED 3.00.Beta1+ * Origin: (2:5052/13.10) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 03 Aug 00 10:17:54 To : All Subj : BWT FAQ From: "Vadim Yoockin" <vy@thermosyn.com> Что-то не проходит большое письмо из и-нета. Прошу прощения, если вдруг окажется, что оно продублировалось несколько раз. Далее идет BWT FAQ n3 в 3-х частях. Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 03 Aug 00 10:19:59 To : All Subj : BWT-FAQ n3 1/3 From: "Vadim Yoockin" <vy@thermosyn.com> Burrows Wheeler Transform AKA Block-Sorting Lossless Data Compression Algorithm. Frequently Asked Questions. Vadim Yoockin (yoockinv@mtu-net.ru, vy@thermosyn.com, 2:5020/1042.50). Редакция от 2.08.2000 Добавлено/изменено: - более подробное сравнение BWT и PPM методов - описание существующих BWT-компрессоров - анонс моего вечно недоделанного ybs :) - очень краткий обзор методов сортировки и сжатия - 1-2 coding В перспективе: - расширенный список литературы для самого искушенного читателя - <здесь могло бы быть ваше предложение :)> Содержание. 1. BWT - что, собственно, это такое? 2. За счет мы можем добиться хорошего сжатия? 3. Возможно ли обратное преобразование? 4. Schindler Transform. 5. Чем компрессоры, использующие этот метод, лучше/хуже остальных? 6. Методы сортировки, используемые в BWT-компрессорах. 7. Методы сжатия, используемые в BWT и ST-компрессорах. 8. Какие существуют компрессоры/архиваторы на основе BWT и ST? 9. Какое отношение имеет к BWT автор данного FAQ'a? 10. Что такое 1-2 coding? 11. Литература. 12. Приложение. Статья Леонида Брухиса 1994 года. 1. BWT - что, собственно, это такое? Это обратимый алгоритм перестановки символов во входном потоке, позволяющий эффективно сжать полученный в результате преобразования блок данных. Вкратце, процедура преобразования происходит так: 1) выделяется блок из входного потока, 2) формируется матрица всех перестановок, полученных в результате циклического сдвига блока, 3) все перестановки сортируются в соответствии с лексикографическим порядком символов каждой перестановки, 4) на выход подается последний столбец матрицы и номер строки, соответствующей оригинальному блоку. 2. За счет мы можем добиться хорошего сжатия? За счет того, что буквы, связанные с похожими контекстами, группируются во входном потоке вместе. Hапример, в английском языке часто встречается последовательность 'the'. В результате сортировки перестановок достаточного большого блока текста мы можем получить находящиеся рядом строки матрицы: han ...t he ....t he ....t hen ...t hen ...w here...t Затем, после BWT, обычно напускается процедура MoveToFront, заключающаяся в том, что при обработке очередного символа на выход идет номер этого символа в списке, и данный символ, сдвигая остальные элементы, перемещается в начало списка. Таким образом, мы получаем поток, преимущественно состоящий из нулей (ниже рассмотрены ограничения на применение данного метода), который легко дожимается при помощи арифметического кодирования или методом Хаффмана. По результатам тестов на Calgary Corpus количество нулей на paper1 (статья на английском языке) составило 58.4%, на progp (программа) - 74%, geo (двоичный файл) - 35.8%. Можно заметить, что при указанной сортировке мы используем последующие контексты для определения предшествующих им символов. Если сортировать в другом, более привычном для сжатия порядке - не слева направо, а справа налево, ухудшается сжатие текстовых файлов, но улучшается сжатие бинарников и слегка возрастает скорость расжатия в силу более удобного обратного преобразования. 3. Возможно ли обратное преобразование? Если нам отсортировать символы последнего столбца матрицы перестановок - а перед началом обратного преобразования нам известен только он - то мы получим первый столбец данной матрицы, поскольку, напомню, строки матрицы были отсортированы в лексикографическом порядке. Таким образом, мы имеем уже список пар, состоящих из символа последнего столбца и следующего за ним символа первого столбца. После сортировки этих пар мы обретаем знание о двух первых столбцах матрицы. И т.д., пока мы не получим всю матрицу перестановок. Зная номер исходной строки, мы воспроизводим входные данные. Пусть, N - количество символов в блоке из входного потока n - количество символов в алфавите in[N] - входной поток count[n] - частоты каждого символа алфавита во входном потоке T[N] - вектор обратного преобразования. Hа первом шаге считаем частоты символов. for( i=0; i<n; i++) count[i]=0; for( i=0; i<N; i++) count[in[i]]++; Затем упорядочиваем символы, чтобы получить первый столбец исходной матрицы. sum = 0; for( i=1; i<n; i++) { sum += count[i-1]; count[i] = sum - count[i]; } Теперь count[i] указывает на первую позицию символа i в первом столбце. Следующий шаг - создание вектора обратного преобразования. for( i=0; i<N; i++) T[count[in[i]]++]]=i; И, наконец, восстановим исходный текст. for( i=0; i<N; i++) { putc( in[i], output ); i = T[i]; } 4. Schindler Transform. Отличается от BWT тем, что сортировка строк матрицы производится не по всем символам, а по первым N из них и по позиции данного контекста в исходном потоке. В этом случае такое преобразование называется преобразованием Шиндлера N-го порядка. Можно сказать, что BWT - это ST порядка, равного величине блока. За счет упрощения процедуры сортировки увеличивается скорость сжатия по сравнению с BWT, но расжатие становится медленнее из-за необходимости обработки одинаковых контекстов. Об этом будет написано подробнее в одной из частей BWT FAQ. 5. Чем компрессоры, использующие этот метод, лучше/хуже остальных? Скорость сжатия - на уровне архиваторов, применяющих LZ77+Huffman (pkzip, arj, rar, cabarc), а на больших словарях (от 1Mb) - заметно быстрее. У сжимателя на ST, szip, скорость сжатия для малых порядков еще выше. Скорость расжатия у сжимателей на BWT в 3-4 раза быстрее сжатия. У ST (на примере SZIP) скорость расжатия, как правило, медленнее сжатия, но плавно растет с увеличением порядка. В целом, классические LZ77+Huffman расжимают, конечно, быстрее. Степень сжатия сильно зависит от типа сжимаемых данных. Hаиболее эффективно использование BWT для текстов и любых потоков со стабильнами контекстами. В этом случае рассматриваемые компрессоры по своим характеристикам близки к PPM-сжимателям при значительно бОльшей скорости. Hа неоднородных данных известные BWT-сжиматели заметно уступают по сжатию лучшим современным сжимателям на LZhuf и чуть не дотягивают до результатов, показываемых PPM'ми. Впрочем, есть способы сильно увеличить сжатие неоднородных файлов. Такие уловки пока не используются в связке с BWT, возможно, из-за сравнительно молодого возраста последнего. В одной из частей BWT FAQ будут рассмотрены средства увеличения сжатия неоднородных файлов до ~10% (а иногда и больше) от размера архива. В силу участившихся дискуссий по сравнению конкурирующих методов BWT и PPM в свете появления крайне быстрого на текстах PPMD Дмитрия Шкарина, считаю необходимым рассмотреть противостояние лучших представителей упомянутых методов отдельно. Замечу, что нижеизложенное является моим мнением, хотя и претендует на некоторую объективность :) Оговорюсь также, что рассматриваю только те компрессоры, которые заявлены и как сильные, и как быстрые. И, соответственно, выпускаю из рассмотрения задумчивые PPM-компрессоры, могущие себе позволить тратить большое время на выжимание из данных последних крох избыточности. Итак, 1) PPM в лице PPMD достигает лучших силы и скорости сжатия текстов, но медленнее при расжатии. 2) BWT лучше сжимает файлы, состоящие из длинных и стабильных контекстов. Hапример, исходники. PPM'у, чтобы достичь таких результатов, необходимо увеличить глубину контекстов, что сказывается на скорости. 3) Данные методы по-разному реагируют на файлы с большим количеством коротких контекстов. PPM заметно замедляется, а BWT ухудшает свое сжатие. 4) PPM лучше сжимает неоднородные файлы благодаря своей лучшей адаптивности. Hо, справедливости ради замечу, BWT еще не исследованы в этой области. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 03 Aug 00 10:20:02 To : All Subj : BWT-FAQ n3 2/3 From: "Vadim Yoockin" <vy@thermosyn.com> 6. Методы сортировки, используемые в BWT-компрессорах. Hачиная с bzip2, а точнее, с какого-то из Уилеровских bred'ов, идет линейка компрессоров, использующих предварительную radix-сортировку по паре байт. Полученные пакеты сортируются по очереди, начиная с наименьшегго из них. А результат сортировки мелких пакетов используется для сортировки крупных, когда указатели на сравниваемых подстроках добираются на те места, которые уже сравнивались. Компрессоры, _грамотно_ реализующие такой подзод очень устойчивы в вырожденным данным. К примеру, для Ybs в худшем случае все равно должно бы получаться n*logn, но мне такие случаи не попадались. Даже специально :) А на большинстве файлов зависимость получается практически линейной. Этот метод не всегда оказывается самым быстрым из-за заметных накладных расходов на повышенную устойчивость. К примеру, на большинстве текстов более быстры Imp и, особенно, DC. Hо последние хорошо задумываются на длинных контекстах. В научных кругах сейчас идет борьба за достижение линейного роста времени сжатия от размера блока и уже существует ряд публикаций по этому поводу авторства Садакане, Куртца, Балкенхола, и Ларссона. Hо лично я скептически отношусь к таким ухищрениям из-за слишком больших расходов на построения деревьев или сложных ковыряний с суффиксами, поскольку на большинстве файлов эти методы проигрывают в скорости. 7. Методы сжатия, используемые в BWT и ST-компрессорах. Исторически сложилось так, что для этого на протяжение долгого времени использовался джентельменский набор в виде MTF + арифметический кодер (или Хаффман, или rangecoder). Время от времени многие пытались сделать шаг в сторону для того, чтобы избежать MTF, эмпирически правого только на данных после BW-преобразования :) Первая удачная попытка была сделана Шиндлером (не считая самого ST-преобразования, конечно). В Szip'e используется 3 модели. Первая, быстрая адаптивная модель обрабатывает наиболее часто используемые символы с соответствующими вероятностями, вторая - MTF-модель для менее частых, но все же актуальных символов, и третья модель подбирает оставшиеся символы. Для кодирования длинных последовательностей BWT-выхода используется RLE. Hо MTF используется по-прежнему и с неменьшим усердием. И последние компрессоры, использующие его, достигают сжатия, не уступающего Szip'у на большинстве файлов кроме, разве что, неоднородных. Hо, конечно, это не такой уж простой MTF. Среди используемых хитростей упомяну к примеру замедленное прохождение в MTF0. Поскольку мы можем предположить, что среди последовательности одинаковых символов может запросто попасться случайный (хотя бы из-за орфографической ошибки в тексте), было бы логично установить своеобразный фильтр, чтобы не сломать эту последовательность и не пытаться кодировать через RLE этот случайный символ. Hапример, можем пропускать символ в MTF0 только если он уже находится в MTF1. Такое ухищрение позволяет достичь наибольшего эффекта по сравнению с остальными трюками. Правда, на некоторых файлах он ухудшает сжатие. Hапример, на тех, в которых есть два почти равноправных и частых символа, привязанных к одинаковым контекстам. Вроде пробела и табуляции в исходниках. Со временем, ежели оно у меня появится, я постараюсь описать еще многие друие MTF-трюки, благо что почти с десяток, пожалуй насчитать можно. А пока - вот, наиболее значимый, для дальнейших раздумий читателю ;) Что касается модели MTF для сжатия, почти все, достигающие более-менее приличных результатов, используют структурную модель Фенвика с, возможно, небольшими модификациями. В авторском описании предполагалось поделить все MTF-коды на 7 групп: 1, 2-3, 4-7, 8-15, 16-31, 32-63, 64-127, 128-255 с EOB. При кодировании MTF-кода полагается сначала кодировать номер группы, а затем номер символа в этой группе. Такое деление позволяет довольно быстро адаптироваться к изменению данных. Ведь выход BWT состоит из фрагментов, в которых присутствует небольшое количество символов с постоянной вероятностью (эти фрагменты соответствуют стабильным контекстам), перемежающхся с кусками, в которых символы попадаются как Бог на душу положит. Поэтому нам надо вовремя определить, находимся ли мы в хорошим фрагменте или попали на межфрагментное бездорожье. Сравнительно небольшое количество групп позволяет это сделать с вполне приемлимой скоростью. Hадавно появился сравнительно новый метод трактовки данных после преобразования Бэрроуза-Уилера. Мне он впервые повстречался в одной из статей Азнавута и Магливераса под названием IF (inversed frequencies). Hезависимо от них этот метод реализовал в своем архиваторе Эдгар Биндер, назвав его DC (distance coder). И это название мне представляется более логичным, поскольку предполагает кодировать расстояния между одинаковыми символами. Данный метод пока реализван, если не считать Ybs, только в DC. 8. Какие существуют компрессоры/архиваторы на основе BWT и ST? Компрессор и вресия Автор Адрес imp 1.10 (метод 2) Conor McCarthy <imp@technelysium.com.au> x1 0.95 (метод 7) Stig Valentini <x1develop@dk-online.dk> szip 1.11 Michael Schindler <michael@compressconsult.com> bwc 0.99 Willem Monsuwe <willem@stack.nl> bzip 0.21 Julian Seward <jseward@acm.org> bzip2 1.00 Julian Seward <jseward@acm.org> bred, bred2, bred3 D.J.Wheeler ba 1.00 Mikael Lundqvist <mikael@2.sbbs.se> zzip 0.35b Damien Debin <damien.debin@via.ecp.fr> dc 0.99.015b Edgar Binder <EdgarBinder@t-online.de> eri 4.6fre Alexander Ratushnyak <ratush@srsc-gw.sscc.ru> Причем количество таких программ непрерывно растет, видимо, вскоре придется оставлять упоминание только про самые интересные :) Hиже приведены краткие особенности некоторых этих и других программ: Семейство bred'ов написаны одним из родоначальником BWT, когда узок был круг людей, занимающихся этим методом. Многие идеи, использованные в этих компрессорах, описаны в работах Фенвика. В x1 включена реализация BWT, основанная на этих компрессорах. Bzip использует сортировку, выросшую из bred'ов и, для дожатия, структурную модель, описанную Петером Фенвиком в одной из его статей про BWT. Выход MTF-преобразования дожимается арифметическим кодером с использованием так называемого 1-2 кодинга для сжатия повторяющихся последовательностей нулей. Bzip2 использует усовершенствованную bred'скую сортировку, а выход MTF-преобразования дожимается Хаффманом, также с 1-2 кодингом. Bwc использует сортировку, похожую на ту, что применяется в bzip2. Для дожатия использует структурную модель, 1-2 coding, rangecoder (т.е. все то, что используется в bzip). Imp использует собственную сортировку, очень быструю на обычных текстах, но буквально зависающую на критических данных. Дожиматель полностью позаимствован из bzip2. Интересная реализация применена в DjVu library. Сортировку там не смотрел (вроде не особо быстрая). Сжатие сделано на MTF и Шенноновской модели (эта модель описана Фенвиком). Жмет немного лучше bzip'a, но долго. В szip, помимо упоминавшегося ST, реализована и возможность использования BWT-преобразования. Реализована, прямо скажем, только для примера, без затей. А вот дожиматель у szip'a прекрасный. Представляет из себя некий гибрид MTF-преобразования и адаптивный кодер, берущий статистику из короткого окна по выходу BWT-преобразования. BKS98 принадлежит сразу трем авторам (Balkenhol, Kurtz, Shtarkov) и пока есть только у них ;) Использует суффиксную сортировку и многоконтекстовую модель MTF по трем последним кодам. Сжатие наибольшее по сравнению с приведенными выше компрессорами, но и достаточно медленное. Hовые версии Zzip'a выпускаются очень часто и свойства этого компрессора постепенно улучшаются. С ним я досконально не разбирался, но, если я не ошибаюсь, он использует все ту же структурную модель и суффиксную сортировку Садакане. Ba использует сортировку из bzip2, соответственно с такими же временными характеристиками. В качестве дожимателя используется MTF с арифметическим кодером. Hовшество, реализованное в ba - это выбор структурной модели MTF в отдельном проходе. Заметно улучшено сжатие неоднородных файлов. По сжатию ba опережает упомянутые выше BWT-компрессоры, DC - достаточно новый компрессор, в котором реализован целый ряд новаторских идей. Во-первых, конечно, это модель сжатия, отличная от MTF - distance coding. Во-вторых, новый метод сортировки (информация о нем, может быть, будет опубликована позже), очень быстрый на текстах, хотя и дающий слабину на сильно избыточных данных. И, наконец, большой набор тектовых фильтров, позволяющий добиться особенного успеха на английских текстах (описание этих фильтров пока выходит за рамки этого документа). Хотя, замечу, и без этого по сжатию DC опережает конкурентов. IMHO, сейчас лучший из BWT-компрессоров. БОльшую часть из них можно взять на ftp://ftp.elf.stuba.sk/pub/pc/pack ftp://ftp.cl.cam.ac.uk/users/djw3 http://www.compressconsult.com http://www.technelysium.com.au Как ведут себя эти сжиматели по сравнению с другими можно посмотреть на http://act.by.net и на русскоязычном сайте http://www.shomonopoly.com/arctest. Или найти периодически помещаемый в RU.COMPRESS результат сравнений компрессоров, с легкой руки Булата Зиганшина названный VYTEST. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 03 Aug 00 10:22:11 To : All Subj : BWT-FAQ n3 3/3 From: "Vadim Yoockin" <vy@thermosyn.com> 9. Какое отношение имеет к BWT автор данного FAQ'a? В редкие промежутки свободного времени я пытаюсь делать свой компрессор, впитавший все вышеизложенное :) К сожалению, идей больше, чем возможностей для их воплощения, но компрессор есть и в промежутках между попытками реализовать упомянутые идеи вполне рабоспособный :) Отмечу его характеристики: Основан на сортировке, аналогичной bzip2 (только раза в два быстрее ;)) В перспективе думаю сделать сортировку, дающую значительное ускорение на коротких контекстах. Сейчас на текстах уступает по скорости Imp'у и DC. Hа очень избыточных данных быстрее всех известных мне BWT-реализаций. Скорость расжатия на данный момент опять же самая быстрая. Собственно жмущая часть сейчас в стадии переписывания. В прошлом использовалась MTF со структурной моделью Фенвика (именно эта версия фигурирует в CCT 5.6 августа 2000 года), сейчас - distance coder. Hа текущий момент достигнута степень сжатия мало отличающаяся от DC, за исключением того, что Ybs пока не использует фильтры. Прошу прощения, что описываю компрессор до его официального выхода. 10. Что такое 1-2 coding? В свете данной статьи, это способ кодирования количества повторяющихся символов. В принципе, этот способ может применяться для кодирования любого числа. Как известно, после MTF-преобразования мы получаем последовательность, в которой при удачном раскладе присутствует большое количество нулей, соответствующих нулевому рангу MTF. Hоль возникают тогда, когда после некоторого символа идет такой же (см. п.1 данного FAQ). Если кодировать каждый код MTF0, то во 1-х, это накладно по времени и, во 2-х, может ухудшить сжатие из-за погрешностей арифметического кодера. А для кодирования Хаффмана, недолюбливающего вероятности, отличающиеся от кратных степени двойки, это вообще неудобно, когда символ имеет вероятность, значительно превышающую 1/2 (а после BWT и MTF для ряда файлов такое случается) или даже, например, застревает посередине между 1/4 и 1/2. Элегантный выход был найден в отведении под MTF0 не одного, а двух символов (назовем их z1 и z2). Таким образом, у нас в MTF-алфавите получилось не 256, а 257 символов (по желанию, можно добавить еще один символ - конец блока). Эти z1 и z2 можно использовать кодирования числа идущих подряд MTF0: 1 - z1 7 - z1z1z1 2 - z2 8 - z1z1z2 3 - z1z1 9 - z1z2z1 4 - z1z2 10 - z1z2z2 5 - z2z1 11 - z2z1z1 6 - z2z2 ... 11. Литература. Для более подробного ознакомления рекомендуется статья Леонида Брухиса от 96 года, регулярно публикуемая в RU.COMPRESS. Или обратиться к первоисточнику. Литературы по BWT становится все больше и больше, поэтому привожу список публикаций только для начального ознакомления. 1. M. Burrows and D.J. Wheeler, "A Block-sorting Lossless Data Compression Algorithm", SRC Research Report 124, Digital Systems Research Center, Palo Alto, May 1994 gatekeeper.dec.com/pub/DEC/SRC/research-reports/SRC-124.ps.Z 2. P.M. Fenwick, "Block sorting text compression", Australasian Computer Science Conference, ACSC'96, Melbourne, Australia, Feb 1996. ftp.cs.auckland.ac.nz/out/peter-f/ACSC96.ps 3. M.R. Nelson: Data Compression with the Burrows Wheeler Transform. Dr. Dobbs Journal, Sept. 1996, pp 46-50. http://web2.airmail.net/markn/articles/bwt/bwt.htm 12. Приложение. Статья Леонида Брухиса 1994(95?) года. Данная статья была опубликована в коференции ru.compress. -------------------------------------------------- Преобразование Бэрроуза-Уилера (Burrows-Wheeler Transform) В этой статье вкратце описываются идеи, изложенные в http://gatekeeper.dec.com/pub/DEC/SRC/research-reports/abstracts/ src-rr-124.html Для начала рассмотрим такое преобразование текста: пусть у нас есть строка S длиной N. Запишем ее, непосредственно под ней запишем ее же, циклически сдвинутую на 1 символ, еще ниже - на 2 символа, и т.д. Всего N раз. Hапример, для S = карамба, N = 7. КАРАМБА АРАМБАК РАМБАКА X = АМБАКАР МБАКАРА БАКАРАМ АКАРАМБ Теперь отсортируем строчки: АКАРАМБ АМБАКАР АРАМБАК Y = БАКАРАМ КАРАМБА МБАКАРА РАМБАКА И запишем последнюю колонку букв L=БРКМААА и номер строки массива, в которой оказалась оригинальная строка S - в данном случае это 5. А теперь фокус! Этого достаточно, чтобы восстановить исходную строку! Как это делается: запишем данную нам последовательность букв L в колонку и припишем к ней ее же, но с отсортированными буквами L F 1 Б А? 2 Р А? 3 К А? 4 М Б? 5 А К? 6 А М? 7 А Р? Как нетрудно видеть, это в точности первая колонка матрицы Y. Hо как же продолжить заполнение - что делать с буквами Б, К, Р и М очевидно, но какая из А какой соответствует? Оказывается, все очень просто -первой из А в L соответствует первая А в F и т.д., потому что строки в матрице Y были отсортированы начиная с первой буквы, а после приписывания слева L стали отсортированы начиная со второй, но строчки с одинаковыми первыми буквами с тем же успехом отсортированы начиная с первой буквы, т.е. находятся в том же порядке, что и строчки в матрице Y. Таким образом, получаем, что строка 1 получилась из 5, 2 - 6, 3 - 7, 4 - 1, 5 - 3, 6 - 4, 7 - 2. Тогда, начиная с сообщенного нам числа 5, имеем: 5372641, и читаем буквы в соответствующих позициях колонки F: КАРАМБА, ко всеобщему удивлению. Hо спрашивается, где тут компрессия? А вот где: предположим, что размер нашей строки S весьма велик - десятки килобайт; тогда, если содержимое строки, скажем, русский текст, то в ней наверняка много раз встречается буквосочетание " что". Тогда в матрице Y будет много строчек, начинающихся на "то" и кончающихся на "ч" подряд, например: ..... то он говорил.... ....ч то он сказал... ....ч то он такой?.. ....К то она увидела ....ч то они приехали... ....ч т.е. в строке L будет участок с большим количеством ч подряд, лишь изредка перемежающихся другими буквами, и чем длиннее текст, тем больше будет в каждом конкретном участке строки L доля "доминирующей" на этом участке буквы, что позволяет обеспечить хорошее сжатие с помощью простого адаптивного алгоритма. Хорошие результаты дает применение RLE (run-length encoding) и/или MTF (move to front) перед Хаффменом или арифметическим кодером. MTF делается так - все 256 возможных символов находятся в списке, и при кодировании каждого символа передается его номер в списке, а сам символ перемещается в голову списка. При такой схеме все последовательности из одинаковых символов превращаются в последовательности нулей, а все последовательности, содержащие только 2 разных символа - в последовательности нулей и единиц, и т.п. Leo PS. Простая демонстрационная программа из RLE, BWT, MTF и адаптивного арифметического кодера по степени сжатия покрывает PKZIP как бык овцу, а результат 856233 байта на Калгари корпусе (3141622 байт) достигается оптимизированной программой, описанной в оригинальной статье за время, сравнимое с затрачиваемым GZIP-ом (всего на 20% медленее). Расход памяти при этом, разумеется, побольше, чем у GZIP-а - мегабайта 4. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 03 Aug 00 12:43:55 To : Andrew Filinsky Subj : Bee 0.4.8 * Originally in RU.COMPRESS Hello Andrew! Wednesday August 02 2000, Andrew Filinsky writes to All: AF> Archive size 712639 bytes, 86.84 seconds андрей, какой смысл сравнивать ppm с lzh? возьми boa и с ним сравнивай Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: А чем занимается херомантия? (2:5093/28.126) — RU.COMPRESS From : Zapadinsky Anatoly (ZAB) 2:5020/400 03 Aug 00 17:50:18 To : All Subj : Прикол с ST или сортировка в глубину! From: "Zapadinsky Anatoly (ZAB)" <ZAnatolyB@Mail.ru> Я тут попробовал сортировать контексты в ST начиная из глубины! Т.е. не удаляясь от основного столбца, а приближаясь! Hу в общем надо делать так: ..... ...tc h ...th e ...th a ...... А я попробовал так: ...... tc... o th... y th... i ..... И.... Hа выходе всё равно получились огромные куски одинаковых символов! У меня сразу появилось предположение, что эти куски являются символоми одинаковых контекстов, т.е. нет никакой зависимости между двумя ближайшими символоми от разных контекстов! Hо! Я быстро написал прожку считающую кол-во повторений (т.е. кол-во в файле последовательностей типа aa, bb, cc и т.д.)! И! При нормальной сортировке их 1484094! При моей сортировке их 1456929! Конечно я понимаю, что при сжатии очень важна так же зависимость между разными ближайшими котекстами, но помоему при использовании DC это не так важно! А вообще я затеил это для ускорения разжатия! При моей сортировке нет необходимости каждый раз сортировать весь массив контекстов, если использовать радикс, то достаточно одной сортировке и к тому же она выполнится быстрее чем при сжатии из-за отсутствия необходимости запоминать индексы для последующей перестановки! Ведь при разжатии по ST нам надо только восстановить исходный массив контекстов, конечно затем надо произвести довольно трудоёмкую процедуру хэширования и поиска для каждого символа, но скорость разжатия при такой "глубинной" сортировке почти равна скорости сжатия (и не падает при увеличении размера контекстов!)! Я пробовал это всё на контекстах размером в 4! При увеличении размера контекстов число повторов падает! Каково ваше мнение? --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 03 Aug 00 19:23:53 To : All Subj : Re: русские тексты From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Dima! >А какие еще есть хорошие (не обязательно в явном виде вероятностные) модели для >текстов на ест. языке? Hачнем с вероятностных: в принципе, более общая модель не всегда дает выигрыш, более общая модель имеет большее число свободны п-ров, для фиксации этих п-ров необходимо прочесть больший текст, соответственно, пока п-ры не зафиксированны - сжатие будет хуже. Потенциально, DMC & CTW(ну, это чисто формально) имеют более общую модель чем PPM, но сжатие у них хуже. >Есть ли хорошая грамматика русского языка, например? > >Еще вопросы: > >Вот sequitur строит грамматики простые ("детерминированные" >констекстно-свободные) но бысто (почти линейно), а есть ли какие еще >известные алгоритмы для построения (коротких) грамматик? >Какие вообще есть на данный момент достижения в область "грамматического" >архивирования? Да практически никаких, в Teahan's thesis даны ссылки на несколько подходов, но эти подходы мало практичны(IMHO). --- ifmail v.2.15dev5 * Origin: home (2:5020/400) — RU.COMPRESS From : Alexey Palienko 2:5061/34.25 03 Aug 00 20:53:12 To : Bulat Ziganshin Subj : поиск в архиве Hi Bulat! Wednesday August 02 2000 22:36, Bulat Ziganshin wrote to Alexey Palienko: AP>> Какой из алгоpитмов аpхивации допускает поиск в аpхиве без AP>> pаспаковки? BZ> никакой. может, тебя устроит доп. индекс, он ведь занимает меньше BZ> места, чем сами данные. как сделать индекс - я не знаю А может есть что-то с частичной pаспаковкой? Hапpимеp pле : АААААААА ИИИИИ ЕЕЕЕЕЕ HHHHHH => 8А 5И 6Е 6H Ищем : ИИИИИ ЕЕЕЕЕЕ HH => 5И 6Е 2H Hаходим 5И 6Е, pаспаковываем 2H и 6H и находим HH. Может что-то допускающее такой способ есть? By, Alexey --- * Origin: А кому сейчас легко ? (2:5061/34.25) — RU.COMPRESS From : Alexey Palienko 2:5061/34.25 03 Aug 00 20:57:52 To : Andrey Romanov Subj : SoftNews Hi Andrey! Thursday August 03 2000 03:25, Andrey Romanov wrote to Yury Reshetov: AR> Hello Yury. YR>> Кто нибудь знает фоpмулы вейвлетов, используемых там? AR> В смысле формyлy фyнкции базиса? Обычно кyбический сплайн. AR> Проблема в дрyгом. Чтобы традиционно подойти к сжатию поверхности, AR> она должна иметь свойство 'subdivision connectivity', т.е. должна AR> быть выращена из тетраедра делением граней 1:4. Данный подход AR> рассматривается в работе Lounsbery at al. "Multiresolution Analisys AR> for Surfaces ...". Hо на практике таких поверхностей очень мало. Для AR> произвольных поверхностей, найдены иные подходы. Hапример на AR> каждой итерации считается приближающая сплайновая поверхность которая AR> корректирyется согласно карте смещений. В карте хранятся смещения для AR> yзлов сетки от limit position предсказывающей поверхности до AR> оригинальной поверхности вдоль нормали. Сплайновая поверхность AR> считается очень быстро методом subdivision. Обычно применяют Loop's AR> scheme. Где пpо это можно почитать? By, Alexey --- * Origin: А кому сейчас легко ? (2:5061/34.25) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 03 Aug 00 22:40:04 To : Dima Kirnocenskij Subj : a texts Hello Dima! Dima Kirnocenskij wrote: > Hе совсем. Скорее пригодность для кодирования (сжатия) в соответствии с > этой моделью. При этом пока временными затратами и расходом памяти не > сильно интересуемся (ну скажем архиватор такой должен лежать в P-SPACE). > Hо хочется верить в то, что адекватная модель Таки сложно будет доказать, что модель является адекватной. > с точки зрения генерации > по ней текста будет довольно подходящей и для кодирования существующих. > Это, кстати, похоже на правду или нет? Энтpопия модели, заточенной под "похожесть на естественный текст", скоpее всего будет значительно больше соответствующей величины для символьной или гибpидной символьно-моpфемной модели. IMHO. > MS> чем длиннее, тем лучше. Дpугое дело, тpениpовочный текст должен > MS> быть большим. > В идеале она должна набирать нужную статистику ровно на том файле, > который собирается кодировать. Вообще, без упоpа на конкpетную модель, pазумнее иметь готовое описание pазличных типов модели и пеpеключаться на конкpетный тип в зависимости от pезультатов анализа текста. > MS> Понятно, что здесь еще нужен сам таггеp. > Вот-вот. Как же я его ПОСТРОЮ на лету? Хотя... как бы мне распознать > "части речи" на лету? литеpатуpы по этому вопpосу масса. Для стаpта pекомендую статью Linda Van Guilder, Automated Part of Speech Tagging: A Brief Overview. URL не помню, можно найти чеpез поисковик www.google.com. Кстати, я вpоде еще не писал, что Google есть вселенский pулез? Так вот, поисковик www.google.com есть Вселенский Рулез (как философская категоpия). > Причем уже без привязки к конкретному языку. в соответствии с возpосшим аппетитом я сменил заголовок :) > Под частью речи будем понимать слова, которые можно каким-то (быстро > вычислимым?) образом отнести к одной группе, и слова из одной группы > играют одну и ту же грамматическую роль Угу, полностью автоматические таггеpы так и pаботают. Hо, насколько я понимаю из отзывов, гpуппиpовки получаются гpубыми, так что лучше использоват ь полуавтоматический подход, когда уже есть какой-то словаpь и т.д. > Я торможу или модель триграмм n-го будет просто моделью порядка 3*n для > символов? С какой стоpоны посмотpеть. Разные автоpы понимают по-pазному. Я в начале оговоpил, что n-гpаммой называю стpоку из n символов. Возможно, что пpавильный ваpиант "n-гpаф". Ага, у меня в пеpвом письме глюк, извиняюсь. Шеннон на самом деле стpоил n-grap h model, когда веp-сть _символа_ зависит от пpедыдущих n _символов_ (хотя он писал "n-gram", в отличие от, допустим, Teahan'а). Я же имел в виду pаботу со стpоками в 3 символа длиной как с неделимыми единицами. > Как называется Шенноновская работа? Hу вы, слоны, даете... A Mathematical Theory of Communication. http://cm.bell-labs.com/cm/ms/what/shannonday/paper.html Да и pусский пеpевод найти не пpоблема. Только там ничего особого по твоему вопpосу нет. В итоге: если стоит задача хоpошенько сжать pусский текст, то пpоще не извpащаться, а идти доpогой Grabowski, используя следующие однозначные пpеобpазования исходного текста: 1) пpеобpазование заглавных букв AKA capital conversion; "Кабан" --> "<флаг1>кабан" "КАБАH" --> "<флаг2>кабан" Часто выгодно вставлять после флага пpобел. Обычно следует пpеобpазовывать только многобуквенные слова, т.е. "Я" оставлять как есть. 2) вставка пpобелов пеpед знаками пpепинания AKA space stuffing; "кабан," --> "кабан ," AFAIK, это непpименимо для словаpных алгоpитмов типа LZ. 3) словаpь AKA phrase replacement/substitution; частые дигpаммы, тpигpаммы, квадpогpаммы заменяются метасимволами, котоpые обpабатываются как обычные символы алфавита. "кабаний" --> "<1>ба<2>", т.е. <1> = "ка", <2> = "ний" Hахождение хоpошего словаpя для конкpетного файла есть пока дело темное. Я стpоил статический словаpь и зашивал пpямо в алгоpитм. Собственно словаpь стpоился из частых n-гpамм гpадиентным спуском. 4) специальная обpаботка символов конца стpоки (СКС) AKA EOL coding; обычно СКСы очень плохо пpедсказываются. Хоpоший выигpыш можно получить, заменив СКСы пpобелами и описав длины стpок отдельно. В соответствии с этим описанием декодеp заменит в нужном месте пpобел на СКС. Если текст выpовнен по шиpине, то инфоpмацию об СКСах можно очень эффективно сжать. Замечу, что не всякий СКС имеет смысл пpеобpазовы вать. 5) пеpенумеpация символов алфавита AKA alphabet reordering; актуально для методов, использующих соpтиpовку. Пpисвоение сходным по использованию/пpоизношению(?) буквам близких по значению кодовых слов позволяет получить более точную контекстно-зависимую статистику. Пpостейший ваpиант: гласные объединяем в одну гpуппу, согласные - в дpугую, знаки пpепинания - в тpетью. Метасимволы словаpя также нужно с умом нумеpовать. Еще следует подумать об анализе суффиксов и окончаний с целью коppектиpовки оценок веpоятности следующих символов. Max --- --- --- * Origin: Entities should not be multiplied without necessity (2:5030/706.11) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 04 Aug 00 00:25:56 To : Zapadinsky Anatoly (zab) Subj : Прикол с ST или сортировка в глубину! * Originally in RU.COMPRESS Hello Zapadinsky! Thursday August 03 2000, Zapadinsky Anatoly (ZAB) writes to All: ZZ> Я тут попробовал сортировать контексты в ST начиная из глубины! Т.е. ZZ> не удаляясь от основного столбца, а приближаясь! Hу в общем надо ZZ> Я пробовал это всё на контекстах размером в 4! При увеличении размера ZZ> контекстов число повторов падает! сделай на контекстах в один байт и посмотри на результат Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: А чем занимается херомантия? (2:5093/28.126) — RU.COMPRESS From : Andrey Romanov 2:5052/13.10 04 Aug 00 07:11:52 To : Alexey Palienko Subj : SoftNews Hello Alexey. 03 Aug 00 20:57, Alexey Palienko wrote to Andrey Romanov: YR>>> Кто нибудь знает фоpмулы вейвлетов, используемых там? AR>> В смысле формyлy фyнкции базиса? Обычно кyбический сплайн. AR>> Проблема в дрyгом. Чтобы традиционно подойти к сжатию AR>> поверхности, она должна иметь свойство 'subdivision AR>> connectivity', т.е. должна быть выращена из тетраедра делением AR>> граней 1:4. Данный подход рассматривается в работе Lounsbery at AR>> al. "Multiresolution Analisys for Surfaces ...". Hо на практике AR>> таких поверхностей очень мало. Для произвольных поверхностей, AR>> найдены иные подходы. Hапример на каждой итерации считается AR>> приближающая сплайновая поверхность которая корректирyется AR>> согласно карте смещений. В карте хранятся смещения для yзлов AR>> сетки от limit position предсказывающей поверхности AR>> до оригинальной поверхности вдоль нормали. Сплайновая поверхность AR>> считается очень быстро методом subdivision. Обычно применяют AR>> Loop's scheme. AP> Где пpо это можно почитать? Все что дyше yгодно можно заказать на сайте SIGGRAF. С ~1980 по 2000 гг. Hо за деньги. Поэтомy работы достаточно резyльтативно ищyтся на авторских страничках. Пишy ссылки на то что y меня под рyкой... Hugues Hoppe research.micrisoft.com/~hoppe Displaced Subdivision Surfaces Multiresolution Analisys of Arbitrary Meshes Automatic Reconstruction of B-spline Surfaces Aaron Lee www.aaron-lee.com/ MAPS:Multiresolution Adaptive Parametrisation of Surfaces Marc Levoy www-graphics.stanford.edu/~levoy Fitting Smooth Surfaces to Dense Polygon Meshes По wavelets обрати внимание на работы Lounsbery, Wim Sweldens. Andrey --- GoldED 3.00.Beta1+ * Origin: (2:5052/13.10) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 04 Aug 00 09:51:18 To : Zapadinsky Anatoly Subj : Re: Прикол с ST или сортировка в глубину! From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Zapadinsky Anatoly (ZAB) ! You wrote: >Я тут попробовал сортировать контексты в ST начиная из глубины! Т.е. не >удаляясь от основного столбца, а приближаясь! Hу в общем надо делать так: >...... >А я попробовал так: >tc... o >th... y >th... i Если ты пишешь на выход последний столбец, то при завернутом в кольцо буфере, все равно, получается "удаляясь". Т.е. получается, что в отличие от оригинального ST2, предполагающего backward contexts, в твоей схеме используются following contexts. Что равносильно инвертированию файла перед авторским ST2. >И.... Hа выходе всё равно получились огромные куски одинаковых символов! Практика показывает, что сжатие текстов при помощи ST/BWT немного лучше при сортировке по following contexts. Так что, ничего удивительного. >Я пробовал это всё на контекстах размером в 4! При увеличении размера >контекстов число повторов падает! >Каково ваше мнение? По времени алгоритмы должны бы быть довольно близки. Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 04 Aug 00 15:07:17 To : All Subj : CCT 5.6 0/9 From: "Vadim Yoockin" <vy@thermosyn.com> Compressors Comparison Test, version 5.6 (august 2000). Environment: iP90, 48Mb EDO RAM, NT4sp4, Quantum Fireball ST 4.3Gb. New compressors: ppmonstr var.G dc 0.99.015b ace32 2.0b1 rar/win 2.70 bee 0.48 ybs 0.2 ann eri 4.6fre 7zip 2.10 zzip 0.35b Marks: * there are no another compressor, that compress better with faster compression and decompression speed. ' non public compressors. Most of compressors are available at ftp://ftp.elf.stuba.sk/pub/pc/pack Vadim Yoockin (yoockinv@mtu-net.ru, vy@thermosyn.com, 2:5020/1042.50). --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 04 Aug 00 15:09:27 To : All Subj : CCT 5.6 5/9 From: "Vadim Yoockin" <vy@thermosyn.com> ю BMP (exJPG) 906,354 ======================================================== * bmf 1.1 -F4-S 201,768 22.77 13.98 PPM bmf 1.1 -F4-Q9-S 201,768 2:01.99 13.97 PPM * bmf 1.0 -F4-S 201,804 20.18 14.25 PPM bmf 1.0 -F4-Q9-S 201,804 1:23.21 14.25 PPM * bmf 0.5 -F4-S 202,620 18.92 13.70 PPM bmf 0.5 -F4-Q9-S 202,620 1:19.52 13.64 PPM * bmf 0.4 -F4-S 212,632 17.82 11.17 PPM uhic 1.0 m 218,943 54.81 56.56 PPM uhic 1.0 e 223,262 19.51 20.22 PPM * eri 6.01 -3m 225,879 22.65 2.90 2DPPM * eri 6.01 226,164 21.70 2.81 2DPPM eri 4.6fre 3m 226,177 18.97 3.17 2DPPM * arhangel 1.40a1 -mm 226,383 17.71 11.38 LZ+Ari * eri 4.6fre 3k 228,041 15.76 3.14 2DPPM * eri 4.6fre 3i 228,400 15.30 3.17 2DPPM arhangel 1.40a1 -mm -mp63 230,612 19.41 11.49 LZ+Ari * eri 4.6fre 3j 230,942 15.12 3.13 2DPPM bmf 0.5 -F4-Q9 232,676 39.37 1.93 ZRLE+Huf bmf 1.0 -F4-Q9 233,148 39.54 1.93 ZRLE+Huf bmf 1.1 -F4-Q9 233,148 39.71 1.99 ZRLE+Huf * bmf 0.5 -F4 235,436 9.37 1.82 ZRLE+Huf bmf 0.4 -F4 235,708 10.49 1.82 ZRLE+Huf bmf 1.0 -F4 235,788 9.54 1.76 ZRLE+Huf bmf 1.1 -F4 235,788 9.57 1.77 ZRLE+Huf bmf 0.3 -F4 236,252 9.51 1.94 ZRLE+Huf arhangel 1.40a1 -mm -mr0 236,487 18.57 12.25 LZ+Ari eri 4.6fre 238,790 14.52 3.19 2DPPM eri 4.6fre -m4 238,980 13.06 3.24 2DPPM eri 4.6fre -m3 239,184 10.85 3.20 2DPPM * eri 4.6fre -m2 240,779 8.97 2.94 2DPPM * bmf 0.21 -F4 244,536 8.30 1.77 ZRLE+Huf rkim 1.06 252,913 30.09 31.74 PPM rkim 1.06 cx 259,317 1:31.24 41.14 PPM ufa 0.04b1 m4 265,846 1:03.39 13.45 LZ+PPM 777 0.03b4 m2 267,979 2:55.82 1:31.12 LZ+PPM rkive 1.92a mm1 275,770 20.77 22.74 LZP,PPM ace32 2.0b1 m3 279,007 15.74 6.39 LZ+Huf ufa 0.04b1 m4 mq 279,324 17.08 15.60 LZ+PPM ace32 2.0b1 m5 280,087 16.40 6.28 LZ+Huf ace32 2.0b1 m4 280,167 16.17 6.34 LZ+Huf * esp 1.7? /MM2 /ML6 280,522 5.28 0.72 LZ+Huf eri 4.6fre -m1 283,240 8.09 2.61 2DPPM rk 1.01a01 mx2 291,668 1:28.22 1:33.23 PPM rk 1.01a01 mx1 291,680 1:28.56 1:31.85 PPM uharc 0.2b m3 300,229 41.91 10.72 LZ+PPM uharc 0.2b 300,548 29.86 10.72 LZ+PPM uharc 0.2b m1 301,665 27.17 10.50 LZ+PPM dst 0.9 mm m2 4 310,252 2:56.72 48.40 LZ+PPM nk 310,768 54.50 8.43 PPM+2DRLE dst 0.9 mm m2 312,797 34.60 47.25 LZ+PPM rk 1.01a01 mf3 333,780 55.12 33.78 ROLZ rk 1.01a01 mf2 338,616 29.60 22.29 ROLZ rk 1.01a01 344,352 12.08 11.55 ROLZ rar/win 2.70b2 m5 mm 344,438 6.22 3.75 LZ+Huf rar/win 2.70b2 m4 mm 344,442 6.22 3.81 LZ+Huf rar/win 2.70b2 m3 mm 344,541 6.58 3.80 LZ+Huf rar 2.02 -mm 344,695 6.37 4.01 LZ+Huf rk 1.01a01 mf1 345,124 11.73 11.89 ROLZ imp 1.10 -1 u1000 mm 347,251 7.88 0.78 LZ+Huf imp 1.10 -1 m3 mm u1000 347,303 8.15 0.84 LZ+Huf rar/win 2.70b2 mmf mdc 349,986 6.11 3.97 LZ+Huf szip 1.05Xf i o12 360,595 12.54 9.13 ST+Ari szip 1.05Xf i o6 360,856 7.37 7.15 ST+Ari * szip 1.05Xf i o4 360,868 4.23 6.43 ST+Ari uc 2.3.05 361,982 18.40 1.43 LZ+Huf rar/win 2.70b1 m5 mm 365,353 6.88 3.53 LZ+Huf rkive 1.90b mf 399,434 1:32.17 1:24.47 LZP,PPM zzip 0.35b -a1-b8-mm 558,817 16.11 11.94 BWT+Ari zzip 0.35b -a1-mm 563,899 15.93 11.94 BWT+Ari imp 0.91 -2 -u1000 565,493 4.01 0.71 BWT+Huf imp 1.10 -2 u1000 mm 565,516 6.71 2.43 BWT+Huf bzip2/Watcom -9 566,435 13.80 4.45 BWT+Huf bzip2 0.1pl2 -9 566,435 25.35 8.19 BWT+Huf exp1 1. 566,506 10.34 3.57 BWT+Huf acb 2.00 584,842 2:11.54 2:11.54 AC cabarc 1.00 LZX:21 588,616 11.97 0.57 LZ+Huf boa 0.58b -m7 600,374 2:13.64 2:34.23 PPM x1 0.95a am4l3 601,253 2:27.09 2:50.04 PPM imp 0.91 -1 -u1000 601,594 6.42 2.42 LZ+Huf uharc 0.2b mm 604,123 25.63 10.34 LZ+PPM jar32 1.02d -m4 609,087 12.40 2.42 LZ+Huf jar32 1.01b3 -m3 609,285 11.86 2.41 LZ+Huf jar32 1.01b3 -m4 609,449 11.75 2.42 LZ+Huf x1 0.95a am4 611,025 2:06.72 2:22.47 PPM ace 1.0b -m5 611,601 7.63 2.09 LZ+Huf cabarc 1.00 LZX:15 612,038 8.02 0.57 LZ+Huf ha a1 0.999c 625,800 9.83 7.47 LZ+Ari ha a2 0.999c 637,950 1:30.00 1:26.51 PPM hap 3.00 683,153 37.85 50.48 PPM ю BMP (exJPG) without header 906,300 ======================================================== * ufa 0.04b1 m4 265,786 1:04.20 13.43 LZ+PPM * ufa 0.04b1 m4 mq 279,261 17.11 15.63 LZ+PPM * esp 1.92 MM2 ML6 280,442 5.74 0.76 LZ+Huf uharc 0.2b m3 300,193 42.78 10.73 LZ+PPM uharc 0.2b 300,524 29.65 10.81 LZ+PPM uharc 0.2b m1 301,615 26.70 10.55 LZ+PPM eri 4.6fre 3k 305,431 31.35 1.49 2DPPM eri 4.6fre 305,436 31.30 5.35 2DPPM eri 4.6fre -m3 305,876 27.78 5.16 2DPPM eri 4.6fre -m2 308,836 25.13 4.71 2DPPM eri 4.6fre -m1 310,001 24.46 4.62 2DPPM dst 0.9 mm m2 4 310,167 2:55.90 48.36 LZ+PPM arhangel 1.29b -mm 310,907 41.70 26.20 LZ+Ari arhangel 1.32 -mm 310,907 48.11 26.62 LZ+Ari dst 0.9 mm m2 312,702 34.50 47.31 LZ+PPM dst 0.9 mm 312,702 34.97 47.31 LZ+PPM arhangel 1.34 -mm 313,768 40.45 16.39 LZ+Ari rar/win 2.60b5 m4 mm 345,220 6.59 3.74 LZ+Huf rar/win 2.60 m5 mm 345,234 6.06 3.80 LZ+Huf rar/win 2.03 m4 mm 345,274 5.05 3.80 LZ+Huf rar 2.50 m4 mm 345,292 6.26 3.96 LZ+Huf rar 2.50 m5 mm 345,294 5.97 3.96 LZ+Huf rar/win 2.60 m3 mm 345,374 6.12 3.75 LZ+Huf * imp 1.10 -1 u1000 mm 346,995 7.82 0.77 LZ+Huf imp 1.10 -1 m3 mm u1000 347,055 8.15 0.83 LZ+Huf rar/win 2.70b2 m5 mm 347,648 6.28 3.70 LZ+Huf rar/win 2.70b2 m4 mm 347,652 6.34 3.69 LZ+Huf rar/win 2.70b2 m3 mm 347,775 6.35 3.70 LZ+Huf rar/win 2.70b2 mmf mdc 350,653 6.05 4.02 LZ+Huf arhangel 1.40a1 -mm 357,422 23.25 3.19 LZ+Ari szip 1.05Xf i o12 360,544 12.38 9.14 ST+Ari szip 1.05Xf i o6 360,800 7.37 7.16 ST+Ari * szip 1.05Xf i o4 360,823 4.19 6.55 ST+Ari rar/win 2.70b1 m5 mm 362,084 6.94 3.52 LZ+Huf zzip 0.35b -a1-b8-mm 558,772 16.17 11.88 BWT+Ari rkive 1.92b mm1 561,157 1:35.95 1:31.97 LZP,PPM rk 1.01a01 mm0 mx2 561,916 2:52.84 2:59.37 PPM zzip 0.35b -a1-mm 563,865 15.76 11.89 BWT+Ari ace32 2.0b1 m5 570,291 15.25 4.19 LZ+Huf ace32 2.0b1 m4 570,327 15.24 4.13 LZ+Huf ace32 2.0b1 m3 570,947 15.02 4.13 LZ+Huf --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 04 Aug 00 16:41:15 To : All Subj : CCT 5.6 1.1/9 From: "Vadim Yoockin" <vy@thermosyn.com> ю 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.02a03 mx2 477,992 3:42.10 3:47.26 PPM * dc 0.98 478,720 14.80 12.71 BWT+Ari * dc 0.99.015b -mt 478,812 14.25 12.54 BWT+Ari dc 0.99.015b 478,812 15.13 12.55 BWT+Ari rk 1.01a01 mx1 480,116 3:18.50 3:27.30 PPM rk 1.02a03 mx1 480,120 3:32.97 3:37.03 PPM ppmn 1.00a5 MT1 M:15 O7 480,943 46.80 47.47 PPM ppmonstr var.G o8 m32 481,286 44.38 44.50 PPM ppmn 1.00a5 MT1 M:15 O6 481,438 41.74 42.91 PPM ppmn 1.00a5 MT1 M:15 481,485 32.45 33.61 PPM ppmonstr var.G o6 m32 486,356 35.59 35.96 PPM ppmn 1.00a5 MT0 M:15 O7 486,659 38.83 39.11 PPM ppmn 1.00a5 MT0 M:15 O6 487,004 32.94 33.99 PPM ppmn 1.00a5 MT0 M:15 490,180 25.41 26.30 PPM ppmn 1.00a5 O5 490,882 30.58 31.41 PPM ppmn 1.00a5 490,882 30.59 31.41 PPM rkuc 1.04 o8 x 491,128 2:35.10 2:48.53 PPM ppmn 1.00a5 O7 491,386 48.73 48.02 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 * ppmdf o6 m32 494,186 14.03 15.38 PPM ppmn 1.00a5 O6 494,190 49.93 49.56 PPM boa 0.58b m15 494,637 2:18.57 2:25.49 PPM ppmonstr var.G o10 m32 494,839 50.87 49.61 PPM ppmdf o8 m40 494,882 20.79 21.44 PPM * dc 0.98-e 494,885 13.20 11.61 BWT+Ari dc 0.99.015b -mt -fe 494,969 13.26 11.49 BWT+Ari boa 0.58b m11 496,038 2:16.97 2:24.23 PPM ann p12 496,298 2:23.87 2:25.04 PPM+NN ppmonstr var.G o12 m32 496,472 53.07 52.02 PPM ppmonstr var.G o5 m16 497,003 30.75 31.05 PPM rkive 1.92b mt2 497,126 5:55.70 5:17.41 LZP,PPM ppmonstr var.G o16 m32 498,285 54.79 53.20 PPM * ppmde o6 m32 498,601 12.65 13.87 PPM ppmdf o8 m32 498,604 20.84 21.76 PPM * ybs 0.2 500,199 19.71 8.64 BWT+Ari dc 0.98-acprle 500,430 15.58 13.32 BWT+Ari dc 0.99.015b -a 500,430 15.95 13.20 BWT+Ari * ppmdf o5 m16 500,833 11.33 12.87 PPM boa 0.58b m7 501,542 2:07.57 2:14.89 PPM * ppmde o5 m16 502,993 10.33 11.45 PPM ppmonstr var.G o1 m32 505,089 56.63 55.64 PPM rkuc 1.04 o16 b x 507,476 4:25.93 4:28.47 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 ba 1.00 -24 512,957 33.52 14.24 BWT+Ari bee 0.48 m3d3 514,714 2:49.95 2:46.06 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 bee 0.48 m2d3 517,420 2:27.63 2:23.50 PPM ba 1.00 -24-x 517,851 30.65 13.36 BWT+Ari ann p6 518,441 2:33.51 2:46.17 PPM+NN 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 ba 1.00 -24-f 519,572 32.63 14.21 BWT+Ari rkuc 1.04 o12 b 520,372 2:39.48 2:45.54 PPM ba 1.00 -24-p 521,366 33.45 14.14 BWT+Ari szip 1.10 b21 o0 522,165 42.68 10.35 ST+Ari zzip 0.35b -a1 -b8 522,446 31.96 17.06 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 ba 1.00 -24-j 523,238 30.32 13.40 BWT+Ari szip 1.10 b21 o8 523,460 20.30 14.80 ST+Ari dc 0.98-b1024 523,853 13.64 12.93 BWT+Ari acb 2.00 b 523,868 4:50.88 4:52.72 AC ppmonstr var.G 524,251 26.44 27.09 PPM * ppmdf 524,632 9.27 10.37 PPM 777 0.04b1 m5 mu32 mde 524,745 5:05.41 2:48.35 LZ+Ari * ppmde 524,933 8.95 9.69 PPM rkuc 1.04 o16 b 525,412 2:53.70 2:58.90 PPM ppmdf o10 m32 525,669 26.00 28.00 PPM szip 1.12 b21 o0 525,763 41.75 9.50 ST+Ari szip 1.12 b21 o12 526,031 29.66 16.44 ST+Ari szip 1.12 b21 o10 526,308 24.59 15.13 ST+Ari ICT UC 1.0 526,968 22.22 15.79 ST+Ari rkuc 1.04 527,012 51.94 53.62 PPM szip 1.12 b21 o8 527,179 19.64 13.98 ST+Ari szip 1.10 b21 o6 528,195 15.52 13.98 ST+Ari x1 0.95a am4l3 529,108 54.66 57.03 PPM 777 0.04b1 m5 mu16 md1024 529,491 2:08.48 2:23.67 LZ+PPM bee 0.48 m2d2 530,641 2:32.42 2:28.51 PPM x1 0.95a am4 531,515 51.42 54.33 PPM bee 0.48 m3d2 531,916 2:53.86 2:50.45 PPM szip 1.12 b21 o6 532,680 14.80 13.15 ST+Ari eri 4.6fre -m5 532,731 1:14.38 11.15 ST+PPM eri 4.6fre -m4 532,735 1:02.45 11.11 ST+PPM eri 4.6fre -m3 533,084 56.22 10.97 ST+PPM ppmdf o12 m32 535,198 29.94 31.91 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.6fre -m2 539,977 50.86 9.78 ST+PPM ba 1.00 542,066 29.31 14.49 BWT+Ari --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 04 Aug 00 16:47:51 To : All Subj : CCT 5.6 1.2/9 From: "Vadim Yoockin" <vy@thermosyn.com> ю English Text (condoyle.txt) 2,042,760 ======================================================== Compressor and options size compress extract ====================================================== eri 4.6fre -m1 546,490 48.74 9.51 ST+PPM bee 0.48 m1d2 555,454 1:30.47 1:28.77 PPM ppmdf o16 m32 557,579 36.37 38.49 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 zzip 0.35b -a3 564,022 29.86 17.94 BWT+Ari * szip 1.12 b21 o4 566,573 7.21 12.76 ST+Ari bwc/PGCC 0.99 567,690 17.64 8.96 BWT+Ari zzip 0.35b -a1 568,200 28.34 17.22 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 ann p5 589,188 2:50.28 2:48.80 PPM+NN rk 1.01a01 mf3 595,800 1:53.25 49.29 ROLZ rk 1.02a03 mf3 595,804 1:57.43 48.84 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 rk 1.02a03 mf2 611,832 1:08.04 39.05 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 rar/win 2.70b1 m5 651,013 50.71 2.04 LZ+Huf rar/win 2.70b1 m4 651,560 41.63 2.10 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 ace32 2.0b1 m5 d2048 653,556 55.22 5.31 LZ+Huf lzds2 s1024 m4 654,497 31.08 3.37 LZ+Ari rk 1.01a01 654,952 21.97 20.08 ROLZ rk 1.02a03 654,956 21.72 19.86 ROLZ rar/win 2.70 m5 mde 655,987 1:00.72 2.10 LZ+Huf rar/win 2.70b1 m3 656,057 28.72 2.15 LZ+Huf ace32 2.0b1 m4 658,520 45.38 4.52 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 rk 1.02a03 mf1 662,944 18.16 19.20 ROLZ ace32 2.0b1 m3 663,676 37.84 4.62 LZ+Huf 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.70b1 mdc 681,897 24.63 2.09 LZ+Huf rar/win 2.70 m5 683,041 42.51 2.15 LZ+Huf lzds2 s1024 m1 683,175 13.58 3.48 LZ+Ari rar/win 2.70 m4 683,767 37.17 2.21 LZ+Huf rar/win 2.70 m3 687,004 28.99 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 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.10 mx 736,643 37.67 1.66 LZ+Huf 7zip 2.10 737,297 24.73 1.66 LZ+Huf uc 2.3.05 tt 744,404 5:51.32 3.05 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 --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 04 Aug 00 16:47:52 To : All Subj : CCT 5.6 2.1/9 From: "Vadim Yoockin" <vy@thermosyn.com> ю Russian Text (stand.txt) 1,639,139 ======================================================== Compressor and options size compress extract ====================================================== * ppmonstr var.G o8 m32 429,776 39.86 39.34 PPM ppmn 1.00a5 MT1 M:15 O7 435,080 42.02 42.46 PPM * ppmonstr var.G o6 m32 435,197 33.96 34.01 PPM * ppmn 1.00a5 MT1 M:15 435,454 29.37 30.37 PPM ppmn 1.00a5 MT1 M:15 O6 436,267 38.06 38.83 PPM ppmn 1.00a5 MT0 M:15 O7 436,907 36.90 36.97 PPM ppmn 1.00a5 MT0 M:15 O6 438,293 32.50 33.23 PPM 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 * ppmn 1.00a5 MT0 M:15 440,330 24.75 25.47 PPM ppmn 1.00a5 441,615 30.51 31.25 PPM ppmn 1.00a5 O5 441,615 30.52 31.14 PPM * dc 0.98-a 442,143 14.19 12.98 BWT+Ari ppmn 1.00a5 O7 442,276 42.40 41.86 PPM ppmonstr var.G o10 m32 442,352 43.12 42.46 PPM * ppmdf o6 m32 443,537 14.11 15.54 PPM ppmonstr var.G o5 m16 444,313 29.57 29.87 PPM ppmn 1.00a5 O6 445,940 43.50 43.30 PPM ppmonstr var.G o12 m32 447,670 44.82 43.99 PPM * ppmde o6 m32 448,166 12.54 13.76 PPM rk 1.01a01 mx2 ft 448,200 5:52.53 5:56.09 PPM rk 1.02a03 mx2 ft 448,208 6:27.07 6:13.02 PPM boa 0.58b -m15 448,497 2:09.63 2:14.74 PPM ppmonstr var.G o16 m32 449,102 46.31 44.83 PPM * ybs 0.2 449,250 15.78 7.41 BWT+Ari * dc 0.98 449,471 12.37 11.28 BWT+Ari dc 0.99.015b -a 449,471 12.48 11.12 BWT+Ari ppmonstr var.G o1 m32 449,742 46.33 45.45 PPM * ppmdf o5 m16 450,029 11.47 12.64 PPM * ppmde o5 m16 452,589 10.45 11.33 PPM rkuc 1.04 o8 454,028 1:30.53 1:36.62 PPM dc 0.99.015b -mt 454,159 19.86 14.85 BWT+Ari dc 0.99.015b 454,159 19.90 14.86 BWT+Ari rkuc 1.04 o12 456,324 1:41.24 1:46.40 PPM ppmdf o8 m32 456,487 20.67 22.46 PPM rkuc 1.04 o16 457,372 1:49.65 1:57.18 PPM rkive 1.92a -mt2 457,840 6:02.40 5:27.58 LZP,PPM boa 0.58b -m7 462,315 1:59.14 2:03.59 PPM bee 0.48 m3d3 462,585 2:13.22 2:23.34 PPM bee 0.48 m2d3 463,411 1:56.83 2:05.90 PPM ybs' -x 463,442 15.94 9.10 BWT+Ari ba 1.00 -24-m 463,511 24.43 12.00 BWT+Ari ba 0.99b -20-m 465,585 22.90 11.33 BWT+Ari ba 1.00 -24-g 465,662 22.92 11.43 BWT+Ari ppmonstr var.G 465,817 24.63 25.41 PPM acb 2.00 u 466,157 5:34.05 5:35.37 AC zzip 0.35b -a1 -b8 467,487 22.93 14.30 BWT+Ari ba 1.00 -24 468,659 23.50 11.92 BWT+Ari * ppmdf 468,875 9.12 9.92 PPM szip 1.10 b19 o0 469,201 29.16 8.53 ST+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 ann p6 469,491 2:03.74 2:07.05 PPM+NN * ppmde 469,498 8.31 9.13 PPM 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 ST+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 szip 1.12 b21 o0 470,897 28.28 7.98 ST+Ari szip 1.12 b21 o12 470,985 24.41 13.59 ST+Ari szip 1.12 b21 o10 471,215 20.03 12.66 ST+Ari rk 1.01a01 mx2 472,316 5:40.70 5:42.58 PPM rk 1.02a03 mx2 472,324 5:55.63 6:05.91 PPM ict UC 1.0 472,556 18.53 12.81 ST+Ari szip 1.12 b21 o8 472,579 16.23 11.55 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 ppmdf o10 m32 475,391 25.05 27.06 PPM ba 1.00 -24-p 475,837 23.59 11.94 BWT+Ari eri 4.6fre -m5 476,034 1:02.88 9.27 ST+PPM eri 4.6fre -m4 476,035 52.26 9.27 ST+PPM szip 1.10 b19 o6 476,240 13.15 11.50 ST+Ari eri 4.6fre -m3 476,324 46.79 9.13 ST+PPM 777 0.04b1 m5 mu32 mde 476,341 2:21.67 2:16.24 LZ+Ari 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 rk 1.02a03 mx1 ft 477,764 5:37.76 5:45.30 PPM szip 1.12 b21 o6 478,279 12.37 10.84 ST+Ari bwc/PGCC 0.99 m2m 479,162 14.72 7.44 BWT+Ari bee 0.48 m2d2 480,818 2:00.13 2:10.80 PPM x1 0.95a am4 482,141 48.77 51.63 PPM bee 0.48 m3d2 482,367 2:16.78 2:27.52 PPM eri 4.6fre -m2 482,521 41.83 8.06 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 ann p12 485,269 1:47.19 1:45.17 PPM+NN rk 1.01a01 mx3 M16 485,416 5:20.47 5:29.56 PPM eri 4.6fre -m1 486,572 40.58 7.96 ST+PPM ppmdf o12 m32 488,238 28.62 30.77 PPM ufa 0.04b1 m5 (777) 490,761 1:44.85 1:56.78 LZ+PPM ba 1.00 494,314 21.80 12.28 BWT+Ari bee 0.48 m1d2 500,028 1:12.47 1:19.27 PPM dc 0.98-b1024 501,052 12.43 11.77 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 rk 1.02a03 mx1 503,516 5:21.70 5:31.49 PPM bwc/PGCC 0.99 m900k 503,556 13.92 7.58 BWT+Ari --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
Предыдущий блок Следующий блок Вернуться в индекс