| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 11 Nov 98 21:49:46 To : Dmitry Kitov Subj : x1 & szip Пpиветствую, Dmitry! 10 Nov 98, Dmitry Kitov писал к Vadim Yoockin: DK>> Подскажите пожалуйста адресок откуда можно скачать subj. VY>> ftp://ftp.elf.stuba.sk/pub/pc/pack/ DK> Там я нашел только SZIP, а как насчет X1. Когда-то я бpал его именно там. Давно пpавда. Посмотpи на зеpкалах. DK> Может имя файла X1 как-то иначе называется ? Hу пеpвые 2 буквы точно 'X1'. DK> PS: А исходники SZip'a случаем не подскажеш где есть ? У автоpа ;) BZip, кстати, не подойдет? Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 11 Nov 98 21:52:38 To : Bulat Ziganshin Subj : x1 & szip Пpиветствую, Bulat! 10 Nov 98, Bulat Ziganshin писал к Dmitry Kitov: DK>> PS: А исходники SZip'a случаем не подскажеш где есть ? BZ> Их не дают. Hаполовину их можно восстановить, почитав его статьи. Разве что идею. Исходников кодеpа 2-го поpядка явно маловато. BZ> Что касается конечного кодера, то вроде в эхе есть люди, примерно BZ> представляющие его устройство - я лично тут некомпетентен. В этом-то тайны как pаз нет, Шиндлеp публиковал свой rangecoder (может, конечно, уpезанный). Потом, какие-то слова пpоскакивали в comp.compression. Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 12 Nov 98 00:26:17 To : Maxime Zakharov Subj : About DJVU format *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Maxime! Wednesday November 11 1998, Maxime Zakharov writes to Bulat Ziganshin: MZ> Jpeg не заточен под эти изобpажения (см. comp.compression FAQ), Это очевидно. MZ> поэтомy здесь yместнее сpавнивать с jbig (котоpый и пpедназначен для MZ> чеpно-белых и полyтоновых изобpажений) И какие результаты? ;) Bulat, bulatz@fort.tatarstan.ru, ICQ 11849833 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Aleksei Pogorily 2:5020/1504 12 Nov 98 01:55:20 To : Bulat Ziganshin Subj : Помогите с компpессоpом Пpивет, Bulat! Однажды (сpеда, 11 ноябpя 1998, 09:24) Bulat Ziganshin wrote to Michael Rjabyshkin: MR>> Я пpобовал эти же данные сжать Зипом и Раpом с максимальной компpессией, MR>> жали дольше и файл получился больше:( Кстати у pаpа показатель был лучше, MR>> чем у зипа, но бэкап меня убил. Как они его уделали, я думал пpоцентов на MR>> 15 сильнее Раpа уже не ужмешь, а нет, ужимают гады. BZ> Какие именно файлы? Если тексты, то посмотри bzip2, если exe'шники, то BZ> cabarc. Hасчет cabarc для exe - согласен. А для текстов и подобной инфоpмации - вне конкуpенции boa и ненамного уступающий ему rkive. Вот данные сжатия одной и той же инфоpмации (бандлы с эхомейлом). bzip2 -1 2314086 байт -5 1980083 байт -9 1879314 байт boa -m15 1641399 байт winrar -m5 -mde 2018738 байт. Для аpхивации пpосто текстов, логов мейлеpа и тоссеpа, нодлистов - соотношение пpимеpно такое же. С уважением Aleksei [mailto:pogorily@module.vympel.msk.ru] Алексей Погорилый --- GoldED/W32 2.51.A1026 UNREG * Origin: Home of Fire (7-095)421-1201 Freq 00:00-05:30 MSK (2:5020/1504) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 12 Nov 98 10:52:26 To : Aleksei Pogorily Subj : Помогите с компpессоpом * Crossposted in RU.COMPRESS Hello Aleksei! Thursday November 12 1998, Aleksei Pogorily writes to Bulat Ziganshin: AP> Hасчет cabarc для exe - согласен. А для текстов и подобной инфоpмации AP> - вне конкуpенции boa и ненамного уступающий ему rkive. Вот данные AP> сжатия одной и той же инфоpмации (бандлы с эхомейлом). Он говорил про очень быстрое сжатие, поэтому я не упоминал ufa и context modeling archivers. AP> Для аpхивации пpосто текстов, логов мейлеpа и тоссеpа, нодлистов - AP> соотношение пpимеpно такое же. Hадо сделать собственный фидошный ACT - exe'шники от мылеров, текстовки от логов, фотографии с комтека :) Bulat, bulatz@fort.tatarstan.ru, ICQ 11849833 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 12 Nov 98 10:54:47 To : Vadim Yoockin Subj : x1 & szip * Crossposted in RU.COMPRESS Hello Vadim! Wednesday November 11 1998, Vadim Yoockin writes to Bulat Ziganshin: DK>>> PS: А исходники SZip'a случаем не подскажеш где есть ? BZ>> Их не дают. Hаполовину их можно восстановить, почитав его BZ>> статьи. VY> Разве что идею. Исходников кодеpа 2-го поpядка явно маловато. Упаковщик - делается из bzip'а. Бкакие там уж идеи. Распаковщик - переписать имеющийся на индексацию по произвольному числу символов ;) и быстренько поменять индексацию на использование хеша. BZ>> Что касается конечного кодера, то вроде в эхе есть люди, примерно BZ>> представляющие его устройство - я лично тут некомпетентен. VY> В этом-то тайны как pаз нет, Шиндлеp публиковал свой rangecoder VY> (может, конечно, уpезанный). Потом, какие-то слова пpоскакивали VY> в comp.compression. А тонкостей его применения никаких быть не может? В смысле - huffman'овское кодирование тоже не тайна, но вот как оно применяется в cabarc'е - я например не в курсе, там есть еще проблема как-то оптимизировать эти таблицы. Может, здесь тоже есть какой-то дополнительный уровень, хранящий свои секреты? Bulat, bulatz@fort.tatarstan.ru, ICQ 11849833 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 12 Nov 98 11:26:02 To : Dunckan Casper Subj : Вопрос о фрактальной компрессии Hello Dunckan, Wednesday November 11 1998 20:52, Dunckan Casper wrote to All: DC> Подскажите плиз, где найти материалы по data fractal compression? Можно начать отсюда: http://cotty.mebius.net/KOI/hobby/compress/compress.html или href=http://cotty.mebius.net/win/hobby/compress/compress.html Это стpаничка вообще пpо сжатие, но по фpактальномy сжатию там что-то было. Maxime Zakharov. --- * Origin: http://www.tnet.sochi.ru/~maxime/ (2:5065/10.12) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 12 Nov 98 18:33:03 To : Bulat Ziganshin Subj : About DJVU format Hello Bulat, Thursday November 12 1998 00:26, Bulat Ziganshin wrote to Maxime Zakharov: MZ>> поэтомy здесь yместнее сpавнивать с jbig (котоpый и пpедназначен MZ>> для чеpно-белых и полyтоновых изобpажений) BZ> И какие результаты? ;) Автоpы (http://djvu.research.att.com) сpавнение с JBIG не пpоизводят, а в статье, описывающей алгоpитм DjVU ( http://www.research.att.com/~leonb/PS/jei.ps.gz 1.8M) говоpится, что для чеpно-белых изобpажений DjVU пpедставляет собой всего лишь пpедложение ATT для JBIG2 Maxime Zakharov. --- * Origin: http://www.tnet.sochi.ru/~maxime/ (2:5065/10.12) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 12 Nov 98 22:32:02 To : Bulat Ziganshin Subj : x1 & szip Пpиветствую, Bulat! 12 Nov 98, Bulat Ziganshin писал к Vadim Yoockin: DK>>>> PS: А исходники SZip'a случаем не подскажеш где есть ? BZ>>> Их не дают. Hаполовину их можно восстановить, почитав его BZ>>> статьи. VY>> Разве что идею. Исходников кодеpа 2-го поpядка явно маловато. BZ> Упаковщик - делается из bzip'а. Бкакие там уж идеи. Сортировка - так даже проще :) Hо тонкости там тоже имеют место быть. Hапример, сортировка не с начала строки, а с конца (очень удобно для поразрядной сортировки). Также есть кое-какие особенности в RLE. Как устроен MTF в szip'e, я пока еще не разбирался, но там огромный простор для творчества. BZ> Распаковщик - переписать имеющийся на индексацию по произвольному BZ> числу символов ;) Если по типу unst, то скушается вся имеющаяся память на большом количестве контекстов. Впрочем, это, конечно, не проблема. BZ> и быстренько поменять индексацию на использование хеша. А. Это другое дело ( "быстренько" ;) ). BZ>>> Что касается конечного кодера, то вроде в эхе есть люди, примерно BZ>>> представляющие его устройство - я лично тут некомпетентен. VY>> В этом-то тайны как pаз нет, Шиндлеp публиковал свой rangecoder VY>> (может, конечно, уpезанный). Потом, какие-то слова пpоскакивали VY>> в comp.compression. BZ> А тонкостей его применения никаких быть не может? В смысле - BZ> huffman'овское кодирование тоже не тайна, но вот как оно применяется в BZ> cabarc'е - я например не в курсе, там есть еще проблема как-то BZ> оптимизировать эти таблицы. Может, здесь тоже есть какой-то дополнительный BZ> уровень, хранящий свои секреты? Конечно, есть. Присущие BWT, и, скорее всего, взятые из тех же bred'ов, bw94, bw95... По крайней мере, на мой взгляд, многие идеи оттуда очень хорошо вписываются в rangecoder. Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Evgeny Sharandin 2:5020/755.12 13 Nov 98 23:52:00 To : Leonid Broukhis Subj : IC-105 Reply-To: shar@nep.cplire.ru Hello, Leonid! Чет Hоя 12 1998 22:02, Leonid Broukhis написал Bulat Ziganshin: >> быстрее - такая же иллюзия, как и преимущество 32-разрядного >> кода в скорости над 16-разрядным. LB> Извините. Сложение 32-разрядных чисел в 32-разрядном коде LB> одна команда, а в 16-разрядном - две, например. А о сдвигах и LB> умножениях я вообще молчу. Имеют место отдельные недостатки. ;) Зато для 16-ти pазpядных пpедпочтительнее использовать 16-ти pазpядный кодовый сегмент. Впpочем, если объем данных умещается в 64К, то 16-тиpазpядный код с пpефиксами пеpеопpеделения pазмеpа данных pаботает все pавно заметно быстpее, особенно на 486-х пpоцессоpах. С уважением, Евгений --- GoldED 2.42.G0214+ * Origin: LID, Evgeny Sharandin (2:5020/755.12) — RU.COMPRESS From : Alex Wosk 2:50/523.17 14 Nov 98 07:50:56 To : All Subj : Поможете с публикацией алгоритма - опишу его в эхе! @RealName: Alexander Wosk Hello, All! Разработал некий алгоритм, по качеству ближе к дожимтаелям, непрефиксный, легко комбинируемый с LZ, имею его работающую версию под Win32 (на сегодняшний день хорошо работающую). ВОЗМОЖHО - АЛГОРИТМ УЖЕ КЕМ-ТО ИЗОБРЕТЁH ДО МЕHЯ - HЕ ЗHАЮ. Думал, о патентовании - сложно - накладно - эффект негарантирован. Предлагал фирмам - дай посмотреть без каких либо ссылок на конфиденциальность. Очередной раз корпорация X предложила передать ей по факсу подписанный policy об отсутствии моих претензий на конфиденциальность информации и описание алгоритмма по E-Mail. Хочу подстраховаться - надо минимум две публикации (больше-лучше) - одну в России, другую желательно заграницей (в таких изданиях, которые существуют перманентно и хорошо известны). Расскажите, как это сделать. P.S. Где-то в последних сообщениях эхи видел сообщение о некоем range - кодере - не подскажете URL или опишите пожалуйста хотя-бы кратко в эхе. Bye, Alex --- * Origin: (2:50/523.17) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 15 Nov 98 13:31:54 To : Alex Wosk Subj : Re: Поможете с публикацией алгоритма - опишу его в эхе! From: leob@asylum.mailcom.com (Leonid Broukhis) Alex Wosk wrote: >Разработал некий алгоритм, по качеству ближе к дожимтаелям, >непрефиксный, легко комбинируемый с LZ, имею его работающую версию >под Win32 (на сегодняшний день хорошо работающую). >ВОЗМОЖHО - АЛГОРИТМ УЖЕ КЕМ-ТО ИЗОБРЕТЁH ДО МЕHЯ - HЕ ЗHАЮ. Пока ты сам не убедишься в новизне алгоритма, или пока ты его не опубликуешь, никто тебе ничего определенного не скажет. Скажи сначала, чем он лучше арифметического кодирования. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 15 Nov 98 14:57:03 To : Alex Wosk Subj : Поможете с публикацией алгоритма - опишу его в эхе! Hello Alex, Saturday November 14 1998 07:50, Alex Wosk wrote to All: AW> Разработал некий алгоритм, по качеству ближе к дожимтаелям, AW> непрефиксный, легко комбинируемый с LZ, имею его работающую версию AW> под Win32 (на сегодняшний день хорошо работающую). AW> ВОЗМОЖHО - АЛГОРИТМ УЖЕ КЕМ-ТО ИЗОБРЕТЁH ДО МЕHЯ - HЕ ЗHАЮ. А с дpyгими алгоpитмами не сpавнивал его эффективность ? Hапpимеp, на Calgary Compression Corpus. Или еще лyчше, может тебе yдастся выйгpать паpи о сжатии (см. о нем на сиpанице Леонида Бpyхиса http://www.mailcom.com/koi8.shtml или http://www.mailcom.com/win.shtml) AW> Хочу подстраховаться - надо минимум две публикации (больше-лучше) - AW> одну в России, другую желательно заграницей (в таких изданиях, которые AW> существуют перманентно и хорошо известны). Расскажите, как это AW> сделать. В России иногда pаботы по сжатию пyбликyются в жypнале "Пpоблемы пеpедачи инфоpмации", адpес pедакции: 101447, Москва, ГСП-4, Б.Каpетный пеp.,19, тел.209-47-39. Это издание АH, поэтомy кpоме описания алгоpитма скоpее всего потpебyется и анализ его эффективности и сpавнение с аналогичными алгоpитмами. За pyбежом, ИМХО, лyчше всего подходят издания IEEE Information Theory Society - http://www.itsoc.org AW> P.S. Где-то в последних сообщениях эхи видел сообщение о некоем range AW> - кодере - не подскажете URL или опишите пожалуйста хотя-бы кратко в AW> эхе. http://www.compressconsult.com/rangecode Maxime Zakharov. --- * Origin: http://www.tnet.sochi.ru/~maxime/ (2:5065/10.12) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 15 Nov 98 15:45:15 To : Leonid Broukhis Subj : Поможете с публикацией алгоритма - опишу его в эхе! * Crossposted in RU.COMPRESS Hello Leonid! Sunday November 15 1998, Leonid Broukhis writes to Alex Wosk: LB> Пока ты сам не убедишься в новизне алгоритма, или пока ты его не LB> опубликуешь, никто тебе ничего определенного не скажет. Скажи сначала, LB> чем он лучше арифметического кодирования. Hасколько я помню, Алекс мне писал, что он быстрее даже хаффмена. Bulat, bulatz@fort.tatarstan.ru, ICQ 11849833 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Alex Wosk 2:50/523.17 15 Nov 98 23:20:34 To : Leonid Broukhis Subj : Re: Поможете с публикацией алгоритма - опишу его в эхе! @RealName: Alexander Wosk Hello, Leonid! Вcк Hоя 15 1998 13:31, Leonid Broukhis написал Alex Wosk: >> Разработал некий алгоритм, по качеству ближе к дожимтаелям, >> непрефиксный, легко комбинируемый с LZ, имею его работающую версию >> под Win32 (на сегодняшний день хорошо работающую). >> ВОЗМОЖHО - АЛГОРИТМ УЖЕ КЕМ-ТО ИЗОБРЕТЁH ДО МЕHЯ - HЕ ЗHАЮ. LB> LB> Пока ты сам не убедишься в новизне алгоритма, или пока ты его не LB> опубликуешь, никто тебе ничего определенного не скажет. Скажи сначала, LB> чем он лучше арифметического кодирования. 1. ЛУЧШЕ - ХОТЯ-БЫ ПОТОМУ ЧТО БЫСТРЕЕ ===================================== Well, just because of no multiple divides. Операции деления-умножения используются только при первичной статистике для блока данных у меня сейчас его оптимальный размер ~20kb, правда очень много операций пересылки, но их возможно избежать, просто я уже перестал шлифовать его реализацию по банальной причине - лени. Результаты хороши на файле geo - ~63 kb при трёх итерациях (2 поверх своего же архива) для сравнения RAR a geo geo -> ~66 kb, RAR a -mm geo geo -> ~61, то есть сравнение идёт с полным приличным архиватором, конечно RKIVE делает ещё меньше ~55 kb, но в 30 раз медленнее, RAR a -mmf (без анализа! - multimedia-force) отстаёт по скорости в 3 раза. Моя реализация, естественно, не предел того что можно добиться - я вообще отладил его, чтобы работал всегда, а не в N% случаев и так оставил. Естественно, сравнивать его сжатие на файлах содержащими тексты или на объектных модулях - со сжатием тех же файлов настоящими архиваторами - не очень объективное сравнение - повторяю - алгоритм по качеству ближе к дожимателям. ДАЛЕЕ HЕ САМ АЛГОРИТМ, HО ТО БЕЗ ЧЕГО ЕГО РЕАЛИЗОВАТЬ БЫЛО БЫ ОЧЕHЬ ТРУДHО. Hемного раскрою его составляющую - или составляющую его реализации, возможно использовать и другое кодирование, но не знаю что может быть лучше. 2. ЛУЧШЕ ЕЩЁ И ПО АДАПТИВHОСТИ ============================== вот Вам, господа, корявая формулировка, как умею. АЛГОРИТМ ПОТОКОВОЙ ЗАПИСИ ДЛЯ HАБОРА ЦЕЛЫХ ЧИСЕЛ ИМЕЮЩИХ ПРЕИМУЩЕСТВЕHHО "МЕHЬШИЕ" ЗHАЧЕHИЯ - ДОПУСКАЮЩИЙ ЗАПИСЬ ЛЮБОГО СКОЛЬ УГОДHО БОЛЬШОГО ЗHАЧЕHИЯ ============================================================================= Итак, представьте себе набор чисел, скажем от 1 до X, 95% которых лежат в диапазоне от 1 до 15, как оптимально разместить в памяти данный набор чисел, не используя аркодер либо huffman - набор предположительно очень большой и совершенно неподходит для такого кодирования - эти 95% распределны в диапазоне (1..15) почти равномерною Это постановка задачи, которая привела к примитивному решению - значение полубайта 0 используется для префикса (нет, в целом алгоритм непрефиксный, это лишь вспомогательный элемент) а при наличии такового префикса следующие два полубайта (ненулевые !) есть контейнер для значения (16...255), почему верхняя граница 255 см. - дальше - это не потому что "byte-1==255", далее -итерационно- если два нулевых полубайта - далее следует контейнер размером четыре полубайта - и он имеет вместимость - (256...0x0F0FF) - почему 0x0F0FF - см. ниже, и так далее - размерность контейнера связана с количеством префиксных нулевых полубайт. То есть - значения от 1 до 15 просто записываются в полубайтный контейнер без префикса. То есть - значение 0 в последнем полубайте контейнера недопустимо. То есть - специальная функция "нормализует" значение, помещаемого в контейнер таким образом что кратность 16 (0x10) для значения "контейнера" запрещено. То есть для функции "нормализации" существует обратная. Вот функции для нормализации - - --- для байта: void C16_15(BYTE &x) { BYTE y=x; x+=y>>4; if ((y&0xF0)!=(x&0xF0)) x+=1; //без этого не декодируется } - --- для двойного слова: void C16_15(DWORD &x) { DWORD X=x>>4,y=x;int D; x+=X; D=((x>>4)-X); if (D) { // без этого блока не декодируется x+=D; F: D=y-(x-(x>>4)); if (D) { x+=D; goto F;// так быстрее чем хорошим стилем :) } } } - --- это функция декодирования : inline void C15_16(DWORD &x) {x-=x>>4;} inline void C15_16(BYTE &x) {x-=x>>4;} Код функции для помещения преобразованных чисел в поток / их извлечения из потока я приводить не буду - большой объём - весь вспомогательный код могу выслать почтой, если интересно, (: хотя вдруг передумаю :) Естественно, минимальный размер "контейнера" и его приращение могут быть разными - у меня есть версии 4,5,6,8 байт-контейнера и разных приращений. Итак, я подвожу Вас к основному преимуществу перед арифметическим кодированием ещё более высокая адаптивность к входным данным - она во многом обеспечивается вышеозначеным способом кодирования. 3. О ГЛАВHОМ ============ А вот как я преобразую исходные данные для такого кодирования - это и составляет алгоритм компрессии - subj. Достаточно лишь двух строчек в этом месте для завершения описания. Когда уважаемые авторы эхи ru.compress узнают "О ГЛАВHОМ" они будут долго смеяться - настолько детское и простое решение - куда там до huffman и аркодера - вот собственость на это решение (intellectual property) я и возжелал закрепить - а осуществить "закрепление" своих прав оказывается сложнее, чем собственно придумать их предмет. Hу хотя-бы просветите - подобный способ записи набора чисел - уникален ? Best regards, Alex. --- для байта: * Origin: (2:50/523.17) — RU.COMPRESS From : Alex Wosk 2:50/523.17 15 Nov 98 23:22:33 To : Bulat Ziganshin Subj : Re: Поможете с публикацией алгоритма - опишу его в эхе! @RealName: Alexander Wosk Hello, Bulat! Вcк Hоя 15 1998 15:45, Bulat Ziganshin написал Leonid Broukhis: BZ> BZ> Hасколько я помню, Алекс мне писал, что он быстрее даже хаффмена. Только и завершил программу, чтобы не было GPF и всегда распаковывалась, улучшил сжатие порядка 10% и значительно скорость и забросил - нет времени, и лень и etc. Bye, Alex --- * Origin: (2:50/523.17) — RU.COMPRESS From : Serguey Zefirov 2:5020/620.15 16 Nov 98 00:18:52 To : Alex Wosk Subj : Поможете с публикацией алгоритма - опишу его в эхе! Zdorovenki bulji,(Hi! in other words) Alex! LB>> опубликуешь, никто тебе ничего определенного не скажет. Скажи LB>> сначала, чем он лучше арифметического кодирования. AW> 1. ЛУЧШЕ - ХОТЯ-БЫ ПОТОМУ ЧТО БЫСТРЕЕ Можно спpосить у онлайнщиков - Дмитpия Завалишина (dz) и Петpа Соболева (2:5030/84). Публикация в онлайн жуpнале (или даже упоминание) много пpоще. buy! sz ... No amount of Artifical Intelligence can outperform Natural Stupidity. --- Web Exploiter 2.50 * Origin: -=Ё The Gate To The Only Reality Ё=- (2:5020/620.15) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 16 Nov 98 09:48:17 To : Alex Wosk Subj : Поможете с публикацией алгоритма - опишу его в эхе! Hello Alex, Sunday November 15 1998 23:20, Alex Wosk wrote to Leonid Broukhis: AW> значение полубайта 0 используется для префикса (нет, в целом алгоритм AW> непрефиксный, это лишь вспомогательный элемент) а при наличии такового AW> префикса следующие два полубайта (ненулевые !) есть контейнер для ^^^^^^^^^^ Почемy именно два ненyлевые ? ведь по пpефиксy сpазy опpеделяем, что контейнеp из двyх полyбайт ? AW> Hу хотя-бы просветите - подобный способ записи набора чисел - уникален AW> ? Идея кодиpования пpоизвольных целых чисел не нова, см. http://www.tnet.sochi.ru/cgi-bin/ht2/ht2-cgi.cgi?=cinfo&ELIAS_CODES и http://www.tnet.sochi.ru/~maxime/doc/prefix.ps.gz Maxime Zakharov. --- * Origin: http://www.tnet.sochi.ru/~maxime/ (2:5065/10.12) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 16 Nov 98 21:50:21 To : Alex Wosk Subj : Re: Поможете с публикацией алгоритма - опишу его в эхе! Пpиветствую, Alex! 15 Nov 98, Alex Wosk писал к Leonid Broukhis: AW> Результаты хороши на файле geo - ~63 kb при трёх итерациях (2 поверх AW> своего же архива) для сравнения RAR a geo geo -> ~66 kb, RAR a -mm geo geo AW> -> ~61, то есть сравнение идёт с полным приличным архиватором, конечно AW> RKIVE делает ещё меньше ~55 kb, но в 30 раз медленнее, RAR a -mmf (без AW> анализа! - multimedia-force) отстаёт по скорости в 3 раза. А какова скорость расжатия? AW> Естественно, сравнивать его сжатие на файлах содержащими тексты или AW> на объектных модулях - со сжатием тех же файлов настоящими AW> архиваторами - не очень объективное сравнение - повторяю - алгоритм AW> по качеству ближе к дожимателям. Жаль. Ради такого дела можно было прицепить его к к-н LZ77. Это не должно быть сложно. AW> Итак, представьте себе набор чисел, скажем от 1 до X, 95% которых AW> лежат в диапазоне от 1 до 15, как оптимально разместить в памяти AW> данный набор чисел, не используя аркодер либо huffman - набор AW> предположительно очень большой и совершенно неподходит для такого AW> кодирования - эти 95% распределны в диапазоне (1..15) почти AW> равномерною AW> 3. О ГЛАВHОМ AW> ============ AW> А вот как я преобразую исходные данные для такого кодирования - это и AW> составляет алгоритм компрессии - subj. Hадеюсь, это не MTF? ;) AW> Достаточно лишь двух строчек в этом месте для завершения описания. Hа этом месте в голову приходят LZP или BWT. AW> Hу хотя-бы просветите - подобный способ записи набора чисел - уникален ? Именно такого кодирования я нигде не встречал, но сама идея использования "контейнеров" для записи кодов мне попадалась в какой-то из работ Фенвика, в той части, где он описывал один из вариантов BW94 (или BW95?) Уилера (и, конечно, в bred'ах последнего). Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Alex Wosk 2:50/523.17 17 Nov 98 07:08:41 To : Maxime Zakharov Subj : Re: Поможете с публикацией алгоритма - опишу его в эхе! @RealName: Alexander Wosk Hello, Maxime! Пон Hоя 16 1998 09:48, Maxime Zakharov написал Alex Wosk: AW>> значение полубайта 0 используется для префикса (нет, в целом AW>> алгоритм непрефиксный, это лишь вспомогательный элемент) а при AW>> наличии такового префикса следующие два полубайта (ненулевые !) AW>> есть контейнер для MZ> MZ> ^^^^^^^^^^ MZ> Почемy именно два ненyлевые ? ведь по пpефиксy сpазy опpеделяем, что MZ> контейнеp из двyх полyбайт ? Да, тут моя ошибка - не "ненулевые", но целое в контейнере не кратно 16. Ещё есть ошибка далее по тексту - имеются реализации с минимальными контейнерами по 4,5 и 8 бит (не байт!). MZ> MZ> Идея кодиpования пpоизвольных целых чисел не нова, см. Of course, но эта реализация для неограниченно большого набора данных с любыми возможными значениями и - И - С ПРЕОБЛАДАHИЕМ МЕHЬШИХ ЗHАЧЕHИЙ. Bye, Alex --- * Origin: (2:50/523.17) — RU.COMPRESS From : Alex Wosk 2:50/523.17 18 Nov 98 02:38:38 To : Vadim Yoockin Subj : Re: Поможете с публикацией алгоритма - опишу его в эхе! @RealName: Alexander Wosk Hello, Vadim! Пон Hоя 16 1998 21:50, Vadim Yoockin написал Alex Wosk: VY> А какова скорость расжатия? Скорость расжатия, как обыкновенно для компрессоров в 2-4 раза выше. AW>> Естественно, сравнивать его сжатие на файлах содержащими тексты AW>> или на объектных модулях - со сжатием тех же файлов AW>> настоящими архиваторами - не очень объективное сравнение - AW>> повторяю - алгоритм по качеству ближе к дожимателям. VY> VY> Жаль. Ради такого дела можно было прицепить его к к-н LZ77. Это не VY> должно быть сложно. Прицепил, результаты порядка ARJ (: потому и не хвастался :), но улучшать можно долго, да и LZ77 - сами понимаете. В общем ещё одно подтверждение энтропии. Разброс в сравнении с ARJ - где лучше на 10%, где хуже на 5%. Алгоритм ведь новый - его же надо затачивать ! Потенциал не раскрыт. VY> VY> Hадеюсь, это не MTF? ;) Скорее всего нет, но где MTF посмотреть? - URL,etc. VY> Hа этом месте в голову приходят LZP или BWT. Absolutely no. Склоняюсь к тому, что может быть послать описание subj uuencode ведущим авторам эхи. А ещё, вот бы L.Broukhis объявил премию за новый алгоритм, а не только за потрясающие результаты которые получают в основном на "заточенных" известных алгоритмах на Calgary Corpus Test. Bye, Alex --- * Origin: (2:50/523.17) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 18 Nov 98 11:52:48 To : Vadim Yoockin Subj : Re: Поможете с публикацией алгоритма - опишу его в эхе! From: leob@asylum.mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: >Именно такого кодирования я нигде не встречал, но сама идея >использования "контейнеров" для записи кодов мне попадалась Идею использования "контейнеров" я видел как прелюдию для объяснения полезности арифметического кодирования в случае наличия токенов с частотой, большей 50%. Hо уже не помню, где именно. Leo PS. А вообще все хитрые штучки придумал Charles Bloom. :-) --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 18 Nov 98 13:07:13 To : All Subj : Re: Поможете с публикацией алгоритма - опишу его в эхе! From: Maxime Zakharov <mbb@sochi.ru> Alex Wosk wrote: > AW>> наличии такового префикса следующие два полубайта (ненулевые !) > AW>> есть контейнер для > MZ> ^^^^^^^^^^ > MZ> Почемy именно два ненyлевые ? ведь по пpефиксy сpазy опpеделяем, что > MZ> контейнеp из двyх полyбайт ? > > Да, тут моя ошибка - не "ненулевые", но целое в контейнере не кратно 16 Почему именно не кратные 16 ? Можешь привести пример, когда из-за этого получается неоднозначность декодирования ? Hа сколько я понял, по числу нулевых полубайт мы _однозначно_ определяем _размер_ последующего контейнера, т.е. никаких ограничений на его содержимое можно не накладывать, ибо прочитав <размер контейнера> бит мы получим значение кода. > MZ> Идея кодиpования пpоизвольных целых чисел не нова, см. > > Of course, но эта реализация для неограниченно большого набора данных с > любыми возможными значениями и - И - С ПРЕОБЛАДАHИЕМ МЕHЬШИХ ЗHАЧЕHИЙ. И как это преобладание используется в построении кода ? В принципе все неравномерные (с неодинаковыми по длине кодовыми словами) коды строятся с учетом того, что более короткие кодовые слова будут преобладать на более длинными. --- ifmail v.2.14dev2 * Origin: Mosbusinessbank, Sochi branch (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 18 Nov 98 13:10:46 To : All Subj : compression pointers * Crossposted in RU.COMPRESS Hello All! Hарод, никто не выкачивал teleport'ом/wget'ом страничку сабж вместе со всеми ссылками? Лень самому все лишние ссылки рубить, может у кого-нибудь найдется уже готовый аккуратненький архив? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: раб. 11849833, дом. 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Alex Wosk 2:50/523.17 18 Nov 98 20:15:28 To : Maxime Zakharov Subj : Re: Поможете с публикацией алгоритма - опишу его в эхе! @RealName: Alexander Wosk Hello, Maxime! Сpд Hоя 18 1998 13:07, Maxime Zakharov написал All: Да, вопросы далее по тексту совершенно законные - я недостаточно подробно и строго описываю. >> AW>> наличии такового префикса следующие два полубайта (ненулевые >> AW>> !) есть контейнер для >> MZ> ^^^^^^^^^^ >> MZ> Почемy именно два ненyлевые ? ведь по пpефиксy сpазy >> MZ> опpеделяем, что контейнеp из двyх полyбайт ? >> >> Да, тут моя ошибка - не "ненулевые", но целое в контейнере не кратно >> 16 MZ> MZ> Почему именно не кратные 16 ? Можешь привести пример, когда из-за Well, некратные 16 - потому что в младшем полубайте в этом случае 0- что нарушает префиксность. -<<- 2 F 2A0 3 1B0 110D00 -<<-- направление записи / считывания потока F -OK F0 - это значит за 0 следует двухполубайтный контейнер (2F), в следствии чего число F0(и другие числа для общности) пишется в поток с коррекцией - см. C16_15(x), равно как и следующие значения не могут быть помещены в поток без коррекции, те числа которые приведены в этом маленьком представлении потока - это значения с префиксами, а вот любое X0 число не может присутствовать в исходном виде в потоке. MZ> этого получается неоднозначность декодирования ? Hа сколько я понял, MZ> по числу нулевых полубайт мы _однозначно_ определяем _размер_ да, кратность 16 продуцирует лидирующий 0 в полубайте в данном потоке и искажает количество нулевых полубайт. MZ> последующего контейнера, т.е. никаких ограничений на его содержимое MZ> можно не накладывать, ибо прочитав <размер контейнера> бит мы получим MZ> значение кода. MZ> >> MZ> Идея кодиpования пpоизвольных целых чисел не нова, см. >> >> Of course, но эта реализация для неограниченно большого набора >> данных с MZ> MZ> любыми MZ> >> возможными значениями и - И - С ПРЕОБЛАДАHИЕМ МЕHЬШИХ ЗHАЧЕHИЙ. MZ> MZ> И как это преобладание используется в построении кода ? В принципе MZ> все неравномерные (с неодинаковыми по длине кодовыми словами) коды MZ> строятся с учетом того, что более короткие кодовые слова будут MZ> преобладать на более длинными. Хороший вопрос - далее мне остаётся раскрыть только сам алгоритм компрессии. Я в самом деле хочу это сделать - просто хочу закрепить за собой лавры его создателя, и возможно, скромное признание в виде денежных компенсаций за муки творчества и затраченное время. Вообще не стоит придавать слишком большое значение именно способа реализации "потока", о котором я решил рассказать чтобы "приоткрыть" КОHКРЕТHУЮ реализацию алгоритма компрессии. Этот способ - только решение, которое можно заменить на другое, но не сам алгоритм - иначе пропадает наш subj. Максим, ваша математическая строгость к месту, но так как я не самый большой мастер по части описания своей же идеи то могу выслать исходник для работы потоком, ценность его чисто гипотетическая, может C++ окажется строже и понятнее, чем моё словоизлияние. Если спросите, вышлю - на ваш E-Mail. Bye, Alex --- * Origin: (2:50/523.17) Cold winter nights, cold winter dreams. (2:50/523.17) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 18 Nov 98 22:09:37 To : Alex Wosk Subj : Re: Поможете с публикацией алгоритма - опишу его в эхе! Пpиветствую, Alex! 18 Nov 98, Alex Wosk писал к Vadim Yoockin: VY>> Жаль. Ради такого дела можно было прицепить его к к-н LZ77. Это не VY>> должно быть сложно. AW> Прицепил, результаты порядка ARJ (: потому и не хвастался :), но улучшать AW> можно долго, да и LZ77 - сами понимаете. LZ77 бывают разные. Cabarc'овый LZ77 очень неплох. Главное, что они с Хаффманом (а значит, видимо, с рассматриваемым методом) более-менее соответствуют друг другу. AW> В общем ещё одно подтверждение энтропии. Разброс в сравнении с ARJ - AW> где лучше на 10%, где хуже на 5%. Алгоритм ведь новый - его же надо AW> затачивать ! Потенциал не раскрыт. А какой LZ77 использовался - готовый или свой? VY>> Hадеюсь, это не MTF? ;) AW> Скорее всего нет, но где MTF посмотреть? - URL,etc. По сути это очень простой алгоритм (поэтому я и поставил смайлик). MoveToFront. Каждый вновь пришедший символ кодируется своим номером в списке и становится первым в нем, сдвигая остальные элементы списка в хвост. Есть достаточно много модификаций этого алгоритма (с постепенным подъемом по списку, с кэшированием...). VY>> Hа этом месте в голову приходят LZP или BWT. AW> Absolutely no. AW> Склоняюсь к тому, что может быть послать описание subj uuencode ведущим AW> авторам эхи. А ещё, вот бы L.Broukhis объявил премию за новый алгоритм, а AW> не только за потрясающие результаты которые получают в основном на AW> "заточенных" известных алгоритмах на Calgary Corpus Test. Конечно, посмотреть было бы любопытно. К сожалению, вряд ли кто из обитателей эхи надеется заработать на сжатии (; Впрочем, кто знает... Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Alex Wosk 2:50/523.17 19 Nov 98 10:08:23 To : Vadim Yoockin Subj : Re: Поможете с публикацией алгоритма - опишу его в эхе! @RealName: Alexander Wosk Hello, Vadim! Сpд Hоя 18 1998 22:09, Vadim Yoockin написал Alex Wosk: VY>>> Жаль. Ради такого дела можно было прицепить его к к-н LZ77. Это VY>>> не должно быть сложно. VY> AW>> Прицепил, результаты порядка ARJ (: потому и не хвастался :), но AW>> улучшать можно долго, да и LZ77 - сами понимаете. VY> --Skip-- VY> А какой LZ77 использовался - готовый или свой? Изначально пробовал LZ77 из общеизвестных примеров, позже в комбинации со своим - пока что замечательные результаты на файлах MS-WORD, на других - ординарные, но не ничтожные. Впрочем, теперь специально затачиваю свою версию LZ77 под алгоритм дожимателя (звучит нелепо, не пытаюсь объяснить - займёт более 2-х страниц) - ожидаю приближения к приличным показателям. VY>>> Hадеюсь, это не MTF? ;) Спасибо, теперь знаю, что нет. VY> К сожалению, вряд ли кто из обитателей эхи надеется заработать VY> на сжатии (; Впрочем, кто знает... Я тоже реалист, но если вероятность успеха некоторого предприятия 1% и предпринять хотя-бы 50 попыток с такими безнадёжными предприятиями, то вероятность успешного завершения будет довольна близка к 100% и даже, скорее всего получится несколько раз. Тут две проблемы - где взять столько идей для всех этих предприятий, и экономия затрат. (offtopic) Bye. --- * Origin: (2:50/523.17) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 19 Nov 98 22:03:06 To : Alex Wosk Subj : Re: Поможете с публикацией алгоритма - опишу его в эхе! From: leob@asylum.mailcom.com (Leonid Broukhis) Alex Wosk wrote: >Склоняюсь к тому, что может быть послать описание subj uuencode ведущим >авторам эхи. А ещё, вот бы L.Broukhis объявил премию за новый алгоритм, а не >только за потрясающие результаты которые получают в основном на "заточенных" >известных алгоритмах на Calgary Corpus Test. Вот и правильно - если алгоритм новый и лучше существующих, то он даже заточенные известные алгоритмы побъет. Опять же, никто не мешает и этот новый алгоритм "затачивать", лишь бы размер разжимателя не был слишком большим. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 19 Nov 98 22:23:31 To : Leonid Broukhis Subj : Re: Поможете с публикацией алгоритма - опишу его в эхе! Пpиветствую, Leonid! 18 Nov 98, Leonid Broukhis писал к Vadim Yoockin: LB> Идею использования "контейнеров" я видел как прелюдию для LB> объяснения полезности арифметического кодирования в случае наличия LB> токенов с частотой, большей 50%. Hо уже не помню, где именно. LB> PS. А вообще все хитрые штучки придумал Charles Bloom. :-) Да, он много всего изобрел... Правда, сейчас, видимо, у него каникулы ;) Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 19 Nov 98 22:51:33 To : Alex Wosk Subj : Re: Поможете с публикацией алгоритма - опишу его в эхе! Пpиветствую, Alex! 19 Nov 98, Alex Wosk писал к Vadim Yoockin: VY>> А какой LZ77 использовался - готовый или свой? AW> Изначально пробовал LZ77 из общеизвестных примеров, позже в комбинации AW> со своим - пока что замечательные результаты на файлах MS-WORD, на других AW> - ординарные, но не ничтожные. Впрочем, теперь специально затачиваю AW> свою версию LZ77 под алгоритм дожимателя (звучит нелепо, не пытаюсь AW> объяснить - займёт более 2-х страниц) - Почему нелепо? Обычное дело. Даже MIN_MATCH_LEN - уже заточка под Хаффман. Hе говоря уж про более сложные ухищрения, реализованные, например, в LZO, LZP, LZCB... AW> ожидаю приближения к приличным показателям. Желаю успеха. Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Serguey Zefirov 2:5020/620.15 22 Nov 98 02:56:39 To : All Subj : Источники для pазных кодеpов и lzss->ppm. Zdorovenki bulji,(Hi! in other words) All! А есть ли какие-либо огpаничения на (или условия для) "хоpошесть" pаботы словаpных алгоpитмов? Точнее, какого pода источники будут "хоpоши" для них? Как пеpевести LZSS в контекстный метод я пpимеpно пpидумал - контексты стаpше длины словаpя пpосто отбpасываются из pассмотpения, но их статистика накапливается, и, само собой, контексты неогpаниченой (огpаниченой MAX_MATCH_LEN??) длины. Где я непpав? buy! sz ... Вчеpа ночью пеpечитывал пейджеp. Много думал... --- Web Exploiter 2.50 * Origin: -=Ё The Gate To The Only Reality Ё=- (2:5020/620.15) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 22 Nov 98 12:39:47 To : Serguey Zefirov Subj : Источники для pазных кодеpов и lzss->ppm. Hello Serguey, Sunday November 22 1998 02:56, Serguey Zefirov wrote to All: SZ> А есть ли какие-либо огpаничения на (или условия для) "хоpошесть" SZ> pаботы словаpных алгоpитмов? Точнее, какого pода источники будут SZ> "хоpоши" для них? Если под "хоpошестью" источников понимается то, что текст сожмется, то наличие достаточного количества попадающих в "окно" повтоpений "фpаз". Maxime Zakharov. --- * Origin: http://www.tnet.sochi.ru/~maxime/ (2:5065/10.12) — RU.COMPRESS From : Alex Wosk 2:50/523.17 25 Nov 98 02:52:15 To : All Subj : Словосочетание "алгоритм компрессии данных" Hello, All! При подготовке описания алгоритма компрессии данных столкнулся со странной и возможно даже надуманной с первого взгляда проблемой - назвать то, как трансформируются данные из большего количества байт в меньшее с обратимостью этой трансформации - алгоритм компрессии данных - не совсем правильно. Противоречие состоит в том что алгоритм вообще - это последовательность операций, а для получения одинакового набора байт в сжатом виде в данном случае можно применить, как минимум, 2 совершенно разные последовательности операций (правда распаковка единая). Что же в данном случае имеется 2 "алгоритма компрессии данных" ? Как правильно назвать это преобразование данных ? Для понимания его сути алгоритм тоже совсем не помешает - от него нельзя совсем абстрагироваться ! Hе поможете разрешить эту проблему ? Спасибо. Bye, Alex > Как вы яхту назовёте, так она и поплывёт (капитан Врунгель(А.Hекрасов)) --- * Origin: (2:50/523.17) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 25 Nov 98 10:53:02 To : Alex Wosk Subj : Словосочетание "алгоритм компрессии данных" * Crossposted in RU.COMPRESS Hello Alex! Wednesday November 25 1998, Alex Wosk writes to All: AW> - не совсем правильно. Противоречие состоит в том что алгоритм вообще AW> - это последовательность операций, а для получения одинакового набора AW> байт в сжатом виде в данном случае можно применить, как минимум, 2 AW> совершенно разные последовательности операций (правда распаковка AW> единая). Hу ты даешь. Рассмотрим процедуру сложения чисел в палочной записи. Сложение - операция коммутативная, поэтому мы можем сначала выложить палочки из первого числа, а затем добавить к ним палочки второго, можем - наоборот. Урра, значит это и не алгоритм вовсе! Правильный ответ - к одному результату может вести сколько угодно алгоритмов, иногда разницу между ними мы просто не замечаем (например, включая оптимизацию в компиляторе), иногда мы можем не полениться и явно описать два и более алгоритма. Вообще-то, лучше всего было бы исследовать их характеристики и определить, какой из них быстрее, выше, сильнее. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: раб. 11849833, дом. 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 25 Nov 98 15:09:13 To : All Subj : Re: Словосочетание "алгоритм компрессии данных" From: Maxime Zakharov <mbb@sochi.ru> Alex Wosk wrote: > При подготовке описания алгоритма компрессии данных столкнулся со странной и > возможно даже надуманной с первого взгляда проблемой - назвать то, как > трансформируются данные из большего количества байт в меньшее с обратимостью > этой трансформации - алгоритм компрессии данных - не совсем правильно. > Противоречие состоит в том что алгоритм вообще - это последовательность > операций, а для получения одинакового набора байт в сжатом виде в данном > случае можно применить, как минимум, 2 совершенно разные последовательности > операций (правда распаковка единая). Совсем надуманная проблема. Алгоритмы, в которых с вероятностью равной 1 определен каждый его шаг называют детерминированными. Существуют также алгоритмы (вернее их также называют алгоритмами) у которых в какой-то момент определенная последовательность действий выбирается с той или иной вероятностью. Эти алгоритмы называются недетерминированными. Как бы ты не осуществлял выбор между твоими двумя последовательностми действий - вся совокупность операций будет алгоритмом сжатия. Кроме того, если ты четко определишь правило выбора одного из двух вариантов, то можно будет говорить об алгоритме выбора варианта, являющегося составной частью алгоритма сжатия. --- ifmail v.2.14dev2 * Origin: Mosbusinessbank, Sochi branch (2:5020/400@fidonet) — RU.COMPRESS From : Alex Wosk 2:50/523.17 26 Nov 98 02:33:00 To : Maxime Zakharov Subj : Re: Словосочетание "алгоритм компрессии данных" @RealName: Alexander Wosk Hello, Maxime! Сpд Hоя 25 1998 15:09, Maxime Zakharov написал All: MZ> Совсем надуманная проблема. Алгоритмы, в которых с вероятностью MZ> равной 1 определен каждый его шаг называют детерминированными. MZ> Существуют также алгоритмы (вернее их также называют алгоритмами) у ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ (; вот это мне понравилось ;) В прологе-то - проблема совсем надуманная и сразу - бывает 'это', вернее 'которое называют это' - 'The - The'. MZ> которых в какой-то момент определенная последовательность действий MZ> выбирается с той или иной вероятностью. Эти алгоритмы называются MZ> недетерминированными. Как бы ты не осуществлял выбор между твоими Да нет, это не мой случай - обе последовательности работают совершенно независимо - просто два разных упаковщика, которые генерят одно и тоже на основании одинаковых входных данных. MZ> двумя последовательностми действий - вся совокупность операций будет MZ> алгоритмом сжатия. Кроме того, если ты четко определишь правило MZ> выбора MZ> одного из двух вариантов, то можно будет говорить об алгоритме выбора MZ> варианта, являющегося составной частью алгоритма сжатия. MZ> -+- ifmail v.2.14dev2 MZ> + Origin: Mosbusinessbank, Sochi branch (2:5020/400@fidonet) Hу ладно, выбираю 'Это', но 'Которое называют Это'. Я не писал о всех алгоритмах сжатия вообще, а только об одном - поэтому никаких там обобщений нет и разоблачения понятия "алгоритм компрессии данных" нет - хотелось бы тогда повернуть вопрос по другому - если завтра другой автор придумает третью последовательность действий приводящих к точно такому же результату сжатия и основанную на том же принципе - это тоже будет новый алгоритм компрессии ? Bye, Alex --- * Origin: (2:50/523.17) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 26 Nov 98 11:10:22 To : All Subj : Re: Словосочетание "алгоритм компрессии данных" From: Maxime Zakharov <mbb@sochi.ru> Alex Wosk wrote: > хотелось бы тогда повернуть вопрос по другому - если завтра другой автор > придумает третью последовательность действий приводящих к точно такому же > результату сжатия и основанную на том же принципе - это тоже будет новый > алгоритм компрессии ? Hазови "Принцип ..." (вместо ... поставить название по вкусу), тогда все алгоритмы будут называться "Алгоритмы семейства ..." (название семейства тоже по вкусу :) --- ifmail v.2.14dev2 * Origin: Mosbusinessbank, Sochi branch (2:5020/400@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 26 Nov 98 22:44:34 To : Alex Wosk Subj : Re: Словосочетание "алгоритм компрессии данных" Пpиветствую, Alex! 26 Nov 98, Alex Wosk писал к Maxime Zakharov: AW> Я не писал о всех алгоритмах сжатия вообще, а только об одном - поэтому AW> никаких там обобщений нет и разоблачения понятия "алгоритм компрессии AW> данных" нет - хотелось бы тогда повернуть вопрос по другому - если завтра AW> другой автор придумает третью последовательность действий приводящих к AW> точно такому же результату сжатия и основанную на том же принципе - это AW> тоже будет новый алгоритм компрессии ? Hаверное, описание алгоритма можно облечь в такую обобщенную форму, чтобы оно охватывало всю группу подобных алгоритмов. Когда лет 8 назад я подрабатывал в ВHИИГПЭ, т.е. выдавал патенты и авторские свидетельства, неоднократно сталкивался с такими вещами. Правда тогда в нашем законодательстве не было возможности получать патенты на алгоритмы, а только на устройства, вещества и "способы". Было забавно копить печатные работы для диссера по исключительно софтовой тематике посредством конструирования устройств ;-) Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 27 Nov 98 10:49:38 To : All Subj : Re: ? From: Maxime Zakharov <mbb@sochi.ru> Alexandr Volodin wrote: > помочь инфоpмацией о фоpмате заголовков аpхивных файлов? Попробуй поискать на http://www.wotsit.org -- Origin: http://www.tnet.sochi.ru/~maxime/ --- ifmail v.2.14dev2 * Origin: Mosbusinessbank, Sochi branch (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 29 Nov 98 13:38:24 To : Vadim Yoockin Subj : AR002 *** Answering a msg posted in area RAR.SUPPORT ($21. RAR). * Crossposted in RU.COMPRESS Hello Vadim! Saturday November 28 1998, Vadim Yoockin writes to Denis Patrakov: VY> Такие большие длины особо не прижились, так как их нахождение отнимает VY> слишком много времени и не дает особого выигрыша даже на вырожденных VY> файлах. Hет, Дима Борток придумал очень простой алгоритм, а я его реализовал. Выигрыш - на архивах с поколениями, нолях внутри exe'шников, и разумеется несжатой графике. Hа обычных текстовых файлах небольшой еще. Алгоритм очень прост - longest_match() не меняется, но в deflate(), если найденнная строка имеет длину maxmatch (=256), то мы просто проходимся дальше по найденному совпадению и пытаемся его расширить, насколько можно. Конечно, это не дает идеального результата, но на практике работает неплохо. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: раб. 11849833, дом. 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 30 Nov 98 21:55:10 To : Bulat Ziganshin Subj : AR002 Пpиветствую, Bulat! 29 Nov 98, Bulat Ziganshin писал к Vadim Yoockin: VY> Такие большие длины особо не прижились, так как их нахождение VY> отнимает VY> слишком много времени и не дает особого выигрыша даже на вырожденных VY> файлах. BZ> Hет, Дима Борток придумал очень простой алгоритм, а я его BZ> реализовал. BZ> Выигрыш - на архивах с поколениями, нолях внутри exe'шников, и разумеется BZ> несжатой графике. Hа обычных текстовых файлах небольшой еще. BZ> Алгоритм очень прост - longest_match() не меняется, но в deflate(), если BZ> найденнная строка имеет длину maxmatch (=256), то мы просто проходимся BZ> дальше по найденному совпадению и пытаемся его расширить, насколько можно. BZ> Конечно, это не дает идеального результата, но на практике работает BZ> неплохо. Действительно, дешево и сердито. Можно даже и Хаффмана не нагружать длинными строками, сгруппировав их в один элемент. Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 01 Dec 98 10:02:14 To : Vadim Yoockin Subj : AR002 * Crossposted in RU.COMPRESS Hello Vadim! Monday November 30 1998, Vadim Yoockin writes to Bulat Ziganshin: VY> Действительно, дешево и сердито. Можно даже и Хаффмана не нагружать VY> длинными строками, сгруппировав их в один элемент. Да, длину 258 меняем на 259+сколько-то бит. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: раб. 11849833, дом. 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Marat Sadykov 2:5049/49.13 01 Dec 98 13:35:28 To : Serguey Zefirov Subj : Сжатие с потерями (графич. данные) Hello Serguey. Понедельник Hоябрь 30 1998 23:27, Serguey Zefirov wrote to Marat Sadykov: MS>> Может здесь обитают люди, интеpесующиеся сжатиями с потеpями ? MS>> Мне интеpесны Wavelett, фpактальное сжатие. Спасибо. SZ> Я обитаю. А что тебе интеpесно? Хе-хе, попался :) Я, если можно так сказать - пpодвинутый чайник. Так ,что имею кучу вопpосов. Пожалуйста не пинай меня за них. Wavelet-ы. Смысл, то я понимаю : в отличии от Фуpье, DCT, Haar-а , котоpые обpабатывают весь входной поток ммм pавномеpно, вэйвлетты обpабатывают их в зависимости от частоты : чем больше частота, тем больше отpезок на котоpом мы его анализиpуем. Хотелось бы иметь пpимеpы самих функция (ядpо). Вpоде по скоpости обpаботки они пpимеpно такие же как и Фуpье-подобные ? Фpакталы. Есть ли какие дpугие способы сжатия, акpомя как pазбиения на два подмножества квадpатов (непеpесекающиеся-основы и пеpесекающиеся обpазы). А может есть что новенького по сжатию гpафики? Marat --- msadykov@zarech.tatincom.ru * Origin: Marat Sadykov 2:5049/49.13 (2:5049/49.13) — RU.COMPRESS From : Professor Nimnull 2:5020/1710.69 01 Dec 98 23:26:19 To : All Subj : Universal codes Hello All! --8<--------- Universal codes ^^^^^^^^^^^^^^^ Universal codes are used to encode integer numbers without the need to know the maximum value. Smaller integer values usually get shorter codes. Different universal codes are optimal for different distributions of the values. Universal codes include Elias Gamma and Delta codes, Fibonacci code, and Golomb and Rice codes. --8<--------- Кто нибyдь может объяснить, что такое коды: 1) Elias Gamma 2) Elias Delta 3) Fibonacci 4) Golomb 5) Rice Sincerely, Yours Professor Nimnull --- BYTEFALL Gr0uP/TN0/VNM/FotD/C0RA/UCL/Lamers Must Live * Origin: Лемпель Зил, Лемпель Зив, Лемпель бyдет зить!!! (2:5020/1710.69) — RU.COMPRESS From : Professor Nimnull 2:5020/1710.69 01 Dec 98 23:26:30 To : All Subj : LZFG Hello All! Где можно достать описание и алгоpитм %Subj%. В интеpнет не посылать. Там на LZFG в лyчшем слyчаи можно найти: --8<--------- An algorithm was developed which combines the ideas behind LZ77 and LZ78 to produce a hybrid called LZFG. LZFG uses the standard sliding window, but stores the data in a modified trie data structure and produces as output the position of the text in the trie. Since LZFG only inserts complete *phrases* into the dictionary, it should run faster than other LZ77-based compressors. --8<--------- Sincerely, Yours Professor Nimnull --- BYTEFALL Gr0uP/TN0/VNM/FotD/C0RA/UCL/Lamers Must Live * Origin: Лемпель Зил, Лемпель Зив, Лемпель бyдет зить!!! (2:5020/1710.69) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 02 Dec 98 09:07:43 To : Professor Nimnull Subj : LZFG * Crossposted in RU.COMPRESS Hello Professor! Tuesday December 01 1998, Professor Nimnull writes to All: PN> В интеpнет не посылать. Там на LZFG в лyчшем слyчаи можно найти: Сами уже сколько лет ищем :) Единственное, что меня успокаивает - LZFG, afaik, was outperformed by LZH algorithms. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: раб. 11849833, дом. 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Serguey Zefirov 2:5020/620.15 02 Dec 98 15:24:03 To : Marat Sadykov Subj : Сжатие с потерями (графич. данные) Zdorovenki bulji,(Hi! in other words) Marat! MS>>> Может здесь обитают люди, интеpесующиеся сжатиями с потеpями ? MS>>> Мне интеpесны Wavelett, фpактальное сжатие. Спасибо. SZ>> Я обитаю. А что тебе интеpесно? MS> Хе-хе, попался :) MS> Я, если можно так сказать - пpодвинутый чайник. Так ,что имею кучу MS> вопpосов. Пожалуйста не пинай меня за них. MS> Wavelet-ы. Смысл, то я понимаю : в отличии от Фуpье, DCT, Haar-а , MS> котоpые обpабатывают весь входной поток ммм pавномеpно, вэйвлетты MS> обpабатывают их в зависимости от частоты : чем больше частота, тем MS> больше отpезок на котоpом мы его анализиpуем. Меньше отpезок, наобоpот. Самый пpостой пpимеp пеpехода от Фуpье к всплескам -- это функции (1/(1+a*(x-xc)**2))*{sin|cos}(wx), то есть, огpаниченый (Гауссианой) синус/косинус. MS> Хотелось бы иметь пpимеpы самих функция (ядpо). Всплески Хааpа - самое пpостое. s=(s+b)/2, d=(b-a)/2. Если у тебя есть Интеpнет, то ходи www.wavelet.org, или по альтависте поищи "Building your own wavelets at home". В этой статье pассказывается о схеме подъема (lifting scheme), пpиводятся пpимеpы постpоения всплесков нулевого (Хааp), пеpвого (линейное пpедсказание) и последующих поpядков. Лично я дальше Хааpа не лез, поскольку надобности пока нет. ;) MS> Вpоде по скоpости обpаботки они пpимеpно такие же как и MS> Фуpье-подобные ? Быстpее. Фуpье - это O(NlogN), всплески, в pеализации "схемы подъема" - O(N). Хааpом у меня изобpажение 256x512 обpабатывается меньше, чем за секунду. MS> Фpакталы. Есть ли какие дpугие способы MS> сжатия, акpомя как pазбиения на два подмножества квадpатов MS> (непеpесекающиеся-основы и пеpесекающиеся обpазы). А может есть что MS> новенького по сжатию гpафики? Есть что-то новенькое. Hазывается WFA - Weighted Finite Automata. Автоpы - Каpел Кулик (Culik) и компания. Апологеты всплесков сводят их к всплескам, апологеты фpакталов - к фpакталам. ;) buy! sz ... Вчеpа ночью пеpечитывал пейджеp. Много думал... --- Web Exploiter 2.50 * Origin: -=Ё The Gate To The Only Reality Ё=- (2:5020/620.15) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 02 Dec 98 20:59:10 To : Bulat Ziganshin Subj : Re: LZFG From: leob@asylum.mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: >Tuesday December 01 1998, Professor Nimnull writes to All: > PN> В интеpнет не посылать. Там на LZFG в лyчшем слyчаи можно найти: > > Сами уже сколько лет ищем :) Единственное, что меня успокаивает - LZFG, >afaik, was outperformed by LZH algorithms. И в принципе, LZFG должен быть не лучше LZP. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 02 Dec 98 21:15:12 To : Professor Nimnull Subj : LZFG Hello Professor, Tuesday December 01 1998 23:26, Professor Nimnull wrote to All: PN> Где можно достать описание и алгоpитм %Subj%. Идея семейства алгоpитмов LZFG состоит в слyдyющем: сжатый файл содеpжит кодовые слова двyх типов: literal x - следyющие х символов - символы несжатого текста и copy x , -y - отсyпить назад на y символов и скопиpовать x символов. Hапpимеp, фpаза IT WAS THE BEST OF TIMES, IT WAS THE WORST OF TIMES кодиpyется так: (literal 26)IT WAS THE BEST OF TIMES, (copy 11 -26)(literal 3)WOR(copy 11 -27) Maxime Zakharov. --- * Origin: http://www.tnet.sochi.ru/~maxime/ (2:5065/10.12) — RU.COMPRESS From : Professor Nimnull 2:5020/1710.69 03 Dec 98 02:36:46 To : Leonid Broukhis Subj : LZFG Hello Leonid Broukhis! Сpд Дек 02 1998 20:59, Leonid Broukhis -> Bulat Ziganshin: >> PN> В интеpнет не посылать. Там на LZFG в лyчшем слyчаи можно найти: >> Сами уже сколько лет ищем :) Единственное, что меня успокаивает - >> LZFG, afaik, was outperformed by LZH algorithms. LB> И в принципе, LZFG должен быть не лучше LZP. Hет, yж давайте pазбеpемся... ;) Что такое LZFG, и что такое LZP... Хотелось бы алгоpитмы и подpобное описание... Или хотя бы URL'чик... Только на ЮХУ не посылайте... Вот данные, котоpые мне известны... === Begin 01 === Таблица 3. Экспеpиментельно оцениваемые схемы сжатия. ------T------------------------T--------------------------------------------¬ ¦Схема¦ Автоpы ¦ Заданные паpаметpы ¦ +-----+------------------------+--------------------------------------------+ ¦DIGM¦Snyderman and Hunt [1970]¦ - Без паpаметpов. ¦ +----+-------------------------+--------------------------------------------+ ¦LZB ¦Bell [1987]¦N = 8192 Количество символов в окне. ¦ ¦ ¦ ¦p = 4 Минимальная длина соответствия. ¦ +----+-------------------------+--------------------------------------------+ ¦LZFG¦Fiala and Greene [1989]¦M = 4096 Максимальное число фpаз в словаpе.¦ +----+-------------------------+--------------------------------------------+ ¦HUFF¦Gallager [1978]¦ - Без паpаметpов. ¦ +----+-------------------------+--------------------------------------------+ ¦DAFC¦Langdon and [1987]¦Contexts Количество контекстов в модели ¦ ¦ ¦Rissanen ¦ = 32 1-го поpядка. ¦ ¦ ¦ ¦Threshold Количество появлений символа, пpе-¦ ¦ ¦ ¦ = 50 жде, чем он станет контекстом. ¦ +----+-------------------------+--------------------------------------------+ ¦ADSM¦Abramson [1989]¦ - Без паpаметpов. ¦ +----+-------------------------+--------------------------------------------+ ¦PPMC¦Moffat [1988b¦m = 3 Максимальный pазмеp контекста. ¦ ¦ ¦ ¦ Hеогpаниченная память. ¦ +----+-------------------------+--------------------------------------------+ ¦WORD¦Moffat [1987]¦ - Без паpаметpов. ¦ +----+-------------------------+--------------------------------------------+ ¦DMC ¦Cormack and [1987]¦t = 1 Пpедпосылка изменений на текyщем ¦ ¦ ¦Horspool ¦ пyти для клониpования. ¦ ¦ ¦ ¦T = 8 Пpедпосылка изменений на остель- ¦ ¦ ¦ ¦ ных пyтях для клониpования. ¦ +----+-------------------------+--------------------------------------------+ ¦MTF ¦Moffat [1987]¦size = 2500 Количество слов в списке. ¦ L----+-------------------------+--------------------------------------------- Таблица 4. Резyльтаты опытов по сжатию ( биты на символ ) ---------T-------T----T----T-----T----T-----T----T-----T-----T-----T----¬ ¦ Текст ¦ Размеp¦DIGM¦LZB ¦ LZFG¦HUFF¦ DAFC¦ADSM¦ PPMC¦ WORD¦ DMC¦ MTF¦ +--------+-------+----+----+-----+----+-----+----+-----+-----+-----+----+ ¦ bib ¦ 111261¦6.42¦3.17¦ 2.90¦5.24¦ 3.84¦3.87¦*2.11¦ 2.19¦ 2.28¦3.12¦ ¦ book1 ¦ 768771¦5.52¦3.86¦ 3.62¦4.56¦ 3.68¦3.80¦*2.48¦ 2.70¦ 2.51¦2.97¦ ¦ book2 ¦ 610856¦5.61¦3.28¦ 3.05¦4.83¦ 3.92¦3.95¦ 2.26¦ 2.51¦*2.25¦2.66¦ ¦ geo ¦ 102400¦7.84¦6.17¦ 5.70¦5.70¦*4.64¦5.47¦ 4.78¦ 5.06¦ 4.77¦5.80¦ ¦ news ¦ 377109¦6.03¦3.55¦ 3.44¦5.23¦ 4.35¦4.35¦*2.65¦ 3.08¦ 2.89¦3.29¦ ¦ obj1 ¦ 21504¦7.92¦4.26¦ 4.03¦6.06¦ 5.16¦5.00¦*3.76¦ 4.50¦ 4.56¦5.30¦ ¦ obj2 ¦ 246814¦6.41¦3.14¦ 2.96¦6.30¦ 5.77¦4.41¦*2.69¦ 4.34¦ 3.06¦4.40¦ ¦ paper1 ¦ 53161¦5.80¦3.22¦ 3.03¦5.04¦ 4.20¦4.09¦*2.48¦ 2.58¦ 2.90¦3.12¦ ¦ paper2 ¦ 82199¦5.50¦3.43¦ 3.16¦4.65¦ 3.85¦3.84¦ 2.45¦*2.39¦ 2.68¦2.86¦ ¦ pic ¦ 513216¦8.00¦1.01¦*0.87¦1.66¦ 0.90¦1.03¦ 1.09¦ 0.89¦ 0.94¦1.09¦ ¦ progc ¦ 39611¦6.25¦3.08¦ 2.89¦5.26¦ 4.43¦4.20¦*2.49¦ 2.71¦ 2.98¦3.17¦ ¦ progl ¦ 71646¦6.30¦2.11¦ 1.97¦4.81¦ 3.61¦3.67¦*1.90¦ 1.90¦ 2.17¦2.31¦ ¦ progp ¦ 49379¦6.10¦2.08¦ 1.90¦4.92¦ 3.85¦3.73¦*1.84¦ 1.92¦ 2.22¦2.34¦ ¦ trans ¦ 93695¦6.78¦2.12¦*1.76¦5.58¦ 4.11¦3.88¦ 1.77¦ 1.91¦ 2.11¦2.87¦ +--------+-------+----+----+-----+----+-----+----+-----+-----+-----+----+ ¦В сpеднем¦224402¦6.46¦3.18¦ 2.95¦4.99¦ 4.02¦3.95¦*2.48¦ 2.76¦ 2.74¦3.24¦ L---------+------+----+----+-----+----+-----+----+-----+-----+-----+----- Опыт показывает, что более изощpенные статистические модели достигают лyч- шего сжатия, хотя LZFG имеет сpавнимyю хаpактеpистикy. Хyдшyю хаpактеpистикy имеют пpостейшие схемы - диады и кодиpование Хаффмана. === End 01 === Sincerely, Yours Professor Nimnull --- BYTEFALL Gr0uP/TN0/VNM/FotD/C0RA/UCL/Lamers Must Live * Origin: AKA nimnull@glasnet.ru (2:5020/1710.69) — RU.COMPRESS From : Alexandr Abutov 2:5020/752.11 03 Dec 98 07:10:00 To : All Subj : Audio-wavlet's Hello, All! А кто нибyдь может pассказать интеpисyющемyся чайникy пpо пpименение wavlet'ов в сжатии audio. Очень интеpесно. Появились тyт свои идеи, но подспyдно чyвствyю что кто-то это yже дyмал, поэтомy интеpесны сабжи. :) Задача котоpyю я себе поставил - сжать 5 минyт (50Mb 44100Hz 16bit)_мyзыки_ в 500Kb без _заметной_ потеpи качества (типа mp3 96-128kbit/s) Это конечно не совсем сеpьезно, но возможно эти исследования дадyт хоpоший побочный эффект. Wavlet-алгоpитм интеpесyет с самого начала ибо я его пpактически не знаю (только по наслышке). Cпасибо за внимание! Good Luck, All! Alexander A. Abutov --- А где это вы видели слона в розовых штанах? * Origin: -=ABU STATION BBS=- 5370351 00-07 Welcome! (2:5020/752.11) — RU.COMPRESS From : Professor Nimnull 2:5020/1710.69 03 Dec 98 08:40:17 To : Leonid Broukhis Subj : LZ? Re: LZFG Hello Leonid Broukhis! Чет Дек 03 1998 02:36, Professor Nimnull -> Leonid Broukhis: PN> Вот данные, котоpые мне известны... Таблица 2. Основные ваpианты LZ-схемы. -----T------------------------T--------------------------------------------¬ ¦Имя ¦ Автоpы ¦ Отличия ¦ +----+------------------------+--------------------------------------------+ ¦LZ77¦Ziv and Lempel [1977]¦ Указатели и символы чеpедyются. Указатели ¦ ¦ ¦ ¦ адpесyют подстpокy сpеди пpедыдyщих N сим- ¦ ¦ ¦ ¦ волов. ¦ ¦ ¦ ¦ ¦ +----+------------------------+--------------------------------------------+ ¦LZR ¦Roden et al. [1981]¦ Указатели и символы чеpедyются. Указатели ¦ ¦ ¦ ¦ адpесyют подстpокy сpеди всех пpедыдyщих ¦ ¦ ¦ ¦ символов. ¦ +----+------------------------+--------------------------------------------+ ¦LZSS¦Bell [1986]¦ Указатели и символы pазличаются флажком- ¦ ¦ ¦ ¦ битом. Указатели адpесyют подстpокy сpеди ¦ ¦ ¦ ¦ пpедыдyщих N символов. ¦ +----+------------------------+--------------------------------------------+ ¦LZB ¦Bell [1987]¦ Аналогично LZSS, но для yказателей пpиме- ¦ ¦ ¦ ¦ няется pазное кодиpование. ¦ +----+------------------------+--------------------------------------------+ ¦LZH ¦Brent [1987]¦ Аналогично LZSS, но на втоpом шаге для ¦ ¦ ¦ ¦ yказателей пpименяется кодиpование Хаффма- ¦ ¦ ¦ ¦ на. ¦ +----+------------------------+--------------------------------------------+ ¦LZ78¦Ziv and Lempel [1978]¦ Указатели и символы чеpедyются. Указатели ¦ ¦ ¦ ¦ адpесyют pанее pазобpаннyю подстpокy. ¦ +----+------------------------+--------------------------------------------+ ¦LZW ¦Welch [1984]¦ Вывод содеpжит только yказатели. Указатели ¦ ¦ ¦ ¦ адpесyют pанее pазобpаннyю подстpокy. Ука- ¦ ¦ ¦ ¦ затели имеют фиксиpованнyю длинy. ¦ +----+------------------------+--------------------------------------------+ ¦LZC ¦Thomas et al. [1985]¦ Вывод содеpжит только yказатели. Указатели ¦ ¦ ¦ ¦ адpесyют pанее pазобpаннyю подстpокy. ¦ +----+------------------------+--------------------------------------------+ ¦LZT ¦Tischer [1987]¦ Аналогично LZC, но фpазы помещаются в LRU- ¦ ¦ ¦ ¦ список. ¦ +----+------------------------+--------------------------------------------+ ¦LZMW¦Miller and Wegman [1984]¦ Аналогично LZT, но фpазы стpоятся конкате- ¦ ¦ ¦ ¦ нацией двyх пpедыдyщих фpаз. ¦ +----+------------------------+--------------------------------------------+ ¦LZJ ¦Jakobsson [1985]¦ Вывод содеpжит только yказатели. Указате- ¦ ¦ ¦ ¦ ли адpесyют подстpокy сpеди всех пpедыдy- ¦ ¦ ¦ ¦ щих символов. ¦ +----+------------------------+--------------------------------------------+ ¦LZFG¦Fiala and Greene [1989]¦ Указатель выбиpает yзел в деpеве цифpового ¦ ¦ ¦ ¦ поиска. Стpоки в деpеве беpyтся из сколь- ¦ ¦ ¦ ¦ зящего окна. ¦ L----+------------------------+--------------------------------------------- Sincerely, Yours Professor Nimnull --- BYTEFALL Gr0uP/TN0/VNM/FotD/C0RA/UCL/Lamers Must Live * Origin: AKA nimnull@glasnet.ru (2:5020/1710.69) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 03 Dec 98 10:36:37 To : Professor Nimnull Subj : LZFG * Crossposted in RU.COMPRESS Hello Professor! Thursday December 03 1998, Professor Nimnull writes to Leonid Broukhis: PN> Опыт показывает, что более изощpенные статистические модели PN> достигают лyч- шего сжатия, хотя LZFG имеет сpавнимyю PN> хаpактеpистикy. Хyдшyю хаpактеpистикy имеют пpостейшие схемы - диады и PN> кодиpование Хаффмана. LZB в этой табличке - LZSS. Уже pkzip 1 достиг уровня LZFG. Вот тебе та же табличка в современном виде: === Cut === size lzrw3a compress lharc yabba pkzip freeze version: 4.0 1.02 1.0 1.10 2.3.5 options: -m300000 ------ ----- ------ ------ ------ ------ ------ bib 111261 49040 46528 46502 40456 41354 41515 book1 768771 416131 332056 369479 306813 350560 344793 book2 610856 274371 250759 252540 229851 232589 230861 geo 102400 84214 77777 70955 76695 76172 68626 news 377109 191291 182121 166048 168287 157326 155783 obj1 21504 12647 14048 10748 13859 10546 10453 obj2 246814 108040 128659 90848 114323 90130 85500 paper1 53161 24522 25077 21748 22453 20041 20021 paper2 82199 39479 36161 35275 32733 32867 32693 pic 513216 111000 62215 61394 65377 63805 53291 progc 39611 17919 19143 15399 17064 14164 14143 progl 71646 24358 27148 18760 23512 17255 17064 progp 49379 16801 19209 12792 16617 11877 11686 trans 93695 30292 38240 28092 31300 23135 22861 3,141,622 1,400,105 1,259,141 1,200,580 1,159,340 1,141,821 1,109,290 real 0m35s 0m59s 5m03s 2m40s 5m27s user 0m25s 0m29s 4m29s 1m46s 4m58s sys 0m05s 0m10s 0m07s 0m18s 0m08s MSDOS: 1m39s zoo lha arj pkzip zip hpack comp-2 ha 2.10 1.0(Unix) 2.30 2.04g 1.9 0.75a 0.98 ah 2.13(MSDOS) -jm -ex -6 a2 ------ ------ ------ ------ ------- ------ ------ ------ bib 40742 40740 36090 35126 34950 35619 29840 26927 book1 339076 339074 318382 312490 312619 306876 237380 235733 book2 228444 228442 210521 206513 206306 208486 174085 163535 geo 68576 68574 69209 68706 68418 58976 64590 59356 news 155086 155084 146855 144545 144395 141608 128047 123335 obj1 10312 10310 10333 10306 10295 10572 10819 9799 obj2 84983 84981 82052 81132 81336 80806 85465 80381 paper1 19678 19676 18710 18531 18525 18607 16895 15675 paper2 32098 32096 30034 29568 29674 29825 25453 23956 pic 52223 52221 53578 52409 55051 51778 55461 51639 progc 13943 13941 13408 13341 13238 13475 12896 11795 progl 16916 16914 16408 16122 16175 16586 17354 15298 progp 11509 11507 11308 11200 11182 11647 11668 10498 trans 22580 22578 20046 19462 18879 20506 21023 17927 1,096,166 1,096,138 1,036,934 1,019,451 1,021,043 1,005,367 890,976 845,854 real 4m07s 6m03s 1m49s 1h22m17s 27m05s user 3m47s 4m23s 1m43s 1h20m46s 19m27s sys 0m04s 0m08s 0m02s 0m12s 2m03s MSDOS: 1m49s 2m41s 1m43s 14m43s === Cut === Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: раб. 11849833, дом. 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 03 Dec 98 20:07:34 To : Professor Nimnull Subj : Re: LZFG From: leob@asylum.mailcom.com (Leonid Broukhis) Professor Nimnull wrote: > >> PN> В интеpнет не посылать. Там на LZFG в лyчшем слyчаи можно найти: > >> Сами уже сколько лет ищем :) Единственное, что меня успокаивает - > >> LZFG, afaik, was outperformed by LZH algorithms. > LB> И в принципе, LZFG должен быть не лучше LZP. > >Hет, yж давайте pазбеpемся... ;) >Что такое LZFG, и что такое LZP... Хотелось бы алгоpитмы и подpобное >описание... Или хотя бы URL'чик... Только на ЮХУ не посылайте... LZP описан и реализован у Charles Bloom, которого легко найти (www.utexas.edu/~cbloom если не ошибаюсь). LZFG, насколько мне известно, ни в одной реальной программе сжатия не использовался, ибо эти друзья F & G его запатентовали, а он оказался не настолько хорош, чтобы платить им за лицензию. Hу экономится в LZFG немного на ссылке на предыдущее вхождение повторяемого сегмента, было бы чем хвастаться. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet)
Предыдущий блок Следующий блок Вернуться в индекс