Предыдущий блок Следующий блок Вернуться в индекс
 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)
 Предыдущий блок Следующий блок Вернуться в индекс