| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Bulat Ziganshin 2:5093/27.61 23 Dec 99 21:30:16 To : Nickita Startcev Subj : Это велосипед или нет? * Crossposted in RU.COMPRESS Hello Nickita! Wednesday December 22 1999, Nickita Startcev writes to All: NS> Так вот, меня мучает вопрос: а не изобретаю ли я велосипед? Hасколько NS> такая метода эффективна? Для использования вместе с lz - очень неплохо, это один из лучших способов сж ать тексты (при использовании lz) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/27.61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/27.61 23 Dec 99 21:33:05 To : Vadim Yoockin Subj : Это велосипед или нет? * Crossposted in RU.COMPRESS Hello Vadim! Thursday December 23 1999, Vadim Yoockin writes to Nickita Startcev: VY> Боюсь, этот велосипед не окажется достаточно хорош :) по-моему, то же, что и dict+arjz Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/27.61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/27.61 23 Dec 99 21:34:05 To : Ivan Azmanoff Subj : CRC32 * Crossposted in RU.COMPRESS Hello Ivan! Thursday December 23 1999, Ivan Azmanoff writes to All: IA> Пипл! Можно ли как-нибyдь pассчитывать сабж без пpименения IA> CRC-таблиц? Hеохота мне тащить 2 кБ с таким малюсеньким алгоpитмом. 1kb и в zip/unarj есть алгоритм построения этих таблиц "на лету" Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/27.61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 24 Dec 99 00:47:49 To : Dmitry Shkarin Subj : Это велосипед или нет? * Crossposted in RU.COMPRESS Hello Dmitry! Thursday December 23 1999, Dmitry Shkarin writes to All: DS> Метода не очень эффективна тк ты не учитываешь корреляций между DS> словами. на самом деле, более-менее, где-то в районе jar/dict Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Yuriy Kaminskiy 2:5020/517.21 24 Dec 99 04:11:06 To : Dmitry Shkarin Subj : Re: Ari Hello, Dmitry! >>>>> On 18:15 22/12/1999, dmitry.shkarin@mtu-net.ru writes: DS> Да нет, это я про ппмд: сам он объявлен public domain, но использует DS> шиндлеровский кодер, который гнусный не потому что плохой, а потому что DS> распространяется под GNU GPL. Кстати, если он использует что-либо, распространяемое под GPL, то он и целиком вовсе не public domain, а GPL'ed. GPL - это "прилипчивая" лицензия :) Точно так же, если вы что-то скомпилируете cygwin'ом, и не получили отдельной коммерческой лицензии, то вы должны распространять это "что-то" под GPL. Wellcome to RU.GNU :) -- Yuriy Kaminskiy. --- Gnus v5.2.25/XEmacs 19.14 * Origin: Kyle Katan's station (2:5020/517.21@fidonet) — RU.COMPRESS From : Yuriy Kaminskiy 2:5020/517.21 24 Dec 99 04:17:40 To : Leonid Broukhis Subj : Re: есколько вопросов Hello, Leonid! >>>>> On 10:39 22/12/1999, leob@mailcom.com writes: LB> О том я и толкую. Ассемблер нужен только для выражения того, что LB> невыразимо средствами Си (RCR, например). Кстати, ROR/ROL gcc вполне понимает :) Т.е. x=(y<<5)|(y>>(WORDLEN-5))&1 он преобразует в roll $5,%%ecx -- Yuriy Kaminskiy. --- Gnus v5.2.25/XEmacs 19.14 * Origin: Kyle Katan's station (2:5020/517.21@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 24 Dec 99 09:00:55 To : Nickita Startcev Subj : Re: Это велосипед или нет? From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Nickita Startcev ! You wrote: >А если изначально составить словарь "приставок","суффиксов", "корней", и >"окончаний"? >А если составить "словарь всех слов" русского/английского языков? и словарь к >оконечному файлу не приписывать? Всех - не надо. Будет многовато неиспользуемых кодов. А вот наиболее частых - запросто. Только на таком велосипеде уже ездят :) Jar, dict, rk, arhangel... Всего доброго, Вадим. --- ifmail v.2.14dev3 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 24 Dec 99 09:52:15 To : Nickita Startcev Subj : Это велосипед или нет? * Crossposted in RU.COMPRESS Hello Nickita! Thursday December 23 1999, Nickita Startcev writes to Dmitry Shkarin: NS> текстовые файлы? Hасколько хорошо "арифметическое кодирование"? Где NS> взять исходники и/или описание LZW и арифм.кодирования? найди узлы, хранящие архивы фэхи adevcomp. arith там точно было, lzw можно заки нуть. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 24 Dec 99 11:42:38 To : All Subj : Как это называется? From: leob@mailcom.com (Leonid Broukhis) Имеем контекстную модель N-го порядка, как у PPM. Для кодирования очередного символа: 1. Hаходим вероятности всех символов в модели всех порядков, которые уже существуют для текущего контекста. 2. Для каждого символа складываем полученные вероятности с определенными весовыми коэффициентами (например, с одинаковыми). 3. Сортируем символы по убыванию вероятностей. 4. Hаходим номер кодируемого символа в полученной последовательности. (он по идее должен быть весьма мал). 5. Кодируем номер чем-нибудь простым, типа ari. 6. Опционально: Модифицируем весовые коэффициенты, отдавая предпочтение моделям низших порядков, если номер больше определенного, или наоборот, если меньше. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Evgeny Mukhachev 2:5020/400 24 Dec 99 11:59:49 To : All Subj : Где найти хорошие исходники алгоритмов сжатия From: "Evgeny Mukhachev" <mea@iitp.ru> Привет. Хочу в программе сделать встроенное сжатие. Меня интересуют исходники арифметического кодирования, PPM, LZx и BWT. Заранее благодарен, Евгений. P.S. Извиняйте, если глупость сказал. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Evgeny Mukhachev 2:5020/400 24 Dec 99 11:59:50 To : All Subj : Re: Посоветуйте метод для сжатия гладкого сигнала From: "Evgeny Mukhachev" <mea@iitp.ru> Vadim Yoockin <vy@thermosyn.com> пишет в сообщении:83ss4c$b4h$1@news.kiev.sovam.com... > >Конечно, не байт, а 4-байтовое число. Иначе, действительно пропадет > >зависимость между байтами. Ведь значения этих чисел распределены > "сильно > >неравномерно" :)). Обычно есть 10-20 наиболее часто встречающихся > значений, > >а остальные встречается по одному разу. > Можно сделать двухступенчатый (трех-, четырех-...) кодер. > К примеру, кодируешь номер диапазона, затем номер числа в этом > диапазоне. Деревья чисел можно строить и общие для разных > диапазонов и отдельные - тут уж экспериментировать надо. Я понял. Допустим я делаю четырехступенчатый кодер. А диапазон делаю равным 256 ;) Что-то мне это напоминает ;))) Может мне все-же оставить Хаффмана в покое, а попробовать арифметическое кодирование? Евгений. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 24 Dec 99 12:28:32 To : Bulat Ziganshin Subj : Re: Это велосипед или нет? From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Bulat Ziganshin ! You wrote: > VY> Боюсь, этот велосипед не окажется достаточно хорош :) > >по-моему, то же, что и dict+arjz Hо у тебя же в dict'e далеко не все слова кодируются ;) Всего доброго, Вадим. --- ifmail v.2.14dev3 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 24 Dec 99 14:23:36 To : All Subj : Re: Как это называется? From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Leonid ! > Имеем контекстную модель N-го порядка, как у PPM. Для кодирования очередного > символа: > ... По-моему, название за тобой. Однако оригинальный PPM все равно будет более эффективным. Такая грубая абстракция (кстати, не ты ли предложил нечто подобное для ACB?) вряд ли даст выигрыш. (Тем более, что того же эффекта можно достичь и без упорядочивания.) Да и скорость не увеличится. Вот в ACB скорость, вероятно, возрастет. С уважением, Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 24 Dec 99 14:23:39 To : All Subj : Re: Ari From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Max ! > Пpоблемы аp.кодеpа: > 1. пеpеполнение > 2. аpифметика конечной точности > 3. eof Чего вы все к eof пристали? Hу сколько вы на нем проиграете? С уважением, Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 24 Dec 99 14:50:32 To : All Subj : Re: PPMZ vs дpугие PPM From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Max! >танки гpязи не бояться. >bwt, ppm можно подкpутить для такой гадости. imho поможет некий мощняцкий >алгоpитм адаптивного изменения поpога для pешкалинга + >вымывание из контекстов стаpых или пpосто подозpительных символов. Или >сбpос подозpительных контекстов целиком, но тут могут быть пpоблемы >с pеализацией. Похоже RKUC так и делает: отслеживает производительность и стабильность распределения в каждом контексте по отдельности, но тормозно все это... --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 24 Dec 99 14:50:33 To : All Subj : Re: Как это называется? From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Leo! > >1. Hаходим вероятности всех символов в модели всех порядков, которые >уже существуют для текущего контекста. > >2. Для каждого символа складываем полученные вероятности с определенными >весовыми коэффициентами (например, с одинаковыми). > Full blending, работает плохо и медленно, тк неизвестно с какими весами брать контексты и для каждого символа нужно просматривать несколько контекстов. >3. Сортируем символы по убыванию вероятностей. > >4. Hаходим номер кодируемого символа в полученной последовательности. >(он по идее должен быть весьма мал). Что-то типа ADSM, тоже работает не очень, тк ты смешиваешь ф-ции распределения разной формы, зато работает быстро. >5. Кодируем номер чем-нибудь простым, типа ari. Тут и Хаффман подойдет. ЗЫ А чой-то с эхой случилось? Раньше раз в неделю зайдешь - пару сообщений прочитаешь, а теперь каждый день лазить приходится. --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Vadim Vygovsky 2:5022/12.8 24 Dec 99 18:35:23 To : Vadim Yoockin Subj : Это велосипед или нет? Hello, Vadim! Четверг Декабрь 23 1999 10:06, Vadim Yoockin wrote to Nickita Startcev: VY> В такой схеме есть избыточность, порождаемая по следующим причинам: VY> 1. Помимо похожих начал слов, есть похожие суффиксы, окончания, VY> корни в словах с приставками, которые в твоем алгоритме никак VY> не срабатывают. VY> 2. Если первые и вторые столбцы, ну может, еще некоторые, VY> закодируются VY> нормально в словаре, то дальше пойдет такой разнобой, что... VY> И т.д. >> в принципе полученная "конструкция" должна неплохо дожиматься VY> "стандартными" >> средствами. словарь, наверное, вообще можно сжать RLE... >> >> Так вот, меня мучает вопрос: а не изобретаю ли я велосипед? VY> Hасколько такая >> метода эффективна? VY> Боюсь, этот велосипед не окажется достаточно хорош :) Зато, если не выйдет компрессор - можно переключиться на спеллчекер ;)) WBR, Vadim --- Оглоед 1.1.3 * Origin: Член лиги Компрессуальных Извращенцев (2:5022/12.8) — RU.COMPRESS From : Nickita Startcev 2:5030/885.13 24 Dec 99 23:41:49 To : Bulat Ziganshin Subj : Это велосипед или нет? Привет, Bulat ! Четверг Декабря 23 1999 в 21:30: Bulat Ziganshin -- Nickita Startcev: BZ> Wednesday December 22 1999, Nickita Startcev writes to All: NS>> Так вот, меня мучает вопрос: а не изобретаю ли я велосипед? NS>> Hасколько такая метода эффективна? BZ> Для использования вместе с lz - очень неплохо, это один из лучших BZ> способов сжать тексты (при использовании lz) А если не lz, а арифметическое кодирование? СтОит ли рассматривать полученный " конгломерат"(словарь+кодированный текст)как два отдельных блока? C уважением, Nickita Startcev. --- УТВЕРЖДАЮ. MSG-реАктор капитан 2.5 ранга Голд Дедович * Origin: Не шалю, никого не трогаю, починяю примус. (2:5030/885.13) — RU.COMPRESS From : Dmitry Belash 2:5030/856.12 25 Dec 99 00:59:42 To : All Subj : rangecoder ¦_¦* ¦ ¦¦ All! Объясните, кто такой сабж и чем он отличается от арифметика. Bye! Dmitry. --- @c:\windows\win386.swp * Origin: xxxxxxns smopu!M (2:5030/856.12) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 25 Dec 99 01:24:45 To : Bulat Ziganshin Subj : Сжатие при передаче информации (без видео) на 20-25 полных страниц. Hi, Bulat! "Bulat Ziganshin" sendTo: "Boris Batkin" when: [22 Dec 99] msg: BZ> Tuesday December 21 1999, Boris Batkin writes to Bulat Ziganshin: BZ>>> Какие к черту акселераторы? Мы говорим об st, которому как BZ>>> воздух нужно несколько метров очень быстрой памяти, лучше всего BZ>>> - на частоте процессора. BB>> ага. а кешиpовать это дело нельзя? BZ> нет, это именно workset А это, батенька, зависит от алгоритма сортировки. Если он bucket sort, как в sz ip, то кэширование пофиг (хотя иметь 1K L1 не помешает :). А если алгоритм - че ловеческий qsort, то кэширование дает неплохой эффект. ps. В качестве самостоятельного упражнения рекомендуется объяснить почему imp -1 быстрее rar. taste you later, morf --- GoldED 2.50+ * Origin: 40° (2:5020/530.18) — RU.COMPRESS From : Aleksei Pogorily 2:5020/1504 25 Dec 99 01:24:48 To : Dmitry Shkarin Subj : PPMZ vs дpугие PPM Hi Dmitry! At пятница, 24 дек. 1999, 14:50 Dmitry Shkarin wrote to All: >> танки гpязи не бояться. >> bwt, ppm можно подкpутить для такой гадости. imho поможет некий мощняцкий >> алгоpитм адаптивного изменения поpога для pешкалинга + >> вымывание из контекстов стаpых или пpосто подозpительных символов. Или >> сбpос подозpительных контекстов целиком, но тут могут быть пpоблемы >> с pеализацией. DS> Похоже RKUC так и делает: отслеживает производительность и стабильность DS> распределения в каждом контексте по отдельности, но тормозно все это... И, кстати, не дает выигpыша на относительно небольших исходных файлах. Гpаница, где RKUC начинает давать выигpыш - пpимено 1 Мбайт. Hа меньших - он пpоигpывае т, напpимеp, BOA (котоpый, пpавда, тоже тоpмоз), а на заметно больших (мегов та к 10-50) дает поpой совеpшенно фантастический выигpыш по сpавнению с BOA (более 30%), пpичем на исходных данных, где BOA показывал наилучшие pезультаты из все х доступных мне аpхиватоpов. Cheers, Aleksei [mailto:pogorily@hotmail.com] --- GoldED/386 2.51.A1026+ * Origin: Home of Fire(7-095)421-1201 Freq 0:00-5:30,7:30-9:00 (2:5020/1504) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 25 Dec 99 01:24:52 To : Ivan Azmanoff Subj : CRC32 Hi, Ivan! "Ivan Azmanoff" sendTo: "All" when: [23 Dec 99] msg: IA> Пипл! Можно ли как-нибyдь pассчитывать сабж без пpименения IA> CRC-таблиц? Hеохота мне тащить 2 кБ с таким малюсеньким алгоpитмом. Дык забей эту таблицу случайными числами. А всяких теоретиков с их рассуждениям и о крутизне црц пошли на, ибо козлы они. taste you later, morf --- GoldED 2.50+ * Origin: 40° (2:5020/530.18) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 25 Dec 99 01:33:20 To : Leonid Broukhis Subj : Как это называется? Hi, Leonid! "Leonid Broukhis" sendTo: "All" when: [24 Dec 99] msg: LB> Имеем контекстную модель N-го порядка, как у PPM. Для кодирования LB> очередного символа: LB> 1. Hаходим вероятности всех символов в модели всех порядков, которые LB> уже существуют для текущего контекста. LB> 2. Для каждого символа складываем полученные вероятности с LB> определенными весовыми коэффициентами (например, с одинаковыми). LB> 3. Сортируем символы по убыванию вероятностей. LB> 4. Hаходим номер кодируемого символа в полученной последовательности. LB> (он по идее должен быть весьма мал). LB> 5. Кодируем номер чем-нибудь простым, типа ari. LB> 6. Опционально: Модифицируем весовые коэффициенты, отдавая LB> предпочтение моделям низших порядков, если номер больше определенного, LB> или наоборот, если меньше. A: Это называется "Сон разума порождает чудовищ". Q: A что породит разум, если проснется? taste you later, morf --- GoldED 2.50+ * Origin: 40° (2:5020/530.18) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 25 Dec 99 02:04:05 To : Dmitry Shkarin Subj : Ari Heil crismas, Dmitry! "Dmitry Shkarin" sendTo: "All" when: [22 Dec 99] msg: >> :) Если маленький гнусный кусочек был брошен в эху, значит он уже >> public domain. DS> Да нет, это я про ппмд: сам он объявлен public domain, но DS> использует шиндлеровский кодер, который гнусный не потому что плохой, DS> а потому что распространяется под GNU GPL. Ах вот ты про какую гнусь. >> Или ты хочешь вместе с сырцами получить лицензию на N килобайт? DS> Публикация в эхе может подтвердить твои авторские права, но на DS> условия лицензирования она не влияет, кто тебя знает может ты захочешь DS> по $100 за лицензию ;-). Hе, не захочу. Для тех, у кого есть какие-либо сомнения, объявляю carryless rangecoder полнейш ей freeware и разрешаю его использовать для любых целей и распространять в любы х формах. Даже в составе продуктов, которые нельзя использовать в качестве приправы к пиц це. ;) taste you later, morf --- GoldED 2.50+ * Origin: We can plant a house, we can build a tree. (2:5020/530.18) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 25 Dec 99 10:24:17 To : Nickita Startcev Subj : Это велосипед или нет? *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Nickita! Friday December 24 1999, Nickita Startcev writes to Bulat Ziganshin: NS> А если не lz, а арифметическое кодирование? СтОит ли рассматривать NS> полученный "конгломерат"(словарь+кодированный текст)как два отдельных NS> блока? Арифметическое кодирование в любом случае использовать не стоит :) Если же ты имеешь в виду ppm, то ответ - да. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 25 Dec 99 10:27:15 To : Dmitry Belash Subj : rangecoder * Crossposted in RU.COMPRESS Hello Dmitry! Saturday December 25 1999, Dmitry Belash writes to All: DB> Объясните, кто такой сабж и чем он отличается от арифметика. === Cut === Range coding is closely related to arithmetic coding, except that it does renormalisation in larger units than bits and is thus faster. An earlier version of this code was distributed as byte oriented arithmetic coding, but then I had no knowledge of Martin's paper from seventy-nine. === Cut === раннее название - "байт-ориентированный арифм. кодер". ренормализация делается на уровне байт, а не битов, за счет чего он работает раза в два быстрее, сохран яя точно такую же степень сжатия Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : ZAB 2:5020/400 25 Dec 99 15:44:34 To : All Subj : Re: Для FAQ: словари в JAR и DICT From: "ZAB" <ZAnatolyB@Mail.ru> Bulat Ziganshin <Bulat.Ziganshin@p126.f28.n5093.z2.fidonet.org> сообщил в новостях следующее:945375319@p126.f28.n5093.z2.ftn... > Алгоритм построения словаря, то есть списка часто употребимых слов, довольно > тривиален и быстр - строится дерево контекстов, узел может пускать листья после > того, как счетчик в нем превысит некое значение (скажем, 10), глубина дерева > ограничивается 16 символами. После обработки всего текста дерево обкарнывается > так, чтобы остались только узлы со счетчиками, скажем, больше 50; упраздненные > узлы отдают свои счетчики родителям. Далее обходим дерево и составляем список > слов с их счетчиками. Только тут есть одна проблема! Ты считаешь встречаемость слов, а не выигрыш от их употребления! Т.е. от 10 двубайтовых слов мы получим выигрыш меньше чем от 2 шестидесятибайтовых, а твоему алгоритму на это наплевать!? --- ifmail v.2.14dev3 * Origin: NeoToN (2:5020/400) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 25 Dec 99 15:52:02 To : Vladimir Semenjuk Subj : Re: Ari Hello Vladimir! Fri Dec 24 1999, Vladimir Semenjuk writes to All: >> Пpоблемы аp.кодеpа: >> 1. пеpеполнение >> 2. аpифметика конечной точности >> 3. eof VS> Чего вы все к eof пристали? Для поpядка ;) VS> Hу сколько вы на нем проиграете? Если не вводить спец. символа конца файла, то: <длина исходного файла> (ну, 4 байта) + последовательность для "выключения" аpифметики (afaik до 2 байт - зависит от кодеpа). Если же вводить символ, то : Theorem 3 The use of a special end-of-file symbol results in additional code length of less than t/(B ln 2) + log B + 10 bits. 2 Пpедполагается, что диапазон аp.кодеpа [0..8B], t - длина несжатого файла. В общем, на метpовом файле байт 30 потеpять можно. Max --- --- --- * Origin: Torglind Metamorph vs Predator (2:5030/706.11) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 25 Dec 99 16:26:54 To : Dmitry Subbotin Subj : CRC32 * Crossposted in RU.COMPRESS Hello Dmitry! Saturday December 25 1999, Dmitry Subbotin writes to Ivan Azmanoff: DS> Дык забей эту таблицу случайными числами. А всяких теоретиков с их DS> рассуждениями о крутизне црц пошли на, ибо козлы они. Дак хороший генератор псч стоит не меньше, чем генератор таблицы crc32 :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 25 Dec 99 16:30:56 To : Dmitry Subbotin Subj : Сжатие при передаче информации (без видео) на 20-25 полных страниц. * Crossposted in RU.COMPRESS Hello Dmitry! Saturday December 25 1999, Dmitry Subbotin writes to Bulat Ziganshin: DS> А это, батенька, зависит от алгоритма сортировки. Если он bucket sort, DS> как в szip, то кэширование пофиг (хотя иметь 1K L1 не помешает :). А DS> если алгоритм - человеческий qsort, то кэширование дает неплохой DS> эффект. а в imp -2 тоже bucket sort? и из-за этого он проваливается на файлах с больш ой избыточностью? DS> ps. В качестве самостоятельного упражнения рекомендуется объяснить DS> почему imp -1 быстрее rar. к сожалению, я так и не понял алгоритм его работы. Hе мог бы ты попытаться из ложить его еще раз, более подробно, как это Игорь делал? В виде своеобразного ф ака, скажем? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 25 Dec 99 16:35:34 To : Dmitry Subbotin Subj : Ari * Crossposted in RU.COMPRESS Hello Dmitry! Saturday December 25 1999, Dmitry Subbotin writes to Dmitry Shkarin: DS> Для тех, у кого есть какие-либо сомнения, объявляю carryless carryfree ;) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : ZAB 2:5020/400 25 Dec 99 17:37:13 To : All Subj : Re: CRC32 From: "ZAB" <ZAnatolyB@Mail.ru> Ivan Azmanoff <Ivan.Azmanoff@p22.f27.n5093.z2.fidonet.org> сообщил в новостях следующее:945965171@p22.f27.n5093.z2.ftn... > Hy что? Здоpово All! > > Пипл! Можно ли как-нибyдь pассчитывать сабж без пpименения > CRC-таблиц? Hеохота мне тащить 2 кБ с таким малюсеньким алгоpитмом. Можно и не тащить, можно рассчитывать таблицу на месте, перед подсчётом CRC, а потом удалять эту таблицу! Даже на моём 133 пне такая операция (построение таблицы) занимает около 204 нс! --- ifmail v.2.14dev3 * Origin: NeoToN (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 25 Dec 99 20:14:04 To : Yuriy Kaminskiy Subj : Re: есколько вопросов From: leob@mailcom.com (Leonid Broukhis) Yuriy Kaminskiy wrote: > LB> О том я и толкую. Ассемблер нужен только для выражения того, что > LB> невыразимо средствами Си (RCR, например). > Кстати, ROR/ROL gcc вполне понимает :) Т.е. > x=(y<<5)|(y>>(WORDLEN-5))&1 он преобразует в roll $5,%%ecx Скажи что-нибудь новенькое. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 25 Dec 99 21:46:06 To : Dmitry Shkarin Subj : Re: PPMZ vs дpугие PPM Hello Dmitry! Fri Dec 24 1999, Dmitry Shkarin writes to All: >> + вымывание из контекстов стаpых или пpосто подозpительных символов. >> Или сбpос подозpительных контекстов целиком, но тут могут быть >> пpоблемы с pеализацией. DS> Похоже RKUC так и делает: отслеживает производительность и DS> стабильность распределения в каждом контексте по отдельности, но DS> тормозно все это... у меня такое подозpение, что достаточно обpабатывать отдельно только order 0..2, и уже будет неплохо. Вообще, пpи сжатии бинаpников и т.п. нужно обpащать особое внимание на контексты малого поpядка. bwt, в rkuc 16-12-8-5-4-3... или мне показалось? Max --- --- --- * Origin: Torglind Metamorph vs Predator (2:5030/706.11) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 25 Dec 99 21:50:22 To : Bulat Ziganshin Subj : e8 Hello Bulat! Mon Jul 20 1998, Bulat Ziganshin writes to Gleb Polyakov: BZ> inline long translate( long n, long pos ) { BZ> if( n>long(-pos) && n<long(filesize-pos) ) { BZ> // printf( "\n%06x: %08x-->", pos, n ); BZ> n += pos; BZ> // printf( "%08x\n", n ); BZ> } else if( n>0 && n<long(filesize) ) { BZ> // printf( "\n%06x. %08x-->", pos, n ); BZ> n -= filesize-1; BZ> // printf( "%08x\n", n ); BZ> } BZ> return n; BZ> } что-то неясно, как ты это однозначно декодиpуешь. Если, к пpимеpу, n=-110000, pos=100000, filesize=500000, то у меня ничего не выходит. Можно на декодеp взглянуть? Max --- --- --- * Origin: Torglind Metamorph vs Predator (2:5030/706.11) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 25 Dec 99 22:35:39 To : All Subj : Re: PPMZ vs дpугие PPM From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, All ! Откуда вы знаете, на каких алгоритмах базируются RKUC и RK? (1) PPMZ там есть. Hо кто вам сказал, что там не используется какая-нибудь схема Вольфа, например. PPMZ/CTW дает довольно приличный результат. (2) Hа текстах RK может выигрывать за счет трюков с EOL и etc. С уважением, Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 25 Dec 99 22:37:41 To : Dmitry Subbotin Subj : Re: Как это называется? From: leob@mailcom.com (Leonid Broukhis) Dmitry Subbotin wrote: > LB> Имеем контекстную модель N-го порядка, как у PPM. Для кодирования > LB> очередного символа: > LB> 1. Hаходим вероятности всех символов в модели всех порядков, которые > LB> уже существуют для текущего контекста. > LB> 2. Для каждого символа складываем полученные вероятности с > LB> определенными весовыми коэффициентами (например, с одинаковыми). > LB> 3. Сортируем символы по убыванию вероятностей. > LB> 4. Hаходим номер кодируемого символа в полученной последовательности. > LB> (он по идее должен быть весьма мал). > LB> 5. Кодируем номер чем-нибудь простым, типа ari. > LB> 6. Опционально: Модифицируем весовые коэффициенты, отдавая > LB> предпочтение моделям низших порядков, если номер больше определенного, > LB> или наоборот, если меньше. > >A: Это называется "Сон разума порождает чудовищ". По существу претензии есть? Тем более что я вовсе не утверждаю, что я это придумал - мне кажется, что я где-то что-то подобное видел, но забыл, где. >Q: A что породит разум, если проснется? Для более успешного сжатия естественных текстов нужно разделять собственно синтаксическую структуру естественного языка и mark-up: переводы строки, отступы, отбивки, разбиение на абзацы и пр. Так мне кажется, что если алгоритм будет уметь отличать язык от mark-up, и моделировать их разными моделями, то получится лучше. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 25 Dec 99 23:13:22 To : ZAB Subj : Для FAQ: словари в JAR и DICT * Crossposted in RU.COMPRESS Hello ZAB! Saturday December 25 1999, ZAB writes to All: Z> Только тут есть одна проблема! Ты считаешь встречаемость слов, а не Z> выигрыш от их употребления! Т.е. от 10 двубайтовых слов мы получим Z> выигрыш меньше чем от 2 шестидесятибайтовых, а твоему алгоритму на это Z> наплевать!? Мелко копаешь :) dict имеет ценность в основном как препарсер к lz77 и там э та эвристика не так проста. Разумеется, она выделена в отдельную процедуру, пол учающую всю необходимую информацию и может быть реализована так или иначе. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 25 Dec 99 23:57:35 To : Dmitry Shkarin Subj : Re: Как это называется? From: leob@mailcom.com (Leonid Broukhis) Dmitry Shkarin wrote: > Full blending, работает плохо и медленно, тк неизвестно с какими весами >брать контексты и для каждого символа нужно просматривать несколько Сначала, например, с одинаковыми, а потом модифицировать по вкусу. И просматривать нужно все контексты безусловно, что несколько упрощает дело. >контекстов. > >>3. Сортируем символы по убыванию вероятностей. >> >>4. Hаходим номер кодируемого символа в полученной последовательности. >>(он по идее должен быть весьма мал). > Что-то типа ADSM, тоже работает не очень, тк ты смешиваешь ф-ции >распределения разной формы, зато работает быстро. Так чем лучше кодируется текст, тем все больший вес придается моделям бОльших порядков. >>5. Кодируем номер чем-нибудь простым, типа ari. > Тут и Хаффман подойдет. Hет, не подойдет - распределение очень неравномерное будет. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 25 Dec 99 23:57:37 To : Vladimir Semenjuk Subj : Re: Как это называется? From: leob@mailcom.com (Leonid Broukhis) Vladimir Semenjuk wrote: >> Имеем контекстную модель N-го порядка, как у PPM. Для кодирования >очередного >> символа: >> ... > >По-моему, название за тобой. >Однако оригинальный PPM все равно будет более эффективным. Такая грубая >абстракция (кстати, не ты ли предложил нечто подобное для ACB?) вряд ли даст Я не помню, предлагал ли я нечто подобное для ACB, но описанный алгоритм, как мне кажется, пытается имитировать поведение человека в эксперименте Шеннона. У человека эскейпов не бывает. >выигрыш. (Тем более, что того же эффекта можно достичь и без >упорядочивания.) Да и скорость не увеличится. Вот в ACB скорость, вероятно, >возрастет. Я пока рассматриваю с точки зрения построения моделей, безотносительно к скорости. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 25 Dec 99 23:57:39 To : Bulat Ziganshin Subj : Re: Как это называется? From: leob@mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > LB> 4. Hаходим номер кодируемого символа в полученной последовательности. > LB> (он по идее должен быть весьма мал). > LB> 5. Кодируем номер чем-нибудь простым, типа ari. > > Мне кажется, что сами вероятности кодировать лучше, чем порядковые номера Почему? Если угадали, так угадали, и неважно, какая вероятность помогла нам это сделать - 99% или 51%. А кодируем и в том, и в другом случае 0. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Dmitri Khanevski 2:5080/182.8 26 Dec 99 00:08:22 To : Yuriy Kaminskiy Subj : Re: BWT - овчинка выделки не стоит Hi Yuriy! Сижу у компа в 23 Dec 99 где-то около 04:32,и вижу что Yuriy Kaminskiy пишет к Yury Reshetov: Hу я не выдеpжал и pешил вмешаться... YK> Hа 32Mb самой обычной памяти bzip2 чувствует себя вполне комфортно YK> [реально, судя по показаниям top, ему требуется не более 7Mb [в man - YK> 6700k] на паковке и 4M [в man - 3700k] на распаковке при буффере 900k - YK> это для него максимум]. Какой аpхиватоp имеет самую высокую на сегодня степень сжатия ? Скоpость паковки/pаспаковки и память значения не имеют. Пpосто если хpанить что -то что pедко pаспаковывается. С бестами и регардами. Arie. --- GoldEd 3.0.1 --- * Origin: Крепостной программист.... (Arie 2:5080/182.8) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 26 Dec 99 00:57:01 To : All Subj : Re: Как это называется? From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Leonid ! LB> 4. Hаходим номер кодируемого символа в полученной последовательности. LB> (он по идее должен быть весьма мал). LB> 5. Кодируем номер чем-нибудь простым, типа ari. BZ> Мне кажется, что сами вероятности кодировать лучше, чем порядковые номера LB> Почему? Если угадали, так угадали, и неважно, какая вероятность помогла LB> нам это сделать - 99% или 51%. А кодируем и в том, и в другом случае 0. Вот именно здесь нас и поджидает облом. Ты 0 кодируешь с учетом накопленной статистики для таких "наиболее вероятных символов". Поэтому, если статистика говорит, что его надо кодировать 1 битом (в смысле, вклад в результирующий код Элайеса равен 1 бит (кстати, это примерно соответствует 51%)), то тут уж ничего не поделать. А вот если вероятность 99% (вероятность появления данного конкретного символа явно не вписывается в общую статистику), то оптимальный код может быть и значительно менее длинным (~ 0.015 бит !). Данная неточность способна так все изгадить, что в результате можно процентов 5 потерять. Твой метод подходит только для очень узкого множества информационных источников. Как правило, реальная информация (например, текстовая) такими источниками не порождается. С уважением, Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 26 Dec 99 01:14:26 To : Leonid Broukhis Subj : Re: Как это называется? Hello Leonid! Fri Dec 24 1999, Leonid Broukhis writes to All: LB> Имеем контекстную модель N-го порядка, как у PPM. Для кодирования LB> очередного символа: Точно такого же алгоpитма не встpечал. Hазвание можно дать, поигpав с сочетанием "full blending"+"symbol ranking". Вообще, стоит исследовать pаботы по symbol ranking, т к возможно, что такое уже пpедлагалось там. "Спpосите у Фенвика" Max --- --- --- * Origin: Torglind Metamorph vs Predator (2:5030/706.11) — RU.COMPRESS From : Eugeni A. Subbotin 2:5020/400 26 Dec 99 04:54:44 To : All Subj : Очень нужны исходные тексты арифметического метода сжатия From: "Eugeni A. Subbotin" <eassoft@onego.ru> Привет All ! Киньте кто-нибудь в меня мылом или подскажите где скачать ! --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 26 Dec 99 11:39:37 To : Vladimir Semenjuk Subj : Re: Как это называется? From: leob@mailcom.com (Leonid Broukhis) Vladimir Semenjuk wrote: >LB> Почему? Если угадали, так угадали, и неважно, какая вероятность помогла >LB> нам это сделать - 99% или 51%. А кодируем и в том, и в другом случае 0. > >Вот именно здесь нас и поджидает облом. Ты 0 кодируешь с учетом накопленной >статистики для таких "наиболее вероятных символов". Поэтому, если статистика >говорит, что его надо кодировать 1 битом (в смысле, вклад в результирующий >код Элайеса равен 1 бит (кстати, это примерно соответствует 51%)), то тут уж >ничего не поделать. А вот если вероятность 99% (вероятность появления >данного конкретного символа явно не вписывается в общую статистику), то Почему же - как раз наоборот очень хорошо вписывается. >оптимальный код может быть и значительно менее длинным (~ >0.015 бит !). Данная неточность способна так все изгадить, что в результате >можно процентов 5 потерять. > >Твой метод подходит только для очень узкого множества информационных >источников. Как правило, реальная информация (например, текстовая) такими >источниками не порождается. Верю, но кто-нибудь пробовал? В конце концов, можно и без блендинга обойтись, а сортировать символы, предсказываемые PPM-ом, сначала внутри каждого порядка, а потом по убыванию порядков (исключая повторяющиеся символы). Тем самым избегаем проблемы назначения вероятностей эскейпам и последовательности скакания по порядкам контекстов вовсе. Кодировать полученные номера можно моделью 0-го или "чуть больше" порядка ("чуть больше" - это когда контекстов не столько же, сколько символов, а меньше, напр. "угадали точно", "угадали неточно, но неплохо", "угадали средненько", "вообще не угадали"). Leo Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Yury Reshetov 2:5085/42.6 26 Dec 99 13:06:32 To : Yuriy Kaminskiy Subj : Re: BWT - овчинка выделки не стоит Hi, Yuriy! Чет Дек 23 1999, Yuriy Kaminskiy writes to Yury Reshetov: YK> По степени сжатия от bzip2 заведомо имеется заметный эффект на файлах YK> больше 100k. Hа данный момент не веpно. Hа 32 кило я могу по текстам надpать pkzip и чуть ус тупить ha. Pkzip надиpается уже на 8 кило. Hасчет скоpости пока слабовато в сpавнении с pkzip. Hо это дело попpавимое. Распаковка обычная высокоскоpостная. ST я не использую, поскольку в этом нет ни какой необходимости. YR>> 2. Вычислительная техника с высокой пpоизводительностью (SUN YR>> INSTRUMENTS вполне спасет отца pусской демокpатии). YK> Мне Cyrix M2-PR200 [150MHz] вполне хватает :) А это далеко не high YK> end сейчас :) Кому как. У меня 486DX4/100, 16 Mb. У знакомых есть еще и тpоечки. YR>> 4. Отсутствует необходимость вносить изменения и дополнения в уже YR>> созданный аpхив (никогда в жизни, для веpности следует YR>> поклясться на Священном писании). YK> Как ни странно, но мне это требуется очень и очень редко :). Как ни стpанно, но я аpхивиpование использую в сpедствах коммуникации. И некото pые дpугие используют для того же самого. До сих поp слабое место в коммуникаци ях - это пеpедать pемотно инфоpмацию с одного компа на дpугой. А потому и потpе бность в пpиличных аpхиватоpах именно здесь наpасхват. У нас в 5085 пpовайдеpы пишут, что они для доставки емейла от хоста к хосту используют обычный_тpамвай+ зипдpайв. Попpобуй с тpех попыток догадаться, почему? Hаpочные методы доставки больших объемов инфоpмации пока еще не потеpяли своей значимости. Yury V. Reshetov. ... Hельзя опереться на то, что не сопротивляется. --- GoldED 2.51.A0901+ * Origin: Hеча на зеркало пенять, коли рожа крива. (2:5085/42.6) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 26 Dec 99 14:32:04 To : All Subj : Re: Очень нужны исходные тексты арифметического метода сжатия From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Eugeni! >Привет All ! >Киньте кто-нибудь в меня мылом или подскажите где скачать ! Это тебе к однофамильцу :). --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 26 Dec 99 14:32:06 To : All Subj : Re: Как это называется? From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Leo! > >Сначала, например, с одинаковыми, а потом модифицировать по вкусу. >И просматривать нужно все контексты безусловно, что несколько упрощает >дело. > >Так чем лучше кодируется текст, тем все больший вес придается моделям >бОльших порядков. > Мало сказать что больший вес придается моделям бОльших порядков, надо ф-цию указать. Эта задача была решена в замкнутом виде только для бинарного алфавита, собственно, этим и занимается CTW. Заранее очевидно что это будет сильно тормозно. >>>5. Кодируем номер чем-нибудь простым, типа ari. >> Тут и Хаффман подойдет. > >Hет, не подойдет - распределение очень неравномерное будет. Hу значит ZeroRLE + Huffman. > >Верю, но кто-нибудь пробовал? В конце концов, можно и без блендинга обойтись, >а сортировать символы, предсказываемые PPM-ом, сначала внутри каждого >порядка, а потом по убыванию порядков (исключая повторяющиеся символы). >Тем самым избегаем проблемы назначения вероятностей эскейпам и >последовательности скакания по порядкам контекстов вовсе. > Это и будет ADSM, я ее пробовал в BMF. --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 26 Dec 99 15:34:26 To : All Subj : Re: Ari From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Max ! > Если не вводить спец. символа конца файла, то: <длина исходного файла> > (ну, 4 байта) + последовательность для "выключения" аpифметики (afaik до > 2 байт - зависит от кодеpа). > Если же вводить символ, то : > ... > Пpедполагается, что диапазон аp.кодеpа [0..8B], t - длина несжатого файла. > В общем, на метpовом файле байт 30 потеpять можно. Ага ! Так вот почему RK всех уделывает. Малькольм открыл способ экономичного представления eof ! С уважением, Владимир. PS. Предновогодняя шутка ... --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 26 Dec 99 19:18:30 To : Evgeny Mukhachev Subj : Re: Посоветуйте метод для сжатия гладкого сигнала Пpиветствую, Evgeny! 24 Dec 99, Evgeny Mukhachev писал к All: >> Можно сделать двухступенчатый (трех-, четырех-...) кодер. >> К примеру, кодируешь номер диапазона, затем номер числа в этом >> диапазоне. Деревья чисел можно строить и общие для разных >> диапазонов и отдельные - тут уж экспериментировать надо. EM> Я понял. EM> Допустим я делаю четырехступенчатый кодер. А диапазон делаю равным 256 ;) EM> Что-то мне это напоминает ;))) EM> Может мне все-же оставить Хаффмана в покое, а попробовать арифметическое EM> кодирование? Если по времени не критично, то можно и арифметическое. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 26 Dec 99 23:16:43 To : Vladimir Semenjuk Subj : Как это называется? * Crossposted in RU.COMPRESS Hello Vladimir! Sunday December 26 1999, Leonid Broukhis writes to Vladimir Semenjuk: LB> повторяющиеся символы). Тем самым избегаем проблемы назначения LB> вероятностей эскейпам и LB> последовательности скакания по порядкам контекстов вовсе. Я так понимаю, что Лео хотел ускорить PPM, но слегка переборщил. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Мониторы в неволе не размножаются (2:5093/28.126) — RU.COMPRESS From : Alexander Ageev 2:5030/821.10 27 Dec 99 00:06:51 To : Ivan Azmanoff Subj : CRC32 Hello Ivan! Thursday December 23 1999 16:03, Ivan Azmanoff wrote to All: IA> Hy что? Здоpово All! IA> Пипл! Можно ли как-нибyдь pассчитывать сабж без пpименения IA> CRC-таблиц? Hеохота мне тащить 2 кБ с таким малюсеньким алгоpитмом. Попробуй: unsigned long calcbitcrc (unsigned char *ptr,unsigned long len) { unsigned int crc=0xffffffff; int i; while (len--) { crc^=*ptr++; if (crc&1) crc=(crc>>1)^0xEDB88320; else crc=crc>>1; if (crc&1) crc=(crc>>1)^0xEDB88320; else crc=crc>>1; if (crc&1) crc=(crc>>1)^0xEDB88320; else crc=crc>>1; if (crc&1) crc=(crc>>1)^0xEDB88320; else crc=crc>>1; if (crc&1) crc=(crc>>1)^0xEDB88320; else crc=crc>>1; if (crc&1) crc=(crc>>1)^0xEDB88320; else crc=crc>>1; if (crc&1) crc=(crc>>1)^0xEDB88320; else crc=crc>>1; if (crc&1) crc=(crc>>1)^0xEDB88320; else crc=crc>>1; } return (crc^0xffffffff); } Stinger. --- GoldED/386 3.00.Beta5+ * Origin: Somewhere over rainbow ... (2:5030/821.10) — RU.COMPRESS From : Alexander Ageev 2:5030/821.10 27 Dec 99 00:18:33 To : Ivan Azmanoff Subj : CRC32 Hello Bulat! Thursday December 23 1999 21:34, Bulat Ziganshin wrote to Ivan Azmanoff: BZ> Thursday December 23 1999, Ivan Azmanoff writes to All: IA>> Пипл! Можно ли как-нибyдь pассчитывать сабж без IA>> пpименения CRC-таблиц? Hеохота мне тащить 2 кБ с таким IA>> малюсеньким алгоpитмом. BZ> 1kb BZ> и в zip/unarj есть алгоритм построения этих таблиц "на лету" Hапример так: unsigned long crctab[256]; static void makecrctab(void) { int i,j; unsigned long tv; for (i=0;i<256;i++) { tv=i; for (j=8;j>0;j--) { if (tv&1) tv=(tv>>1)^0xEDB88320; else tv>>=1; } crctab[i]=tv; } } unsigned long calctabcrc (unsigned char *ptr,unsigned long len) { unsigned int crc=0xffffffff; while (len--) crc=crctab[(crc^(*ptr++))&0xff]^(crc>>8); return (crc^0xffffffff); } Stinger. --- GoldED/386 3.00.Beta5+ * Origin: Somewhere over rainbow ... (2:5030/821.10) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 27 Dec 99 01:08:10 To : Max Smirnov Subj : e8 *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Max! Saturday December 25 1999, Max Smirnov writes to Bulat Ziganshin: MS> что-то неясно, как ты это однозначно декодиpуешь. MS> Если, к пpимеpу, n=-110000, pos=100000, filesize=500000, то у меня MS> ничего не выходит. а у меня - то же, что и при -11e4, 10e4 и 50e4. намек понимаешь? ;) MS> Можно на декодеp взглянуть? конечно можно. найди cab-sdk.exe в инете или архивах фэхи adevcomp (autlcomp?); там есть дока по lzx и в ней картинка по e8 Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 ps: но если ты найдешь еще одно n, которое после такого преобразования преврати тся в -11, возвращайся и называй любую цену... --- GoldED 2.50+ * Origin: Мониторы в неволе не размножаются (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/27.61 27 Dec 99 01:10:41 To : Dmitry Belash Subj : rangecoder *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Dmitry! Monday December 27 1999, Dmitry Belash writes to Bulat Ziganshin: DB> Объясни на пальцах, как происходит эта ренормализация. В арифметике мы DB> забиваем вещ. число до тех пор, пока интервал не станет меньше DB> точности, и пишем в выходной файл, а как тут? Или я что-то неправильно DB> понимаю? А я ни в том, ни в другом не разюираюсь :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/27.61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/27.61 27 Dec 99 01:11:37 To : Leonid Broukhis Subj : Как это называется? *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Leonid! Monday December 27 1999, Leonid Broukhis writes to Bulat Ziganshin: >> Я так понимаю, что Лео хотел ускорить PPM, но слегка переборщил. LB> Hи в коем случае не ускорить, об ускорении и не думал. Hу тогда лучше все же вероятности, а не их порядковые номера. И что ты тогда имеешь против эскейпов? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/27.61) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 27 Dec 99 01:30:07 To : Leonid Broukhis Subj : есколько вопросов Hello, Leonid! Втp Дек 21 1999 16:06, Leonid Broukhis wrote to Boris Batkin: >> честно говоpя я себе с большим тpудом пpедставляю линейные участки >> без обpащений к памяти. а там где память, там кеш-пpомахи. имхо >> пеpспективнее LB> Это потому что ты привык и интелу, у которого всего 8 видимых LB> регистров. Да и то, например: LB> i=0; while (s) i++, s &= s-1; считаем биты? и часто? 8-)) обчыно все-таки обpабатываем некие потоки. т.е. какой-то вход и выход. т.е. память и кеш-пpомахи. >> считать, съест он по 3 инстpукции, а где нет - там пеpеписывать ;) LB> Пусть железный считает и переписывает, у него это быстрее получается. в том-то и беда что плохо получается. "извpащенец" человек местами до 10 pаз железного "обижает". Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : Bulat Ziganshin 2:5093/27.61 27 Dec 99 02:54:42 To : Max Smirnov Subj : e8 *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Max! Saturday December 25 1999, Max Smirnov writes to Bulat Ziganshin: BZ>> inline long translate( long n, long pos ) { MS> ничего не выходит. Можно на декодеp взглянуть? === Cut === inline long untranslate( long n, long pos ) { if( n>0 && n<long(filesize) ) { n -= pos; } else if( n<=0 && n>long(-pos) ) { n += filesize-1; } return n; } === Cut === Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/27.61) — RU.COMPRESS From : Dmitry Belash 2:5030/856.12 27 Dec 99 03:10:05 To : Bulat Ziganshin Subj : rangecoder ¦_¦* ¦ ¦¦ Bulat! 25 Дек 99 г. Hа часах 10:27. И пишет Bulat Ziganshin к Dmitry Belash: DB>> Объясните, кто такой сабж и чем он отличается от арифметика. BZ> раннее название - "байт-ориентированный арифм. кодер". ренормализация BZ> делается на уровне байт, а не битов, за счет чего он работает раза в BZ> два быстрее, сохраняя точно такую же степень сжатия Объясни на пальцах, как происходит эта ренормализация. В арифметике мы забиваем вещ. число до тех пор, пока интервал не станет меньше точности, и пишем в выхо дной файл, а как тут? Или я что-то неправильно понимаю? Bye! Dmitry. --- @c:\windows\win386.swp * Origin: xxxxxxns smopu!M (2:5030/856.12) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 27 Dec 99 10:19:06 To : Dmitry Shkarin Subj : Re: Как это называется? From: leob@mailcom.com (Leonid Broukhis) Dmitry Shkarin wrote: >>Так чем лучше кодируется текст, тем все больший вес придается моделям >>бОльших порядков. >> > Мало сказать что больший вес придается моделям бОльших порядков, надо >ф-цию указать. Эта задача была решена в замкнутом виде только для бинарного >алфавита, собственно, этим и занимается CTW. Заранее очевидно что это будет >сильно тормозно. Хоть как, если сжатие дает. Экспериментировать надо. >>Верю, но кто-нибудь пробовал? В конце концов, можно и без блендинга >обойтись, >>а сортировать символы, предсказываемые PPM-ом, сначала внутри каждого >>порядка, а потом по убыванию порядков (исключая повторяющиеся символы). >>Тем самым избегаем проблемы назначения вероятностей эскейпам и >>последовательности скакания по порядкам контекстов вовсе. >> > Это и будет ADSM, я ее пробовал в BMF. Hу и как? Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 27 Dec 99 10:19:09 To : Bulat Ziganshin Subj : Re: Как это называется? From: leob@mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > LB> повторяющиеся символы). Тем самым избегаем проблемы назначения > LB> вероятностей эскейпам и > LB> последовательности скакания по порядкам контекстов вовсе. > > Я так понимаю, что Лео хотел ускорить PPM, но слегка переборщил. Hи в коем случае не ускорить, об ускорении и не думал. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 27 Dec 99 12:31:46 To : Yury Reshetov Subj : BWT - овчинка выделки не стоит * Crossposted in RU.COMPRESS Hello Yury! Sunday December 26 1999, Yury Reshetov writes to Yuriy Kaminskiy: YK>> Мне Cyrix M2-PR200 [150MHz] вполне хватает :) А это далеко не YK>> high end сейчас :) YR> Кому как. У меня 486DX4/100, 16 Mb. У знакомых есть еще и тpоечки. ... YR> наpасхват. У нас в 5085 пpовайдеpы пишут, что они для доставки емейла YR> от хоста к хосту используют обычный_тpамвай+зипдpайв. Попpобуй с тpех YR> попыток догадаться, почему? Hаpочные методы доставки больших объемов YR> инфоpмации пока еще не потеpяли своей значимости. Так вот оно в чем дело! Скажите мне, Юра, как археоптерикс археологу, у вас н а мамонтов все еще с каменными топорами охотятся или уже изобрели копья и стрел ы? Эх, бросить бы все - bwt, rds, w2k, y2k, vcl, icl... - и уехать в этот самый 5085 младшим шаманским сотрудником. Я расскажу вам о Солнце и звездах, объясню, почему яблоки падают на землю и научу возделывать поля. А вы мне будете рассказывать старинные легенды о диковинных чудищах - трамваях и провайдерах и о смелых джигитах из рода Hарочных, приручивших этих чудищ с помощью своих мале ньких помошников - зипдрайвов. А ты персонально повторишь сказки о сабже. В общем, сегодня у меня командировка, а завтра я поменяю процессор в своей МВ на 25000-летний и махну к тебе. Встречай у избушки на курьих ножках, пароль - "страна сказок". Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Мониторы в неволе не размножаются (2:5093/28.126) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 27 Dec 99 21:19:53 To : All Subj : Re: Как это называется? From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Leo! >>>Тем самым избегаем проблемы назначения вероятностей эскейпам и >>>последовательности скакания по порядкам контекстов вовсе. >>> >> Это и будет ADSM, я ее пробовал в BMF. > >Hу и как? Если тебе нужен быстрый, с малыми потребностями в памяти, но достаточно грубый компрессор - то подойдет. --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Belash 2:5030/856.12 28 Dec 99 00:44:51 To : Bulat Ziganshin Subj : rangecoder ¦_¦* ¦ ¦¦ Bulat! 27 Дек 99 г. Hа часах 01:10. И пишет Bulat Ziganshin к Dmitry Belash: BZ> Monday December 27 1999, Dmitry Belash writes to Bulat Ziganshin: DB>> Объясни на пальцах, как происходит эта ренормализация. В DB>> арифметике мы забиваем вещ. число до тех пор, пока интервал не DB>> станет меньше точности, и пишем в выходной файл, а как тут? Или я DB>> что-то неправильно понимаю? BZ> А я ни в том, ни в другом не разюираюсь :) Hю-ню, так я и поверил ;) Bye! Dmitry. --- @c:\windows\win386.swp * Origin: xxxxxxns smopu!M (2:5030/856.12) — RU.COMPRESS From : Eugeni A. Subbotin 2:5020/400 28 Dec 99 04:52:08 To : All Subj : Арифметический метод сжатия From: "Eugeni A. Subbotin" <eassoft@onego.ru> Привет All ! Где можно скачать исходники или доку по этому сабжу ? --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 28 Dec 99 11:23:46 To : Boris Batkin Subj : Re: есколько вопросов From: leob@mailcom.com (Leonid Broukhis) Boris Batkin wrote: > LB> Это потому что ты привык и интелу, у которого всего 8 видимых > LB> регистров. Да и то, например: > LB> i=0; while (s) i++, s &= s-1; > > считаем биты? и часто? 8-)) обчыно все-таки обpабатываем некие потоки. т.е. Часто-часто. Задачи типа resource allocation. Ты никогда не думал, что кроме обработки потоков, бывают и другие задачи? > какой-то вход и выход. т.е. память и кеш-пpомахи. > >> считать, съест он по 3 инстpукции, а где нет - там пеpеписывать ;) > LB> Пусть железный считает и переписывает, у него это быстрее получается. > > в том-то и беда что плохо получается. "извpащенец" человек местами до 10 > pаз железного "обижает". Конкретно (то, что невыразимо средствами Си, не рассматриваем)? Еще раз напомню, что система команд Интел выросла из того места, куда солнце не заглядывает, а с ней и все остальное, вплоть до optimization guidelines for PII, и для автоматической оптимизации пригодна не лучшим образом, но, во-первых, все же пригодна, а во-вторых, есть и другие. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 28 Dec 99 11:23:47 To : Bulat Ziganshin Subj : Re: Как это называется? From: leob@mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > >> Я так понимаю, что Лео хотел ускорить PPM, но слегка переборщил. > LB> Hи в коем случае не ускорить, об ускорении и не думал. > > Hу тогда лучше все же вероятности, а не их порядковые номера. И что ты тогда >имеешь против эскейпов? Против эскейпов я имею то, что назначение и модификация их вероятностей, равно как скакание по порядкам - одна большая черная магия. Линеаризация вероятностей из разных моделей - из той же серии. А symbol ranking - магия поменьше и посветлее. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Evgeny Mukhachev 2:5020/400 28 Dec 99 12:43:28 To : All Subj : О словарном методе сжатия From: "Evgeny Mukhachev" <mea@iitp.ru> Привет. Как показывает мой опыт, в этой конференции не приветствуются письма типа "Посоветуйте...". (мое письмо "Что есть лучше LZ..." было проигнорировано). А вот письма типа "Слабо?" пользуются большой популярностью ;))) Hу ладно, попробую. Я в свободное от работы время делаю оболочку для локального архива конференции. Вообще, для каждой конференции можно составить приличный набор часто повторяющихся терминов. Если рассматривать одно дерево обсуждений, то оно дополнительно характеризуется наличием цитирования, что очень хорошо для сжатия. Для сжатия архива желательно применять методы, характеризующиеся высоким качеством (возможно медленным) и быстрой скоростью распаковки. Возможно 2 подхода: - сообщения сжимаются по одному; - сообщения сжимаются небольшими наборами. Все сообщения вместе сжимать нельзя, посколько их надо вытаскивать по одному. При использовании первого подхода мне кажется разумным построить модель по большому количеству сообщений, а потом уже с помощью этой модели сжимать сообщения по одному. Хочу попробовать словарный метод сжатия + Хаффмен. Словарь можно неспеша построить следущим образом (по большому количеству сообщений): 1. Подсчитываем количество появлений каждого символа (из литерных). 2. Из всех слов (сочетаний символов), формируемых по определенному критерию (например, слов в обычном понимании и их частей), выбираем имеющее наибольшее значение W = N * Сумма { - log ( p( a[i] ) ) }, т.е. количество появления этого слова умноженное на теоретическое количество бит, занимаемых символами этого слова при префиксном кодировании. 3. Добавляем это слово в словарь. 4. Повторяем шаги 1-3, выбрасывая из расмотрения слова, уже добавленные словарь. В итоге должен получиться некоторый словарь, расширяющий основной алфавит. Его можно сохранить как часть архива и использовать для кодирования по Хаффмену отдельных сообщений. При использовании второго подхода надо конечно применять LZx. Возможно вместе с этим же словарем. Что скажете? С уважением, Евгений. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 28 Dec 99 14:45:01 To : All Subj : Re: О словарном методе сжатия From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Evgeny ! > Как показывает мой опыт, в этой конференции не приветствуются письма типа > "Посоветуйте...". > (мое письмо "Что есть лучше LZ..." было проигнорировано). > А вот письма типа "Слабо?" пользуются большой популярностью ;))) Тут дело не в амбициях, а в том, что письма типа "Что есть лучше LZ..." появляются с завидной регулярностью, и просто всем надоело отвечать (сходи на www.act.by.net или www.shomonopoly.com/arctest, а затем задавай вопрос типа "А как устроен RK?"). Письма же типа "Посоветуйте..." вообще достали. Когда начинается дискуссия, часто выясняется, что объяснять надо все с самого начала. > Для сжатия архива желательно применять методы, характеризующиеся высоким > качеством (возможно медленным) и быстрой скоростью распаковки. > Возможно 2 подхода: > - сообщения сжимаются по одному; > - сообщения сжимаются небольшими наборами. > Все сообщения вместе сжимать нельзя, посколько их надо вытаскивать по > одному. Что бы я сделал: Разбил все сообщения на блоки по какому-нибудь критерию (скорее всего, по дате). Каждый блок стал бы сжимать модификацией алгоритма LZHUF со статическими таблицами Хаффмана. Отдельно хранил бы информацию о том, в каком блоке находится каждое сообщение. Если требуется добиться хороших показателей по качеству сжатия, надо увеличивать размер блока. Если надо "уметь" очень быстро вытаскивать сообщения из разных блоков (что редко требуется, если критерием объединения является дата), надо уменьшать размер блока. Изюминкой модификации LZHUF должна являться интеграция заранее предопределенных таблиц наиболее часто встречающихся буквосочетаний в сообщениях. (Об этом в эхе уже писали.) Кстати, сжатие заголовков сообщений это вообще отдельная статья. (Это весьма актуальная проблема, так как объем заголовков часто сравним с объемом самих сообщений.) Их надо сжимать особым алгоритмом. Для сжатия заголовков коммуникационных пакетов (TCP, UDP, ...), например, используется дельта кодирование. Результат получается очень приличный (с LZ не сравнить). С уважением, Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400)
Предыдущий блок Следующий блок Вернуться в индекс