[an error occurred while processing this directive][an error occurred while processing this directive][an error occurred while processing this directive]
— 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)
[an error occurred while processing this directive][an error occurred while processing this directive]