Предыдущий блок Следующий блок Вернуться в индекс
 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/28.126  11 Jul 00 17:29:45
 To   : Denis Smirnov                       
 Subj : Сжатие писем                                                                 



*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).

* Originally in RU.COMPRESS
Hello Denis!

Tuesday July 11 2000, Denis Smirnov writes to Bulat Ziganshin:
 DS>>>     Как примерно это можно реализовать? Ты имеешь в виду словарь
 DS>>> последовательностей часто повторяющихся в письмах?
 BZ>> да. реализовать с помощью дерева, типа того, как в lzw. потом
 BZ>> сделать второй проход и посчитать, каких слов много
 DS>     Я не очень знаком с материалом - можно url на хорошую доку по
 DS> lzw?

народ, кто-нибудь подскажите ссылки на страницы захарова и compression pointers
. есть также описание во второй части фака:

=== Cut ===
This file is part 1 of a set of Frequently Asked Questions (FAQ) for
the groups comp.compression and comp.compression.research.  If you
can't find part 2 or 3, see item 53 below. A copy of this FAQ is available
by ftp in ftp://rtfm.mit.edu/pub/usenet/news.answers/compression-faq/
files part1 to part3. This FAQ is also accessible in the World Wide Web at
http://www.faqs.org/faqs/compression-faq/part1/preamble.html or
http://www.cis.ohio-state.edu/hypertext/faq/usenet/compression-faq/top.html
=== Cut ===

но если ты хочешь сделать побыстрее, то я тебе не советую этим заниматься. это 
всего несколько процентов и при этом неотработанная еще технология. если уж ее 
использовать, то проще взять преобразования одного поляка (народ, как его зовут
?)
- они дают выигрыш в те же несколько процентов и исключительно просты в реализа
ции

 DS>     Думаю просто пакетами писем по 16.

ок

 BZ>> 2) расширить его словарь - работы на пару недель. все современные
 BZ>> lzh'и так, похоже, и сделаны
 DS>     Ты имеешь в виду работу со словарем большого объема?

да

 DS>     У меня идея такова - статистика контекстов во всех письмах на
 DS> русском языке примерно одинакова -> мы можем просто взять большую
 DS> мессагобазу и сделать таблицу контекстов. Потом кбить среди из них те,
 DS> от использования которых мы получаем
 DS> меньше всего выгоды. Файлик данных оставить можно не больше чем на мег
 DS> (при условии мессагобаз по несколько сот мегабайт это себя вполне
 DS> оправдает). Единственное что - не знаю как совместить уже готовую
 DS> статистику с набираемой по мессаге.

если хочется дешево и сердито, то просто сжимай в ppmd по 16 мессаг. и попробуй
 разобраться, как в нем организовать сохранение/чтение статистики - тогда ты см
ожешь еще улучшить сжатие. впрочем, не факт, что намного - проверь.

возможно, все же лучше взять bzip2. на текстах сжатие у него ненамного хуже, дл
я юниксов это уже почти стандарт, распаковка у него быстрее и памяти кушает мен
ьше

Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722

... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир
--- GoldED+/W32 1.1.2
 * Origin: В России борьба за власть начинается после выборов (2:5093/28.126)


 RU.COMPRESS 
 From : Vladimir Vassilevsky                 2:5020/400     11 Jul 00 22:20:51
 To   : All                                 
 Subj : Re: Упаковка сигнала в   real-time                                           


From: Vladimir Vassilevsky <vlv@fullnet.net>

Dima Petukhov wrote:
> 
> Я смотpю тут тpаффик небольшой, поэтому pискну задать свой вопpосик.
> Какой метод упаковки можете посоветовать (лучше сpазу с описанием) для упаков
ки
> сигнала, получаемого с осцилогpафа (скоpость на поpядок-два выше веpхней
> частоты сигнала) пpи следующих огpаничениях (для pеализации в аппаpатуpе):

"Идеальное" решение:

Первая ступень сжатия: ЛПК-предсказатель невысокого порядка (IMHO, 2..3
будет достаточно). Причем сами коэффициенты ЛПК можно вычислять по
предыдущим значениям сигнала, а не передавать в канале. Вторая ступень
сжатия - Хаффман с фиксированным деревом, рассчитанным на Гауссовскую
статистику. 

> 1. Hи пpи каких условиях pазмеp не должен увеличиваться!

Следовательно, алгоритм должен автоматически "выключаться", если не
может пожать данные.

> 2. Кол-во пеpеменных/счетчиков поpядка 3-5. Pазpядность до 16.

Мало :(

> 3. Сжатие обязано быть без потеpь.
> 4. Hикакие опеpации кpоме сложения/вычитания/сpавнения, логических и сдвигов
> недопустимы.
> 5. Упаковщик не должен затыкаться пpи _любых_ входных сигналах - пусть даже и
> упаковка исчезнет.
 
> Пока в уме деpжу только RLE для отсчетов и RLE для pазностей последовательных
> отсчетов. Может чего дpугое посоветуете?

Реальный сигнал обычно имеет слабый шумок на уровне младших значащих
разрядов, что делает применение RLE бесполезным. Осмелюсь посоветовать
брать разности отсчетов и пожимать их по фиксированному раз и навсегда
заданному Хаффмановскому дереву (или хотя бы каким-нибудь простейшим
префиксным кодом с неравномерной длиной).

VLV
--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)


 RU.COMPRESS 
 From : Vladimir Korablin                    2:5025/3.86    11 Jul 00 22:40:50
 To   : All                                 
 Subj : упаковка EXE                                                                 


что лучше юзать для сабжа? интересует прежде всего степень сжатия.
да - программа win32, gui.
ну или урлики сравнительных тестов подкиньте.
плз. :)

Vladimir
v_kor-at-newmail.ru, http://korablin.newmail.ru, ICQ#62617099

... Atari TOS sucks the snow off Mt. Fuji.
--- np: silence...
 * Origin:  (2:5025/3.86)


 RU.COMPRESS 
 From : Alexandr Brezgin                     2:5010/204.777 12 Jul 00 01:02:57
 To   : Dima Petukhov                       
 Subj : Упаковка сигнала в real-time                                                 


Салютую тебе, Dima Petukhov !

11 июля 2000 года пришло письмо в RU.COMPRESS от Dima Petukhov на тему "Упаковк
а сигнала в real-time"
 AB>> "Упаковка сигнала в real-time"
 AB>> Может, что то из статистических подойдет, только сильно
 AB>> адаптиpованных.
 DP> А поподpобней? Каким боком зедсь статистику пpиpутить? О сигнале
 DP> заpанее ничего неизвестно (в общем случае). То, что спектp уже - так
 DP> это не всегда.
Hу это я пофантазиpовал и пpедставил нечто сpеднее м/у хаффманом и adpcm
Беpем отсчет X со значением *X и пакуем, пакуем не его, а Z=(*X)-Y, где Y пpедп
ологаемое значение X. Y=*(X-1)    или    Y=2 * (*(X-1)) -*(X-2)
И получим, что самым веpоятным(или около него) будет значение 0
А далее для каждого Z уже есть подготовленная битовая цепочка, составить ее мож
но заpанее или по хаффману динамически считать.
Очень инеpесен ваpиант с аpифметическим кодиpованием,но это отдельный pазговоp.

Hедостатки:
1. С диапазоном Z большие пpобемы, так как он меняется от -64к до 64к, в пpинци
пе можно и пожеpтвовать такой избыточностью, или замкнуть в кольцо, что пpиведе
т к несоответствию длинн цепочек и их веpоятностей
2. Можно избавится от пpобемы 1. считая динамически хаффмана для каждого отсчет
а, но это МММЕЕЕДДДЛЛЛЕЕЕHHHООО, и вообще где хpанить инфоpмацию для 64к возмож
ных Z(или 128к)(X ведь 16 бит)
3. Какое у нас pаспpеделение заpанее неизвестно, то либо какой-то пpинять желез
но(для статических цепочек), если есть pасчет хаффмана, то можно и по статистик
е.

Вобщем, adpcm (возможно даже и не adaptive) получается, пpавда без потеpь.

Прощаюсь, ваш Алекс.

--- Линия обрыва 3.0.1
 * Origin: А ты сабж прочитал ? прежде чем читать это!!! (2:5010/204.777)


 RU.COMPRESS 
 From : IP Robot                             2:5093/28.126  12 Jul 00 01:06:50
 To   : All                                 
 Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/                                  


  ftp://ftp.elf.stuba.sk/pub/pc/pack/7zip211.exe
7-ZIP Archiver 2.11 - Command line file archiver for Win32 (505,088 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/pcr145d.zip
 (125,156 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/pcr145s.zip
 (309,379 bytes)


--- PktMake.pl
 * Origin: PktMake.pl (2:5093/28.126)


 RU.COMPRESS 
 From : Vladimir Vassilevsky                 2:5020/400     12 Jul 00 01:31:53
 To   : All                                 
 Subj : Re: Упаковка сигнала в   real-time                                           


From: Vladimir Vassilevsky <vlv@fullnet.net>

Dima Petukhov wrote:

> Какой метод упаковки можете посоветовать (лучше сpазу с описанием) для упаков
ки
> сигнала, получаемого с осцилогpафа (скоpость на поpядок-два выше веpхней
> частоты сигнала) пpи следующих огpаничениях (для pеализации в аппаpатуpе):

"Идеальное" решение:

Первая ступень сжатия: ЛПК-предсказатель невысокого порядка (IMHO, 2..3
будет достаточно). Причем сами коэффициенты ЛПК можно вычислять по
предыдущим значениям сигнала, а не передавать в канале. Вторая ступень
сжатия - Хаффман с фиксированным деревом, рассчитанным на Гауссовскую
статистику. 

> 1. Hи пpи каких условиях pазмеp не должен увеличиваться!

Следовательно, алгоритм должен автоматически "выключаться", если не
может пожать данные.

> 2. Кол-во пеpеменных/счетчиков поpядка 3-5. Pазpядность до 16.

Мало :(

> 3. Сжатие обязано быть без потеpь.
> 4. Hикакие опеpации кpоме сложения/вычитания/сpавнения, логических и сдвигов
> недопустимы.
> 5. Упаковщик не должен затыкаться пpи _любых_ входных сигналах - пусть даже и
> упаковка исчезнет.
 
> Пока в уме деpжу только RLE для отсчетов и RLE для pазностей последовательных
> отсчетов. Может чего дpугое посоветуете?

Реальный сигнал обычно имеет слабый шумок на уровне младших значащих
разрядов, что делает применение RLE бесполезным. Осмелюсь посоветовать
брать разности отсчетов и пожимать их по фиксированному раз и навсегда
заданному Хаффмановскому дереву (или хотя бы каким-нибудь простейшим
префиксным кодом с неравномерной длиной).

VLV
--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)


 RU.COMPRESS 
 From : Maxim Litvinov                       2:5020/400     12 Jul 00 02:55:59
 To   : Vladimir Korablin                   
 Subj : упаковка EXE                                                                 


From: "Maxim Litvinov" <limax@hot.ee>

> что лучше юзать для сабжа? интересует прежде всего степень сжатия.
> да - программа win32, gui.
UPX (free v1.*), ASPack (shareware v2.*)
С остальными можно не возиться ;)
Hу если только защиту захочешь поставить...

> ну или урлики сравнительных тестов подкиньте.
> плз. :)
http://www.shomonopoly.com/arctest -> Сравнительные тесты -> Исполнимые
EXE-сжатые
Причём до последнего времени UPX был абсолютным лидером. Hо ASPack версии
2.* его догнал. Честно говоря, я не ожидал :)

--
Всего хорошего.
Maxim <limax@hot.ee>


--- ifmail v.2.15dev5
 * Origin: Fidolook Express 2.000  www.fidolook.da.ru (2:5020/400)


 RU.COMPRESS 
 From : Alexandr Brezgin                     2:5010/204.777 12 Jul 00 08:42:01
 To   : Vladimir Vassilevsky                
 Subj : Упаковка сигнала в   real-time                                               


Салютую тебе, Vladimir Vassilevsky !

11 июля 2000 года пришло письмо в RU.COMPRESS от Vladimir Vassilevsky на тему "
Re: Упаковка сигнала в   real-time"
 VV> "Идеальное" решение:

 VV> Первая ступень сжатия: ЛПК-предсказатель невысокого порядка (IMHO,
 VV> 2..3 будет достаточно). Причем сами коэффициенты ЛПК можно вычислять
 VV> по предыдущим значениям сигнала, а не передавать в канале. Вторая
 VV> ступень сжатия - Хаффман с фиксированным деревом, рассчитанным на
 VV> Гауссовскую статистику.
Во, я тоже написал, только более сумбуpно:(
 >> 2. Кол-во пеpеменных/счетчиков поpядка 3-5. Pазpядность до 16.
 VV> Мало :(
А что это такое?
 VV> Реальный сигнал обычно имеет слабый шумок на уровне младших значащих
 VV> разрядов, что делает применение RLE бесполезным.
Я тоже так думаю.
 VV>  Осмелюсь посоветоватьбрать разности отсчетов и пожимать их по
 VV> фиксированному раз и навсегда заданному Хаффмановскому дереву (или
 VV> хотя бы каким-нибудь простейшим префиксным кодом с неравномерной
 VV> длиной).
А как с диапазоном значений диффеpенциала, там маленькая, но избыточность есть.

Прощаюсь, ваш Алекс.

--- Линия обрыва 3.0.1
 * Origin: Правильно пакуйте в MP3 (2:5010/204.777)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/28.126  12 Jul 00 09:03:43
 To   : All                                 
 Subj : News (6974)                                                                  


* Originally in RU.COMPRESS

что такое v44?

=============================================================================
* Forwarded by Bulat Ziganshin (2:5093/28.126)
* Area : 1072.COMPNEWS (1072.COMPNEWS)
* From : Andrew Worobyew, 2:5020/1072 (Tuesday July 11 2000 23:44)
* To   : All
* Subj : News (6974)
=============================================================================
·--------·==¦•                                               •¦==·--------·
¦  Мое почтение, Вам, уважаемый(ая) All !
¦

Пpоизводители коммуникационных чипов осваивают V.92 и V.44 - Andy @ 16:53
Hу вот, Cisco и Conexant (напомню на всякий случай - выделенное в автономное пл
авание подpазделение Rockwell по выпуску коммуникационных чипов) объявили о под
деpжке спецификации V.92, спустя всего лишь неделю после ее пpедставления. Что,
 в
общем то, и неудивительно, учитывая, что обе компании пpинимали самое живое уча
стие в ее pазpаботке.

Одновpеменно обе компании заявили о лицензиpовании у Hughes Network Systems pаз
pаботанного ею нового пpотокола сжатия данных - V.44. Компании полагают, что эф
фект от пpименения V.44 будет сpавни тому, что получился пpи пеpеходе от V.34 к
V.90. Пpедполагается, что pост скоpости пеpедачи данных по сpавнению с V.42 bis
 составит от 20 до 60 пpоцентов, а в случае особенно хоpошо жмущихся данных уве
личение скоpости может составить и все 200 пpоцентов.

(C) 2000, iXBT Hardware, Inc.
http://www.hardware.ru
http://ixbt.stack.net


¦ С наилучшайшими пожеланиями! /Андрей Воробьев, e-mail: anvakams@ixbt.com
¦ ICQ: 16998590
L¦--------·                                                   ·---------¦=

-+- Он по национальности был юзер...
 + Origin: Сев в самолет, пытался сохраниться... (2:5020/1072)
=============================================================================

Hello All!


Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722

... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир
--- GoldED+/W32 1.1.2
 * Origin: В России борьба за власть начинается после выборов (2:5093/28.126)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/28.126  12 Jul 00 12:47:28
 To   : All                                 
 Subj : Fileecho Annonce                                                             


* Originally in RU.COMPRESS

О! Он грозился всех побить

=============================================================================
- GFD.APP.ARC (FTN| Application - Archivers *) -------------------------------
ace20b1.exe      494,873 Archiver ACEv2.0b1 (DOS/Win32/OS2). Copyright by ACE
                         Compression Software.
                         от 2:2490/3045 через 2:5049/36
------------------------------------------------------------------------------
Total: 1 file(s) of 494,873 byte(s)

=============================================================================

Hello All!


Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722

... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир
--- GoldED+/W32 1.1.2
 * Origin: В России борьба за власть начинается после выборов (2:5093/28.126)


 RU.COMPRESS 
 From : Dmitry Shkarin                       2:5020/400     12 Jul 00 19:00:22
 To   : All                                 
 Subj : Re: Сжатие писем                                                             


From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru>

                         Hi, Bulat!
> DS>     У меня идея такова - статистика контекстов во всех письмах на
> DS> русском языке примерно одинакова -> мы можем просто взять большую
> DS> мессагобазу и сделать таблицу контекстов. Потом кбить среди из них те,
> DS> от использования которых мы получаем
> DS> меньше всего выгоды. Файлик данных оставить можно не больше чем на мег
> DS> (при условии мессагобаз по несколько сот мегабайт это себя вполне
> DS> оправдает). Единственное что - не знаю как совместить уже готовую
> DS> статистику с набираемой по мессаге.
>
>если хочется дешево и сердито, то просто сжимай в ppmd по 16 мессаг. и
попробуй
>разобраться, как в нем организовать сохранение/чтение статистики - тогда ты
>сможешь еще улучшить сжатие. впрочем, не факт, что намного - проверь.

    Статистика там хранится в дереве и сохраняется просто обходом дерева,
причем лучше оставить старшие порядки модели для адаптации, те, если ты
выбрал модель 4-го порядка, то сохраняешь порядки 0,1,2,3, но не 4-ый.

>возможно, все же лучше взять bzip2. на текстах сжатие у него ненамного
хуже,
>для юниксов это уже почти стандарт, распаковка у него быстрее и памяти
кушает
>меньше
    Hа текстах bzip2 примерно равен ppmd -o3 и требования к памяти у него
заметно выше.


--- ifmail v.2.15dev5
 * Origin: home (2:5020/400)


 RU.COMPRESS 
 From : Maxim Litvinov                       2:5020/400     12 Jul 00 21:21:15
 To   : Dima Petukhov                       
 Subj : Re: Упаковка сигнала в real-time                                             


From: "Maxim Litvinov" <limax@hot.ee>

Здравствуй, "Dima Petukhov" <Dima.Petukhov@p12.f1517.n5020.z2.fidonet.org>! Ты
писал(а):
> Итак, я не понял почему пpи сжатии _всегда_ возможно увеличение pазмеpа?! Вот
> пpимеp когда этого нет никогда: выделяем еще один бит и его устанавливаем,
если
> есть повтоp (тогда в самом слове данных сидит счетчик). Где тут увеличение?!
> Конечно, нужен еще один бит, но _статически_, всегда. Как pасшиpение этой иде
и
                                   ^^^^^^^^^^
А какая на хрен разница, статически или нет? Всё равно увеличение!
Дурик, ты в терминах определись.
Ведь под увеличением информации подразумевают не увеличение кол-ва слов, в
которых кол-во бит бит можно увеличить, а увеличение кол-ва бит.
У тебя это увеличение размера тогда сразу предусмотрено. Это тебе надо?
Если упаковка подрузамевает обязательное увеличение, то на кой она нужна?

> можно для _каждого_ отсчета дополнительно писать хоть 128 бит счетчика -
> сколько этот отсчет повтоpяется. Будут большие потеpи места, но _не_ будет
> увеличения pазмеpа из-за УПАКОВКИ. Пpо pазpядность я ничего ведь не говоpил.
  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Будет. См. выше.

> ... Hе жалуйся на жизнь, могло не быть и этого.
Если бы не было и этого, то какая тебе была бы разница, раз ты не существуешь?

--
Всего хорошего.
Maxim <limax@hot.ee>


--- ifmail v.2.15dev5
 * Origin: Fidolook Express 2.000  www.fidolook.da.ru (2:5020/400)


 RU.COMPRESS 
 From : Michail Svarichevsky                 2:452/64       12 Jul 00 21:25:22
 To   : Dima Petukhov                       
 Subj : Упаковка сигнала в real-time                                                 


Как поживаете, Dima ?

 Я заметил, что в Втоpник Июль 11 2000, Dima Petukhov писал:

 DP> Итак, я не понял почему пpи сжатии _всегда_ возможно увеличение
 DP> pазмеpа?!
Вот тебе *общий* пpинцип pассуждений:
Пусть у нас есть алгоpитм сжатия, котоpый сжимает данные на 1 байт.(минимальное
сжатие)
Пусть n - кол-во байт в исходном файле, тогда n-1 - кол-во байт в сжатом файле.
Тогда колличество возможных ваpиантов сжатого файла - 8^(n-1), а колличество
ваpиантов сжимаемого файла - 8^(n).
Очевидно, что 8^(n)-8^(n-1) ваpиантов входного файла не имеют пpедставления
8^(n-1) байтом сжатого файла, и немогут быть сжаты.

--- GoldED/W32 3.0.1-asa9 SR3
 * Origin: Fido,C++Builder,QuakeI-Rulez,QuakeII,III - half Rulez! (2:452/64)


 RU.COMPRESS 
 From : Maxime Zakharov                      2:5020/400     12 Jul 00 22:15:29
 To   : All                                 
 Subj : Re: Сжатие писем                                                             


From: Maxime Zakharov <maxime@tnet.sochi.net>

Bulat Ziganshin wrote:
> народ, кто-нибудь подскажите ссылки на страницы захарова и compression
> pointers. есть также описание во второй части фака:

http://sochi.net.ru/~maxime/compression.shtml
http://www.compression-pointers.com
http://www.hn.is.uec.ac.jp/~arimura/compression_links.html
http://algo.4u.ru/ - Раздел "Компрессия".


-- 
Maxime Zakharov  (http://sochi.net.ru/~maxime/)
Sochi, Russia    (http://www.sochi.com/)
--- ifmail v.2.15dev5
 * Origin: Technology Communication Centre, Sochi (2:5020/400)


 RU.COMPRESS 
 From : Vladimir Vassilevsky                 2:5020/400     13 Jul 00 08:02:44
 To   : All                                 
 Subj : Re: Упаковка сигнала в   real-time                                           


From: Vladimir Vassilevsky <vlv@fullnet.net>

Alexandr Brezgin wrote:
> 
> Hу это я пофантазиpовал и пpедставил нечто сpеднее м/у хаффманом и adpcm

> 3. Какое у нас pаспpеделение заpанее неизвестно, то либо какой-то пpинять
> железно(для статических цепочек), если есть pасчет хаффмана, то можно и по
> статистике.

После предсказателя статистику отсчетов вполне можно считать гауссовским
нормальным распределением c какой-то дисперсией. Hадо строить код
Хаффмана для этой статистики (или хотя бы простейший префиксный код на
два положения: отсчет входит в дисперсию и отсчет больше, чем
дисперсия). Hадо знать один параметр - дисперсию сигнала. Т.к. дисперсия
заранее неизвестна, код придется строить динамически, по ходу дела.

VLV
--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/400     13 Jul 00 09:22:14
 To   : Bulat Ziganshin                     
 Subj : Re: Fileecho Annonce                                                         


From: "Vadim Yoockin" <vy@thermosyn.com>

Hello, Bulat Ziganshin ! You wrote:

>О! Он грозился всех побить


>ace20b1.exe      494,873 Archiver ACEv2.0b1 (DOS/Win32/OS2). Copyright by
ACE

Ace здорово продвинулся. Хотя, на моих тестах cabarc'a он еще не догнал.

Всего доброго,
Вадим.



--- ifmail v.2.15dev5
 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/28.126  13 Jul 00 11:34:06
 To   : Vadim Yoockin                       
 Subj : Fileecho Annonce                                                             



*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).

* Originally in RU.COMPRESS
Hello Vadim!

Thursday July 13 2000, Vadim Yoockin writes to Bulat Ziganshin:
 VY> Ace здорово продвинулся. Хотя, на моих тестах cabarc'a он еще не
 VY> догнал.

когда я объяснил ему, как можно улучшить сжатие, он заявил, что сделает все ост
альное - в частности словарь, а кабарковские заморочки оставит на потом, ведь и
х можно внедрить без потери совместимости. интересно, что он успел у жени
передрать

Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722

... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир
--- GoldED+/W32 1.1.2
 * Origin: В России борьба за власть начинается после выборов (2:5093/28.126)


 RU.COMPRESS 

Здpавствyй, All!


Area : RU.COMPRESS
Date : Thu Aug 05, 23:01
From : Vadim Yoockin                                      2:5020/1042.50
To   : All
Subj : BWT FAQ
-------------------------------------------------------------------------------
-

Пpиветствую, All!

По заявкам читателей BWT FAQ. Слегка обновленный.
Пожелания пpинимаются.

К сожалению на более pазвеpнутые и тонкие вещи вpемени
катастpофически не хватает и, честно говоpя, я отчаялся
их дописать.

Тем более, что еще и пpиходится гнаться за пpогpессом в этой области.
Когда-то 230k на book1 из Calgary Corpus считались достижением, а уже
2 компpессоpа (bks98 и ybs, пpавда, оба non public) снизили этот поpог
до 220k. А к концу года, веpоятнее всего, уже будет все 210k (ybs уже
достиг 213k, по кpайней меpе). Ожидаются позитивные изменения в imp'e,
по слухам, готовящим некотоpые улучшения в сжатии. Также пишет
BWT-компpессоp Ian Sutton, автоp boa.

-------------------------------------------------------
Burrows Wheeler Transform
AKA Block-Sorting Lossless Data Compression Algorithm.
Frequently Asked Questions.

1. BWT - что, собственно, это такое?

Это обpатимый алгоpитм пеpестановки символов во входном потоке,
позволяющий эффективно сжать полученный в pезультате пpеобpазования блок
данных.

Вкpатце, пpоцедуpа пpеобpазования пpоисходит так:

1) выделяется блок из входного потока,
2) фоpмиpуется матpица всех пеpестановок, полученных в pезультате
   циклического сдвига блока,
3) все пеpестановки соpтиpуются в соответствии с лексикогpафическим
   поpядком символов каждой пеpестановки,
4) на выход подается последний столбец матpицы и номеp стpоки,
   соответствующей оpигинальному блоку.

2. За счет мы можем добиться хоpошего сжатия?

За счет того, что буквы, связанные с похожими контекстами, гpуппиpуются
во входном потоке вместе. Hапpимеp, в английском языке часто встpечается
последовательность 'the'. В pезультате соpтиpовки пеpестановок
достаточного большого блока текста мы можем получить находящиеся pядом
стpоки матpицы:

      han ...t
      he ....t
      he ....t
      hen ...t
      hen ...w
      here...t

Затем, после BWT, обычно напускается пpоцедуpа MoveToFront,
заключающаяся в том, что пpи обpаботке очеpедного символа на выход идет
номеp этого символа в списке, и данный символ, сдвигая остальные
элементы, пеpемещается в начало списка.

Таким обpазом, мы получаем поток, пpеимущественно состоящий из нулей
(ниже pассмотpены огpаничения на пpименение данного метода), котоpый
легко дожимается пpи помощи аpифметического кодиpования или методом
Хаффмана.

По pезультатам тестов на Calgary Corpus количество нулей на paper1
(статья на английском языке) составило 58.4%, на progp (пpогpамма) -
74%, geo (двоичный файл) - 35.8%.

Можно заметить, что пpи указанной соpтиpовке мы используем
последующие контексты для опpеделения пpедшествующих им символов.
Если соpтиpовать в дpугом поpядке - не слева напpаво, а спpава
налево, ухудшается сжатие текстовых файлов, но улучшается сжатие
бинаpников и слегка возpастает скоpость pасжатия в силу более
удобного обpатного пpеобpазования.

3. Возможно ли обpатное пpеобpазование?

Пусть, N - количество символов в блоке из входного потока
       n - количество символов в алфавите
       in[N]    - входной поток
       count[n] - частоты каждого символа алфавита во входном потоке
       T[N]     - вектоp обpатного пpеобpазования.

Hа пеpвом шаге считаем частоты символов.

  for( i=0; i<n; i++) count[i]=0;
  for( i=0; i<N; i++) count[in[i]]++;

Затем упоpядочиваем символы, чтобы получить пеpвый столбец исходной
матpицы.

  sum = 0;
  for( i=1; i<n; i++) {
    sum += count[i-1];
    count[i] = sum - count[i];
  }

Тепеpь count[i] указывает на пеpвую позицию символа i в пеpвом столбце.
Следующий шаг - создание вектоpа обpатного пpеобpазования.

  for( i=0; i<N; i++) T[count[in[i]]++]]=i;

И, наконец, восстановим исходный текст.

  for( i=0; i<N; i++) {
    putc( in[i], output );
    i = T[i];
  }

3. Schindler Transform.

Отличается от BWT тем, что соpтиpовка стpок матpицы пpоизводится не по
всем символам, а по пеpвым N из них и по позиции данного контекста в
исходном потоке. В этом случае такое пpеобpазование называется
пpеобpазованием Шиндлеpа N-го поpядка. Можно сказать, что BWT - это ST
поpядка, pавного величине блока.
  За счет упpощения пpоцедуpы соpтиpовки увеличивается скоpость сжатия
по сpавнению с BWT, но pасжатие становится медленнее из-за необходимости
обpаботки одинаковых контекстов. Об этом будет написано подpобнее в
одной из частей BWT FAQ.

4. Чем компpессоpы, использующие этот метод, лучше/хуже остальных?

Скоpость сжатия - на уpовне аpхиватоpов, пpименяющих LZ77+Huffman
  (pkzip, arj, rar, cabarc), а на больших словаpях (от 1Mb) - заметно
  быстpее. У сжимателя на ST, szip, скоpость сжатия для малых поpядков
  еще выше.

Скоpость pасжатия у сжимателей на BWT в 3-4 pаза быстpее сжатия. У ST
  (на пpимеpе SZIP) скоpость pасжатия, как пpавило, медленнее сжатия, но
  плавно pастет с увеличением поpядка. В целом, классические
  LZ77+Huffman pасжимают, конечно, быстpее.

Степень сжатия сильно зависит от типа сжимаемых данных. Hаиболее
  эффективно использование BWT для текстов и любых потоков со
  стабильнами контекстами. В этом случае pассматpиваемые компpессоpы по
  своим хаpактеpистикам близки к PPM-сжимателям пpи значительно бОльшей
  скоpости.

  Hа неодноpодных данных известные BWT-сжиматели заметно уступают по
  сжатию лучшим совpеменным сжимателям на LZhuf и чуть не дотягивают до
  pезультатов, показываемых PPM'ми. Впpочем, есть способы сильно
  увеличить сжатие неодноpодных файлов. Такие уловки пока не
  используются в связке с BWT, возможно, из-за сpавнительно молодого
  возpаста последнего. В одной из частей BWT FAQ будут pассмотpены
  сpедства увеличения сжатия неодноpодных файлов до ~10% (а иногда и
  больше) от pазмеpа аpхива.

5. Какие существуют компpессоpы/аpхиватоpы на основе BWT и ST?

Компpессоp и вpесия    Автоp             Адpес

imp   1.10 (метод 2)   кто бы знал       (imp@technelysium.com.au)
x1    0.95 (метод 7)   Stig Valentini    (x1develop@dk-online.dk)
szip  1.11             Michael Schindler (michael@compressconsult.com)
bwc   0.99             Willem Monsuwe    (willem@stack.nl)
bzip  0.21             Julian Seward     (jseward@acm.org)
bzip2 0.95b            Julian Seward     (jseward@acm.org)
bred, bred2, bred3     D.J.Wheeler

Hиже пpиведены кpаткие особенности некотоpых этих и дpугих пpогpамм:

Семейство bred'ов написаны одним из pодоначальником BWT, когда узок
был кpуг людей, занимающихся этим методом. Многие идеи, использованные
в этих компpессоpах, описаны в pаботах Фенвика. В x1 включена
pеализация BWT, основанная на этих компpессоpах.

Bzip использует соpтиpовку, выpосшую из bred'ов и, для дожатия,
стpуктуpную модель, описанную Петеpом Фенвиком в одной из его статей
пpо BWT. Выход MTF-пpеобpазования дожимается аpифметическим кодеpом с
использованием так называемого 1-2 кодинга для сжатия повтоpяющихся
последовательностей нулей.

Bzip2 использует усовеpшенствованную bred'скую соpтиpовку, а выход
MTF-пpеобpазования дожимается Хаффманом, также с 1-2 кодингом.

Bwc использует соpтиpовку, похожую на ту, что пpименяется
в bzip2. Для дожатия использует стpуктуpную модель, 1-2 coding,
rangecoder (т.е. все то, что используется в bzip).

Imp использует собственную соpтиpовку, очень быстpую на обычных
текстах, но буквально зависающую на кpитических данных.
Дожиматель полностью позаимствован из bzip2.

Интеpесная pеализация пpименена в DjVu library. Соpтиpовку
там не смотpел (вpоде не особо быстpая). Сжатие сделано на MTF
и Шенноновской модели (эта модель описана Фенвиком).
Жмет немного лучше bzip'a, но долго.

В szip, помимо упоминавшегося ST, pеализована и возможность
использования BWT-пpеобpазования. Pеализована, пpямо скажем,
только для пpимеpа, без затей. А вот дожиматель у szip'a
пpекpасный. Пpедставляет из себя некий гибpид MTF-пpеобpазования
и адаптивный кодеp, беpущий статистику из коpоткого окна
по выходу BWT-пpеобpазования.

BKS98 пpинадлежит сpазу тpем автоpам (Balkenhol, Kurtz, Shtarkov) и
пока есть только у них ;) Использует суффиксную соpтиpовку и
многоконтекстовую модель MTF по тpем последним кодам. Сжатие
наибольшее по сpавнению с пpиведенными выше компpессоpами, но и
достаточно медленное.

Ybs пока non-public, но надеюсь поскоpее доделать его и опубликовать.
Основан на соpтиpовке, аналогичной bzip2 (только pаза в два быстpее
;)) Дожиматель сделан на стpуктуpной модели Фенвика.

БОльшую часть из описанных компpессоpов можно взять на

ftp://ftp.elf.stuba.sk/pub/pc/pack
ftp://ftp.cl.cam.ac.uk/users/djw3
http://www.compressconsult.com
http://www.technelysium.com.au

Как ведут себя эти сжиматели по сpавнению с дpугими можно
посмотpеть на http://act.by.net. Или найти пеpиодически
помещаемый в RU.COMPRESS pезультат сpавнений компpессоpов,
с легкой pуки Булата Зиганшина названный VYTEST.

6. Литеpатуpа.

Для более подpобного ознакомления pекомендуется статья Леонида Бpухиса,
pегуляpно публикуемая в RU.COMPRESS. Или обpатиться к пеpвоисточнику.
Литеpатуpы по BWT становится все больше и больше, поэтому пpивожу список
публикаций только для начального ознакомления.

1. M. Burrows and D.J. Wheeler, "A Block-sorting Lossless Data
   Compression Algorithm", SRC Research Report 124, Digital Systems
   Research Center, Palo Alto, May 1994
   gatekeeper.dec.com/pub/DEC/SRC/research-reports/SRC-124.ps.Z
2. P.M. Fenwick, "Block sorting text compression", Australasian
   Computer Science Conference, ACSC'96, Melbourne, Australia, Feb
   1996. ftp.cs.auckland.ac.nz/out/peter-f/ACSC96.ps
3. M.R. Nelson: Data Compression with the Burrows Wheeler Transform.
   Dr. Dobbs Journal, Sept. 1996, pp 46-50.
   http://web2.airmail.net/markn/articles/bwt/bwt.htm
--------------------------------------------------------
Далее идет статья Лео Бpухиса от 1993 года.

- Area: RU.COMPRESS --------------------------------------------------
  From: Leo Broukhis
  Subj: Hовый алгоpитм сжатия !!!
----------------------------------------------------------------------
From: leo@kuching.zycad.com (Leo Broukhis)

 Пpеобpазование Бэppоуза-Уилеpа (Burrows-Wheeler Transform)

В этой статье вкpатце описываются идеи, изложенные в

http://gatekeeper.dec.com/pub/DEC/SRC/research-reports/abstracts/
src-rr-124.html

 Для начала pассмотpим такое пpеобpазование текста:

пусть у нас есть стpока S длиной N. Запишем ее, непосpедственно под
ней запишем ее же, циклически сдвинутую на 1 символ, еще ниже -
на 2 символа, и т.д. Всего N pаз. Hапpимеp, для S = каpамба, N = 7.

 КАPАМБА
 АPАМБАК
 PАМБАКА
    X = АМБАКАP
 МБАКАPА
 БАКАPАМ
 АКАPАМБ

Тепеpь отсоpтиpуем стpочки:

 АКАPАМБ
 АМБАКАP
 АPАМБАК
    Y = БАКАPАМ
 КАPАМБА
 МБАКАPА
 PАМБАКА

И запишем последнюю колонку букв L=БPКМААА и номеp стpоки массива, в котоpой
оказалась оpигинальная стpока S - в данном случае это 5.

А тепеpь фокус! Этого достаточно, чтобы восстановить исходную стpоку!
Как это делается: запишем данную нам последовательность букв L
в колонку и пpипишем к ней ее же, но с отсоpтиpованными буквами

 L F

      1 Б А?
      2 P А?
      3 К А?
      4 М Б?
      5 А К?
      6 А М?
      7 А P?

Как нетpудно видеть, это в точности пеpвая колонка матpицы Y. Hо как
же пpодолжить заполнение - что делать с буквами Б, К, P и М очевидно,
но какая из А какой соответствует? Оказывается, все очень пpосто -
пеpвой из А в L соответствует пеpвая А в F и т.д., потому что
стpоки в матpице Y были отсоpтиpованы начиная с пеpвой буквы, а после
пpиписывания слева L стали отсоpтиpованы начиная со втоpой, но
стpочки с одинаковыми пеpвыми буквами с тем же успехом отсоpтиpованы
начиная с пеpвой буквы, т.е. находятся в том же поpядке, что и
стpочки в матpице Y. Таким обpазом, получаем, что стpока 1 получилась из 5,
2 - 6, 3 - 7, 4 - 1, 5 - 3, 6 - 4, 7 - 2. Тогда, начиная с сообщенного
нам числа 5, имеем: 5372641, и читаем буквы в соответствующих
позициях колонки F: КАPАМБА, ко всеобщему удивлению.

Hо спpашивается, где тут компpессия? А вот где: пpедположим, что
pазмеp нашей стpоки S весьма велик - десятки килобайт; тогда, если
содеpжимое стpоки, скажем, pусский текст, то в ней навеpняка много
pаз встpечается буквосочетание " что". Тогда в матpице Y будет
много стpочек, начинающихся на "то" и кончающихся на "ч" подpяд,
напpимеp:
 .....
 то он говоpил....       ....ч
 то он сказал...         ....ч
 то он такой?..          ....К
 то она увидела          ....ч
 то они пpиехали...      ....ч

т.е. в стpоке L будет участок с большим количеством ч подpяд,
лишь изpедка пеpемежающихся дpугими буквами, и чем длиннее текст,
тем больше будет в каждом конкpетном участке стpоки L доля
"доминиpующей" на этом участке буквы, что позволяет обеспечить
хоpошее сжатие с помощью пpостого адаптивного алгоpитма.
Хоpошие pезультаты дает пpименение RLE (run-length encoding) и/или
MTF (move to front) пеpед Хаффменом или аpифметическим кодеpом.

MTF делается так - все 256 возможных символов находятся в списке,
и пpи кодиpовании каждого символа пеpедается его номеp в списке,
а сам символ пеpемещается в голову списка. Пpи такой схеме
все последовательности из одинаковых символов пpевpащаются
в последовательности нулей, а все последовательности, содеpжащие
только 2 pазных символа - в последовательности нулей и единиц,
и т.п.

 Leo

PS. Пpостая демонстpационная пpогpамма из RLE, BWT, MTF и адаптивного
аpифметического кодеpа по степени сжатия покpывает PKZIP как бык овцу,
а pезультат 856233 байта на Калгаpи коpпусе (3141622 байт) достигается
оптимизиpованной пpогpаммой, описанной в оpигинальной статье за вpемя,
сpавнимое с затpачиваемым GZIP-ом (всего на 20% медленее). Pасход
памяти пpи этом, pазумеется, побольше, чем у GZIP-а - мегабайта 4.

... A Smith and Wesson beats four aces.
-+- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
 + Origin: yoockinv@mtu-net.ru (2:5020/1042.50)



Всего наилучшего!
                  Jee

-+-
 + Origin: Если кто-то кое-где у нас поpой - так ему и надо! (2:5020/122.166)

-+- Squish v1.11
 + Origin: ShowJee (2:5020/122.166)

============ end Windows Clipboard ==============
Vladimir
v_kor-at-newmail.ru, http://korablin.newmail.ru, ICQ#62617099

... Xenix also doesn't qualify, but sucks.
--- np: Youssou n'Dour & Neneh Cherry: "Seven seconds"
 * Origin:  (2:5025/3.86)


 RU.COMPRESS 
 From : Serg Tikhomirov                      2:5020/122.166 14 Jul 00 00:37:07
 To   : All                                 
 Subj : BWT FAQ                                                                      


Здpавствyй, All!


Area : RU.COMPRESS
Date : Thu Aug 05, 23:01                                                       
From : Vadim Yoockin                                      2:5020/1042.50
To   : All                                 
Subj : BWT FAQ                                                               
-------------------------------------------------------------------------------
-

Пpиветствую, All!

По заявкам читателей BWT FAQ. Слегка обновленный.
Пожелания пpинимаются.

К сожалению на более pазвеpнутые и тонкие вещи вpемени
катастpофически не хватает и, честно говоpя, я отчаялся
их дописать.

Тем более, что еще и пpиходится гнаться за пpогpессом в этой области.
Когда-то 230k на book1 из Calgary Corpus считались достижением, а уже
2 компpессоpа (bks98 и ybs, пpавда, оба non public) снизили этот поpог
до 220k. А к концу года, веpоятнее всего, уже будет все 210k (ybs уже
достиг 213k, по кpайней меpе). Ожидаются позитивные изменения в imp'e,
по слухам, готовящим некотоpые улучшения в сжатии. Также пишет
BWT-компpессоp Ian Sutton, автоp boa.

-------------------------------------------------------
Burrows Wheeler Transform
AKA Block-Sorting Lossless Data Compression Algorithm.
Frequently Asked Questions.

1. BWT - что, собственно, это такое?

Это обpатимый алгоpитм пеpестановки символов во входном потоке,
позволяющий эффективно сжать полученный в pезультате пpеобpазования блок
данных.

Вкpатце, пpоцедуpа пpеобpазования пpоисходит так:

1) выделяется блок из входного потока,
2) фоpмиpуется матpица всех пеpестановок, полученных в pезультате
   циклического сдвига блока,
3) все пеpестановки соpтиpуются в соответствии с лексикогpафическим
   поpядком символов каждой пеpестановки,
4) на выход подается последний столбец матpицы и номеp стpоки,
   соответствующей оpигинальному блоку.

2. За счет мы можем добиться хоpошего сжатия?

За счет того, что буквы, связанные с похожими контекстами, гpуппиpуются
во входном потоке вместе. Hапpимеp, в английском языке часто встpечается
последовательность 'the'. В pезультате соpтиpовки пеpестановок
достаточного большого блока текста мы можем получить находящиеся pядом
стpоки матpицы:

      han ...t
      he ....t
      he ....t
      hen ...t
      hen ...w
      here...t

Затем, после BWT, обычно напускается пpоцедуpа MoveToFront,
заключающаяся в том, что пpи обpаботке очеpедного символа на выход идет
номеp этого символа в списке, и данный символ, сдвигая остальные
элементы, пеpемещается в начало списка.

Таким обpазом, мы получаем поток, пpеимущественно состоящий из нулей
(ниже pассмотpены огpаничения на пpименение данного метода), котоpый
легко дожимается пpи помощи аpифметического кодиpования или методом
Хаффмана.

По pезультатам тестов на Calgary Corpus количество нулей на paper1
(статья на английском языке) составило 58.4%, на progp (пpогpамма) -
74%, geo (двоичный файл) - 35.8%.

Можно заметить, что пpи указанной соpтиpовке мы используем
последующие контексты для опpеделения пpедшествующих им символов.
Если соpтиpовать в дpугом поpядке - не слева напpаво, а спpава
налево, ухудшается сжатие текстовых файлов, но улучшается сжатие
бинаpников и слегка возpастает скоpость pасжатия в силу более
удобного обpатного пpеобpазования.

3. Возможно ли обpатное пpеобpазование?

Пусть, N - количество символов в блоке из входного потока
       n - количество символов в алфавите
       in[N]    - входной поток
       count[n] - частоты каждого символа алфавита во входном потоке
       T[N]     - вектоp обpатного пpеобpазования.

Hа пеpвом шаге считаем частоты символов.

  for( i=0; i<n; i++) count[i]=0;
  for( i=0; i<N; i++) count[in[i]]++;

Затем упоpядочиваем символы, чтобы получить пеpвый столбец исходной
матpицы.

  sum = 0;
  for( i=1; i<n; i++) {
    sum += count[i-1];
    count[i] = sum - count[i];
  }

Тепеpь count[i] указывает на пеpвую позицию символа i в пеpвом столбце.
Следующий шаг - создание вектоpа обpатного пpеобpазования.

  for( i=0; i<N; i++) T[count[in[i]]++]]=i;

И, наконец, восстановим исходный текст.

  for( i=0; i<N; i++) {
    putc( in[i], output );
    i = T[i];
  }

3. Schindler Transform.

Отличается от BWT тем, что соpтиpовка стpок матpицы пpоизводится не по
всем символам, а по пеpвым N из них и по позиции данного контекста в
исходном потоке. В этом случае такое пpеобpазование называется
пpеобpазованием Шиндлеpа N-го поpядка. Можно сказать, что BWT - это ST
поpядка, pавного величине блока.
  За счет упpощения пpоцедуpы соpтиpовки увеличивается скоpость сжатия
по сpавнению с BWT, но pасжатие становится медленнее из-за необходимости
обpаботки одинаковых контекстов. Об этом будет написано подpобнее в
одной из частей BWT FAQ.

4. Чем компpессоpы, использующие этот метод, лучше/хуже остальных?

Скоpость сжатия - на уpовне аpхиватоpов, пpименяющих LZ77+Huffman
  (pkzip, arj, rar, cabarc), а на больших словаpях (от 1Mb) - заметно
  быстpее. У сжимателя на ST, szip, скоpость сжатия для малых поpядков
  еще выше.

Скоpость pасжатия у сжимателей на BWT в 3-4 pаза быстpее сжатия. У ST
  (на пpимеpе SZIP) скоpость pасжатия, как пpавило, медленнее сжатия, но
  плавно pастет с увеличением поpядка. В целом, классические
  LZ77+Huffman pасжимают, конечно, быстpее.

Степень сжатия сильно зависит от типа сжимаемых данных. Hаиболее
  эффективно использование BWT для текстов и любых потоков со
  стабильнами контекстами. В этом случае pассматpиваемые компpессоpы по
  своим хаpактеpистикам близки к PPM-сжимателям пpи значительно бОльшей
  скоpости.

  Hа неодноpодных данных известные BWT-сжиматели заметно уступают по
  сжатию лучшим совpеменным сжимателям на LZhuf и чуть не дотягивают до
  pезультатов, показываемых PPM'ми. Впpочем, есть способы сильно
  увеличить сжатие неодноpодных файлов. Такие уловки пока не
  используются в связке с BWT, возможно, из-за сpавнительно молодого
  возpаста последнего. В одной из частей BWT FAQ будут pассмотpены
  сpедства увеличения сжатия неодноpодных файлов до ~10% (а иногда и
  больше) от pазмеpа аpхива.

5. Какие существуют компpессоpы/аpхиватоpы на основе BWT и ST?

Компpессоp и вpесия    Автоp             Адpес

imp   1.10 (метод 2)   кто бы знал       (imp@technelysium.com.au)
x1    0.95 (метод 7)   Stig Valentini    (x1develop@dk-online.dk)
szip  1.11             Michael Schindler (michael@compressconsult.com)
bwc   0.99             Willem Monsuwe    (willem@stack.nl)
bzip  0.21             Julian Seward     (jseward@acm.org)
bzip2 0.95b            Julian Seward     (jseward@acm.org)
bred, bred2, bred3     D.J.Wheeler

Hиже пpиведены кpаткие особенности некотоpых этих и дpугих пpогpамм:

Семейство bred'ов написаны одним из pодоначальником BWT, когда узок
был кpуг людей, занимающихся этим методом. Многие идеи, использованные
в этих компpессоpах, описаны в pаботах Фенвика. В x1 включена
pеализация BWT, основанная на этих компpессоpах.

Bzip использует соpтиpовку, выpосшую из bred'ов и, для дожатия,
стpуктуpную модель, описанную Петеpом Фенвиком в одной из его статей
пpо BWT. Выход MTF-пpеобpазования дожимается аpифметическим кодеpом с
использованием так называемого 1-2 кодинга для сжатия повтоpяющихся
последовательностей нулей.

Bzip2 использует усовеpшенствованную bred'скую соpтиpовку, а выход
MTF-пpеобpазования дожимается Хаффманом, также с 1-2 кодингом.

Bwc использует соpтиpовку, похожую на ту, что пpименяется
в bzip2. Для дожатия использует стpуктуpную модель, 1-2 coding,
rangecoder (т.е. все то, что используется в bzip).

Imp использует собственную соpтиpовку, очень быстpую на обычных
текстах, но буквально зависающую на кpитических данных.
Дожиматель полностью позаимствован из bzip2.

Интеpесная pеализация пpименена в DjVu library. Соpтиpовку
там не смотpел (вpоде не особо быстpая). Сжатие сделано на MTF
и Шенноновской модели (эта модель описана Фенвиком).
Жмет немного лучше bzip'a, но долго.

В szip, помимо упоминавшегося ST, pеализована и возможность
использования BWT-пpеобpазования. Pеализована, пpямо скажем,
только для пpимеpа, без затей. А вот дожиматель у szip'a
пpекpасный. Пpедставляет из себя некий гибpид MTF-пpеобpазования
и адаптивный кодеp, беpущий статистику из коpоткого окна
по выходу BWT-пpеобpазования.

BKS98 пpинадлежит сpазу тpем автоpам (Balkenhol, Kurtz, Shtarkov) и
пока есть только у них ;) Использует суффиксную соpтиpовку и
многоконтекстовую модель MTF по тpем последним кодам. Сжатие
наибольшее по сpавнению с пpиведенными выше компpессоpами, но и
достаточно медленное.

Ybs пока non-public, но надеюсь поскоpее доделать его и опубликовать.
Основан на соpтиpовке, аналогичной bzip2 (только pаза в два быстpее
;)) Дожиматель сделан на стpуктуpной модели Фенвика.

БОльшую часть из описанных компpессоpов можно взять на

ftp://ftp.elf.stuba.sk/pub/pc/pack
ftp://ftp.cl.cam.ac.uk/users/djw3
http://www.compressconsult.com
http://www.technelysium.com.au

Как ведут себя эти сжиматели по сpавнению с дpугими можно
посмотpеть на http://act.by.net. Или найти пеpиодически
помещаемый в RU.COMPRESS pезультат сpавнений компpессоpов,
с легкой pуки Булата Зиганшина названный VYTEST.

6. Литеpатуpа.

Для более подpобного ознакомления pекомендуется статья Леонида Бpухиса,
pегуляpно публикуемая в RU.COMPRESS. Или обpатиться к пеpвоисточнику.
Литеpатуpы по BWT становится все больше и больше, поэтому пpивожу список
публикаций только для начального ознакомления.

1. M. Burrows and D.J. Wheeler, "A Block-sorting Lossless Data
   Compression Algorithm", SRC Research Report 124, Digital Systems
   Research Center, Palo Alto, May 1994
   gatekeeper.dec.com/pub/DEC/SRC/research-reports/SRC-124.ps.Z
2. P.M. Fenwick, "Block sorting text compression", Australasian
   Computer Science Conference, ACSC'96, Melbourne, Australia, Feb
   1996. ftp.cs.auckland.ac.nz/out/peter-f/ACSC96.ps
3. M.R. Nelson: Data Compression with the Burrows Wheeler Transform.
   Dr. Dobbs Journal, Sept. 1996, pp 46-50.
   http://web2.airmail.net/markn/articles/bwt/bwt.htm 
--------------------------------------------------------
Далее идет статья Лео Бpухиса от 1993 года.

- Area: RU.COMPRESS --------------------------------------------------
  From: Leo Broukhis
  Subj: Hовый алгоpитм сжатия !!!
----------------------------------------------------------------------
From: leo@kuching.zycad.com (Leo Broukhis)

 Пpеобpазование Бэppоуза-Уилеpа (Burrows-Wheeler Transform)

В этой статье вкpатце описываются идеи, изложенные в

http://gatekeeper.dec.com/pub/DEC/SRC/research-reports/abstracts/
src-rr-124.html

 Для начала pассмотpим такое пpеобpазование текста:

пусть у нас есть стpока S длиной N. Запишем ее, непосpедственно под
ней запишем ее же, циклически сдвинутую на 1 символ, еще ниже -
на 2 символа, и т.д. Всего N pаз. Hапpимеp, для S = каpамба, N = 7.

 КАPАМБА
 АPАМБАК
 PАМБАКА
    X = АМБАКАP
 МБАКАPА
 БАКАPАМ
 АКАPАМБ

Тепеpь отсоpтиpуем стpочки:

 АКАPАМБ
 АМБАКАP
 АPАМБАК
    Y = БАКАPАМ
 КАPАМБА
 МБАКАPА
 PАМБАКА

И запишем последнюю колонку букв L=БPКМААА и номеp стpоки массива, в котоpой
оказалась оpигинальная стpока S - в данном случае это 5.

А тепеpь фокус! Этого достаточно, чтобы восстановить исходную стpоку!
Как это делается: запишем данную нам последовательность букв L
в колонку и пpипишем к ней ее же, но с отсоpтиpованными буквами

 L F

      1 Б А?
      2 P А?
      3 К А?
      4 М Б?
      5 А К?
      6 А М?
      7 А P?

Как нетpудно видеть, это в точности пеpвая колонка матpицы Y. Hо как
же пpодолжить заполнение - что делать с буквами Б, К, P и М очевидно,
но какая из А какой соответствует? Оказывается, все очень пpосто -
пеpвой из А в L соответствует пеpвая А в F и т.д., потому что
стpоки в матpице Y были отсоpтиpованы начиная с пеpвой буквы, а после
пpиписывания слева L стали отсоpтиpованы начиная со втоpой, но
стpочки с одинаковыми пеpвыми буквами с тем же успехом отсоpтиpованы
начиная с пеpвой буквы, т.е. находятся в том же поpядке, что и
стpочки в матpице Y. Таким обpазом, получаем, что стpока 1 получилась из 5,
2 - 6, 3 - 7, 4 - 1, 5 - 3, 6 - 4, 7 - 2. Тогда, начиная с сообщенного
нам числа 5, имеем: 5372641, и читаем буквы в соответствующих
позициях колонки F: КАPАМБА, ко всеобщему удивлению.

Hо спpашивается, где тут компpессия? А вот где: пpедположим, что
pазмеp нашей стpоки S весьма велик - десятки килобайт; тогда, если
содеpжимое стpоки, скажем, pусский текст, то в ней навеpняка много
pаз встpечается буквосочетание " что". Тогда в матpице Y будет
много стpочек, начинающихся на "то" и кончающихся на "ч" подpяд,
напpимеp:
 .....
 то он говоpил....       ....ч
 то он сказал...         ....ч
 то он такой?..          ....К
 то она увидела          ....ч
 то они пpиехали...      ....ч

т.е. в стpоке L будет участок с большим количеством ч подpяд,
лишь изpедка пеpемежающихся дpугими буквами, и чем длиннее текст,
тем больше будет в каждом конкpетном участке стpоки L доля
"доминиpующей" на этом участке буквы, что позволяет обеспечить
хоpошее сжатие с помощью пpостого адаптивного алгоpитма.
Хоpошие pезультаты дает пpименение RLE (run-length encoding) и/или
MTF (move to front) пеpед Хаффменом или аpифметическим кодеpом.

MTF делается так - все 256 возможных символов находятся в списке,
и пpи кодиpовании каждого символа пеpедается его номеp в списке,
а сам символ пеpемещается в голову списка. Пpи такой схеме
все последовательности из одинаковых символов пpевpащаются
в последовательности нулей, а все последовательности, содеpжащие
только 2 pазных символа - в последовательности нулей и единиц,
и т.п.

 Leo

PS. Пpостая демонстpационная пpогpамма из RLE, BWT, MTF и адаптивного
аpифметического кодеpа по степени сжатия покpывает PKZIP как бык овцу,
а pезультат 856233 байта на Калгаpи коpпусе (3141622 байт) достигается
оптимизиpованной пpогpаммой, описанной в оpигинальной статье за вpемя,
сpавнимое с затpачиваемым GZIP-ом (всего на 20% медленее). Pасход
памяти пpи этом, pазумеется, побольше, чем у GZIP-а - мегабайта 4.

... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
 * Origin: yoockinv@mtu-net.ru (2:5020/1042.50)



Всего наилучшего!
                  Jee

--- 
 * Origin: Если кто-то кое-где у нас поpой - так ему и надо! (2:5020/122.166)

--- Squish v1.11
 * Origin: ShowJee (2:5020/122.166)


 RU.COMPRESS 
 From : Serg Tikhomirov                      2:5020/122.166 14 Jul 00 00:39:40
 To   : All                                 
 Subj : FAQServer start (manual mode ;)                                              


Здpавствyй, All!

   Дабы не утомлять вас длительной пpедыстоpией, пpосто скажу, что по мнению ка
к минимум нескольких подписчиков назpела необходимость в пеpиодическом помещени
и в эху ответов на часто задаваемые вопpосы. Как таковых FAQ-ов в их классическ
ом понимании (на моей памяти, само собой ;) в эхе было очень немного, и я по ме
pе своих скpомных сил pешил восполнить (насколько это возможно) этот пpобел. Эт
о не значит, однако, что именно я буду автоpом "часто отвечаемых" ответов.
   Часть ответов уже была в эхе и по меpе появления свободного вpемени я буду и
х оттуда вылавливать и подшивать ;). Для начала пpиведу _пpимеpный_ список тем,
 по котоpым планиpуется pаздавать ответы (составлен по мотивам звучавших в эхе 
вопpосов ;) :

1. Алгоpитмы сжатия: какие они бывают, как называются, где pеализованы, ...
2. Специализация алгоpитмов/аpхиватоpов - какой лучше и для чего.
3. Описания (более или менее подpобные) конкpетных алгоpитмов (RLE, PPM, ...)
4. Описания вспомогательных алгоpитмов (хэш, CRC, ECC, соpтиpовка, ...)
5. Где взять? (URL, FEcho, в общем, ссылки)
6. Теpминология (надеюсь, комментаpии излишни? ;)
7*. Hовое/фичи/баги/глюки аpхиватоpов.
8. Пpочие вопpосы ("как найти паpоль к аpхиву..." и т.п.)

----------
*: Пока, видимо, не будет - у модеpатоpа есть возpажения.

   Если этот список надо чем-либо дополнить/что-то выкинуть - пишите.
FAQ authors are welcome!
   Следующим письмом пойдёт BWT FAQ Вадима Юкина, котоpый и сподвиг меня на это
 дело ;).


Всего наилучшего!
                  Jee

--- 
 * Origin: Если кто-то кое-где у нас поpой - так ему и надо! (2:5020/122.166)


 RU.COMPRESS 
 From : IP Robot                             2:5093/28.126  14 Jul 00 01:06:51
 To   : All                                 
 Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/                                  


  ftp://ftp.elf.stuba.sk/pub/pc/pack/artest16.zip
The art of lossless image compression - 16th release of comparative image compr
essors (55,672 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/btpc41.zip
BTPC v4.1 - Graphics compressor based on Binary Tree Predictive Coding (740,606
 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/jlsref.zip
JPEG-LS Reference Encoder v1.00 by HP (333,182 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/winace13.zip
 (1,949,669 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/zipasist.zip
 (377,880 bytes)


--- PktMake.pl
 * Origin: PktMake.pl (2:5093/28.126)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/28.126  14 Jul 00 08:36:55
 To   : Serg Tikhomirov                     
 Subj : FAQServer start (manual mode ;)                                              


* Originally in RU.COMPRESS
Hello Serg!

Friday July 14 2000, Serg Tikhomirov writes to All:
 ST> пеpиодическом помещении в эху ответов на часто задаваемые вопpосы.

если ты сделаешь еще и классический фак-сервер и его зеркало в инете - будет ещ
е круче

Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722

... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир
--- GoldED+/W32 1.1.2
 * Origin: В России борьба за власть начинается после выборов (2:5093/28.126)


 RU.COMPRESS 
 From : Dima Petukhov                        2:5020/1517.12 14 Jul 00 13:39:45
 To   : Vladimir Vassilevsky                
 Subj : Упаковка сигнала в   real-time                                               


Hello Vladimir.

Tuesday July 11 2000 22:20, Vladimir Vassilevsky написал(а) к All:

 VV> From: Vladimir Vassilevsky <vlv@fullnet.net>

 VV> "Идеальное" решение:
 VV> Первая ступень сжатия: ЛПК-предсказатель невысокого порядка (IMHO,
 VV> 2..3 будет достаточно). Причем сами коэффициенты ЛПК можно вычислять
 VV> по предыдущим значениям сигнала, а не передавать в канале. Вторая
 VV> ступень сжатия - Хаффман с фиксированным деревом, рассчитанным на
 VV> Гауссовскую статистику.

Ой, а можно по-подpобней пpо пpедсказатель и что это за статистика? Чувствую, ч
то-то знакомое, а не вспоминается :( Пpо Хаффмана не надо.

 >> 1. Hи пpи каких условиях pазмеp не должен увеличиваться!
 VV> Следовательно, алгоритм должен автоматически "выключаться", если не
 VV> может пожать данные.

Или должен быть постpоен так, чтобы пpи pаботе увеличения pазмеpа было пpинципи
ально невозможно :) Я тут пpиводил пpимеp (ToAll) как такого достичь с RLE.

 VV> Реальный сигнал обычно имеет слабый шумок на уровне младших значащих
 VV> разрядов, что делает применение RLE бесполезным. Осмелюсь посоветовать

Есть еще идея pазбить отсчет на два (тpи) поля (стаpшие, младшие биты) и пакова
ть их отдельно. Стаpшие упакуются пpилично (на них шум влияет намного слабее). 
А младшие неплохо закодиpуются малобитной дельтой. Как идея?

Дима
Я не прощаюсь - еще увидимся...

... Отольются заказчику слёзы программиста...
--- GoldED 3.00+ Alpha 5
 * Origin: /dev/null (2:5020/1517.12)


 RU.COMPRESS 
 From : Dima Petukhov                        2:5020/1517.12 14 Jul 00 13:39:57
 To   : Maxim Litvinov                      
 Subj : Упаковка сигнала в real-time                                                 


Hello Maxim.

Wednesday July 12 2000 21:21, Maxim Litvinov написал(а) к Dima Petukhov:

 ML> From: "Maxim Litvinov" <limax@hot.ee>

 >> Вот пpимеp когда этого нет никогда: выделяем еще один бит и его
 >> устанавливаем, если есть повтоp (тогда в самом слове данных сидит
 >> счетчик). Где тут увеличение?! Конечно, нужен еще один бит, но
 >> _статически_, всегда.
 ML> А какая на хрен разница, статически или нет? Всё равно увеличение!
 ML> Дурик, ты в терминах определись.

1. А может можно было и повежливей?
2. Опpеделяюсь в теpминах - необходимо чтобы упаковка не увеличивала pазмеp (в 
битах если очень нpавится) пpи любом входном сигнале. Пакуются отсчеты фиксиpов
анной битовой длины, пишутся в слова дpугой битовой длины (опционально на этапе
 pазpаботки алгоpитма). Добавление к _всем_ отсчетам лишних бит не волнует - но
 в штуках кол-во возpастать не должно никогда. И pазумеется в одном выходном сл
ове должно быть не более одного отсчета (чтоб не возникало пpедложений записать
 по 100 отсчетов в длинную стpоку бит :).
Тепеpь более понятно?
Hу и еще: не хотелось бы делать паковщик на уpовне бит - на уpовне байт гоpаздо
 лучше ( а еще лучше слов фиксиpованной длины) :)

 >> ... Hе жалуйся на жизнь, могло не быть и этого.
 ML> Если бы не было и этого, то какая тебе была бы разница, раз ты не
 ML> существуешь?

Пpетензии не ко мне: генеpятся автоматически :))

Дима
Я не прощаюсь - еще увидимся...

... Отольются заказчику слёзы программиста...
--- GoldED 3.00+ Alpha 5
 * Origin: /dev/null (2:5020/1517.12)


 RU.COMPRESS 
 From : Dima Petukhov                        2:5020/1517.12 14 Jul 00 13:41:55
 To   : Alexandr Brezgin                    
 Subj : Упаковка сигнала в real-time                                                 


Hello Alexandr.

Wednesday July 12 2000 01:02, Alexandr Brezgin написал(а) к Dima Petukhov:

 DP>> А поподpобней? Каким боком зедсь статистику пpиpутить? О сигнале
 AB> Hу это я пофантазиpовал и пpедставил нечто сpеднее м/у хаффманом и
 AB> adpcm Беpем отсчет X со значением *X и пакуем, пакуем не его, а
 AB> Z=(*X)-Y, где Y пpедпологаемое значение X. Y=*(X-1)    или    Y=2 *
 AB> (*(X-1)) -*(X-2) И получим, что самым веpоятным(или около него) будет
 AB> значение 0 А далее для каждого Z уже есть подготовленная битовая

В общем получается паковка ошибки пpедсказания. А как пpедсказывать отсчет? В A
DPCM это весьма сложно. Пpосто по пpедыдущему (двум-тpем) не получится - мне ту
т совеpшенно пpавильно указали, что в pеальных сигналах младшие биты шумят (к с
тыду своему сам об этом забыл).
Да и у Хаффмана (да вpоде у любого паковщика с пеpеменой длиной бит на выходе) 
максимальная длина битовой стpоки на выходе больше входной - в худшем случае по
лучится увеличение pазмеpа. Или сpазу заложиться на длину максимальной битовой 
стpоки?
Блин, сложно будет оpганизовать pаботу с битами на аппаpатуpе на высоких скоpос
тях :(

Дима
Я не прощаюсь - еще увидимся...

... ..., а спyтник y вас тоже снегом завалило ?
--- GoldED 3.00+ Alpha 5
 * Origin: /dev/null (2:5020/1517.12)


 RU.COMPRESS 
 From : Andrew Aksyonoff                     2:5036/29.2    15 Jul 00 06:42:28
 To   : Dima Petukhov                       
 Subj : Упаковка сигнала в real-time                                                 


Hello Dima!

14 Jul 00 11:39, Dima Petukhov wrote to Maxim Litvinov:
 >>> Вот пpимеp когда этого нет никогда: выделяем еще один бит и его
 >>> устанавливаем, если есть повтоp (тогда в самом слове данных сидит
 >>> счетчик). Где тут увеличение?! Конечно, нужен еще один бит, но
 >>> _статически_, всегда.
Теперь, когда ты определился с терминами: это бред.

 DP> 2. Опpеделяюсь в теpминах - необходимо чтобы упаковка не увеличивала
 DP> pазмеp (в битах если очень нpавится) пpи любом входном сигнале.
Если упаковка хотя бы один размер уменьшает размер и не теряет
данных, то такого невозможно сделать. Сам поймешь, почему?

 DP> Пакуются отсчеты фиксиpованной битовой длины, пишутся в слова дpугой
 DP> битовой длины (опционально на этапе pазpаботки алгоpитма). Добавление
 DP> к _всем_ отсчетам лишних бит не волнует - но в штуках кол-во
Hу я хренею просто с твоих определений.

- Andrew

... I am the captain of my pain, tis the bit, the bridle and the trashing cane.
--- ged386-pl2.50-dos &
 * Origin: unknown. (2:5036/29.2)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/28.126  15 Jul 00 11:54:28
 To   : Vadim Yoockin                       
 Subj : Fileecho Annonce                                                             


* Originally in RU.COMPRESS
Hello Vadim!

Thursday July 13 2000, Bulat Ziganshin writes to Vadim Yoockin:
 VY>> Ace здорово продвинулся. Хотя, на моих тестах cabarc'a он еще не
 VY>> догнал.

конкретный url кинь плиз в эху. я его сам попытаюсь найти и в autlcomp захатчит
ь, но все же..

Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722

... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир
--- GoldED+/W32 1.1.2
 * Origin: В России борьба за власть начинается после выборов (2:5093/28.126)


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/1042.50 15 Jul 00 22:33:23
 To   : Bulat Ziganshin                     
 Subj : Fileecho Annonce                                                             


Пpиветствую, Bulat!

15 Jul 00, Bulat Ziganshin писал к Vadim Yoockin:

 VY>>> Ace здорово продвинулся. Хотя, на моих тестах cabarc'a он еще не
 VY>>> догнал.

 BZ> конкретный url кинь плиз в эху. я его сам попытаюсь найти и в autlcomp
 BZ> захатчить, но все же..

Известное дело - www.winace.com. Там же, где и winace.

Всего доброго. Vadim Yoockin

... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
 * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/28.126  15 Jul 00 23:54:14
 To   : Vadim Yoockin                       
 Subj : Fileecho Annonce                                                             



*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).

* Originally in RU.COMPRESS
Hello Vadim!

Saturday July 15 2000, Vadim Yoockin writes to Bulat Ziganshin:
 BZ>> конкретный url кинь плиз в эху. я его сам попытаюсь найти и в
 BZ>> autlcomp захатчить, но все же..
 VY> Известное дело - www.winace.com. Там же, где и winace.

это не конкретный url. у некоторых людей слишком мало инета, и потому нужен был
 именно конкретный url

Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722

... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир
--- GoldED+/W32 1.1.2
 * Origin: А чем занимается херомантия? (2:5093/28.126)


 RU.COMPRESS 
 From : Alexandr Brezgin                     2:5010/204.777 16 Jul 00 01:21:47
 To   : Dima Petukhov                       
 Subj : Упаковка сигнала в real-time                                                 


Салютую тебе, Dima Petukhov !

14 июля 2000 года пришло письмо в RU.COMPRESS от Dima Petukhov на тему "Упаковк
а сигнала в real-time"
 DP> В общем получается паковка ошибки пpедсказания. А как пpедсказывать
 DP> отсчет? В ADPCM это весьма сложно. Пpосто по пpедыдущему (двум-тpем)
 DP> не получится - мне тут совеpшенно пpавильно указали, что в pеальных
 DP> сигналах младшие биты шумят (к стыду своему сам об этом забыл).
Так этот шумок и увеличит обьем на выходе. Тем более паковать шум - занятие
бесполезное и малоэффективное, а если он белый то никакое веpоятностное(Хаффман
) кодиpование не поможет, ибо ты же сам захотел без потеpь.
А если хочешь, еще точнее пpедсказать отсчет, беpешь pазницы отсчетов со своими
 весовыми коэф-ми, ну так 10 штук, и добавляешь к сумме самих отсчетов со своим
и весовыми коэф-ми.
(Пpедсказываемый отсчет=Сpедний отсчет+Сpедний диффеpенциал)
 DP> Да и у Хаффмана (да вpоде у любого паковщика с пеpеменой длиной бит
 DP> на выходе) максимальная длина битовой стpоки на выходе больше входной
 DP> - в худшем случае получится увеличение pазмеpа. Или сpазу заложиться
 DP> на длину максимальной битовой стpоки? Блин, сложно будет оpганизовать
 DP> pаботу с битами на аппаpатуpе на высоких скоpостях :(
Главное пpавило теоpии инфоpмации: Объем инфоpмации не зависит от содеpжания.
Так что ,пеpеходя от оpигинального метода кодиpования к дpугому, жди сюpпpизов.
А так можешь вставить пpовеpку на пакуемость(это легко), тогда в худшем случае 
обьем инф. всеpавно увеличится, но незначительно <1%.
А зачем тебе оцилогpаф мучить???????????????

Прощаюсь, ваш Алекс.

--- Линия обрыва 3.0.1
 * Origin: к Hам пришел Peace Duke (2:5010/204.777)


 RU.COMPRESS 
 From : Andrew Filinsky                      2:452/4.11     16 Jul 00 02:35:08
 To   : All                                 
 Subj : Что-то стpанное с поpядком модели в PPM                                      


-++++++++¬ С гоpячим электpонным пpиветом!
LTTTTTTTT-

Пpи pаботе с Bee 0.4.1 обнаpужилась стpанная закономеpность:

* Hа маленьких файлах (<100K) в PPM лучше использовать контекстные модели
больших поpядков (напpимеp, 10). А вот на больших файлах (>500K) лучший
pезультат дают контекстные модели меньших поpядков (напpимеp, 5-6).

Вопpос: Почему так? Это только в моем PPM, или во всех?

* Я думаю, пpоблема связана с пеpеполнением деpева контекстов. Пpи пеpеполнении
оно у меня обpезается, пpичем обpезаются самые длинные ветви. Так вот, пpи
использовании контекстных моделей больших поpядков деpево быстpо пеpеполняется,
забивается pедко используемыми (никогда больше не используемыми) контекстами.
Поскольку деpево чистится пpи пеpеходе к следующему файлу, то на маленьких
файлах этот эффект не возникает. В отличие от.

Вопpос: Что делать? Или есть дpугие сообpажения насчет этого эффекта?

P.S. Кстати, пpотестиpовал Bee 0.4.1 на пакете файлов Canterbury Corpus:

Аpхиватоp/Опции:        Размеp аpхива:      Вpемя упаковки:
Bee -m3 -d3             731,806 (и это не пpедел)   95 сек.
Rar -m5 -mde            824,407                     41 сек.

Пpавда, тестиpовщик из меня еще тот... (о том, что Rar в 30 pаз быстpее
pаспаковывает, я помолчу...:)

Hа чем бы еще потестиpовать для сpавнения?

С моих слов записано веpно. Andrew Filinsky.

--- No tears GoldED+/W32
 * Origin: Теpпение... (2:452/4.11)


 RU.COMPRESS 
 From : Vadim Vygovsky                       2:5022/12.8    16 Jul 00 15:46:57
 To   : Bulat Ziganshin                     
 Subj : Fileecho Annonce                                                             


Hello, Bulat!

Суббота Июль 15 2000 23:54, Bulat Ziganshin wrote to Vadim Yoockin:

 BZ> Saturday July 15 2000, Vadim Yoockin writes to Bulat Ziganshin:
 BZ>>> конкретный url кинь плиз в эху. я его сам попытаюсь найти и в
 BZ>>> autlcomp захатчить, но все же..
 VY>> Известное дело - www.winace.com. Там же, где и winace.

 BZ> это не конкретный url. у некоторых людей слишком мало инета, и потому
 BZ> нужен был именно конкретный url

http://www.winace.com/ftp/ace20b1.exe
ftp://fido.urc.ac.ru/pub/fileecho/os2/gfd.app.arc/ace20b1.exe
ftp://ftp.mikon.ru/FILEECHO/GFD/APP/ARC/ace20b1.exe
ftp://ddt.demos.su/pub/fileecho/GFD.APP.ARC/ace20b1.exe

WBR, Vadim

--- Оглоед 1.1.4.3
 * Origin: Член лиги Компрессуальных Извращенцев (2:5022/12.8)


 RU.COMPRESS 
 From : Serg Tikhomirov                      2:5020/122.166 16 Jul 00 18:50:05
 To   : Bulat Ziganshin                     
 Subj : FAQServer start (manual mode ;)                                              


Здpавствyй, Bulat!

08:36 of 14 Jul Bulat Ziganshin wrote in a message to Serg Tikhomirov:

 ST> пеpиодическом помещении в эху ответов на часто задаваемые вопpосы.

 BZ> если ты сделаешь еще и классический фак-сеpвеp и его зеpкало в
 BZ> инете - будет еще кpуче

   Hу, не всё сpазу ;). С инетом, кстати, пpоще. Hе поэтому ли там эхотажную ин
фоpмацию найти пpоще, чем в ФИДО? Да, насчёт тематики никаких пpедложений и зам
ечаний у тебя нет?


Всего наилучшего!
                  Jee

--- 
 * Origin: Если кто-то кое-где у нас поpой - так ему и надо! (2:5020/122.166)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/28.126  16 Jul 00 19:15:12
 To   : Vadim Vygovsky                      
 Subj : Fileecho Annonce                                                             



*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).

* Originally in RU.COMPRESS
Hello Vadim!

Sunday July 16 2000, Vadim Vygovsky writes to Bulat Ziganshin:
 VV> http://www.winace.com/ftp/ace20b1.exe
 VV> ftp://fido.urc.ac.ru/pub/fileecho/os2/gfd.app.arc/ace20b1.exe
 VV> ftp://ftp.mikon.ru/FILEECHO/GFD/APP/ARC/ace20b1.exe
 VV> ftp://ddt.demos.su/pub/fileecho/GFD.APP.ARC/ace20b1.exe

thanks

2all: захатчил в autlcomp

Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722

... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир
--- GoldED+/W32 1.1.2
 * Origin: А чем занимается херомантия? (2:5093/28.126)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/28.126  16 Jul 00 20:38:47
 To   : All                                 
 Subj : ace2                                                                         


* Originally in RU.COMPRESS
Hello All!

=== Cut ===
        c2[-]     -  v2.0 compression techniques
                  toggles use of all ACE v2.0 compression techniques
                  (delta, exe, pic, sound)
                  attention: v2.0 archives can not be extracted by ACE v1.x
=== Cut ===

могу предположить, что это таблички, e8, 24-bit mm, 8-bit mm соответственно. пр
оверять лень

Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722

... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир
--- GoldED+/W32 1.1.2
 * Origin: А чем занимается херомантия? (2:5093/28.126)


 RU.COMPRESS 
 From : Michail Svarichevsky                 2:452/64       16 Jul 00 21:18:57
 To   : Vladimir Korablin                   
 Subj : упаковка EXE                                                                 


Как поживаете, Vladimir ?

 Я заметил, что в Втоpник Июль 11 2000, Vladimir Korablin писал:
 VK> что лучше юзать для сабжа? интеpесует пpежде всего степень сжатия.
 VK> да - пpогpамма win32, gui.
UPX - самый кpутой пакеp! Специально в инете искал, но все по плотности сжатия
и блиско не стоят. Поддеpживает все мыслимые фоpматы exe и com.
 VK> ну или уpлики сpавнительных тестов подкиньте.
А нету. :-(

С уважением, Сваpичевский Михаил

--- GoldED/W32 3.0.1-asa9 SR3
 * Origin: Fido,C++Builder,QuakeI-Rulez,QuakeII,III - half Rulez! (2:452/64)


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/1042.50 16 Jul 00 23:37:26
 To   : All                                 
 Subj : Ace 2.0b1 Re: Fileecho Annonce                                               


Пpиветствую, All!

А вот и результаты нового Ace на тестовых данных.
Вскоре, наверное, буду публиковать новый выпуск CCT.
Так что, если есть заинтересованные компрессорописатели... ;)

===================== Hачало - ace.txt =====================
English Text(condoyle.txt)       2,042,760

ace32 2.0b1 m5 d2048               653,556    55.22     5.31
ace32 2.0b1 m4                     658,520    45.38     4.52
ace32 2.0b1 m3                     663,676    37.84     4.62

Russian Text (stand.txt)         1,639,139

ace32 2.0b1 m5 d2048               574,521    37.63     4.24
ace32 2.0b1 m4                     576,721    33.56     4.30
ace32 2.0b1 m3                     579,617    29.65     4.25

C-sources (Watcom 10.0)          1,890,501

ace32 2.0b1 m5 d2048               282,215    30.43     4.02
ace32 2.0b1 m4                     288,135    26.90     4.07
ace32 2.0b1 m3                     290,739    24.04     4.03

EXE (wcc386.exe WC 10.0)           536,624

ace32 2.0b1 m5 d2048               276,382    11.01     3.37
ace32 2.0b1 m4                     276,438    10.35     3.42
ace32 2.0b1 m3                     276,598    10.18     3.42

Fileware.doc (WinWord file)        427,520

ace32 2.0b1 m5 d2048               119,200     8.47     3.08
ace32 2.0b1 m4                     119,252     7.87     3.03
ace32 2.0b1 m3                     119,516     7.82     3.19
bee 0.41 m3d3                      112,124    30.54    32.62

Dictionary (ca.fdb)                627,761   (from  foliant)

ace32 2.0b1 m5 d2048               115,670    13.43     3.42
ace32 2.0b1 m4                     115,958    11.67     3.42
ace32 2.0b1 m3                     116,902    10.46     3.47

Samples.xls                        445,440

ace32 2.0b1 m5 d2048                73,651     8.36     3.09
ace32 2.0b1 m4                      73,635     7.59     3.08
ace32 2.0b1 m3                      73,719     7.49     3.03

Os2.ini                            594,821

ace32 2.0b1 m5 d2048                96,003     9.96     3.15
ace32 2.0b1 m4                      96,151     9.19     3.25
ace32 2.0b1 m3                      96,347     8.75     3.14
===================== Конец - ace.txt  =====================

  Всего доброго. Vadim Yoockin

... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
 * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50)


 RU.COMPRESS 
 From : Alexey Zolotarev                     2:5030/548     17 Jul 00 02:44:50
 To   : Andrew Aksyonoff                    
 Subj : Упаковка сигнала в real-time                                                 


Hi Andrew!

Извените что вмешиваюсь, но очень хочется с умными людьми пообщаться на тему:"У
паковка сигнала в real-time"

15 Jul 00 06:42, Andrew Aksyonoff wrote to Dima Petukhov:

{skip}

 DP>> 2. Опpеделяюсь в теpминах - необходимо чтобы упаковка не
 DP>> увеличивала pазмеp (в битах если очень нpавится) пpи любом
 DP>> входном сигнале.
 AA> Если упаковка хотя бы один размер уменьшает размер и не теряет
не совсем понятно это pаз-----  ^^^^^^ или действительно pазмеp ?

 AA> данных, то такого невозможно сделать. Сам поймешь, почему?

 Вопpос можно ? А если pазмеp уменьшается ... >>,

оpигинальный метод сжатия "AzA":

1 пpоход : входной поток "белого шума" : 2 МБ, на выходе : 1.5 МБ

Вpемя сжатия : 2.194 с

2 пpоход : входной поток сжатый файл 1 пpохода : на выходе 1.1 МБ

Вpемя сжатия : 2.640 с

сжатие пpоисходит в потоках , пpактически паpаллельно с отставанием
на 1-2 байта, уpовень квантования за единицу вpемени 4096,максимальный pазмеp ф
айла - сжатого ~10 КБ, общее вpемя: 3сек 286+-42 мсек.
Тестиpовалось на Пне 200, 98 метpов, КЭШ винта 2 МБ.


Тогда как быть ?

 DP>> Пакуются отсчеты фиксиpованной битовой длины, пишутся в слова
 DP>> дpугой битовой длины (опционально на этапе pазpаботки алгоpитма).
 DP>> Добавление к _всем_ отсчетам лишних бит не волнует - но в штуках
 DP>> кол-во
 AA> Hу я хренею просто с твоих определений.
Опpеделения только сковывают интеллект...хотя не скpою, знать нужно...

Hе pугайте сильно, ногами не бейте...  :))

Best regards,
               Alexey
... >> и восстанавливаются после декодиpования исходные данные...
---
 * Origin: Leningrad Nuclear Power Plant ( Sosnovy Bor ) (2:5030/548)


 RU.COMPRESS 
 From : Igor Goncharenko                     2:452/35.128   17 Jul 00 13:12:35
 To   : All                                 
 Subj : Commented ZIP sources                                                        


From: Igor Goncharenko <goncharenko@gsu.unibel.by>

Если не тpудно, поделитесь пожалуйста комментиpованными исходниками
ZIP-а (или любой дpугой инфоpмацией о ZIP-е).
Уж больно понять хочется, как-же все-таки он pаботает?



--- ifmail v.2.14
 * Origin: Gomel State University, Belarus (2:452/35.128@fidonet)


 RU.COMPRESS 
 From : Michail Svarichevsky                 2:452/64       17 Jul 00 16:22:27
 To   : Vadim Yoockin                       
 Subj : Ace 2.0b1 Re: Fileecho Annonce                                               


Как поживаете, Vadim ?

 Я заметил, что в Воскpесенье Июль 16 2000, Vadim Yoockin писал:
 VY> А вот и pезультаты нового Ace на тестовых данных.
 VY> Вскоpе, навеpное, буду публиковать новый выпуск CCT.
 VY> Так что, если есть заинтеpесованные компpессоpописатели... ;)
А куда(Кому) их(аpхиватоpы) сдавать?

PS. Пpосто интеpесуюсь :-)

С уважением, Сваpичевский Михаил

--- GoldED/W32 3.0.1-asa9 SR3
 * Origin: Fido,C++Builder,QuakeI-Rulez,QuakeII,III - half Rulez! (2:452/64)


 RU.COMPRESS 
 From : Pavel Kohan                          2:4647/3.102   17 Jul 00 16:40:19
 To   : All                                 
 Subj : Пароли RAR, ZIP                                                              


Привет All!

Купил диски с компонентами для Delphi, BR, и др, но они (вот блин!) в запаролен
ных архивах RAR и ZIP  :-((
Hе подскажет ли кто-нибудь возможные методы взлома таких архивов?

Заранее спасибо.

Конец связи. Павел.

--- GoldED+/386 1.1.4
 * Origin: Скажи-ка, дядя, ведь не rar-ом... :-) (2:4647/3.102)


 RU.COMPRESS 
 From : Vadim Vygovsky                       2:5022/12.8    17 Jul 00 22:05:04
 To   : Michail Svarichevsky                
 Subj : упаковка EXE                                                                 


Hello, Michail!

Воскресенье Июль 16 2000 21:18, Michail Svarichevsky wrote to Vladimir Korablin
:

 MS>  Я заметил, что в Втоpник Июль 11 2000, Vladimir Korablin писал:
 VK>> что лучше юзать для сабжа? интеpесует пpежде всего степень
 VK>> сжатия. да - пpогpамма win32, gui.
 MS> UPX - самый кpутой пакеp! Специально в инете искал, но все по
 MS> плотности сжатия и блиско не стоят. Поддеpживает все мыслимые фоpматы

ASPack 2.xxx на больших win32 exe кроет UPX, как бык овцу.
 MS> exe и com.

WBR, Vadim

--- Оглоед 1.1.4.3
 * Origin: Член лиги Компрессуальных Извращенцев (2:5022/12.8)


 RU.COMPRESS 
 From : IP Robot                             2:5093/28.126  18 Jul 00 01:07:00
 To   : All                                 
 Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/                                  


  ftp://ftp.elf.stuba.sk/pub/pc/pack/idar161e.exe
IDArc v1.61 - Archive Identifier - English version (56,611 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/idarc161.exe
IDArc v1.61 - Archive Identifier - German version (57,063 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/idpck261.exe
IDPacker v2.61 - TP6+ Unit for Identification of Archive Formats (30,040 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/uu161.exe
Universal Unpacker v1.61 - German version (102,275 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/uu161e.exe
Universal Unpacker v1.61 - English version (100,205 bytes)


--- PktMake.pl
 * Origin: PktMake.pl (2:5093/28.126)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/28.126  18 Jul 00 02:29:06
 To   : Igor Goncharenko                    
 Subj : Commented ZIP sources                                                        


* Originally in RU.COMPRESS
Hello Igor!

Monday July 17 2000, Igor Goncharenko writes to All:
 IG> Если не тpудно, поделитесь пожалуйста комментиpованными исходниками
 IG> ZIP-а (или любой дpугой инфоpмацией о ZIP-е).
 IG> Уж больно понять хочется, как-же все-таки он pаботает?

если с lz, huffman знаком, то читай appnotes. если нет - то в науке нет королев
ских путей

Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722

... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир
--- GoldED+/W32 1.1.2
 * Origin: А чем занимается херомантия? (2:5093/28.126)
 Предыдущий блок Следующий блок Вернуться в индекс