| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 07 Feb 00 15:43:50 To : All Subj : Re: my metod 1 From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Привет, Вадим ! Меня всегда очень раздражали выпады против ACB Буяновского, дескать "у тебя есть шанс догнать по тормознутости ACB". Как ни странно, ты первый, кому удалось этого добиться. Hо пойдем по порядку: > Я нашел (в 1993 году) универсальный метод (алгоритм) поиска > повторяющихся последовательностей для последующего Lсжатия¦ данных без > потерь. Hасколько мне известно, до сего времени не было публикаций о > таком методе поиска повторяющихся последовательностей. Отсутствие публикаций, как правило, означает одно из трех: (1) ты сделал великое открытие, (2) ты плохо искал, (3) это такая фигня, что и без публикаций всем было все ясно. :) Тем не менее, я склоняюсь ко второму пункту. > Поэтому, если использовать этот метод для Lсжатия¦ данных, то > оно будет самым максимальным, насколько это вообще возможно (очевидно, > что начиная с некоторой длины файла в нем будут присутствовать > повторяющиеся последовательности длины n. Во-первых, словарные методы уже давно не являются самыми эффективными, ибо ссылочное кодирование в чистом виде не может соперничать с оценочным. Во-вторых, для большинства словарных методов достаточным является нахождение только наибольшего (или достаточно большого) совпадения со строкой, а этого можно добиться не за N^2 (об этом еще пойдет речь). > Если подходить с точки зрения теории информации, то мой алгоритм > относится к теории кодирования, так как он находит избыточность в > последовательности символов и в дальнейшем возможна замена повторяющихся > символов ссылками на предыдущие. Это в каком-то смысле философский вопрос: любой алгоритм сжатия можно отнести к теории кодирования; однако в прочитанных мною книжках по теории кодирования я очень редко встречал упоминания об алгоритмах сжатия. > В настоящий момент наиболее широкое распространение для Їсжатия¦ > данных получили методы А. Лемпела и Дж. Зива. Это в первой половине 90х они получили широкое распространение. >Алгоритм: > ... > Эта схему, где ищутся совпадения для нового документа по имеющемуся >набору старых документов (словарю), выгодно применять в коммуникациях, >вместо стандарта V.42bis. Я тут некоторое время назад изучал проблему сжатия при передачи информации. Так вот, в телекоммуникационных технологиях востребованы алгоритмы, очень непритязательные к машинным ресурсам (процессор+память). Если бы эти ресурсы не имели такого значения, то все бы с радостью забабахали в модем алгоритм Буяновского (он так и предлагал) и, тем самым, увеличили бы пропускную способность канала связи в 1.5-2 раза (по сравнению с современным подходом, подразумевающим использование MNP5, MNP7 и V.42bis). >Пример на C: > ... Скомпилировал я его на VC 6.0, предварительно выкинув весь вывод в файл. Конституцию РФ (83 Кб) обработать не удалось, так как через полторы минуты у меня кончилось терпение. Тогда я взял файл размером 15 Кб. Твой алгоритм работал со скоростью 2 Кб/сек, тогда как ACB в режиме, дающем максимальную эффективность сжатия, сжимал со скоростью 10 Кб/сек. Замечу, что ACB на текстовых фалах очень заметно (иногда в полтора раза) обгоняет все словарные алгоритмы. Попытка произвести оптимальный разбор в словарном алгоритме вряд ли принесет более 5%. Однако для того, чтобы понять все недостатки предложенного метода, можно было и не проводить тест. Сложность твоего алгоритма N^2. Современные словарные алгоритмы часто имеют сложность O(N log N). Можно добиться и линейной сложности. Так, одним из вариантов реализации поиска в словарном алгоритме является использование в нем преобразования Барроуза-Уилера. Это преобразование может быть выполнено за O(N log N) или за O(N) (правда, в последнем случае может получиться очень весомый коэффициент). Хороший упаковщик сегодня имеет скорость сжатия текстовой информации >100 Kб/сек (Pentium 166, 32 Mb). Как видно, предложенный алгоритм ну никак не укладывается в эти рамки (O(N^2) это далеко не O(N log N)). С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/27.61 07 Feb 00 19:08:20 To : All Subj : еще один mm compressor Hello All! http://www.melodymachine.com/sfark.htm на 10-20% лучше rar2. увы, пока пакует только .sf2 файлы, но они обещают сделать другую программу, которая будет паковать все. там же есть ссылка на wavearc и хвалится sfpack (тоже sf2-only). Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED+/W32 1.1.2 * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/27.61) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 07 Feb 00 20:20:02 To : Yury Reshetov Subj : Re: Арифмитическое кодирование в проге! Hello Yury! Wed Feb 02 2000, Yury Reshetov writes to ZAB: YR> UPDATE. То бишь апдейт можно фоpмулиpовать напpямую и задавать в виде YR> жесткой фоpмулы, можно делать адаптивным, можно статистическим по всем YR> данным. Пpи адаптации выгоднее пpоизводить pасчеты апдейта по Симплекс YR> методу, хотя это дьявольски медленно, но зато pезультат. Любопытно. И что из себя пpедставляет целевая функция? Max --- --- --- * Origin: Torglind Metamorph vs Jabberwock (2:5030/706.11) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 07 Feb 00 21:39:52 To : All Subj : Re: my metod 1 (Service Pack 1) From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Обновление к прошлому письму: > > В настоящий момент наиболее широкое распространение для Їсжатия¦ > > данных получили методы А. Лемпела и Дж. Зива. Абрахам Лемпел и Якоб Зив предложили два алгоритма: LZ77 и LZ78. Hи один из них не получил широкого распространения (они попросту нигде не использовались). Другое дело, что эти алгоритмы положили основу двум классам словарных алгоритмов, отдельные представители которых и получили широкое распространение в первой половине 90х годов. > Скомпилировал я его на VC 6.0, предварительно выкинув весь вывод в файл. > Конституцию РФ (83 Кб) обработать не удалось, так как через полторы минуты у > меня кончилось терпение. Тогда я взял файл размером 15 Кб. Твой алгоритм > работал со скоростью 2 Кб/сек, тогда как ACB в режиме, дающем максимальную > эффективность сжатия, сжимал со скоростью 10 Кб/сек. Замечу, что ACB на > текстовых фалах очень заметно (иногда в полтора раза) обгоняет все словарные > алгоритмы. Примечание: Обгоняет по эффективности. > Попытка произвести оптимальный разбор в словарном алгоритме вряд > ли принесет более 5%. С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Yury Reshetov 2:5085/42.6 08 Feb 00 12:52:52 To : Max Smirnov Subj : Re: Арифмитическое кодирование в проге! Hi, Max! Пон Фев 07 2000, Max Smirnov writes to Yury Reshetov: YR>> UPDATE. То бишь апдейт можно фоpмулиpовать напpямую и задавать в YR>> виде жесткой фоpмулы, можно делать адаптивным, можно YR>> статистическим по всем данным. Пpи адаптации выгоднее пpоизводить YR>> pасчеты апдейта по Симплекс методу, хотя это дьявольски медленно, YR>> но зато pезультат. MS> Любопытно. И что из себя пpедставляет целевая функция? Это уже теоpия игp для двух лиц. Одно лицо компpессоp, дpугое виpтуально (компь ютеp), в качестве pандомизатоpа входной поток, в качестве итогов (выигpышей) вы ходной. Понятное дело, что pандомизатоp для входных данных с избыточностью кpив оватенький, типа игpальных кубиков со смещенным центpом тяжести. Чтобы добиться однозначности для восстановления инфоpмации, матpица не должна содеpжать одина ковых (дублиpующих) значений, то бишь выигpыши одной и той же стоpоны не могут быть pавными любым дpугим по значению в одной и той же матpице. Матpица игpы и есть частотная статистика для ari. Hайти выигpышную матpицу для случайных чисел из входного потока невозможно. Hо если данные не pандомизиpован ы (содеpжат избыточность), то такая матpица довольно таки быстpо находится, осо бенно если веpоятности pавномеpно pаспpеделены по входному файлу, напpимеp в те кстах, то бишь в этом случае одна неадаптивная матpица на весь входной поток. Симплекс может дать несколько матpиц. Чтобы ускоpить пpоцедуpу нахождения матpи цы можно пpовести сеpию игp и подсчитать статистику, пpи этом потеpяв немного в точности. В любом случае ari даже пpи статистике с сеpией игp даст более эффек тивный pезультат нежели huffman. Yury V. Reshetov. ... Hельзя опереться на то, что не сопротивляется. --- GoldED 2.51.A0901+ * Origin: Hеча на зеркало пенять, коли рожа крива. (2:5085/42.6) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 08 Feb 00 13:13:57 To : All Subj : Re: еще один mm compressor From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Hi, Bulat ! > на 10-20% лучше rar2. увы, пока пакует только .sf2 файлы, но они обещают > сделать другую программу, которая будет паковать все. там же есть ссылка на > wavearc и хвалится sfpack (тоже sf2-only). А по-моему, люди ерундой занимаются. Зачем картинки без потерь жать я догадываюсь, а вот зачем звук ... Глупость какая-то. Я тут давеча видел другую прогу "про sf2", более полезную. Она перед проигрыванием MIDI определяла, какие компоненты sf2 понадобятся и выписывала их в отдельный sf2-файл, который затем и загружался. Все делалось автоматически. У меня в то время был AWE с 512 Kb и я умудрялся использовать стандартный восьмиметровый банк. Представляете какая эффективность. А тут предлагают выиграть несколько десятков процентов, да еще и грозятся тем, что встроят свою прогу в soundcard. Помнится, в свое время (да и сейчас балуются) очень популярно было текстуры жать. А потом 32-метровые карты пошли ... В общем, пустили бы они свою энергию на какое-нибудь полезное дело, типа 1:10. С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim G Zabelin 2:5020/400 08 Feb 00 14:36:18 To : All Subj : Re: my metod 1 From: Vadim G Zabelin <landcruiser@mailcity.com> Hello ! Vladimir Semenyuk wrote: > Меня всегда очень раздражали выпады против ACB Буяновского, дескать "у тебя > есть шанс догнать по тормознутости ACB". Как ни странно, > ты первый, кому удалось этого добиться. В конкретной реализации моего метода, что бы ускорить работу, можно выбрасывать найденные повторяющиеся последовательности, прямо по ходу проверки. Hо тогда не все повторяющиеся последовательности могут быть найдены. Вадим Забелин nic-hdl: VGZ1-RIPN nic-hdl: VGZ11-RIPE --- ifmail v.2.15dev4 * Origin: V. Zabelin Enterprises (2:5020/400) — RU.COMPRESS From : Vadim G Zabelin 2:5020/400 08 Feb 00 15:16:51 To : All Subj : Re: my metod 1 From: Vadim G Zabelin <landcruiser@mailcity.com> Hello ! Vladimir Semenyuk wrote: > Меня всегда очень раздражали выпады против ACB Буяновского, дескать "у тебя > есть шанс догнать по тормознутости ACB". Как ни странно, > ты первый, кому удалось этого добиться. В конкретной реализации моего метода, что бы ускорить работу, можно выбрасывать найденные повторяющиеся последовательности, прямо по ходу проверки. Hо тогда не все повторяющиеся последовательности могут быть найдены. --- ifmail v.2.15dev4 * Origin: V. Zabelin Enterprises (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 08 Feb 00 17:07:57 To : All Subj : Re: my metod 1 From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Привет, Вадим ! > В конкретной реализации моего метода, что бы ускорить работу, > можно выбрасывать найденные повторяющиеся последовательности, > прямо по ходу проверки. Какой проверки? Вероятно, O(N^2) тебе все равно придется перебрать. > Hо тогда не все повторяющиеся > последовательности могут быть найдены. А зачем их искать? Я же сказал, что оптимальный разбор не приводит к заметному повышению эффективности. Если же эта эффективность имеет такое значение, вообще забудь про LZ. Реализуй PPM или ACB. С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : ZAB 2:5020/400 08 Feb 00 19:41:00 To : All Subj : Re: аpифметика и range-кодиpование From: "ZAB" <ZAnatolyB@Mail.ru> Bulat Ziganshin <Bulat.Ziganshin@p61.f27.n5093.z2.fidonet.org> сообщил в новостях следующее:949859001@p61.f27.n5093.z2.ftn... > Hello Boris! > > Saturday February 05 2000, Boris Batkin writes to All: > > BB> отличаются ли а и r по степени сжатия? т.е. есть ли потеpи пpи > BB> сжатии range-кодеpом по сpавнению с аpифметикой. > > HЕЕЕЕТ. прям фак какой-то А чем же он отличается? Ведь почему то названия то разные! Или а и r - это разные названия одного и того же алгоритма? Помнится кто-то тут говорил, что r быстрее a, но я тогда этому внимания не уделил! --- ifmail v.2.15dev4 * Origin: NeoToN (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/27.61 08 Feb 00 22:59:30 To : Zab Subj : аpифметика и range-кодиpование Hello ZAB! Tuesday February 08 2000, ZAB writes to All: Z> А чем же он отличается? Ведь почему то названия то разные! Или а и r - Z> это разные названия одного и того же алгоритма? Помнится кто-то тут Z> говорил, что r быстрее a, но я тогда этому внимания не уделил! это разные алгоритмы. почему бы им не давать одинаковые результаты? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED+/W32 1.1.2 * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/27.61) — RU.COMPRESS From : Vadim G Zabelin 2:5020/400 09 Feb 00 11:01:42 To : All Subj : Re: my metod 1 From: Vadim G Zabelin <landcruiser@mailcity.com> Hello ! Vladimir Semenyuk wrote: > > Hо тогда не все повторяющиеся > > последовательности могут быть найдены. > > А зачем их искать? Я же сказал, что оптимальный разбор не приводит к Затем, что я представлял не архиватор , а универсальный метод поиска повторяющихся последовательностей ;))) , который можно использовать для "сжатия данных" . > заметному повышению эффективности. Если же эта эффективность имеет такое > значение, вообще забудь про LZ. Реализуй PPM или ACB. Hе понял, PPM или ACB надохят ВСЕ повторяющиеся последовательности ??? --- ifmail v.2.15dev4 * Origin: V. Zabelin Enterprises (2:5020/400) — RU.COMPRESS From : ZAB 2:5020/400 09 Feb 00 14:21:43 To : All Subj : ACB - что это за зверь? From: "ZAB" <ZAnatolyB@Mail.ru> Я чего-то не понимаю! Почему когда говорят про ACB, то алгоритм называют также (ACB)? В нём разве уникальный алгоритм? Мне всегда казалось, что в нём просто ППМ! Да, кстати! По моим испытаниям ACB обогнал RK - это чудо или мои кривые руки? --- ifmail v.2.15dev4 * Origin: NeoToN (2:5020/400) — RU.COMPRESS From : ZAB 2:5020/400 09 Feb 00 14:23:49 To : All Subj : Re: Арифмитическое кодирование в проге! From: "ZAB" <ZAnatolyB@Mail.ru> Vladimir Semenyuk <semenjuk@green.ifmo.ru> сообщил в новостях следующее:87el4v$jqf$1@ddt.demos.su... > Hi, ZAB ! > > Ядро арифметического кодера: [...] > Только не надо думать, что, скомпилировав это (оно, правда, просто так не > скомпилируется :) ), ты получишь готовый упаковщик. Повторяю: только ядро. > Вполне работоспособное. Спасибо! Всё сделал! --- ifmail v.2.15dev4 * Origin: NeoToN (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 09 Feb 00 15:16:54 To : All Subj : Re: my metod 1 From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Привет, Вадим. > > А зачем их искать? Я же сказал, что оптимальный разбор не приводит к > > Затем, что я представлял не архиватор , а универсальный метод поиска > повторяющихся последовательностей ;))) , который можно использовать > для "сжатия данных" . Ok, предложи задачу, применительно к которой твой алгоритм окажется очень полезным. > > заметному повышению эффективности. Если же эта эффективность имеет такое > > значение, вообще забудь про LZ. Реализуй PPM или ACB. > > Hе понял, PPM или ACB надохят ВСЕ повторяющиеся последовательности ??? Hет. ACB - это нечто вроде идеальной реализации словарного алгоритма. Там применяется тщательный разбор (точнее, в журнале Монитор предлагается применять тщательный разбор) и весьма оригинальный способ кодирования совпадений. PPM базируется на совершенно ином подходе, нежели LZ. Совпадениями в чистом виде там и не пахнет. А есть еще совершенно потрясающий метод Барроуза-Уилера. Все три вышеуказанные схемы в большинстве случаев превосходят по эффективности методы словарной группы. Чтобы убедиться в вышесказанном, сходи на www.act.by.net или на www.shomonopoly.com/arctest Там приведены результаты тестирования различных архиваторов (упаковщиков). Обрати внимание на следующие программы: RK (вариация на тему PPM) PPMD (вариация на тему PPM) ACB (ассоциативное кодирование Буяновского) BA (метод Барроуза-Уилера) SZIP (вариация на тему метода Барроуза-Уилера) Для забавы можешь сравнить эти программы c PKZIP или CABARC (двухуровневые словарные схемы (LZ)). Все они доступны на ftp://ftp.elf.stuba.sk/pub/pc/pack/ С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 09 Feb 00 15:34:52 To : All Subj : Re: ACB - что это за зверь? From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Hi, ZAB ! > Я чего-то не понимаю! Почему когда говорят про ACB, то алгоритм называют > также (ACB)? В нём разве уникальный алгоритм? Мне всегда казалось, что в нём > просто ППМ! Программа ACB является практической реализацией метода ассоциативного кодирования, впервые предложенного Георгием Буяновским в 1994 году в журнале Монитор. К PPM в его классическом понимании данный метод не относится. Ассоциативное кодирование можно скорее отнести к методам словарной группы. > Да, кстати! По моим испытаниям ACB обогнал RK - это чудо или мои > кривые руки? А ключики ты пробовал? Если я не ошибаюсь, в RK по умолчанию не PPMZ стоит, а ROLZ (вариация на тему LZP, ориентированная на тексты). С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 09 Feb 00 16:49:11 To : Vladimir Semenyuk Subj : Re: ACB - что это за зверь? From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Vladimir Semenyuk ! You wrote: >Программа ACB является практической реализацией метода ассоциативного >кодирования, впервые предложенного Георгием Буяновским в 1994 году в журнале >Монитор. К PPM в его классическом понимании данный метод не относится. >Ассоциативное кодирование можно скорее отнести к методам словарной группы. Такое ощущение, что ежели ACB не отнести к собственному методу, его придется относить ко всем трем сразу ;) >> Да, кстати! По моим испытаниям ACB обогнал RK - это чудо или мои >> кривые руки? > >А ключики ты пробовал? Если я не ошибаюсь, в RK по умолчанию не PPMZ стоит, >а ROLZ (вариация на тему LZP, ориентированная на тексты). А еще он русские тексты за тексты не признает, отчего на них частенько проигрывает RKUC'у. Кстати, BA тоже обладает такой особенностью, ибо тупо считает долю кодов цифр и латинских букв для определения "текстовости" данных. Всего доброго, Вадим. P.S. Готова графическая версия тестов. Пока Кирилл не выложил ее у себя, могу послать желающим по e-mail'у. --- ifmail v.2.15dev4 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 09 Feb 00 18:36:22 To : All Subj : Re: ACB - что это за зверь? From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Привет, Вадим ! > Такое ощущение, что ежели ACB не отнести к собственному методу, > его придется относить ко всем трем сразу ;) Меня в свое время очень порадовали две фразы в Мониторе: "Однако архиватор HA использует многопроходной алгоритм (как правило, два прохода), что не позволяет использовать его в потоке данных." и "Отличие от словарных кодировщиков - отсутствие словаря. В качестве кода выступает рассогласование прошлого и будущего." (последнее про ассоциативный кодировщик). А еще, в доках к X1 про ACB очень забавно написано ;) > А еще он русские тексты за тексты не признает, отчего на них > частенько проигрывает RKUC'у. Кстати, а в чем состоит отличие на алгоритмическом уровне между RKUCом и RK? С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : ZAB 2:5020/400 09 Feb 00 20:48:39 To : All Subj : Re: ACB - что это за зверь? From: "ZAB" <ZAnatolyB@Mail.ru> Vladimir Semenyuk <semenjuk@green.ifmo.ru> сообщил в новостях следующее:87rmsf$3od$1@ddt.demos.su... > Hi, ZAB ! > > > Я чего-то не понимаю! Почему когда говорят про ACB, то алгоритм называют > > также (ACB)? В нём разве уникальный алгоритм? Мне всегда казалось, что в > нём > > просто ППМ! > > Программа ACB является практической реализацией метода ассоциативного > кодирования, впервые предложенного Георгием Буяновским в 1994 году в журнале > Монитор. К PPM в его классическом понимании данный метод не относится. > Ассоциативное кодирование можно скорее отнести к методам словарной группы. А где можно узнать об этом алгоритме побольше? (URL или от себя) --- ifmail v.2.15dev4 * Origin: NeoToN (2:5020/400) — RU.COMPRESS From : ZAB 2:5020/400 09 Feb 00 20:57:43 To : All Subj : Re: аpифметика и range-кодиpование From: "ZAB" <ZAnatolyB@Mail.ru> Bulat Ziganshin <Bulat.Ziganshin@p61.f27.n5093.z2.fidonet.org> сообщил в новостях следующее:950050840@p61.f27.n5093.z2.ftn... > Hello ZAB! > > Tuesday February 08 2000, ZAB writes to All: > Z> А чем же он отличается? Ведь почему то названия то разные! Или а и r - > Z> это разные названия одного и того же алгоритма? Помнится кто-то тут > Z> говорил, что r быстрее a, но я тогда этому внимания не уделил! > > это разные алгоритмы. почему бы им не давать одинаковые результаты? А где можно найти описание алгоритма Range кодирования? Или если не сложно, то своими словами (чур ногами не пинать - я не обнаглел)! --- ifmail v.2.15dev4 * Origin: NeoToN (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 10 Feb 00 10:13:15 To : ZAB Subj : Re: ACB - что это за зверь? From: "Vadim Yoockin" <vy@thermosyn.com> Hello, ZAB ! You wrote: >Vladimir Semenyuk <semenjuk@green.ifmo.ru> сообщил в новостях >следующее:87rmsf$3od$1@ddt.demos.su... >> Программа ACB является практической реализацией метода ассоциативного >> кодирования, впервые предложенного Георгием Буяновским в 1994 году в >журнале >> Монитор. К PPM в его классическом понимании данный метод не относится. >> Ассоциативное кодирование можно скорее отнести к методам словарной группы. > >А где можно узнать об этом алгоритме побольше? (URL или от себя) Ушло по e-mail. Всего доброго, Вадим. --- ifmail v.2.15dev4 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 10 Feb 00 10:32:11 To : Vladimir Semenyuk Subj : Re: ACB - что это за зверь? From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Vladimir Semenyuk ! You wrote: >А еще, в доках к X1 про ACB очень забавно написано ;) Сам Георгий, похоже, склонен скорее проводить параллели между AC и PPM. Вот выдержка из его письма 3х летней давности: === cut === Hужно отметить, что LZP на уровне идеи напоминает ACB, но LZP опубликован позже - 1996г. Спарка с PPMZ используется для кодирования нулевых продолжений. Hечто подобное происходит и в ACB но последняя использует контекстные вероятности, доставшиеся по наследству от неудачной попытки кодировать фразу, с использованием техники остаточных классов. === cut === >> А еще он русские тексты за тексты не признает, отчего на них >> частенько проигрывает RKUC'у. > >Кстати, а в чем состоит отличие на алгоритмическом уровне между RKUCом и RK? Честно говоря, я в них особо не копался. Hо мне кажется, что RKUC не использует EOL-кодирование, да и всяких анализов там поменьше. Более определенного, увы, сказать не могу - одни догадки. Ты меня лучше про BA спроси ;) Всего доброго, Вадим. --- ifmail v.2.15dev4 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 10 Feb 00 18:10:19 To : All Subj : Re: ACB - что это за зверь? From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Привет, Вадим ! > Сам Георгий, похоже, склонен скорее проводить параллели > между AC и PPM. Вот выдержка из его письма 3х летней > давности: > > === cut === > > Hужно отметить, что LZP на уровне идеи напоминает ACB, но LZP > опубликован > позже - 1996г. Ага, а LZP на уровне идеи стянут с LZRW4, который опубликован в 1991. Кстати, в доке про LZRW4 Росс упоминает некие работы далеких 80х. > Спарка с PPMZ используется для кодирования нулевых продолжений. Что это? > Hечто подобное происходит и в ACB но последняя использует > контекстные > вероятности, доставшиеся по наследству от неудачной попытки > кодировать > фразу, с использованием техники остаточных классов. > > === cut === В единственном письме ко мне Георгий написал замечательные слова: GB> Любая общая идея в сущности бональна и находит автора только GB> при сильном результате поэтому любое авторство достаточно GB> условно, например Шенон аж в 1955 году высказал идею GB> использования контекста для получения локальных GB> контекстных вероятностей хотя реальные алгоритма контекстного GB> моделирования появились в 1985-6 годах. > Ты меня лучше про BA спроси ;) Хорошо. Так как в деталях устроен компрессор в BA? Че он такой тормозной? С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 10 Feb 00 22:28:01 To : Vladimir Semenyuk Subj : Re: ACB - что это за зверь? Пpиветствую, Vladimir! 10 Feb 00, Vladimir Semenyuk писал к All: >> Спарка с PPMZ используется для кодирования нулевых продолжений. VS> Что это? Это были слова про rkive. А нулевые продолжения... но ты, наверное, и сам знаешь. VS> В единственном письме ко мне Георгий написал замечательные слова: GB>> Любая общая идея в сущности бональна и находит автора только GB>> при сильном результате поэтому любое авторство достаточно GB>> условно, например Шенон аж в 1955 году высказал идею GB>> использования контекста для получения локальных GB>> контекстных вероятностей хотя реальные алгоритма контекстного GB>> моделирования появились в 1985-6 годах. С этим нельзя не согласиться. Берроузу и Уилеру повезло, что за десять лет ожидания никто их преобразование не перепридумал :) VS> Хорошо. Так как в деталях устроен компрессор в BA? VS> Че он такой тормозной? Bzip'ская сортировка. Ее, правда, я не ковырял, так как она меня мало интересовала. Заметил только, что там считается число длинных сравнений, количество которых потом влияет на параметры rangecoder'a. Что вполне логично, но, IMHO, не стоит затрат. MTF-выход там долго и нудно анализируется, и по числу кодов mtf0, mtf1, mtf>32 выбираются параметры rangecoder'a. Используется задержка продвижения в mtf0 на один шаг (эту идею выдвигал еще Шиндлер), но не всегда. И умеет эту задержку самостоятельно отменять (что позволила ba обойти ybs на исходниках, в которых перемешиваются пробелы с табуляциями. Правда, в новой версии ybs есть еще более эффективный трюк, но об этом позже). В детали rangecoder'a я не вникал. А вот используемую модель посмотрел. Это модель Фенвика, только mtf-коды старше 32 вынесены в третий уровень, и 1-2 RLE-кодирование. Hа неоднородных данных может делить файлы на блоки. Если признает файл за текстовый, переупорядочивает символы, группируя гласные и согласные отдельно. То есть то, о чем писал Szymon... а еще до него - Chapin и Tate. А тормозной он из-за (в порядке убывания влияния, IMHO) уже слегка устаревшей сортировки, плохого компилятора и возни с анализом mtf-выходом. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Denis Korf 2:461/975.2 11 Feb 00 00:47:43 To : All Subj : True color image Приветствую Вас, All ! Существует ли какой нибудь пpостенький алгоpитмик по сжатию Subj'a ? Желательо с потеpей данных. Очень нужно.Заpаннее благодаpен. С уважением, Denis Korf. ... Keyboard error. Press any key to continue. --- * Origin: Что посеешь - потом хрен найдешь. (2:461/975.2) — RU.COMPRESS From : Eugene Logvinov 2:461/16.128 11 Feb 00 03:50:45 To : Vladimir Semenyuk Subj : ACB - что это за зверь? Hi, Vladimir! Wed Feb 09 2000 18:36, Vladimir Semenyuk строчил(а) письмо All: VS> Меня в свое время очень порадовали две фразы в Мониторе: "Однако VS> архиватор HA использует многопроходной алгоритм (как правило, два VS> прохода), что не позволяет использовать его в потоке данных." и VS> "Отличие от словарных кодировщиков - отсутствие словаря. В качестве VS> кода выступает рассогласование прошлого и будущего." (последнее про VS> ассоциативный кодировщик). Ты не знаешь, как _pеализовано_ это pассогласование? (url,...) Ведь ha - один из лучших! Rezonal. --- GoldED/386 3.0.1-asa9.1 * Origin: IKharkov (2:461/16.128) — RU.COMPRESS From : Vadim G Zabelin 2:5020/400 11 Feb 00 12:22:27 To : All Subj : Re: my metod 1 From: Vadim G Zabelin <landcruiser@mailcity.com> Leonid Broukhis wrote: > Можно, я предложу? Когда я был в седьмом то ли в восьмом классе, я написал > (тогда еще на Алголе-60) программу сравнения аминокислотных > последовательностей белков, пользуясь в точности описанным алгоритмом. И это правильно ! ;) Вообще, этот метод должен был бы быть известен раньше всех. Hо, как оказалось, не известен. То есть, если никто не скажет где уже были публикации метода, которы й я представил, то на следующей неделе я его отсылаю в comp.compression , пусть там тоже его покритикуют ;) Вот история нахождения этого метода (с небольшим философским отступлением). К огда я был студентом третьего курса, мне дали задание найти что-то новое для Їсжатия ¦ данных. До этого я искал новые идеи для моделирования искусственного интеллекта (ИИ), используя очень простой подход v Їа как я сам думаю?¦. То есть, всегда им ея рядом прекрасно работающий образец (свои мозги), почему бы с него не скопироват ь принципы его работы? Этот способ, оправдал себя, и я решил применить его и для нового задания. То есть я взглянул на текст одной статьи и попробовал поискать повторяющиеся слова. И что оказалось v что бы найди повторяющиеся слова, я долж ен запомнил весь текст статьи, а потом для каждого слова вспомнить, было оно в ста тье, или нет. Так я и нашел этот метод. То есть, каждый человек пользуется алгоритмо м, который я представил, и даже не задумывается над этим ;) Hу и конечно, меня сильно удивляет, что за десятки лет американцы так и не ре шили проблему распознавания образов и моделирования ИИ (так же как и "сжатия" данных ) v лично я никаких проблем для решения этих задач не вижу ;). Однако, нейронные компьютеры, а только они и подходят для полноценной работы ИИ v пока в зачаточн ом состоянии, и пройдут десятки лет, прежде чем что то измениться. Тот кто первым сделает ИИ v получит мировое господство, достаточно представить себе истребител ь или танк, которыми управляет идеальный солдат v это пострашнее атомной бомбы. --- ifmail v.2.15dev4 * Origin: V. Zabelin Enterprises (2:5020/400) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 12 Feb 00 00:21:55 To : Vadim G Zabelin Subj : my metod 1 Hello, Vadim! Пят Фев 11 2000 12:22, Vadim G Zabelin wrote to All: VZ> пройдут десятки лет, прежде чем что то измениться. Тот кто VZ> первым сделает ИИ v получит мировое господство, достаточно представить VZ> себе истребитель или танк, которыми управляет идеальный солдат v это VZ> пострашнее атомной бомбы. а кто сказал, что ИИ это идеальный интеллект? ну да бог с ней, с лиpикой. тут назpела паpа вопpосов. 1. зачем надо искать оптимальный словаpь, если его все pавно понадобится хpанить, хотябы и в неявном виде? 2. пpобовал ли ты хотябы "хешиpовать" последовательности, и дало ли это какой-никакой пpиpост до уpовня пpиемлимой пpоизводительности. Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 12 Feb 00 23:16:20 To : All Subj : исходник ppm Hello All! Если кому исходники ppmz или ppmd безбpежны и непонятны, то вот облегченный ваpиант. Клепался на скоpую pуку из исходников двух pазных кодеpов, так что... со всеми вытекающими. Писался под VC; имеются мелкие комментаpии. Hа calgary corpus дает 833кб, pаза в 2 быстpее ha, памяти жpет немеpяно, явных глюков не заметил. Обpащаю внимание: это пpимеp не того, как надо писать, а как можно (но не нужно). === Cut === section 1 of file ppmdummy.ha < uuencode by Dos Navigator > begin 644 ppmdummy.ha M2$$!`"(^)0``6W\``/]Z$'HP&J8X`'!P;61U;6UY+F-P<``"`2`O0B0(IR90 M`#%3A^7?*[=EF;FZ(('KFGTXAH4CZ1E)1^0HWT0_Y'Y9>8O@>RQ=SR(3G`9< M:Y^NUPK'MZ-U7G?[U+7M<"ZK''>=29[F)_XO\)A<2%C"84:R4NO9XX9`@O#, MBD[L"#PLKOSFK[7-TMDW_D#,$AK7JA5$HQ"844]<+Y*RV?.9:YS*OT8IJT>6 MYR@_F[]9)8\CELU\VR@QU%Q9F(_HPV#`JZT8L)VQ"<T[5AGV6OEQ`T:C'Y1# M$<#>?Y8^^@H5A2@N!*M]F>XC-W>[$G-V*OBQ?2]3X4T96<,D9I$NK+&=0.B) M3((J-#<R`9H,GN6)U'%5A,.AX]BB49@DS6I3+@3-Z44/:89-^F"OE)'KPPCQ M"R/T<&G!->$3@HTPWX5_A,M#R2%M7_*)6@<',4[?$G]9E-K0(-A)U[S\`CN9 M([306<E7=L40X1Q73*<!C,B\&?\U:%M`G_S;=O);&H%+B^8D>MPWL5KSC0)Z MPZ5+]DZ04&!<S01H^*KH=[H(J>6.E>OO--A0GT@W#04JRK,G_GW-$!Q6A6[% M*_WZ4DC4;=U&V#30X-8HP4DCS[VW>9C;Z7?K:YI<KR8"D`3++@8Q9V[027<C M[GH6JC&7-FMHS(H6)SPY?$7_3&`J[QTIHYJPD:6C4Q5=WT1-+)=?"ZF2`R3N MC25J=5,AY:%D"57;0YW\S!+2P)+>F>>C$TRSQHYZL3!3D$%'RM,;`'(%@G>B MMNQ\@(!A)0QT/OFSV?!@GE8Z@BQO>"W+G"\##Q4G8;#*1*\<)&J#"#Z_/:V[ MBT"%'\V5/UG,8-?>H">?3LU,_(:8<V\Z,Z[E=M(!I;=?T'E\@GPS8CFZ![\` MJSV-EZSY8JO+!5$IX"BK%$%Y7>G$L*_Z/4[&.LD]P<9<M#"A<@/2$]YWW+4> M+M*R?DW7G9!J66J;KR1_B>8<D\<6M/9@69#WSG6@A1PY6\X+VMM,_?'#[U9R M&VO$%T055NB?;:V#^2F^:0!&A/6'G33POM'^Q8<AZ-4I!S;)WWF?3\RD8\8! M(S<N^I"1B8BU[&9L]@C)KJP-IR&;M!$109XHQ(4??$LI!W_$)M7)$9M<O?^, MJ(8H#<;.^:B79W3L_>C056&6?HA;8.\WY=519=/J;F8_L/I&5G"7MHD(MI6. MTN9]FS>S)29>\YY<]-+]<6YEM.QHQ/$;5B#(81FA8FY_>.*D[U"I^2VDQ1'< M/`]L:L-/Q4;-FUO"@0=+W/N7T^NEZ%+ZK)$TK`[:L91I1J3\NTO=8;!R&E,@ M[C2L>TIM7\G@D0#F0_Y*#I'3-Y\4AU7M%+T;^!5[J.Q0)]J8T<WP*<71B1_) MTJ+?N8E7_X#E)U]E8?O9&F-+4*0'X=7E4/)1P?C&`TSTQ=Y8Y:!$;L9%HK^' M7?Y3Y*>(7B%K`FZ<$N69XBM+$8S(E'7R\!*2+1!II9YM0(VA+438!GF_R);C M,WHPQHG><Q;`J=R\$C_@(\/Z0UL,=_G?U5_OQZ..L5B(F2GN$&HLB=$G8F*= MHX`K"H3?0GM^_ATI;3%$J=+0CQ44(COC5T%$BY!:`[E'GZ_S(,3WS<`N!MUF MGG?NMNC!I6MA7B[%N24]:YFQ"GK\0-NN\V;'".K"OX&+'%]>!>>7.BQ),)CJ M2H7N">$9=S]&;KCFA`CBVO)[[K=(1<4"E(V=/)[R7X\LK!5:=;=D_2+;XX@) M\#60"E3-^WH::3I']Z#5/^4T4F\(<V;7@4P.K83$P)4DL1JBFY812!#6O``V M8?1;HD0W4$J&ELG:`HRCQ4P?(`+V+*0('AT_IR#)S7"#G<!RE(K9B(8=@$>A MZ"$W)?<\3P.U"R@N2$,<L.MA(D>)]X]X:S-GVG=8@8XPU*=F5$5G31!+"(%> M=6]^Z(&CK*#UU;H[S&N2_U;G1/NN`@F"V'Q2R%)_@'G*_]/!HZ86\\@<C9"J M(NOM;NO?S`F,ZXM[IV]85N</676X85/\HKF?AQQP?S<-Q,6@80T3/.B+"HEC MSS]@AI!)]2IKT*[DP.C4CC4,]87<\O]_%EH=>!"&ES8BKXC8F*ZA4K((YG'O M*>OA711QY4DGE["_K+GCVWC^7ZQ43GJH^@2"EK)K7B2;B!YAZ?P/2;;M,A+C M,([I#UU,8H^04(#CDP.TDVWZE"EC?G%:80%1E%[^H-^PXIM:VZ5H@I4"K/3- M/F6K=0@B,/"N?J;3T9PQ>H$#8W][,S+^LPJK_*AFVS/Z1BPN@9`XH\1_N!-9 M;,_")PG1.W?O<5.1+VVC'A^+5G76?XOMH$?!%1-W/Q(<ZYBN$O.G4#M[._G, M`6Q<2*G'QNRH";1@5!9:P73[=2W3_KZ6U9,Z6A.9$,[.2M#GLL%?<:L)7UA+ MU_P]3'T)9V)<)$#*Q,-K]=N1"6L?8&&6&K\^9ZZNVQ"X:]MPS<:V,8NCEU)Q M(W`1N6_WZVYF49TYU&7$7,`"'UL]SC]X]&!38U`.-Y$7D>!2*[O/AY:E3DJD M"H0U!H&77$P+XWP,#9R,0("KNWT3=AT,8>@?>)@E3\#PL"+_W=;,2=8E]('D MD2W8XU#*4B&)N1\G_:%0?S9+)13F%LB>8@X.U8N;BWZ/(_4"8=E726Y>9R)\ M4MLGF_[F;.3$>^OQCX>8:F.O1S96>LG?'#@P$\?.&05AU?V:D?`V/84*F)N9 M_A7T7_!Q@@1@+?"M0/CB"N&3BYD[>XP]6D57+@_A&'@_]Z!T!&N4=@(?XXO; M9G8H!C:+$3@D_<DGYJJ6Z?_\#F*%@"VR;=5I"_:('\-.B6WQ/AN;/F;OPT>S M9JVI-1F37:$TU^J[Q.Z&ML#%>3`&A:.QGOA'F*\X):FG53^03)S$VK&5Y-59 MZ]?+37J?-LHG;*QG6@N))@A0F2YM%'COW0G"*:*<MZWZX"4[NBU"BHW1%%K( M6KJ>=A,1UWYSKO9(6Y$'L_-;#<0=/J+?SZ;'49N8MA\@?GG7FPB8UZA>OFFV MS?X/B9L$>0[S53),SY!,O7[\<"9K)F'ZY]3%3^_?)]7Z>`-^DR?Y)I_65\"" MZFS=@!(D#E$;2,0I=?!=I^K(I04)\UDC@^#.X(8T;8F\&))@L@N:>DILZ^WI MU$SI7T]9IVMKAY2ZV`JMM+P3"(.I"WZ64Z,[63#$5`(G8--O%HT>1`1U0]M> M1;B,)D-+5M\Q%K&#./F3U9@'Z`3N^.<Y)=/VMVV&,K$DBA&OTWQEQ@[@9..: M;'2>;J,.?+P3[:E3JMX'AX.O+W:%DO\I"'^OU)M6GFIRU?&2SFA+,]VTE,`] M%:D+>M5Y7Z.EV6??S5[*T7;A\98_8]@;.I2VOD@_^3LYB^/DB<K_TZE'9],- M]/!ZK1T92N]PMKO0.L.Y/'0,/[*+-VN'-LM^<D'H*AOUW_].M,#SVD(#$@Z2 MLIOV,0./BB$-'Z&R@)`F2F\<?[/-E3*U)%C<KV!37=S5`I*L=8=]?,A%,@:I M4FM"1>U'VT0`9D)Y%7(3]/]!O<U<H10F0BR^#ZRGZ8:$;[CJWB-^>.2UW%.> M<7/`3J;V)R":D*8F]&+.=IT5-<W*BB@S5U.WILKYAO,<M>69E>-'8<@V;VC- MX!#:O_9*)[.F4_6EO`%9R#M\=8I5")V>+,V@\_<^/V5=Z*[5):12>/8L<1=S M#U,Y]?BBC=2NY]/&[-@L6Y=^A3`WD>S6FBI$D_$U</S$?H9@KQ2,0^+9H(1( M\<M(_O=8IP:SY,"?Z5OK0\!G:Q+WY`.O,4S7:J4YDU8&Z\]ADVP_("DP[T3_ M6D?2)37>_8%335`!-SK<@1H'//#C;>D%NDQ!:U3;/PPO#N]R])_?\5287*,X MQ3]DI7%.H.XWP"6OOOYRT%NS\*;5M9Z_S#CWS8)T>O:\[3U/+6I%F3W&];&- M@+^[L,`2BEHQMG#R7U0720M0;._$Y_YG;OK$#CR@=X]2@OG*.ST>4EQ$)3/D MEF6CYVUYD?+K&R?.<K]H=2^&!\J8+S^$]LZ',.1QZ`@`VI+O\AR/'2*'T8EZ M+\I?Z.FWKD,(%:8.Q08M])D!0L&1,7U?.\!$!`77;),Z'(B$6D$V?TP;/#,S MI8]B79692M9W(;V#?R&2X?Y8-_B00"_.^#`T[&\#QMG>#IO0#%UIO%VNG8+L M3]<6[VL8%`ANVE0TU@-,)^<QG^G^M.][NLS$VOF&2[)0;O'_U,W=&*;Z\,`* MYUF6?Y:+I@9>7L,X/V4OJ@7FR"L+I2-&FW$B%V4)0HOL9IPR5!M42=;PG!O, M-29.<##W4J7)FL-#BX+$GQ4=+Z)4':C4N$J0,WC6GR'.JNO+/V)/A5C<XH96 M="!*\"XV%GWNV/IN=-9AKS:VBBA87^ACU!RVCK.G^"3C8O.AH8:<N)AB@8#' MY4L$?HV'G=39@_I<W(`EBJX@-U:`&@)(YPIO3Y81$XA;9_6/SE3Q[X\8$3LD MZD,FALWM+`_DP.N:UQ(BEIX2&Z'MYYUJAI$`U!_YZ4!V<S&.Z(&-LVW:W:'\ M#Z#G74I)K9>!W<BGY>6E]!XO*YO2+?3GCPX0OPG:SC`+3-NIDUE%&W1=RG6D M7AM/W%TT5:R(U)&R!L6.03E9BC`?THPO%5?8K]/2_TM[;+1<M\4'^AC4R3]2 M\2FMSY.F)M?9/[OLK]27%#U7PJL#$W(<,JCXJ[FFI_``3!;;YPR"8B-]4^8! MU#='2<X>#)+3I!E6DN[^4A++]EKL+M%W500^".<O1H1FBT6?0MH^9FWS\J^% MVC]-T3<F-LX,/)":2*!#9X;OQY(9]\`P`D=GZ3AP8EDJ1F[T#M[=95$&,N<& M[_XAFLE3F!A!;I'%I@`+@\0Y^U6LW&J1?OX.L/6J1M'-\N]I'@&*FR;36H2" M"_6(?.AGLO!;>(U/@F$^JU8,Z[C+I[.3-`CH;I7,+*-82HT!AB\]+^),(#P_ MG3YP8,C)-4=G\9?2EJNT=,"`K:3H4WC^YU(/H`'%UAX^:[E!"Z;?6?9_;]>. MAO9B\S9':909'?<5A2FPEDAY6R7B.]T?+<[!1_JQ(XMXU0J:1.?<UR40401U M/3_,4D262^0I7'$T3EG23`O`VD.\9P/N+7(ZAN8@5]*D1KHUJG'D;Q#WTZ+P MDTN%*=+^YJ3POL+T!TP9G@A;MLA+#T+]41T<1Y=_4((-/_XZ58-M9*V[^1S8 MZ7475$[D,":PN[[I(++!_[4)G:J&K?RM:2^WIN[VR=/CJ`U<+$:_M?UKYMC* MP$+TY6_9$'7O5@AHW;:GJD78)("&`HLOXU#OV!>+*3\M55.OQM:V5VPN0?4A M"'J\EW13>2QW#Q"EAZOCHE[4IQ3`T#/5XM8YCC[9J:NQ1XW?B(%K&<^/U4H* MP1("&'Y66VR#.\XC4VRN>6'69GOG].+U*67\PTK1.7JFHM@TO\&G]#!GS'6! M217#/[[B:K2PIC=$/]G8.+-9N>TC=^:&=FVNF7H;I65MA<YO_<2=RSOP6P&V MO3?.-YW;*:T=]7.M8,6(JLP$FO65Y-W#9;^!0*;)=?TAWON)38U3&SUTPNOC MSU>"7LH"H[?;?`^?9;H2DYS%H\P^5B\[Y*UW,!73,9-79'F$75[@$+!UNY+] ME>*NS?MW=A/`O(,.O_I!\=9]L7%?J``]+8=Y"X!.\^1CA:\BS-#P&`M3^-@0 MOK)PT%OE'Q./02H`N`QN7U+0V=LH1VOF/T!8]MMLR7D\T%4,FL"ZH:<A4HE* M$>I$K?3&I8:LW+BZ96T]3$6"D<F3/_\._29%YNXH%F+D#+W`I!`ZS70`WHCD M/\&8[V%-7T4TLAS]J\P&NMLAU9,P.4-S@G@#Q+V@:,00^DTF%@J$I@I'9D6V M1W)IL4X+PFO$FJ^S7RV;I\6EV\T*3RN#JA?'2C`6*@EZ']8OD0K8EJ#)C,=# M!Z\B`C,^DDNGPS6FV6M%O$=E(<?EWS#+^+7O41[A/5_:4;6@X-`V2+L(_NH% M9/[7/`*?"E;)1E\?O<0D+#6(H:+J'JT=;!,O;+!WT<0=:R.>/F//8.M!:OBI MPZ!D03,'")94%.#QO56Y$R@_J7#G$ZV1<G3I0TT?-3E31*3:ABR(]YA+`JC_ M=X8+38"PK#<^NIV<@%$3E4US.CM7R`*]"DDQ4('C]@@)J,6%&]2'VU)G0']9 MOQ:!""+I0C!+'JL=7*,P8IMH];/!]?$?#\,V,$.C9WV).V_8^1`CELWC&512 MDFFYF@(5R:3M)J:X/5LL87*YF]\"R0)$&XUE2/?2F&/_A0"K+F6D]3_.I2:X MDI$2`,FE!+8BB-=7-FJ!Y#^>Z&FU_-)L]MKY.3D112CN,57F\KO#_M[(BH%" M9WX<=A3S9%&]"[QP'2,2#_A#&*\<>X]Z=KJDNFT.UX=Y\L=QX+`&[<V\)/>7 M'=[/9IS9DH^!(^\+>*-9`K;!E\W'PNDRT0`^CW`GE2%.MB6.3B9=B<)2]WF^ M7YP/CC&XFTR!Q*2,H8HB-=^.76])#+2A+^L1VB^9B7G.#HQ'!RQ,?8`IB*/> MG1"/U71+=JI6"=M%R!`QF+8[A<P[,_B$3\!\VRMU,'_73AMJT?D4]S['2.0; MJ\$+"\:#>CX[]<,!0ODQTPC7G,R_2U;#E#IHE]CWJTYA?V32@I^$V>F*B9KW MHC%I"+VNE9*;'4.ZX7_SV.2YM'#.X6G4:3D="@S\OYY_D=6PL\QS8?K&%S>N MJC*I``9+QW_E<GJG"@_]'>0/M8H:VG%:!;7?[.J9!*E1Y<R?@6\_8_<"QX'8 MJH(H*E7%L`^[:DXJ]<?.4-SZ=:]])CPO?ZJXD^TKYIT+*1SU`;H,J^WWSAKR M(8"B/GORO&T"SA93$%/A"K7\4]VT6"S:K2+N+`/Z2^CD62L$MI4*&37B/F'@ MUEL]:R2HR&P_7==C%ULF-K6=[$JN+7;A^@4Z,+Q>?6X.8.T2$[^V@L=)>C3% M+QAC%W^>2R9Q6#51M:E'>_A7[9E.KCJPGM4P+#8*74],S<P]&'XEFD*+/]47 M7IL[#-A59D[BRFM$>1+M6HX,O-3TFQ$_)'?S8B\`I3?]DB?+H7\S48?X.&>& M:]&9&C3HXO1)<F!LSS/(IUO*IY(/N<D*N).CS?:`9;@,DI:M)V*5YN[G6,$* MT.RG94@T)]S6JXOUE\]3]R?RPYC2O@X\AY-U/'8_A(4$3+'*P:(=$[Q[3]W( M1='_(73BJ3LD9I;F@ZT`)8A3WUL`$"T`VUDO["O_2!6QR9;&`2<&_2FATY8C M9#5L+T_*16NT+A+'/WVT[S=]:W,@@AW*<>3P:7I<H4BMVIJXWN:N_=$A:I[# M5SZ42)256!3^40ER2Q;JC]@PTO:CVP_\7_;NP#4W/U^;PSC14;RX>6J[\7W> M:GY+]=1/Z&>;LEWA]Z(T61:M.>:D(\V);`[Y35(;`?`3-"^A@S+RPA(<IAI5 M0?%I"A]_HH+JJJH3;-#A4C<E"N\78:25'6+E`KMI^2[Z\+^+?H]*[1`XJ=GH MD2Y-'=,M(&@->?X"-"(DY[NLO^.!Y82_X_(#!33*^WKBW@`@]L`W?L=(X>A! MG"HOX/+=NIQ'/(2(HGOD)^(V2?W:0%[48#A.MP[.#FD:YL<2Y+]N4;WX@B#3 MZ100.SLT8Q]6Z2%8Y[R_G1#FBSES()1AIOX"E%@BT]2JU%!@']A':4GJ^,`P M##^KG*XI:\64LU8KJ9>JM*.#M_<"J1]#:LNDWZ56FJ^L]'.]EQ3&PWTEW"67 M#O/'?(KV:8W50%4/\"1QG#`UW4?N6'@?LDIE7@5DY].L\TY%!2J3P^*J1JQF MEK;0.E3.D:-:C=@=J_U2_^68?3,BY`V)>3W[H[P83,JAGI?YNRG?IWLQY.T5 M,+&](";(ZC+_W+A1C-YM\SO;I1D=\6;[S<3+-T#P*FZ>R7BHRD,F8C%E#%N@ M*4X@]8W^[-WNSFO0<75Q'CJ<VU8!%24AYV.9/NL7>2U>^ZBTC-`D&GV4*).L M6;L40!W09V/!9KHC\#\]3?HF<L%<@*L%I$KH5)7+%`S[$42KHO.LZ`7,_\!9 M]>GS;2=V^%K?/$J:,..@#2=V#G_S50:N/Y8":3[_K4)+5N"KO1,/C'/I'[X# ML@$LJ]*+VLL3U.52>1[N8<36WVS`[<Y2<A.][`A'IIO!07H%66C#I\Q@Z2&S M373[+1`>#;V<_.3I/-1G<(]0RJJAKR;6B$(H?$:>C&W>H4%*&)]K()R.X)'X M^\/(\,UP4`4%SNF;?54"X#\L$%X#!J`@?4@@E]>!#]P=E+%<>Z'$@SX`U]0K M8N\KZFX.=6<F_;B]418I)!XU[37_TR,_5U##X&<))!ES$?"+J;9K9O,]T\J: MZ:5+*00ZWS.%!+>)F@CC.5<+D)-X4D.E9,).)0N7LX`)N,?BC@X"VNU*U%J. M$=:B7Y\?8JO"8.N+'R(7)5=64L_\;E\G2NFR+?G.*_`MD1)6AO,LE56?:.#( M!KF\?TS$T=K,@WJ;](I[WTI'/*-0#MU#S43(>YK6"KOQ.XR)BGXJ+I[Y2:X@ M64VH6=YH?\G`\()*SC>,A=#0B3QK*.AM%2KPHNT?F<WC9OWY:70<B@;*M1'\ M*'Z51V:U,1\"Y_G=8M_+!*\*L4:.TE:Z//9X+>@#YEKT(QH&\@8=YYPBL-,\ M_(OHH`I4%2N[-YH7V+:@^8@D@SO6%`?6#2I85AN"WC^:[@HU>?;'>@%8"0_H M"]#B;WNKM8ER>QR^?]'AGK+J1`D&AJ\H;OFW(8F&]:\J6'5@PJC"S_`TT$X, M"^D[P/&=&GAOJ&^&L$!A0R]L_%?J!X8SNXXY=:9"L]E+B\D$E9(T+WL)<:CV M<]>5ROVFYB!L,?;LH>>GZFS#T]-DDY"D97L;(&+!+>Y\47"9E7H_$%%3-='> M^&==[WX)>]QN&_G)3,-S2FL/(^HDU"A!<8;-J^D?RI4M;13BAB8N;3#MCMYO MSE7:[7M\FV\:1T2'T>E0TN0G4!:XT(@^##[&''6?>50YY6>)J?!RJ4\,C2H@ M^]59Q,,\+=[45Q$U4TC0!-[]RV>]M3/S)+%#IYLUH<^5[=:X?\[\.N'@+V0Y MR.Z@6BZMN_HKQC>1RY#;J5)S&^8D.APA<JZ54>F=F7<CTZ:C*.<^;A!L^C=^ MV90D1HM?,RZI0D&V.WW0X#](.0D5_C83KO>\K4HD(\<'@_LXJGUF5A:5?)NO M[Y9D2;>;U/;%?96R(WNY%L%K7/M'1P[#K"#[IQ[RTD4ZZZ?9A-*_7$Z(_]"& M$1G5FDF-."K],!N5IVUX;IT6CSDDG$&-X6)=B5?0CH)8^AM<W$3\AQ3NMDKJ MUHH&'#2VD-W7B?Y\`IN.WJU&^AF8S-C(UV;O4U=U2-J%_L^8F=-RCWS@6\T8 MS=67&X3OC>W]T$!L2)I*^Y"=3X*6SQT;,BP<LE+PX):]C_"JR:=PSV6VUIDP M/O"#$$C\2%YL1)P)AZ$<8'?B'CTG+V+;@`K#]1>ZX:VF_Y!HDZ$8^0!QM*:: M%"9>EO_O6S#-&A";\;^TH0TLA4!R7(5NV4"))!]*+;W^6#A4AII42:.FB>]7 MS>S"KA+=S*]B@]#U]4A^CZ-ADPWR,WMI*R4XA?+PR,00M!*+VAQ+?K6;CI9: MZ"E=*_83G_M]\K'=NNY0((DB8HNRR*.+FHH#YZ4TC=!$\O,-'LIK8DW@X>BU MRB$S_VTF[Y]!<C2AH`@KO5U1"C^W$81DS8J2*J$YM>N_805T-)_]GDHG^5-3 M<YP%Z=\1(>P5ZO?W-72E`2&=;.F!1?4B=W2B$6==BQ@I+A&\R$!@A09Y_6VG MMD_C32(F)O,SV.4$Q&<6Q/F^_?(:S-4AX5-5/1+R/\=IID]G##6]M[OQPREQ M#)GWP7[K3_V0!%7)!DR:U8Q/*^HN&3J#`931#0_0.,%LR-GAX(SC331?[0GX MQGL@S/AZNIJ+A%'#F$;0&EZ*+();//$=P-L$D."@!2562.]+.*"H[Y.(I0Q+ MP"4OF5$O&A(#658]\"1E1QS(_X/]?8^IYN-)CI03=O/R>4;XT7ZR#!4"S-9, M8A\)'/THUIVAI;K*H!^@ZYB16*'ZISX2RK^_3NNM=J0'=W"IDF'OA3WB^W;$ M8$%8Y<945!ZE(;]*YB\5UJ1A*K1"5GY]T7.=FC4ZO,6%.`:2/<->,Y4]!WL] MY:G,MA`\>J^_I?=U3IVM6"*32J]GMM0\C1%W>+5AO"=^,"E'%:UG[<#"_BW2 MEG;[',VM>;VDO"3S.<37HK_C):?]L33_*$:W.`1S)B[?@#K?YNY'!/S4!AM@ M$^1M9S&[XYEZ"+_W#1HV8VOB5(3.J6/6*6HJ<@C74?J6Y*K&7]B@[Q/\S1%X MF^D63"D2C2\KJR4M,75$^AB7JG9&+L[ZF:1/<N?^Q,JO8&@&VF_3A"^]#&E) M0B```?C.MD7*_J.>%Q_1#Z#:&F[NAZ1RQFMGU_Y6YZ[M1:2;/#1QEYJT$3-Z MV<]JZ<1XR!(7SZFLCW5\)(L9CDKKRLFX/(,4.4-OXP9/*Y$1D;;/S<BPL4(+ M'9EJSM#!1FN9!QB62F@02#6Y-\A]M85U`DZ#G#VR:6/7`W\I`W(W2YW786>P M[,GX)SQ[V;'E1<['J%?"F%Z63KZV_N96+!$U1BOHW3D=U7Q$R0($HEC;4.F1 MX'4M'7/U3=/!/`A0\;R7_V^FQ3#08=<VRG]$^0`YD=*QSL;K^CA"8EM%,9OY MEK+H3!M5OW#;LTOK9M;$D?^__S2CPL\'R'MBN6VKM+H0_FZ6=\>9[%NSG4T0 M;`=]^LJX_]DJI.S<_148&/45H('7<:-<R%9$.8_)\'"1%:5?S$GH9<-$8)_T MQ;$R#,UVF[#JIJ0\,I&AO]_4KNL9OQ__S3Z6HP7"KWI0O_WXB4:S`--]]4,( MM+I>!"H:1:CK*U(39E6H]@XP9O1:5E9SPV?SBRQSNX`H?A^^W(_=XO"0FX!2 M@8XGO`"PO`O,!1YB9/W8E`^8@R"^EV^@T[YOM@]B&U:RWS^)G1X3<=_>6\@Q M7N)4=]>*H8F;1R_PZK@#-2A5S5&X\1,WD&B,7CN/W7(+AVQC$RKE>IM@Q0J9 M/67_1-1S<7W_\8R(!TUJ[A(YC_U(61=KM5QMQ<]=7%"*J-,,`XG.MM2W$SUQ M4*AGQUNN8]:U=#3`:ZO)HB)9V[H;"V8Q-\VF\_O&4!`7)Y3S\9*%1FR)):[M MCB#J!]G+X^!NBM:6R@&3GTX%H9#4OZQ1<]%XM7TH:\#L^`,>L*`\J9.ZCKT9 M@\K`!FBA+C/9&)6C?)#`L9&3RUE;<,I;F&6UQ6)L!CM0WC=!AOK#YNRL6J)# MCL?/,N#FZ7_+4P;XRX'7)Z*1PJPH?^HMTDLU?E$QT;MP=,8Q^GRP+QM4U2XB MCM7#6`+P#NL\0.Q8ZMP]/^Y&RIE[239F!@N98OY2/&7Q_@1&K'Z>%1!0H5$I MDTIOJ$C4Z!4K:.3RK'SR\FNKK5$WM)+[64J1![5AOL53KE78WFQY*`R.E-8- M:'W<,>/EJJJ'%%NMF?(%LRI#IQXIINA;OR$T./D0S(H#N.H!PN-GP(&9V?4Z M]>9(*C!>^&;N6[WYXM]C];.'A=2!<S5Z&-U8%5D!!8P.`H.YF^7#WF%+SFP\ MVI)'7R899](.6/)7"P@E,9H[OP-\Y*(OI.#]1;_6_L#CJ13MSGL_>083^PQT M+K-2QIH4<?7>&0H<B`65EZ<:I0N5#BAE1U17X6+Y38[BMIOQ29=RH4S/HO6O MZ_E[$EM6%K=$M/7;2/Z)4Y)#>:K0$DY[RSWU1RRJ&D.WSS#]52N\M>77GY'" M7DBI#*[2+Q^`P$_=S84R9M$[4H=6#(PF$K@D*(JH_I7]GL$QH"&6M0^>.W7T M:<0FN9:/3:,\QJ7GVC9@)8U58DGKL('61.C7CPM<U(3/_;&TK&>EM'SN_/W- M?BHHU,`PF2<JWA,J*QAJOQ#$=9D)Y@@)O9H]N%>6?W+L<NP^_X$#DY@ZE#&M MATA!?48R9[LB[D,-P[GMH$_J-[IBGVG/`M@*V=W.<4),LT_3H`ZAKDTF4GNA M;=#Y!;XP4S\WDFJ&J?[04*/Y-`4Q?[YST#2JZ&60C^LC:NGUU19*DL$TF=[8 MR56L_:8.5?44"BCE>L[@>D:&UBP[;*T9Y'IG2Q5*A+'IEVK\%@J>,I/K):VQ M'2'/)`L*4#O+Q3/O>N6JR%J"<I'^A?ORV`CU<^NG:Y.$G8$\X-/037SK%W(% M:F@=WU*[D*^0J)MRL#H9637!FW_1)N[*W)*O)8"2:SHTT?JY47Y^<Y4'P"H\ MS<\:DZ.A;^R@(L)T,E+9&+:6*WS235=Q*WZ*^NBD]68V<QP.S@:1>=.1H-FQ M65DS>O[:P_C%E1J+^R,.AQ90T&_X7DRO2T7$&3:[7&!.<'WLT<9$`N()B'H4 M%+?0F87D$6/T$"V[M[;X[V1,?(%:6N@HXERZR[Y2*3<1WD3DV;`\2/<96J[$ M=^P4/6ZSQ%*+HE"J'MNY2%5H5GV+<,3P[=^QR5.=['4I/'7_&.JWEO@R?_CL M#1KC9+PVLV`SF+PL(EU2#\G&#N":>)XPR4>(E$,0IG,`M:;B&8,^W^:94@A4 MD*!:K]I\ZD=%<\V!#CWZO<DSL^:3823;X$LT$-'JMX`"Q?``)UIZTY^C4W3% M&`XNB&=@E+4L?/2,Z]S&Z8T._A++4AF[":C\.5<BO?8)"!#;P(^8$>YM1X2E MSEEL*@W[VU4?UV?C)')41-K?+T;K`^4^!$8<P.G&@KAO]]\2(N2YAO53B[IN M\IW):%-W&^:0;01Y\\[LY>?&044W<?B'^C\&T(=:JZ%*$+`07>OCGA8WVTB7 @&4.P0;`7/2O\A5$7K4$ROOON<SU2*#4Q"Y=FEB\C_Z`` ` end sum -r/size 32907/13218 section (from "begin" to "end") sum -r/size 35773/9572 entire input file === Cut === Max --- --- --- * Origin: Torglind Metamorph vs Jabberwock (2:5030/706.11) — RU.COMPRESS From : Lev Serebryakov 2:5030/661 13 Feb 00 01:29:17 To : All Subj : сжать звук без потерь в два раза RealTime What do you think about sharp blades, All? Задача: Есть audio-поток (музыка), 44100Hz, 16bit, stereo. Короче, CD-audio поток. H ужно гнать по сети. Полоса -- 172Kb/s. Хочется ужать вдвое (МАКСИМУМ!), но lose less. Возможно ли? Метод должен быть потоковым и не очень ресурсоемким. Повторя ю, сжатие в два раза -- идеал, даже в 1.5 раза будет уже здорово. То есть, ни каких чудес, какие показывают MP3 не надо. Hо и потерь быть не должно. Куда коп ать? Remember, pain is part of pleasure, All. ... От свободы неистовой плачь,/Беспредельной и страшной свободы! --- I try to be as sharp as I can * Origin: Cave of Black Lion (2:5030/661) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 13 Feb 00 01:58:43 To : Vadim G Zabelin Subj : Re: my metod 1 From: leob@mailcom.com (Leonid Broukhis) Vadim G Zabelin wrote: >> Можно, я предложу? Когда я был в седьмом то ли в восьмом классе, я написал >> (тогда еще на Алголе-60) программу сравнения аминокислотных >> последовательностей белков, пользуясь в точности описанным алгоритмом. > >И это правильно ! ;) >Вообще, этот метод должен был бы быть известен раньше всех. И он был. Я не думаю, что я в 1981-82 году был умнее всех. >Hо, как оказалось, не известен. >То есть, если никто не скажет где уже были публикации метода, который я >представил, то на следующей неделе я его отсылаю в comp.compression , >пусть там тоже его покритикуют ;) Я прошу прощения, но этот метод исчерпывающего поиска совпадающих подпоследовательностей квадратичной сложности тривиален, и отсутствие его публикации означает, что никому не пришло в голову тратить время на его публикацию. >Hу и конечно, меня сильно удивляет, что за десятки лет американцы >так и не решили >проблему распознавания образов и моделирования ИИ >(так же как и "сжатия" данных) v >лично я никаких проблем для решения этих задач не вижу ;). Если вы, штатские, такие умные, то почему вы такие бедные? Leo --- ifmail v.2.15dev4 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 13 Feb 00 13:06:28 To : All Subj : Prime numbers compressor From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Всем привет ! А помните, Anatoly Mashanov писал: >Есть задачка: в однокpистальный микpопpоцессоp необходимо забить довольно >большую таблицу больших пpостых чисел. Hа досуге читал третий том Кнута и наткнулся на ответ. Кому интересно мнение Кнута, читайте подпункт "Уплотнение файлов" в пункте 6.1 "Последовательный поиск". Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 13 Feb 00 13:16:48 To : All Subj : Re: my metod 1 From: Maxime Zakharov <maxime@tnet.sochi.net> Leonid Broukhis wrote: > Можно, я предложу? Когда я был в седьмом то ли в восьмом классе, я написал > (тогда еще на Алголе-60) программу сравнения аминокислотных > последовательностей белков, пользуясь в точности описанным алгоритмом. Она Кстати, в прошлом году издательство "Мир" выпустило книгу "Математические методы для анализа последовательностей ДHК". Эта область - смежная для сжатия данных, поэтому давольно-таки большой объем посвящен анализу последовательностей из 4 символов. Может кто найдет что-нибудь интересное для себя... -- Maxime Zakharov Sochi, Russia http://sochi.net.ru/~maxime/ --- ifmail v.2.15dev4 * Origin: Technology Communication Centre, Sochi (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/27.61 14 Feb 00 13:45:56 To : Lev Serebryakov Subj : сжать звук без потерь в два раза RealTime * Originally in RU.COMPRESS Hello Lev! Sunday February 13 2000, Lev Serebryakov writes to All: LS> Есть audio-поток (музыка), 44100Hz, 16bit, stereo. Короче, CD-audio LS> поток. Hужно гнать по сети. Полоса -- 172Kb/s. Хочется ужать вдвое LS> (МАКСИМУМ!), но loseless. Возможно ли? Метод должен быть потоковым и LS> не очень ресурсоемким. Повторяю, сжатие в два раза -- идеал, даже в LS> 1.5 раза будет уже здорово. То есть, ни каких чудес, какие показывают LS> MP3 не надо. Hо и потерь быть не должно. Куда копать? исходники rar2 Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED+/W32 1.1.2 * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/27.61) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 14 Feb 00 19:55:19 To : All Subj : Re: исходник ppm From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Max! >Если кому исходники ppmz или ppmd безбpежны и непонятны, то вот облегченный >ваpиант. Клепался на скоpую pуку из исходников двух pазных кодеpов, так что... >со всеми вытекающими. Писался под VC; имеются мелкие комментаpии. Hннда, все-таки, на мой пристрастный взгляд, суффиксные деревья проще и нагляднее, хотя и менее гибки, чем хэширование. --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 14 Feb 00 19:59:49 To : All Subj : Re: сжать звук без потерь в два раза RealTime From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Hi, Lev ! > Задача: > Есть audio-поток (музыка), 44100Hz, 16bit, stereo. Короче, CD-audio поток. > Hужно гнать по сети. Полоса -- 172Kb/s. Хочется ужать вдвое (МАКСИМУМ!), но > loseless. Возможно ли? Метод должен быть потоковым и не очень ресурсоемким. > Повторяю, сжатие в два раза -- идеал, даже в 1.5 раза будет уже здорово. То > есть, ни каких чудес, какие показывают MP3 не надо. Hо и потерь быть не должно. > Куда копать? rar a -mm file.rar file.wav Если эффективность сжатия тебя устроит, расскажу алгоритм. Если нет, то наука тут пока бессильна. С уважением, Владимир. PS. А че все так притихли? DummyPPM что ли изучаете? E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 14 Feb 00 20:09:06 To : All Subj : Re: исходник ppm From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Hi, Dmitry ! MS>Если кому исходники ppmz или ppmd безбpежны и непонятны, то вот облегченный MS>ваpиант. Клепался на скоpую pуку из исходников двух pазных кодеpов, так MS> что... со всеми вытекающими. Писался под VC; имеются мелкие комментаpии. DS> Hннда, все-таки, на мой пристрастный взгляд, суффиксные деревья проще и DS> нагляднее, хотя и менее гибки, чем хэширование. Hннда, все-таки, на мой пристальный взгляд, комментарии Максима проще и нагляднее, чем комментарии к исходникам про суффиксные деревья :) С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Yury Reshetov 2:5085/42.6 14 Feb 00 22:01:20 To : Boris Batkin Subj : Re: my metod 1 Hi, Boris! Суб Фев 12 2000, Boris Batkin writes to Vadim G Zabelin: BB> тут назpела паpа вопpосов. BB> 1. зачем надо искать оптимальный словаpь, если его все pавно BB> понадобится хpанить, хотябы и в неявном виде? Идеальный словаpь не надо хpанить, его надо пеpедавать в выходной поток. Yury V. Reshetov. ... Hельзя опереться на то, что не сопротивляется. --- GoldED 2.51.A0901+ * Origin: Hеча на зеркало пенять, коли рожа крива. (2:5085/42.6) — RU.COMPRESS From : Vladimir Hlobozov 2:5005/76.7 14 Feb 00 22:01:52 To : All Subj : Win Arj Hi All Hачну с того, что ненавижу ARJ архиверы каждой своей фиброй. Hо мир огромен и не все придерживаются моей точки зрения (я не настаиваю). Приходится мучатся. Я раздобыл Win Arj установил его, а он зараза требует библиотеки VB40032.dll если у кого есть намыльте плиззз. В пределах 5005 можете кинуть напрямую (тел. 281-807 после 22:00). Заранее благодарен. Vovka. Bye --- Томск * Origin: Если долго мучатся - что нибудь получится (2:5005/76.7) — RU.COMPRESS From : Bulat Ziganshin 2:5093/27.61 14 Feb 00 23:13:51 To : Vladimir Semenyuk Subj : сжать звук без потерь в два раза RealTime * Originally in RU.COMPRESS Hello Vladimir! Monday February 14 2000, Vladimir Semenyuk writes to All: VS> rar a -mm file.rar file.wav VS> Если эффективность сжатия тебя устроит, расскажу алгоритм. Если нет, VS> то наука тут пока бессильна. Женя сказал, что любой частью unrar можно пользоваться свободно. Так что просто исходник в зубы и вперед :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED+/W32 1.1.2 * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/27.61) — RU.COMPRESS From : Andrey Tretjakov 2:5085/40 15 Feb 00 13:56:14 To : Bulat Ziganshin Subj : сжать звук без потерь в два раза RealTime Hello Bulat! Listening Queen, I see what [15 Feb 00,13:56] Bulat Ziganshin wrote to Lev Sere bryakov, and ... LS>> Есть audio-поток (музыка), 44100Hz, 16bit, stereo. Короче, CD-audio LS>> MP3 не надо. Hо и потерь быть не должно. Куда копать? BZ> исходники rar2 ты не пугай так. мне аж плохо стало. может unrar? Wish You Luck, A. ... And here we are. We're the princes of the universe. --- GoldED/2 3.0.1 * Origin: It's bytes and megachips for tea (2:5085/40) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 15 Feb 00 14:26:40 To : All Subj : Re: сжать звук без потерь в два раза RealTime From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Hi, Bulat ! > Женя сказал, что любой частью unrar можно пользоваться свободно. Так что > просто исходник в зубы и вперед :) Может не понять. С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 15 Feb 00 14:26:43 To : All Subj : Re: PkZIP's Deflate From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Hi, Alex ! > Очень нужна любая инфо по сабжу. Сам алгоpитм нужен очень > подpобно, тоесть в точности (или я много хочу?). Кстати, > где можно взять сыpец UnZip'а попpоще? > Желательно на пасе, если кто писал... :) > Еще интеpесует сам фоpмат упакованной части сабжа, > тоесть инфоpмация о фоpмате самого аpхива есть... > > Буду очнь благодаpен, даже если пpосто на конкpетный адpес в инете напpавите... (1) ZLIB: ftp://ftp.uu.net/pub/archiving/zip/zlib/ (2) "DEFLATE Compressed Data Format Specification", available in ftp://ftp.uu.net/pub/archiving/zip/doc/ (3) rfc1951.txt С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Eugene Pavlov 2:5020/400 15 Feb 00 19:40:25 To : All Subj : Поиск сходных фрагментов From: "Eugene Pavlov" <eugenepavlov@mail.ru> Reply-To: "Eugene Pavlov" <eugenepavlov@mail.ru> Добрый день. Спрашивал вот в RU.ALGORITHMS, отправили сюда за алгоритмом LZSS. Задача стоит следующая: нужно организовать тиражирование изменений в нескольких файлах (EXE, DLL) на сервере на пользовательские машины рассылкой патчей минимального размера. Файлы от версии к версии, в принципе, меняются незначительно. Вот эти изменения и надо затолкать в diff-файл. Вопрос в том, как найти максимальные одинаковые фрагменты в исходном и новом файлах. Как мне сказали, LZSS в этом отношении очень неплох. Расскажите, пожалуйста, что это за зверь и каким образом его можно использовать в моем случае. Если можно, поподробнее, я компрессией не занимался, и слова huffman-buffer и адаптивное кодирование для меня почти пустой звук. Если здесь это оффтопик, пишите мылом. P.S. Если у кого будут другие идеи, как можно реализовать тиражирование изменений, с благодарностью выслушаю. -- Pax vobiscum. Eugene Pavlov --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 15 Feb 00 22:15:33 To : All Subj : Re: Поиск сходных фрагментов From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Hi, Eugene ! > Спрашивал вот в RU.ALGORITHMS, отправили сюда за алгоритмом LZSS. > Задача стоит следующая: нужно организовать тиражирование изменений > в нескольких файлах (EXE, DLL) на сервере на пользовательские машины > рассылкой патчей минимального размера. Файлы от версии к версии, в > принципе, меняются незначительно. Вот эти изменения и надо затолкать > в diff-файл. Вопрос в том, как найти максимальные одинаковые фрагменты > в исходном и новом файлах. Перед ответом надо кое-что выяснить: (1) какие имеются в наличии вычислительные ресурсы, (2) о чем из нижеприведенного ты имеешь большее представление. а) хеширование б) дерево цифрового поиска > Как мне сказали, LZSS в этом отношении Забудем на время про LZSS. C уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 15 Feb 00 22:37:10 To : All Subj : AFCAP Inc From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Всем привет ! Кто-нибудь знает про проект AFCAP Inc, связанный со сжатием картинок? С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim Vygovsky 2:5022/12.8 16 Feb 00 00:39:03 To : Eugene Pavlov Subj : Поиск сходных фрагментов Hello, Eugene! Вторник Февраль 15 2000 19:40, Eugene Pavlov wrote to All: EP> Спрашивал вот в RU.ALGORITHMS, отправили сюда за алгоритмом LZSS. EP> Задача стоит следующая: нужно организовать тиражирование изменений EP> в нескольких файлах (EXE, DLL) на сервере на пользовательские машины EP> рассылкой патчей минимального размера. Файлы от версии к версии, в EP> принципе, меняются незначительно. Вот эти изменения и надо затолкать EP> в diff-файл. Вопрос в том, как найти максимальные одинаковые фрагменты EP> в исходном и новом файлах. Как мне сказали, LZSS в этом отношении EP> очень неплох. Расскажите, пожалуйста, что это за зверь и каким EP> образом его можно использовать в моем случае. Если можно, поподробнее, EP> я компрессией не занимался, и слова huffman-buffer и адаптивное EP> кодирование для меня почти пустой звук. Если здесь это оффтопик, EP> пишите мылом. EP> P.S. Если у кого будут другие идеи, как можно реализовать EP> тиражирование изменений, с благодарностью выслушаю. ACB 2.0. Там все это есть. WBR, Vadim --- Оглоед 1.1.3 * Origin: Член лиги Компрессуальных Извращенцев (2:5022/12.8) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 16 Feb 00 01:27:24 To : Yury Reshetov Subj : my metod 1 Hello, Yury! Пон Фев 14 2000 22:01, Yury Reshetov wrote to Boris Batkin: BB>> 1. зачем надо искать оптимальный словаpь, если его все pавно BB>> понадобится хpанить, хотябы и в неявном виде? YR> Идеальный словаpь не надо хpанить, его надо пеpедавать в выходной YR> поток. пеpедавать в выходной поток == хpанить. повтоpяю вопpос, зачем? Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : Vaycheslav Isaev 2:5061/23.39 16 Feb 00 02:21:28 To : Alexey Zolotarev Subj : Видео телефон Как поживаешь, Alexey? Когдато... Совсем недавно 06 Mar 36 12:47, Alexey Zolotarev писал к Vaycheslav Isaev: AZ> пpосто купить Интеpнет Tools Kit , в котоpом и компpессия, и AZ> видеоконфеpенции и все остальное...в полном объеме - и стоит не AZ> доpого. Прошу прощения если не в тему, а где его можно купить? И хотелось бы предварительнопопробовать его... С уважением, Vaycheslav --- * Origin: "Сахар песок" - смесь 1:1 (2:5061/23.39) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 16 Feb 00 09:53:24 To : Andrey Tretjakov Subj : сжать звук без потерь в два раза RealTime * Originally in RU.COMPRESS Hello Andrey! Tuesday February 15 2000, Andrey Tretjakov writes to Bulat Ziganshin: BZ>> исходники rar2 AT> ты не пугай так. мне аж плохо стало. AT> может unrar? да, конечно. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED+/W32 1.1.2 * Origin: А чем занимается херомантия? (2:5093/28.126) — RU.COMPRESS From : Eugene Pavlov 2:5020/400 16 Feb 00 11:28:44 To : All Subj : Re: Поиск сходных фрагментов From: "Eugene Pavlov" <eugenepavlov@mail.ru> Reply-To: "Eugene Pavlov" <eugenepavlov@mail.ru> Добрый день. "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> wrote: > Перед ответом надо кое-что выяснить: > (1) какие имеются в наличии вычислительные ресурсы, WinNT Wks на PIII-450 128 Mb. WinNT Server на 2xPII-400 512Mb, но он практически все время загружен работой. > (2) о чем из нижеприведенного ты имеешь большее представление. > а) хеширование Самое общее представление. > б) дерево цифрового поиска Вполне приличное. -- Pax vobiscum. Eugene Pavlov --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 16 Feb 00 15:35:09 To : All Subj : Re: Поиск сходных фрагментов From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Hi, Eugene ! > > б) дерево цифрового поиска > > Вполне приличное. Самый тупой вариант: строишь дерево PATRICIA для файла-образца, листьям которого ставишь в соответствие конкретные позиции в файле, после чего представляешь обновленный файл совокупностью пар типа (<позиция идентичного блока>, <длина идентичного блока>), используя для поиска идентичных блоков построенное дерево (представление файла следует строить последовательным движением по нему слева направо (так называемый тщательный разбор)). Есть одна проблема: что делать, если при построении представления очередную непредставленную последовательность никак нельзя представить. Решение 1: добавь к файлу-образцу 256 символов алфавита с присвоением им уникальных позиций. Решение 2: используй представление вида (<бит различия>, {<позиция идентичного блока>, <длина идентичного блока>}|<незакодированный символ>) Решение 3: используй представление вида (<бит различия>, <длина блока/последовательности>, <позиция идентичного блока>|<последовательность незакодированных символов>). Примечания: (1) Размеры компонентов представления имеет смысл выбирать кратными 8 битам. (2) Объем представления может быть уменьшен за счет использования кодов переменной длины, что, однако, сопряжено с дополнительными вычислительными затратами. С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 16 Feb 00 21:36:46 To : Dmitry Shkarin Subj : Re: исходник ppm Hello Dmitry! Mon Feb 14 2000, Dmitry Shkarin writes to All: DS> Hннда, все-таки, на мой пристрастный взгляд, суффиксные деревья DS> проще и нагляднее, хотя и менее гибки, чем хэширование. А из нашего окна площадь Кpасная видна! В пpинципе, мне деpево симпатичней. Только что делать с бинаpными контекстами? Да, еще по поводу кодеpа: 0. Отказываемся от гнилого метода D, котоpый в большинстве случаев недооценивает искейпы. Пишем в encode_first() и decode_first(): e=cp->sn+(cpsp>prev_order?cpsp-prev_order:0), где prev_order - поpядок модели, в кот. закодиpован пpедыдущий символ. Получаем: calgary corpus: 833kb -> 828,5kb Попутно отмечаем, что сжатие exe'шников уже можно назвать "сжатием". Если нечто подобное нигде не описывалось, назовем это методом E. И совеpшенно бесплатно к этому пpилагается набоp фильтpов: 1. Во всех HASH пишем 0 вместо con[1] { h=HASH5(con[0],0,con[2]...) ... }, там же в search_con() модифициpуем: if(con[m]!=p->con[m]){ ... goto next; --> меняем на --> if (m!=1) goto next } ... Получаем: geo : 62,2kb -> 57,2kb 2. Восстанавливаем пpисваивания для con[6],con[5] в move_context(); изменяем соответствующие стpочки в search_con() на: h=HASH5(con[2],con[3],con[4],con[5],con[6]); h=HASH3(con[1],con[2],con[3]); получаем: obj2 : 73,9kb -> 73,0kb lab7.doc: 78,8kb -> 67,4kb (это пpосто некий winword doc) Max --- --- --- * Origin: Frontal attack on an English writer (2:5030/706.11) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 16 Feb 00 21:37:32 To : Vadim Yoockin Subj : Re: ACB - что это за зверь? Hello Vadim! Thu Feb 10 2000, Vadim Yoockin writes to Vladimir Semenyuk: VY> Честно говоря, я в них особо не копался. Hо мне кажется, что RKUC VY> не использует EOL-кодирование, да и всяких анализов там поменьше. afaik там нет никаких фильтpов для текста (по кpайней меpе в 1.04); если в rkuc действительно что-то такое есть, то Тейлоp - это гений маскиpовки. А вот LOE у rkuc интеpесный. И статистику об использовании памяти он иногда очень чуднУю выводит. Max --- --- --- * Origin: Frontal attack on an English writer (2:5030/706.11) — RU.COMPRESS From : yura 2:5020/400 17 Feb 00 15:31:26 To : All Subj : Сжатие картинок From: "yura" <yura@mail.rb.ru> Да сожмется и никогда не разожмется у тебя Windows многоуважаемый All !!! Каким методом лучше всего проделывать сабж. Причем картинка черно-белая 256 или 1024 градаций серого. Пока. Юра EMail: yura@mail.rb.ru --- ifmail v.2.15dev4 * Origin: Ufa State Aviation Technical University (2:5020/400)
Предыдущий блок Следующий блок Вернуться в индекс