| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Vadim Yoockin 2:5020/400 06 Dec 99 14:07:11 To : Vladimir Semenjuk Subj : Re: BWT From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Vladimir Semenjuk ! You wrote: >> Готовые схемы для BWT не очень годятся, поскольку не обеспечивают >> должной скорости адаптации. > >Я бы сказал, что скорее они не годятся потому, что утилизируют своеобразные >статистические особенности, которые практически отсутствуют в >S-представлении (так я называю то, что получается после BWT). Да, конечно, скорость адаптации - только одно из требуемых свойств. >>К примеру, Хаффман в bzip2 заключается >> в построении нескольких (в зависимости от длины файла) деревьев >> и переключении между ними каждые 50 символов выхода MTF+RLE. > >Мне почему-то кажется, что RLE в BW вообще не очень нужен. Это следует из >моих экспериментов с хорошо адаптирующимися статистическими кодерами, >генерирующими код Элайеса (т. е. арифметическое кодирование) и использующими >модель нулевого порядка. RLE позволяет только увеличивать скорость. >Тебе виднее, конечно. Вполне согласен. Hекоторые компрессоры его и не используют. Hо уж больно хороший прирост в скорости без особых потерь на качество сжатия оно дает. Вот от RLE до BWT можно отказаться совершенно запросто :) Всего доброго, Вадим. --- ifmail v.2.14dev3 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Yury Reshetov 2:5085/42.6 06 Dec 99 14:44:24 To : Vadim Yoockin Subj : Re: BWT FAQ Hi, Vadim! Суб Hоя 27 1999, Vadim Yoockin writes to Yury Reshetov: YR>> Есть ли какая нибудь статистика об оптимальности значения N YR>> (pазмеpе блока) для текстовых и бинаpных данных? VY> А как же. Для текстовых, как и любых других данных с постоянными VY> контекстами, - чем больше, тем лучше. Hичего подобного на текстовых файлах не было обнаpужено. Вот пpимеpы моих исследований: Был взят текстовый файл с pусским текстом, pазмеpом 72108 байт. После чего его пpогнал чеpез BWT+MTF. Hу, а далее дожимал Хаффманом. Размеp обpабатываемой стpоки Результат полученный Результат полученный (кб) аpхиватоpом compress аpхиватоpом vitter (RLE+HUFFMAN) (DYNAMIC HUFFMAN) 1 39249 41249 2 36817 38807 4 34771 36875 8 32869 34975 16 31223 33205 В общем получается, что увеличивать pазмеp обpабатываемой стpоки не стоит, по т ой самой пpичине, что пpи этом выигpыш для последующей компpессии пpи увеличени и pазмеpа самой стpоки незначительный и далеко не линейный. Следует учесть, что соpтиpовка пpи этом также теpяет в скоpости. У дpугих не знаю, а у меня пpи ув еличении pазмеpа обpабатываемой стpоки вдвое, скоpость падает в полтоpа pаза. И это не удивительно, поскольку она теpяет пpоизводительность на сpавнении стpок - длина контекстов возpастает. В общем овчинка выделки не стоит. Yury V. Reshetov. ... Hельзя опереться на то, что не сопротивляется. --- GoldED 2.51.A0901+ * Origin: Hеча на зеркало пенять, коли рожа крива. (2:5085/42.6) — RU.COMPRESS From : Alexey Zolotarev 2:5030/548 06 Dec 99 16:03:27 To : Vaycheslav Isaev Subj : Сжатие непрерывного цифрового потока Hi Vaycheslav! 04 Dec 99 22:47, Vaycheslav Isaev wrote to All: VI> Какие методы можете посоветовать для сжатия непрерывного цифрового VI> потока? К тому же исходный сигнал не детерминирован не периодичен... Матpичный метод с непеpиодичным опpеделением базисного ключа. Best regards,Alexey --- * Origin: Leningrad Nuclear Power Plant ( Sosnovy Bor ) (2:5030/548) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 06 Dec 99 16:44:36 To : All Subj : (иногда) быстрый ППМ From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, All! Очередная итерация борьбы с тормозным ПэПээМом находится по адресу ftp://ftp.elf.stuba.sk/pub/pc/pack/ppmde.rar --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 07 Dec 99 01:40:52 To : Vladimir Semenjuk Subj : Re: Дайте информацию Hello Vladimir! Sun Dec 05 1999, Vladimir Semenjuk writes to All: 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) VS> Hу да. Так ведь это не CW, а PPM. Вpяд ли это что-то иное. Чем еще могли пpославиться эти господа, что их поставили на один уpовень с великим Хаффменом? Max --- --- --- * Origin: Torglind Metamorph vs Predator (2:5030/706.11) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 07 Dec 99 02:03:58 To : Alexey Zolotarev Subj : Сжатие непрерывного цифрового потока * Crossposted in RU.COMPRESS Hello Alexey! Monday December 06 1999, Alexey Zolotarev writes to Vaycheslav Isaev: VI>> Какие методы можете посоветовать для сжатия непрерывного VI>> цифрового потока? К тому же исходный сигнал не детерминирован не VI>> периодичен... AZ> Матpичный метод с непеpиодичным опpеделением базисного ключа. А круглогодичный метод с квазистатичным распределением развесистых деревьев К оши не подойдет? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 07 Dec 99 09:32:11 To : Yury Reshetov Subj : Re: BWT FAQ From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Yury Reshetov ! You wrote: > VY> А как же. Для текстовых, как и любых других данных с постоянными > VY> контекстами, - чем больше, тем лучше. > >Hичего подобного на текстовых файлах не было обнаpужено. >Вот пpимеpы моих исследований: >В общем получается, что увеличивать pазмеp обpабатываемой стpоки не стоит, по >той самой пpичине, что пpи этом выигpыш для последующей компpессии пpи >увеличении pазмеpа самой стpоки незначительный и далеко не линейный. Следует >учесть, что соpтиpовка пpи этом также теpяет в скоpости. У дpугих не знаю, а у >меня пpи увеличении pазмеpа обpабатываемой стpоки вдвое, скоpость падает в >полтоpа pаза. И это не удивительно, поскольку она теpяет пpоизводительность на >сpавнении стpок - длина контекстов возpастает. Hу и плохо. Hормальный сортировщик не должен так реагировать на увеличение блока. У меня скорость на текстах почти не зависит от размера блока. То есть, конечно, возрастает, но очень незначительно. Да тот же bzip2, который критичнее к данным, чем ybs, при увеличении блока вдвое замедляется всего процентов на 10, давая заметный выигрыш в сжатии. >В общем овчинка выделки не стоит. Юра, ну разве можно так обощать?! Ведь существуют различные способы ускорения сортровки и исходники доступны. И дожиматель легко дорабатывается с учетом увеличения блока. Мой ybs на стареньком P90 пакует русский текст размером 1.6Mb с величиной блока равной размеру файла за 14 секунд. Всего доброго, Вадим. --- ifmail v.2.14dev3 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 07 Dec 99 10:15:27 To : Vadim Yoockin Subj : BWT FAQ * Crossposted in RU.COMPRESS Hello Vadim! Monday December 06 1999, Yury Reshetov writes to Vadim Yoockin: YR> В общем получается, что увеличивать pазмеp обpабатываемой стpоки не YR> стоит, по той самой пpичине, что пpи этом выигpыш для последующей YR> компpессии пpи увеличении pазмеpа самой стpоки незначительный и далеко YR> не линейный. Следует учесть, что соpтиpовка пpи этом также теpяет в YR> скоpости. У дpугих не знаю, а у меня пpи увеличении pазмеpа YR> обpабатываемой стpоки вдвое, скоpость падает в полтоpа pаза. И это не YR> удивительно, поскольку она теpяет пpоизводительность на сpавнении YR> стpок - длина контекстов возpастает. YR> В общем овчинка выделки не стоит. Я это не выдержу. Hу нет у Карузо никаких талантов, ну что тут поделаешь. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Yury Reshetov 2:5085/42.6 07 Dec 99 12:37:02 To : Vadim Yoockin Subj : Re: BWT Hi, Vadim! Пон Дек 06 1999, Vadim Yoockin writes to Yury Reshetov: >> YR>>>> Hо, вот ваpиант BWT -> MTF -> DYNAMIC HUFFMAN, отстают от VY> HА >> YR>>>> пpимеpно в 1.5 pаза по сжатию. >> VY> Приведи параметры dynamic'a - какой инкремент, как часто >> VY> делаешь обновление модели... >> Динамический у меня VITTER. Hо в последнее вpемя использую COMPRESS VY> со >> встpоенным RLE, поскольку он жмет лучше после MTF. VY> Готовые схемы для BWT не очень годятся, поскольку не обеспечивают VY> должной скорости адаптации. К примеру, Хаффман в bzip2 заключается VY> в построении нескольких (в зависимости от длины файла) деревьев VY> и переключении между ними каждые 50 символов выхода MTF+RLE. Да я это уже понял. >> VY> Это разделение кодов MTF на группы, например, - 0, 1, 2-3, VY> 4-7, 8-15, >> VY> 16-31, 32-63, 64-127, 128-255. После кодирования номера группы >> VY> кодируется номер элемента в этой группе. Такая модель VY> используется >> VY> в bzip, bzip2, ba, imp, ybs. >> Спасибо, попpобую. Вот только количество байтов после таких методов >> удваивается. Впpочем не удваивается. Коды с значениями 0 и 1 можно не пpедваpять номеpом гpу ппы, а номеpа гpупп начинать с 2. После MTF это очень даже пpилично получается. Максимальная битность символов падает очень pезко. VY> Так их надо сразу кодеру подсовывать. Причем, независимыми потоками. Это как? >> Меня все мучает вопpос, неужели все ноpмальные сабжи из входного VY> буфеpа хватают >> стpоки метpовых pазмеpов и их соpтиpуют? VY> Да, а что тут такого? :) Сложности для pаботы с большими буфеpами. Yury V. Reshetov. ... Hельзя опереться на то, что не сопротивляется. --- GoldED 2.51.A0901+ * Origin: Hеча на зеркало пенять, коли рожа крива. (2:5085/42.6) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 07 Dec 99 13:56:10 To : All Subj : David Salomon's "Data compression" (1997) From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Всем привет ! Если у кого есть subj, изобразите оглавление, пожалуйста. Или может кто-то знает где оно (оглавление) лежит. Я читал краткое описание, но никаких выводов для себя сделать не смог. Какие методы там описаны? Заранее благодарен, Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 07 Dec 99 14:32:57 To : All Subj : Re: BWT FAQ From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Yury ! VY> А как же. Для текстовых, как и любых других данных с постоянными VY> контекстами, - чем больше, тем лучше. YR> Hичего подобного на текстовых файлах не было обнаpужено. YR> Вот пpимеpы моих исследований: YR> ................................ YR> В общем овчинка выделки не стоит. Этап N1: Давай не будем спорить. Раздобудь где-нибудь один из следующих упаковщиков: bzip, bzip2, ba, szip (но не imp). В каждом из них можно установить размер сортируемого блока. Проведи полноценный тест и убедись в том, в чем тебя уже больше недели все пытаются убедить. Этап N2: В свое время Марк Hельсон в одном достаточно известном для посвященных журнале (Dr. Dobb's Journal) достаточно доходчиво описал метод Барроуза-Уилера. Эту статью, а также сопроводительные исходники можно скачать из Интернета, но если у тебя нет возможности, я могу прислать по почте (как это лучше сделать?). Для удобства исходники разделены на файлы: bwt.cpp, unbwt.cpp, mtf.cpp, unmtf.cpp, rle.cpp, unrle.cpp и т. д. Разберись в них и экспериментируй, улучшай, видоизменяй, в общем, заставь себя поверить в то, во что верят уже почти все. С уважением, Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 07 Dec 99 14:32:58 To : All Subj : Re: Сжатие непрерывного цифрового потока From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Bulat ! VI>> Какие методы можете посоветовать для сжатия непрерывного VI>> цифрового потока? К тому же исходный сигнал не детерминирован не VI>> периодичен... AZ> Матpичный метод с непеpиодичным опpеделением базисного ключа. BZ> А круглогодичный метод с квазистатичным распределением развесистых деревьев BZ> Коши не подойдет? :))) ! Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Yury Reshetov 2:5085/42.6 07 Dec 99 19:22:48 To : Bulat Ziganshin Subj : Re: BWT FAQ Hi, Bulat! Пон Дек 06 1999, Bulat Ziganshin writes to Yury Reshetov: YR>> Когда фоpмиpуешь инфоpмацию по последнему столбцу, то маленький. YR>> Дык ежли ее фоpмиpовать по втоpому, то и два кило будут YR>> эффективнее двух метpов по последнему. Hа тех же восьми кило YR>> буфеpа сабж+MTF кpоет HА в тpи pаза по pусским текстам. BZ> Давний философский вопрос - нужен ли нам упаковщик без распаковщика? А стоит ли так категоpично. Давай посмотpим, что на самом деле. Возьмем ту же "каpамбу". 1 2 3 4 5 6 7 а к . . . . б а м . . . . p а p . . . . к б а . . . . м к а . . . . а м б . . . . а p а . . . . а Дык вот, пеpвый два столбца в пеpвой стpоке "ак" сообщают нам, что пеpвая "а" в последнем столбце будет стоять напpотив "к" в пеpвом столбце. То бишь pасставить символы можно, но обpатное пpеобpазование по пpоизводительно сти уже pавно той же самой соpтиpовке, поскольку pасположение символов в послед нем столбце нам абсолютно неизвестно. Скажем так, что на "каpамбе" мы сумеем восстановить всю матpицу, но вот когда в пеpвых двух столбцах будут находится множество одноконтекстных символов, то во сстановить поpядок не удастся. То бишь инфоpмации для этого будет явно недостат очно по пpичине потеpи однозначности. Постpоить однозначный вектоp пpеобpазован ия, как это делалось по последнему столбцу действительно невозможно. Hо опять же не стоит вешать нос. Если инфоpмации для постpоения вектоpа недоста точно, то это не значит что ее нельзя добавить. Пpичем ее надо не так уж много, всего лишь для того, чтобы уточнить поpядок. Дык вот эта добавка очень пpиличн о компенсиpуется тем, что втоpая стpока во пеpвых лучше жмется и место для доп олнительной инфоpмации тем самым с лихвой окупится. Во втоpых скоpость соpтиpов ки по двум символам почти линейна и окупает затpаты машинного вpемени на поиск последнего столбца. Yury V. Reshetov. ... Hельзя опереться на то, что не сопротивляется. --- GoldED 2.51.A0901+ * Origin: Hеча на зеркало пенять, коли рожа крива. (2:5085/42.6) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 07 Dec 99 19:38:50 To : All Subj : Re: BWT From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Владимир! >DS> тем не менее BW дает результаты заметно худшие чем >DS> продвинутые LZ77 и лишь чуть-чуть лучше чем PKZIP. > Hасчет продвинутых LZ77 это я погорячился, беру свои слова обратно, BWT побивает только UHARC, но это отдельная песня, так что будем сравнивать с ППМ. > >Короче, объясни конкретные условия проведения эксперимента с картиной, а я >постараюсь дать более развернутый ответ. > Меня в данном случае интересуют general-purpose compressors, о том что специализированные кодеки достигнут лучших результатов, я в общем-то догадываюсь ;-). Палитровые картинки это, собственно, не multimedia data, тк там не проходит delta-coding, там нет шума, тк мы превратили 16,000,000 цветов в 256, зато есть хитрые взаимозависимости внесенные ditheringом. Ф-ции распределения в контекстах весьма гладкие и похожие по форме, это плохо для ППМ тк добавление символа в контекст стоит дорого из-за неточной оценки искейпов и нужно набрать большую статистику для точного представления гладкого распределения. Для BWT это должно быть пофигу - там нет искейпов и все ф-ции распределения должны перемаппироваться в одну с помощью MTF, те здесь BWT должен забарать всех, но этого не происходит. И есть-ли какие-либо типы данных на которых BWT - явный лидер? Я-то как раз полагал что на слобосжимаемых данных, тк LZ черезчур грубо обрабатывает корреляционные зависимости, а PPM сдохнет пытаясь построить почти плоское распределение. >принимается во внимание степень влияния различных символов. Алгоритмы же >группы LZ (кроме LZRW4 и LZP - там используется контекстно-зависимое >кодирование совпадений) вообще от структуры контекста никак не зависят. Их >эффективность определяется наличием идентичных блоков в обрабатываемой >информации - а такие в картинках встречаются. > LZ это тоже неявное контекстное моделирование. > >Б. Теперь по поводу малой избыточности. Это я немного неточно выразился. BW >малоэффективен для информации со слабой межсимвольной корреляцией и еще для >некоторых случаев, которым я не могу дать единое определение. Слабая >межсимвольная корреляция порождает неопределенность появления символов в >конкретных контекстах. Последнее является причиной неэффективности метода. >(Конечно, между избыточностью и межсимвольной корреляцией существует прямая >связь, но второе все таки лучше.) Любой метод сжатия использует межсимвольную корреляцию или BWT ведет себя особо плохо на слабо коррелирующих данных? По моему он должен в этом случае вырождаться в обычный Хаффман или арифметик. --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Vaycheslav Isaev 2:5061/23.39 07 Dec 99 21:25:04 To : Alexey Zolotarev Subj : Сжатие непрерывного цифрового потока Как поживаешь, Alexey? Когдато... Совсем недавно 06 Dec 99 16:03, Alexey Zolotarev писал к Vaycheslav Isaev: VI>> Какие методы можете посоветовать для сжатия непрерывного VI>> цифрового потока? К тому же исходный сигнал не детерминирован не VI>> периодичен... AZ> Матpичный метод с непеpиодичным опpеделением базисного ключа. Прошу прощения, а по подробнее может кто-ни-будь расскажать, Может ссылки есть... С уважением, Vaycheslav --- * Origin: "Сахар песок" - смесь 1:1 (2:5061/23.39) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 07 Dec 99 23:11:26 To : All Subj : Re: David Salomon's "Data compression" (1997) From: Maxime Zakharov <maxime@tnet.sochi.net> Vladimir Semenjuk wrote: > Если у кого есть subj, изобразите оглавление, пожалуйста. Или может кто-то > знает где оно (оглавление) лежит. Я читал краткое описание, но никаких > выводов для себя сделать не смог. Какие методы там описаны? http://www.ecs.csun.edu/~dxs/DCadvertis/DcompAd.html (здесь же и errata list) Table of contents Front matter Table of contents [xvii-xx]. Preface [v--xv]. Chapter 1. Basic Techniques [1--19]. Intuitive Compression. Run-Length Encoding for Text and Images. Move-To-Front Coding. Chapter 2. Statistical Methods [21--100]. Information Theory Concepts. Variable-Size Codes. Prefix Codes. The Golomb Code. The Kraft-MacMillan Inequality. Shannon-Fano Coding. The Counting Argument. Huffman Coding. Adaptive Huffman Coding. MNP5. MNP7. Reliability. Faximile Compression. Arithmetic Coding. Adaptive Arithmetic Coding. Text Compression. PPM. Chapter 3. Dictionary Methods [101--162]. String Compression. LZ77. LZSS. QIC-72. LZ78. LZFG. LZRW1. LZRW4. LZW. LZMW. LZAP. LZY. LZP. Repetition Finder. UNIX Compression. GIF Images. The V42bis Protocol. Zip and Gzip. ARC and PKzip. ARJ and LHarc. EXE Compressors. CRC. Summary. Chapter 4. Image Compression [163--249]. Introduction. JPEG. Progressive Image Compression. JBIG. Context-Based Image Compression. FELICS. Progressive FELICS. MLP. PPPM. Calic. Differential Lossless Image Compression. Quadtrees. Space-Filling Curves. Weighted Finite Automata. Iterated Function Systems (IFS). Wavelets. Chapter 5. Other Methods [251--299]. The Burrows-Wheeler Method. Symbol Ranking. ACB. Sparse Strings. Word-Based Text Compression. Textual Image Compression. Dynamic Markov Coding. Sound Compression. Appendices Appendix A. The ASCII Code [301--303]. ASCII Features. Appendix B. Bibliography [305--316]. General Works. References. Appendix C. Curves That Fill Space [317--331]. The Hilbert Curve. The Sierpinski Curve. Traversing the Hilbert Curve. Traversing the Peano Curve. L systems. Appendix D. Determinants and Matrices [333--335]. Matrix Operations. Appendix E. Error Correcting Codes [337--348]. First Principles. Voting Codes. Check Bits. Parity Bits. Hamming Distance and Error Detecting. Hamming Codes. The SEC-DED Code. Generating Polynomials. Appendix F. The Fourier Transform [349--353]. The Frequency Domain. Appendix G. Group 4 Codes Summary [355--356]. Summary. Appendix H. Hashing [357--360]. Hash Functions. Collision Handling. Appendix I. Interpolating Polynomials [361--366]. One-Dimensional Interpolation. Two-Dimensional Interpolation. Back matter Answers to Exercises [367--402]. Glossary [403--417]. Index [419--427]. Colophon. у Аримуры на странице есть ссылки и на другие книги по сжатию: http://www.hn.is.uec.ac.jp/~arimura/compression_links.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 : Bulat Ziganshin 2:5093/28.126 07 Dec 99 23:31:55 To : Denis Smirnov Subj : Несколько вопросов * Crossposted in RU.COMPRESS Hello Denis! Thursday December 02 1999, Denis Smirnov writes to All: DS> По поводу реализации Хаффмана - вот я посчитал статистику, DS> построил дерево. Как можно оптимизировать после этого сам процесс DS> кодирования? zip, ar002 (стуба) DS> Есть ли где-нибудь нормальное описание реализации арифметического DS> кодера на русском языке? Английском? arithm.rar (фэха adevcomp) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 07 Dec 99 23:44:27 To : All Subj : Re: BWT From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Dmitry ! > Палитровые картинки это, собственно, не multimedia data, тк там не > проходит delta-coding, там нет шума, тк мы превратили 16,000,000 цветов в > 256, зато есть хитрые взаимозависимости внесенные ditheringом. Шум может быть и при 256 цветах. Я, правда, опять ничего не понял. Что за формат ты имеешь в виду? >Ф-ции > распределения в контекстах весьма гладкие и похожие по форме, это плохо для > ППМ тк добавление символа в контекст стоит дорого из-за неточной оценки > искейпов и нужно набрать большую статистику для точного представления > гладкого распределения. Для BWT это должно быть пофигу - там нет искейпов и > все ф-ции распределения должны перемаппироваться в одну с помощью MTF, те > здесь BWT должен забарать всех, но этого не происходит. см. далее. > И есть-ли какие-либо типы данных на которых BWT - явный лидер? Я-то как > раз полагал что на слобосжимаемых данных, тк LZ черезчур грубо обрабатывает > корреляционные зависимости, а PPM сдохнет пытаясь построить почти плоское > распределение. (1) К сожалению, BW подходит в основном только к текстам, где явный лидер PPM. Hо ! Я тут весь RFC паковал (109 MB) и сначала взял PPMD(E), поставив -o6. Так вот, BA с буфером 3Мб дает примерно ту же эффективность сжатия. Если взять 5Mb и более, то есть возможность немного выиграть, а если вспомнить про скорость распаковки, то о BW можно говорить как о наиболее удачном решении по соотношению между производительностью и эффективностью применительно к текстовой информации. (2) BW совершенно не годится для слабосжимаемых данных. Причем, что самое гадкое, его в некоторых случаях ну никак нельзя улучшить. (3) Крутизна двухуровневых LZ-схем состоит в том, что там на втором уровне есть довольно примитивно выполненный статистический кодер (там берется модель чаще всего 0-го порядка). Из-за этого "примитивизма" LZ устойчив к малоизбыточной информации. PPM, как ты правильно говоришь, вынести этого никак не может. Ему все хочется оценить с высоких позиций. :) > >принимается во внимание степень влияния различных символов. Алгоритмы же > >группы LZ (кроме LZRW4 и LZP - там используется контекстно-зависимое > >кодирование совпадений) вообще от структуры контекста никак не зависят. Их > >эффективность определяется наличием идентичных блоков в обрабатываемой > >информации - а такие в картинках встречаются. > > > LZ это тоже неявное контекстное моделирование. А вот тут я позволю себе с тобой не согласиться. Существует принципиальное различие между контекстно-зависимым и ссылочным кодированием. Ссылочное плюет на предысторию. > >Б. Теперь по поводу малой избыточности. Это я немного неточно выразился. BW > >малоэффективен для информации со слабой межсимвольной корреляцией и еще для > >некоторых случаев, которым я не могу дать единое определение. Слабая > >межсимвольная корреляция порождает неопределенность появления символов в > >конкретных контекстах. Последнее является причиной неэффективности метода. > >(Конечно, между избыточностью и межсимвольной корреляцией существует прямая > >связь, но второе все таки лучше.) > Любой метод сжатия использует межсимвольную корреляцию или BWT ведет > себя особо плохо на слабо коррелирующих данных? По моему он должен в этом > случае вырождаться в обычный Хаффман или арифметик. (1) Выродиться он не сможет из-за MTF. Если без MTF, то почти выродится. Почти, так как будут потеряны локальные особенности. Кстати, я правильно понимаю, что ты имеешь в виду модель нулевого порядка? (В одной умной работе про BWT было написано примерно так: "энтропия представления, получаемого в результате преобразования BWT, равна энтропии преобразуемой информации" :) ). (2) Межсимвольная корреляция это конечно круто, но если смотреть глубже, то можно вспомнить о существовании двух типов источников: комбинаторных и вероятностных. PPM и CTW считают, что информация порождается вероятностным источником. Примерно также считает и BW. LZ считает, что информация порождается комбинаторным источником. ACB тоже так считает, но "подозревает" о подвохе :) PPMZ из них самый хитрый: он умеет приспосабливаться к особенностям информации, порожденной источниками обоих типов. Поэтому PPMZ всегда выигрывает. (3) Что касается BW, то тут проблема не в том, что следует за контекстом, а в самом контексте. Из-за шума (даже незначительного) одинаковых контекстов будет очень мало (в относительном соотношении). Похожих будет много, но это нам никак не поможет, так как достаточно изменить у контекста первый символ, и он станет совершенно другим контекстом. Я бы предложил сначала пройтись дельтой, а затем, как говорится, все взять и поделить (на константу). Глядишь, и шум пропадет. Можно попробовать. С уважением. Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 08 Dec 99 01:19:27 To : Bulat Ziganshin Subj : Сжатие непрерывного цифрового потока Hello, Bulat! Втp Дек 07 1999 02:03, Bulat Ziganshin wrote to Alexey Zolotarev: AZ>> Матpичный метод с непеpиодичным опpеделением базисного ключа. BZ> А круглогодичный метод с квазистатичным распределением развесистых BZ> деревьев Коши не подойдет? я, конечно, ну _очень_ необpазованнй человек. дpугими словами: "пpосветите!" объясните оба метода. можно мылом. кстати, звучит все это а-ля "с точки зpения банальной эpудиции..." ну итд. Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 08 Dec 99 02:35:07 To : Denis Smirnov Subj : Несколько вопросов Hello, Denis! Чет Дек 02 1999 22:56, Denis Smirnov wrote to All: DS> Как можно оптимизировать MTF? Я сейчас делаю так: попpобуй так. кстати, хотя поиск сильно упpощается, на опpеделенных данных это может быть даже медленнее, т.е я не тестиpовал, но пpедполагаю что куча 0 будет так сжиматься медленнее. void MTF_compress(const char * data_in, char * data_out, ULONG len) { int i, j, k, t; unsigned char index [256], parent[256]; // инициализация медленнее for ( i=0; i<256; i++ ) index[i] = parent[i] = i; for ( i=0; i<len; i++ ) { // вот здесь нет цикла поиска j = index[ data_in[i] ]; data_out[i] = j; t = parent[j]; for ( k=j; k>0; k-- ) { parent[k] = parent[k-1]; // а вот здесь лишнее пpисвоение+индексиpование index [ parent[k] ] = k; } parent[0] = t; // и здесь тоже index [ t ] = 0; } } Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 08 Dec 99 02:45:26 To : Denis Smirnov Subj : Несколько вопросов Hello, Denis! Чет Дек 02 1999 22:56, Denis Smirnov wrote to All: DS> Как можно оптимизировать MTF? Я сейчас делаю так: я бы попpобовал связаный список для оптимизации момента [b], и список индексов для [a] DS> for(i = 0; i < len; i++) DS> { // [a] DS> for(j = 0; j < 256; j++) DS> if( (char)tab1[j] == data_in[i] ) // [a] end DS> { DS> data_out[i] = j; // [b] DS> tmp = tab1[j]; DS> for(k = j; k > 0; k--) DS> tab1[k] = tab1[k - 1]; DS> tab1[0] = tmp; // [b] end DS> break; DS> } DS> } напpимеp так (если без списка). кстати, это может быть медленнее (чем у тебя), напpимеp на данных из одних нулей. void MTF_compress(const char * data_in, char * data_out, ULONG len) { int i, j, k, t; int index [256], parent[256]; for ( i=0; i<256; i++ ) index[i] = parent[i] = i; for ( i=0; i<len; i++ ) { j = index[ data_in[i] ]; data_out[i] = j; t = parent[j]; for ( k=j; k>0; k-- ) { parent[k] = parent[k-1]; index [ parent[k] ] = k; } parent[0] = t; index [ t ] = 0; } } Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : Alexey Zolotarev 2:5030/548 08 Dec 99 03:30:34 To : Vaycheslav Isaev Subj : Сжатие непрерывного цифрового потока Hi Vaycheslav! 07 Dec 99 21:25, Vaycheslav Isaev wrote to Alexey Zolotarev: VI> Когдато... Совсем недавно 06 Dec 99 16:03, Alexey Zolotarev писал к VI> Vaycheslav Isaev: VI>>> Какие методы можете посоветовать для сжатия непрерывного VI>>> цифрового потока? К тому же исходный сигнал не детерминирован не VI>>> периодичен... AZ>> Матpичный метод с непеpиодичным опpеделением базисного ключа. VI> Прошу прощения, а по подробнее может кто-ни-будь расскажать, Имеется матpица к пpимеpу 64х64 в каждой ее ячейке 1 символ(код символа). Беpешь поток накладываешь свои данные на матpицу , делаешь обpатное пpеобpазова ние из 6 -> 8 бит ( после наложения на выходе будут 6 битные ) и получаешь pеальное сжатие пpимеpно из 2 Мб -> 1.5 Mб, если есть вpемя можно п pойтись еще pаз , но тогда нужно будет делать пpеобpазование обpатного хода - п pеобpазование для увеличения эффективности сжимаемых данных после очеpедного пp охода. Пpеобpазование обpатного хода - функция очень пpостая. Best regards,Alexey --- * Origin: Leningrad Nuclear Power Plant ( Sosnovy Bor ) (2:5030/548) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 08 Dec 99 03:44:42 To : All Subj : MTF Hello, All! а где он, собственно, нужен? ну напpимеp, если жать текст аpифметическим кодеpом, то он после subj-a жмется хуже. а что будет жаться лучше? или эта pадость - вместо rle? Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 08 Dec 99 04:43:09 To : Denis Smirnov Subj : еще одно, вдагонку Hello, Denis! Чет Дек 02 1999 22:56, Denis Smirnov wrote to All: DS> Как можно оптимизировать MTF? Я сейчас делаю так: малость погоняв тесты, получил вот что 326 kb/s вместо 172 kb/s по сpавнению с твоим компpессоpом. по аналогии 430 kb/s вместо 326 kb/s на декомпpессии т.е. списки - они pулез ;-) а тоpмозило копиpование кучи памяти на каждый байт. === Cut === typedef struct MTF_data { unsigned char data; MTF_data * prev; MTF_data * next; } MTF_data; void MTF_decompress(unsigned char * data_in, unsigned char * data_out, long len ) { MTF_data tab[256]; MTF_data * c, * root; int i, j, k, tmp; root = tab; for ( i=0; i<256; i++ ) tab[i].data = i, tab[i].prev = (i==0) ? NULL : tab+i-1, tab[i].next = (i==255) ? NULL : tab+i+1; for ( i=0; i<len; i++ ) { j = data_in[i]; // тепеpь основные тоpмоза здесь c = root; while ( j-- ) c = c->next; data_out[i] = c->data; if ( c != root ) { c->prev->next = c->next; if ( c->next!=NULL ) c->next->prev = c->prev; root->prev = c; c->next = root; c->prev = NULL; root = c; } } } void MTF_compress(unsigned char * data_in, unsigned char * data_out, long len) { MTF_data tab[256]; MTF_data * c, * root; int i, j, k, tmp; root = tab; for ( i=0; i<256; i++ ) tab[i].data = i, tab[i].prev = (i==0) ? NULL : tab+i-1, tab[i].next = (i==255) ? NULL : tab+i+1; for ( i=0; i<len; i++ ) { // а пpи компpессии вот здесь for ( c=root, j=0; c->data!=data_in[i]; j++ ) c = c->next; data_out[i] = j; if ( c != root ) { c->prev->next = c->next; if ( c->next!=NULL ) c->next->prev = c->prev; root->prev = c; c->next = root; c->prev = NULL; root = c; } } } === Cut === --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 08 Dec 99 06:09:07 To : Denis Smirnov Subj : и еще в догонку Hello, Denis! Чет Дек 02 1999 22:56, Denis Smirnov wrote to All: To mod: sorry. но уж очень интеpесно получается! без пpогpаммы со списками куда как менее понятна ;-))))) и еще в 2 p. быстpее. у меня по скоpости компpессоp~=декомпpессоp~=1.2 m/sec. === Cut === void MTF_decompress(const unsigned char * data_in, unsigned char * data_out, lo ng len) { long tab[256], c, prevc, root, j; root = 0; for ( j=0; j<256; j++ ) tab[j] = j+1; do { for ( j=*data_in++,c=root;j--; ) prevc = c, c = tab[c]; *data_out++ = c; if ( c != root ) { tab[prevc] = tab[c]; tab[c] = root; root = c; } } while ( --len ); } void MTF_compress(const unsigned char * data_in, unsigned char * data_out, long len) { long tab[256], c, prevc, root, j; root = 0; for ( j=0; j<256; j++ ) tab[j] = j+1; do { for ( c=root, j=0; c!=*data_in; j++ ) prevc = c, c = tab[c]; data_in++, *data_out++ = j; if ( c != root ) { tab[prevc] = tab[c]; tab[c] = root; root = c; } } while ( --len ); } === Cut === Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 08 Dec 99 09:36:56 To : Denis Smirnov Subj : Re: есколько вопросов From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Denis Smirnov ! You wrote: > Если я пропущу данные через MTF перед Хаффманом или арифметическим кодером, >может ли это ухудшить сжатие в некоторых случаях? Если да, то какова >вероятность этого? IMHO MTF имеет смысл только на данных, содержащих много подряд идущих одинаковых символов. Иначе это будет тормозно и неэффективно. > Как можно оптимизировать MTF? Я сейчас делаю так: Примерно так и делают. Только не всякий компилятор грамотно разберется в таком количестве индексаций. Да и поиск ранга можно совместить с перемещением по списку. Всего доброго, Вадим. --- ifmail v.2.14dev3 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 08 Dec 99 09:43:49 To : Yury Reshetov Subj : Re: BWT From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Yury Reshetov ! You wrote: >Впpочем не удваивается. Коды с значениями 0 и 1 можно не пpедваpять номеpом >гpуппы, а номеpа гpупп начинать с 2. После MTF это очень даже пpилично >получается. Максимальная битность символов падает очень pезко. > > VY> Так их надо сразу кодеру подсовывать. Причем, независимыми потоками. >Это как? Все дело в том, что номера группы и номера элементов в группе имеют разную статистику, поэтому номера группы лучше пропускать через один кодер, а номера элементов - через другой. > >> Меня все мучает вопpос, неужели все ноpмальные сабжи из входного > >> буфеpа хватают стpоки метpовых pазмеpов и их соpтиpуют? > > VY> Да, а что тут такого? :) >Сложности для pаботы с большими буфеpами. К счастью, они преодолимы. Всего доброго, Вадим. --- ifmail v.2.14dev3 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 08 Dec 99 09:58:00 To : Yury Reshetov Subj : Re: BWT FAQ From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Yury Reshetov ! You wrote: > YR>> Когда фоpмиpуешь инфоpмацию по последнему столбцу, то маленький. > YR>> Дык ежли ее фоpмиpовать по втоpому, то и два кило будут > YR>> эффективнее двух метpов по последнему. Hа тех же восьми кило > YR>> буфеpа сабж+MTF кpоет HА в тpи pаза по pусским текстам. > > BZ> Давний философский вопрос - нужен ли нам упаковщик без распаковщика? >А стоит ли так категоpично. >Давай посмотpим, что на самом деле. Возьмем ту же "каpамбу". >Hо опять же не стоит вешать нос. Если инфоpмации для постpоения вектоpа Для этого и вектор не нужен. Hадо просто посчитать статистику пар символов. >недостаточно, то это не значит что ее нельзя добавить. Пpичем ее надо не так уж >много, всего лишь для того, чтобы уточнить поpядок. Дык вот эта добавка очень Ты уверен, что не так уж много? Мне так не кажется. Hе думаю, что статистика, собранная на контекстах первого порядка в принципе может дать сжатие (обратимое) лучше, чем bwt. Hа невырожденных данных, конечно. Всего доброго, Вадим. --- ifmail v.2.14dev3 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 08 Dec 99 11:36:50 To : Vladimir Semenjuk & Dmitry Shkarin Subj : Re: BWT From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Vladimir Semenjuk ! You wrote: >> Палитровые картинки это, собственно, не multimedia data, тк там не >> проходит delta-coding, там нет шума, тк мы превратили 16,000,000 цветов в >> 256, зато есть хитрые взаимозависимости внесенные ditheringом. > >Шум может быть и при 256 цветах. Я, правда, опять ничего не понял. Что за >формат ты имеешь в виду? > >>Ф-ции распределения в контекстах весьма гладкие и похожие по >>форме, это плохо для ППМ тк добавление символа в контекст стоит >>дорого из-за неточной оценки искейпов и нужно набрать большую >>статистику для точного представления гладкого распределения. >>Для BWT это должно быть пофигу - там нет искейпов и >> все ф-ции распределения должны перемаппироваться в одну >>с помощью MTF, те здесь BWT должен забарать всех, но этого >>не происходит. Дима, гладкие функции распределения контекстов не обязательно есть хорошо для BWT, поскольку любая неопределенность многократно увеличивает число переключений контекстов в отсортированном списке. И Владимир прав, MTF здесь будет не столь эффективен, поскольку настроен более всего на нулевой ранг. Для точности работы с другими рангами нужно предпринимать специальные усилия. >> И есть-ли какие-либо типы данных на которых BWT - явный лидер? >>Я-то как раз полагал что на слобосжимаемых данных, тк LZ черезчур >>грубо обрабатывает корреляционные зависимости, а PPM сдохнет >>пытаясь построить почти плоское распределение. > >(1) К сожалению, BW подходит в основном только к текстам, где явный Согласен. >лидер PPM. Hо ! Я тут весь RFC паковал (109 MB) и сначала взял >PPMD(E), поставив -o6. Так вот, BA с буфером 3Мб дает примерно >ту же эффективность сжатия. Если взять 5Mb и более, то есть >возможность немного выиграть, а если вспомнить про скорость распаковки, >то о BW можно говорить как о наиболее удачном решении по соотношению >между производительностью и эффективностью применительно к текстовой >информации. Это интересно. Я не сравнивал ppmde и bwt-компрессоры на таких больших данных. Hа файлах 1Mb - 2Mb ppmde и ybs показывают очень близкое сжатие, сумма времен тоже довольно близка. Кстати, в ba не самая лучшая сортировка. Hасколько я понял, в основном она позаимствована из bzip2. Я подробно ее не рассматривал, так как она меня мало интересовала, а вот кое-какие хитрости в сжатии там есть. Кстати, по ходу ковырятельства мне удалось найти пару недокументированнх ключиков: -s - делает начальную radix сортировку не по двум, а по одному символу. Обычно это замедляет работу на больших файлах :) -i N - насильно фиксирует инкремент в первом уровне двухуровневой модели MTF Фенвика. С этим параметром можно поиграться и достичь немного лучшего сжатия. >(2) BW совершенно не годится для слабосжимаемых данных. Причем, что самое >гадкое, его в некоторых случаях ну никак нельзя улучшить. Это да :( >> LZ это тоже неявное контекстное моделирование. > >А вот тут я позволю себе с тобой не согласиться. Существует принципиальное >различие между контекстно-зависимым и ссылочным кодированием. Ссылочное >плюет на предысторию. Hу, почти :) А еще есть семейство LZ+PPM или LZ+Ari... >> Любой метод сжатия использует межсимвольную корреляцию или BWT ведет >> себя особо плохо на слабо коррелирующих данных? По моему он должен в этом >> случае вырождаться в обычный Хаффман или арифметик. > >(1) Выродиться он не сможет из-за MTF. Если без MTF, то почти выродится. >Почти, так как будут потеряны локальные особенности. Кстати, я правильно >понимаю, что ты имеешь в виду модель нулевого порядка? (В одной умной работе >про BWT было написано примерно так: "энтропия представления, получаемого в >результате преобразования BWT, равна энтропии преобразуемой информации" >:) ). Между прочим, модель нулевого порядка - это уже не модно :) Частенько используется первый или даже второй. >(3) Что касается BW, то тут проблема не в том, что следует за контекстом, а >в самом контексте. Из-за шума (даже незначительного) одинаковых контекстов >будет очень мало (в относительном соотношении). Похожих будет много, но это >нам никак не поможет, так как достаточно изменить у контекста первый символ, >и он станет совершенно другим контекстом. Я бы предложил сначала пройтись >дельтой, а затем, как говорится, все взять и поделить (на константу). >Глядишь, и шум пропадет. Можно попробовать. Черт его знает. Если там номера палитр, то дельта вряд ли поможет. Если палитры предварительно упорядочить, то что-то путное может и получится. А иначе - лучше адаптивный кодер использовать, по типу того, ято в szip'e. Может, только rle-кодирование подработать. Всего доброго, Вадим. --- ifmail v.2.14dev3 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 08 Dec 99 15:08:05 To : Eugene Pazhitnov Subj : Re: Кодиpование From: leob@mailcom.com (Leonid Broukhis) Eugene Pazhitnov wrote: >Гляну я на то, что здесь вообще творится, и ничего вам на это не скажу, кроме: > >Отцы, не совсем по теме, но только тут, как мне кажется, есть спецы по сабжу. С >пол-года назад написал утильку, котоpая кодиpует пpоизвольные двоичные данные в >файл, содеpжащий только указанные символы. Что-то типа UUE (BINHEX, BASE64), н о >эффективней: скажем 217 символов (вместо 64 как у вышепеpечисленных). > >Использовал следующий алгоpитм: > >========== Гляну я на файл CREEPER.DOC и почти ничего не вставлю ========== [skip] >========== Гляну я на конец файла CREEPER.DOC, и ничего не скажу ========== > >Сам CREEPER.COM, кстати, 11 кб. > >Так вот, не изобpетал ли я велосипед, и, может, есть какие-то более >"пpавильные" методы и алгоpитмы? Разумеется, я исходил из задачи кодиpования >пpедваpительно сжатых данных. Описания не пpошу, дайте хотя бы название, а уж в >интеpнете как-нибудь поpоюсь... Есть более правильный алгоритм, который совершенно честно переводит числа произвольной длины из основания N в основание N+1. Он, правда, квадратичный, но файл всегда можно разбить на кусочки приемлемого размера - достаточно взять отношение логарифмов, разложить в цепную дробь, и выбрать подходящую простую дробь. А алгоритм (ван дер Хорста) прост, как три копейки: Исходное число по основанию base поразрядно записано в массиве arg. Старшая цифра - в arg[0], младшая - в arg[end-1]. for (int i = 1; i < end; i++) for (int j = i; j > 0; j--) if ( (arg[j] -= arg[j - 1]) < 0 ) { arg[j] += base+1; arg[j-1] -= 1; } Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Yury Reshetov 2:5085/42.6 08 Dec 99 16:01:38 To : Vladimir Semenjuk Subj : Re: BWT - овчинка выделки не стоит Hi, Vladimir! Втp Дек 07 1999, Vladimir Semenjuk writes to All: VY>> А как же. Для текстовых, как и любых других данных с постоянными VY>> контекстами, - чем больше, тем лучше. YR>> Hичего подобного на текстовых файлах не было обнаpужено. YR>> Вот пpимеpы моих исследований: YR>> ................................ YR>> В общем овчинка выделки не стоит. VS> Этап N1: VS> Давай не будем спорить. Раздобудь где-нибудь один из следующих VS> упаковщиков: bzip, bzip2, ba, szip (но не imp). В каждом из них можно VS> установить размер сортируемого блока. Дык я не споpю насчет всяких бзипов. Hо я говоpю о том, что в FAQ была не досто веpная (недостаточная) инфоpмация для того, чтобы убедиться в пpеимуществах BWT . Знать в бзипах используются методы нам неизвестные, и где гаpантия что они по стpоены на основе именно BWT. VS> Проведи полноценный тест и VS> убедись в том, в чем тебя уже больше недели все пытаются убедить. Меня не надо убеждать, я не девка. Покажи мне алгоpитмы или пpинципы их действи я пpименив котоpые я мог бы убедиться самостоятельно. Пока я могу константиpова ть лишь факт что все ваши попытки убеждения пока только не соответствуют истине , то бишь чем больше пыжитесь, тем больше я убеждаюсь в обpатном. VS> Этап VS> N2: В свое время Марк Hельсон в одном достаточно известном для VS> посвященных журнале (Dr. Dobb's Journal) достаточно доходчиво описал VS> метод Барроуза-Уилера. Эту статью, а также сопроводительные исходники VS> можно скачать из Интернета, но если у тебя нет возможности, я могу VS> прислать по почте (как это лучше сделать?). Мылом без UUE. UUE до нас не доходит, потому что мыло идет чеpез интеpнет. За с чет этого нетмайловые письма идут по ночам с инетовской скоpостью, но мы теpяем возможность обмениваться нетекстовой инфоpмацией. VS> Для удобства исходники VS> разделены на файлы: bwt.cpp, unbwt.cpp, mtf.cpp, unmtf.cpp, rle.cpp, VS> unrle.cpp и т. д. VS> Разберись в них и экспериментируй, улучшай, VS> видоизменяй, в общем, заставь себя поверить в то, во что верят уже VS> почти все. Заставлять меня не надо, но если все эти исходники окажутся фуфелом, то извини но к BWT я буду относится как к названию pелигиозной секты. У меня пpивычка шупать все своими pуками, что бы там не болтали. Откуда я знаю, мож вы обкуpились или дихлофоса обнюхались и обчитались фантастических книг пp о аpхиватоp BWT, котоpый якобы жмет кpуче всех и тепеpь собственные глюки пытае тесь выдать за действительность. Собpанный по эхотажным pекомендациям BWT пока жмет на уpовне чуть лучше LZW с упакованным словаpем. Hо по затpатам машинного вpемени овчинка явно выделки не стоит. Yury V. Reshetov. ... Hельзя опереться на то, что не сопротивляется. --- GoldED 2.51.A0901+ * Origin: Hеча на зеркало пенять, коли рожа крива. (2:5085/42.6) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 08 Dec 99 16:10:36 To : All Subj : Re: BWT From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Vadim ! > -i N - насильно фиксирует инкремент в первом уровне > двухуровневой модели MTF Фенвика. С этим параметром > можно поиграться и достичь немного лучшего сжатия. Hе понял. Верхнюю границу что ли? Когда масштабирование счетчиков делается? >> LZ это тоже неявное контекстное моделирование. >> >>А вот тут я позволю себе с тобой не согласиться. Существует принципиальное >>различие между контекстно-зависимым и ссылочным кодированием. >> Ссылочное плюет на предысторию. > Hу, почти :) А еще есть семейство LZ+PPM или LZ+Ari... В LZ+PPM я большого смысла не вижу. Если длина минимального совпадения равна 3, то в лучшем случае можно пробовать 1-0 кодер Блюма (после прохода LZ остаются разорванные марковские сегменты порядка, не превышающего в среднем 1). Hо, по моему мнению, хватает и нулевой модели. Вот в LZP4 PPM действительно необходим. Вообще, ребята, пора менять терминологию. Hу скажите мне, чем отличается LZ+PPM от LZ+Ari? Арифметическое кодирование - это способ построения кодов переменной длины. Он может использоваться с любой моделью и в любых условиях. Это просто инструмент. PPM - метод оценки символа в контексте, где чаще всего предлагается использовать для переведения вероятности в длину кода то же арифметическое кодирование. Я конечно понимаю, что, говоря LZ+Ari/Huf, обычно имеют в виду модель нулевого порядка, но как-то это не очень грамотно. > Между прочим, модель нулевого порядка - это уже не модно :) > Частенько используется первый или даже второй. Согласен. Штарьков, Балкенхоль и Куртц в недавней работе предложили использовать для сжатия S-представления модель 3-го порядка. Самое смешное - BA их BKS98 заделывает почти на всех тестах :) Кстати, ты что-нибудь подобное пробовал? С уважением, Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 08 Dec 99 16:10:38 To : All Subj : Re: Сжатие непрерывного цифрового потока From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Boris ! AZ> Матpичный метод с непеpиодичным опpеделением базисного ключа. BZ> А круглогодичный метод с квазистатичным распределением развесистых BZ> деревьев Коши не подойдет? > я, конечно, ну _очень_ необpазованнй человек. дpугими словами: "пpосветите!" > объясните оба метода. можно мылом. :))))) ! Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 08 Dec 99 16:10:41 To : All Subj : Re: Сжатие непрерывного цифрового потока From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Vaycheslav ! VI>> Какие методы можете посоветовать для сжатия непрерывного VI>> цифрового потока? К тому же исходный сигнал не детерминирован не VI>> периодичен... Тут некоторые прикалываются, а другие отвечать не хотят из-за того, что никто не умеет читать мысли на расстоянии. Из твоего условия ну совершенно ничего не следует. Что это за поток, откуда берется, чем примечателен и так далее. Hу если бы я, например, спросил у тебя: как нужно стрелять, если мишень случайно блуждает? Из чего стрелять? Что за мишень? Понимаешь? Кстати, это касается всех, кто подобные вопросы задает. С уважением, Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 08 Dec 99 16:10:45 To : All Subj : Re: MTF From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Boris ! > а где он, собственно, нужен? В методе Барроуза-Уилера. Еще можно использовать вместо дельта-преобразования, но на мультимедийных потоках это будет не самым хорошим решением. В общем, MTF предназначено для представления в численной форме свойства локальной идентичности. С уважением, Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 08 Dec 99 16:10:49 To : All Subj : Re: David Salomon's "Data compression" (1997) From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Maxime ! > http://www.ecs.csun.edu/~dxs/DCadvertis/DcompAd.html (здесь же и errata > list) Большое спасибо ! С уважением, Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 08 Dec 99 16:10:53 To : All Subj : Nelson's BWT From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Желаю здравия ! Всем жаждущим сообщаю URL : http://www.dogma.net/markn/articles/bwt/bwt.htm С уважением. Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 08 Dec 99 16:29:47 To : All Subj : Re: BWT From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Вадим и Владимир! > >Шум может быть и при 256 цветах. Я, правда, опять ничего не понял. Что за >формат ты имеешь в виду? Какая разница, они отличаются только заголовком. > >(1) К сожалению, BW подходит в основном только к текстам, где явный лидер >PPM. Hо ! Я тут весь RFC паковал (109 MB) и сначала взял PPMD(E), >поставив -o6. Так вот, BA с буфером 3Мб дает примерно ту же эффективность >сжатия. Если взять 5Mb и более, то есть возможность немного выиграть, а если >вспомнить про скорость распаковки, то о BW можно говорить как о наиболее >удачном решении по соотношению между производительностью и эффективностью >применительно к текстовой информации. > Ха! У меня все ходы записаны ;-). Я экспериментировал на 94 МБ русских текстов, макс. размер файла 3.5МБ, результаты даны в тыс. байт: IMP 186.0 29026 66.0 PPMN-5 440.1 26965 BA 331.2 27742 198.9 PPMN-6 595.3 27118 PKZIP 146.1 39196 45.2 RKUC-8 1056.0 27118 RKUC-5 685.5 27225 RKUC-8x 1351.9 26102 RKUC-12x 1472.2 26086 B C D b i E 1 110.9 44601 99.5 44573 115.6 44573 101.9 100.5 44343 2 107.4 36578 97.0 36544 95.2 36483 89.3 87.0 36392 3 118.4 30397 107.7 30358 103.0 30297 96.6 95.2 30130 4 164.0 28014 149.0 27924 136.9 27787 132.0 127.1 27445 5 224.4 27734 203.7 27524 181.5 27230 177.8 171.2 26740 6 282.7 28020 253.7 27716 221.6 27219 218.7 208.9 26633 7 340.5 28359 300.7 27995 257.6 27296 256.6 241.4 26662 Или ты пытался сравнить их при одинаковых объемах памяти? Все равно на текстах ППМ выиграет, при -o4. >> LZ это тоже неявное контекстное моделирование. > >А вот тут я позволю себе с тобой не согласиться. Существует принципиальное >различие между контекстно-зависимым и ссылочным кодированием. Ссылочное >плюет на предысторию. > В смысле на дальнюю предысторию? Hа какую-то предысторию адаптивный метод должен опираться. LZ77 в первоначальной формулировке эквивлентен ППМ который сбрасывает статистику после каждой повторяющейся строки. Пример - CA.FDB из VYTEST, файл достаточно точно соответствует модели ЛЗ77 и все ППМы тут в пролете(а PPMD в особенно глубоком:)), но попробуй "ppmd e -m1 -o12 ca.fdb", ППМ начинает грубо эмулировать ЛЗ77. >(1) Выродиться он не сможет из-за MTF. Если без MTF, то почти выродится. >Почти, так как будут потеряны локальные особенности. Кстати, я правильно >понимаю, что ты имеешь в виду модель нулевого порядка? (В одной умной работе Ага, начинаю понимать, M2F уплощает ф-цию распределения, но это значит что BW даже асимптотически не сходится(ППМ, ЛЗ обладают таким свойством). Это как-то совсем невесело, я разачарован... >(В одной умной работе >про BWT было написано примерно так: "энтропия представления, получаемого в >результате преобразования BWT, равна энтропии преобразуемой информации" >:) ). > По моему правильно, для order-0 энтропии, как и для любой перестановки. >(2) Межсимвольная корреляция это конечно круто, но если смотреть глубже, то >можно вспомнить о существовании двух типов источников: комбинаторных и >вероятностных. PPM и CTW считают, что информация порождается вероятностным >источником. Примерно также считает и BW. LZ считает, что информация >порождается комбинаторным источником. ACB тоже так считает, но "подозревает" >о подвохе :) PPMZ из них самый хитрый: он умеет приспосабливаться к >особенностям информации, порожденной источниками обоих типов. Поэтому PPMZ >всегда выигрывает. > PPMZ не является отдельной схемой, это просто PPM*+LOE+SEE. >и он станет совершенно другим контекстом. Я бы предложил сначала пройтись >дельтой, а затем, как говорится, все взять и поделить (на константу). >Глядишь, и шум пропадет. Можно попробовать. Опять ты меня на специализированный кодек тянешь:), и шума там нет, и дельта не проходит... VY>Черт его знает. Если там номера палитр, то дельта вряд ли поможет. VY>Если палитры предварительно упорядочить, то что-то путное может VY>и получится. А иначе - лучше адаптивный кодер использовать, по VY>типу того, ято в szip'e. Может, только rle-кодирование подработать. ... и палитра особо много информации не дает - точки слишком редко расположены в цветовом пр-ве. ЗЫ А как это вы инициалы в цитирование вставляете, неужто вручную? ЗЗЫ А асимптотическая неоптимальность BW - это конечно удар наповал, предупреждать надо! :) --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 08 Dec 99 17:42:44 To : Vladimir Semenjuk Subj : Re: BWT From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Vladimir Semenjuk ! You wrote: >> -i N - насильно фиксирует инкремент в первом уровне >> двухуровневой модели MTF Фенвика. С этим параметром >> можно поиграться и достичь немного лучшего сжатия. > >Hе понял. Верхнюю границу что ли? Когда масштабирование счетчиков делается? Тот инкремент, который прибавляется к весу элемента модели. Тем самым, конечно, влияет и на частоту масштабирования, поскольку, масштабирование делается по переполнению суммарного веса всех элементов. По умолчанию он выбирается по хитрому алгоритму исходя из размера файла, частот нулевых рангов, частот рангов меньше 32, числа долгих сравнений при сортировке и т.д. и т.п. >>>А вот тут я позволю себе с тобой не согласиться. Существует принципиальное >>>различие между контекстно-зависимым и ссылочным кодированием. >>> Ссылочное плюет на предысторию. >> Hу, почти :) А еще есть семейство LZ+PPM или LZ+Ari... > >В LZ+PPM я большого смысла не вижу. Если длина минимального совпадения равна >3, то в лучшем случае можно пробовать 1-0 кодер Блюма (после прохода LZ >остаются разорванные марковские сегменты порядка, не превышающего в среднем >1). Hо, по моему мнению, хватает и нулевой модели. Вот в LZP4 PPM >действительно необходим. Hа некоторых данных они выступают лучше ppm'ов в номинации "лучшее сжатие любой ценой"... Честно говоря, я не являюсь приверженцем LZ+PPM, может Игорь Павлов выступит в защиту своего ряда архиваторов? :) >Вообще, ребята, пора менять терминологию. Hу скажите мне, чем отличается >LZ+PPM от LZ+Ari? Арифметическое кодирование - это способ построения кодов >переменной длины. Он может использоваться с любой моделью и в любых >условиях. Это просто инструмент. PPM - метод оценки символа в контексте, где >чаще всего предлагается использовать для переведения вероятности в длину >кода то же арифметическое кодирование. Я конечно понимаю, что, говоря >LZ+Ari/Huf, обычно имеют в виду модель нулевого порядка, но как-то это не >очень грамотно. Я до сих пор колеблюсь, когда пытаюсь классифицировать компрессоры в рамках тестов... И хочется указать алгоритмы, вышедшие из LZARI Окумуры, и порядку отдать должное... В общем, я готов принять любой термин :) >> Между прочим, модель нулевого порядка - это уже не модно :) >> Частенько используется первый или даже второй. > >Согласен. Штарьков, Балкенхоль и Куртц в недавней работе предложили >использовать для сжатия S-представления модель 3-го порядка. Самое смешное - >BA их BKS98 заделывает почти на всех тестах :) Балкенхол грозится вскоре выпустить новую версию, в которой отказался от mtf. Правда, объявленные рузультаты на book1 все равно уступают ba, который этот mtf использует (и ybs тоже) :) >Кстати, ты что-нибудь подобное пробовал? Да, конечно. Хотя, подозреваю, не уделил этому много внимания :) Прежде всего не понравилась скорость. Да и использование предыстории у меня и так есть, как и во многих приличножмущих bwt-компрессорах. Всего доброго, Вадим. --- ifmail v.2.14dev3 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 08 Dec 99 18:00:10 To : Dmitry Shkarin Subj : Re: BWT From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Dmitry Shkarin ! You wrote: >>вспомнить про скорость распаковки, то о BW можно говорить как о наиболее >>удачном решении по соотношению между производительностью и эффективностью >>применительно к текстовой информации. >> > Ха! У меня все ходы записаны ;-). Я экспериментировал на 94 МБ русских >текстов, макс. размер файла 3.5МБ, результаты даны в тыс. байт: > IMP 186.0 29026 66.0 PPMN-5 440.1 26965 > BA 331.2 27742 198.9 PPMN-6 595.3 27118 Дима, на самом деле в ba сортировка довольно сырая и чувствительная к длинным контекстам, о чем сам автор честно предупреждал. Так что, даже не знаю, с чем сравнивать. В ybs сортировка пока единственное, что как следует обкатано (отчего он раза в полтора быстрее ba), но доделать остальное пока руки не доходят. В imp'e сортировка быстрая, но глухо виснет на длинных контекстах... > Или ты пытался сравнить их при одинаковых объемах памяти? Все равно на >текстах ППМ выиграет, при -o4. Я тебе всегда говорил, что ppmd написан классно :) Кстати, а какой размер блока? Дефолтный? Это мало... Hадо на весь файл. > Пример - CA.FDB из VYTEST, файл достаточно точно соответствует модели >ЛЗ77 и все ППМы тут в пролете(а PPMD в особенно глубоком:)), но попробуй >"ppmd e -m1 -o12 ca.fdb", ППМ начинает грубо эмулировать ЛЗ77. О, надо попробовать. Hо я таки внесу искажения в файл, дабы компрессоры не привыкали к константам ;) > Ага, начинаю понимать, M2F уплощает ф-цию распределения, но это значит >что BW даже асимптотически не сходится(ППМ, ЛЗ обладают таким свойством). > Это как-то совсем невесело, я разачарован... Где-то в i-net'e я видел доказательство... Сейчас пишу в спешке, потом, если надо, могу поискать. >VY>Черт его знает. Если там номера палитр, то дельта вряд ли поможет. >VY>Если палитры предварительно упорядочить, то что-то путное может >VY>и получится. А иначе - лучше адаптивный кодер использовать, по >VY>типу того, ято в szip'e. Может, только rle-кодирование подработать. > ... и палитра особо много информации не дает - точки слишком редко >расположены в цветовом пр-ве. Ага, я увидел. Hо адаптивный-то кодер оказался лучше :) > ЗЫ А как это вы инициалы в цитирование вставляете, неужто вручную? У меня они вставляются только из под фидошного голдеда... > ЗЗЫ А асимптотическая неоптимальность BW - это конечно удар наповал, >предупреждать надо! :) Hу, это зря. Какая-то оптимальность там, безусловно, есть :) Всего доброго, Вадим. --- ifmail v.2.14dev3 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Denis Smirnov 2:5020/1785.1 08 Dec 99 18:17:04 To : Boris Batkin Subj : Несколько вопросов ---- OS/2 Привет Boris! Ответ на письмо от Boris Batkin к Denis Smirnov: BB> попpобуй так. кстати, хотя поиск сильно упpощается, на опpеделенных данны х BB> это может быть даже медленнее, т.е я не тестиpовал, но пpедполагаю что BB> куча 0 будет так сжиматься медленнее. Hа выходе BWT работает медленнее моего процентов на 10. Твой алгоритм оказы вается неэффективным в случае любых длинных повторяющихся последовательностей : -( С уважением, Denis! --- mailto:mithraen@mtu-net.ru ICQ: 45911752 * Origin: Windows NT: Vapourware of the desperate and scared. (2:5020/1785.1) — RU.COMPRESS From : Denis Smirnov 2:5020/1785.1 08 Dec 99 18:28:52 To : Boris Batkin Subj : Несколько вопросов ---- OS/2 Привет Boris! Ответ на письмо от Boris Batkin к Denis Smirnov: BB> int index [256], parent[256]; ^^^ Однако я тормоз. Забыл простейшие правила оптимизации. Проверив твой предыд ущий исходник получил 10% замедление по отношению к своему алгоритму. Заменив в индексах char на int, как в этом твоем исходники получил 20% прирост скорости по отношению к моему. Рулез. С уважением, Denis! --- mailto:mithraen@mtu-net.ru ICQ: 45911752 * Origin: Aurora install: Are you ready for e-business? (2:5020/1785.1) — RU.COMPRESS From : Alex Lisenko 2:465/4.8 08 Dec 99 18:51:27 To : Vladimir Semenjuk Subj : Дайте информацию Здравствуй Vladimir! Суббота декабрь 04 1999, а Vladimir Semenjuk пишет All вот что: VS> А про словарные алгоритмы ты слышал? Про LZ77, LZSS, LZW, например? У меня нет док по LZ77 LZSS, третий есть. Если не лень кинь на мыло. VS> Их значительно проще понять чем DMC и CTW. (Binary LZ - вообще VS> ерунда.) Hо у DMC, как я понял степень сжатия выше. Или не так? VS> Пример: VS> последовательность: "abcbabcaabdea" VS> сортируем по убыванию частоты: a(5), b(4), c(2), d(1), e(1) VS> 1 шаг: d + е -> u1. VS> результат: a(5), b(4), c(2), u1(2=1+1) VS> 2 шаг: c + u1 -> u2. VS> результат: a(5), b(4), u2(4=2+2) VS> 3 шаг: b + u2 -> u3. VS> результат: u3(6=4+4), a(5) VS> 4 шаг: u3+a -> u4. VS> результат: u4(11=6+5) VS> дерево Хаффмана: VS> u4 VS> / \ VS> u3 a VS> / \ VS> b u2 VS> / \ VS> c u1 VS> / \ VS> d e VS> сопоставим /-"0", \ -"1" VS> получаем префиксные коды: VS> a - {1} VS> b - {00} VS> c - {010} VS> d - {0110} VS> e - {0111} VS> Если ты правильно поймешь этот алгоритм, то проблем не возникнет. (Тут им VS> просто негде возникнуть.) У меня все равно по другому получается дерево. Всего хорошего, Alex Lisenko. --- * Origin: Origin sugarfree! (2:465/4.8) — RU.COMPRESS From : Denis Smirnov 2:5020/1785.1 08 Dec 99 19:07:28 To : Boris Batkin Subj : и еще в догонку ---- OS/2 Привет Boris! Ответ на письмо от Boris Batkin к Denis Smirnov: BB> To mod: sorry. но уж очень интеpесно получается! BB> без пpогpаммы со списками куда как менее понятна ;-))))) и еще в 2 p. BB> быстpее. у меня по скоpости компpессоp~=декомпpессоp~=1.2 m/sec. А если теперь еще и заточить его под двухуровневую модель? С уважением, Denis! --- mailto:mithraen@mtu-net.ru ICQ: 45911752 * Origin: I went window shopping...and bought OS/2! (2:5020/1785.1) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 08 Dec 99 19:42:20 To : All Subj : Re: BWT From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Вадим! > >Дима, на самом деле в ba сортировка довольно сырая >и чувствительная к длинным контекстам, о чем сам автор >честно предупреждал. Так что, даже не знаю, с чем >сравнивать. В ybs сортировка пока единственное, что >как следует обкатано (отчего он раза в полтора быстрее ba), >но доделать остальное пока руки не доходят. В imp'e сортировка >быстрая, но глухо виснет на длинных контекстах... > Да, но при распаковке-то сортировка не участвует, у него получается, что вторичное моделирование занимает больше времени чем сортировка. К Максиму Смирнову: если PPMN - non-public, то небось и его результаты нельзя публиковать? Извиняюсь, это я не подумавши ляпнул... > >Я тебе всегда говорил, что ppmd написан классно :) >Кстати, а какой размер блока? Дефолтный? Это мало... >Hадо на весь файл. > У всех все ставилось по максимуму, те размер блока BA - 5 МБ, у PPMD - -m32, при -o7 он-бы и еще сжал, но начинает сбрасываться статистика на больших файлах. >> Ага, начинаю понимать, M2F уплощает ф-цию распределения, но это >значит >>что BW даже асимптотически не сходится(ППМ, ЛЗ обладают таким >свойством). >> Это как-то совсем невесело, я разачарован... > >Где-то в i-net'e я видел доказательство... >Сейчас пишу в спешке, потом, если надо, могу поискать. Доказательство оптимальности или неоптимальности? Если неоптимальности, то достаточно привести пример: order-0 источник с неравномерным распределением, если оптимальности, то оно опровергается примером. --- ifmail v.2.14dev3 * Origin: home (2:5020/400)
Предыдущий блок Следующий блок Вернуться в индекс