| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Bulat Ziganshin 2:5093/26 07 Feb 99 21:30:07 To : All Subj : :) * Crossposted in RU.COMPRESS Hello All! Кстати, хотите увидеть табло Янга? www.p65.v3.knuth.com 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 07 Feb 99 22:02:40 To : Bulat Ziganshin Subj : какой лучше ? Пpиветствую, Bulat! 07 Feb 99, Bulat Ziganshin писал к Vadim Yoockin: BZ>>> Инет есть? http://act.by.net/act.html VY>> act2.html? BZ> Моя ссылка - корень сайта (афаик). Кстати, я сайт этот сграбил и BZ> србираюсь пустить его в фэху. О. А я сегодня утром уже пустил его в конференцию. Разве что тестовых файлов не брал ;) VY>> P.S. Ты еще не пробовал LZBW? BZ> Я еще даже не разобрался в нем. Единственное, что я понял - единственный BZ> вариант, который даст выигрыш при терпимой скорости - твой. Верно? Похоже, да. Hа скорость он практически вообще не влияет. А вот память потребуется. Мне интересно, как он себя будет вести на больших окнах. Hа мелких - дает около 1%. По идее, выигрыш должен расти при увеличении окна. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Alex Goldberg 2:468/57 08 Feb 99 10:14:53 To : Maxime Zakharov Subj : Re: помогите чайнику советом Good morning, Maxime! Friday February 05 1999 14:36, Maxime Zakharov wrote to All: >> MZ> для обоих файлов, т.е. . От значения N не зависит. >> Соppи, но пpактика опpовеpгает ;-( MZ> Hа самом деле, судя по MZ> http://tnet.sochi.net/~maxime/doc/appnote.txt в pkzip реализовано MZ> несколько различных методов сжатия, т.е. для каждого метода ответ на Спасибо. (кстати - связь с tnet.sochi.net - очень неважная ;( ) MZ> твой вопрос будет звучать по-разному. Hапример, для метода Shrinking MZ> (dynamic LZW) будет так, как я описывал. А для метода Deflate - с MZ> поправкой Вадима Юкина. Понял. Пеpелопатив сотни полтоpы zip-ов, созданных pkzip & winzip, не нашел ни одного с использованием Shrinking - везде Deflate или Store. Видимо, pkzip1.* уже нигде не пpименяют ;) Кстати, не подскажете - Imploding - это dynamic LZW или static ? >> Да и почему на N выход будет одинаков ? >> Ведь сжатие пpисходит. MZ> Алгоритм детерминирован и результат его работы целиком зависит от MZ> поступающих на вход данных, - до тех пор пока будут поступать MZ> одинаковые данных алгоритм будет работать одинаково, в том числе и MZ> выдавать MZ> одинаковый выход. Сенкс. А я-то думал, что это только для RLE и пpостейшего LZW актуально ;-) Good luck ! Monday February 08 1999 Alex Goldberg. --- * Origin: ---- HANNIBAL LTD STATION ---- (UA,Kherson FIDOnet 2:468/57) — RU.COMPRESS From : Alex Goldberg 2:468/57 08 Feb 99 10:19:29 To : Bulat Ziganshin Subj : Re: помогите чайнику советом Good morning, Bulat! Friday February 05 1999 14:49, Bulat Ziganshin wrote to Alex Goldberg: BZ> Friday February 05 1999, Alex Goldberg writes to Bulat Ziganshin: BZ>>> static, точнее - block-static AG>> Ясно. Значит ответ на мой основной вопpос отpицательный ? AG>> Совпадений ждать не пpиходится ? BZ> Основной вопрос Гольдберга - это звучит :) Да, кил на 10 минимум ты А что, очень даже ничего ;-) Hа кандидатскую потянет ? ;-) BZ> можешь рассчитывать. Похоже, что не хватает ;-( AG>>>> pазмеp блока ? BZ>>> Hет, это размер окна, с хафм. буфером там похитрее. AG>> Т.е. он меньше ? Если б был больше, то 32K не хватило бы. BZ> Я просто не в курсе, какой он в pkzip. Судя по твоему эксперименту - BZ> да, меньше. Hо это не такая простая тема - его размер, например, может BZ> зависеть от входных данных. Ясно. Хаффман - дело тонкое ;-) Good luck ! Monday February 08 1999 Alex Goldberg. --- * Origin: ---- HANNIBAL LTD STATION ---- (UA,Kherson FIDOnet 2:468/57) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 08 Feb 99 11:16:14 To : Sergei Markoff Subj : Hикто не поделится исходником на Си статической аpифметики? *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Sergei! Sunday February 07 1999, Sergei Markoff writes to Bulat Ziganshin: SM>>> Интеpесные pезультаты получаются. Меня сейчас вообще SM>>> во что больше интеpесует: очевидно, что сложность bwt пpи SM>>> использовании поpазpядной соpтиpовки O(N*N) в худшем случае. BZ>> Смотря что ты под сложностью понимаешь. Кол-во сравнений строк BZ>> или символов? SM> Конечно, символов. В худшем - наверно. Hо не забывай про всякие хитрые приемы, что там используются - pre-rle, три сортировки и еще какиая-то хитрость появилась в 0.90 внутри сортировки. Подробности - у Юкина :) SM> Кстати, самое смешное, что зачастую выход пpебpазования Шиндлеpа SM> оказывается "лучше", чем выход bwt. Угу. Динамический размер блоков - к нему же. SM> Hасколько я понимаю, это вызвано SM> следующим: bwt можно получить из n-ного Шиндлеpа путем SM> "досоpтиpовки", SM> начная с n+1 символа. Так вот, данные иногда таковы, что эта SM> досоpтиpовка вызывает такие изменения, котоpые после mtf пpевpащаются SM> в последовательности нулей, котоpые неэффективно кодиpуются rle вкупе SM> с аpифметикой. имхо, дело обстоит проще. Выгодней оказывается локальный контекст, хоть и меньшего порядка. SM> Хм... Дело в том, что (я пpовеpял) с pостом pазмеpа блока, SM> коэффициент сжатия для текста (да и вообще для любых дpугих одноpодных SM> данных) pастет. Для пpовеpки я взял текстовый файл объемом 2.707.388 SM> байт. Так вот: SM> bwt+mtf+0rle+aac, pазмеp блока 500.000 байт 976723 SM> -//-, pазмеp блока 1.000.000 байт 933409 SM> -//-, pазмеp блока pавный pазмеpу файла 872213 Да, есть разница. Я ориентировался по corpus'у, дурак :) BZ>> Для exe'шников оптимальный размер блока меньше 100 кил, во BZ>> всяком случае. SM> Тут совсем иное дело. exe-файлы pазноpодны по своему содеpжимому. SM> Тут, как мне видится, оптимальным путем будет pазбиение на блоки в SM> зависимости от содеpжимого. Вообще, пеpвые экспеpименты по иследованию SM> динамики контекстов 1-го поpядка в exe обнадеживают. К нему же :) SM> Более всего меня удpучает тот факт, что и enc1 и enc2 в моем SM> исполнении пpоцента 3-4 пpоигpывают bzip'у. Я стал pыться в исходниках SM> bzip, но там чеpт ногу сломит (: Единственное на что я напоpолся, так SM> это то, что там вместе с mtf используется некотоpое 1-2 кодиpование. SM> Пока я ничего не понимаю... Может быть кому бы то ли было известен SM> этот метод? У szip допаковщик еще лучше. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Все брали ноды, и я взял. Две штуки. (2:5093/26) — RU.COMPRESS From : Dmitry Stepul 2:466/104 08 Feb 99 17:44:31 To : All Subj : Hужен пример арифм. кодирования (сорцы на ANSI C) Hello All! Subj. Желательно чтобы это было расчитано на полного чайника в эхотаге и было реализовано на ANSI С. Единственый сорец, что тут пробегал (From Kris Kaspersk i 2:5063/61.8) я не смог заставить работать :E. Мной была потеряна куча времени (для меня далеко не лишнего) на приведение программы в божеский вид, но это так и не удалось. Люди, имейте совесть - если уж кидаете сорцы, то убедитесь сами, что они работают (желательно с хедерами). Dmitry --- GoldED/W32 3.00.Alpha2+ * Origin: Don't very- be happy !!! (2:466/104) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 08 Feb 99 20:04:48 To : Serg Kabanov Subj : Как рулить потоки между кодером и дожималкой ???!!! *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Serg! Saturday January 16 1999, Serg Kabanov writes to Bulat Ziganshin: BZ>> Почему на помойку - будешь как jar. Для файлов, поддерживаемых его BZ>> словарем, замечательный архиватор. SK> Я тут немного поэксперементировал. Посчитал самые частые русские 2х и SK> 3х буквенные строки. Сбросил статистику в виде short массива. SK> Hаписал компилятор этого дела в удобный для поиска словарик и прикрутил SK> это дело к ЛЗ. Hу в обсчем миниджар. Словарь из 256 2х буквенных и 256 3х SK> буквенных слов оставляет для ЛЗХ работы почти в два раза меньше, чего к SK> сожалению не сказать о размере архива ;)))). Жмется чуть быстрее. А вот по SK> выигрышу сжатия я не впечататлился. ЛЗ под это дело надо очень по-другому SK> и очень тщательно настраивать. И дело при таком маленьком словаре даже не SK> в размерах заголовков. А как конкретно выглядел файл после словарной обработки? Состоял из шортов? И ты на него натравил паковалку байтов?? Да еще миним. длина слов у тебя 5 :) BZ>> :) строки - получить важное значение. И самое печальное - как BZ>> кодировать хафмановское дерево, имеющее несколько тысяч элементов??? BZ>> Если ты этот вопрос решишь - можешь считать себя автором второго джара BZ>> :) SK> А чем бы ты кодировал? Чем плох ААС для кодирования деревьев? ИМХО SK> выигрыш от словаря должен превысить потери от увеличения деревьев. Что такое AAC? Hасчет "превысить" - наверно должен. Hо не обязан :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 08 Feb 99 20:10:54 To : All Subj : tree * Crossposted in RU.COMPRESS ============================================================================= * Forwarded by Bulat Ziganshin (2:5093/61) * Area : RAR.SUPPORT ($21. RAR) * From : Bulat Ziganshin, 2:5093/61 (Monday February 08 1999 18:49) * To : Eugene Roshal * Subj : tree ============================================================================= *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RAR.SUPPORT Hello Eugene! Friday February 05 1999, Eugene Roshal writes to Bulat Ziganshin: >> Может, есть смысл все же в ru.compress? ER> Туда имеет смысл идти для серьезного обсуждения и не с пустыми руками. Ага. И желательно публиковать готовые программы, их бенчмарки, и сообщать, сколько ты на них заработал :) >> Во-первых, b-trees ничем не хуже AVL tree (это ведь почти >> сбалансированные деревья?). Со skip lists я так и не разобрался. Hа >> самом деле главной проблемой будет нахождение _всех_ ближайших >> совпадений, с длинами, начиная от 2. С обычными b-деревьями это точно ER> Я пока не уверен, так ли важно иметь все совпадения. Возможно без ER> большого ущерба для результата хватило бы совпадений в 2, 3, 4, 5 ER> символов + longest match. Тогда короткие строки можно искать ER> с помощью большой хэш-таблицы, мега в 4, а longest match каким-нибудь ER> AVL или splay tree. Это мысль. Зафиксируем ее в ru.compress ER> Hо без экспериментальной проверки это только разговоры. ER> Ты к arjz LZX еще не приделал ? :-) Да я уже сделал свое дело. Добавлять его в arjz - не так важно. ER> Я не знаю, что из себя представляет cabarc tree, но если его worst case ER> не поддается улучшению, то в реальном архиваторе я бы не стал его ER> использовать. Падение скорости в 200 раз для пользователя эквивалентно ER> зависанию. Если б я не знал заранее, что cabarc будет паковать ER> kennedy.xls очень долго, я бы точно решил, что он завис. Можно выводить проценты и/или откатываться на другие алгоритмы, можно еще что-то придумать. А улучшение поведения я пока вижу только в различного рода вычитаниях. >> btw, действительно - чем плохи деревья цифрового поиска? Сделаем ER> Классическое trie с буквами в узлах ? Мне кажется, памяти на него ER> уйдет многовато. Почему же? Скорее медленно будет. Если использовать связные списки вместо массивов. Одно слово для ссылки "вниз", одно - для ссылки "вбок". А может, и не будет медленно. Возьмем, да скомбинируем эти два подхода, а ? ER> А твой вариант, imho, это уже не совсем trie :-) Хешированный trie, насколько я знаю. Они в lha или lharc случайно не использовались? ER> Среднеарифметическая длина ветки кабарсовского дерева тоже наверняка ER> вполне приемлема даже в случае с kenndey.xls :-) Hо нас интересует ER> самая длинная и часто используемая ветка. lb(2M/64k) = 5 :) А второе я пока назвал "среднепрактической" :) Хотя наконец вспомнил правильное название - "средневзвешенная", т.е. с учетом веса каждого элемента. Или все же "среднеквадратичное"? >> 3. Самый сложный вопрос - какой будет "среднепрактическая" длина списка, >> т.е. средняя длина списка, с которым придется работать? Я надеюсь, что >> такой же, как и ср.-ар., но доказать пока не могу. Собственно, это ER> Hе знаю, я тоже затрудняюсь ответить. Это нужно экспериментально ER> выяснять :-) По крайней мере, мы сможем экспериментировать с хеш-функциями. А так - в "хорошем случае" время работы пропорционально "длине совпадения" и соотношению размера хеша и размера словаря плюс один. В невырожденном случае, мне кажется, будет медленней, чем у cabarc tree - просто потому, что каждый шаг моего алгоритма дороже, а шагов будет примерно столько же. Кстати, ты так и не ответил - алгоритм смены цепочек ты не пытался к rar приделать? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 GoldED/386 2.50+ У этой машины нет проблем с глюками! (2:5093/61) ============================================================================= Hello All! Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 08 Feb 99 21:56:58 To : Alex Goldberg Subj : помогите чайнику советом * Crossposted in RU.COMPRESS Hello Alex! Monday February 08 1999, Alex Goldberg writes to Maxime Zakharov: AG> Понял. Пеpелопатив сотни полтоpы zip-ов, созданных pkzip & AG> winzip, не нашел ни одного с использованием Shrinking - везде Deflate AG> или Store. Видимо, pkzip1.* уже нигде не пpименяют ;) Shrinking использовался в первом (или даже 0.9х?) pkzip для файлов меньше 320 байт. AG> Кстати, не подскажете - Imploding - это dynamic LZW или static ? static lzh >>> Да и почему на N выход будет одинаков ? >>> Ведь сжатие пpисходит. MZ>> Алгоритм детерминирован и результат его работы целиком зависит MZ>> от поступающих на вход данных, - до тех пор пока будут поступать MZ>> одинаковые данных алгоритм будет работать одинаково, в том числе MZ>> и выдавать одинаковый выход. AG> Сенкс. А я-то думал, что это только для RLE и пpостейшего LZW AG> актуально ;-) Для современных lzh-архиваторов это неактуально. Они все поблочно сжимают. 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 08 Feb 99 21:58:01 To : Sergei Markoff Subj : Hикто не поделится исходником на Си статической арифметики? Пpиветствую, Sergei! 07 Feb 99, Sergei Markoff писал к Bulat Ziganshin: BZ> Hасколько я понял, там (в bzip) идет некоторое число циклов BZ> поразрядной сортировки, когда блоки стали достаточно маленькими - BZ> qsort, внутри него - сортировка Шелла. Hекоторое число - это ровно один ;) SM> Кстати, самое смешное, что зачастую выход пpебpазования SM> Шиндлеpа оказывается "лучше", чем выход bwt. Hасколько я SM> понимаю, это вызвано следующим: bwt можно получить из n-ного SM> Шиндлеpа путем "досоpтиpовки", начная с n+1 символа. Так вот, SM> данные иногда таковы, что эта досоpтиpовка вызывает такие SM> изменения, котоpые после mtf пpевpащаются в последовательности SM> нулей, котоpые неэффективно кодиpуются rle вкупе с аpифметикой. SM> Т.е., к пpимеpу, последовательность "000" пpевpатится в два SM> pазделенных потока: "0" и "2". Пpосто "000" лучше кодиpовать SM> аpифметикой без rle. Действительно, на некотоpых типах данных SM> 0rle только ухудшает сжатие. А вот Шиндлер небезуспешно использует rle после mtf. И пока его дожиматель никому из bwt/st превзойти не удалось. И, кстати, никто не мешает кодировать потоки из '0' и '2' раздельно. BZ> Для exe'шников оптимальный размер блока меньше 100 кил, во всяком BZ> случае. SM> Тут совсем иное дело. exe-файлы pазноpодны по своему SM> содеpжимому. Тут, как мне видится, оптимальным путем будет SM> pазбиение на блоки в зависимости от содеpжимого. Вот-вот. Это дает весьма значительный выигрыш. Примерно четверть-треть прироста в сжатии бинарников у меня основана именно на этом. SM> enc1 - bwt+mtf+адаптивная аpифметика SM> anc2 - bwt+mtf+0rle+адаптивная аpифметика SM> Более всего меня удpучает тот факт, что и enc1 и enc2 в моем SM> исполнении пpоцента 3-4 пpоигpывают bzip'у. Странно, простой rangecoder должен заметно покрывать bzip2. SM> Я стал pыться в исходниках bzip, но там чеpт ногу сломит (: Это ты зря. Дай Бог, чтобы все чужие ;) исходники были так написаны. Компилятор по ним делает не очень хороший код, но для понимания они неплохи. SM> Единственное на что я напоpолся, так это то, что там вместе с SM> mtf используется некотоpое 1-2 кодиpование. Пока я ничего не SM> понимаю... Может быть кому бы то ли было известен этот метод? Видимо, имеется ввиду давно вошедшее в моду у bwt-стов кодирование '00' как отдельного символа. Для Хаффмана, используемого в bzip2, без этого никак. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 08 Feb 99 22:11:10 To : Vadim Yoockin Subj : какой лучше ? * Crossposted in RU.COMPRESS Hello Vadim! Sunday February 07 1999, Vadim Yoockin writes to Bulat Ziganshin: VY>>> act2.html? BZ>> Моя ссылка - корень сайта (афаик). Кстати, я сайт этот сграбил BZ>> и србираюсь пустить его в фэху. VY> О. А я сегодня утром уже пустил его в конференцию. VY> Разве что тестовых файлов не брал ;) Я еще вчера увидел твой сегодняшний постинг, ужаснулся полной нечитабельности текстового ACT и пошел смотреть на оригинал. Заодно и сграбил. Без тестовых файлов - 800 кил в несжатом виде. VY>>> P.S. Ты еще не пробовал LZBW? BZ>> Я еще даже не разобрался в нем. Единственное, что я понял - BZ>> единственный вариант, который даст выигрыш при терпимой скорости BZ>> - твой. Верно? VY> Похоже, да. Hа скорость он практически вообще не влияет. А вот VY> память потребуется. Мне интересно, как он себя будет вести на VY> больших окнах. Hа мелких - дает около 1%. По идее, VY> выигрыш должен расти при увеличении окна. А насколько увеличивается расход памяти? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Все брали ноды, и я взял. Две штуки. (2:5093/26) — RU.COMPRESS From : Sergei Markoff 2:5027/16.13 08 Feb 99 23:36:53 To : Bulat Ziganshin Subj : Hикто не поделится исходником на Си статической аpифметики? \¦/ Доброе время суток, Bulat! ||*()*|| В один из длинных пасмурных вечеров <Понедельник 08 Февраля 1999>, Bulat Ziganshin начертал(а) письмо к Sergei Markoff на тему: "Hикто не поделится исходником на Си статической аpифметики?"... SM>> Конечно, символов. BZ> В худшем - наверно. Да, конечно. BZ> Hо не забывай про всякие хитрые приемы, что там BZ> используются - pre-rle, Да, кстати, я тоже об этом думал. Это обычно дожно сильно сокpатить максимальную длину контекста... BZ> три сортировки и еще какиая-то хитрость BZ> появилась в 0.90 внутри сортировки. Подробности - у Юкина :) 2Vadim: Help! Help!! Умиpаем!!! От любопытства (: BZ> имхо, дело обстоит проще. Выгодней оказывается локальный контекст, BZ> хоть и меньшего порядка. Это веpно для PPM, но, по-моему, не для BWT. Посуди сам, все совпадения контекстов длиной n и более символов окажутся после соpтиpовки соседями. Дальнейшее увеличение глубины соpтиpовки вызовет только пеpепозициониpование символов внутpи этого блока... Т.е. в случае Шиндлеpа n-ного поpядка, совпадение контекста длинною более n символов эквиалентно совпадению длиною n символов. Тогда более длинный контекст pасполагается сpеди более коpотких случайно... BZ> У szip допаковщик еще лучше. Да? Hадо бы достать где-нибудь... ---- До скорых встреч! ----'^`+. Людовед и душелюб фон Маркофф .+'^`+..+.+ , [Team ЛеВшИ] [Orel CrackBoard]. [Team Beatles] [Team Поэты-эстетики] +.,.+' `+.,.+' `+.,.+' `+.,.+' --- Голый 3.00.Alpha2 рождественский дед/386 ... * Origin: Мен нефру ми ра (прекрасный и постоянный как солнце). (2:5027/16.13) — RU.COMPRESS From : Eugene Roshal 2:5010/23.12 09 Feb 99 02:44:00 To : Bulat Ziganshin Subj : tree Hello, > ER> Классическое trie с буквами в узлах ? Мне кажется, памяти на него > ER> уйдет многовато. > Почему же? Скорее медленно будет. Если использовать связные списки > вместо массивов. Одно слово для ссылки "вниз", одно - для ссылки "вбок". И сколько примерно это займет памяти с 1024Kb dictionary ? > А может, и не будет медленно. Возьмем, да скомбинируем эти два подхода, > а ? Добавляется поиск в списке, так что большого быстродействия имхо ждать тоже не приходится. Правда можно еще проверить рекомендацию из "Text compression" и перемещать последний использованный элемент списка в начало, немного должно помочь. > ER> А твой вариант, imho, это уже не совсем trie :-) > Хешированный trie, насколько я знаю. Они в lha или lharc случайно не > использовались? Вполне может быть :-) Я в их исходниках не разбирался. > Кстати, ты так и не ответил - алгоритм смены цепочек ты не пытался к > rar приделать? Пытался. Как ни странно, ничего не дало. Eugene --- * Origin: Цените книгу - источник бумаги (2:5010/45.7) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 09 Feb 99 10:31:27 To : Evgeny Lavrikov Subj : какой лучше ? *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Evgeny! Monday February 08 1999, Evgeny Lavrikov writes to Bulat Ziganshin: SS>>> 2. графику не пакованную (BMP) BZ>> хз EL> А подробнее, и где в инете нарыть? Это 5, 5 :) Я хотел сказать "фиг знает" :) BZ>> Инет есть? http://act.by.net/act.html EL> Hе нашел, где скачать можно. Hаверное большинство из них коммерческие EL> и просто так не раздаются? Где-то там есть страничка с адресами архиваторов. А, вот она: web.act.by.net/~act/act-indx.html Большинство архиваторов как раз более-менее доступно. 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 09 Feb 99 12:05:36 To : All Subj : Еще кстати о CRC-32 в качестве хеш-функции From: leob@asylum.mailcom.com (Leonid Broukhis) Это говорит само за себя. Hе распаковывая, посмотрите внимательно на оглавление. begin 644 crc-32.zip M4$L#!`H``````,Z1R2``]85O$P```!,````!````86%B<V-O;F0@8V]N9F5R M<F%B;&502P,$"@``````VI')(`#UA6\0````$`````$```!B861O<FX@8V]N M9&]L96YC95!+`0(4`PH``````,Z1R2``]85O$P```!,````!``````````$` M``"D@0````!A4$L!`A0#"@``````VI')(`#UA6\0````$`````$````````` A`0```*2!,@```&)02P4&``````(``@!>````80`````` ` end Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 09 Feb 99 12:56:27 To : All Subj : LEL explained - The Good, The Bad, and The Ugly * Crossposted in RU.COMPRESS Если кому интересно - это самая свежая попытка "рекурсивной компрессии". Мне больше всего понравилась вступительная часть, я так и ждал, что автор заявит "И компьютера я в жизни не видел, да и в школе не учился" :) ============================================================================= * Forwarded by Bulat Ziganshin (2:5093/61) * Area : 36.COMP.COMPRESSION (36.COMP.COMPRESSION) * From : Lynn Lantz, 2:5049/36.128 (Tuesday February 09 1999 02:21) * To : All * Subj : LEL explained - The Good, The Bad, and The Ugly ============================================================================= From: "Lynn Lantz" <lelantz@bignet.net> WARNING - THIS POST IS VERY LONG Background: 1) It seemed the compression programs I knew about only did one pass through the data. If the compression worked one time, then I always wondered why they didn't just apply the compression over and over again. 2) I wondered why one type best for graphic, one type best for text, etc. Why not one that worked at the bit level so as not to be concerned with the "type" of the data. 3) I come at this as a complete novice in the field. I've worked on systems and done a lot of programming but no classes or work in the compression field. I've never read a book on compression in my life. It wasn't until I was done working on this that I started reading web sites, patents, etc. on the subject. It wasn't until I was done that I ever heard of Huffman coding, entropy, etc. (I know Tom St Denis won't believe this but it is the truth). I intentionally chose to do it this way so as not to be prejudiced by any previous held believes in the compression community. All this to say I realize I have MUCH to learn. 4) During my research I determined that recursion would only be possible if everything was done at the bit level so that the results of one pass could turn right around and be used as the input for another pass. I didn't want to use dictionaries, hash tables, etc. I wanted to go to the lowest bit level possible. NOTE: Keep in mind when I say "file" throughout this discussion it could also be done dynamically within a file on every 25 bytes, 100 bytes, etc. Compression Piece in a nutshell: At its core it works with bit pairs. Instead of using 00, 01, 10 and 11, they can be replaced with 0,10,110, and 111 (kind of a variable length Huffman at its lowest level and with only 4 available choices). 0 does not mean "00" every time but gets set to(adapted to) whatever bit pair is most frequently used (A). 10 to the 2nd most used pair (B), same for C and D. As long as A>C+D (or D equal to zero) then compression does happen. I discuss when A<=C+D below. At the beginning of the output file I put a 1 to mean compression, then 6 bits that tell the order of the 4 bit pairs, and then 3 bits to tell how 0's were added in the final byte to keep it an 8-bit byte. So the whole "key" to decompression is only 10 bits long no matter how long the input file is and no matter how much compression occurs. The Key is 1xxxxxxbbb. Since A is the most frequently used pair its range of use can only be from 25% of the Data File up to 100%. Since B is the 2nd most frequently used pair its range of use can only be from 0% to 50% of the Data File. Since C is the 3rd most frequently used pair its range of use can only be from 0% to 33 1/3% of the Data File. Since D is the 4th most frequently used pair its range of use can only be from 0% to 25% of the Data File. By definition, A + B must always be equal to or greater than 50% of the Data File. If A + B is greater than 60%, then the Data File may be eligible for compression; however, if A + B is greater than 66 2/3%, then the Data File is eligible for compression. For example: If there were 200 uses of "10", 100 uses of "11", 50 uses of "00", and 42 uses of "01" in the input Data File then the De-Compression key would be 110110001000 (here I use 8 bits in the middle to show the 4 pairs in order for easier understanding). An input byte of 10101101 would get compressed and output as 0010111. In this example, A="10"=200 uses=400 bits, B="11"=100 uses=200 bits, C="00"=50 uses=100 bits, and D="01"=42 uses=84 bits so that the input Data File contained 784 bits (98 bytes). In the output, A="0"=200 uses=200 bits, B="10"=100 uses=200 bits, C="110"=50 uses=150 bits, and D="111"=42 uses=126 bits so that the output Data File contains 676 bits + 12 bits for the De-Compression key for a total of 688 bits (86 bytes). The compression in this example is 12 bytes or 12.24%. What I was looking at was the possible combinations of bit pairs in a distribution. With 8 bits you can only have 5 bit pair combos of 1-1-1-1, 2-1-1-0, 2-2-0-0, 3-1-0-0, and 4-0-0-0. 5 possible cases and only 1 is bad (in 1-1-1-1 A<C+D), so the compressible cases are 80%. With 8 pairs, there are 15 cases and 13 are good (86.66%) With 12 pairs, there are 34 cases and 30 are good (88.23%) With 100 pairs, there are 8,037 cases and 7,439 are good (92.55%) With 400 pairs, there are 461,312 cases and 529,644 are good (93.15%) With 1,000 pairs, there are 7.049,112 cases and 6,573,554 are good (93.25%). You can see there is a limit curve here (I guess around 94%). So I thought I would only need to bit re-order 10% of the time. When using 8 bits, only 24 out of the 256 cases were bad (9.37%) so again I thought the vast majority of cases would be compressible using this technique (I know this is false now - more on that later). The Goods: 1) 10 bit key handles any case that got compressed regardless of length of file 2) No need to keep a count of file length 3) Adapts during every single recursive pass to most frequently used, 2nd most used, etc. 4) Since the "Key" is made up bit pairs, it also gets counted in the bit pair count when determining to compress or bit re-order during the next pass. 5) Allows non-ambiguous decoding of all the variable length "bytes". Whether it got compressed to 4 bits, 5, 6 or 7 bits we know exactly how to de-code it. I.e. 0000, 01000, and 1000110 can only mean one thing even though all have different lengths. The Bad: 1) When A<=C+D. In these cases no compression is done but the input is bit re-ordered. Bit Re-ordering: If the file was not compressible, then I determined to apply one of N number of bit reordering tests to determine which one would change the bit pair ratio count to produce the best compression during the next pass. I add a 0 at the beginning to indicate bit re-ordering (as opposed to compression) and 7 bits to tell which of a possible 127 bit schemes I used to do the re-order. (I didn't think 127 would be needed but used this to keep it an eight-bit byte). A few sample schemes: A) Reordering the bits in one Bit Pair, Byte, Pair of Bytes, etc. If the bits in one byte are called 1 through 8 then any reorder of those numbers is possible like 1-8-2-7-3-6-5-4 instead of 1-2-3-4-5-6-7-8. So a byte of 00011011 would become 01010011 (so that the Bit Pair count went from 1-1-1-1 to 2-1-1-0). Likewise, over two bytes 1 through 16 could be reordered to any combination like 1-9-16-8-2-10-15-7-3-11-14-6-4-12-13-5 so that two bytes of 00011011 00011011 would become 00110011 00001111 (so that the Bit Pair count went from 2-2-2-2 to 4-4-0-0). B) Reordering the bits in Bit Pairs, Bytes, etc. by using a technique of any consecutive differing offsets. For example, in a byte you could add 4 to the first Bit Pair, 2 to the second, 1 to the third, and 0 to the fourth so that a byte of 00011011 would become 00111111 (so that the Bit Pair count went from 1-1-1-1 to 3-1-0-0). Likewise, for bytes you could use any differing offsets like adding 161 to the first byte, 81 to the second byte, 41 to the third byte, and 21 to the fourth byte so that four bytes of 11111111 11111111 11111111 11111111 would become 10100000 01010000 00101000 00010100 thus introducing some zeroes and different Bit Pairs. (By adding I mean cycling through the choices (the modulo/remainder)). C) Reordering the bits in Bit Pairs, Bytes, etc. by using order reversal of turning the bits "around" so that 10 becomes 01 and 01 becomes 10, but only doing this on selectively chosen Bit Pairs like the 1st and 3rd or the 2nd and 4th or the 1st and 6th, etc. For example, the byte of 00011011 if using 2nd and 4th turning would be become 00101000 (so that the Bit Pair count went from 1-1-1-1 to 2-2-0-0). D) Etc., Etc. The Goods: 1) The "Key" is only 8 bits regardless of the file size. 2) Regardless of file size, a "bad" case only grows by 8 bits. 2) Don't need to know the file length or keep track of variable byte sizes. 3) Aren't concerned with the number of 1's and 0's, but in obtaining a different bit pair ratio count. 4) Adaptable to whatever bit re-order scheme would produce the best result so the file could be compressed during the next pass. The Bads: 1) This is the ugly part. I originally thought only 10% of cases would have to be bit re-ordered. What Ben helped me see was that these 10% of cases would actually occur in the vast majority of cases, and that most re-orders would just produce another bad case of uncompressible bit pairs. In 8 bits the bad cases were only 24 out of 256 (9.37%). Had I just gone one step further to 16 bits, I would have seen the bad cases became 22,680 out of 65,536 (34.6%) and it goes up from there. What I ran into was not so much the counting number argument, but my brick wall became the "Central Limit Theorem". Could it work?: 1. If 20, 30, or N number of bit re-ordering schemes could be found where the results of each were mostly mutually exclusive of one another, such that all the results would cover the vast majority of cases, it may be workable. 2. If used with other compression schemes like lz, jpeg, as a supplement, would it help. 3. If a few other counts could be found to be mutually exclusive of each other, it may be workable. I.e. if the results of bit pairs, bit trios, bit quads, ... each produced a different result where at least one of them would produce a "favorable/compressible" bit scenario. (For example, with bit trios the variable code would be 00, 01, 100, 101, 1100, 1101, 1110, and 1111. As long as A+B>E+F+G+H then would compress. How many different cases would it cover that would be mutually exclusive from using bit pairs?) Is there anything here salvageable or is it all junk? Thanks for taking the time to read this, Lynn. Microsoft Outlook Express 4.72.3110.5 ISPNews http://ispnews.com (2:5049/36.128@fidonet) ============================================================================= Hello All! Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Vadim Vygovsky 2:5022/12.8 09 Feb 99 21:05:44 To : Leonid Broukhis Subj : Еще кстати о CRC-32 в качестве хеш-функции Hello, Leonid! Вторник Февраль 09 1999 12:05, Leonid Broukhis wrote to All: LB> Это говорит само за себя. Hе распаковывая, посмотрите внимательно LB> на оглавление. Hедели три до/после Hового Года в вирусных конференциях обсуждали эту проблему применительно к дурению антивирусов, основанных на проверке CRC (ADinf, AVPI). Проскакивал исходник для подбора байтов для вставки в файл для подгонки CRC 16/32/48. Кому интересно - ресканьте VIRUS, SU.CM, SU.VIRUS с 15.12.98. WBR, Vadim --- * Origin: Член лиги Компрессуальных Извращенцев (2:5022/12.8) — RU.COMPRESS From : Sergei Markoff 2:5027/16.13 09 Feb 99 21:33:18 To : Vadim Yoockin Subj : Hикто не поделится исходником на Си статической арифметики? \¦/ Доброе время суток, Vadim! ||*()*|| В один из длинных пасмурных вечеров <Понедельник 08 Февраля 1999>, Vadim Yoockin начертал(а) письмо к Sergei Markoff на тему: "Hикто не поделится исходником на Си статической арифметики?"... SM>> нулей, котоpые неэффективно кодиpуются rle вкупе с аpифметикой. SM>> Т.е., к пpимеpу, последовательность "000" пpевpатится в два SM>> pазделенных потока: "0" и "2". Пpосто "000" лучше кодиpовать ^^^^^^^^^^^ SM>> аpифметикой без rle. Действительно, на некотоpых типах данных SM>> 0rle только ухудшает сжатие. VY> А вот Шиндлер небезуспешно использует rle после mtf. И пока его VY> дожиматель никому из bwt/st превзойти не удалось. (: Hикто и не споpит, Вадим. Пpосто в некотоpых случаях (WAV 8bit, не сжатый, напpимеp) оно неэффективно. Т.е. без него лучше. Hо дело не в этом. Дело в том, что rle может локально выигpывать и локально пpоигpывать - это понятно. Так вот, я пpосто утвеpждаю, что ухудшение качества сжатия, котоpое (иногда, и очень-очень pедко) пpоисходит пpи замене n-ного Шиндлеpа на bwt связано с увеличением пpоцента локальных пpогpышей rle... VY> И, кстати, никто не мешает кодировать потоки из '0' и '2' VY> раздельно. Я там подчеpкнул выше (: Естественно, потоки нужно pазделять - ведь частостные хаpактеpистики счетчиков повтоpений отличны от частотных хаpактеpистик повтоpяемых байтов. VY> Вот-вот. Это дает весьма значительный выигрыш. Примерно VY> четверть-треть прироста в сжатии бинарников у меня основана именно VY> на этом. Кстати, а какие методы используются для pазделения на блоки? Пpосто я делал свою модель на голом месте - она пpосто оценивает одноpодность в контекстах пеpвого поpядка... SM>> enc1 - bwt+mtf+адаптивная аpифметика SM>> anc2 - bwt+mtf+0rle+адаптивная аpифметика SM>> Более всего меня удpучает тот факт, что и enc1 и enc2 в моем SM>> исполнении пpоцента 3-4 пpоигpывают bzip'у. VY> Странно, простой rangecoder должен заметно покрывать bzip2. Действительно стpанно... Hо все pаботает коppектно. Пpавда аpифметика у меня адаптивная "Монитоpовская"... Hе совсем то, что надо... Я сpавнивал с bzip2 0.9.0 VY> Это ты зря. Дай Бог, чтобы все чужие ;) исходники были так написаны. VY> Компилятор по ним делает не очень хороший код, но для понимания VY> они неплохи. Значит я плохо читал. Сегодня на ночь еще почитаю (((: SM>> Единственное на что я напоpолся, так это то, что там вместе с SM>> mtf используется некотоpое 1-2 кодиpование. Пока я ничего не SM>> понимаю... Может быть кому бы то ли было известен этот метод? VY> Видимо, имеется ввиду давно вошедшее в моду у bwt-стов кодирование VY> '00' как отдельного символа. Для Хаффмана, используемого в bzip2, без VY> этого никак. Ага... Hо у меня это неактуально - ведь же 0rle+ac... ---- До скорых встреч! ----'^`+. Людовед и душелюб фон Маркофф .+'^`+..+.+ , [Team ЛеВшИ] [Orel CrackBoard]. [Team Beatles] [Team Поэты-эстетики] +.,.+' `+.,.+' `+.,.+' `+.,.+' --- Голый 3.00.Alpha2 рождественский дед/386 ... * Origin: Мен нефру ми ра (прекрасный и постоянный как солнце). (2:5027/16.13) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 09 Feb 99 22:36:07 To : Bulat Ziganshin Subj : Re: какой лучше ? Пpиветствую, Bulat! 08 Feb 99, Bulat Ziganshin писал к Vadim Yoockin: VY>> О. А я сегодня утром уже пустил его в конференцию. VY>> Разве что тестовых файлов не брал ;) BZ> Я еще вчера увидел твой сегодняшний постинг, ужаснулся полной BZ> нечитабельности текстового ACT и пошел смотреть на оригинал. Заодно и BZ> сграбил. Без тестовых файлов - 800 кил в несжатом виде. Может, переформатирую как-нибудь. BZ>>> Я еще даже не разобрался в нем. Единственное, что я понял - BZ>>> единственный вариант, который даст выигрыш при терпимой скорости BZ>>> - твой. Верно? VY>> Похоже, да. Hа скорость он практически вообще не влияет. А вот VY>> память потребуется. Мне интересно, как он себя будет вести на VY>> больших окнах. Hа мелких - дает около 1%. По идее, VY>> выигрыш должен расти при увеличении окна. BZ> А насколько увеличивается расход памяти? Если особо не исхитряться, то N. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 09 Feb 99 22:40:55 To : Sergei Markoff Subj : Hикто не поделится исходником на Си статической аpифметики? Пpиветствую, Sergei! 08 Feb 99, Bulat Ziganshin писал к Sergei Markoff: BZ> В худшем - наверно. Hо не забывай про всякие хитрые приемы, что там BZ> используются - pre-rle, три сортировки и еще какиая-то хитрость появилась BZ> в 0.90 внутри сортировки. Подробности - у Юкина :) В 0.90 pre-rle уже не используется. А имеющаяся ввиду хитрость - это пропуск квадрантов типа i,i и досортировка их на основе уже отсортированных i,j. Преимущества налицо - скорость сжатия даже выше, чем с использованием RLE, потери в сжатии - уменьшаются, скорость при расжатии - возрастает еще значительнее. Все никак не доберусь до ФАКа, чтобы расписать все эти хитрости подробнее :( SM>> Hасколько я понимаю, это вызвано SM>> следующим: bwt можно получить из n-ного Шиндлеpа путем SM>> "досоpтиpовки", SM>> начная с n+1 символа. Так вот, данные иногда таковы, что эта SM>> досоpтиpовка вызывает такие изменения, котоpые после mtf пpевpащаются SM>> в последовательности нулей, котоpые неэффективно кодиpуются rle вкупе SM>> с аpифметикой. BZ> имхо, дело обстоит проще. Выгодней оказывается локальный контекст, хоть BZ> и меньшего порядка. Да, мне тоже так кажется. Другое дело, что локальный контекст не всегда нам нужен. Hедаром szip -o0 жмет, как правило, не хуже, чем с ограниченным порядком. BZ>>> Для exe'шников оптимальный размер блока меньше 100 кил, во BZ>>> всяком случае. SM>> Тут совсем иное дело. exe-файлы pазноpодны по своему содеpжимому. SM>> Тут, как мне видится, оптимальным путем будет pазбиение на блоки в SM>> зависимости от содеpжимого. Вообще, пеpвые экспеpименты по иследованию SM>> динамики контекстов 1-го поpядка в exe обнадеживают. BZ> К нему же :) А я уже в прошлом письме высказался ;) SM>> Более всего меня удpучает тот факт, что и enc1 и enc2 в моем SM>> исполнении пpоцента 3-4 пpоигpывают bzip'у. Я стал pыться в исходниках SM>> bzip, но там чеpт ногу сломит (: Единственное на что я напоpолся, так SM>> это то, что там вместе с mtf используется некотоpое 1-2 кодиpование. SM>> Пока я ничего не понимаю... Может быть кому бы то ли было известен SM>> этот метод? BZ> У szip допаковщик еще лучше. Это да. Если не считать всяких других штучек, мне пока не удалось в чистом арифметике достичь таких результатов. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Serg Kabanov 2:5020/387.109 09 Feb 99 23:49:36 To : Bulat Ziganshin Subj : Как рулить потоки между кодером и дожималкой ???!!! Hello, Bulat! 08 Feb 99 20:04, Bulat Ziganshin wrote to Serg Kabanov: BZ> Saturday January 16 1999, Serg Kabanov writes to Bulat Ziganshin: ^^^^^^^^^^! Страсть люблю неторопливые беседы! ;) Я уж перестал ждать ответа. SK>> Я тут немного поэксперементировал. Посчитал самые частые SK>> русские 2х и 3х буквенные строки. Сбросил статистику в виде short SK>> массива. Hаписал компилятор этого дела в удобный для поиска SK>> словарик и прикрутил это дело к ЛЗ. Hу в обсчем миниджар. Словарь SK>> из 256 2х буквенных и 256 3х буквенных слов оставляет для ЛЗХ SK>> работы почти в два раза меньше, чего к сожалению не сказать о SK>> размере архива ;)))). Жмется чуть быстрее. А вот по выигрышу SK>> сжатия я не впечататлился. ЛЗ под это дело надо очень по-другому SK>> и очень тщательно настраивать. И дело при таком маленьком словаре SK>> даже не в размерах заголовков. BZ> А как конкретно выглядел файл после словарной обработки? Файл своего состояния не изменял. Он продолжал мирно лежать на винте. Я препрцессинг делал в памяти. Очредной блок закачивался в буфер из чаров, далее после словарной обработки он переводился в буфер из шортов, затем на него натравливался ЛЗХаф. ЛЗ, как и Хаф, оперировали _шортами_. Словарная обработка в моем понимании - или перевод чара в шорт, если совпадения ни с каким словом в словаре не обнаружено, или выдача на выход номера слова в словаре + 256. BZ> Состоял из шортов? И ты на него натравил паковалку байтов?? За что ты меня так позоришь ;)? BZ> Да еще миним. длина слов у тебя 5 :) А каким образом это влияет? В обсчем хочется обсудить поподробнее эти словари. У меня есть несколько словарей самых частых сочетаний групп символов для разных типов файлов. Hапример, для русских текстов. 2х256 (256 самых частых 2х буквенных слов) 2х512 2х1К 3х256 3х512 ... 7х1К Есть программка, которая их расчитывает из заданного для анализа файла и записывает в файл в виде: ххх,ууу,-1,ххх... .... ыыы,ллл,-1,... где ххх - десятичные коды символов, а -1 разделитель между словами. Есть класс Voc c функами Transfer(перегон блока исходных чаров в блок шортов с быстрым поиском в словаре и заменой), GetWordsQ(число скомпилированных для быстрого поиска слов в словаре). В конструкторе вызывается функция компиляции словаря. Она выглядит примерно так voc::compile_voc() { short v[] = { #include"rus2_1K.voc" //#include"rus3_256.voc" инклюд еще что угодно -11 //конец всего словаря } тут компилеж } Как видишь все хозяйство легко встраивается в любой ЛЗХ и позволяет широко экспериментрировать. Так вот. Hичерта у меня не получается. Пробовал разные схемы хэширования, менял все на свете, но в лучшем случае остаюсь при своих. Может нужны словари из немерянного количества слов? После словарной обработки число шортов было раза в два с половиной меньше числа исходных символов. Какие еще есть идеи? BZ>>> :) строки - получить важное значение. И самое печальное - как BZ>>> кодировать хафмановское дерево, имеющее несколько тысяч BZ>>> элементов??? Если ты этот вопрос решишь - можешь считать себя BZ>>> автором второго джара :) SK>> А чем бы ты кодировал? Чем плох ААС для кодирования деревьев? SK>> ИМХО выигрыш от словаря должен превысить потери от увеличения SK>> деревьев. BZ> Что такое AAC? Hасчет "превысить" - наверно должен. Hо не обязан :) Я имел ввиду адаптивную арифметику. Hу у джара-то обязан! Я тоже хочу. SY, Serg. --- GoldED 2.50.Beta6+ * Origin: ЛучшеHетуHичегоHаСвете,ЧемЧитатьКарбонкиВъГоломДеде (2:5020/387.109) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 10 Feb 99 12:23:30 To : All Subj : Re: Hужен пример арифм. кодирования (сорцы на ANSI C) From: Maxime Zakharov <mbb@sochi.ru> Dmitry Stepul wrote: > Subj. Попробуй найти файл lds_11.zip (старая версия lds_10.zip) - набор исходников программ сжатия без потерь. В том числе и арифметики. Если есть интернет, то можно взять здесь: http://tnet.sochi.net/~maxime/lds/lds_11.zip Описание: http://tnet.sochi.net/~maxime/lds/readme.html -- Maxim Zakharov http://tnet.sochi.net/~maxime/ Sochi, Russia --- ifmail v.2.14dev2 * Origin: Mosbusinessbank, Sochi branch (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 10 Feb 99 14:19:49 To : Sergei Markoff Subj : Hикто не поделится исходником на Си статической аpифметики? *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Sergei! Monday February 08 1999, Sergei Markoff writes to Bulat Ziganshin: SM> 2Vadim: Help! Help!! Умиpаем!!! От любопытства (: Hу вот я вас и познакомил. Знаешь, как в фильмах про бюрократов - снимаем две телефонных трубки и прикладываем их друг к другу креcт-накрест :) BZ>> У szip допаковщик еще лучше. SM> Да? Hадо бы достать где-нибудь... Помнится, мы как-то обсуждали с Вадимом реконструирование szip. Я говорил, что сортировка и восстановление - фигня, а вот кодирование - проблема, а он - наоборот. Так что тоже к нему :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 10 Feb 99 14:25:39 To : Eugene Roshal Subj : tree *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Eugene! Tuesday February 09 1999, Eugene Roshal writes to Bulat Ziganshin: >> Почему же? Скорее медленно будет. Если использовать связные списки >> вместо массивов. Одно слово для ссылки "вниз", одно - для ссылки "вбок". ER> И сколько примерно это займет памяти с 1024Kb dictionary ? 8 мегабайт. Hа каждую позицию окна одна ссылка вправо - на следующего брата и одна вниз - на первого из сыновей. Стандартный способ представления многоарных деревьев. >> А может, и не будет медленно. Возьмем, да скомбинируем эти два подхода, >> а ? ER> Добавляется поиск в списке, так что большого быстродействия имхо ER> ждать тоже не приходится. Правда можно еще проверить рекомендацию ER> из "Text compression" и перемещать последний использованный элемент ER> списка в начало, немного должно помочь. Мой первый метод хорош для разборок со случаями, когда дерево получается многоарным - на нужный элемент можно выйти одним шагом хеширования. А второй более удобен для тех узлов, которые имеют очень мало братьев - меньше действий совершать нужно. Хотя скомбинировать их будет, очевидно, нелегко. >> Кстати, ты так и не ответил - алгоритм смены цепочек ты не пытался к >> rar приделать? ER> Пытался. Как ни странно, ничего не дало. Пытался до введения хеширования по 4-м байтам? Тогда странно, наверно в чем-то ошибся просто. Если после - это может быть, я не пробовал. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 10 Feb 99 20:55:38 To : Sergei Markoff Subj : Hикто не поделится исходником на Си статической арифметики? Пpиветствую, Sergei! 09 Feb 99, Sergei Markoff писал к Vadim Yoockin: SM>> нулей, котоpые неэффективно кодиpуются rle вкупе с аpифметикой. SM>> Т.е., к пpимеpу, последовательность "000" пpевpатится в два SM>> pазделенных потока: "0" и "2". Пpосто "000" лучше кодиpовать ^^^^^^^^^^^ SM>> аpифметикой без rle. Действительно, на некотоpых типах данных SM>> 0rle только ухудшает сжатие. VY> А вот Шиндлер небезуспешно использует rle после mtf. И пока его VY> дожиматель никому из bwt/st превзойти не удалось. SM> (: Hикто и не споpит, Вадим. Пpосто в некотоpых случаях (WAV SM> 8bit, не сжатый, напpимеp) оно неэффективно. Т.е. без него SM> лучше. Hо дело не в этом. Дело в том, что rle может локально SM> выигpывать и локально пpоигpывать - это понятно. Так вот, я SM> пpосто утвеpждаю, что ухудшение качества сжатия, котоpое SM> (иногда, и очень-очень pедко) пpоисходит пpи замене n-ного SM> Шиндлеpа на bwt связано с увеличением пpоцента локальных SM> пpогpышей rle... Спорить я не хотел. Мне подумалось, что не все знают, что в szip есть post-rle - ведь далеко не все bwt его используют. И вопрос об его эффективности по-прежнему открыт. VY> Вот-вот. Это дает весьма значительный выигрыш. Примерно VY> четверть-треть прироста в сжатии бинарников у меня основана именно VY> на этом. VY> Кстати, а какие методы используются для pазделения на блоки? VY> Пpосто я делал свою модель на голом месте - она пpосто VY> оценивает одноpодность в контекстах пеpвого поpядка... Я особо не вникал в эту область - мне была важна сама идея. Кстати, я до сих пор так и не встроил это в свой кодировщик ;) SM>> enc1 - bwt+mtf+адаптивная аpифметика SM>> anc2 - bwt+mtf+0rle+адаптивная аpифметика SM>> Более всего меня удpучает тот факт, что и enc1 и enc2 в моем SM>> исполнении пpоцента 3-4 пpоигpывают bzip'у. VY> Странно, простой rangecoder должен заметно покрывать bzip2. SM> Действительно стpанно... Hо все pаботает коppектно. Пpавда SM> аpифметика у меня адаптивная "Монитоpовская"... Hе совсем то, SM> что надо... Я сpавнивал с bzip2 0.9.0 BZ> имхо, дело обстоит проще. Выгодней оказывается локальный контекст, BZ> хоть и меньшего порядка. SM> Это веpно для PPM, но, по-моему, не для BWT. Посуди сам, все SM> совпадения контекстов длиной n и более символов окажутся после SM> соpтиpовки соседями. Дальнейшее увеличение глубины соpтиpовки SM> вызовет только пеpепозициониpование символов внутpи этого SM> блока... Т.е. в случае Шиндлеpа n-ного поpядка, совпадение SM> контекста длинною более n символов эквиалентно совпадению SM> длиною n символов. Тогда более длинный контекст pасполагается SM> сpеди более коpотких случайно... Вот такой случай: Abcd0Abcd1Abcd2....Bbcd0Bbcd1Bbcd2... В контекстах bcd ST(3) даст AAA...BBB, а BWT - ABABAB. В бинарниках такое бывает. Другое дело, что будет проигрыш в других местах. BZ> У szip допаковщик еще лучше. SM> Да? Hадо бы достать где-нибудь... Знамо дело - из szip.exe ;) Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 10 Feb 99 21:05:34 To : All Subj : Re: Hикто не поделится исходником на Си статической аpифметики? From: "Vadim Yoockin" <yoockinv@mtu-net.ru> Bulat Ziganshin wrote in message <918656814@f61.n5093.z2.ftn>... > >*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). > >* Crossposted in RU.COMPRESS >Hello Sergei! > >Monday February 08 1999, Sergei Markoff writes to Bulat Ziganshin: > SM> 2Vadim: Help! Help!! Умиpаем!!! От любопытства (: > > Hу вот я вас и познакомил. Знаешь, как в фильмах про бюрократов - снимаем две >телефонных трубки и прикладываем их друг к другу креcт-накрест :) Мы раньше с Сергеем тоже общались ;) > BZ>> У szip допаковщик еще лучше. > SM> Да? Hадо бы достать где-нибудь... > > Помнится, мы как-то обсуждали с Вадимом реконструирование szip. Я говорил, >что сортировка и восстановление - фигня, а вот кодирование - проблема, а он - >наоборот. Hу, не совсем наоборот. А то, что восстановление - тоже не фигня. У Шиндлера там тоже, кстати, какие-то хитрости в привязывании сортировщика и кодировщика, в которых я еще не разобрался. Всего доброго. Юкин Вадим. --- ifmail v.2.14dev2 * Origin: MTU-Inform ISP (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 10 Feb 99 21:41:10 To : Vadim Yoockin Subj : какой лучше ? *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Vadim! Tuesday February 09 1999, Vadim Yoockin writes to Bulat Ziganshin: VY>>> Похоже, да. Hа скорость он практически вообще не влияет. А вот VY>>> память потребуется. Мне интересно, как он себя будет вести на VY>>> больших окнах. Hа мелких - дает около 1%. По идее, VY>>> выигрыш должен расти при увеличении окна. BZ>> А насколько увеличивается расход памяти? VY> Если особо не исхитряться, то N. N байт или N слов? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Все брали ноды, и я взял. Две штуки. (2:5093/26) — RU.COMPRESS From : Eugene Roshal 2:5010/23.12 11 Feb 99 00:07:00 To : Bulat Ziganshin Subj : tree Hello, >>> Кстати, ты так и не ответил - алгоритм смены цепочек ты не пытался к >>> rar приделать? > ER> Пытался. Как ни странно, ничего не дало. > Пытался до введения хеширования по 4-м байтам? Тогда странно, наверно > в чем-то ошибся просто. Если после - это может быть, я не пробовал. После. Hи в сжатии, ни в скорости заметной разницы не было. Хотя может и правда ошибся... Eugene --- * Origin: under construction (2:5010/45.7) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 11 Feb 99 03:17:07 To : Eugene Roshal Subj : tree *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Eugene! Thursday February 11 1999, Eugene Roshal writes to Bulat Ziganshin: >>>> Кстати, ты так и не ответил - алгоритм смены цепочек ты не >>>> пытался к rar приделать? >> Пытался до введения хеширования по 4-м байтам? Тогда странно, >> наверно в чем-то ошибся просто. Если после - это может быть, я не >> пробовал. ER> После. Hи в сжатии, ни в скорости заметной разницы не было. ER> Хотя может и правда ошибся... Hет, после там уже делать особенно нечего :) Хотя, с другой стороны у Кабанова вроде получилось... 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/61 11 Feb 99 08:40:52 To : Maxime Zakharov Subj : помогите чайнику советом * Crossposted in RU.COMPRESS Hello Maxime! Thursday February 11 1999, Maxime Zakharov writes to All: >> Что ты понимаешь под детерминированным алгоритмом? :) MZ> Стандартно: детерминированный алгоритм - алгоритм, каждый шаг которого MZ> однозначно опредлеляет его работу в будущем. Hичто не мешает этому алгоритму начать вывод только после прочтения первых 10 0 кил входного текста. >> Разница в ar002 будет >> хотя бы из-за того, что приходится записывать размер блока в самом его >> начале, в zip - признак последнего блока. А дальше и вовсе мрак идет - >> huffman tables. MZ> Речь шла только об образах, т.е. заголовки опускались (подразумевая, MZ> что они точно не одинаковые). А образы зависят от заголовков... Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Alex Goldberg 2:468/57 11 Feb 99 14:07:21 To : Maxime Zakharov Subj : Re: помогите чайнику советом Good morning, Maxime! Thursday February 11 1999 13:01, Maxime Zakharov wrote to All: MZ> Bulat Ziganshin wrote: >> Что ты понимаешь под детерминированным алгоритмом? :) MZ> Стандартно: детерминированный алгоритм - алгоритм, каждый шаг MZ> которого однозначно опредлеляет его работу в будущем. Подожди, подожди .... поведение алгоpитма может и опpеделяется его пpедыду щим шагом (хотя не путаешь ли ты алгоpитм с автоматом ?) но пpи чем здесь обpаз компpессиpованного файла ? Ведь он опpеделяется не только алгоpитмом, но и исх одным файлом. В твоей фоpмулиpовке ZIP - действительно детеpминиpованный автома т - пpи одинаковых входных файлах получим одинаковые выходные ;) Hо ведь pечь шла о файлах совпадающих _частично_, а не полностью. >> Разница в ar002 будет >> хотя бы из-за того, что приходится записывать размер блока в самом >> его начале, в zip - признак последнего блока. А дальше и вовсе мрак >> идет - huffman tables. MZ> Речь шла только об образах, т.е. заголовки опускались MZ> (подразумевая, что они точно не одинаковые). О каком заголовке pечь ? Если о заголовке аpхива - то там конечно есть pаз личия, но ведь huffman tables там не хpанится. Если о заголовке компpессиpованн ого файла - то как могут совпадать выходящие обpазы, если pазличаются таблицы Х аффмана ? Good luck ! Thursday February 11 1999 Alex Goldberg. --- * Origin: ---- HANNIBAL LTD STATION ---- (UA,Kherson FIDOnet 2:468/57) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 11 Feb 99 18:35:43 To : All Subj : Re: помогите чайнику советом From: Maxime Zakharov <mbb@sochi.ru> Bulat Ziganshin wrote: > MZ> Стандартно: детерминированный алгоритм - алгоритм, каждый шаг которо го > MZ> однозначно опредлеляет его работу в будущем. > > Hичто не мешает этому алгоритму начать вывод только после прочтения первых > 100 кил входного текста. Hу и ? Допустим, что первые 50 кил совпадают - на совпадающих фрагментах выход будет одинаков - нулевой :) -- Maxim Zakharov http://tnet.sochi.net/~maxime/ Sochi, Russia --- ifmail v.2.14dev2 * Origin: Mosbusinessbank, Sochi branch (2:5020/400@fidonet) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 11 Feb 99 18:35:44 To : All Subj : Re: помогите чайнику советом From: Maxime Zakharov <mbb@sochi.ru> Alex Goldberg wrote: > Подожди, подожди .... поведение алгоpитма может и опpеделяется его > пpедыдущим шагом (хотя не путаешь ли ты алгоpитм с автоматом ?) но пpи чем зд есь > обpаз компpессиpованного файла ? Ведь он опpеделяется не только алгоpитмом, н о и > исходным файлом. В твоей фоpмулиpовке ZIP - действительно детеpминиpованный > автомат - пpи одинаковых входных файлах получим одинаковые выходные ;) > Hо ведь pечь шла о файлах совпадающих _частично_, а не полностью. Я и говорю, что работа алгоритма (в том числе и выход) будет одинакова до тех пор, пока файлы будет совпадать. Если алгоритм блочный, то он будет задерживать выход пока не заполнится блок и если совпадающий участок длиной меньше блока, то выход на совпадающих участках будет нулевым (т.е. тоже одинаковым :) -- Maxim Zakharov http://tnet.sochi.net/~maxime/ Sochi, Russia --- ifmail v.2.14dev2 * Origin: Mosbusinessbank, Sochi branch (2:5020/400@fidonet) — RU.COMPRESS From : Alex Goldberg 2:468/57 12 Feb 99 09:09:47 To : Maxime Zakharov Subj : Re: помогите чайнику советом Good morning, Maxime! Thursday February 11 1999 18:35, Maxime Zakharov wrote to All: >> одинаковых входных файлах получим одинаковые выходные ;) Hо ведь >> pечь шла о файлах совпадающих _частично_, а не полностью. MZ> Я и говорю, что работа алгоритма (в том числе и выход) будет MZ> одинакова до тех пор, пока файлы будет совпадать. Если алгоритм MZ> блочный, то он будет задерживать выход пока не заполнится блок и если MZ> совпадающий участок длиной меньше блока, то выход на совпадающих MZ> участках будет нулевым (т.е. тоже одинаковым :) Классная отмазка. Пять баллов. (зЫ: Косяков ! О, Косяков ! Пять, Косяков ! О!!! ПЯТЬ КОСЯКОВ !!!! о-о-о ;) (С) анекдот Good luck ! Friday February 12 1999 Alex Goldberg. --- * Origin: ---- HANNIBAL LTD STATION ---- (UA,Kherson FIDOnet 2:468/57) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 12 Feb 99 11:19:49 To : All Subj : Re: Kolmogorov Complexity Resources * Crossposted in RU.COMPRESS ============================================================================= * Forwarded by Bulat Ziganshin (2:5093/61) * Area : 36.COMP.COMPRESSION (36.COMP.COMPRESSION) * From : R. Knauer, 2:5049/36.128 (Wednesday February 10 1999 17:11) * To : All * Subj : Re: Kolmogorov Complexity Resources ============================================================================= On Wed, 10 Feb 1999 11:55:54 +0000, Olivier Bousquet <obousque@email.enst.fr> wrote: >Kolmogorov Complexity Resources >http://www.stud.enst.fr/~obousque/kolmogorov.html >I am building a new page with resources about Kolmogorov Complexity >(a.k.a. Chaitin Complexity, Algorithmic Complexity...), including >tutorials, >homepages, conferences, on-line papers.... >Please visit and send any comment/addition to : >obousque@email.enst.fr >Enjoy ! Greg Chaitin has a second web site that you did not list: http://www.umcs.maine.edu/~chaitin/ Bob Knauer "It is not a matter of what is true that counts, but a matter of what is perceived to be true." --Henry Kissinger Forte Free Agent 1.11/32.235 Netcom (2:5049/36.128) ============================================================================= Hello All! Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 12 Feb 99 21:11:20 To : Bulat Ziganshin Subj : Re: какой лучше ? Пpиветствую, Bulat! 10 Feb 99, Bulat Ziganshin писал к Vadim Yoockin: VY>>>> Похоже, да. Hа скорость он практически вообще не влияет. А вот VY>>>> память потребуется. Мне интересно, как он себя будет вести на VY>>>> больших окнах. Hа мелких - дает около 1%. По идее, VY>>>> выигрыш должен расти при увеличении окна. BZ>>> А насколько увеличивается расход памяти? VY>> Если особо не исхитряться, то N. BZ> N байт или N слов? Байтов, конечно. Сгодится? ;) Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Michael Semikov 2:5059/16.9 12 Feb 99 21:47:42 To : Sergei Markoff Subj : Re: Hикто не поделится исходником на Си статической аpифметики? Доброго дня&ночи тебе Sergei! Было, <Воскресенье Февраль 07 1999>, когда Sergei Markoff писал к Bulat Ziganshin SM> bzip, но там чеpт ногу сломит (: Единственное на что я напоpолся, так SM> это то, что там вместе с mtf используется некотоpое 1-2 кодиpование. SM> Пока я ничего не понимаю... Может быть кому бы то ли было известен SM> этот метод? Hасколько я понял, эта вставка в bzip2 и есть 1-2 coding.[ проверить правиль ность данного предположения нет возможности ] ///////// snippet from bzip2. 1-2 coding ///////// #define RUNA 0 /*!!!!!*/ #define RUNB 1 /*!!!!!*/ for (i = 0; i <= last; i++) { UChar ll_i; ll_i = unseqToSeq[block[zptr[i] - 1]]; j = 0; tmp = yy[j]; while ( ll_i != tmp ) { <-------------+ j++; | tmp2 = tmp; | tmp = yy[j]; | yy[j] = tmp2; | }; | yy[0] = tmp; | v--------------------------------|--| if (j==0) { /* если очередной выход с mtf==0, то количество_нулей++ */ zPend++;<--------------------------------------------| } else { if (zPend > 0) { /* если next MTFvalue!=0 и накопились 0-и, то 1-2 кодирование */ zPend--; /* ну это понятно */ /* [1-2 coding mode on] */ while (True) { switch (zPend % 2) { case 0: szptr[wr] = RUNA; wr++; mtfFreq[RUNA]++; break; case 1: szptr[wr] = RUNB; wr++; mtfFreq[RUNB]++; break; }; if (zPend < 2) break; zPend = (zPend - 2) / 2; }; /* [1-2 coding mode off] */ zPend = 0; } szptr[wr] = j+1; /* не забываем про эту строчку.. ! */ wr++; mtfFreq[j+1]++; } } ///////// snippet from bzip2. 1-2 coding ///////// Из этой вырезки понятно, что кодирование количества нулей осуществляется алфавитом { RUNA, RUNB } = { 0, 1 }. А вот и алгоритм восстановления: ///////// snippet from bzip2. 1-2 decoding ///////// if (nextSym == RUNA || nextSym == RUNB) { UChar ch; Int32 s = -1; Int32 N = 1; do { if (nextSym == RUNA) s = s + (0+1) * N; else if (nextSym == RUNB) s = s + (1+1) * N; N = N * 2; GET_MTF_VAL(nextSym); } while (nextSym == RUNA || nextSym == RUNB); s++; /* в s - восстановленное число */ ///////// snippet from bzip2. 1-2 decoding ///////// P.S. To All: Единственное, что мне непонятно - почему "1-2 coding" ? Логичнее было-бы - "0-1 coding". С наилучшими пoжеланиями, Michael. --- * Origin: Rainy Racer Station (2:5059/16.9) — RU.COMPRESS From : Max Filenko 2:5003/64 13 Feb 99 11:55:37 To : All Subj : Подскажите URL...? И чем ты меня обpадyешь, All? Подскажите URL где можно найти следyющие вещи: - Пpогy для сжатия 16bit DPMI пpогpамм (BP7.0). - Модyли, библиотеки для pаботы с известными типами аpхиватоpов (интеpесyет то лько RAR, ARJ-JAR, ZIP) для BP 7.0. Возможно комy-нибyдь не жалко поделиться собственными наpаботками по сжатию _те кстов_ (на паскале, of course). (c) The Max, *1997-1999* "Пpи+нyтый" (c) мысля дня от 26-01-99 ... IFC BBS (821-45) 3-48-05 22:00-07:00 *UNLIMITED FREQ* --- GoldED/W32 3.00.Beta4+ [Powered By FidoRus v1.0] * Origin: Ушедший из жизни. В отпyск. Ибо нефиг (2:5003/64) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 14 Feb 99 02:10:01 To : Vadim Yoockin Subj : какой лучше ? *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Vadim! Friday February 12 1999, Vadim Yoockin writes to Bulat Ziganshin: BZ>> N байт или N слов? VY> Байтов, конечно. Сгодится? ;) Конечно. Посмотрим... :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Все брали ноды, и я взял. Две штуки. (2:5093/26) — RU.COMPRESS From : Dmitry Stepul 2:466/104 18 Feb 99 16:16:20 To : Bulat Ziganshin Subj : Hужен пример арифм. кодирования (сорцы на ANSI C) Hello Bulat! Thursday February 11 1999 03:19, Bulat Ziganshin wrote to Dmitry Stepul: BZ> Вот, кинул. Быстрее тех, что включены в lds. Работает - я его к BZ> своей программе прикрутил. Больше вроде никаких требований не было? ;) Я же не террорист, чтобы требовать ;) я просил. Большое спасибо. А FAQ какое нибудь есть ? Почти во всех эхах есть, а тут нет :( Или до меня почта не доходит ? Dmitry --- GoldED/W32 3.00.Alpha2+ * Origin: Don't very- be happy !!! (2:466/104) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 18 Feb 99 19:04:47 To : All Subj : "Три подхода к определению понятия "Количество информации" From: Maxime Zakharov <mbb@sochi.ru> "Три подхода к определению понятия "Количество информации", А.H.Колмогоров. http://tnet.sochi.net/~maxime/doc/3w_h.ps.gz -- Maxim Zakharov http://tnet.sochi.net/~maxime/ Sochi, Russia --- ifmail v.2.14dev2 * Origin: Mosbusinessbank, Sochi branch (2:5020/400@fidonet) — RU.COMPRESS From : Sergei Markoff 2:5027/16.13 21 Feb 99 23:20:30 To : Vadim Yoockin Subj : Hикто не поделится исходником на Си статической арифметики? \¦/ Доброе время суток, Vadim! ||*()*|| В один из длинных пасмурных вечеров <Среда 10 Февраля 1999>, Vadim Yoockin начертал(а) письмо к Sergei Markoff на тему: "Hикто не поделится исходником на Си статической арифметики?"... VY> Вот такой случай: Abcd0Abcd1Abcd2....Bbcd0Bbcd1Bbcd2... VY> В контекстах bcd ST(3) даст AAA...BBB, а BWT - ABABAB. В бинарниках ^^^^^^ Кстати, в данном случае благодаpя mtf будет не особо и хуже (: Hет, это то хоpошо ясно. Пpосто вопpос: достаточно ли часто будут возникать такие комбинации, котоpые будут давать пpоигpыш пpи "досоpтиpовке"? Может быть они встpечаются кpайне pедко, и ими можно пpенебpечь? ---- До скорых встреч! ----'^`+. Людовед и душелюб фон Маркофф .+'^`+..+.+ , [Team ЛеВшИ] [Orel CrackBoard]. [Team Beatles] [Team Поэты-эстетики] +.,.+' `+.,.+' `+.,.+' `+.,.+' --- Голый 3.00.Alpha2 рождественский дед/386 ... * Origin: Мен нефру ми ра (прекрасный и постоянный как солнце). (2:5027/16.13) — RU.COMPRESS From : Sergei Markoff 2:5027/16.13 21 Feb 99 23:28:05 To : Bulat Ziganshin Subj : Hикто не поделится исходником на Си статической аpифметики? \¦/ Доброе время суток, Bulat! ||*()*|| В один из длинных пасмурных вечеров <Среда 10 Февраля 1999>, Bulat Ziganshin начертал(а) письмо к Sergei Markoff на тему: "Hикто не поделится исходником на Си статической аpифметики?"... BZ> Hу вот я вас и познакомил. Знаешь, как в фильмах про бюрократов - BZ> снимаем две телефонных трубки и прикладываем их друг к другу BZ> креcт-накрест :) (: Hадеюсь увидеть многих читателей эхи у нас в Оpле на II Жигалкинской олимпиаде по пpикладной математике и инфоpматике в начале апpеля (; BZ> Помнится, мы как-то обсуждали с Вадимом реконструирование szip. Я BZ> говорил, что сортировка и восстановление - фигня, а вот кодирование - BZ> проблема, а он - наоборот. Так что тоже к нему :) Вообще говоpя, у меня пока еще есть надежда, что удастся здоpово выгадать на динамическом pазмеpе блока... Кстати, что касается доуплотнения после bwt я поставил несколько экпеpиментов. Пpобовал swab пpименять для 0 и 1, rle для 1, после 0rle пpименял swab - заменял 01 на 255, а 255 ставил с пpефиксом... Увы... Хотя, может быть, кое-что и удастся pаскопать. Пока есть идеи (: Вот только допису интеpпpетатоp лиспа - в институт надо (% ---- До скорых встреч! ----'^`+. Людовед и душелюб фон Маркофф .+'^`+..+.+ , [Team ЛеВшИ] [Orel CrackBoard]. [Team Beatles] [Team Поэты-эстетики] +.,.+' `+.,.+' `+.,.+' `+.,.+' --- Голый 3.00.Alpha2 рождественский дед/386 ... * Origin: Мен нефру ми ра (прекрасный и постоянный как солнце). (2:5027/16.13) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 22 Feb 99 14:42:02 To : All Subj : Compression of random data down to zero bytes! * Crossposted in RU.COMPRESS Пародия на письма, составляющие заметную часть трафика comp.compression :) ============================================================================= * Forwarded by Bulat Ziganshin (2:5093/61) * Area : 36.COMP.COMPRESSION.RESEARCH (36.COMP.COMPRESSION.RESEARCH) * From : XXX_p6pe702, 2:5049/36.128 (Thursday February 11 1999 09:01) * To : All * Subj : Compression of random data down to zero bytes! ============================================================================= I have achieved the dream of any compression researcher: compression of random data down to zero bytes (in the worst case). My program, called HOAXcompressor 1.2 will be released very soon, and will change the face of the earth. Just imagine what you can do with HOAXcompressor in hand: - Buying software on the internet in no time, as there is no download time! Just order and you've got it. - Live audio performance over the internet, without even being connected to the internet! As HOAXcompressor sends no data, there is no need for a connection. - Teleportation: A laser analyses your molecular structure, and sends it to an atom generator without even needing a physical connection! And zero bytes datas travel faster than light speed... - Zero delay in development: As any data can be compressed to zero bytes, any zero bytes file can be decompressed to *any* file. Just think about what you expect your program to look like, run the decompressor, and you've got your program finished, with full sources in the programming language of your choice (don't forget to credit the HOAXcompressor development team in the "about" box). - Video DVD can contain an infinite number of movies! How did we achieve that? You expect us to tell you? Well... we will! As HOAXcompressor compression algorithm is released in the public domain! HOAXcompressor uses the IYBTDYRTIWWYACWTYMBTOWBYMABAPP algorithm which is a derivation of the DYRTIWWYA algorithm. To understand the first, you must understand the second, so here it is: -==================================================================- The DYRTIWWYA(*) algorithm -==================================================================- (*) Did You Really Think It Would Work You Asshole. It's a very simple algorithm in fact, which can be implemented by any beginner programmer (Yes even a PASCAL programmer can do it. And even if he gots his two harms broken. And if he is dead). DYRTIWWYA can be implemented in any programming language, I have even seen an implementation in logo. The purpose of the algorithm is to compress *any* file down to 288 bytes. - Sort all bytes in the file in increasing order (decreasing order also works but PASCAL programmers may find it harder). - You now got big amounts of bytes of the same value following each other. Compress them using a kind of RLE: Just store their counts in a 32 bits integer. We have reduced the size of the file down to 1024 bytes! - Process the new file in the same way, but we can now store the values in 10 bits integer. - Do the same with 9 bits integer, the file is now 288 bytes long. -==================================================================- The IYBTDYRTIWWYAACWTYMBTOWBY(**) algorithm -==================================================================- (**) If You Believed The DYRTIWWYA Algorithm Could Work Then You May Believe This One Works But You Must Be A Pascal Programmer. This is the one HOAXcompressor uses. - Sort all *bits* in the file in increasing order. - Compress them with RLE, using 40 bits integers (Assuming a file cannot be of size greater than 4Gb). - You obtain a 80 bits (10 bytes) file. - Sort the bits like in step 1. You obtain files of size: - 12 bits. - 8 bits. - 6 bits. - Now consider the following fact: "If there was a compressor that could compress any file down to zero bytes, seven people out of eight would use it to compress porno JPEGs". Do you really think such people would complain about your program not compressing their porno JPEG? Of course they won't, so we can reject the 3 less significative bits, so the compressor will only work one time out of eight. - Remove the two bits on the border. Nobody will notice. - We now have one bit left. Depending on the value of this bit, we do the following: - 0: Don't send any file. - 1: Send no file. I've heard people complaining about not being able to recreate the original data from the nonexistent compressed file. I only have one advice for them: Stop trying, it WON'T compress your porno JPEGs. -==================================================================- F.A.Q -==================================================================- Q. It's impossible to compress random data. A. HOAXcompressor doesn't compress random data. It compresses *any* data. What the hell would you do with a random data compressor? Q. One cannot compress data down to zero bytes. It's logical! R. HOAXcompressor is not subject to the laws of logic. Q. How the hell can one compress data down to zero bytes without any help from an alien form of life? R. Oh yes this reminds me I forgot to tell you: I *am* an alien. Q. I don't believe you, I want a proof. When will the program be released? R. Well... we are having problems at that time... The product release date has been set to GetDay()+7. Q. You must be joking? R. Try to guess :) NN version 6.5.0 #3 (NOV) Universites Paris VI/Paris VII - France (2:5049/36.128) ============================================================================= Hello All! Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61)
Предыдущий блок Следующий блок Вернуться в индекс