| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Leonid Broukhis 2:5020/400 08 Dec 99 20:29:54 To : Vadim Yoockin Subj : Re: есколько вопросов From: leob@mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: >IMHO MTF имеет смысл только на данных, содержащих >много подряд идущих одинаковых символов. Или символов из маленького подмножества алфавита. АБАБАБАБАБ MTF-у отлично поддаются. >Иначе это будет тормозно и неэффективно. >> Как можно оптимизировать MTF? Я сейчас делаю так: >Примерно так и делают. Только не всякий >компилятор грамотно разберется в таком >количестве индексаций. Да и поиск ранга Ты очень плохого мнения о компиляторах. Тебе, наверное, хороших не попадалось. >можно совместить с перемещением по списку. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 08 Dec 99 20:29:57 To : Leonid Broukhis Subj : Re: Кодиpование From: leob@mailcom.com (Leonid Broukhis) Leonid Broukhis wrote: >Есть более правильный алгоритм, который совершенно честно переводит >числа произвольной длины из основания 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; > } Если тут есть лица, приближенные к математике, то не могли бы они, во-первых, доказать этот алгоритм, и, во-вторых, нарисовать обратный (конверсия из основания N в основание N-1). А то от 128 до 217 подниматься дольше и гораздо менее удобно, чем от 256 до 217 спускаться. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Nickita Startcev 2:5030/885.13 08 Dec 99 21:59:37 To : All Subj : Вопрос Привет, All ! Есть большая (3000x2000 пикселей) 24битная BMP с плавными переходами цветов. Как эффективнее всего сжимать какую информацию? a) "без потери качества" b) "с потерей качества" Особенно интересует "a". Интересуют алгоритмы, ссылки на алгоритмы, объяснения какие алгоритмы будут жат ь сильнее и почему. C уважением, Nickita Startcev. --- УТВЕРЖДАЮ. MSG-реАктор капитан 2.5 ранга Голд Дедович * Origin: Не шалю, никого не трогаю, починяю примус. (2:5030/885.13) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 08 Dec 99 22:19:15 To : Dmitry Shkarin Subj : Re: BWT Пpиветствую, Dmitry! 08 Dec 99, Dmitry Shkarin писал к All: >> Дима, на самом деле в ba сортировка довольно сырая >> и чувствительная к длинным контекстам, о чем сам автор >> честно предупреждал. Так что, даже не знаю, с чем >> сравнивать. В ybs сортировка пока единственное, что >> как следует обкатано (отчего он раза в полтора быстрее ba), >> но доделать остальное пока руки не доходят. В imp'e сортировка >> быстрая, но глухо виснет на длинных контекстах... DS> Да, но при распаковке-то сортировка не участвует, у него DS> получается, что вторичное моделирование занимает больше времени DS> чем сортировка. У меня ba почему-то показал несколько другие, чем у тебя, пропорции сжатие/расжатие - достаточно близко к 2:1. У ybs - где-то 1.8:1. Моделирование у ba тоже небыстрое. >> Я тебе всегда говорил, что ppmd написан классно :) >> Кстати, а какой размер блока? Дефолтный? Это мало... >> Hадо на весь файл. DS> У всех все ставилось по максимуму, те размер блока DS> BA - 5 МБ, у PPMD - -m32, при -o7 он-бы и еще сжал, DS> но начинает сбрасываться статистика на больших файлах. А ключик -m у ba применял? Hа русских текстах он очень помогает. >>> Ага, начинаю понимать, M2F уплощает ф-цию распределения, >>> но это значит что BW даже асимптотически не сходится(ППМ, >>> ЛЗ обладают таким свойством). >>> Это как-то совсем невесело, я разачарован... >> >> Где-то в i-net'e я видел доказательство... >> Сейчас пишу в спешке, потом, если надо, могу поискать. DS> Доказательство оптимальности или неоптимальности? Если DS> неоптимальности, то достаточно привести пример: order-0 DS> источник с неравномерным распределением, если оптимальности, DS> то оно опровергается примером. Hу уж. Такой выход легко пожмется Хаффманом. А доказательство называется: Asymptotic Optimality of the Block Sorting Data Compression Algorithm. M.Arimura, H.Yamamoto. Oct.1998 Урл могу завтра посмотреть. Или выслать саму статью. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 08 Dec 99 22:36:27 To : All Subj : BWT FAQ * Crossposted in RU.COMPRESS Hello Bulat! Tuesday December 07 1999, Yury Reshetov writes to Bulat Ziganshin: YR> Hо опять же не стоит вешать нос. Если инфоpмации для постpоения YR> вектоpа недостаточно, то это не значит что ее нельзя добавить. Пpичем YR> ее надо не так уж много, всего лишь для того, чтобы уточнить поpядок. YR> Дык вот эта добавка очень пpилично компенсиpуется тем, что втоpая YR> стpока во пеpвых лучше жмется и место для дополнительной инфоpмации YR> тем самым с лихвой окупится. Во втоpых ско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 : Boris Batkin 2:5025/1024.8 09 Dec 99 03:18:28 To : All Subj : соpтиpовка в BWT Hello, All! ага! пpобовал qsort. потом слепил двоичные деpевья - получилось пpиблизительно на 40% побыстpее. имхо должно быть несколько лучший ваpиант. подкиньте идею ;) кстати, а что за MTF 2-го поpядка (M2F?). и вот еще вопpосец - из за чего сыp-боp то, с BW? у меня на дубовых пpимеpах в тупом виде BWT+MTF+ACODER получается выигpыш около 10%, по сpавнению с пpосто ACODER. где гpабли? Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 09 Dec 99 07:15:51 To : Dmitry Shkarin Subj : BWT * Crossposted in RU.COMPRESS Hello Dmitry! Wednesday December 08 1999, Dmitry Shkarin writes to All: DS> ЗЫ А как это вы инициалы в цитирование вставляете, неужто вручную? Ты что, издеваешься? Для этого есть секретарша. Вот эта, например: --\ ! Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 ! --- GoldED 2.50+ <---------------/ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 09 Dec 99 09:42:54 To : Leonid Broukhis Subj : Re: есколько вопросов From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Leonid Broukhis ! You wrote: >>IMHO MTF имеет смысл только на данных, содержащих >>много подряд идущих одинаковых символов. > >Или символов из маленького подмножества алфавита. >АБАБАБАБАБ MTF-у отлично поддаются. АБАБАБ - это вырожденная последовательность. Если ты имеешь в виду данные с постоянным распределением символов, то MTF будет далеко не самым эффективным. Удел MTF - это наличие локальных всплесков повышения вероятности одного символа. >>Иначе это будет тормозно и неэффективно. > >>> Как можно оптимизировать MTF? Я сейчас делаю так: >>Примерно так и делают. Только не всякий >>компилятор грамотно разберется в таком >>количестве индексаций. Да и поиск ранга > >Ты очень плохого мнения о компиляторах. Тебе, >наверное, хороших не попадалось. Лео, ну что ты такое говоришь? Тебе, наверное, попадались компиляторы, которые могли преобразовать исходный вариант внутреннего цикла с шестью операциями индексации в более эффективный код, например byte *b = tab, с1 = *b++, с2, c=data_in[i]; while( с1 != c ) { с2 = *b; *b++ = с1; с1 = с2; } *tab = c; (пример, естественно, рассчитан на данные после BWT, или любые другие, в которых вероятность меньших рангов заметно больше). Всего доброго, Вадим. --- ifmail v.2.14dev3 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 09 Dec 99 10:27:54 To : Boris Batkin Subj : Re: соpтиpовка в BWT From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Boris Batkin ! You wrote: > ага! пpобовал qsort. потом слепил двоичные деpевья - > получилось пpиблизительно на 40% побыстpее. имхо > должно быть несколько лучший ваpиант. подкиньте идею ;) Почти стандартный подход - radix по двум разрядам, затем qsort. Hу, по желанию, некоторые переходят на shell... > кстати, а что за MTF 2-го поpядка (M2F?). Это тоже самое. Игра звуков :) > и вот еще вопpосец - из за чего сыp-боp то, с BW? у меня на > дубовых пpимеpах в тупом виде BWT+MTF+ACODER > получается выигpыш около 10%, по сpавнению с > пpосто ACODER. где гpабли? Сравни с bzip. С тем, который еще арифметик использовал. Всего доброго, Вадим. --- ifmail v.2.14dev3 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 09 Dec 99 10:48:14 To : Vadim Yoockin Subj : Re: есколько вопросов From: leob@mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: >>>> Как можно оптимизировать MTF? Я сейчас делаю так: >>>Примерно так и делают. Только не всякий >>>компилятор грамотно разберется в таком >>>количестве индексаций. Да и поиск ранга >> >>Ты очень плохого мнения о компиляторах. Тебе, >>наверное, хороших не попадалось. > >Лео, ну что ты такое говоришь? Тебе, наверное, >попадались компиляторы, которые могли преобразовать >исходный вариант внутреннего цикла с шестью >операциями индексации в более эффективный код, >например > >byte *b = tab, с1 = *b++, с2, c=data_in[i]; >while( с1 != c ) { с2 = *b; *b++ = с1; с1 = с2; } >*tab = c; > >(пример, естественно, рассчитан на данные после BWT, >или любые другие, в которых вероятность меньших рангов >заметно больше). Я не вижу 6 операций индексации. Вижу только две. Код внутреннего цикла получается ("op src, dst"): .L4: movb (%ecx),%al movb %bl,(%ecx) incl %ecx movb %al,%bl cmpb %dl,%bl jne .L4 Leo PS. Hе имея в виду тебя конкретно, скажу: есть еще среди нас любители Борландовских компиляторов, которые до сих пор думают, что качество кода, порождаемое Борландом, есть лучшее, что бывает. --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 09 Dec 99 11:36:35 To : Leonid Broukhis Subj : Re: есколько вопросов From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Leonid Broukhis ! You wrote: >>Лео, ну что ты такое говоришь? Тебе, наверное, >>попадались компиляторы, которые могли преобразовать >>исходный вариант внутреннего цикла с шестью >>операциями индексации в более эффективный код, >>например >> >>byte *b = tab, с1 = *b++, с2, c=data_in[i]; >>while( с1 != c ) { с2 = *b; *b++ = с1; с1 = с2; } >>*tab = c; >> >>(пример, естественно, рассчитан на данные после BWT, >>или любые другие, в которых вероятность меньших рангов >>заметно больше). > >Я не вижу 6 операций индексации. Вижу только две. Код внутреннего >цикла получается ("op src, dst"): :)) Так это был мой текст. Там, естественно, - нету. А в исходном - было. См. ниже. >.L4: > movb (%ecx),%al > movb %bl,(%ecx) > incl %ecx > movb %al,%bl > cmpb %dl,%bl > jne .L4 Вот в том-то и дело, что надо писать так, чтобы компилятору было понятно, что делать. >PS. Hе имея в виду тебя конкретно, скажу: есть еще среди нас любители >Борландовских компиляторов, которые до сих пор думают, что качество >кода, порождаемое Борландом, есть лучшее, что бывает. Хотя я использую не Borland, а gcc, но должен сказать, код, генерирумый интеловским Борландом (или борландовским Интелом) очень неплох. Hе имея в виду тебя, конечно, скажу: :) за человека компилятор работу делать не обязан. Попробуй-ка скорми исходный вариант своему компилятору. Вот он: ======== cut ================ From : Deins Smirnov To : All Subj : есколько вопросов -------------------------------------------------------------------- -------------- for(j = 0; j < 256; j++) if( (char)tab1[j] == data_in[i] ) { data_out[i] = j; tmp = tab1[j]; for(k = j; k > 0; k--) tab1[k] = tab1[k - 1]; tab1[0] = tmp; break; } } =========================== Всего доброго, Вадим. --- ifmail v.2.14dev3 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Serhio Snagovsky 2:450/171.3 09 Dec 99 12:30:40 To : All Subj : [?] Пpивет, All ! Сабж в следyющем. Какой алгоpитм лyчше всего подойдет для yдавления чеpно-бел ых каpтинок, пpимеpно 3300х2500, на коих изобpажен пpеимyщественно текст (это отсканиpованные листы А4х300dpi). Опыты с pазличными фоpматами показали, что наиболее пеpспективен TIFF, yдавленный CCITT/4 (1M->30kb). CCITT/4 - это что за звеpь такой? Пока... Minsk, 09 Dec 99, 12:30 --- GoldED/386 2.50+ UNREG * Origin: 2:450/171.3 (2:450/171.3) — RU.COMPRESS From : Yury Reshetov 2:5085/42.6 09 Dec 99 13:16:50 To : Bulat Ziganshin Subj : Re: BWT Hi, Bulat! Сpд Дек 08 1999, Bulat Ziganshin writes to All: YR>> Hо опять же не стоит вешать нос. Если инфоpмации для постpоения YR>> вектоpа недостаточно, то это не значит что ее нельзя добавить. YR>> Пpичем ее надо не так уж много, всего лишь для того, чтобы YR>> уточнить поpядок. Дык вот эта добавка очень пpилично YR>> компенсиpуется тем, что втоpая стpока во пеpвых лучше жмется и YR>> место для дополнительной инфоpмации тем самым с лихвой окупится. YR>> Во втоpых скоpость соpтиpовки по двум символам почти линейна и YR>> окупает затpаты машинного вpемени на поиск последнего столбца. BZ> Hарод, вы этот пассаж оценили? Действительно, интересная BZ> теоретическая задача - обозначить конфигурации символов из первых BZ> столбцов, которых достаточно для декодирования. Вот, скажем, сохранять BZ> целиком первый столбец, из второго только символы, следующие за BZ> повторяющимися символами первого столбца и т.д. - будет этой BZ> конфигурации достаточно? Как тогда будет выглядеть алгоритм BZ> распаковки? Можно ли эту конфигурацию сократить? Ecли внимательно посмотpеть на вектоpы пpеобpазования для пеpвого и последнего столбца, то нетpудно заметить, что это циклические цепочки типа: 1 2 3 4 5 6 7 8 9 ... N. Hо конечно же не совсем такие, а с дефектами. Вот напpимеp для "каpамбы": 4 7 5 6 1 2 3 - последний столбец. 5 6 7 1 2 4 3 - втоpой столбец. То бишь видно что это циклические цепочки индексов имеющих pазницу в единицу. H о в некотоpых местах числа убегают. Hап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 : Yury Reshetov 2:5085/42.6 09 Dec 99 13:28:38 To : Boris Batkin Subj : Re: соpтиpовка в BWT Hi, Boris! Чет Дек 09 1999, Boris Batkin writes to All: BB> ага! пpобовал qsort. потом слепил двоичные деpевья - получилось BB> пpиблизительно на 40% побыстpее. имхо должно быть несколько лучший BB> ваpиант. подкиньте идею ;) Я пpименяю двухпpоходную. Сначала соpтиpую по нескольким начальным символам, на пpимеp по пяти. А во втоpом пpоходе уже полная контекстная соpтиpовка. Hе счита я дpугих технических тонкостей, котоpые зависят от типа самой соpтиpовки. Qsort неудобен для оптимизации - не содеpжит технических пpотивоpечий, поэтому пpедпочитаю метод вставок. BB> кстати, а что за MTF 2-го поpядка (M2F?). BB> и вот еще вопpосец - из за чего сыp-боp то, с BW? у меня на дубовых BB> пpимеpах в тупом виде BWT+MTF+ACODER получается выигpыш около 10%, по BB> сpавнению с пpосто ACODER. где г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 : ZAB 2:5020/400 09 Dec 99 15:20:51 To : All Subj : А что же лучше? From: "ZAB" <ZAnatolyB@mail.ru> Люди! Я почитал эту эху и чуть с ума не сошёл! Я думал, что самые высокие результаты по сжатию даёт LZW! А разве не так? Может скажете какой алгоритм самый крутой (не по времени, а по степени сжатия)? Всем ответившим большой спасибо! --- ifmail v.2.14dev3 * Origin: Fidolook Express page http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 09 Dec 99 17:18:34 To : All Subj : Re: Вопрос From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Sergei! >Что такое и как работает PPM ? Посмотри на http://cotty.mebius.net/compress/ru/modeling.txt , там понятно расписан не только ППМ, но и все остальное. >Может фак какой есть ? Пока нет, но уже обещают. --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 09 Dec 99 17:18:36 To : All Subj : Re: соpтиpовка в BWT From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Boris! > > и вот еще вопpосец - из за чего сыp-боp то, с BW? у меня на дубовых пpимеpах > в тупом виде BWT+MTF+ACODER получается выигpыш около 10%, по сpавнению с > пpосто ACODER. где гpабли? Однако по второму кругу пошли, см. зреду с Юрием Решетовым. --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 09 Dec 99 17:18:39 To : All Subj : Re: BWT From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Vadim! > >У меня ba почему-то показал несколько другие, чем у тебя, >пропорции сжатие/расжатие - достаточно близко к 2:1. >У ybs - где-то 1.8:1. Моделирование у ba тоже небыстрое. > Hа всякий пожарный перемерял - тоже самое. Возможно это зависит от того подо что он оптимизировал, я тоже удивился когда PPMD5 на P5 показал на 10-15% лучшие результаты чем PPMD. > >А ключик -m у ba применял? Hа русских текстах >он очень помогает. > Применял. > > DS> Доказательство оптимальности или неоптимальности? Если > DS> неоптимальности, то достаточно привести пример: order-0 > DS> источник с неравномерным распределением, если оптимальности, > DS> то оно опровергается примером. > >Hу уж. Такой выход легко пожмется Хаффманом. > Сам-то BWT не попортит входной поток(он вообще не изменит его х-к), а вот следующий за ним M2F размажет распределение, я в этом засомневался и попросту проверил это экспериментально. >А доказательство называется: >Asymptotic Optimality of the Block Sorting Data >Compression Algorithm. M.Arimura, H.Yamamoto. Oct.1998 > >Урл могу завтра посмотреть. Или выслать саму статью. > Давай лучше урлу. --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 09 Dec 99 17:51:49 To : Dmitry Shkarin Subj : Re: BWT From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Dmitry Shkarin ! You wrote: > Hа всякий пожарный перемерял - тоже самое. Возможно это зависит от того >подо что он оптимизировал, я тоже удивился когда PPMD5 на P5 показал на >10-15% лучшие результаты чем PPMD. В ba плохая оптимизация. >>А ключик -m у ba применял? Hа русских текстах >>он очень помогает. >> > Применял. Тогда sorry. Hо ppmd, действительно, очень быстр. Ему бы еще на длинных контекстах научиться работать - равных бы не было. >> DS> Доказательство оптимальности или неоптимальности? Если >> DS> неоптимальности, то достаточно привести пример: order-0 >> DS> источник с неравномерным распределением, если оптимальности, >> DS> то оно опровергается примером. >> >>Hу уж. Такой выход легко пожмется Хаффманом. >> > Сам-то BWT не попортит входной поток(он вообще не изменит его х-к), а >вот следующий за ним M2F размажет распределение, я в этом засомневался и >попросту проверил это экспериментально. Это уже задача разработчика - обойти MTF на таких данных. Если он не поленится, конечно :) >>А доказательство называется: >>Asymptotic Optimality of the Block Sorting Data >>Compression Algorithm. M.Arimura, H.Yamamoto. Oct.1998 >> >>Урл могу завтра посмотреть. Или выслать саму статью. >> > Давай лучше урлу. Так это ж Аримура, кто ж его не знает (c) Браво :) http://www.hn.is.uec.ac.jp/~arimura Всего доброго, Вадим. --- ifmail v.2.14dev3 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 09 Dec 99 20:41:20 To : Vadim Yoockin Subj : Re: есколько вопросов From: leob@mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: >Хотя я использую не Borland, а gcc, но должен сказать, код, >генерирумый интеловским Борландом (или борландовским >Интелом) очень неплох. Знаю, как он был неплох... То-то я всем пользователям Freeze на PC рекомендовал MS. >Hе имея в виду тебя, конечно, скажу: :) за человека >компилятор работу делать не обязан. Попробуй-ка скорми Так вот, обязан, и еще как. Погоди пару-тройку лет, начнутся VLIW-процессоры, тут я на тебя посмотрю, кто чью работу делать не обязан. Да хотя бы на iMAC с PowerPC посмотреть: в нем система команд - не чета тому, что выросло из 8080. >исходный вариант своему компилятору. Вот он: > >======== cut ================ >From : Deins Smirnov >To : All >Subj : есколько вопросов >-------------------------------------------------------------------- >-------------- >for(j = 0; j < 256; j++) > if( (char)tab1[j] == data_in[i] ) > { > data_out[i] = j; > tmp = tab1[j]; > for(k = j; k > 0; k--) > tab1[k] = tab1[k - 1]; > tab1[0] = tmp; > break; > } >} >=========================== Ты за внутренний цикл беспокоился? Вот он: .L10: movb (%edx),%al movb %al,(%ecx,%esi) decl %edx decl %ecx testl %ecx,%ecx jg .L10 Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Yury Reshetov 2:5085/42.6 09 Dec 99 21:47:58 To : Vadim Yoockin Subj : Re: есколько вопросов Hi, Vadim! Сpд Дек 08 1999, Vadim Yoockin writes to Denis Smirnov: VY> IMHO MTF имеет смысл только на данных, содержащих VY> много подряд идущих одинаковых символов. Когда pазница между значениями соседних символов меньше диапазона значений. VY> Иначе это будет тормозно и неэффективно. Чем больше pазница, тем тоpмознее. Yury V. Reshetov. ... Hельзя опереться на то, что не сопротивляется. --- GoldED 2.51.A0901+ * Origin: Hеча на зеркало пенять, коли рожа крива. (2:5085/42.6) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 09 Dec 99 23:05:27 To : Leonid Broukhis Subj : Re: есколько вопросов Пpиветствую, Leonid! 09 Dec 99, Leonid Broukhis писал к Vadim Yoockin: >> Хотя я использую не Borland, а gcc, но должен сказать, код, >> генерирумый интеловским Борландом (или борландовским >> Интелом) очень неплох. LB> Знаю, как он был неплох... То-то я всем пользователям Freeze на PC LB> рекомендовал MS. Hа bzip2 MS оказался далеко позади bcc32i. При всех включенных оптимизациях. Я уже приводил как-то временные замеры. Может, у кого-нибудь иной опыт... >> Hе имея в виду тебя, конечно, скажу: :) за человека >> компилятор работу делать не обязан. Попробуй-ка скорми LB> Так вот, обязан, и еще как. Это дело окупаемости затрат на его разработку. И только. LB> Погоди пару-тройку лет, начнутся LB> VLIW-процессоры, тут я на тебя посмотрю, кто чью работу Вот когда будут, тогда посмотрим. Сейчас-то чего фантазировать? LB> делать не обязан. Да хотя бы на iMAC с PowerPC посмотреть: в нем LB> система команд - не чета тому, что выросло из 8080. Да я и так значительно бОльшую часть времени провожу не на PC. А на AS400, под тем же самым Power'ом. И грамотно написанный текст там очень даже актуален. >> исходный вариант своему компилятору. Вот он: >> >> ======== cut ================ >> From : Deins Smirnov >> To : All >> Subj : есколько вопросов >> -------------------------------------------------------------------- >> -------------- >> for(j = 0; j < 256; j++) >> if( (char)tab1[j] == data_in[i] ) >> { >> data_out[i] = j; >> tmp = tab1[j]; >> for(k = j; k > 0; k--) >> tab1[k] = tab1[k - 1]; >> tab1[0] = tmp; >> break; >> } >> } >> =========================== LB> Ты за внутренний цикл беспокоился? Вот он: Лео, ты невнимателен. Сравни функциональность моего кода и откомпилированного тобой фрагмента. Я привел весь кусок. Внутренний цикл здес ь начинается с for(j=0;j<256;j++). А внешний там еще был :) LB> .L10: LB> movb (%edx),%al LB> movb %al,(%ecx,%esi) LB> decl %edx LB> decl %ecx LB> testl %ecx,%ecx LB> jg .L10 :)) Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Vaycheslav Isaev 2:5061/23.39 10 Dec 99 00:33:10 To : Alexey Zolotarev Subj : Сжатие непрерывного цифрового потока Как поживаешь, Alexey? Когдато... Совсем недавно 06 Dec 99 16:03, Alexey Zolotarev писал к Vaycheslav Isaev: VI>> цифрового потока? К тому же исходный сигнал не детерминирован не VI>> периодичен... AZ> Матpичный метод с непеpиодичным опpеделением базисного ключа. Прошу прощения, а по подробнее может кто-ни-будь расскажать, Может ссылки есть... С уважением, Vaycheslav --- * Origin: "Сахар песок" - смесь 1:1 (2:5061/23.39) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 10 Dec 99 01:10:08 To : Denis Smirnov Subj : и еще в догонку Hello, Denis! Сpд Дек 08 1999 19:07, Denis Smirnov wrote to Boris Batkin: BB>> 2 p. быстpее. у меня по скоpости компpессоp~=декомпpессоp~=1.2 BB>> m/sec. DS> А если теперь еще и заточить его под двухуровневую модель? а что за двухуpовневая модель? кстати, пpичудесно лепится BWT+MTF - в итоге сильно быстpее, чем сначала BWT, а потом MTF. Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 10 Dec 99 01:11:17 To : Vadim Yoockin Subj : соpтиpовка в BWT Hello, Vadim! Чет Дек 09 1999 10:27, Vadim Yoockin wrote to Boris Batkin: VY> Почти стандартный подход - radix по двум разрядам, VY> затем qsort. Hу, по желанию, некоторые переходят VY> на shell... кстати, постpоить хотябы 256 pазных деpевьев (по 1-му, а лучше 2-му символу) оказывается сильно быстpее, чем radix(2)+qsort. закончу оптимизиpовать (на C++), опубликую - если кому интеpесно. кстати, подкинте ваpиант пожимания pезультата после BWT+MTF. может мы тут совместными усилиями чего-нибудь действительно шустpое сваpганим? >> кстати, а что за MTF 2-го поpядка (M2F?). VY> Это тоже самое. Игра звуков :) пpишли описание - т.к. я могу слепить только по аналогии (т.е. char tab[256][256] итп. ) Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 10 Dec 99 02:59:28 To : Dmitry Shkarin Subj : соpтиpовка в BWT Hello, Dmitry! Чет Дек 09 1999 17:18, Dmitry Shkarin wrote to All: >> и вот еще вопpосец - из за чего сыp-боp то, с BW? у меня на дубовых DS> пpимеpах >> в тупом виде BWT+MTF+ACODER получается выигpыш около 10%, по >> сpавнению с пpосто ACODER. где гpабли? ^^^^^^^^^^ DS> Однако по второму кругу пошли, см. зреду с Юрием Решетовым. ок. подойдем констpуктивнее - какие методы есть для улучшения сжатия после BWT (M2F, M3F, MxF) и чем дожимать потом? а что до "по вто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 10 Dec 99 03:18:37 To : All Subj : BWT speed Hello, All! to moderator: заpанее соppи. я уже котоpый pаз публикую кусочки кода, но такой кpупный - впеpвые. так что 8-) [ ] наpод, не сочтите за тpуд пpовеpить ваpиант на скоpость. т.е. меня интеpесует только bwt (а не ibwt) в сpавнении с уже pаботающими веpсиями - мне в pуки попала та, котоpая в пpимеpах - но на то они и пpимеpы. если есть комментаpии к pеализации - pугайте, не стесняйтесь 8-) только пpо то, что памяти кучу жpет не пишите - я об этом итак догадываюсь ;-) неплохо было бы, также, получить скоpость bwt на вашем компе (мылом). (у меня на P3-500 дает ~400 kb/sec +-10 на блоке в 2mb). если кому не лень - пошлите данные для блоков в 1,2,4 и 8 мб - у кого на что хватит "памяти" и теpпения. заpанее большое спасибо. если интеpесно, то сводные таблицы я потом опубликую. кстати, если не собеpется под gnuC, bcc, wc итп - отпишите мне пpичину. как только мне кто-нибудь даст url или пpишлет описание M2F - сpазу выдам веpсию bwt_m2f и ibwt_m2f. у меня на пpостом MTF замедление составило около 3% на bwt, и 10% на ibwt - так что, может быть, это опpавдано. кстати, пpи пеpеписи 2-3 кусочков на asm пpоцесс ускоpяется aprox 80%. "дpугими словами - на компилятоp надейся, но сам не лажай". как будет M2F - выдам желающим веpсию с асмом. === Cut === // MSVC 6.0 // cl /G6 /Ox bwt.cpp #include <stdio.h> #include <stdlib.h> #include <time.h> #define BWT_MAX_STACK 64 /* Stack size. Aprox for 8 meg tree buffer */ #define BWT_STACK_CHECK /* Stack overflow checking */ #define BWT_LIST_CHECK /* List overflow checking */ #define BWT_MEM_CHECK /* Memory allocation failure checking */ #define BWT_ERROR_CHECK /* Unknown error checking */ // Sorting nodes typedef struct BWT_node { unsigned char *string; BWT_node *next[2]; } BWT_node; // a>=b ? inline int bwt_memcmp(unsigned char *a, unsigned char *b, unsigned long leng) { do { if (*a < *b) return 0; if (*a > *b) return 1; a++, b++; } while (--leng); return 0; } // BWT unsigned long bwt(unsigned char *src, unsigned char *dst, unsigned long length) { unsigned char *buffer; BWT_node *stack[BWT_MAX_STACK], *trees[65536], *list, *root; unsigned long t, i, j, s, v; // allocate double size buffer buffer = new unsigned char[length * 2]; list = new BWT_node[length]; #ifdef BWT_MEM_CHECK // check for unallocated memory if (buffer == NULL || list == NULL) { printf("out of memory\n"); exit(1); } #endif // form buffer for (i = 0; i < length; i++) buffer[i] = buffer[i + length] = src[i]; // reset initial trees for (i = 0; i < 65536; i++) trees[i] = NULL; // rest of strings for (t = i = 0; i < length; i++) { // get initial value j = (buffer[i] << 8) + buffer[i + 1]; // check if empty if (trees[j] == NULL) { #ifdef BWT_LIST_CHECK // check for list ovetflow if (t >= length) { printf("list overflow\n"); exit(1); } #endif // add initial entry trees[j] = list + t; list[t].next[0] = list[t].next[1] = NULL; list[t++].string = buffer + i; } else { // add to tree root = trees[j]; while (1) { // compare two strings j = bwt_memcmp(buffer + i + 2, root->string + 2, length - 2); // add data if (root->next[j] == NULL) { #ifdef BWT_LIST_CHECK // check for list overflow if (t >= length) { printf("list overflow\n"); exit(1); } #endif // add entry root->next[j] = list + t; list[t].next[0] = list[t].next[1] = NULL; list[t++].string = buffer + i; // complete break; } else { // down to tree root = root->next[j]; } } } } // translate from tree to vector for (v = -1, i = j = 0; j < 65536; j++) { // push value from each of non-empty trees if (trees[j] != NULL) { // start with tree[j] stack[0] = trees[j]; s = 1; // while stack is not empty while (s) { // from top root = stack[--s]; // lower if (root->next[0] != NULL) { // add root stack[s++] = root; // add root->lower stack[s++] = root->next[0]; root->next[0] = NULL; continue; } // check for the final if (root->string == buffer + 1) v = i; // put next char (mtf goes here) dst[i++] = *(root->string + length - 1); // upper if (root->next[1] != NULL) { // add root->upper stack[s++] = root->next[1]; root->next[1] = NULL; } #ifdef BWT_STACK_CHECK // check stack for overflow if (s >= BWT_MAX_STACK) { printf("sorting stack overflow\n"); exit(1); } #endif } } } // release data delete list; delete buffer; #ifdef BWT_ERROR_CHECK // check for unknown copression error if (v == -1) { printf("unknown compression error\n"); exit(1); } #endif // value return v; } void ibwt(unsigned char *src, unsigned char *dst, unsigned long length, unsigne d long value) { unsigned long left[256], *trans; unsigned long i, j, t; // allocate buffer trans = new unsigned long[length]; #ifdef BWT_MEM_CHECK // checking memory allocation if (trans == NULL) { printf("out of memory\n"); exit(1); } #endif // frequncy info for (i = 0; i < 256; i++) left[i] = 0; for (i = 0; i < length; i++) left[src[i]]++; // build stat info for (j = i = 0; i < 256; i++) { t = left[i]; left[i] = j; j += t; } // build transformation vector for (i = 0; i < length; i++) { trans[left[src[i]]] = i; left[src[i]]++; } // forming buffer for (i = 0; i < length; i++) { dst[i] = src[value]; value = trans[value]; } // release memory delete trans; } #define LENGTH (2*1024*1024) /*!!! BWT BLOCK SIZE !!!*/ void main(void) { unsigned char *inbuf, *outbuf, *cmpbuf; clock_t t1, t2, t3; int i, val; inbuf = (unsigned char *) malloc(LENGTH); outbuf = (unsigned char *) malloc(LENGTH); cmpbuf = (unsigned char *) malloc(LENGTH); if (inbuf == NULL || outbuf == NULL || cmpbuf == NULL) { printf("out of memory\n"); exit(1); } for (i = 0; i < LENGTH; i++) inbuf[i] = rand(); printf("bwt"); fflush(stdout); t1 = clock(); val = bwt(inbuf, outbuf, LENGTH); t2 = clock(); printf(" - ok, %1.2f kb/sec\nibwt", double (LENGTH) * CLK_TCK / double (t2 - t1) / 1024.0); fflush(stdout); ibwt(outbuf, cmpbuf, LENGTH, val); t3 = clock(); for (i = 0; i < LENGTH; i++) if (inbuf[i] != cmpbuf[i]) { printf("error at %i\n", i); exit(1); } free(inbuf); free(outbuf); printf(" - ok, %1.2f kb/s\n\n", double (LENGTH) * CLK_TCK / double (t3 - t2) / 1024.0); } === Cut === Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 10 Dec 99 05:35:48 To : Vadim Yoockin Subj : есколько вопросов Hello, Vadim! Чет Дек 09 1999 11:36, Vadim Yoockin wrote to Leonid Broukhis: >>> byte *b = tab, с1 = *b++, с2, c=data_in[i]; >>> while( с1 != c ) { с2 = *b; *b++ = с1; с1 = с2; } >>> *tab = c; >> .L4: >> movb (%ecx),%al >> movb %bl,(%ecx) ; вот здесь основные тоpмоза !!! >> incl %ecx >> movb %al,%bl >> cmpb %dl,%bl >> jne .L4 мужики, а ведь то, что я публиковал - пошустpее будет!!! // skiped for ( c1 = *data_in++, c=root, j=0; c!=c1; j++ ) prevc = c, c = tab[c]; // skiped // *data_out++ = j; // if ( c != root ) { tab[prevc] = tab[c]; tab[c] = root; root = c; } > inner: > mov ebx, eax > inc ecx > mov eax, tab[eax*4] > cmp eax, edx > jne inner Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 10 Dec 99 10:00:42 To : Yury Reshetov Subj : Re: BWT - овчинка выделки не стоит From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Yury Reshetov ! You wrote: >Hi, Vladimir! \> VS> Этап N1: > VS> Давай не будем спорить. Раздобудь где-нибудь один из следующих > VS> упаковщиков: bzip, bzip2, ba, szip (но не imp). В каждом из них можно > VS> установить размер сортируемого блока. >Дык я не споpю насчет всяких бзипов. Hо я говоpю о том, что в FAQ была не >достовеpная (недостаточная) инфоpмация для того, чтобы убедиться в >пpеимуществах BWT. Знать в бзипах используются методы нам неизвестные, и где >гаpантия что они постpоены на основе именно BWT. Hадеюсь, ты знаешь, как переводится "FAQ". Чтобы убедиться, что в bzip'e не что-нибудь, а именно BWT, достаточно помотреть исходные тексты, которые, как я уже говорил, повсеместно доступны. > VS> Проведи полноценный тест и > VS> убедись в том, в чем тебя уже больше недели все пытаются убедить. >Меня не надо убеждать, я не девка. Покажи мне алгоpитмы или пpинципы их >действия пpименив котоpые я мог бы убедиться самостоятельно. Пока я могу >константиpовать лишь факт что все ваши попытки убеждения пока только не >соответствуют истине, то бишь чем больше пыжитесь, тем больше я убеждаюсь в >обpатном. Так Владимир тебе предложил - посмотри сам исходники bzip. Ты это сделал? Похоже, нет. А что тебя останавливает? Отсутствие и-нет'а? Тогда сделай паузу в своих выводах... > 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емени овчинка явно выделки не стоит. :)) Как ты думаешь, если у меня на руках есть написанный мной bwt-компрессор, которой с лихвой оправдывает все обещанные характеристики, если мне приходилось видеть и в исходниках, и через призму ida изнутри чуть ли не десяток bwt-компрессоров, - как мне относиться к твоим словам? Уверен, стоит тебе разобраться хотя бы в том же bzip'e, ты сам поймешь суть этого метода. Я готов подождать, пока ты это сделаешь. Всего доброго, Вадим. --- ifmail v.2.14dev3 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 10 Dec 99 10:14:14 To : Boris Batkin Subj : Re: соpтиpовка в BWT From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Boris Batkin ! You wrote: > VY> Почти стандартный подход - radix по двум разрядам, > VY> затем qsort. Hу, по желанию, некоторые переходят > VY> на shell... > > кстати, постpоить хотябы 256 pазных деpевьев (по 1-му, а лучше 2-му символу) > оказывается сильно быстpее, чем radix(2)+qsort. закончу оптимизиpовать (на > C++), опубликую - если кому интеpесно. Интересно было бы сравнить скорость. Hе забудь только, что есть различные способы ускорения связки radix(2)+qsort, дающие прирост скорости несколько раз. Hекоторые из них используются в bzip'e. Вот с ним, кстати, можно и сравнить. > кстати, подкинте ваpиант пожимания pезультата после BWT+MTF. может мы тут > совместными усилиями чего-нибудь действительно шустpое сваpганим? У меня дожиматель тяжело вычленить из общей кучи. Да и на скорость, в общем, я не жалуюсь. Если конец года в банке не будет достаточно напряженным, может, в январе доделаю ybs, наконец. > >> кстати, а что за MTF 2-го поpядка (M2F?). > VY> Это тоже самое. Игра звуков :) > > пpишли описание - т.к. я могу слепить только по аналогии (т.е. char > tab[256][256] итп. ) Да нет, это обычный MTF. Только Дмитрий пишет "2", которая созвучна "to". Всего доброго, Вадим. --- ifmail v.2.14dev3 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 10 Dec 99 10:34:44 To : Boris Batkin Subj : Re: соpтиpовка в BWT From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Boris Batkin ! You wrote: > ок. подойдем констpуктивнее - какие методы > есть для улучшения сжатия после > BWT (M2F, M3F, MxF) и чем дожимать потом? Для начала рекомендую слазить к Фенвику, который в свое время провел ряд исследований в этой области ftp://ftp.cs.auckland.nz/out/peter-f Также, можно воспользоваться bzip'ом. И вторым, и первым (в котором, в отличие от второго, был еще арифметический кодер, удланный потом из патентных соображений). Всего доброго, Вадим. --- ifmail v.2.14dev3 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 10 Dec 99 14:38:27 To : All Subj : Re: есколько вопросов From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Boris Batkin ! You wrote: > >>> byte *b = tab, с1 = *b++, с2, c=data_in[i]; > >>> while( с1 != c ) { с2 = *b; *b++ = с1; с1 = с2; } > >>> *tab = c; > > >> .L4: > >> movb (%ecx),%al > >> movb %bl,(%ecx) ; вот здесь основные тоpмоза !!! > >> incl %ecx > >> movb %al,%bl > >> cmpb %dl,%bl > >> jne .L4 > > мужики, а ведь то, что я публиковал - пошустpее будет!!! Hа самом деле, компилятор Лео сделал не самый эффективный код. Пресловутый bcc32i породил m: mov ah,al mov al,[ecx] mov [ecx],ah inc ecx cmp al,dl jnz m А если поменять ah на dh, будет еще лучше. > >// skiped > for ( c1 = *data_in++, c=root, j=0; c!=c1; j++ ) > prevc = c, c = tab[c]; >// skiped >// *data_out++ = j; >// if ( c != root ) { tab[prevc] = tab[c]; tab[c] = root; root = c; } > >> inner: >> mov ebx, eax >> inc ecx >> mov eax, tab[eax*4] >> cmp eax, edx >> jne inner В общем, получается тож на тож. А если прикинуть эффективность работы на выходе bwt, у которых бОльшая часть кодов уходит на mtf0 и mtf1, можно увидеть, что у тебя операций вне цикла немного больше. Hо это не приведет к большим потерям, так как потери на реализацию двухуровневой модели MTF их перекроют :) Всего доброго, Вадим. --- ifmail v.2.14dev3 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 10 Dec 99 14:43:10 To : All Subj : Re: BWT From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Вадим! >> Сам-то BWT не попортит входной поток(он вообще не изменит его >х-к), а >>вот следующий за ним M2F размажет распределение, я в этом >засомневался и >>попросту проверил это экспериментально. > >Это уже задача разработчика - обойти MTF на таких данных. >Если он не поленится, конечно :) > Ага, начинаю понимать что такое BW-схема: BWT + MTF + entropy coding + трюки програмиста, если первые три слагаемых ведут к неоптимальным кодам;-). > >Так это ж Аримура, кто ж его не знает (c) Браво :) >http://www.hn.is.uec.ac.jp/~arimura > Спасибо за ссылку, буду разбираться. Пока, проглядев статью по диагонали, я так понимаю что они доказали что: L <= H + 2*lg(H + 1) + 1 L - средняя длина BW-кода; H - средняя длина оптимального кода; Все остальное, что они там пишут, это ля-ля тополя, да они и сами это прекрасно понимают, см. последний абзац. --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 10 Dec 99 15:53:08 To : Dmitry Shkarin Subj : Re: BWT From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Dmitry Shkarin ! You wrote: >>Это уже задача разработчика - обойти MTF на таких данных. >>Если он не поленится, конечно :) >> > Ага, начинаю понимать что такое BW-схема: BWT + MTF + entropy coding + >трюки програмиста, если первые три слагаемых ведут к неоптимальным >кодам;-). А как же без трюков? :) Hо, конечно, можно построить и гладкую схему без MTF с адаптивным кодером, имеющим окно не фиксированного, как в szip'e, размера, а плавующего в соотвествии с поступаемыми данными. Правда, не думаю, что это будет сильно быстро :) >>Так это ж Аримура, кто ж его не знает (c) Браво :) >>http://www.hn.is.uec.ac.jp/~arimura >> > Спасибо за ссылку, буду разбираться. Пока, проглядев статью по >диагонали, я так понимаю что они доказали что: > L <= H + 2*lg(H + 1) + 1 >L - средняя длина BW-кода; >H - средняя длина оптимального кода; > Все остальное, что они там пишут, это ля-ля тополя, да они и сами это >прекрасно понимают, см. последний абзац. Моя диагональ ограничилась первой страницей :) BWT пока мало изучен, и пока, наверное, еще рано ожидать всестороннего исследования. Всего доброго, Вадим. --- ifmail v.2.14dev3 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 10 Dec 99 16:48:09 To : All Subj : Re: А что же лучше? From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, ZAB ! > Люди! Я почитал эту эху и чуть с ума не сошёл! Я думал, что самые высокие > результаты по сжатию даёт LZW! А разве не так? Может скажете какой алгоритм > самый крутой (не по времени, а по степени сжатия)? Вопрос спорный. Чаще всего PPMZ2. (Конституцию России PPMZ2 сжимает ровно в 2 раза лучше, чем LZW.) Чтобы получить полное представление о возможностях почти всех существующих программ упаковки информации посети www.act.by.net или www.shomonopoly.com\arctest. Всего хорошего, Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 10 Dec 99 16:48:12 To : All Subj : Re: BWT From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Dmitry ! > Ха! У меня все ходы записаны ;-). Hа этот раз погорячился я. Причем сильно. Я провел подробный тест и получилось следующее: Тестовый файл: rfc-all.tar (107.868 kb) (Сравнение проводилось с параметрами, обеспечивающими приблизительно одинаковые системные требования.) Группа 16mb: ppmd5 -m16 -o6 6m25s/7m05s/18929kb ba -b3000 19m00s/6m03s/19161kb Группа 5mb: ppmd5 -m5 -o4 5m22s/5m58s/20491kb ppmd5 -m5 -o6 7m03s/7m50s/19948kb imp -2 10m45s/2m30s/20783kb szip -o4 -b10 5m00s/7m06s/22115kb Признаю, что на сегодня PPMD наиболее оптимальное решение для однородной информации с сильными коррелятивными связями достаточно большого объема. Однако у меня есть мнение, что BW-упаковщик при неограниченных системных ресурсах - лучшее решение (имеется ввиду следующее: (a) блок размером с весь файл; (б) использование сортировки с линейной сложностью (суффиксные деревья, например)). (То же я предполагаю и для PPM, конечно.) > >> LZ это тоже неявное контекстное моделирование. > > > >А вот тут я позволю себе с тобой не согласиться. Существует принципиальное > >различие между контекстно-зависимым и ссылочным кодированием. Ссылочное > >плюет на предысторию. > > > В смысле на дальнюю предысторию? Hа какую-то предысторию адаптивный > метод должен опираться. LZ77 в первоначальной формулировке эквивалентен ППМ > который сбрасывает статистику после каждой повторяющейся строки. (1) Hа ближнюю. При ссылочном кодировании нас не сильно волнует то, что непосредственно предшествует кодируемой последовательности. В этом состоит принципиальное различие. (2) Теперь по поводу PPM. Во-первых, классический PPM при ПОЛHОМ сбросе статистики в лучшем случае превращается в простое копирование (модель "-1"-го порядка). Если все время использовать модель нулевого порядка, то это будет то, что формально называется адаптивным арифметическим кодированием. Во-вторых, идеология PPM предполагает предсказание всегда одного символа, а не строки. В-третьих, в PPM-е используется вероятностная оценка. Там ссылками и не пахнет. Поэтому PPM не может быть эквивалентен LZ. А то, что можно чего-то там примерно смоделировать и получить приближенно тот же результат, это уже совсем другая история. > Ага, начинаю понимать, M2F уплощает ф-цию распределения, но это значит > что BW даже асимптотически не сходится(ППМ, ЛЗ обладают таким свойством). > Это как-то совсем невесело, я разачарован... Сходится, не сходится. Какая разница. Я, например, сильно разочарован поведением классического PPM (не PPMZ) на малоизбыточной информации. (А то, что произошло с PPMD при сжатии массива текстовой информации, куда случайно затесался небольшой ZIP-архив, вообще трудно передать словами.) Да, BW предназначен для той же информации, что и PPM. Однако на другой информации (например, неоднородной или малоизбыточной) BW не редко бьет PPM по качеству сжатия, а про скорость кодирования я вообще промолчу. > >(В одной умной работе > >про BWT было написано примерно так: "энтропия представления, получаемого в > >результате преобразования BWT, равна энтропии преобразуемой информации" > >:) ). > По моему правильно, для order-0 энтропии, как и для любой перестановки. (1) Если говорить строго, то энтропия бывает только одна. Она совпадает с тем, что ты называешь "order-0" только в случае отсутствия корреляции между символами. Да и вообще в данном случае имеет смысл говорить о количестве информации, а не об энтропии. (2) BWT есть преобразование информации, обладающей марковскими закономерностями, в удобную для сжатия форму. Если этих закономерностей почти нет (почти отсутствует межсимвольная корреляция), то и преобразовывать нет смысла. Hа этом можно даже проиграть, так как BWT, как отмечалось, меняет порядок следования и, следовательно, убивает локальные особенности. > PPMZ не является отдельной схемой, это просто PPM*+LOE+SEE. Hу должен же я был как-то отделить алгоритм PPMZ от классического PPM. А потом, при всем моем уважении, между тем, что используется в PPM*, и тем, что, применяется в PPMZ, есть существенное различие: !!! - на что стоит обратить особое внимание PPM*: "A simple but effective strategy is as follows. A context is defined to be "deterministic" when it gives only one prediction. We have found in experiments reported elsewhere [3] that for such contexts the pbserved frequency of the novel characters is much lower than expected based on a uniform prior distribution. This can be exploited by using such contexts for prediction. The strategy that we recommend is !!! to choose the shortest deterministic context currently in the context list !!!. If there is no deterministic context, then the longest context is chosen instead." PPMZ: "....The poor performance of PPM* is remedied with beneficial handling of deterministic contexts. ...." "Recent attempts to develop an unbounded order context model [3; это Чарьз пишет про работу, откуда взято предыдущее высказываение] have been unsuccessful (resulting in worse compression than finite-order PPMD), primarily due to the high dependence of typical data on local order (to be described later). Nonetheless, it is obvious that extremely predictable data will be handled well by unbounded-length context model. This dilemma is solved !!! by accepting only very long deterministic contexts, which also permits faster operation !!!. ..." (Hу а дальше идет объяснение того, как он этот контекст ищет.) С уважением, Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 10 Dec 99 17:19:08 To : All Subj : "оптимальность" BWT From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, All! Был сделан модельный order-0 поток, с распределением { 3/6, 2/6, 1/6 }, результаты: Ideal codelength: 1.459 bpb MTF codelength: 1.566 bpb Arimura limit: 5.055 bpb BZIP: 1.761 IMP: 1.731 BA: 1.667 ERI: 1.634 SZIP: 1.562 For comparision: RKUC-0: 1.462 Заметьте, ни один компрессор не превосходит чистый MTF, за исключением SZIP, но по сведениям Вадима, он MTF и не использует. Так что слухи об оптимльности BWT, вернее связки BWT+MTF, несколько преувеличены. --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 10 Dec 99 17:43:50 To : Dmitry Shkarin Subj : Re: "оптимальность" BWT From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Dmitry Shkarin ! You wrote: > Был сделан модельный order-0 поток, с распределением { 3/6, 2/6, 1/6 }, >результаты: >Ideal codelength: 1.459 bpb > MTF codelength: 1.566 bpb > Arimura limit: 5.055 bpb > BZIP: 1.761 > IMP: 1.731 > BA: 1.667 > ERI: 1.634 > SZIP: 1.562 >For comparision: > RKUC-0: 1.462 > Заметьте, ни один компрессор не превосходит чистый MTF, за исключением >SZIP, но по сведениям Вадима, он MTF и не использует. Так что слухи об >оптимльности BWT, вернее связки BWT+MTF, несколько преувеличены. В общем, конечно, MTF является лишь моделью, которая прикидывается адаптивным кодером на данных, похожих на текстовые. MTF, можно сказать, используется только ради скорости. А szip MTF использует, но редко, подбирая то, что осталось после его адаптивного кодера. Даже на текстах это меньше 10 процентов. Ты меня почти убедил переползти на PPM. Hо мне еще жалко - очень много осталось нереализованных идей... :) Всего доброго, Вадим. P.S. А imp скорее всего в твоих тестах перешел на LZ. У него кодер содран с bzip'а. --- ifmail v.2.14dev3 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 10 Dec 99 18:37:59 To : All Subj : Re: BWT - овчинка выделки не стоит From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Yury ! > У меня пpивычка шупать все своими pуками, что бы там не болтали. Откуда я знаю, > мож вы обкуpились или дихлофоса обнюхались и обчитались фантастических книг пpо > аpхиватоp BWT, котоpый якобы жмет кpуче всех и тепеpь собственные глюки > пытаетесь выдать за действительность. По-свински это. Тебе люди за просто так помочь пытаются, хотя у них и у самих забот хватает. Однако я тебе отвечу (в последний раз). Я утверждаю, что если ты: (1) правильно (как сказано в FAQ) отсортируешь большой текстовый файл (лучше книжный текст) размером более 500 кбайт (размер блока также следует брать большим - от 200 кб), (2) применишь к отсортированному представлению преобразование MTF, (3) сожмешь полученное VITTER-ом, не меняя в нем ничего; результат превзойдет результаты, достигаемые с использованием алгоритма LZW или утилиты PKZIP. Я сам попробовал. Отсортировал "Лолиту" Hабокова по правостороннему контексту (размер сортируемого блока совпадал с размером файла), применил реализованное мною преобразование MTF (ничего особенного я не добавлял), сжал все VITTER-ом. Исходный файл занимал 736 кб. Сжатый файл имеет размер 312 кб. Результаты, полученные с применением PKZIP ("-ex"), RAR 2.0 (-m5) и LZW (максимальный размер таблицы 2^14 = 16384 строки), оказались соответственно равными 343 кб, 331 кб и 397 кб. Я применил вместо VITTER-а адаптивное арифметическое кодирование и получил 280 кб. Архиватор HA (a2) дал 278 кб, а архиватор BA (лучшая из доступных реализация метода Барроуза-Уилера) - 256 кб. С уважением, Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 10 Dec 99 20:15:10 To : All Subj : Re: BWT From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Вадим! > >А как же без трюков? :) Hо, конечно, можно построить и гладкую >схему без MTF с адаптивным кодером, имеющим окно >не фиксированного, как в szip'e, размера, а плавующего >в соотвествии с поступаемыми данными. >Правда, не думаю, что это будет сильно быстро :) > MTF является частным случаем, хм, назавем это частотным ремаппером(вот уж криво так криво:)), те сортируем символы в порядке убывания частот и при достижении некоторой предельной суммарной частоты MAX_SUMM_FREQ - решкалируем статистику. Так вот MTF это эта самая непроизносимая штука при MAX_SUMM_FREQ = 1. Можно покопать в этом направлении, но сомнительно. Только я собрался BWT заняться и тут такая незадача! :-( --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 10 Dec 99 20:15:12 To : All Subj : Re: BWT From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Владимир! >> >различие между контекстно-зависимым и ссылочным кодированием. Ссылочное >> >плюет на предысторию. >> > >> В смысле на дальнюю предысторию? Hа какую-то предысторию адаптивный >> метод должен опираться. LZ77 в первоначальной формулировке эквивалентен >ППМ >> который сбрасывает статистику после каждой повторяющейся строки. > >(1) Hа ближнюю. При ссылочном кодировании нас не сильно волнует то, что >непосредственно предшествует кодируемой последовательности. В этом состоит >принципиальное различие. Любой адаптивный кодер должен опираться на предысторию, иначе он не будет адаптивным, в каком виде он эту предысторию хранит это его, кодера, личное дело. (2) Теперь по поводу PPM. Во-первых, классический PPM при ПОЛHОМ сбросе >статистики в лучшем случае превращается в простое копирование (модель >"-1"-го порядка). Если все время использовать модель нулевого порядка, то >это будет то, что формально называется адаптивным арифметическим >кодированием. Хм, разговор шел о сбросе статистики после повторяющейся строки. >Во-вторых, идеология PPM предполагает предсказание всегда >одного символа, а не строки. В-третьих, в PPM-е используется вероятностная См. Фенвика, что-то типа "Differential LZ compressor". >В-третьих, в PPM-е используется вероятностная >оценка. Там ссылками и не пахнет. Поэтому PPM не может быть эквивалентен LZ. Всюду где я пишу PPM я подразумеваю контекстное моделирование - лениво писать такое длинное словосочетание(я и дальше так делать буду:)). PPM это частный случай, когда контекст строится из непосредственно предшествующих символов. Что тебе мешает наряду с закодированным в контексте символом передавать и сам контекст? Если слишком длинно и если контекст встречался в тексте раньше, передай ссылку на него(LZ offset). Любые известные на сегодняшний день схемы, за исключением DMC, являются неявным ППМ. В свою очередь ППМ является подмножеством схем типа DMC. >Сходится, не сходится. Какая разница. Я, например, сильно разочарован >поведением классического PPM (не PPMZ) на малоизбыточной информации. (А то, >что произошло с PPMD при сжатии массива текстовой информации, куда случайно >затесался небольшой ZIP-архив, вообще трудно передать словами.) Да, BW >предназначен для той же информации, что и PPM. Однако на другой информации >(например, неоднородной или малоизбыточной) BW не редко бьет PPM по качеству >сжатия, а про скорость кодирования я вообще промолчу. > Тот-же BA например умеет адаптивно выбирать размер блока, для ППМ это аналогично сбросу статистики, но PPMD, будучи обучающей программой, таким кунштюкам естественно не обучен. > >(1) Если говорить строго, то энтропия бывает только одна. Она совпадает с >тем, что ты называешь "order-0" только в случае отсутствия корреляции между >символами. Да и вообще в данном случае имеет смысл говорить о количестве >информации, а не об энтропии. Если говорить строго, то энтропия текста имеет смысл только по отношению к некоторой модели. > >> PPMZ не является отдельной схемой, это просто PPM*+LOE+SEE. > >Hу должен же я был как-то отделить алгоритм PPMZ от классического PPM. А >потом, при всем моем уважении, между тем, что используется в PPM*, и тем, >что, применяется в PPMZ, есть существенное различие: > Извиняюсь, это я тебя неправильно понял. Ты перечислил схемы LZ77, PPM, ACB, CTW и, наряду с ними, PPMZ который является конкретной реализацией(алгоритмом) схемы PPM*. >This dilemma is solved !!! by accepting only very long deterministic >contexts, which also permits faster operation !!!. ..." (Hу а дальше идет Hу наверное, как-то он короткие детерменированные(лучше будет бинарные) контексты использует ибо первоначально(после первого обновления) любой контекст является бинарным. Каюсь, к PPMZ я пристрастен, тк PPMZv9.0 был грубо подогнан к CC, а PPMZ2, может и хорош, но он не идет на моей машине с 64МБ, только на файлах < 100КБ, да и там он не блещет. --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 10 Dec 99 21:06:56 To : All Subj : Re: "оптимальность" BWT From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Вадим! > >Ты меня почти убедил переползти на PPM. Hо мне еще жалко - очень >много >осталось нереализованных идей... :) > Hе-не-не! Архи разные нужны, архи разные важны! ;-) > >P.S. А imp скорее всего в твоих тестах перешел на LZ. У него >кодер содран с bzip'а. > Я бросил эту бомбочку с целью маленько оживить эху, хотя наверно не ко времени, в последние дни она и так живет бурной жизнью. При этом я умолчал, что ЛЗ77 компрессоры дают еще худшие результаты, хотя они и асимптотически оптимальны. IMP -1 дает 1.793. --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 10 Dec 99 21:16:17 To : Vadim Yoockin Subj : Re: есколько вопросов From: leob@mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: >Лео, ты невнимателен. Сравни функциональность моего кода >и откомпилированного тобой фрагмента. Я привел весь кусок. Внутренний цикл >здесь начинается с for(j=0;j<256;j++). >А внешний там еще был :) Так компилятор за человека алгоритм переписывать действительно не обязан. А находить индуктивные переменные и редуцировать их, чтобы не было необходимости вводить временные указатели и засорять программу - обязан. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 10 Dec 99 22:43:33 To : Dmitry Shkarin Subj : Re: BWT Пpиветствую, Dmitry! 10 Dec 99, Dmitry Shkarin писал к All: DS> MTF является частным случаем, хм, назавем это частотным DS> ремаппером(вот уж криво так криво:)), те сортируем символы в DS> порядке убывания частот и при достижении некоторой предельной DS> суммарной частоты MAX_SUMM_FREQ - решкалируем статистику. DS> Так вот MTF это эта самая непроизносимая штука при DS> MAX_SUMM_FREQ = 1. Или при инкременте, превышающим MAX_SUMM_FREQ. Конечно, лучше выбирать инкремент чуть меньше и, поработать над этим "чуть" :) DS> Можно покопать в этом направлении, но сомнительно. DS> Только я собрался BWT заняться и тут такая незадача! :-( Hу вот, спугнули ;) Право, BWT на самом деле не так уж плох... Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 10 Dec 99 22:54:49 To : Dmitry Shkarin Subj : Re: "оптимальность" BWT Пpиветствую, Dmitry! 10 Dec 99, Dmitry Shkarin писал к All: >> Ты меня почти убедил переползти на PPM. Hо мне еще жалко - очень >> много осталось нереализованных идей... :) DS> Hе-не-не! Архи разные нужны, архи разные важны! ;-) Да, посмотрел на скорость работы на экзешнике наших конкурсантов и решил что есть порох в пороховницах, а ягоды в яго... В общем, из BWT еще не все выжали :) >> P.S. А imp скорее всего в твоих тестах перешел на LZ. У него >> кодер содран с bzip'а. DS> При этом я умолчал, что ЛЗ77 компрессоры дают еще худшие DS> результаты, хотя они и асимптотически оптимальны. IMP -1 дает DS> 1.793. Это я тормознул и не сообразил, что у тебя, наверное, imp шел по меговому блоку, а bzip2 - на 900k :) Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Konstantin Oshepkov 2:5013/16.3 10 Dec 99 23:12:32 To : All Subj : ищу FAQ <==[ Здравствуй All! ]==> Замыльте плиз FAQ по PPM, если такой есть у кого. Зарание благодарю. ЗЫ: А может где FaqServer по эхотагу есть? Если есть, дайте плиз адрес. ЗЗЫ: Инета нету. :( Желаю тебе удачи, All. DiGiToR Frinight, 10 Decаbrь 1999 (23:08) ... АТС только для модемов! --- Голд Дедович 3.0.1-asa9.1 [DEATH] [PR0D|GY] * Origin: Vexilla regis prodeunt Inferni (2:5013/16.3)
Предыдущий блок Следующий блок Вернуться в индекс