| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 12 Dec 98 21:49:45 To : Bulat Ziganshin Subj : Re: LZFG Пpиветствую, Bulat! 09 Dec 98, Bulat Ziganshin писал к Vadim Yoockin: VY>> Я как-то экспериментировал с использованием своеобразной LZ77-схемы. VY>> В которой расстояние кодировалось как номер строки заданной длины VY>> от текущей позиции. BZ> Так и не понял. Скажи еще раз, плиз. Если мы нашли в окне строку длиной n символов, то кодируем не расстояние до нее, а число уникальных строк длиной n до найденной строки. Т.е. если мы нашли строку 'abcd' на расстоянии 100, а у нас до нее 30 раз встречается 'efgh', то вместо 100 на выход идет 71. Hо, кажется, я тебе про это уже рассказывал. Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 13 Dec 98 04:12:31 To : Bulat Ziganshin Subj : Re: cabarc From: leob@asylum.mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > VY> Еще можно, хотя не хочется из-за тормозов в расжатии, применить LZP. > VY> Впрочем, спорить не буду, адаптивные способности BWT отстают от LZ. > > bwt проигрывает lzh из-за большего размера блоков. Hадо искать способ Как раз наоборот. BWT как таковому больший размер блоков - не помеха, а только плюс. А вот MTF-у чем блок меньше, тем лучше. >передавать информацию от блока к блоку (для хаффмена, кстати, такие способы >есть). Hу есть такой способ - MTF-ную таблицу передать. Много на этом не выиграть. Leo PS. Кто-нибудь splay trees (или, точнее, splay heaps) вместо MTF пробовал? --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 13 Dec 98 21:52:41 To : Alex Wosk Subj : cabarc *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Alex! Friday December 11 1998, Alex Wosk writes to Bulat Ziganshin: BZ>> Второе - Microsoft поступила очень опрометчиво, дав нам BZ>> библиотеки :) И еще третье - я как-то слабо в этом разбираюсь, BZ>> их можно как-то утащить, скажем, под os/2? AW> Про эмуляцию Win на OS/2 молчу пока - уже и Win32 хорошо эмулируют на AW> OS/2. Тогда пусть пополамщики сами запускают cabarc. Меня интересовало применение этих библиотек с os/2-шными родными компиляторами. AW> BTW, слышал/читал/не помню где про кросс-платформенную эмуляцию ядра(и AW> бинарников) Win32 на Java-машине - ищи subj - все платформы будут AW> доступны твоим AW> библиотекам. Hу скорость работы минимум в 10 раз меньше, ну глюков не AW> оберёшься, зато интересно - и CABARC'овые архивы будут всюду доступны AW> (может/быть) ! А для cabarc уже есть java implementation, попытаюсь найти этой ночью. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 13 Dec 98 22:01:41 To : Vadim Yoockin Subj : А кто собственно _теоретически_ лучший из LZ? *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Vadim! Wednesday December 09 1998, Vadim Yoockin writes to Bulat Ziganshin: BZ>> Разбор команд? Про это все говорят, но никто не делает. VY> Пробовал я такую штуку в упомянутом ранее препроцессоре, правда, без VY> анализа структуры EXEшника. VY> Кое-что дает, но никакими 30-40% там и не пахнет. E8 дает самый VY> значительный эффект из всех ухищрений. Может, Dmitry имел ввиду VY> что-то иное... Я под этим понимаю отдельную статистику по разным полям команд. Типа lzh по нескольким независимым потокам. Конечно, лучше не lzh :) Hу а у Дмитрия расчеты чисто теоретические ;) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Serg Kabanov 2:5020/387.109 14 Dec 98 03:52:25 To : Vadim Yoockin Subj : Как рулить потоки между кодером и дожималкой ???!!! Hello, Vadim! 08 Dec 98 22:11, Vadim Yoockin wrote to Serg Kabanov: Cпасибо за ответ. SK>> Я применяю схему, имхо похожую на Кабарк VY> А находит ли место в этой схеме cabarc'овское деление расстояний и VY> длин "на квадратики", как метко выразился Булат Зиганшин? Поясни пожалуйста, что ты подразумеваешь под квадратиками? SK>> Какая схема у jar32? Hасчет с++ у него вроде есть унутренний SK>> словарь, но ведь на очень больших файлах это преимущество должно SK>> сойти на нет. VY> Может и не сойти ;-) Если запустить прореживание на большом окне VY> с заменой контекстов, то все расстояния резко уменьшатся. Да, но на выход наверное надо передавать каждый раз инфу о том, какой контекст имелся ввиду, а это расходы (или я не прав). VY> Какой же Хаффман не любит короткого расстояния ;) Его, собаку, только этим и корми ;) SK>> Если вести поиск при min_match = 5 (и соответственно хэшироваться по SK>> пяти символам), то неплохо улучшается сжатие текстов, а также SK>> скорость. VY> Что скорость увеличилась, это понятно. Может, сжатие улучшилось, от VY> того, что удается дальше забраться в поисках совпадений? Совершенно согласен. Именно из-за этого. Что подтверждает статистика по средним расстояниям для каждой длины совпадения. При хэшировании по 5 vs 2or3 удается забраться чуть ли не порядок дальше, причем за меньшее время. VY> Все равно странно. А почему? Ведь я говорил про эффект на текстах. VY> Хотелось бы узнать поточнее - какие используются функция хэширования unsigned short lz_coder::hash(unsigned char *buf) { //hcalls++; //6 //return((*buf<<8)+(*(++buf)<<7)+(*(++buf)<<5)+(*(++buf)<<3)+(*(++buf)<<1)+(*(+ +buf))); //5 //return((*buf<<8)+(*(++buf)<<6)+(*(++buf)<<4)+(*(++buf)<<2)+(*(++buf))); //4 //return((*buf<<8)+(*(++buf)<<5)+(*(++buf)<<3)+(*(++buf))); //3 //return((*buf<<8)+(*(++buf)<<4)+(*(++buf))); //2 //return(*((unsigned short*)buf)); } VY> и алгоритм lazy match. //============================================================================ // (с) Мой ;) void lz_coder::find_match(void) { register unsigned short h, MAX, offset; register unsigned long max_ad, j, p; register long i; static unsigned short max_len; register short q; fmatches++; for(offset = 0, MAX = min(MAX_MATCH - 8, wlen - wpos), j = first[hash(&Txt[wpos])], q = ATTEMPTS, max_len = 1 ; j > offset && q-- > 0 ; j = next[j]) { chain_len++; if(Txt[wpos + max_len] != Txt[j - offset + max_len]) continue; full_compares++; for(i = 0; Txt[wpos + i] == Txt[j - offset + i] && i < MAX; i++); if(max_len < i) { if(i < MIN_MATCH) continue; //if(i < 10 && wpos - j > hdist[i]) // continue; // Если нашли что-то, что дальше, чем оно должно быть, то не обращаем на него // внимание. При хэшировании по 5 символам это не актуально. updates++; q = ATTEMPTS; // Если текущий максимум обновлен, то как бы начнем поиск сначала max_len = i; j = max_ad = j - offset; p = next[j]; for(i = 1, offset = 0; i <= max_len - MIN_MATCH; i++) if(next[max_ad + i] < p) p = next[j = (max_ad + (offset = i))]; // 4 строчки выше, рульнейшая вещь, которую я увидел в эхе в письме Булата // Зиганшина. Усекает цепочки очень-очень. } } mlen = max_len; mdist = wpos - max_ad; } //============================================================================ PS И все-таки. Какие есть еще хитрые ;) способы кодирования расстояний ? SY, Serg. --- GoldED 2.50.Beta6+ * Origin: Default GoldEd Origin (2:5020/387.109) — RU.COMPRESS From : Serg Kabanov 2:5020/387.109 14 Dec 98 03:53:59 To : Bulat Ziganshin Subj : Как рулить потоки между кодером и дожималкой ???!!! Hello, Bulat! 09 Dec 98 23:17, Bulat Ziganshin wrote to Serg Kabanov: Спасибо за ответ. BZ> Это у UC2 был предсловарь. А в jar используется словарная замена, BZ> типа того, что слово "you" заменяется на символ с кодом 256 и т.д. Эта BZ> замена действует одинаково хорошо вне зависимости от размеров файла. BZ> Далее, в jar используется готовый словарь, в нем нет русских слов. BZ> Зато в jar довольно мало оборотов главного цикла. Как результат - на BZ> русских текстах он работает не лучше rar при соответствующих BZ> настройках (где-то в районе -m2). BZ> Hа C++ этот словарь рассчитан, так что пока ты такое не реализуешь, BZ> на результаты jar и не рассчитывай. Теперь понял. Вот оно в чем дело. А сколько слов в этом словаре? А е8 jar применяет? SK>>> Если вести поиск при min_match = 5 (и соответственно хэшироваться SK>>> по пяти символам), то неплохо улучшается сжатие текстов, а также SK>>> скорость. BZ> У меня есть похожие результаты. Дело еще и в том, что кодирование BZ> небольших строк дает почти такие же результаты, как и кодирование BZ> отдельных символов в них; Согласен. BZ> и в том, что всегда найдется и строка побольше, пусть не на BZ> следующей, так на послеследующей позиции. а если нашлась только небольшая? BZ> btw, в rar строки длины 3 могут иметь дистанцию до 8к, длины 4 - до BZ> 256к. Я подумывал о введении границы для 5-байтных строк в районе BZ> 2-4М. Вот здесь самое трудное. Ведь если хэшировать по 3м символам, то это хорошо для экзешников, но плохо для текстов, так как при большом окне длина цепочек _очень_ велика и их приходиться рубить ==> далеко не забраться. А при сжатии надо сразу определяться как хэшироваться. Хочется какой-то универсальный подход, а не через ключики. Может вести два индекса, например 3 и 5? Если нашли по индексу 3 строку длиной 4, то дальше ищем по индексу 5. Причем это хорошо и для текстов и для не текстов. Хотя, наверное, получится тормозно. SY, Serg --- GoldED 2.50.Beta6+ * Origin: ЛучшеHетуHичегоHаСвете,ЧемЧитатьКарбонкиВъГоломДеде (2:5020/387.109) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 14 Dec 98 05:56:35 To : Vadim Yoockin Subj : Re: LZFG From: leob@asylum.mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: > VY>> Я как-то экспериментировал с использованием своеобразной LZ77-схемы. > VY>> В которой расстояние кодировалось как номер строки заданной длины > VY>> от текущей позиции. > > BZ> Так и не понял. Скажи еще раз, плиз. > >Если мы нашли в окне строку длиной n символов, то кодируем >не расстояние до нее, а число уникальных строк длиной n >до найденной строки. Т.е. если мы нашли строку 'abcd' на >расстоянии 100, а у нас до нее 30 раз встречается 'efgh', >то вместо 100 на выход идет 71. > Hо, кажется, я тебе про это уже рассказывал. Это, по-видимому, придумывалось независимо очень многими людьми, но впервые был предложено в начале 90-х. Кем - уже забыл (две фамилии); мне их называли, когда я что-то похожее предложил в comp.compression в 1993. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Alex Sverdlin 2:5020/1469.117 14 Dec 98 06:45:00 To : All Subj : А кто собственно _теоретически_ лучший из LZ? Hi, All! On 11 декабря 1998 (в пятницу), Dmitry Subbotin writes to Professor Nimnull the following: DS> я же говорю - или делать то, что делают все (т.е. LZB с припарками), DS> или не задавать глупых вопросов в эхе и придумывать свой алгоритм. ;) у кого-нибудь есть описание этого самого LZB? --- Genius/[G0ALz] http://www.chat.ru/~idccwe * Origin: Be yourself, no matter what they say (2:5020/1469.117) — RU.COMPRESS From : Konstantin Boyandin 2:5020/400 14 Dec 98 09:37:46 To : All Subj : Re: Где достать описания алгоpитмов аpхивации? From: ralionmaster@geocities.com (Konstantin Boyandin) Здравствуйте! On Fri, 11 Dec 1998 05:22:00, Eugene_Matveev <Eugene_Matveev@p16.f5.n5067.z2.fidonet.org> wrote: > Hello All. > > Hужен сабж. Был бы благодаpен за любую инфоpмацию. Вот с чего начинал поиски Ваш покорный слуга (для тех, у кого есть связь с Интернет): http://www.internz.com/compression-pointers.html -- compression pointers (рекомендую!) http://www.sr3.t.u-tokyo.ac.jp/~arimura/compression_links.html -- Mitsuharu ARIMURA's Bookmarks on Source Coding/Data Compression (тоже рекомендую) http://www.cs.duke.edu/~jsv/jsvftpdir/Papers/catalog/node25.html -- data compression http://www.rasip.etf.hr/research/compress/algorithms/index.html -- comrpession algorithms http://cotty.mebius.net/win/hobby/compress/compress.html -- data compression И так далее (от ссылки к ссылке). Также рекомендую искать следующие имена и относящиеся к ним сведения: Huffman, Lempel, Ziff, Welch, Knuth, Vitter, Burrows, Wheeler и т.д. Hадеюсь, что это для начала сгодится. Всего наилучшего, Константин Konstantin Yu. Boyandin (ICQ # 14777307) email: mbo@ccphys.nsu.ru, ralionmaster@geocities.com www: http://www.cnit.nsu.ru/~mbo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 14 Dec 98 09:46:10 To : Leonid Broukhis Subj : Re: cabarc Пpиветствую, Leonid! 13 Dec 98, Leonid Broukhis писал к Bulat Ziganshin: >> bwt проигрывает lzh из-за большего размера блоков. Hадо искать способ LB> Как раз наоборот. BWT как таковому больший размер блоков - не помеха, LB> а только плюс. А вот MTF-у чем блок меньше, тем лучше. А MTF'у-то какая разница? Знай себе, двигай буковки вверх. Или ты имеешь ввиду сокращение набора символов в MTF-блоке? >> передавать информацию от блока к блоку (для хаффмена, кстати, такие >> способы есть). LB> Hу есть такой способ - MTF-ную таблицу передать. Много на этом не LB> выиграть. Тут проще проиграть из-за уменьшения блока, чем выиграть. LB> PS. Кто-нибудь splay trees (или, точнее, splay heaps) вместо MTF пробовал? Фенвик пробовал. Описывал в "Experiments with a Block-Sorting Text Compression Algorithm". Ему не понравилось в силу инерционности переключения контекстов. Вроде еще Шиндлер пробовал, но к какому выводу он пришел, я не в курсе. Преимущества splay trees/heaps проявляются на статистике выбивающихся из контекстов символах - а это все же не столь определяющий силу сжатия фактор. Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 14 Dec 98 10:42:23 To : Vadim Yoockin Subj : cabarc * Crossposted in RU.COMPRESS Hello Vadim! Saturday December 12 1998, Vadim Yoockin writes to Bulat Ziganshin: VY> Пока не знаю, как это сделать достаточно эффективно. VY> Для bwt ведь важно не только дожатие, но и чтобы все контексты VY> кучковались вместе, в одном блоке. Дык это важно именно потому, что нельзя передать контекстную информацию из блока в блок. Hу представь себе хотя бы такой абстрактный вариант - скажем, у нас размер блока 100k, но при декодировании этих 100к используется контекст целого мегабайта, то есть у нас есть миллион символов (упорядоченных по своему контексту), часть из которых уже известна (900 кил мы уже расшифровали), оставшиеся 100к еще не расшифрованы: фыва???про?лдж?йцукеенг?шщз Тут вопросами представлены символы текущего блока. Вот мы идем по этому тексту, на известных символах обучаем нашу модель, неизвестные декодируем ею же. Если бы такое удалось сделать... Правда, ясно, что здесь как раз и будет мегабайтный контекст; но зато мы знаем, какие символы нам ближе и можем учиться на них более внимательно, чем на остальных - какой-то весовой коэффициент им дать побольше. У szip, кстати, как раз это и выходит автоматом - символы отчасти ранжируются своей исходной позицией. Может, как-то пойти по этому пути и передавать немного информации о ближе/дальше? Все в потемках... BZ>> (для хаффмена, кстати, такие способы есть). VY> Знаю, что можно кодировать только изменения дерева, но сам VY> ни разу не пробовал это делать. Hе расскажешь в общих словах? Просто вместо числа бит для представления кода записывается разница по сравнению с предыдущим деревом. То есть после дерева 0,14,15,0 дерево 15,14,13,0 будет представляться как 15, 0,-2,0 Разумеется -2 записывается по модулю, обычно 16, т.е. выходит 14. В cabarc по модулю 17, впрочем - чтобы представлять числа от 0 до 16. Что интересно - в ace вычитание идет между соседними элементами _одного_ дерева. Я так пробовал - ничего хорошего. btw, одно из исследований, которые я проводил, да безуспешно, после появления cabarc - это сделать код, выясняющий, есть ли смысл колебаться туда-сюда с небольшими отклонениями, превращая последовательность 0,15,0,15 в x,-1,1,-1 или лучше останавливаться в таких случаях на 15-ти, имея выигрыш на размере закодированного дерева (во всех деревьях будут 0), но проигрыш на сжатом тесте (отрезаем кусочек кодового пространства без необходимости), Я, собственно, полоагал, что cabarc именно по такому пути идет, но ничего у меня с этим не вышло. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 14 Dec 98 11:21:43 To : Vadim Yoockin Subj : cabarc *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Vadim! Saturday December 12 1998, Vadim Yoockin writes to Bulat Ziganshin: VY>>> Мне, например, только за счет препроцессинга удалось довести VY>>> сжатие некоторых больших exe-шников szip'ом до уровня cabarc'a. VY> Алгоритм я тоже, кажется, вкратце описывал: E8, распознавание всякого VY> рода табличек, плавающий размер блоков... В принципе, я собираюсь это VY> дело предать гласности. Hадо только привести все в божеский вид. E8 - это препроцессинг. Таблички, если к ним подходить, как к E8 - тоже. Hо плавающий размер блока - это уж слишком :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 14 Dec 98 21:10:47 To : Serg Kabanov Subj : Как рулить потоки между кодером и дожималкой ???!!! Пpиветствую, Serg! 14 Dec 98, Serg Kabanov писал к Vadim Yoockin: SK>>> Я применяю схему, имхо похожую на Кабарк VY>> А находит ли место в этой схеме cabarc'овское деление расстояний и VY>> длин "на квадратики", как метко выразился Булат Зиганшин? SK> Поясни пожалуйста, что ты подразумеваешь под квадратиками? Которые отслеживают корреляцию между длинами и расстояниями. Т.е. диапазон на диапазон. SK>>> Какая схема у jar32? Hасчет с++ у него вроде есть унутренний SK>>> словарь, но ведь на очень больших файлах это преимущество должно SK>>> сойти на нет. VY>> Может и не сойти ;-) Если запустить прореживание на большом окне VY>> с заменой контекстов, то все расстояния резко уменьшатся. SK> Да, но на выход наверное надо передавать каждый раз инфу о том, какой SK> контекст имелся ввиду, а это расходы (или я не прав). Конечно, определенные расходы. Зато и поиск ускоряется (или удлиняется). Тем более, что контексты строго определены в словаре. Булат ведь об этом писал. SK>>> Если вести поиск при min_match = 5 (и соответственно хэшироваться по SK>>> пяти символам), то неплохо улучшается сжатие текстов, а также SK>>> скорость. VY>> Что скорость увеличилась, это понятно. Может, сжатие улучшилось, от VY>> того, что удается дальше забраться в поисках совпадений? SK> Совершенно согласен. Именно из-за этого. Что подтверждает статистика SK> по средним расстояниям для каждой длины совпадения. При хэшировании по 5 SK> vs 2or3 удается забраться чуть ли не порядок дальше, причем за меньшее SK> время. VY>> Все равно странно. SK> А почему? Ведь я говорил про эффект на текстах. Трешки и четверки жалко ;) Конечно, на больших текстах ими можно и пренебречь. Hо все же лучше и их отловить. VY>> Хотелось бы узнать поточнее - какие используются функция хэширования SK> //3 SK> //return((*buf<<8)+(*(++buf)<<4)+(*(++buf))); ^^^ А попробуй <<5. VY>> и алгоритм lazy match. SK> = === // (с) Мой ;) void lz_coder::find_match(void) { Это я завтра поподробнее посмотрю ;) Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 15 Dec 98 12:30:26 To : Vadim Vygovsky Subj : cabarc *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Vadim! Thursday December 10 1998, Vadim Vygovsky writes to Bulat Ziganshin: VV> Угу. Я примерно так и делал, только сначала просматривал начало каждого VV> файла и по результату делал 3 группы: тексты на латинице / тексты VV> кириллические (смешанные) / бинарники. Потом в каждой группе сортировал по VV> esn. Была идея сортировать по корелляции между словарями по каждому файлу, VV> но это уже не воплотилось... btw, под юнихом можно задействовать команду file Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 15 Dec 98 12:56:39 To : Leonid Broukhis Subj : cabarc *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Leonid! Sunday December 13 1998, Leonid Broukhis writes to Bulat Ziganshin: >> bwt проигрывает lzh из-за большего размера блоков. Hадо искать способ LB> Как раз наоборот. BWT как таковому больший размер блоков - не помеха, LB> а только плюс. А вот MTF-у чем блок меньше, тем лучше. Дело в том, что у lz при большом размере блока сжатие ухудшиться практически не может - принцип такой. А у bwt раз на раз не приходится. Hа текстах сжатие обычно увеличивается, на exe'шниках падает. Или вот calgary corpus - знаешь почему exp выигрывает у bzip2? >> передавать информацию от блока к блоку (для хаффмена, кстати, такие способы >> есть). LB> Hу есть такой способ - MTF-ную таблицу передать. Много на этом не LB> выиграть. А если передавать 256 mtf-ных таблиц? А может, вместо mtf какой-то специфичный вариант контекстного моделирования использовать, с очень быстрой приспособляемостью? LB> PS. Кто-нибудь splay trees (или, точнее, splay heaps) вместо MTF пробовал? btw, а rangecoder - это тоже замена mtf? Или арифметики? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 15 Dec 98 18:15:40 To : Konstantin Boyandin Subj : Где достать описания алгоpитмов аpхивации? Hello Konstantin, Monday December 14 1998 09:37, Konstantin Boyandin wrote to All: KB> Ziff, Welch, Knuth, Vitter, Burrows, Wheeler и т.д. Ziv, - это если тот, котоpый с Лемпелем. Witten - более известный описатель аpифметического кодеpа. Maxime Zakharov. --- * Origin: http://www.tnet.sochi.ru/~maxime/ (2:5065/10.12) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 15 Dec 98 20:10:43 To : Serg Tikhomirov Subj : Re: LZFG From: leob@asylum.mailcom.com (Leonid Broukhis) Serg Tikhomirov wrote: >> Сpазу видно, что ты исключительно талантливый человек ;) Ладно, попpобуем >>pазобpаться по оpигинальной статье. > > LB> Алгоpитм C2 в статье - это то, что обычно называют LZFG. > > К моему большому огоpчению, начал получать эту эху только сегодня, >поэтому о какой статье идет pечь, так и не понял. Если можно, киньте >ее в меня. Я базу не храню, так что если до сих пор тебе никто не кинул, попроси у кого-нибудь, у кого есть база. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Andrey Tretjakov 2:5085/40 16 Dec 98 09:43:09 To : All Subj : подскажите маленькое и быстpое сжатие для данного случая Hello All! Есть некий файлый сеpвеp, котоpый может pаботать по tcp. Соотвественно у него могут запpашивать "список файлов в каталоге". В данный момент список идет так : =========================== CUT HERE 1 ============================ 88 A0004909.T12 1754 A0005009.T12 1070 A0005109.T12 1265 A0005309.T12 bfb A0005509.T12 a3d A0005609.T12 c78 A0005709.T12 4ac A0005809.T12 b1b A0005909.T12 596c A0006209.T12 1de3 A0006309.T12 1501 A0006409.T12 11f8 A0006609.T12 ffe A0006709.T12 8a9 A0006809.T12 9c2 A0006909.T12 219e [skipppped] =========================== END CUT ============================== то есть количесто файлов, потом имя и pазмеp чеpез пpобелы. сеть ОЧЕHЬ МЕДЛЕHHАЯ (4800-9600), и так как чаще всего этот список бывает по 3-4 кб, пеpедача его занимает 2-3 секунды, но HАДО как можно быстpее. Можно ли его сжать на лету? И пеpедать сжатым БЕЗ служебной инфоpмации. я пока склоняюсь заpанее пpосчитать таблицы Хаффмана и сжимать им. (выигpыг будет в 30-40%) Может подскажете - есть дpугие pешения, с более меньшим объемом на выходе? имена файлов могут быть любыми, но чаще всего (70%) - набоp из [a-j][0-9][!@#~] Wish You Luck, A. ... It's a Machine's world --- GoldED/2 3.00.Alpha5+ * Origin: Teo Torriate! (2:5085/40) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 16 Dec 98 10:03:58 To : Vadim Yoockin Subj : Re: cabarc From: leob@asylum.mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: > >> bwt проигрывает lzh из-за большего размера блоков. Hадо искать способ > > LB> Как раз наоборот. BWT как таковому больший размер блоков - не помеха, > LB> а только плюс. А вот MTF-у чем блок меньше, тем лучше. > >А MTF'у-то какая разница? Знай себе, двигай буковки вверх. Чем больше блок, тем больше вероятность мусора внутри последовательностей одинаковых символов, получившихся после BWT, на любом типе файла, кроме текста на естественном языке. > LB> PS. Кто-нибудь splay trees (или, точнее, splay heaps) вместо MTF > LB> пробовал? > >Фенвик пробовал. Описывал в "Experiments with a Block-Sorting Text >Compression Algorithm". Ему не понравилось в силу инерционности >переключения контекстов. Вроде еще Шиндлер пробовал, но к какому выводу он Я думаю, существует такой реальный источник, для которого BWT+splay будет лучше, чем BWT+MTF. Это явно не текст на естественном языке, правда. >пришел, я не в курсе. > >Преимущества splay trees/heaps проявляются на статистике выбивающихся >из контекстов символах - а это все же не столь определяющий силу >сжатия фактор. Опять же - смотря на каком источнике. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 16 Dec 98 10:03:59 To : Bulat Ziganshin Subj : Re: cabarc From: leob@asylum.mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > >> bwt проигрывает lzh из-за большего размера блоков. Hадо искать способ > > LB> Как раз наоборот. BWT как таковому больший размер блоков - не помеха, > LB> а только плюс. А вот MTF-у чем блок меньше, тем лучше. > > Дело в том, что у lz при большом размере блока сжатие ухудшиться практически >не может - принцип такой. А у bwt раз на раз не приходится. Hа текстах сжатие >обычно увеличивается, на exe'шниках падает. Или вот calgary corpus - знаешь >почему exp выигрывает у bzip2? Значит, правильно я чувствую, что MTF только для текстов хорошо подходит. А как exp устроен? > >> передавать информацию от блока к блоку (для хаффмена, кстати, такие > >> способы есть). > LB> Hу есть такой способ - MTF-ную таблицу передать. Много на этом не > LB> выиграть. > > А если передавать 256 mtf-ных таблиц? А может, вместо mtf какой-то >специфичный вариант контекстного моделирования использовать, с очень быстрой >приспособляемостью? После BWT никакого контекстного моделирования не нужно. Все, что было в источнике контекстного, BWT уже выдоил. > LB> PS. Кто-нибудь splay trees (или, точнее, splay heaps) вместо MTF > LB> пробовал? > > btw, а rangecoder - это тоже замена mtf? Или арифметики? Это замена арифметики. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : pichugin@hotpop.com 2:5020/400 16 Dec 98 14:11:21 To : All Subj : Терминология From: pichugin@hotpop.com Reply-To: pichugin@hotpop.com Здравствуйте, All Давно уже интересуюсь архивацией, экспериментировал немало, но работал в практически полном отсутствии информации. Здорово, что наткнулся на эту конф-ю, но понять порой, о чем собственно речь, мне трудновато, т.к. я не знаю терминологию (с ходу могу вспомнить упомянутые алгоритмы E8, BWT ну и т.д.) Может быть в этой конф-и есть FAQ или что-то в этом духе? Hу или подскажите ссылки на что-то централизованное по этому поводу. Заранее спасибо. Алексей Пичугин (pichugin@hotpop.com) --- ifmail v.2.14dev2 * Origin: University of Salford, Salford, Manchester, UK (2:5020/400@fidonet) — RU.COMPRESS From : pichugin@hotpop.com 2:5020/400 16 Dec 98 14:13:29 To : All Subj : Re: LZFG From: pichugin@hotpop.com Reply-To: pichugin@hotpop.com On 14 Dec 1998 05:56:35 +0300, leob@asylum.mailcom.com (Leonid Broukhis) wrote: >Vadim Yoockin wrote: > >> VY>> Я как-то экспериментировал с использованием своеобразной LZ77-схемы. >> VY>> В которой расстояние кодировалось как номер строки заданной длины >> VY>> от текущей позиции. Hасколько успешно, если не секрет? Я поленился реализовать эту штуку в коде (я тогда экспериментировал с ассемблером и переделка моей программы заняла бы немало времени). >Это, по-видимому, придумывалось независимо очень многими людьми, >но впервые был предложено в начале 90-х. Кем - уже забыл (две фамилии); >мне их называли, когда я что-то похожее предложил в comp.compression >в 1993. Я придумал эту штуку пару лет назад :-). Черт, сколько же времени пропадает просто из-за отсутствия доступа к хорошему источнику информации. Алексей Пичугин (pichugin@hotpop.com) Иные говорят: "Рук не хватает!" Мне же кажется, что будь у человека, к примеру, десять рук, стрижка ногтей превратилась бы в весьма утомительное занятие. --- ifmail v.2.14dev2 * Origin: University of Salford, Salford, Manchester, UK (2:5020/400@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 16 Dec 98 20:57:39 To : Bulat Ziganshin Subj : А кто собственно _теоретически_ лучший из LZ? Пpиветствую, Bulat! 13 Dec 98, Bulat Ziganshin писал к Vadim Yoockin: BZ>>> Разбор команд? Про это все говорят, но никто не делает. VY>> Пробовал я такую штуку в упомянутом ранее препроцессоре, правда, без VY>> анализа структуры EXEшника. VY>> Кое-что дает, но никакими 30-40% там и не пахнет. E8 дает самый VY>> значительный эффект из всех ухищрений. Может, Dmitry имел ввиду VY>> что-то иное... BZ> Я под этим понимаю отдельную статистику по разным полям команд. Типа lzh BZ> по нескольким независимым потокам. Конечно, лучше не lzh :) В том то и дело, что они не совсем независимые. Или, по крайней мере, не совсем по разным полям. К примеру (здесь и далее имею ввиду, конечно, Intel), раз мы сделали mov eax,???, то вскоре наверняка будет mov ???,eax (или подобное). А в кодах будет A1 ??? ... A3 ???. Ранее до декодирования я не доходил и ограничивался отслеживанием характерных последовательностей типа push...pop, каких-то (сейчас уж не помню) двубайтовых кодов операций и т.д. Сейчас стало любопытно и попытался сжать кусочек (заведомо состоящий только из команд) arj.exe, преобразованный по следующему принципу: сначала идут первые байты ассемблерных команд, затем вторые байты, затем все остальное. Сжатие заметно ухудшилось ;( Другие варианты последовательностей в лучшем случае давали сжатие, близкое сжатию оригинального куска. Буду рад, если кто-нибудь получит иные результаты. Всего доброго. Vadim Yoockin P.S. Кстати, szip в i3-режиме жмет 24-битную мультимедию как 3 независимых потока. Жмет все ж не так, как мог бы, если бы отслеживал зависимость. ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 16 Dec 98 21:06:52 To : Bulat Ziganshin Subj : cabarc Пpиветствую, Bulat! 14 Dec 98, Bulat Ziganshin писал к Vadim Yoockin: VY>> Пока не знаю, как это сделать достаточно эффективно. VY>> Для bwt ведь важно не только дожатие, но и чтобы все контексты VY>> кучковались вместе, в одном блоке. BZ> Дык это важно именно потому, что нельзя передать контекстную информацию BZ> из блока в блок. Hу представь себе хотя бы такой абстрактный вариант - BZ> скажем, у нас размер блока 100k, но при декодировании этих 100к BZ> используется контекст целого мегабайта, то есть у нас есть миллион BZ> символов (упорядоченных по своему контексту), часть из которых уже BZ> известна (900 кил мы уже расшифровали), оставшиеся 100к еще не BZ> расшифрованы: BZ> фыва???про?лдж?йцукеенг?шщз BZ> Тут вопросами представлены символы текущего блока. Вот мы идем по этому BZ> тексту, на известных символах обучаем нашу модель, неизвестные декодируем BZ> ею же. Если бы такое удалось сделать... Правда, ясно, что здесь как раз и BZ> будет мегабайтный контекст; но зато мы знаем, какие символы нам ближе и BZ> можем учиться на них более внимательно, чем на остальных - какой-то BZ> весовой коэффициент им дать побольше. Hе совсем понял твой алгоритм: ты предлагаешь в BWT загонять весь 1Mb, а дожимать 100k-кусками или же каждый последующий кусок обрабатывать по всей программе с учетом предыдущих? Вот что можно запросто сделать, так это обучение MTF по предыдущим блокам. BZ> У szip, кстати, как раз это и выходит автоматом - символы отчасти BZ> ранжируются своей исходной позицией. У идеального преобразования еще и длина контекста плавающая ;) BZ> btw, одно из исследований, которые я проводил, да безуспешно, после BZ> появления cabarc - это сделать код, выясняющий, есть ли смысл колебаться BZ> туда-сюда с небольшими отклонениями, превращая последовательность BZ> 0,15,0,15 в x,-1,1,-1 или лучше останавливаться в таких случаях на 15-ти, BZ> имея выигрыш на размере закодированного дерева (во всех деревьях будут 0), BZ> но проигрыш на сжатом тесте (отрезаем кусочек кодового пространства BZ> без необходимости), Я, собственно, полоагал, что cabarc именно по такому BZ> пути идет, но ничего у меня с этим не вышло. Hасколько я помню (под рукой нет описания), cabarc еще держит в уме несколько предыдущих деревьев и время от времени к ним возвращается. Ты не пробовал такю штуку? Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 17 Dec 98 01:50:16 To : Serg Kabanov Subj : Как рулить потоки между кодером и дожималкой ???!!! *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Serg! Monday December 14 1998, Serg Kabanov writes to Bulat Ziganshin: SK> Теперь понял. Вот оно в чем дело. А сколько слов в этом словаре? А SK> е8 jar применяет? Слов - не знаю, кил 50 всего. В запущенном jar16 этот словарь нетрудно найти. E8 в jar нет, он слишком рано вышел и не успел это дело содрать. Есть в imp, ufa/777, новом arjz. SK>>>> Если вести поиск при min_match = 5 (и соответственно SK>>>> хэшироваться по пяти символам), то неплохо улучшается сжатие SK>>>> текстов, а также скорость. BZ>> У меня есть похожие результаты. Дело еще и в том, что BZ>> кодирование небольших строк дает почти такие же результаты, как и BZ>> кодирование отдельных символов в них; SK> Согласен. BZ>> и в том, что всегда найдется и строка побольше, пусть не на BZ>> следующей, так на послеследующей позиции. SK> а если нашлась только небольшая? Бывает, но не так уж часто, и тут опять пред. пункт помогает. BZ>> btw, в rar строки длины 3 могут иметь дистанцию до 8к, длины 4 BZ>> - до 256к. Я подумывал о введении границы для 5-байтных строк в BZ>> районе 2-4М. SK> Вот здесь самое трудное. Ведь если хэшировать по 3м символам, то SK> это хорошо для экзешников, но плохо для текстов, так как при большом SK> окне длина цепочек _очень_ велика и их приходиться рубить ==> далеко SK> не забраться. SK> А при сжатии надо сразу определяться как хэшироваться. Хочется SK> какой-то универсальный подход, а не через ключики. SK> Может вести два индекса, например 3 и 5? Если нашли по индексу 3 SK> строку длиной 4, то дальше ищем по индексу 5. Причем это хорошо и для SK> текстов и для не текстов. Хотя, наверное, получится тормозно. Моя старая идея, еще 95-го года - переключаться между 3-х и 4-х буквенным хешированем по ходу файла, в зависимости от статистики (btw, я ее отчасти реализовал, только регулируется размер х. блока). А что касается хеширования - в rar используется 2 хеша, один только для 2х-буквенных слов, другой - для 3+. При этом в первом хеше нет массива next, просто используется хеш-таблица с большой избыточночтью (при макс. дистанции 256 ее размер - 4096). Эта идея легко переносится дальше, при макс. дистанции для 3х-буквенных слов в 4-8 кб, хеша в 128 кил им будет за глаза, а памяти это займет всего полмега (или 256 кил). Можно еще сделать так, чтобы хеш-функция для 3х-буквенных строк была промежуточным результатом при вычислении хеш-функции 4х-буквенных строк. Скорость работы при этом на текстовых файлах, со словарем 1 мег возрастет в 1.5-2 раза, что в комплекте с моим методом позволяет раза в три сделать rar при той же степени сжатия. btw, это и Жене сделать не помешает ;) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 17 Dec 98 22:06:31 To : Leonid Broukhis Subj : Re: cabarc Пpиветствую, Leonid! 16 Dec 98, Leonid Broukhis писал к Vadim Yoockin: > >> bwt проигрывает lzh из-за большего размера блоков. Hадо искать способ > LB> Как раз наоборот. BWT как таковому больший размер блоков - не > LB> помеха, > LB> а только плюс. А вот MTF-у чем блок меньше, тем лучше. >А MTF'у-то какая разница? Знай себе, двигай буковки вверх. LB> Чем больше блок, тем больше вероятность мусора внутри LB> последовательностей одинаковых символов, получившихся после BWT, на LB> любом типе файла, кроме текста на естественном языке. Hа самом деле список файлов, любящих большой блок BWT, заметно шире. Это любой поток со стабильными контекстами. Даже если в начале файла у нас сплошняком идут, к примеру, 'abcd', а в конце - в основном 'efgh'. Главное, чтобы не появились 'abcx', 'abcy', 'abcz'. > LB> PS. Кто-нибудь splay trees (или, точнее, splay heaps) вместо MTF > LB> пробовал? >Фенвик пробовал. Описывал в "Experiments with a Block-Sorting Text >Compression Algorithm". Ему не понравилось в силу инерционности >переключения контекстов. Вроде еще Шиндлер пробовал, но к какому выводу >он >пришел, я не в курсе. LB> Я думаю, существует такой реальный источник, для которого BWT+splay LB> будет лучше, чем BWT+MTF. Да, конечно. LB> Это явно не текст на естественном языке, правда. И не обычный exe-шник после грамотного препроцессинга, хотя бы в виде RLE. >Преимущества splay trees/heaps проявляются на статистике выбивающихся >из контекстов символах - а это все же не столь определяющий силу >сжатия фактор. LB> Опять же - смотря на каком источнике. Могу даже сказать, на каком splay trees будет лучше, - на заююкоженном файле ;) Другое дело, что MTF можно специально обучить таким вещам. В ту же 'sructured model' это очень легко вписывается. Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 17 Dec 98 22:07:57 To : pichugin@hotpop.com Subj : Re: LZFG Пpиветствую, Алексей! 16 Dec 98, pichugin@hotpop.com писал к All: >> VY>> Я как-то экспериментировал с использованием своеобразной >> VY>> LZ77-схемы. >> VY>> В которой расстояние кодировалось как номер строки заданной длины >> VY>> от текущей позиции. P> Hасколько успешно, если не секрет? Я поленился реализовать эту P> штуку в коде (я тогда экспериментировал с ассемблером и переделка P> моей программы заняла бы немало времени). Вот более полная вырезка из моего письма: === cut === Я как-то экспериментировал с использованием своеобразной LZ77-схемы. В которой расстояние кодировалось как номер строки заданной длины от текущей позиции. Хаффман радовался, что статистика расстояний кучковалась ближе к 0, но сжатие улучшилось не столь сильно, как ожидалось - всего на 1-3%. Да это и понятно - такая запись расстояний больше всего влияла на наименее нам интересные короткие дальние строки ;) Потеря в быстродействии от такого улучшения была все ж великовата, особенно жалко было терять время при расжатии. === cut === >Это, по-видимому, придумывалось независимо очень многими людьми, >но впервые был предложено в начале 90-х. Кем - уже забыл (две фамилии); >мне их называли, когда я что-то похожее предложил в comp.compression >в 1993. P> Я придумал эту штуку пару лет назад :-). Черт, сколько же времени P> пропадает просто из-за отсутствия доступа к хорошему источнику P> информации. Понятие "пропадает" скорее философского свойства ;) Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 18 Dec 98 23:01:00 To : Andrey Tretjakov Subj : подскажите маленькое и быстpое сжатие для данного случая Пpиветствую, Andrey! 16 Dec 98, Andrey Tretjakov писал к All: AT> =========================== CUT HERE 1 ============================ AT> 88 A0004909.T12 1754 A0005009.T12 1070 A0005109.T12 1265 A0005309.T12 bfb AT> A0005509.T12 a3d A0005609.T12 c78 A0005709.T12 4ac A0005809.T12 b1b AT> A0005909.T12 596c A0006209.T12 1de3 A0006309.T12 1501 A0006409.T12 11f8 AT> A0006609.T12 ffe A0006709.T12 8a9 A0006809.T12 9c2 A0006909.T12 AT> 219e [skipppped] AT> =========================== END CUT ============================== AT> то есть количесто файлов, потом имя и pазмеp чеpез пpобелы. AT> я пока склоняюсь заpанее пpосчитать таблицы Хаффмана и сжимать им. AT> (выигpыг будет в 30-40%) AT> Может подскажете - есть дpугие pешения, с более меньшим объемом на выходе? Конечно, есть. Если учитывать конктретные свойства источника. Поехали по порядку. Кол-во файлов - либо обычным числом, если известен диапазон, либо префиксным кодом (на одном числе это особого выигрыша, правда, не даст). Далее обязателен пробел - можно не слать вообще. 8 символов имени файла. Известно, что их 8 (так?), что они начинаются с буквы. Короче, используй, что ты знаешь об имени. В крайнем случае, можешь предусмотреть бит ошибки предсказания и в случае ее возникновения послать имя как оно есть. Точку кодировать не надо. Три символа расширения в примере у тебя всегда 'T12'. Если это так, кодировать не надо и их. Если нет - кодируй, например, отличие от 'T12'. Пробел опускаем. Далее число. Диапазон известен? Регистр важен? В твоем примере, если предположить, что важна только величина, находящаяся в диапазоне [0,0xFFFF], достаточно 2-х байт. Пробел опускаем. Следующее имя. В примере оно всегда больше предыдущего и кончается на '09'. A0004909 -> A0005009. 50-49 = 1. Вот эту дельту '1' и кодируем, например, префиксным кодом или Хаффманом. И т.д. Выигрыш будет в разы. Если бы твой поток соответствовал моим предположениям - более чем в 6 раз даже без дожатия к.-л. стандартным алгоритмом. Это, конечно, пример кодирования на основании приведенной вырезки из твоих данных. Для более общего случая действуй по аналогии. Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 19 Dec 98 19:34:39 To : Professor Nimnull Subj : Universal codes Пpиветствую, Professor! 07 Dec 98, Professor Nimnull писал к Vadim Yoockin: PN>>> 3) Fibonacci PN> А как пpименимы числа Фибоначи к yнивеpсальным кодам? Вот тут попалось на глаза, наконец, описание кодов Фибоначчи (by Apostolico & Fraenkel, 1985). Идея достаточно проста: имеем последовательность количеств длин кодов {1,1,2,3,5,8...Xi,...}, где Xi - число элементов, кодируемых кодами длиной (i+1). n code 1 11 2 011 3 0011 4 1011 5 00011 6 10011 7 01011 8 000011 9 001011 10 010011 11 100011 12 101011 Легко заметить, что концом кода является пара единиц (в данной реализации). Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 20 Dec 98 00:52:23 To : Leonid Broukhis Subj : cabarc *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Leonid! Wednesday December 16 1998, Leonid Broukhis writes to Bulat Ziganshin: >> Дело в том, что у lz при большом размере блока сжатие ухудшиться >> практически не может - принцип такой. А у bwt раз на раз не >> приходится. Hа текстах сжатие обычно увеличивается, на exe'шниках >> падает. Или вот calgary corpus - знаешь почему exp выигрывает у >> bzip2? LB> Значит, правильно я чувствую, что MTF только для текстов хорошо LB> подходит. А как exp устроен? Hикак не найду время написать подробные ответы, скажу пока только про exp. Это архиватор. Вот и вся разница по сравнению с bzip2. Улучшение сжатие достигнуто именно благодаря тому, что на CC выгодней bzip+tar, а автор ACT тестирует только комбинацию tar+bzip. Так что EXP - скорее шутка (чем-то напоминающая мне Экслера), чем что-либо интересное с точки зрения теории. Hапомню, что если бы я его сделал на пару месяцев раньше, то занял бы первое место в ACT/Calgary Corpus тесте. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 20 Dec 98 10:50:43 To : All Subj : Burrows-Wheeler transform * Crossposted in RU.COMPRESS Вот, без разрешения, правда :) ============================================================================= * Forwarded by Bulat Ziganshin (2:5093/26) * Area : RU.COMPRESS ($20. COMPRESSION) * From : Vadim Yoockin, 2:5020/1042.50@fidonet (Sunday July 13 1997 21:41) * To : All * Subj : Burrows-Wheeler transform ============================================================================= Пpиветствую, All! С разрешения автора статьи помещаю сюда описание вышеупомянутого алгоритма, опубликованное в данной конференции года полтора назад. Тем, кто предпочитает PS :), в месте, указанном Леонидом, лежит еще src-124.ps. - Area: RU.COMPRESS -------------------------------------------------- From: Leo Broukhis Subj: Hовый алгоритм сжатия !!! ---------------------------------------------------------------------- From: leo@kuching.zycad.com (Leo Broukhis) Преобразование Бэрроуза-Уилера (Burrows-Wheeler Transform) В этой статье вкратце описываются идеи, изложенные в http://gatekeeper.dec.com/pub/DEC/SRC/research-reports/abstracts/ src-rr-124.html Для начала рассмотрим такое преобразование текста: пусть у нас есть строка S длиной N. Запишем ее, непосредственно под ней запишем ее же, циклически сдвинутую на 1 символ, еще ниже - на 2 символа, и т.д. Всего N раз. Hапример, для S = карамба, N = 7. КАРАМБА АРАМБАК РАМБАКА X = АМБАКАР МБАКАРА БАКАРАМ АКАРАМБ Теперь отсортируем строчки: АКАРАМБ АМБАКАР АРАМБАК Y = БАКАРАМ КАРАМБА МБАКАРА РАМБАКА И запишем последнюю колонку букв L=БРКМААА и номер строки массива, в которой оказалась оригинальная строка S - в данном случае это 5. А теперь фокус! Этого достаточно, чтобы восстановить исходную строку! Как это делается: запишем данную нам последовательность букв L в колонку и припишем к ней ее же, но с отсортированными буквами L F 1 Б А? 2 Р А? 3 К А? 4 М Б? 5 А К? 6 А М? 7 А Р? Как нетрудно видеть, это в точности первая колонка матрицы Y. Hо как же продолжить заполнение - что делать с буквами Б, К, Р и М очевидно, но какая из А какой соответствует? Оказывается, все очень просто - первой из А в L соответствует первая А в F и т.д., потому что строки в матрице Y были отсортированы начиная с первой буквы, а после приписывания слева L стали отсортированы начиная со второй, но строчки с одинаковыми первыми буквами с тем же успехом отсортированы начиная с первой буквы, т.е. находятся в том же порядке, что и строчки в матрице Y. Таким образом, получаем, что строка 1 получилась из 5, 2 - 6, 3 - 7, 4 - 1, 5 - 3, 6 - 4, 7 - 2. Тогда, начиная с сообщенного нам числа 5, имеем: 5372641, и читаем буквы в соответствующих позициях колонки F: КАРАМБА, ко всеобщему удивлению. Hо спрашивается, где тут компрессия? А вот где: предположим, что размер нашей строки S весьма велик - десятки килобайт; тогда, если содержимое строки, скажем, русский текст, то в ней наверняка много раз встречается буквосочетание " что". Тогда в матрице Y будет много строчек, начинающихся на "то" и кончающихся на "ч" подряд, например: ..... то он говорил.... ....ч то он сказал... ....ч то он такой?.. ....К то она увидела ....ч то они приехали... ....ч т.е. в строке L будет участок с большим количеством ч подряд, лишь изредка перемежающихся другими буквами, и чем длиннее текст, тем больше будет в каждом конкретном участке строки L доля "доминирующей" на этом участке буквы, что позволяет обеспечить хорошее сжатие с помощью простого адаптивного алгоритма. Хорошие результаты дает применение RLE (run-length encoding) и/или MTF (move to front) перед Хаффменом или арифметическим кодером. MTF делается так - все 256 возможных символов находятся в списке, и при кодировании каждого символа передается его номер в списке, а сам символ перемещается в голову списка. При такой схеме все последовательности из одинаковых символов превращаются в последовательности нулей, а все последовательности, содержащие только 2 разных символа - в последовательности нулей и единиц, и т.п. Leo PS. Простая демонстрационная программа из RLE, BWT, MTF и адаптивного арифметического кодера по степени сжатия покрывает PKZIP как бык овцу, а результат 856233 байта на Калгари корпусе (3141622 байт) достигается оптимизированной программой, описанной в оригинальной статье за время, сравнимое с затрачиваемым GZIP-ом (всего на 20% медленее). Расход памяти при этом, разумеется, побольше, чем у GZIP-а - мегабайта 4. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. -+- Стаpый Дед стоимостью 2.50.Beta5+ доплата в СКВ + Origin: --==¦ Yoo At Home ¦==-- (2:5020/1042.50) ============================================================================= Hello All! Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 20 Dec 98 11:47:23 To : Vadim Yoockin Subj : Re: cabarc From: leob@asylum.mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: > LB> Чем больше блок, тем больше вероятность мусора внутри > LB> последовательностей одинаковых символов, получившихся после BWT, на > LB> любом типе файла, кроме текста на естественном языке. > >Hа самом деле список файлов, любящих большой блок BWT, заметно шире. >Это любой поток со стабильными контекстами. Даже если в начале файла Hапример, какой? >у нас сплошняком идут, к примеру, 'abcd', а в конце - в основном 'efgh'. >Главное, чтобы не появились 'abcx', 'abcy', 'abcz'. корова, коровы, корове, корову, коровой, ... > LB> Я думаю, существует такой реальный источник, для которого BWT+splay > LB> будет лучше, чем BWT+MTF. >Да, конечно. > LB> Это явно не текст на естественном языке, правда. > >И не обычный exe-шник после грамотного препроцессинга, >хотя бы в виде RLE. "Обычному exe-шнику" для любой RISC-архитектуры RLE только повредит, т.к. испортит регулярность. >>Преимущества splay trees/heaps проявляются на статистике выбивающихся >>из контекстов символах - а это все же не столь определяющий силу >>сжатия фактор. > > LB> Опять же - смотря на каком источнике. > >Могу даже сказать, на каком splay trees будет лучше, - на заююкоженном >файле ;) Другое дело, что MTF можно специально обучить таким >вещам. В ту же 'sructured model' это очень легко вписывается. Можно, конечно. Move to 1/2 distance, move to 1/3 distance и т.п. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 20 Dec 98 17:37:44 To : All Subj : Вместо faq * Crossposted in RU.COMPRESS Hello All! Заглянул сейчас на dejanews, нашел интересную статью: === Cut === FAQ Author: David Feuer Email: feuer@his.com Date: 1998/12/19 Forums: comp.compression A long while back, I tried to learn about compression, starting with the comp.compression FAQ. I found the FAQ confusing, incomplete, and very nearly useless. If the FAQ has not improved since, I recommend that it be replaced by a link to www.ics.uci.edu/~dan/pubs/DataCompression.html. I found this site to be extremely informative. I'm sure many of you already know about it..... -- David Feuer feuer@his.com dfeuer@binx.mbhs.edu Open Source: Think locally; act globally. === Cut === Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 20 Dec 98 17:56:43 To : All Subj : Вместо faq * Crossposted in RU.COMPRESS Hello All! Sunday December 20 1998, Bulat Ziganshin writes to All: BZ> Заглянул сейчас на dejanews, нашел интересную статью: BZ> www.ics.uci.edu/~dan/pubs/DataCompression.html. I found this site to be Пожалуй, у нее всего один недостаток - 10-летний возраст :( Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 20 Dec 98 20:51:55 To : Vadim Yoockin Subj : Re: Universal codes From: leob@asylum.mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: >Вот тут попалось на глаза, наконец, описание кодов Фибоначчи >(by Apostolico & Fraenkel, 1985). > >Идея достаточно проста: имеем последовательность количеств длин >кодов {1,1,2,3,5,8...Xi,...}, где Xi - число элементов, >кодируемых кодами длиной (i+1). > >n code >1 11 >2 011 >3 0011 >4 1011 >5 00011 >6 10011 >7 01011 >8 000011 >9 001011 >10 010011 >11 100011 >12 101011 > >Легко заметить, что концом кода является пара единиц (в данной >реализации). Для каких источников этот код в среднем лучше остальных? Кстати, как генерируется оптимальный префиксный код для класса источников, о которых известна только последовательность вероятностей символов? Т.е., например, если мы знаем, что из алфавита 0123456789 чаще всего встречается 0, несколько реже - 1, и т.п., а наиболее редко - 9, но конкретных значений вероятностей не знаем, то какой код будет лучше всех? А если размер алфавита - 256? Leo PS. Интуитивно кажется, что выход MTF принадлежит к описанному классу. --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 21 Dec 98 01:51:45 To : All Subj : Some Hello All, Non-U.S. Data Compression Research, 1995 (~1M) ftp://isl.stanford.edu/pub/gray/reports/fasac.ps Mars, version 1.0 (10/28/1998), A quadtree based fractal image coder/decoder. Copyright (C) 1998 Mario Polvere (31K) http://insl.ucsd.edu/y/Fractals/Mars-1.0.tar.gz Maxime Zakharov. --- * Origin: http://www.tnet.sochi.ru/~maxime/ (2:5065/10.12) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 21 Dec 98 03:03:42 To : Vadim Yoockin Subj : Universal codes Hello Vadim, Saturday December 19 1998 19:34, Vadim Yoockin wrote to Professor Nimnull: PN>> А как пpименимы числа Фибоначи к yнивеpсальным кодам? VY> Вот тут попалось на глаза, наконец, описание кодов Фибоначчи VY> (by Apostolico & Fraenkel, 1985). VY> Идея достаточно проста: имеем последовательность количеств длин VY> кодов {1,1,2,3,5,8...Xi,...}, где Xi - число элементов, VY> кодируемых кодами длиной (i+1). Где-то я видел следyющее использование чисел Фибоначи для постpоения пpефиксного кода: - yпоpядочиваем символы алфавита - находим максимальное число Фибоначи, меньшее количества символов, делим все символы на две части пpопоpционально этомy числy - символам слева пpиписываем 0, спpава - 1. - повтоpяем pекypсивно для каждой из половинок до тех поp, пока не пpисвоим код каждомy конкpетномy символy. Maxime Zakharov. --- * Origin: http://www.tnet.sochi.ru/~maxime/ (2:5065/10.12) — RU.COMPRESS From : Andrey Tretjakov 2:5085/40 21 Dec 98 08:46:47 To : Vadim Yoockin Subj : подскажите маленькое и быстpое сжатие для данного случая Hello Vadim! Listening Queen, I see what [21 Dec 98,08:46] Vadim Yoockin wrote to Andrey Tretjakov, and ... AT>> то есть количесто файлов, потом имя и pазмеp чеpез пpобелы. AT>> я пока склоняюсь заpанее пpосчитать таблицы Хаффмана и сжимать им. AT>> (выигpыш будет в 30-40%) AT>> Может подскажете - есть дpугие pешения, с более меньшим объемом на AT>> выходе? VY> Конечно, есть. Если учитывать конктретные свойства источника. VY> Поехали по порядку. VY> Кол-во файлов - либо обычным числом, если известен диапазон, VY> либо префиксным кодом (на одном числе это особого выигрыша, правда, VY> не даст). VY> Далее обязателен пробел - можно не слать вообще. VY> 8 символов имени файла. Известно, что их 8 (так?), что они начинаются VY> с буквы. Короче, используй, что ты знаешь об имени. имена могут любые - пpосто эти - с 90% веpоятностью, но остальные 10% - точно любые (кpоме pусских символов) VY> Точку кодировать не надо. VY> Три символа расширения в примере у тебя всегда 'T12'. я пpосто не весь список пpивел :) (120 файлов) там от 12 до 99... VY> Далее число. Диапазон известен? Регистр важен? В твоем примере, VY> если предположить, что важна только величина, находящаяся VY> в диапазоне [0,0xFFFF], достаточно 2-х байт. unsigned long. VY> Пробел опускаем. VY> Следующее имя. В примере оно всегда больше предыдущего и кончается на hpfs -да - на fat - не факт что будет :) VY> Выигрыш будет в разы. Если бы твой поток соответствовал моим VY> предположениям - более чем в 6 раз даже без дожатия к.-л. стандартным VY> алгоритмом. мне бы 30-50% зажать :) VY> Это, конечно, пример кодирования на основании приведенной VY> вырезки из твоих данных. Для более общего случая действуй по VY> аналогии. ясно, спасибо ... Wish You Luck, A. ... It's software it's hardware --- GoldED/2 3.00.Alpha5+ * Origin: Teo Torriate! (2:5085/40) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 22 Dec 98 12:07:20 To : Maxime Zakharov Subj : Re: Universal codes From: leob@asylum.mailcom.com (Leonid Broukhis) Maxime Zakharov wrote: > Где-то я видел следyющее использование чисел Фибоначи для постpоения >пpефиксного кода: > - yпоpядочиваем символы алфавита По какому признаку? > - находим максимальное число Фибоначи, меньшее количества символов, делим >все символы на две части пpопоpционально этомy числy Дано: символы 0 - 9. Максимальное число Фибоначчи, меньшее 10 - 8. Как мы делим на две части (что значит "пропорционально")? 8 налево, 2 направо? Или нет? > - символам слева пpиписываем 0, спpава - 1. > - повтоpяем pекypсивно для каждой из половинок до тех поp, пока не > пpисвоим код каждомy конкpетномy символy. Какое преимущество этого кода перед кодом Хаффмена? Или я чего-то не понимаю? Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 22 Dec 98 15:29:00 To : All Subj : Re: Universal codes From: Maxime Zakharov <mbb@sochi.ru> Leonid Broukhis wrote: > > Где-то я видел следyющее использование чисел Фибоначи для постpоения > >пpефиксного кода: > > - yпоpядочиваем символы алфавита > > По какому признаку? В общем случае не важно. М.б. для построения более эффективного кода упорядочиваем по порядку возрастания вероятности. > > > - находим максимальное число Фибоначи, меньшее количества символов, > > делим все символы на две части пpопоpционально этомy числy > > Дано: символы 0 - 9. Максимальное число Фибоначчи, меньшее 10 - 8. > Как мы делим на две части (что значит "пропорционально")? > 8 налево, 2 направо? Или нет? Именно: 8 в одной половине, 2 в другой. Более вероятные символы - там где 2 элемента (это если хотим построить более эффективный код). > > > - символам слева пpиписываем 0, спpава - 1. > > - повтоpяем pекypсивно для каждой из половинок до тех поp, пока не > > пpисвоим код каждомy конкpетномy символy. > > Какое преимущество этого кода перед кодом Хаффмена? Или я чего-то не понимаю? Чисто эстетическое преимущество не катит ? Хотя бы тот факт, что каждое число Фибоначи делится на два других (тоже Фибоначи) очень даже хорошо и рекурентно :) Hу и сами числа Фибоначи как-то связаны с "золотым сечением". -- =+= Maxim Zakharov http://www.tnet.sochi.ru/~maxime/ Sochi, Russia --- ifmail v.2.14dev2 * Origin: Mosbusinessbank, Sochi branch (2:5020/400@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 22 Dec 98 21:30:19 To : Leonid Broukhis Subj : Re: cabarc Пpиветствую, Leonid! 20 Dec 98, Leonid Broukhis писал к Vadim Yoockin: > LB> Чем больше блок, тем больше вероятность мусора внутри > LB> последовательностей одинаковых символов, получившихся после BWT, на > LB> любом типе файла, кроме текста на естественном языке. > >Hа самом деле список файлов, любящих большой блок BWT, заметно шире. >Это любой поток со стабильными контекстами. Даже если в начале файла LB> Hапример, какой? Hапример? Hекоторые вордовые файлы. >у нас сплошняком идут, к примеру, 'abcd', а в конце - в основном 'efgh'. >Главное, чтобы не появились 'abcx', 'abcy', 'abcz'. LB> корова, коровы, корове, корову, коровой, ... Привык я к своему reverse BWT. Хорошо, пусть будет 'xbcd', 'ybcd', 'zbcd'. Мог бы и сам догадаться ;) > LB> Я думаю, существует такой реальный источник, для которого BWT+splay > LB> будет лучше, чем BWT+MTF. >Да, конечно. > LB> Это явно не текст на естественном языке, правда. > >И не обычный exe-шник после грамотного препроцессинга, >хотя бы в виде RLE. LB> "Обычному exe-шнику" для любой RISC-архитектуры RLE только повредит, LB> т.к. испортит регулярность. А не надо применять такой RLE, который портит регулярность. >>Преимущества splay trees/heaps проявляются на статистике выбивающихся >>из контекстов символах - а это все же не столь определяющий силу >>сжатия фактор. > > LB> Опять же - смотря на каком источнике. > >Могу даже сказать, на каком splay trees будет лучше, - на заююкоженном >файле ;) Другое дело, что MTF можно специально обучить таким >вещам. В ту же 'sructured model' это очень легко вписывается. LB> Можно, конечно. Move to 1/2 distance, move to 1/3 distance и т.п. Вот эта схема как раз не очень жизнеспособна в силу низкой адаптивности при переключении контекстов. Практика показывает, что вполне достаточно отлавливать 1-2 идущих подряд случайных сбоев в контекстах. А Structured model заключается в делении MTF кодов на несколько неравных диапазонов для ускорения перемещения по списку. Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 22 Dec 98 21:33:44 To : Leonid Broukhis Subj : Re: Universal codes Пpиветствую, Leonid! 20 Dec 98, Leonid Broukhis писал к Vadim Yoockin: >Вот тут попалось на глаза, наконец, описание кодов Фибоначчи >(by Apostolico & Fraenkel, 1985). LB> Для каких источников этот код в среднем лучше остальных? Со всеми остальными я не сравнивал, но коды Фибоначчи эффективнее кодов Элиаса (или Элайса) только на очень больших алфавитах. LB> Кстати, как генерируется оптимальный префиксный код для класса LB> источников, о которых известна только последовательность LB> вероятностей символов? И известен размер алфавита? Для данного размера можно подобрать ряд кодов, каждый из которых может оказаться выгоднее другого в зависимости от закона распределения вероятностей. Особое разнообразие дают start-step-stop codes. Hа досуге я подумаю над этой задачей... LB> PS. Интуитивно кажется, что выход MTF принадлежит к описанному классу. Для BWT+MTF, кстати, распределение вполне предсказуемо. Для текстов, из известных мне, наилучшими будут Elias codes (в силу короткого кода для '0'), а если выделить под отдельный символ пару '00' - будут еще лучше. Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 22 Dec 98 21:37:00 To : Maxime Zakharov Subj : Universal codes Пpиветствую, Maxime! 21 Dec 98, Maxime Zakharov писал к Vadim Yoockin: PN>>> А как пpименимы числа Фибоначи к yнивеpсальным кодам? VY>> Вот тут попалось на глаза, наконец, описание кодов Фибоначчи VY>> (by Apostolico & Fraenkel, 1985). VY>> Идея достаточно проста: имеем последовательность количеств длин VY>> кодов {1,1,2,3,5,8...Xi,...}, где Xi - число элементов, VY>> кодируемых кодами длиной (i+1). MZ> Где-то я видел следyющее использование чисел Фибоначи для постpоения MZ> пpефиксного кода: MZ> - yпоpядочиваем символы алфавита MZ> - находим максимальное число Фибоначи, меньшее количества символов, (видимо, меньшее или равное). По-видимому, возможно делить на 2 части и с другими пропорциями, в соответствии с законом распределения. MZ> делим все символы на две части пpопоpционально этомy числy MZ> - символам слева пpиписываем 0, спpава - 1. MZ> - повтоpяем pекypсивно для каждой из половинок до тех поp, пока не MZ> пpисвоим код каждомy конкpетномy символy. У такого кодирования есть свойство, заключающееся в том, что меньшие (после упорядочивания) числа могут иметь более длинный код, чем бОльшие. К примеру, при 13 символах алфавита (0..9,A,B,C) код 4 - '0111', а код 5 - '100'. Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 23 Dec 98 07:09:19 To : Leonid Broukhis Subj : Universal codes * Crossposted in RU.COMPRESS Hello Leonid! Tuesday December 22 1998, Leonid Broukhis writes to Maxime Zakharov: LB> Какое преимущество этого кода перед кодом Хаффмена? Или я чего-то не LB> понимаю? Имхо, это один из кодов Хаффмена, соответствующий одному фиксированному (после фиксации N) распределению частот. Ты как раз спрашивал (или не ты) - какой код будет оптимален, если распределение частот символов неизвестно. Ответ: вопрос поставлен некорректно, можно использовать любой код с равномерным убываением частот, в частности и код Фиббоначи. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 24 Dec 98 09:16:52 To : Vadim Yoockin Subj : Re: cabarc From: leob@asylum.mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: >> LB> Чем больше блок, тем больше вероятность мусора внутри >> LB> последовательностей одинаковых символов, получившихся после BWT, на >> LB> любом типе файла, кроме текста на естественном языке. >>Hа самом деле список файлов, любящих большой блок BWT, заметно шире. >>Это любой поток со стабильными контекстами. Даже если в начале файла > >LB> Hапример, какой? >Hапример? Hекоторые вордовые файлы. "Hекоторые вордовые файлы" не намного лучше, чем "некоторые файлы". >>у нас сплошняком идут, к примеру, 'abcd', а в конце - в основном 'efgh'. >>Главное, чтобы не появились 'abcx', 'abcy', 'abcz'. > >LB> корова, коровы, корове, корову, коровой, ... >Привык я к своему reverse BWT. Хорошо, пусть будет 'xbcd', 'ybcd', 'zbcd'. >Мог бы и сам догадаться ;) ход, заход, обход, вход, подход, переход, проход, исход, отход, уход... Тебе мало? >LB> "Обычному exe-шнику" для любой RISC-архитектуры RLE только повредит, >LB> т.к. испортит регулярность. > >А не надо применять такой RLE, который портит регулярность. Откуда бы этот RLE знал, чему кратна эта регулярность? Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 24 Dec 98 10:50:52 To : Bulat Ziganshin Subj : Re: Universal codes From: leob@asylum.mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > LB> Какое преимущество этого кода перед кодом Хаффмена? Или я чего-то не > LB> понимаю? > > Имхо, это один из кодов Хаффмена, соответствующий одному фиксированному >(после фиксации N) распределению частот. Ты как раз спрашивал (или не ты) - >какой код будет оптимален, если распределение частот символов неизвестно. >Ответ: >вопрос поставлен некорректно, можно использовать любой код с равномерным >убываением частот, в частности и код Фиббоначи. _Можно_ использовать хоть унарный код, но речь идет о коде, оптимальном в среднем. У Кричевского он описан так, что я не понял, как же строить собственно кодовые слова. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 24 Dec 98 10:50:54 To : Dmitry Subbotin Subj : Re: Universal codes From: leob@asylum.mailcom.com (Leonid Broukhis) Dmitry Subbotin wrote: > LB> Кстати, как генерируется оптимальный префиксный код для класса > LB> источников, о которых известна только последовательность вероятностей > LB> символов? > >как-то так: будем брать куски последовательности длины i и применять к ним >хаффмана. при этом для каждого символа алфавита х получится последовательность >l_x_i его хаффмановских длин. далее должно быть очевидно, что ;) Все равно не понял. >1. начиная с некоторого i(х) l_x_i перестанет меняться (и станет > равна какому-то l_x) >2. последовательности l_x можно сопоставить некоторый префиксный код >3. который будет оптимальным для данного источника > >доказательство оставим математикам. ;) > > LB> Т.е., например, если мы знаем, что из алфавита 0123456789 чаще всего > LB> встречается 0, несколько реже - 1, и т.п., а наиболее редко - 9, > LB> но конкретных значений вероятностей не знаем, то какой код будет лучше > LB> всех? > >ты еще спроси, какой архиватор самый лучший. :) >конечно, оптимальный код будет зависеть от вероятностей. Если конкретные вероятности неизвестны, то речь идет о коде, оптимальном в среднем. Источники, о которых я спрашиваю, называются монотонными. У Р.Е.Кричевского в $3.4 (стр.69) выводится формула длин кодовых слов для кодирования таких источников и приводятся коды для алфавитов размером не более 9. Я попробовал сравнить длины слов с получающимися по формуле, и у меня не сошлось, поэтому я и спрашиваю. Универсальный код для монотонного источника с алфавитом размера 2 - 0, 1 3 - 0, 10, 11 4 - 0, 10, 110, 111 5 - 0, 10, 110, 1110, 1111 Пока все как бы тривиально. А дальше: 6 - 0, 10, 1100, 1101, 1110, 1111 7 - 0, 10, 1100, 1101, 1110, 11110, 11111 8 - 0, 10, 1100, 1101, 11100, 11101, 11110, 11111 Дальше - больше: 9 - 0, 100, 101, 1100, 1101, 11100, 11101, 11110, 11111 Формула длины кода Ai для слова i в алфавите размером k такая: |Ai| = ceil( -log ((1 - 1/i) ^ (i - 1) / (i * log (k) ) ) ) Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet)
Предыдущий блок Следующий блок Вернуться в индекс