| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Dmitry Pyankov 2:5020/400 19 Apr 99 17:47:43 To : All Subj : IRC : #ARH !!!??? From: "Dmitry Pyankov" <dp@fmf.gasu.gorny.ru> Hello, All! Замечаю, что многие подписчики данной эхи имеют доступ к инету, а другие и вовсе с Fido мало знакомы. Почему бы не встречаться на IRC - канале, например #ARH ???!!! Можно было бы решить некоторые проблемы в реальном времени - да и просто пообщаться на тему... Жду all на #ARH ;) ! ps. Судя по данным теста, выложенным на chat.ru/~arctest на данный момент наилучший результат паковки EXE файлов дает APACK0.98 это верно или информация устарела? С наилучшими, Дима. --- ifmail v.2.14dev3 * Origin: Unknown (2:5020/400) — RU.COMPRESS From : Sergey G Subbotin 2:5020/1998.90 19 Apr 99 19:24:00 To : Sergey Derevyago Subj : Re: Задача Привет, Sergey! Когда-то, Пон Апp 12 1999 10:15, Sergey Derevyago писал к All с сабжектом "Задача": SD> но диспеpсия довольно велика. так. это имхо ключевая фpаза. (или я ничего не понимаю...) не означает ли это, что модуль pазности между двумя соседними будет больше 128 ? Если да, то можно пpовести 'пеpеобозначение' символов, т.е. напpимеp симв. 0x45 будет соответствовать 0xF4 пpичём пеpеобозначение делать таким обpазом, чтобы ситуация стала обpатной, т.е. модуль pазности между двумя соседними <=128 после таких пpеобpазований пихаем пеpвый байт, а затем уpезаем pазность (не модуль!) до 7 бит и пихаем по 7 бит на выход. После всего этого можно запихнуть и табличку из 256 элементов - пеpеобозначений символов. Если нет, то у меня есть запасной ваpиант: можно пpовести пеpеpаспpеделение байт во входном потоке (именно пеpеpаспpелеление, а не пеpеобозначение) - пеpеpаспpеделение пpоводить по конкpетному алгоpитму - что-то вpоде: for (j=0; j<max/256; j++) for (i=0; i<256; i++) Output[j*256+i]=Input[i*256+j]; (циклы _именно_ в таком поpядке, буквы i и j в записях масивов я не пеpепутал.) затем полученную запись pазделить на 256 блоков. и в каждом блоке - фоpмат записи - см. выше - т.е. модули pазности... Сергей Г. Субботин E-Mail : Sergey.Subbotin@AltaVista.Net --- * Origin: Hе всё то Windows, что висит (2:5020/1998.90) — RU.COMPRESS From : Vadim Vygovsky 2:5022/12.8 19 Apr 99 21:41:48 To : Dmitry Pyankov Subj : IRC : #ARH !!!??? Hello, Dmitry! Понедельник Апрель 19 1999 17:47, Dmitry Pyankov wrote to All: DP> ;) ! ps. Судя по данным теста, выложенным на chat.ru/~arctest на DP> данный момент наилучший результат паковки EXE файлов дает APACK0.98 DP> это верно или информация устарела? UPX 0.70 --best порою лучшее. WBR, Vadim --- Оглоед 3.00.Beta5+ * Origin: Член лиги Компрессуальных Извращенцев (2:5022/12.8) — RU.COMPRESS From : Roman Lavrentev 2:5030/821.33 19 Apr 99 22:03:37 To : Bulat Ziganshin Subj : ACB ver.1.23c:2 Hi Bulat Ziganshin! Bulat Ziganshin wrote in a message to Roman Lavrentev: RL> Гм, Вадим, это не корректно!! При чем здесь новая версия?? RL> Тогда уж и jar, arj и cabarc надо брать 99 года! Только их нет пока, RL> у меня по крайней мере... BZ> Ты вроде в Питере? Фэхи RAR, AUTLCOMP. Да, я в Питере :(( Спасибо большое за совет, приму к сведению... BZ> Конечно, с чем сравнивать программы 97-го года - с RAR 96-го BZ> или 99-го - это вопрос тонкий ;) hm... я так понял, что ты, Bulat, очень поднял себе настроение, читая мое письмо :( Однако ничего смешного писать я вобщем-то не собирался, я просто черезмерно криво высказался. Попробую исправиться. Я желал сказать, что сравнивал архиваторы, которыми сейчас народ пользуется... И вовсе, imho, неинтересно проводить тест, ориентируясь лишь на год выпуска архиватора. Гм, нет, это конечно неплохо, но цель стояла иная, так что... RL> Да нет, я не то имел в виду! Я писал о том, что у Рара в принцепе RL> нет нИши, которую бы он твердо занимал: он везде "посерединке", нет RL> параметра где он бы однозначно "рулил". BZ> У него давно есть ниша "zip'а для русских". А есть какая-нибудь информация о пользовании иностранными гражданами этим программным продуктом (это я о Раре)? Bye... NapalmeR.[SoD] •Soldiers Of Destiny• [ TEAM Rage Of Dying Animal ] --- * Origin: my grief is deep, my days are dim... (2:5030/821.33) — RU.COMPRESS From : Roman Lavrentev 2:5030/821.33 19 Apr 99 22:17:37 To : Viktor Ostashev Subj : ACB ver.1.23c:3 Hi Viktor Ostashev! Viktor Ostashev wrote in a message to Roman Lavrentev: VO> Так это и есть его ниша. RAR ни по одномy паpаметpy не VO> стоит на пеpвом месте, но нет ни одного аpхиватоpа, котоpый VO> опеpежал бы RAR по всем паpамет- pам одновpеменно. Так что VO> RAR - это yнивеpсальный аpхиватоp, тягаться с ним может VO> pазве что tar/gzip. Hе хотелось бы особенно впадать в споры, а уж тем более как-то наводить тень на программу-архиватор Rar, но думается что все-таки она обладает огромным плюсом. Который состоит в том, что сделана она в России, и в этой самой России она почему-то совершенно дико "разошлась" и стала "в мясо" популярной. Однако в ответ на твои возрожения, Виктор, я хотел бы сказать следующее: когда тебе надо заархивировать данные, то сначала ты ставишь цель (например быстро запаковать, или запаковать в наименьший размер, не учитывая затрачиваемого времени...). Вот только если ты пользуешься Раром, то значит твой девиз звучит примерно так: "надо заархивировать не очень быстро и в результате получить не очень маленький архив" :) Hе кажется, что это очень странная цель? Думаю доказательство от противного состоялось... :( Bye... NapalmeR.[SoD] •Soldiers Of Destiny• [ TEAM Rage Of Dying Animal ] --- * Origin: my grief is deep, my days are dim... (2:5030/821.33) — RU.COMPRESS From : Vsevolod Fedotov 2:5020/500 20 Apr 99 00:43:48 To : Bulat Ziganshin Subj : WI Monday April 19 1999 13:52, you wrote to me: VF>> угу, это реализация wavelet от фирмы summus. BZ> Где можно взять или украсть? :) сие мне неведомо. :( на http://www.summus.com/products/4u2c/4u2c_products.html сейчас только вьюверы дают, и сэмплы. BZ> Как я понял, поддержка этого формата прям в комплекте PS. Коммерческий BZ> сам PS или нет - я не в курсе. увы-увы. прям в комплекте photoshop (5.0.x) ничего такого нет. а summus продает plugin за $149. BZ> PS: Первое письмо от модератора за последние полгода :) просто все себя хорошо ведут :) Vsevolod --- * Origin: ### VSF&K ### (2:5020/500) — RU.COMPRESS From : Bulat Ziganshin 2:5093/29.61 20 Apr 99 09:50:26 To : Vadim Vygovsky Subj : IRC : #ARH !!!??? * Crossposted in RU.COMPRESS Hello Vadim! Monday April 19 1999, Vadim Vygovsky writes to Dmitry Pyankov: DP>> ;) ! ps. Судя по данным теста, выложенным на chat.ru/~arctest DP>> на данный момент наилучший результат паковки EXE файлов дает DP>> APACK0.98 это верно или информация устарела? VV> UPX 0.70 --best порою лучшее. afaik единственное преимущество apack - алгоритм упаковки релокаций, разработанный вездесущим Димой Борток :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Зубные клетки не восстанавливаются (2:5093/29.61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/29.61 20 Apr 99 09:52:48 To : Dmitry Pyankov Subj : IRC : #ARH !!!??? * Crossposted in RU.COMPRESS Hello Dmitry! Monday April 19 1999, Dmitry Pyankov writes to All: DP> Замечаю, что многие подписчики данной эхи имеют доступ к инету, а DP> другие и вовсе с Fido мало знакомы. Почему бы не встречаться на IRC - DP> канале, например #ARH ???!!! Можно было бы решить некоторые проблемы в DP> реальном времени - да и просто пообщаться на тему... Жду all на #ARH В чем преимущество эхи - она у меня архивируется, чего я не стал бы делать с irc-шными логами. btw - помимо имени канала надо указывать irc-сеть или хотя бы имя сервера. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Зубные клетки не восстанавливаются (2:5093/29.61) — RU.COMPRESS From : Cheklin Alex 2:5020/400 20 Apr 99 10:18:33 To : All Subj : Re: decompressor for NW From: "Cheklin Alex" <son@metib.ru> Cheklin Alex пишет в сообщении ... Проблема : АРКСЕРВОМ переписали каталог в другое место и стерли, некоторые файлы были сжаты . Они в сжатом виде и переписались. Есть ли возможность распаковать сжатые NW файлы ? Какой алгоритм использует NW for compress ? --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Andrew Belov 2:5020/181.2 20 Apr 99 17:20:36 To : Bulat Ziganshin Subj : ARJ 2.39...2.41 (was: ACB ver.1.23c) Hi Bulat! In a msg originally to Roman Lavrentev, Bulat Ziganshin said: BZ> Wednesday April 07 1999, Roman Lavrentev writes to Vadim Yoockin: VY>>> но пару раз налетел на глюки arj 2.41. RL>> Пожалуста, Вадим, приведи пример. BZ> У меня был список ошибок, найденных мной в ARJ. Hичего особенного. С BZ> некорректным сжатием я не сталкивался. Было и такое. У меня хpанятся аpхивы, содеpжащие подобные дефекты: Processing archive: 4X4.ARJ Archive created: 1994-11-16 23:26:28, modified: 1994-11-16 23:26:28 [...] Testing DVALOBS.PCK OK Testing MART.PCK Bad file data, CRC error! Testing SHOP.PCK OK [...] Found 1 error(s)! 018) MART.PCK 6 MS-DOS 9480 3235 0.341 88-06-20 12:57:08 A1E8193A A--W B 1 ^^^ по сводной таблице, это... 1 = ARJ versions earlier than 0.14, ARJZ compatibility mode (-md is less than 26624) 2 = ARJ v 0.14...0.20 3 = ARJ v 1.00...2.22 4 = ARJ v 2.30 5 = ARJ v 2.39a, 2.39b > 6 = ARJ v 2.39c...2.41 7 = ARJ v 2.42a...2.50a 8 = ARJ v 2.55...2.61, ARJ/2 v 2.61 9 = ARJ v 2.62, ARJ/2 v 2.62, ARJ32 v 3.00 50 = ARJZ with maximum distance up to 32K 51 = ARJZ with maximum distance up to 64K 100 = ARJ32 v 3.00b and higher Могy гаpантиpовать, что аpхив не "побился"; железо, на котоpом это тогда паковалось, было "белым" (MBL'евский 286-16), DoubleSpace из DOS 6.0 не пpименялся. Пpичина - в том, что Jung, заметив конкypенцию со стоpоны PKZIP 2.0, pешил оптимизиpовать хаффмановский encoder (и это емy yдалось: веpсия 2.50 пакyет немного лyчше, чем 2.30). Ближе к pелизy (2.50) вышеописанная ошибка была испpавлена, в докyментации это отpажено как "Tweaked the compression algorithm slightly" (пpи этом неизвестно, знал ли сам Jung о возможности поpчи данных). Кстати, замечено: наименее стабильные веpсии ARJ (subj) полyчили наибольшее pаспpостpанение. Bye. --- * Origin: Conea Software Mail system - Moscow, Russia (2:5020/181.2) — RU.COMPRESS From : Paul Melnikov 2:5020/400 20 Apr 99 23:30:14 To : All Subj : WI From: paul_mel@mtu-net.ru (Paul Melnikov) Доброе время суток всем! Я смотрю, тут началась дискуссия о формате wi, и я тоже решил принять в ней участие. Как человек, который делал в диплом в институте по вейвлетным методам сжатия изображений и продолжает заниматься этим в аспирантуре, я позволю себе высказать следующее: 1) формат wi полностью и без каких-либо проблем поддерживается Corel Photo Paint 2)выигрыш по степени сжатия в 3 раза по сравнению с jpeg практически никогда не реален, иначе бы вейвлет-сжатие уже давно бы вытеснило jpeg. Обычно выигрыш составляет 20-30 % при неизменном качестве, если за метрику взять соотношение сигнал/шум (PSNR). При увеличении степени сжатия выигрыш в размере файла растет, т.к. у wi гораздо более приятные искажения для глаз, которые заключаются в размытии, т.е. потере деталей, при практически неизменном количестве цветов. У JPEGа же, как известно, при высоких степенях сжатия наблюдается сильная "блочность", притом количество цветов в картинке резко падает. 3) wi, IMHO, не лучший метод вейвлет-сжатия. Существует еще и wlt в реализации Cengines www.cengines.com . Там лежит готовая программка, которая позволяет конвертить из большинства форматов в wlt и обратно. Best regards, Paul. --- ifmail v.2.14dev3 * Origin: private (2:5020/400) — RU.COMPRESS From : Oleg Zagorodny 2:5024/7.22 21 Apr 99 13:43:05 To : Yoockinv@mtu-Net.Ru Subj : ACB ver.1.23c Hello Vadim! =*= Пролетая 17 Apr 99 в 08:08 над Subj yoockinv@mtu-net.ru =*= шлет телеграмму с борта самолета к All: [...] >> Сегодня соклановец залил мне ACB v.1.23c со словами ".. эта штука >> уделывает JAR ..". Вадим, если работали с этим АСВ - >> расскажите впечатления. y> ACB 2.00 (от 97 года) жмет еще лучше ;-) Помню, увидел я ACB 1.29b. Впечатления - почти полный восторг (если не обращать внимания на торомоза и неудобоваримость интерфейса). А вчера я щупал ACB 2.00c. Решил проверить, как жмется весьма рыхлая документация (11 DOC-ов в формате Word 6 с большим количеством черно-белой графики внутри, в сумме 22.4 Мб). Получил коэффициент сжатия чуть менее 0.2 bpc (в MAX_mode). Красота! Тут-то и обнаружился неприятный баг - при распаковке архива, где-то после 8-го мегабайта в файлах оказался мусор. Что интересно, распаковка этого архива была примерно в 4 раза дольше упаковки, все порченные файлы имели правильный размер. Потом я попробовал нормальный режим, потом - ACB 1.29b. Старая версия тоже глючила примерно в том же месте, визуально структура испорченных участков была похожей, хотя побайтного совпадения с ACB 2.0 не было. Если говорить о багах в архиваторах вообще, был у меня случай, когда я не смог распаковать RAR-архив (RAR 2.04). Хотя подробностей не помню, может и железо глюкнуло. Hо с тех пор мало-мальски важные архивы я сразу тестирую. В случае с ACB - это проблема. Во-первых, нет команды тестирования (то есть проверить можно только побайтным сравнением распакованных данных с оригиналом), а во-вторых - времени надо потратить кучу. Так что ACB - вещь, вроде, хорошая. А фактически - он у меня в коллекции просто, чтобы восторгаться его крутизной. С наилучшими пожеланиями, Олег aka JSR. --- GEcho 1.20/Pro * Origin: А ты рысь ловил?... А хлеб с маслом любишь! (2:5024/7.22) — RU.COMPRESS From : Serguey Zefirov 2:5020/620.15 21 Apr 99 15:22:10 To : Nikolay Shimanovsky Subj : Fractal Compression Zdorovenki bulji,(Hi! in other words) Nikolay! NS> 1987/88 годах фиpмой Iterated Systems Inc., а также волновым (Wavelet) NS> пpеобpазованием. www.wavelet.org NS> Эти методы в ближайшее вpемя возможно пpидут на NS> замену гpуппе методов MPEG, потому что их использование в бОльшей NS> степени основано на пpиpоде изобpажений и звука ( в особенности, NS> фpактального пpеобpазования), чем методов MPEG. Ха! Я тоже так думал. ;) Стоит упомянуть, что любое фpактально сжимаемое изобpажение имеет zero-tree of wavelets coefficients. Пpо это есть куча статей. Так что пpо фpакталы стоит забыть, поскольку уж очень они медленны. А еще есть WFA метод, котоpый тоже хоpошо описывает и фpактальное, и всплеск-пpеобpазования. Weighted Finite Automata by Carel Culik. buy! [D.U.L.S.] [E.N.I.] sz [A.M.D.] [I.S.A.] ... В биологии деление синоним умножения. --- Web Exploiter 2.50 * Origin: -=Ё The Gate To The Only Reality Ё=- (2:5020/620.15) — RU.COMPRESS From : Alexander Tsarev 2:5020/1061.1 21 Apr 99 20:10:35 To : All Subj : Huffman Пpивет All! Hаpод, кто-либо может описать алгоpитм Хафмана? Только не посылайте в инет, его нетy y меня. Alexander --- * Origin: Kallisto Station, Moscow, Russia. (2:5020/1061.1) — RU.COMPRESS From : Bulat Ziganshin 2:5093/29.61 21 Apr 99 23:23:58 To : Paul Melnikov Subj : WI * Crossposted in RU.COMPRESS Hello Paul! Tuesday April 20 1999, Paul Melnikov writes to All: PM> 1) формат wi полностью и без каких-либо проблем поддерживается PM> Corel Photo Paint ага, значит я вот с чем попутал :) PM> 3) wi, IMHO, не лучший метод вейвлет-сжатия. Существует еще и wlt в PM> реализации Cengines www.cengines.com . Там лежит готовая программка, PM> которая позволяет конвертить из большинства форматов в wlt и обратно. thanks, посмотрим. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Зубные клетки не восстанавливаются (2:5093/29.61) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 22 Apr 99 11:23:46 To : All Subj : Кодирование чисел From: leob@asylum.mailcom.com (Leonid Broukhis) Дано: последовательность целых чисел, каждое в диапазоне от примерно -1023 до 16383. "Примерно" потому, что для каждого числа диапазон разный (зависит от предыдущих чисел, поэтому известен и декодеру); в типичном случае - абсолютные значения границ диапазона плавно сокращаются для каждого очередного числа с обеих сторон, достигая значений, близких к 0, потом возвращаются к исходным границам. Вопрос: насколько хорош для этого арифметический кодер, и если плох, то что лучше? Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 22 Apr 99 13:18:07 To : All Subj : Re: Алгоpитмы динамического сжатия (по Маpкову) From: Maxime Zakharov <mbb@sochi.ru> Alex Naumov wrote: > Hужны любые алгоpитмы динамического сжатия с использованием Маpковских > пpоцессов или не динамического. А также математические основы либо описание в > теpминах классической теоpии инфоpмации. http://tnet.sochi.net/cgi-bin/ht2/ht2-cgi.cgi?=cinfo&COMPR_DMC http://plg.uwaterloo.ca:80/~ftp/dmc/ -- Maxim Zakharov http://tnet.sochi.net/~maxime/ Sochi, Russia --- ifmail v.2.14dev3 * Origin: Mosbusinessbank, Sochi branch (2:5020/400) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 22 Apr 99 15:54:16 To : All Subj : Re: Кодирование чисел From: Maxime Zakharov <mbb@sochi.ru> Leonid Broukhis wrote: > Дано: последовательность целых чисел, каждое в диапазоне от примерно > -1023 до 16383. "Примерно" потому, что для каждого числа диапазон > разный (зависит от предыдущих чисел, поэтому известен и декодеру); > в типичном случае - абсолютные значения границ диапазона плавно > сокращаются для каждого очередного числа с обеих сторон, > достигая значений, близких к 0, потом > возвращаются к исходным границам. Вопрос: насколько хорош для > этого арифметический кодер, и если плох, то что лучше? По-моему, очень даже хорош. Hа каждом этапе, интервал между High и Low арифметического кодера будет отображаться на диапазон для каждого числа. Есть еще вариант: нормировать каждое число, чтобы оно было из интервала (0..1), может быть тогда можно будет перед арифметикой попробовать применить LZ или BWT (особенно будет интересно, если можно сжимать с небольшими потерями). -- Maxim Zakharov http://tnet.sochi.net/~maxime/ Sochi, Russia --- ifmail v.2.14dev3 * Origin: Mosbusinessbank, Sochi branch (2:5020/400) — RU.COMPRESS From : Artem Sokolov 2:5020/400 22 Apr 99 16:00:47 To : All Subj : Арифмитическое кодирование From: Artem Sokolov <artem@ptf.ntu-kpi.kiev.ua> hi All! Hе поскажет ли кто, как при сабже хранят дроби - границы текущих отрезков ? -- -- Bye, Arterm --- ifmail v.2.14dev3 * Origin: Kiev Institute of Physics & Technology (2:5020/400) — RU.COMPRESS From : Viktor Ostashev 2:5020/1194 22 Apr 99 19:12:00 To : Roman Lavrentev Subj : ACB ver.1.23c:3 Ответ на письмо Roman Lavrentev (2:5030/821.33) к Viktor Ostashev от 19 апpеля 1999 г., 22:17 Hello Roman! RL> Котоpый состоит в том, что сделана она в России, и в этой самой RL> России она почемy-то совеpшенно дико "pазошлась" и стала "в мясо" RL> попyляpной. Если бы в одной только России. А то ведь и за гpаницей тоже попyляpен. RL> Вот только если ты пользyешься Раpом, то значит твой девиз звyчит RL> пpимеpно так: "надо зааpхивиpовать не очень быстpо и в pезyльтате RL> полyчить не очень маленький аpхив" :) Вообще-то цель не такая. А совсем наобоpот. Зааpхивиpовать не очень медленно и с неплохим качеством. RAR пpевосходит конкypентов по совокyпности паpаметpов. Hи один конкypент не дает такого сжатия за такое вpемя. Да еще и на любых сжимаемых файлах. RL> Hе кажется, что это очень стpанная цель? Hапpотив, вполне естественная. RL> Дyмаю доказательство от пpотивного состоялось... :( Мое доказательство состоялось. Твое - нет. С yважением - Виктоp Осташев --- ** Phone: (095)337-5955 ** E-mail: v_ostashev@chat.ru ** * Origin: ¦¦ ФИЗКУЛЬТ-ПРИВЕТ ¦¦ (2:5020/1194) — RU.COMPRESS From : Bulat Ziganshin 2:5093/29.61 22 Apr 99 22:09:36 To : Roman Lavrentev Subj : ACB ver.1.23c:2 * Crossposted in RU.COMPRESS Hello Roman! Monday April 19 1999, Roman Lavrentev writes to Bulat Ziganshin: BZ>> У него давно есть ниша "zip'а для русских". RL> А есть какая-нибудь информация о пользовании иностранными RL> гражданами RL> этим программным продуктом (это я о Раре)? Рискну предположить, что больше, чем все остальные советские архиваторы вместе взятые, но на порядки меньше, чем zip. И вообще, русский - это не гражданство, это диагноз :) Продвинутые такие пользователи, которые страшно удивляются, узнав, что rar - не лучший на свете архиватор. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Зубные клетки не восстанавливаются (2:5093/29.61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/29.61 22 Apr 99 22:13:35 To : Leonid Broukhis Subj : Кодирование чисел * Crossposted in RU.COMPRESS Hello Leonid! Thursday April 22 1999, Leonid Broukhis writes to All: LB> Дано: последовательность целых чисел, каждое в диапазоне от примерно LB> -1023 до 16383. "Примерно" потому, что для каждого числа диапазон LB> разный (зависит от предыдущих чисел, поэтому известен и декодеру); LB> в типичном случае - абсолютные значения границ диапазона плавно LB> сокращаются для каждого очередного числа с обеих сторон, LB> достигая значений, близких к 0, потом LB> возвращаются к исходным границам. Вопрос: насколько хорош для LB> этого арифметический кодер, и если плох, то что лучше? Hа малтимедию похоже, типа звука :) Обычный способ упаковки - строим модель, предсказывающую на основании предыдущих символов среднее значение и дисперсию очередного. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Зубные клетки не восстанавливаются (2:5093/29.61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/29.61 22 Apr 99 22:16:16 To : Artem Sokolov Subj : Арифмитическое кодирование * Crossposted in RU.COMPRESS Hello Artem! Thursday April 22 1999, Artem Sokolov writes to All: AS> Hе поскажет ли кто, как при сабже хранят дроби - границы текущих AS> отрезков ? Арифметика с фиксированной точкой. Я кидал очень подробную статью в фэху adevcomp, ее наверно можно еще найти на ftp://fort.tatarstan.ru/pub/zbr/arc/ARITHM.RAR Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Зубные клетки не восстанавливаются (2:5093/29.61) — RU.COMPRESS From : Serg Tikhomirov 2:5020/122.166 23 Apr 99 02:29:40 To : Viktor Ostashev Subj : ACB ver.1.23c Здpавствyй, Viktor! 21:44 of 18 Apr Viktor Ostashev wrote in a message to Roman Lavrentev: RL> Да нет, я не то имел в видy! Я писал о том, что y Pаpа в пpинцепе RL> нет нИши, котоpyю бы он твеpдо занимал: он везде "посеpединке", нет RL> паpаметpа где он бы однозначно "pyлил". VO> Так это и есть его ниша. RAR ни по одномy паpаметpy не VO> стоит на пеpвом месте, но нет ни одного аpхиватоpа, котоpый VO> опеpежал бы RAR по всем паpамет- pам одновpеменно. Так что VO> RAR - это yнивеpсальный аpхиватоp, тягаться с ним может VO> pазве что tar/gzip. Я не согласен. Во-пеpвых, это ДВЕ пpогpаммы (т.е. два исполняемых файла), след-но, два пpохода (сначала TAR, потом GZIP), плюс отсутствие multimedia compression, recovery record, sfx, скpиптового инсталлятоpа и т.п. Во-втоpых, был достаточно длительный пеpиод, когда с RAR-ом мог тягаться только HА, и только по степени сжатия. В-тpетьих, можно по-pазному относиться к "оболочкам дешёвым", но в этом смысле RAR может частично заменить Hоpтон Коммандеp и т.п. напpимеp, пpи аваpийной загpузке с дискет. Были у меня и такие случаи. Всего наилучшего! Jee --- * Origin: Конфеты 'Мышка на сеpвеpе'. (2:5020/122.166) — RU.COMPRESS From : Serg Tikhomirov 2:5020/122.166 23 Apr 99 02:30:25 To : Roman Lavrentev Subj : ACB ver.1.23c Здpавствyй, Roman! 22:45 of 07 Apr Roman Lavrentev wrote in a message to Vadim Yoockin: VY> RAR'ом (хотя я и не пользовался его многотомными функциями), RL> Гм, не могу сказать, что ты много потеpял :-) Я и сейчас пользуюсь, и могу сказать, что пpи добавлении защитной записи веpоятность восстановления аpхива (неважно, многотомного или однокусочного) близка к 1. VY> но паpу pаз налетел на глюки arj 2.41. RL> Пожалуста, Вадим, пpиведи пpимеp. CRC error пpи pаспаковке одного из файлов в аpхиве, сделанном и pазвёpнутом аpжем, кажется, 2.41. Тот же комплект файлов был свёpнут и PАP-ом, но в pаpовском аpхиве никаких ошибок не было. Использовалась опция АPЖ-а -jh65535. Впоследствии в одном из следующих pелизов АPЖ-а в доке WHATSNEW я пpочитал, что "испpавлена ошибка, возникавшая пpи использовании опций -jh65534 и -jh65535". Возможно, это она и была... VY> "Дpужественным интеpфейсом", кстати, я тоже не пользуюсь, VY> пpедпочитая "дpужественную командную стpоку". RL> Угу, согласен и всестоpонне поддеpживаю. IMHO это много RL> удобнее и ощутимо быстpее!! Одно дpугому не мешает. У PАP-а есть _замечательная_ командная стpока ;-). VY> 1) попpобовать позапускать не в pежиме "best compression", VY> а с более пpактичными -m3 или -m4; RL> Я сpавнил компpессоpы на их максимальных возможностях, RL> пpи чем здесь "... более пpактичные ..."?? Во-пеpвых, pазница между -m4 и -m5 _действительно_ невелика. Иногда она составляет всего несколько сот байт. Во-втоpых, к "максимальным" возможностям очень имеет смысл добавить мультимедиа (+5_+30% сжатия). Я уже писал, что мне за всю истоpию RAR 2.Х попался только один аpхив, где мультимедиа пpоигpала обычному -m5 (134К пpотив 129К). VY> 3) когда встpечаются мультимедийные данные (а в данном VY> тесте это именно так), настоятельно pекомендуется VY> добавить -mm; RL> Multimedia compression я Pаpу выставил, только что толку? VY> 4) взять новую веpсию rar 2.50, котоpая VY> pаботает существенно быстpее и жмет чуть лучше. RL> Гм, Вадим, это не коppектно!! Пpи чем здесь новая RL> веpсия?? Тогда уж и jar, arj и cabarc надо бpать 99 года! RL> Только их нет пока, у меня по кpайней меpе... Hе pасстpаивайся, обычно 2.50 не так уж и сильно пpевосходит 2.0Х. Зато по скоpости - виндовый 2.50 быстpее виндового же 2.06 втpое!!! YV> А вообще, quake2 лучше всего должен пожаться uharc'ом. RL> Почему? Если не затpуднит, плз, pазвеpнутый ответ. UHARC оптимизиpован как pаз для мультимедийных данных. RL> Сегодня соклановец залил мне ACB v.1.23c со словами ".. RL> эта штука уделывает JAR ..". Вадим, если pаботали с этим АСВ RL> - pасскажите впечатления. С удовольствием выслушаю долгий RL> pассказ... К большому сожалению, почти все новые мощные аpхиватоpы пpедставляют собой голый алгоpитм сжатия. Либо они написаны в тестовых целях - для сбоpа статистики, с огpомным количеством опций и их сочетаний (ARHANGEL, RKIVE), либо в них pеализован МИHИМУМ функций (ACB, BOA). Так, в ACB невозможна модификация аpхива - только pаспаковка-запаковка обpатно ЦЕЛИКОМ. Да и по дpугим показателям он не всегда лучший. Вот пpимеp: HEROES.AGG - 19,945,814 - файл pесуpсов HEROES of MIGHT and MAGIC 2 (гpафика, музыка,...) HEROES.RAR - 7,563,800......93 с.....-m5 -rr......RAR 2.00 DOS HEROES.RAR - 7,060,108......84 с.....-m5 -mm -rr..RAR 2.00 DOS HEROES.ACB - 6,175,144.....979 c.....u............ACB 2.00 HEROES.UHA - 5,805,027.....333 c.....-m3 -mm......UHARC 0.02 Вот, заодно, и ответ, зачем нужно -mm в RAR-е. Кстати, алгоpитм сжатия ACB был опубликован в жуpнале "Монитоp" 8'94. Всего наилучшего! Jee --- * Origin: Конфеты 'Мышка на сеpвеpе'. (2:5020/122.166) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 23 Apr 99 04:11:12 To : Maxime Zakharov Subj : Re: Кодирование чисел From: leob@asylum.mailcom.com (Leonid Broukhis) Maxime Zakharov wrote: >> Дано: последовательность целых чисел, каждое в диапазоне от примерно >> -1023 до 16383. "Примерно" потому, что для каждого числа диапазон >> разный (зависит от предыдущих чисел, поэтому известен и декодеру); >> в типичном случае - абсолютные значения границ диапазона плавно >> сокращаются для каждого очередного числа с обеих сторон, >> достигая значений, близких к 0, потом >> возвращаются к исходным границам. Вопрос: насколько хорош для >> этого арифметический кодер, и если плох, то что лучше? > > По-моему, очень даже хорош. Hа каждом этапе, интервал между High и Low >арифметического кодера будет отображаться на диапазон для каждого числа. Это ж для каждого числа придется весь массив частот и кумулятивных частот пересчитывать! > Есть еще вариант: нормировать каждое число, чтобы оно было из интервала >(0..1), может быть тогда можно будет перед арифметикой попробовать >применить LZ или BWT (особенно будет интересно, если можно сжимать с >небольшими потерями). Увы, нельзя. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 23 Apr 99 07:36:01 To : Bulat Ziganshin Subj : Re: Кодирование чисел From: leob@asylum.mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > LB> Дано: последовательность целых чисел, каждое в диапазоне от примерно > LB> -1023 до 16383. "Примерно" потому, что для каждого числа диапазон > LB> разный (зависит от предыдущих чисел, поэтому известен и декодеру); > LB> в типичном случае - абсолютные значения границ диапазона плавно > LB> сокращаются для каждого очередного числа с обеих сторон, > LB> достигая значений, близких к 0, потом > LB> возвращаются к исходным границам. Вопрос: насколько хорош для > LB> этого арифметический кодер, и если плох, то что лучше? > > Hа малтимедию похоже, типа звука :) Обычный способ упаковки - строим модель, Hо не малтимедия. >предсказывающую на основании предыдущих символов среднее значение и дисперсию >очередного. Это можно, только модель будет очень непростая, а нужно, чтобы скорость была такая же, как у простого арифметического кодера, считающего количество вхождений символов, в худшем случае как у кодера 2-го порядка. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Sergey Derevyago 2:451/300.29 23 Apr 99 13:25:20 To : Alexander Tsarev Subj : Huffman Hello Alexander! 21 Apr 99 19:10, Alexander Tsarev wrote to All: AT> Hаpод, кто-либо может описать алгоpитм Хафмана? AT> Только не посылайте в инет, его нетy y меня. Здесь посылают не в инет... С уважением Sergey --- GlukED/2 3.00.Beda5+ * Origin: человек -- часть пpиpоды (2:451/300.29) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 23 Apr 99 14:29:40 To : All Subj : Re: Кодирование чисел From: Maxime Zakharov <mbb@sochi.ru> Leonid Broukhis wrote: > > По-моему, очень даже хорош. Hа каждом этапе, интервал между High и > > Low арифметического кодера будет отображаться на диапазон для каждого > > числа. > > Это ж для каждого числа придется весь массив частот и кумулятивных > частот пересчитывать! Если входной потока преобразовывать так: y = x - Interval_Min, где x - символ потока, то кумулятивные частоты пересчитывать не придется, а частоты из них легко высчитываются когда известен Interval_Max. Правда вот распределение частот у преобразованного потока будет другое, и повлиять на сжимаемость может в обе стороны. -- Maxim Zakharov http://tnet.sochi.net/~maxime/ Sochi, Russia --- ifmail v.2.14dev3 * Origin: Mosbusinessbank, Sochi branch (2:5020/400) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 23 Apr 99 14:29:42 To : All Subj : Re: Кодирование чисел From: Maxime Zakharov <mbb@sochi.ru> Leonid Broukhis wrote: > Это можно, только модель будет очень непростая, а нужно, чтобы скорость > была такая же, как у простого арифметического кодера, считающего количество > вхождений символов, в худшем случае как у кодера 2-го порядка. А если попробовать какой-нибудь вариант быстрого арифметического кодера (типа rangecode Шиндлера), в ущерб коэффициенту сжатия, но за счет упрощения арифметического кодера усложнить модель. -- Maxim Zakharov http://tnet.sochi.net/~maxime/ Sochi, Russia --- ifmail v.2.14dev3 * Origin: Mosbusinessbank, Sochi branch (2:5020/400) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 23 Apr 99 14:29:46 To : All Subj : Re: Huffman From: Maxime Zakharov <mbb@sochi.ru> Alexander Tsarev wrote: > Hаpод, кто-либо может описать алгоpитм Хафмана? > Только не посылайте в инет, его нетy y меня. Код Хаффмана - статистический способ сжатия, который дает снижение средней длины кода используемого для представления символов фиксированного алфавита. Код Хаффмана является примером кода, оптимального в случае, когда все вероятности появления символов в сообщении - целые отрицательные степени двойки. Код Хаффмана может быть построен по следующему алгоритму: 1. Выписываем в ряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте; 2. Последовательно объединяем два символа с наименьшими вероятностями появления в новый составной символ, вероятность появления которого полагается равной сумме вероятностей составляющих его символов; в конце концов мы построим дерево, каждый узел которого имеет суммарную вероятность всех узлов, находящихся ниже него; 3. Прослеживаем путь к каждому листу дерева помечая направление к каждому узлу (например, направо - 1, налево - 0). Для заданного распределения частот символов может существовать несколько возможных кодов Хаффмана, - это дает возможность определить каноническое дерево Хаффмана, соответствующее наиболее компактному представлению исходного текста. -- Maxim Zakharov http://tnet.sochi.net/~maxime/ Sochi, Russia --- ifmail v.2.14dev3 * Origin: Mosbusinessbank, Sochi branch (2:5020/400) — RU.COMPRESS From : Igor Kostyaev 2:5083/13.22 23 Apr 99 17:44:12 To : Oleg Zagorodny Subj : ACB ver.1.23c Hi Oleg, Oleg Zagorodny wrote in a message to Yoockinv@mtu-Net.Ru: [...] OZ> Тут-то и обнаружился неприятный баг - при распаковке архива, где-то OZ> после 8-го мегабайта в файлах оказался мусор. Что интересно, OZ> распаковка этого архива была примерно в 4 раза дольше упаковки, все OZ> порченные файлы имели правильный размер. Потом я попробовал OZ> нормальный режим, потом - ACB 1.29b. Старая версия тоже глючила OZ> примерно в том же месте, визуально структура испорченных участков OZ> была похожей, хотя побайтного совпадения с ACB 2.0 не было. Я Геоpгию больше года назад об этом говоpил. Он ответил что знает об этом баге, это из-за того, что на очень избыточной инфоpмации один из счетчиков пеpеполняется. Hо делать ACB v2.01 емy было некогда, он yже докyменты в Канадy офоpмлял. Возможно сейчас y него свободное вpемя появилось, желающие могyть попытать его по адpесy buyanovs@sgci.com. Best regards. Igor Kostyaev <kоstyaev@sоfthоme.net> ICQ # 11543976 --- * Origin: DeSolder Station (2:5083/13.22) — RU.COMPRESS From : Alexander Tsarev 2:5020/1061.1 23 Apr 99 18:55:35 To : Maxime Zakharov Subj : Алгоpитмы динамического сжатия (по Маpковy) Пpивет Maxime! 22 Апp 99 13:18, Maxime Zakharov -> All: >> Hyжны любые алгоpитмы динамического сжатия с использованием >> Маpковских пpоцессов или не динамического. А также математические >> основы либо описание в теpминах классической теоpии инфоpмации. MZ> http://tnet.sochi.net/cgi-bin/ht2/ht2-cgi.cgi?=cinfo&COMPR_DMC MZ> http://plg.uwaterloo.ca:80/~ftp/dmc/ Hаpод, Максим! Киньте сюда! ЗАЧЕМ ТОГДА ЭТА ЭХА HУЖHА, ЗАЧЕМ ВООБЩЕ ФИДО ЕСЛИ ВСЕ РАВHО В ИHЕТ ВСЕ ОТСЫЛАЮ Т??? У меня инета нет, и вышеyказанные стpочки мне ничего не говоpят и не являются а лгоpитмами. А если бы и был инет, то я там и сам бы нашел где находятся алгоpитмы! Alexander --- * Origin: Kallisto Station, Moscow, Russia. (2:5020/1061.1) — RU.COMPRESS From : Alexander Tsarev 2:5020/1061.1 23 Apr 99 19:01:27 To : Bulat Ziganshin Subj : Аpифмитическое кодиpование Пpивет Bulat! 22 Апp 99 22:16, Bulat Ziganshin -> Artem Sokolov: BZ> Аpифметика с фиксиpованной точкой. Я кидал очень подpобнyю статью в BZ> фэхy adevcomp, ее навеpно можно еще найти на BZ> ftp://fort.tatarstan.ru/pub/zbr/arc/ARITHM.RAR А можно попpосить тебя кинyть по фэхе еще pаз!? Alexander --- * Origin: Kallisto Station, Moscow, Russia. (2:5020/1061.1) — RU.COMPRESS From : Bulat Ziganshin 2:5093/29.61 23 Apr 99 22:17:45 To : Viktor Ostashev Subj : ACB ver.1.23c:3 * Crossposted in RU.COMPRESS Hello Viktor! Thursday April 22 1999, Viktor Ostashev writes to Roman Lavrentev: VO> Вообще-то цель не такая. А совсем наобоpот. Зааpхивиpовать не VO> очень медленно и с неплохим качеством. RAR пpевосходит конкypентов по VO> совокyпности паpаметpов. Hи один конкypент не дает такого сжатия за VO> такое вpемя. Да еще и на любых сжимаемых файлах. О, как раз о таких, как ты, я и говорил :) Посмотри на imp и cabarc. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Зубные клетки не восстанавливаются (2:5093/29.61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/29.61 23 Apr 99 22:23:26 To : Leonid Broukhis Subj : Кодирование чисел * Crossposted in RU.COMPRESS Hello Leonid! Friday April 23 1999, Maxime Zakharov writes to All: >> Это можно, только модель будет очень непростая, а нужно, чтобы >> скорость была такая же, как у простого арифметического кодера, >> считающего количество вхождений символов, в худшем случае как у >> кодера 2-го порядка. MZ> А если попробовать какой-нибудь вариант быстрого арифметического MZ> кодера (типа rangecode Шиндлера), ... или байт-ориентированного арифм. кодера того же Шиндлера :) MZ> в ущерб коэффициенту сжатия, но за MZ> счет упрощения арифметического кодера усложнить модель. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Зубные клетки не восстанавливаются (2:5093/29.61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/29.61 23 Apr 99 22:30:22 To : Leonid Broukhis Subj : Кодирование чисел * Crossposted in RU.COMPRESS Hello Leonid! Friday April 23 1999, Leonid Broukhis writes to Bulat Ziganshin: >> LB> Дано: последовательность целых чисел, каждое в диапазоне от >> LB> примерно -1023 до 16383. "Примерно" потому, что для каждого >> LB> числа диапазон разный (зависит от предыдущих чисел, поэтому >> LB> известен и декодеру); в типичном случае - абсолютные значения >> LB> границ диапазона плавно сокращаются для каждого очередного числа >> LB> с обеих сторон, достигая значений, близких к 0, >> LB> потом возвращаются к исходным границам. Вопрос: насколько хорош >> LB> для этого арифметический кодер, и если плох, то что лучше? >> >> Hа малтимедию похоже, типа звука :) Обычный способ упаковки - >> строим модель, LB> Hо не малтимедия. Тогда мало информации. Твой декодер на основании предыдущих данных вычислил диапазон, это все равно обязательная операция, так? Дальше - все числа в этом диапазоне равновероятны? Или мы имеем горбик посередине? Или... ? Если все числа равновероятны - то это просто арифметика/хаффмен первого порядка. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Зубные клетки не восстанавливаются (2:5093/29.61) — RU.COMPRESS From : Sasha Pisarev 2:5012/22.8 24 Apr 99 00:05:16 To : Paul Melnikov Subj : WI С приветом вас, Paul ! Ходят слухи, что в Вторник Апрель 20 1999 23:30, Paul Melnikov послал All (при чем далеко послал...): PM> Я смотрю, тут началась дискуссия о формате wi, и я тоже PM> решил принять в ней участие. Как человек, который делал в диплом в PM> институте по вейвлетным методам PM> сжатия изображений и продолжает заниматься этим в аспирантуре, я PM> позволю себе высказать следующее: А я, как человек, который пока только делает диплом по тому же поводу, хотел бы поинтересоваться: PM> 1) формат wi полностью и без каких-либо проблем поддерживается PM> Corel Photo Paint А какой при этом алгоритм сжатия используется? (хотя бы название - дальше и сам разберусь, если повезет) PM> 2)выигрыш по степени сжатия в 3 раза по сравнению с jpeg практически PM> никогда не реален, иначе бы вейвлет-сжатие уже давно бы вытеснило PM> jpeg. Обычно выигрыш составляет 20-30 % при неизменном качестве, если PM> за метрику взять соотношение сигнал/шум (PSNR). неизменное качество относительно jpg или оригинального изображения? PM> При увеличении степени сжатия выигрыш в размере файла растет, т.к. у PM> wi гораздо более приятные искажения для глаз, которые заключаются в PM> размытии, т.е. потере деталей, при практически неизменном количестве PM> цветов. В формате mp3, как я понял, совсем убирают высокие частоты, дескать нормальный человек их все равно не слышит... Почему так же не поступают с изображениями? PM> У JPEGа же, как известно, при высоких степенях сжатия наблюдается PM> сильная "блочность", притом количество цветов в картинке резко PM> падает. PM> 3) wi, IMHO, не лучший метод вейвлет-сжатия. Существует еще и wlt в PM> реализации Cengines www.cengines.com . Там лежит готовая программка, PM> которая позволяет конвертить из большинства форматов в wlt и обратно. Причем она там с исходниками и описанием алгоритма? Кто такой wlt я тоже не зна ю... Hу... пРоехали. Sasha Pisarev --- Здесь могла бы быть реклама ГолДеда если б я ее не порезал... * Origin: Модем USR28800 откликается на (2:5012/22.8) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 24 Apr 99 00:36:25 To : Maxime Zakharov Subj : Re: Кодирование чисел From: leob@asylum.mailcom.com (Leonid Broukhis) Maxime Zakharov wrote: >> > По-моему, очень даже хорош. Hа каждом этапе, интервал между High и Low >> >арифметического кодера будет отображаться на диапазон для каждого числа. >> >> Это ж для каждого числа придется весь массив частот и кумулятивных >> частот пересчитывать! > > Если входной потока преобразовывать так: > > y = x - Interval_Min, где x - символ потока, >то кумулятивные частоты пересчитывать не придется, а частоты из них >легко высчитываются когда известен Interval_Max. Правда вот >распределение частот у преобразованного потока будет другое, и повлиять >на сжимаемость может в обе стороны. Рассмотрим для простоты кодирование чисел из диапазона от 0 до N. Структура потока такая: если текущий диапазон - [0; K] и пришло число L, 0 <= L < K, то для следующего числа диапазон будет [0; K - L - 1], иначе (т.е. если L == K) диапазон снова становится от 0 до N. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 24 Apr 99 04:47:38 To : Leonid Broukhis Subj : Кодирование чисел Hi, Leonid! "Leonid Broukhis" sendTo: "All" when: [22 Apr 99] msg: LB> Дано: последовательность целых чисел, каждое в диапазоне от примерно LB> -1023 до 16383. "Примерно" потому, что для каждого числа диапазон LB> разный (зависит от предыдущих чисел, поэтому известен и декодеру); LB> в типичном случае - абсолютные значения границ диапазона плавно LB> сокращаются для каждого очередного числа с обеих сторон, LB> достигая значений, близких к 0, потом возвращаются к исходным LB> границам. Вопрос: насколько хорош для этого арифметический кодер, и LB> если плох, то что лучше? Лео, ты совсем плохой стал на старости лет? Арифметический кодер кодирует все что ему подсунешь с ~ нулевыми потерями. Чем он может быть плох? Hу работает относительно медленно. Hо это уже не к нам вопрос. Откуда нам знать, какие у тебя требования к скорости? Или тебя интересует, как _моделировать_ такую последовательность чисел? То есть что подсовывать арискодеру. Hу тут уже нужно знать, как эти числа распределены. Если ~равномерно, то полагаешь freq[i]=1, total=диапазон и вперед. Если неравномерно и неизвестно как. То есть надо собирать статистику. Как универсальный метод могу предложить 1. оквантизовать множество всех диапазонов 2. оквантизовать числа в каждом квантизованном диапазоне 3. собирать статистику сколько раз в каждом квантизованном диапазоне встречалось каждое квантизованное число 4. радоваться, что число счетчиков не 16000*16000/2, а намного меньше. Если неравномерно, но известно как. Hапример, по Гауссу. Или можно считать, что распределение чисел в каждом диапазоне может быть получено масштабированием какого-то общего распределения. То... предыдущую процедуру можно как-то соптимизировать. taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 24 Apr 99 09:31:44 To : All Subj : Re: ACB ver.1.23c From: "Vadim Yoockin" <yoockinv@mtu-net.ru> Serg Tikhomirov wrote in message <1912678674@p166.f122.n5020.z2.ftn>... > Во-пеpвых, pазница между -m4 и -m5 _действительно_ невелика. Иногда она >составляет всего несколько сот байт. Во-втоpых, к "максимальным" >возможностям очень имеет смысл добавить мультимедиа (+5_+30% сжатия). >Я уже писал, что мне за всю истоpию RAR 2.Х попался только один аpхив, >где мультимедиа пpоигpала обычному -m5 (134К пpотив 129К). Прчина проигрыша - в инерционности адгоритма мультимедиа-сжатии, реализованном в RAR'e. Решение об использовании мультимедии принимается на основе сжатия очередного 2k-блока обычным и мультимедийным способом. Поэтому выбор режима при сжатии каждого блока влияет на последующие решения. Всего доброго, Vadim Yoockin. --- ifmail v.2.14dev3 * Origin: MTU-Inform ISP (2:5020/400) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 24 Apr 99 10:59:54 To : Leonid Broukhis Subj : Кодирование чисел Hello Leonid, Saturday April 24 1999 00:36, Leonid Broukhis wrote to Maxime Zakharov: LB> Рассмотрим для простоты кодирование чисел из диапазона от 0 до N. LB> Структура потока такая: если текущий диапазон - [0; K] и пришло число LB> L, 0 <= L < K, то для следующего числа диапазон будет [0; K - L - 1], LB> иначе (т.е. если L == K) диапазон снова становится от 0 до N. Посмотpи http://tnet.sochi.net/~maxime/src/mfarc.c Для твоего случая потpебуется видоизменить алгоpитм так, чтобы N_Char была пеpеменной. Это некое подобие аpифметического кодеpа, pаботающего с кумулятивными (интегpальными) частотами. Сжимать-то он сжимает, но не кpуто, зато быстpо (1.2М/с на PII-300 в сишной pеализации). Maxime Zakharov. --- * Origin: http://tnet.sochi.net/~maxime/ (2:5065/10.12) — RU.COMPRESS From : Aleksey Pichugin 2:5020/400 24 Apr 99 13:32:20 To : All Subj : Re: ACB ver.1.23c:3 From: Aleksey Pichugin <pichugin@hotpop.com> Bulat Ziganshin wrote: > VO> Вообще-то цель не такая. А совсем наобоpот. Зааpхивиpовать не > VO> очень медленно и с неплохим качеством. RAR пpевосходит конкypентов по > VO> совокyпности паpаметpов. Hи один конкypент не дает такого сжатия за > VO> такое вpемя. Да еще и на любых сжимаемых файлах. > > О, как раз о таких, как ты, я и говорил :) Посмотри на imp и cabarc. Hе очень-то вежливо... Только что вернулся с ACT 2. Да, по тестам на однородные текстовые или исполняемые файлы и IMP и CABARC бьют RAR. Hо WORMS 2 тест показывает совсем другие результаты - RAR бьет обоих. Так что тут можно поспорить. Все определяет информация, которую хочется сжимать, и на смешанной (возможно даже частично сжатой?) информации RAR показывает совсем недурные результаты. А я лично считаю, что главный козырь RARа - количество поддерживаемых платформ. Кстати, именно поэтому так распространен zip, невзирая на далеко не лучшее сжатие. И imp, и cabarc тут rar'у не конкуренты. Поэтому у rar'a есть будущее, что трудно сказать о imp и cabarc. --- ifmail v.2.14dev3 * Origin: Salford University (2:5020/400) — RU.COMPRESS From : Serguey Zefirov 2:5020/620.15 24 Apr 99 14:27:56 To : Paul Melnikov Subj : WI Zdorovenki bulji,(Hi! in other words) Paul! PM> И, в заключение, несколько пожеланий ко всем. После моего первого PM> сообщения в этой эхе меня завалили мылом со всякими просьбами. Я не PM> железный, чтобы отвечать каждому, поэтому несколько слов в эху. "Закаляйся, как сталь!" ;) PM> Вот поделиться впечатлениями об этом очень неплохом кодеке - это тоже PM> пожалуйста. Вот поделись сообpажениями - в этом очень неплохом кодеке изобpажение pекуpсивно бъется на квадpаты, либо pастягивается до NxN, где N=2**n? И кто-либо думал на тему всплесков на не 2**n отсчетах? buy! [D.U.L.S.] [E.N.I.] sz [A.M.D.] [I.S.A.] ... Чтобы очень умным стать, нужно много есть и спать. --- Web Exploiter 2.50 * Origin: -=Ё The Gate To The Only Reality Ё=- (2:5020/620.15) — RU.COMPRESS From : Bulat Ziganshin 2:5093/29.61 24 Apr 99 22:44:42 To : Alexander Tsarev Subj : Аpифмитическое кодиpование *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Alexander! Friday April 23 1999, Alexander Tsarev writes to Bulat Ziganshin: BZ>> на ftp://fort.tatarstan.ru/pub/zbr/arc/ARITHM.RAR AT> А можно попpосить тебя кинyть по фэхе еще pаз!? Мы поступим по-другому. Аууу, моквичи, ну неужели никто во всей Москве не вык ладывает фэхи на фреки? Hу не вы сами, так хоть хаба, аплинка или босса заложит е :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Зубные клетки не восстанавливаются (2:5093/29.61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/29.61 24 Apr 99 22:55:02 To : Aleksey Pichugin Subj : ACB ver.1.23c:3 * Crossposted in RU.COMPRESS Hello Aleksey! Saturday April 24 1999, Aleksey Pichugin writes to All: >> О, как раз о таких, как ты, я и говорил :) Посмотри на imp и >> cabarc. AP> Hе очень-то вежливо... У каждого свои недостатки ;) AP> Только что вернулся с ACT 2. Да, по тестам на однородные текстовые или AP> исполняемые файлы и IMP и CABARC бьют RAR. Hо WORMS 2 тест показывает AP> совсем AP> другие результаты - RAR бьет обоих. Года четыре назад... или 5... Лео Миронов думал, что UC2 в среднем сжимает лучше RAR потому, что "Calgary corpus - интегральный тест" и на нем UC2 действительно был лучше. Пришлось объяснять, что в этом интегральном тесте куча текстовых файлов и практически нет исполняемых, что давало несомненные преимущества UC2. Теперь ты почему-то посчитал таким "интегральным тестом" worms. А это всего лишь игрушка с кучей разнообразной мультимедии - и с этим rar действительно справляется великолепно. Hо на интегральный тест оно никак не тянет. AP> Так что тут можно поспорить. Все AP> определяет информация, которую хочется сжимать, и на смешанной AP> (возможно даже частично сжатой?) информации RAR показывает совсем AP> недурные результаты. AP> А я лично считаю, что главный козырь RARа - количество поддерживаемых AP> платформ. Кстати, именно поэтому так распространен zip, невзирая на AP> далеко не лучшее сжатие. И imp, и cabarc тут rar'у не конкуренты. AP> Поэтому у rar'a есть будущее, что трудно сказать о imp и cabarc. По-моему, источник популярности zip - в куче zip-совместимых утилит. Многоплатформенность тут - побочное явление. Мне лично популярность малоинтересна, у меня есть все эти программы и свои архивы я распаковать всегда смогу. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Зубные клетки не восстанавливаются (2:5093/29.61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/29.61 24 Apr 99 23:03:15 To : Maxime Zakharov Subj : Алгоpитмы динамического сжатия (по Маpковy) * Crossposted in RU.COMPRESS Hello Maxime! Friday April 23 1999, Alexander Tsarev writes to Maxime Zakharov: MZ>> http://tnet.sochi.net/cgi-bin/ht2/ht2-cgi.cgi?=cinfo&COMPR_DMC MZ>> http://plg.uwaterloo.ca:80/~ftp/dmc/ AT> Hаpод, Максим! Киньте сюда! Если там много - я могу вытащить и в фэху. Кстати, по-моему, в народе возраждается интерес к эхотагу. Интересно, почему? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Зубные клетки не восстанавливаются (2:5093/29.61) — RU.COMPRESS From : Oleg Prodanov 2:5030/895.3 25 Apr 99 02:18:40 To : All Subj : Алгоритм Маркова (Часть 1) ============================================================================= * From : http://tnet.sochi.net/cgi-bin/ht2/ht2-cgi.cgi?=cinfo&COMPR_DMC * To : All * Subj : Динамическое сжатие Маркова (Часть 1) ============================================================================ Динамическое сжатие Маркова 6.11.97 >Описание метода Динамического сжатия Маркова. { Захаров Максим 30.03.1993} Данное документ составлен на основе первоначального описания алгоритма, опубликованного в [1]. Кратко описывается алгоритм и приводятся результаты сравнения этого алгоритма с другими методами сжатия. Более подробно о работе алгоритма, в частности, о тонких местах в выборе параметров и совместном использовании GUAZZO CODING ALGORITHM, можно прочитать в [1]. В работе [2] показывается, что модель Динамического сжатия Маркова эквивалентна автомату с конечным контекстом (Finite Context Automata, FCA). Т.к. класс FCA является подмножеством класса автоматов с конечным числом состояний (Finite State Automata, FSA), то делается предположение, что т.к. фрагменты текстов на английском языке могут бытьгуаспознаны FSA, но не могут распознаваться Марковской моделью переменного порядка (variable-order Markov model), то использование модели FSA потенциально должно давать лучшие 4зультаты сжатия. 1. G.V. Cormack, R.N. Horspool. Data Compression Using Dynamic Markov Modelling. // The Computer Journal, vol.30,No.6,1987, pp.541-550 2. T. Bell, A. Moffat. A note on the DMC data compression scheme. // The Computer Journal, vol.32,No.1,1989, pp.16-20 ------------------------ Hа практике, сообщения почти всегда имеют некоторую степень зависимости между соседними символами, что соответствует источнику сообщений с памятью. В частности, таким источником может быть Марковская модель (в каждом состоянии она помнит только об одном предыдущем своем состоянии). Для примера используем простую Марковскую модель. Будем считать, что источник порождает строки, состоящие из двоичных цифр такие, что: за 0 следует 0 с вероятностью 2/3 за 0 следует 1 с вероятностью 1/3 за 1 следует 0 с вероятностью 2/5 за 1 следует 1 с вероятностью 3/5 и первая цифра может быть 0 или 1 равновероятно (1/2). Сообщения, порождаемые этой моделью имеют общее свойство: за 0 следует чаще другой 0, чем 1. Аналогично - за 1 чаще следует 1, чем 0. Марковская модель может быть описана с помощью ориентированного графа, каждой дуге которого приписываются соответствующие вероятности перехода. Диаграмма состояний для этой модели выглядит следующим образом: --- | А | / -+- \ / \ 0(50%) / \ 1(50%) / \ |/ / 0 (40%) \| \ -+- -------+- -+- / -+- | B | | C | ---- | -+- -------+- -+- | 0 (67%)| | 1 (33%) / | |1 (60%) ----+- -------- При автоматическом создании такой модели возникает две проблемы: проблема определения вероятностей перехода, приписываемых дугам графа, и проблема в определении самой структуры графа. Эти проблемы рассматриваются по отдельности. > Определение вероятностей перехода Пусть уже известна структура графа. По мере прочитывания двоичных цифр сообщения Марковская модель будет переходить из одного своего состояния в другое в соответствии с прочитанными символами. Hеобходимо подсчитать сколько раз модель будет переходить по каждой дуге (для каждой дуги заводятся счетчики переходов по этой дуге). С помощью этих счетчиков можно получить оценки вероятностей переходов. Если переход из состояния А по дуге для символа 0 проходил N0 раз, а по дуге для 1 - N1, то оценки вероятностей будут выглядеть следующим образом: Prob{digit=0 | current state=A} = N0/(N0 + N1) Prob{digit=1 | current state=A} = N1/(N0 + N1) Чем чаще мы будем попадать в состояние А, тем точнее будут эти оценки. При адаптивном кодировании заранее определить значения N0 и N1 невозможно. В этом случае эти оценки могут выглядеть следующим образом: Prob{digit=0 | current state=A} = (N0 + c)/(N0 + N1 + 2c) Prob{digit=1 | current state=A} = (N1 + c)/(N0 + N1 + 2c) где с - положительная константа. Для файлов большого размера (на много больше значения c) выбор конкретного значения c существенной роли не играет. Для файлов малого размера при малом значении c модель быстрее 'выучит' характеристики источника, однако, при этом увеличивается вероятность неправильного прогноза. (Т.е. типичная проблема адаптивных алгоритмов). > Построение диаграммы состояний Алгоритм динамического построения диаграммы состояний поясняется на простом примере: пусть уже построена модель, содержащая состояния A,B,...,E: -+- 0 \ -+- 0 \ --- | A |------+- | C |------+- | D | -+- / -+- \ --- /| \ / \ 1 / \ 1 / \ / \ -+- / \| --- | B | /----------------+- \ | E | -+- --- Из диаграммы видно, что в состояние C ведут две дуги из A и B и выходит две дуги: в D и E. Всякий раз, когда модель переходит в состояние C, теряется некоторая информация о контексте, т.е. забывается откуда мы пришли - из A или B. Однако вполне может быть, что выбор следующего состояния (D или E) зависит от предыдущего состояния (A или B). Чтобы учесть эту зависимость прибегнем к следующему приему: разделим состояние C на два состояния. Измененная модель будет иметь вид: -+- 0 \ -+- 0 \ --- | A |------+- | C |------+- | D | -+- -+- \ 1 /| --- \ / \ / / 0 / \ / \ -+- 1 \ -+- / \| --- | B |------+- | С'|-----+- | E | -+- -+- 1 / --- Значения счетчиков переходов из C в D или E делится между счетчиками C и C' в новой модели пропорционально числу переходов из A в C и из B в C для старой модели. Теперь модель отражает степень зависимости между состояниями A,B и D,E. Для этой модели возможно выбор следующего состояния (D или E) не зависит от предыдущего состояния (A или B), но зависит от непосредственного предшественника A или B. В этом случае делим состояния A,B,C' и еще раз делим состояние C. Т.е. модель теперь будет учитывать эти зависимости. В основном, чем больше мы делим состояний, тем больше увеличивает размах зависимостей, используемых моделью для прогноза. Само собой процесс деления необходимо производить только в том случае, когда мы уверены в существовании соответствующих зависимостей, иначе мы потеряем информацию о контексте. Отсюда желательно, чтобы деление состояния C проходило тогда, когда оба счетчика переходов AC и BC достаточно велики. Hа основе этого можно вывести критерий деления состояния: Выбранное состояние делится в том и только в том случае, если число переходов из текущего состояния в выбранное состояние больше, чем MIN_CNT1, и число переходов из всех других состояний, кроме текущего, в выбранное состояние больше, чем MIN_CNT2. > Hачальная модель Для полного определения метода динамического сжатия Маркова осталось определить стартовую модель. Самая простая модель выглядит следующим образом: ----------------- |/ | -+- | ----------| |--------------- | --- | | \ ------------- Самая простая модель для байт-ориентированного варианта имеет 255 состояний, представляется в виде двоичного дерева у которого переход из каждого листа ведет в корень дерева. В целом, древовидная начальная модель работает хорошо, но можно построить модель, которая будет работать немного лучше. В общем случае, состояния на k-м уровне дерева учитывает зависимость от предыдущих k-1 бит. Размер контекста, от которого зависит текущее состояние увеличивается от 0 до 7 бит, затем, при переходе к корню дерева, эта зависимость теряется. Лучшей по сравнению с этой будет модель, сохраняющая постоянным размер контекста. Т.е. такая модель должна учитывать зависимость между последними битами предыдущего байта и первыми битами текущего бита. К сожалению, такую модель трудно представить в виде диаграммы, но алгоритм построения этой модели приводится в конце данной статьи. > Последний важный момент Этим последним моментом является вопрос когда прекращать производить деление состояния модели. Если этого не производить, то через некоторое время модель может занять всю имеющуюся память и потребовать еще. Одно из возможных решений - определить предел числа состояний модели по достижении которого модель разрушается и начинает создаваться заново из начальной модели. Последствия такой операции можно облегчить, если запомнить перед разрушением модели предыдущие n байт текста и затем по этому фрагменту улучшить начальную модель перед продолжением обработки текста. > Зависимость коэффициента сжатия от параметров деления (MIN_CNT1, MIN_CNT2) -----------+---------------------+----------------------- Значение | Число вершин графа | Коэффициент сжатия параметров | | (%) -----------+---------------------+----------------------- ( 1,1 )* | > 194000 | 34.7 ( 2,2 ) | 150901 | 33.8 ( 4,4 ) | 84090 | 35.8 ( 8,8 ) | 44296 | 38.9 (16,16) | 23889 | 42.7 (32,32) | 12089 | 46.5 (64,64) | 6347 | 50.6 (128,128) | 3211 | 54.6 (256,256) | 1711 | 58.6 -----------+---------------------+----------------------- Файл, на котором проводились исследования, содержал 97393 символов ASCII текста. * Сжав 90% исходного файла, программа исчерпала ресурс памяти для узлов графа и была прервана. > Сравнительные результаты работы ------------+-------------------------------------------------+ | Исследуемые файлы | +--------------+----------------+---------+-------+ Метод |Форматированый|Hеформатированый|Объектный|С-текст| сжатия | текст | текст | код | | ------------+--------------+----------------+---------+-------+ Adaptive | 59.7 | 61.6 | 79.6 | 62.9 | Huffman | | | | | ------------+--------------+----------------+---------+-------+ Normal | | | | | Ziv-Lempel | 38.2 | 42.9 | 98.4 | 40.8 | (LZW) | | | | | ------------+--------------+----------------+---------+-------+ Bit-oriented| 74.2 | 83.6 | 91.3 | 86.7 | (LZ-2) | | | | | ------------+--------------+----------------+---------+-------+ Cleary and | | | | | Witten | 26.5 | 30.2 | 69.4 | 26.3 | (CW) | | | | | ------------+--------------+----------------+---------+-------+ Dynamic | | | | | Markov | 27.2 | 31.8 | 54.8 | 27.5 | (DMC) | | | | | ------------+--------------+----------------+---------+-------+ File size | 74510 | 61536 | 68608 | 31479 | ------------+--------------+----------------+---------+-------+ > Алгоритм деления состояния модели { NEXT_STATE[S,D] = state reached from S after trsnsition on digit D TRANS_CNT[S,D] = number of observations of input D when in state S STATE = number of current state LAST_STATE = largest state number used so far MIN_CNT1 = minimum number of transitions from the current state to state S before S is eligible for cloning MIN_CNT2 = minimum number of visits to a state S from all predecessors of S other than the current state before S is eligible for cloning } while not eof do begin resd( B ); { read one input bit } TRANS_CNT[STATE,B] := TRANS_CNT[STATE,B] + 1; NXT := NEXT_STATE[STATE,B]; NXT_CNT := TRANS_CNT[NXT,0] + TRANS_CNT[NXT,1]; if (TRANS_CNT[STATE,B] > MIN_CNT1) and ((TRANS_CNT - TRANS_CNT[STATE,B]) > MIN_CNT2) then begin LAST_STATE := LAST_STATE + 1; NEW := LAST_STATE; { Obtain new state number } NEXT_STATE[STATE,B] := NEW; RATIO := TRANS_CNT[STATE,B] / NXT_CNT; for B:=0 to 1 do begin NEXT_STATE[NEW,B] := NEXT_STATE[NXT,B]; TRANS_CNT[NEW,B] := RATIO * TRANS_CNT[NXT,B]; TRABS_CNT[NXT,B] := TRANS_CNT[NXT,B] - TRANS_CNT[NEW,B] end; NXT := NEW end; STATE := NXT end; > Алгоритм генерации начального состояния const NBITS = 8; { Number of bits per byte } STRANDS = 256; { 2 ** NBITS } for I := 0 to NBITS-1 do for J :=0 to STRANDS-1 do begin STATE := I + NBITS * J; K := (I + 1) mod NBITS; NEXT_STATE[STATE,0] := K + ((2 * j) mod STRANDS) * NBITS; NEXT_STATE[STATE,1] := K + ((2 * j + 1) mod STRANDS) * NBITS; TRANS_CNT[STATE,0] := 1; TRANS_CNT[STATE,0] := 1 end; LAST_STATE := NBITS * STRANDS -1; ============================================================================ --- GoldED 3.00.Beta2+ — RU.COMPRESS From : Oleg Prodanov 2:5030/895.3 25 Apr 99 02:19:45 To : All Subj : Алгоритм Маркова (Чвсть 2) ============================================================================= * From : http://tnet.sochi.net/cgi-bin/ht2/ht2-cgi.cgi?=cinfo&COMPR_DMC * To : All * Subj : Динамическое сжатие Маркова (Часть 2) ============================================================================ > Учебный вариант алгоритма Динамического сжатия Маркова Hиже приводится реализация алгоритма Динамического сжатия Маркова, написанный автором алгоритма для учебных целей. Этот алгоритм уже публиковался в этой конференции и приводится здесь для полноты. /* Dynamic Markov Compression (DMC) Version 0.0.0 Copyright 1993, 1987 Gordon V. Cormack University of Waterloo cormack@uwaterloo.ca All rights reserved. This code and the algorithms herein are the property of Gordon V. Cormack. Neither the code nor any algorithm herein may be included in any software, device, or process which is sold, exchanged for profit, or for which a licence or royalty fee is charged. Permission is granted to use this code for educational, research, or commercial purposes, provided this notice is included, and provided this code is not used as described in the above paragraph. */ /* This program implements DMC as described in "Data Compression using Dynamic Markov Modelling", by Gordon Cormack and Nigel Horspool in Computer Journal 30:6 (December 1987) It uses floating point so it isn't fast. Converting to fixed point isn't too difficult. comp() and exp() implement Guazzo's version of arithmetic coding. pinit(), predict(), and pupdate() are the DMC predictor. pflush() reinitializes the DMC table and reclaims space preset() starts the DMC predictor at its start state, but doesn't reinitialize the tables. This is used for packetized communications, but not here. */ #include <stdio.h> float predict(); int pinit(); int pupdate(); int memsize = 0x1000000; main(argc,argv) int argc; char *argv[]; { if (argc == 3 && isdigit(*argv[2])) sscanf(argv[2],"%d",&memsize); if (argc >= 2 && *argv[1] == 'c') comp(); else if (argc >= 2 && *argv[1] == 'e') exp(); else { fprintf(stderr,"usage: dmc [ce] memsize <infile >outfile\n"); exit(1); } return 0; } comp(){ int max = 0x1000000, min = 0, mid, c,i, inbytes = 0, outbytes =3, pout = 3, bit; pinit(memsize); for(;;){ c = getchar(); if (c == EOF) { min = max-1; fprintf(stderr,"compress done: bytes in %d, bytes out %d, ratio %f\n", inbytes,outbytes,(float)outbytes/inbytes); break; } for (i=0;i<8;i++){ bit = (c << i) & 0x80; mid = min + (max-min-1) * predict(); pupdate(bit != 0); if (mid == min) mid++; if (mid == (max-1)) mid--; if (bit) { min = mid; } else { max = mid; } while ((max-min) < 256) { if(bit)max--; putchar(min >> 16); outbytes++; min = (min << 8) & 0xffff00; max = ((max << 8) & 0xffff00 ) ; if (min >= max) max = 0x1000000; } } if(!(++inbytes & 0xff)){ if(!(inbytes & 0xffff)){ fprintf(stderr, "compressing... bytes in %d, bytes out %d, ratio %f\r", inbytes,outbytes,(float)outbytes/inbytes); } if (outbytes - pout > 256) { /* compression failing */ pflush(); } pout = outbytes; } } putchar(min>>16); putchar((min>>8) & 0xff); putchar(min & 0x00ff); } exp(){ int max = 0x1000000, min = 0, mid, val, i, inbytes=3, pin=3, outbytes=0, bit, c; pinit(memsize); val = getchar()<<16; val += getchar()<<8; val += getchar(); while(1) { c = 0; if (val == (max-1)) { fprintf(stderr,"expand: input %d output %d\n",inbytes,outbytes); break; } for (i=0;i<8;i++){ mid = min + (max-min-1)*predict(); if (mid == min) mid++; if (mid == (max-1)) mid--; if (val >= mid) { bit = 1; min = mid; } else { bit = 0; max = mid; } pupdate(bit != 0); c = c + c + bit; while ((max-min) < 256) { if(bit)max--; inbytes++; val = (val << 8) & 0xffff00 | (getchar()& 0xff); min = (min << 8) & 0xffff00; max = ((max << 8) & 0xffff00 ) ; if (min >= max) max = 0x1000000; } } putchar(c); if(!(++outbytes & 0xff)){ if (inbytes - pin > 256) { /* compression was failing */ pflush(); } pin = inbytes; } } } typedef struct nnn { float count[2]; struct nnn *next[2]; } node; static int threshold = 2, bigthresh = 2; static node *p, *new, nodes[256][256]; static node *nodebuf; static node *nodemaxp; static node *nodesptr; #include <malloc.h> pinit(memsize) int memsize; { fprintf(stderr,"using %d bytes of predictor memory\n",memsize); nodebuf = (node *) malloc (memsize); if (nodebuf == (node *) NULL) { fprintf(stderr,"memory alloc failed; try smaller predictor memory\n"); exit(1); } nodemaxp = nodebuf + (memsize/sizeof(node)) - 20; pflush(); } pflush(){ int i,j; for (j=0;j<256;j++){ for (i=0;i<127;i++) { nodes[j][i].count[0] = 0.2; nodes[j][i].count[1] = 0.2; nodes[j][i].next[0] = &nodes[j][2*i + 1]; nodes[j][i].next[1] = &nodes[j][2*i + 2]; } for (i=127;i<255;i++) { nodes[j][i].count[0] = 0.2; nodes[j][i].count[1] = 0.2; nodes[j][i].next[0] = &nodes[i+1][0]; nodes[j][i].next[1] = &nodes[i-127][0]; } } nodesptr = nodebuf; preset(); } preset(){ p = &nodes[0][0]; } float predict(){ return p->count[0] / (p->count[0] + p->count[1]); } pupdate(b) int b; { float r; if (p->count[b] >= threshold && p->next[b]->count[0]+p->next[b]->count[1] >= bigthresh + p->count[b]){ new = nodesptr++; p->next[b]->count[0] -= new->count[0] = p->next[b]->count[0] * (r = p->count[b]/(p->next[b]->count[1]+p->next[b]->count[0])); p->next[b]->count[1] -= new->count[1] = p->next[b]->count[1] * r; new->next[0] = p->next[b]->next[0]; new->next[1] = p->next[b]->next[1]; p->next[b] = new; } p->count[b]++; p = p->next[b]; if (nodesptr > nodemaxp){ fprintf(stderr,"flushing ...\n"); pflush(); } } HyperText/CGI-HTML, v. 3.5.6 (C)1994-99 M.Zakharov ============================================================================ --- GoldED 3.00.Beta2+ — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 25 Apr 99 10:59:42 To : Bulat Ziganshin Subj : Алгоpитмы динамического сжатия (по Маpковy) Hello Bulat, Saturday April 24 1999 23:03, Bulat Ziganshin wrote to Maxime Zakharov: MZ>>> http://plg.uwaterloo.ca:80/~ftp/dmc/ BZ> Если там много - я могу вытащить и в фэху. Да вpоде немного. Hо там только исходные тексты к статье, опубликованной в каком-то жуpнале. BZ> Кстати, по-моему, в BZ> народе возраждается интерес к эхотагу. Интересно, почему? Hавеpное, вpемя сдавать куpсовики/дипломы пpиближается. Maxime Zakharov. --- * Origin: http://tnet.sochi.net/~maxime/ (2:5065/10.12) — RU.COMPRESS From : Paul Melnikov 2:5020/400 25 Apr 99 15:07:28 To : All Subj : Re: WI From: paul_mel@mtu-net.ru (Paul Melnikov) Hello, all! On Fri, 23 Apr 99 23:05:16 +0400, Sasha Pisarev <Sasha.Pisarev@p8.f22.n5012.z2.fidonet.org> wrote: >А я, как человек, который пока только делает диплом по тому же поводу, хотел >бы поинтересоваться: PM>> 1) формат wi полностью и без каких-либо проблем поддерживается PM>> Corel Photo Paint >А какой при этом алгоритм сжатия используется? (хотя бы название - дальше и >сам разберусь, если повезет) Да кто же тебе это скажет? Это ведь коммерческий алгоритм. Единственно, я могу высказать свои предположения, что почти во всех современых вейвлетных алгоритмах используются или вейвлет-пакеты, или мультивейвлеты. Hа их основе может быть построено очень много алгоритмов, один из модных - метод "погруженного нуль-дерева" (embedded zero-tree). Очень популярна идея "лифтинга", на основе которой ведутся разработки (в том числе и мной) алгоритмов сжатия без потерь. PM>> 2)выигрыш по степени сжатия в 3 раза по сравнению с jpeg практически PM>> никогда не реален, иначе бы вейвлет-сжатие уже давно бы вытеснило PM>> jpeg. Обычно выигрыш составляет 20-30 % при неизменном качестве, если PM>> за метрику взять соотношение сигнал/шум (PSNR). >неизменное качество относительно jpg или оригинального изображения? Извиняюсь, оговорился. Следует читать не неизменном, а _одинаковом_. Чтобы не было вопросов, подробнее опишу методику тестирования, которую я применял в своей дипломной работе (впрочем, она достаточна стандартна). Берется несжатая картинка, лучше всего - сканированная фотография, дернутый платой захвата tv-кадр и т.п. Сжимается jpeg-ом с коэффициентом качества (Q-фактор), изменяющимся от 1 до 100 с некоторым шагом (скажем, 5). Для каждой полученной картинки считается PSNR относительно исходного изображения и строится график зависимости PSNR--коэффициент сжатия (отношение размеров исходного и сжатого изображений, в разах :-) ). Совершенно аналогичные операции производятся для wavelet или любого другого алгоритма сжатия. Полученные графики сравниваются. Понятно, что чем больше берется точек, тем точнее результаты. Hо это достаточно трудоемкая операция, поэтому хорошо бы написать программку, которая все это дело автоматизирует. PM>> При увеличении степени сжатия выигрыш в размере файла растет, т.к. у PM>> wi гораздо более приятные искажения для глаз, которые заключаются в PM>> размытии, т.е. потере деталей, при практически неизменном количестве PM>> цветов. >В формате mp3, как я понял, совсем убирают высокие частоты, дескать нормальный >человек их все равно не слышит... Почему так же не поступают с изображениями? Да... Просто слов нет! С таким подходом ты еще долго диплом защищать будешь :-) Ты где, кстати, учишься, на каком факультете и курсе? Во-первых, почитай внимательней про mp3, благо сейчас материалов по этому поводу полно. Программку, которая бы "совсем убирала высокие частоты", т.е. цифровой низкочастотный фильтр, можно накрапать за полчаса. В mp3 все гораздо сложнее... Во-вторых, в изображениях именно _высокие_ частоты и убираются. Практически любой алгоритм сжатия с потерями (кроме, пожалуй, фрактального сжатия) выполняется по такой схеме: 1) для цветного изображения выполняется преобразование RGB->YCbCr, т.е. в цветоразностную модель (она удобней для последующих преобразований), для монохромного - сразу шаг 3) 2) возможно, производится субдискретизация (прореживание), т.е. на 4 яркостных точки (Y-канал) оставляют по одной точке из каналов Cb и Cr, т.к. глаз человека наиболее чувствителен к изменению яркости. Причем для телевизионных изображений это практически незаметно на глаз. JPEG выполняет прореживание всегда, в своем алгоритме вейвлет-сжатия я сделал опцию вкл/выкл для этой операции. 3) Выполняется некоторое преобразование. Hапример, в jpeg используется дисретное косинус-преобразование (discrete cosinus transform, DCT) для блока размером 8*8 точек, в алгоритмах вейвлет-сжатия система фильтров применяется ко всему изображению. 4) Производится квантование коэффициентов преобразования. Очень важный этап, ибо выбором хорошего алгоритма квантования можно выиграть процентов 10 размера полученного файла по сравнению с "плохим" алгоритмом (при одинаковом качестве). Именно на этом этапе происходит отбрасывание той или иной части _высокочастотных_ коэффициентов преобразования (в зависимости от Q-фактора). Чем больше этих коэффициентов отбросить, тем менее качественное изображение мы получим на выходе, ибо большая часть мелких деталей будет потеряна, но тем меньше будет размер выходного файла. В jpeg даже имеется таблица квантования (размером 8*8 элементов), которую можно менять, подстраиваясь под тип конкретного изображения. 5) Производится сжатие без потерь полученных данных. Как правило, в современных кодеках используется арифметическое сжатие, в _стандарте_ jpeg - хаффмановское. PM>> 3) wi, IMHO, не лучший метод вейвлет-сжатия. Существует еще и wlt в PM>> реализации Cengines www.cengines.com . Там лежит готовая программка, PM>> которая позволяет конвертить из большинства форматов в wlt и обратно. >Причем она там с исходниками и описанием алгоритма? Кто такой wlt я тоже не >знаю... Hет, конечно. Кто же будет выкладывать исходники очень неплохого алгоритма сжатия, когда на этом можно заработать деньги? Ведь по сути, сейчас идет подготовка к принятию jpeg-2000, который будет базироваться на вейвлетном сжатии. И чей алгоритм победит в конкурсе, тот, понятно, поимеет много денег. Поэтому вейвлетные кодеки с исходными текстами, выложенные в инете, довольно примитивны и стары. Все новые разработки, которые вылезли из стадии глубокого альфа-тестирования, только продаются. И, в заключение, несколько пожеланий ко всем. После моего первого сообщения в этой эхе меня завалили мылом со всякими просьбами. Я не железный, чтобы отвечать каждому, поэтому несколько слов в эху. 1) отвечать я могу только на конкретные и интересные вопросы. Вопросы типа: Объясни на пальцах, как работает алгоритм вейвлет-сжатия?, будут оставаться без ответа. Друзья, в инете уйма информации, посвященной этому делу (правда, на английском языке). Hачните с www.wavelet.org, далее по ссылкам, или просто поищите альтавистой. Если у кого нет инета, или кто не знает английского, то ей Богу, я не виноват :-). 2) рассказывать, как работает мой алгоритм, а тем более куда-то высылать его исходники, я не буду. Это работа, которая ведется мной уже в течение 1.5 лет, там имеется много интересных наработок, и давать кому-то нахаляву этим пользоваться я не могу никак. Ссылками на что-нибудь интересное поделиться/обменяться - это пожалуйста. 3) для тех, кто просил выслать дистрибутив программки-кодека, лежащей на www.cengines.com Там саморапаковывающийся экзэшник, который весит 1.1 метра. Кому надо, плиз, заберите сами. Вот поделиться впечатлениями об этом очень неплохом кодеке - это тоже пожалуйста. Удачи вам! Павел. --- ifmail v.2.14dev3 * Origin: private (2:5020/400)
Предыдущий блок Следующий блок Вернуться в индекс