Предыдущий блок Следующий блок Вернуться в индекс
 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/4.126   24 Oct 01 12:40:28
 To   : Sergey Tchirco                      
 Subj : Hа: И снова Huffman. И ничего смешного :-(                                   


* Originally in RU.COMPRESS
Приятного тебе дня и незабываемой ночи, Sergey!

Wednesday October 24 2001, Sergey Tchirco writes to EinWill:
 >> > А вообще посмотри, что рекомендует Булат.
 >> А что он рекомендует? Я недавно подписан на эту эхоконференцию..
 ST> Так вчера пролетало: bzip2 и readme к pkzip

ar002/zip :)))  bzip2 никакого отношения к lzh не имеет!

Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722

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


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/1042.50 24 Oct 01 13:08:33
 To   : EinWill                             
 Subj : Re: RANGECODER                                                               


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

Hello, EinWill!
You wrote to Bulat Ziganshin on Wed, 24 Oct 2001 06:01:06 +0000 (UTC):

 E> А где об этом RangeCoder'е можно почитать?

http://www.pilabs.org.ua/sh/
http://www.arturocampos.com

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

--- ifmail v.2.15dev5
 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400)


 RU.COMPRESS 
 From : EinWill                              2:5020/400     24 Oct 01 14:20:57
 To   : Sergey Tchirco                      
 Subj : Re: И снова Huffman. И ничего смешного :-(                                   


From: "EinWill" <andrey@neva-roentgen.com>
Reply-To: "EinWill" <andrey@neva-roentgen.com>

Мы к Вам, профессор "Sergey Tchirco" <tchsv@nbrt.kazan.su>, и вот по какому
делу:


> Да, твой вариант дает теоритически несколько лучшую картину, чем
стандартный
> Huffman, но на практике - увы ;(  Вероятность того, что у нескольких узлов
> будут равные вероятности, на сколько нибудь больших  данных ничтожно мала
:(
1) Оптимизация будет если равны не только частоты вхождения, но и те
комбинации их сумм, которые мы получаем при построении дерева Huffman'а.
Последнее, уже на порядок вероятнее... Хотя в чем-то ты прав %-(

2) Hу, это смотря что за данные. В текстовый файле их предостаточно %-)

3) Приятно быть уверенным, что глубина построенного дерева -- минимальна. И
если уж длина кодов вылезла за 32 бита, то значит судьба. Тут уже не
поделаешь, я со своей стороны сделал все что мог etc...

> > М-м-м. Тут не в скорости дело. Я же не кодер пишу. У меня эти, сжимаемые
> > данные предварительно сравнительно долго вычисляются... Дело
исключительно
> > в эстетической красоте кода :-) Hу и плюс здоровый научный инетерес.

> А эстетическая красота достигается вызовом одной, максимум двух функций из
> готовой(!) протестированной(!) и оптимизированной(!) библиотеки,
Таки оно ровно так и есть :-)
Только реализация этих готовых (!) протестированных (!) и ... м-м-м... и
просто библиотеки -- меня не устравивает :-)

> уже написанной за тебя. Программист должен быть ленивым!
Программист должен быть умным. А ленивый он или нет -- это детали. У меня
есть ряд причин, по которым разумнее реализовать алгоритм самому.

> если взять тотже RangeCoder, результать скорее всего получше будет.
Это то, проверкой чего я займусь в ближайшее время :)

С уважением,
--- ifmail v.2.15dev5
 * Origin: Fidolook Express 2.000  www.fidolook.da.ru (2:5020/400)


 RU.COMPRESS 
 From : Maxim Smirnov                        2:5020/400     24 Oct 01 17:29:25
 To   : Bulat Ziganshin                     
 Subj : RANGECODER                                                                   


From: "Maxim Smirnov" <model@iac.spb.ru>

Hi Bulat,

Wed Oct 24 2001 12:36, Bulat Ziganshin wrote to Einwill:

 BZ> * Originally in RU.COMPRESS
 BZ> Приятного тебе дня и незабываемой ночи, Einwill!

 BZ> Wednesday October 24 2001, EinWill writes to Bulat Ziganshin:

 E>> А где об этом RangeCoder'е можно почитать?

 BZ> нигде. но можно взять его исходники :))

Hикогда не говори "никогда" :-)

http://www.pilabs.org.ua/sh/downl_e.htm
http://www.compressconsult.com/rangecoder/
Hу, придется еще приложить кой-какую смекалку, конечно.

2Shelwien: чуешь, какой промоушен я тебе делаю? ;-)

Maxim

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)


 RU.COMPRESS 
 From : Dmitry Shkarin                       2:5020/400     24 Oct 01 18:54:44
 To   : Andrew Gorbunow                     
 Subj : Re: PPMDH                                                                    


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

                    Hi, Andrew!
> Допyстим я сжал файл file.txt PPMonstr-ом (ver.H):
> *ppmonstr e -o16 -m108 file.txt*
> Бyдет ли он ноpмально извлечен y юзеpа с 32Mb ОЗУ (т.е. меньше чем 108)???
    Алгоритм симметричен - памяти при распаковке требуется столько-же как и
при упаковке. Так чтааа... посвопится пару часов - и извлекется ;-).




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


 RU.COMPRESS 
 From : Eugene D. Shelwien                   2:5020/400     25 Oct 01 03:43:52
 To   : Maxim Smirnov                       
 Subj : Re: RANGECODER                                                               


From: "Eugene D. Shelwien" <shelwien@thermosyn.com>
Reply-To: shelwien@thermosyn.com

Hi!

Maxim Smirnov wrote:
>  E>> А где об этом RangeCoder'е можно почитать?
> 
>  BZ> нигде. но можно взять его исходники :))
> 
> Hикогда не говори "никогда" :-)

Это http://www.pilabs.org.ua/sh/ark2.zip имелось в виду,
очевидно?
 
> http://www.pilabs.org.ua/sh/downl_e.htm
> http://www.compressconsult.com/rangecoder/
> Hу, придется еще приложить кой-какую смекалку, конечно.

"Родной" шиндлеровский rangecoder народу не нужен! ;)
У него перенос в старшем бите low хранится, поэтому
в декодере приходится вдвигать в low данные со сдвигом
на бит. Так что если уж смотреть, так на shindler.inc
в http://www.pilabs.org.ua/sh/aridemo6.zip - там почти
все, как в оригинале, только перенос в отдельном регистре.

> 2Shelwien: чуешь, какой промоушен я тебе делаю? ;-)

После того, как Дима меня в comp.compression рекламировал,
это уже непринципиально ;)
 
> Maxim

Хотя, впрочем, собрался я, наконец, с силами, и выложил
на сайт последние версии кодеров (те, что мылом рассылал)
http://www.pilabs.org.ua/sh/coders6a.zip
Hа новый релиз aridemo, увы, собранных сил не хватило ;)
(Хотя есть, что добавить. Ту же модель Микаэля Лундквиста,
хотя бы. http://www.geocities.com/mikaellq/range.tgz )

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Словарь Даля     17,390,634
AriDemo Model:   o0c_v2a.inc
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

             CodeSize   C-Time   D-Time

CL-D       10,680,328    9.66    11.47
CL-R       10,680,668    5.55     7.08
CL-Rf      10,680,351    5.44     6.70
CL-Rfm     10,680,327    6.86     8.62
Subbotin   10,682,917    5.55     6.92
Subb-LB    10,682,917    5.55     6.97
Shindlet   10,680,348    5.77     6.48
Shcoder    10,680,642    6.97     8.34
Ari        10,680,318   12.47    14.06

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

CL-D       

   Dword-ориентированный rangecoder,
FPU'шная реализация. Low, Range - 
64-хбитные, MaxFreq = 2^31.
   Давно не carryless, т.к. первоначальный
вариант глючил ;).

Subbotin

   Субботинский кодер, без модификаций.
MaxFreq = 2^16.

Subb-LB

   Вариант Леонида Брухиса. 

CL-R       

   Альтернативная реализация субботинского
варианта carryless'ности. Упрощены проверки
и поднят MaxFreq, но ренормализации происходят
чаще. MaxFreq = 2^24.

CL-Rf

   Carryless по новому методу, меньше тормозящему
декодирование. При обнаружении возможности
переноса range обнуляется - что не требует вычисления
low в декодере. MaxFreq = 2^24

CL-Rfm

   Версия с умножением/делением через 64 бита.

Shindlet

   Оптимизированный вариант шиндлеровского
rangecoder'а. MaxFreq = 2^24

Shcoder

   Первый вариант "шиндлеровского" кодера
из aridemo с умножением/делением через 64 бита.
MaxFreq = 2^24.

Ari

   Традиционный арифметический кодер, версия
Андрея Филинского. Умножение/деление 
через 64 бита ;).
   MaxFreq = 2^31

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Счастливо!
 - Шелвин
--- ifmail v.2.15dev5
 * Origin: Shadow Research Center (2:5020/400)


 RU.COMPRESS 
 From : Maxim Smirnov                        2:5020/400     25 Oct 01 09:46:31
 To   : Eugene D. Shelwien                  
 Subj : RANGECODER                                                                   


From: "Maxim Smirnov" <model@iac.spb.ru>

Hi Eugene,

 EDS> Это http://www.pilabs.org.ua/sh/ark2.zip имелось в виду,
 EDS> очевидно?

очевидно

 EDS> "Родной" шиндлеровский rangecoder народу не нужен! ;)
 EDS> У него перенос в старшем бите low хранится, поэтому
 EDS> в декодере приходится вдвигать в low данные со сдвигом
 EDS> на бит. 

ну и что? советскому человеку не привыкать...

 EDS> Хотя, впрочем, собрался я, наконец, с силами, и выложил
 EDS> на сайт последние версии кодеров (те, что мылом рассылал)
 EDS> http://www.pilabs.org.ua/sh/coders6a.zip

оно тут и будет лежать?

 EDS> Hа новый релиз aridemo, увы, собранных сил не хватило ;)
 EDS> (Хотя есть, что добавить. Ту же модель Микаэля Лундквиста,
 EDS> хотя бы. http://www.geocities.com/mikaellq/range.tgz )

угу. Хотя я еще не смотрел.

[skip]
 EDS> Shcoder
 EDS>    Первый вариант "шиндлеровского" кодера
 EDS> из aridemo с умножением/делением через 64 бита.
 EDS> MaxFreq = 2^24.
 EDS> Ari
 EDS>    Традиционный арифметический кодер, версия
 EDS> Андрея Филинского. Умножение/деление 
 EDS> через 64 бита ;).
 EDS>    MaxFreq = 2^31

Замечу, кстати, что для нужд Calgary Challenge был в конечном
итоге использован кодер, выдранный из CM Булата Зиганшина.
По интегральной эффективности -- размер сжатых файлов + размер
декодера -- он обошел лучший из твоих то ли 10, то ли на 13 
байтов %-)

Maxim

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/4.126   25 Oct 01 10:50:08
 To   : Maxim Smirnov                       
 Subj : RANGECODER                                                                   


* Originally in RU.COMPRESS
Приятного тебе дня и незабываемой ночи, Maxim!

Thursday October 25 2001, Maxim Smirnov writes to Eugene D. Shelwien:
 MS> итоге использован кодер, выдранный из CM Булата Зиганшина.
 MS> По интегральной эффективности -- размер сжатых файлов + размер
 MS> декодера -- он обошел лучший из твоих то ли 10, то ли на 13
 MS> байтов %-)

а там не было написано откуда он? уж сам я точно такие штучки делать не умею :)
))

Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722

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


 RU.COMPRESS 
 From : Maxim Smirnov                        2:5020/400     25 Oct 01 12:11:20
 To   : Bulat Ziganshin                     
 Subj : RANGECODER                                                                   


From: "Maxim Smirnov" <model@iac.spb.ru>

Thu Oct 25 2001 10:50, Bulat Ziganshin wrote to Maxim Smirnov:
 MS>> итоге использован кодер, выдранный из CM Булата Зиганшина.
 MS>> По интегральной эффективности -- размер сжатых файлов + размер
 MS>> декодера -- он обошел лучший из твоих то ли 10, то ли на 13
 MS>> байтов %-)

 BZ> а там не было написано откуда он? уж сам я точно такие штучки делать не
 BZ> умею :)))

static char copyright[]="arith.c 1.0 (c) 1997 michael@eiunix.tuwien.ac.at"

Для моей модели он даже дает чуть лучшее сжатие (байт эдак на 5 %-) ),
чем стандартный арифметик, украденный из HA, украденный из...

Maxim

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)


 RU.COMPRESS 
 From : Sasha Breger                         2:5066/70.64   25 Oct 01 15:06:58
 To   : Bulat Ziganshin                     
 Subj : Сжатие строк (до 250 символов)                                               


Привет, Bulat.

Вторник Октябрь 23 2001 14:47, Bulat Ziganshin писал Sasha Breger:

 SB>> Чем/как лучше всего сжимать не очень большие строки? Чем можно
 SB>> получить максимальное сжатие (с учётом заголовков)?
 BZ> опиши целиком систему.

Есть строки от 20 до примерно 300 символов. Сейчас в ascii, но потом может быть
 и utf-16. Hадо маскимально сжать эти строки.

 BZ> пока ответ отрицательный, ведь программа тоже место занимает ;)

? Какая программа?

 Sasha, <no@e-mail.smth>
--- ГолДед+1.1.4.7
 * Origin: Где вы были с восьми до одиннадцати? (2:5066/70.64)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/4.126   25 Oct 01 20:26:47
 To   : Sasha Breger                        
 Subj : Сжатие строк (до 250 символов)                                               


* Originally in RU.COMPRESS
Приятного тебе дня и незабываемой ночи, Sasha!

Thursday October 25 2001, Sasha Breger writes to Bulat Ziganshin:
 SB> Есть строки от 20 до примерно 300 символов. Сейчас в ascii, но потом
 SB> может быть и utf-16. Hадо маскимально сжать эти строки.

дай штук 50 таких строк. а лучше скажи - что это? сообщения вв порграмме? русск
ие/...?

Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722

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


 RU.COMPRESS 
 From : Serg Tikhomirov                      2:5020/122.166 25 Oct 01 23:52:05
 To   : Lev Serebryakov                     
 Subj : Huffman                                                                      


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

03:18 of 19 Oct Lev Serebryakov wrote in a message to Serg Tikhomirov:

 LS> [Answer on] [Serg Tikhomirov wrote to Lev Serebryakov at [05 Oct 01
 LS> 13:55]]: 

 ST>    И под это есть - но поскольку сам я с ним не pаботаю, то и не знаю,
 ST> под какие платфоpмы он написан (кстати, это навеpняка описано в доке в
 ST> аpхиве RAR29LNX.TGZ, живущем на ftp://ftp.elf.stuba.sk/pub/pc/pack).
 ST> Там же живут как минимум UNRAR-ы для ATARI, Solaris 7, AIX,... и
 ST> исходники оного.
 LS>   _UN_rar.

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

 LS>> P.S. InfoZIP как альтеpнативу я бы еще понял...
 ST>    ZIP в пpинципе не может быть альтеpнативой RAR-у, как Лексикон
 ST> 6.51 не может быть альтеpнативой PAGEMAKER-у ;-). Слишком велика
 ST> pазница в классе пpодуктов.
 LS>    Вот только zip легален и пеpеносим, а rar нет...

   Вот только качество сжатия и сеpвиса у ZIP-а существенно ниже... 

 ST> Однако, дабы не уйти в оффтопик, посмотpим лишь на pезультаты
 ST> _сжатия_ тестовых пpимеpов:

 ST> TAR 3.21g -cve9f               20.73   5.39  1,576,960
 LS>   что вот это такое, и где bzip2?!
 LS>   Вот pусский текст:

 LS> ORIGINAL:       dird.txt      737463, 00.00 sec
 LS> rar32 -mdE -m5: dird.rar      284399, 20.01 sec
 LS> bzip2 -9        dird.txt.bz2  243874,  3.3  sec

   Цифpа в 20 секунд на сжатие 700 кб текста кажется несколько завышенной...

 LS>    АГА?! И bzip2 есть _подо_все_ платфоpмы, бесплатен и легален. 

   Hе знаю, где ты видел его _подо_все_ платфоpмы, на стубе лежат ваpианты под 
ДОС, винды и полуось. Hи Мака, ни Атаpи, ни Аикса... Хоть пиши сам (как и в слу
чае с RAR-ом ;). Кpоме того, bzip2 - только _компpессоp_. Обслуживание аpхивов 
у него отсутствует как класс.

 ST>    Помимо собственно степени сжатия, где выигpыш составляет (на
 ST> пpедставленных пpимеpах) ~10 - 30%, есть и дpугие аспекты, имеющие
 ST> мало отношения к тематике конфеpенции. Hапpимеp, защита аpхивов от
 ST> повpеждений, кою осуществляет RAR, и не осуществляет ZIP. Вопpосы

 ST> ;). А Gzip вообще не умеет pазбивать аpхивы на тома...
 LS>   А это -- тpетья пpогpамма, split называется. Зачем _компpессоpу_
 LS> уметь pазбивать что-то на тома?! Это должен уметь pазбиватель на
 LS> тома!   Когда у тебя есть много маленьких пpогpамм, каждая из
 LS> котоpых умеет что-то одно, ты можешь постpоить ЛЮБУЮ констpукцию. А
 LS> вот когда у тебя есть одна пpогpамма, котоpая пытается уметь все...
 LS> УВЫ, часто этого ``ВСЕГО'' не хватает. 

   Я уже описывал _свой_ путь к пониманию этой пpоблемы. _Мне_ неудобно для мно
гокpатного выполнения одних и тех же действий по обслуживанию аpхива пользовать
ся двумя, тpемя а то и четыpьмя пpогpаммами (Join какой-нибудь в паpу к Split-у
). Более того, я и сам писал все эти пpогpаммки-кубики, из котоpых можно стpоит
ь _любую_ (?) констpукцию. Когда число этих пpогpаммок достигло некоего локальн
ого максимума, я начал забывать, делал я такую пpогpаммку или нет и как она наз
ывается. Поскольку писалось всё это для себя, то не было и нужды в доках "для ч
айников", был только встpоенный хелп...
   Коpоче говоpя, я пpишёл к выводу, что для весьма обшиpного и часто повтоpяем
ого набоpа действий над pазнообpазными аpхивами удобнее пользоваться  унивеpсал
ьным аpхиватоpом, чем целой коллекцией отдельных пpогpамм. Тот же RAR даёт в эт
ом плане кучу возможностей.
   Кстати, мне кажется, мы всё больше уклоняемся от эхотага. Пpедлагаю pазвёpну
тые дискуссии (если будет желание) пpоводить в мыле.


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

--- 
 * Origin: Весь миp - банкет, а люди в нём - обжоpы. (2:5020/122.166)


 RU.COMPRESS 
 From : Alexey Danov                         2:5020/400     26 Oct 01 09:15:54
 To   : All                                 
 Subj : Требуется сжать массив строк                                                 


From: "Alexey Danov" <arit@arh.ru>

I. Конктретно -  список фамилий (имен / отчеств).

Очевидно, что:
1. Букв 32 (без йо)
2. Фамилии на Ь, Ы и Ъ не начинаются
3. Фамилии очень часто заканчиваются
   на ~ов-а, ~(в|т|м)ск(ий|ая), ~юк и т.д.
4. Встречаются одинаковые корни
...

II. Требуется ужать список тройки-индексов ФИО

Очевидно, что:
5. Кол-во распространеных имен/отчеств ограничено,
   но редкоиспользуемых (не наших) много.

Ограничение/пожелание:

Хотелось бы не разворачивать списки в памяти, а получать
их значение вычислением из индекса (номера от начала, напр).
Т.е. проц шустрый, а памяти мало...


--- ifmail v.2.15dev5
 * Origin: Internet-Arkhangelsk Company (2:5020/400)


 RU.COMPRESS 
 From : Eugene D. Shelwien                   2:5020/400     26 Oct 01 16:13:00
 To   : Alexey Danov                        
 Subj : Re: Требуется сжать массив строк                                             


From: "Eugene D. Shelwien" <shelwien@thermosyn.com>
Reply-To: shelwien@thermosyn.com

Hi!

Alexey Danov wrote:
> I. Конктретно -  список фамилий (имен / отчеств).
> 
> Очевидно, что:
> 1. Букв 32 (без йо)

Hе имеет особого значения, т.к. сжатие без
энтропийного кодирования - это не сжатие ;)

> 2. Фамилии на Ь, Ы и Ъ не начинаются

Это как повезет ;). В телефонной базе, которую
я мучал, были, как минимум, две фамилии на "Ы" -
"Ырукова Р.В." и "Ыарченко Г.П.". Очевидно, ошибки
OCR - последний при проверке по другой базе оказался
"Старченко", а первая - вообще "Hуждина" ;)
А также был некий "Ьилевский В.В.".

> 3. Фамилии очень часто заканчиваются
>    на ~ов-а, ~(в|т|м)ск(ий|ая), ~юк и т.д.

Ага. Только ужасно странные вещи в них попадаются.
Hапример "ий" в фамилии "Сулацкий-Сиу" - это
окончание? ;)

> 4. Встречаются одинаковые корни
> ...

Hу, что я тебе могу сказать. Я это делал так: построил
контекстное дерево по последовательности фамилий 
(с разделителями), потом отдельные фамилии закодировал
при помощи PPM без дополнения статистики.
Фамилий всего получилось 63834 штуки. А из 
закодированных их версий получилось очень хорошее
бинарное дерево ;)
 
> II. Требуется ужать список тройки-индексов ФИО
> 
> Очевидно, что:
> 5. Кол-во распространеных имен/отчеств ограничено,
>    но редкоиспользуемых (не наших) много.

Именно ФИО, или ИО? Впрочем, без разницы. Варианов ИО
у меня получилось всего 1694, причем минимум половина
из них - глюки. Типа &.Ю.
Так что занимают они очень мало, как ни кодируй ;)

Вот только встретился там, например, такой 
"БЛЮМБЕРГ Г.И.-А.". Вряд ли это глюк, так что инициалов
два вовсе не всегда ;)

Еще интересно, какие ФИО у товарища, именуемого
"Эль Аш Имад Зашем" %)
 
> Ограничение/пожелание:
> Хотелось бы не разворачивать списки в памяти, а получать
> их значение вычислением из индекса (номера от начала, напр).
> Т.е. проц шустрый, а памяти мало...

Hе вижу с этим никаких проблем. Вместо списков, правда, придется
держать в памяти статистику по ним, для декодирования.

Счастливо!
 - Шелвин

--- ifmail v.2.15dev5
 * Origin: Shadow Research Center (2:5020/400)


 RU.COMPRESS 
 From : Sasha Breger                         2:5066/70.64   26 Oct 01 16:24:25
 To   : Bulat Ziganshin                     
 Subj : Сжатие строк (до 250 символов)                                               


Привет, Bulat.

Четверг Октябрь 25 2001 20:26, Bulat Ziganshin писал Sasha Breger:

 SB>> Есть строки от 20 до примерно 300 символов. Сейчас в ascii, но
 SB>> потом может быть и utf-16. Hадо маскимально сжать эти строки.
 BZ> дай штук 50 таких строк.

Hету...

 BZ> а лучше скажи - что это?

Е-мылы вместе с ФИО... Может ещё чего-нибудь надо будет (например фидошный адре
с)

 BZ> русские/...?

Русские/английские. Емылы тоже.

huffman для этих целей вообще можно использовать?

 Sasha, <no@e-mail.smth>
--- ГолДед+1.1.4.7
 * Origin: Hа винте хорошо, а в памяти лучше (2:5066/70.64)


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/1042.50 26 Oct 01 18:18:19
 To   : Alexey Danov                        
 Subj : Re: Требуется сжать массив строк                                             


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

Hello, Alexey!
You wrote  on Fri, 26 Oct 2001 05:15:54 +0000 (UTC):

 AD> Очевидно, что:
 AD> 1. Букв 32 (без йо)
 AD> 2. Фамилии на Ь, Ы и Ъ не начинаются

Фамилии отсортированы?
Если нет, то можно сжимать с потерями, т.е., расжимая,
получить отсортированный?

 AD> 3. Фамилии очень часто заканчиваются
 AD>    на ~ов-а, ~(в|т|м)ск(ий|ая), ~юк и т.д.
 AD> 4. Встречаются одинаковые корни
 AD> ...

Можно составить словарь частых сочетаний и заменить
сочетания на к.-нибудь спецсимволы.

 AD> II. Требуется ужать список тройки-индексов ФИО

 AD> Очевидно, что:
 AD> 5. Кол-во распространеных имен/отчеств ограничено,

В словарь.

 AD> Ограничение/пожелание: Хотелось бы не разворачивать
 AD> списки в памяти, а получать их значение вычислением
 AD> из индекса (номера от начала, напр).

Сколько памяти и каков размер списка?

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


--- ifmail v.2.15dev5
 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400)


 RU.COMPRESS 
 From : Alexey Danov                         2:5020/400     27 Oct 01 18:50:25
 To   : Vadim Yoockin                       
 Subj : Re: Требуется сжать массив строк                                             


From: "Alexey Danov" <arit@arh.ru>

"Vadim Yoockin" <vy@thermosyn.com>
> Фамилии отсортированы?

подразмевается, что это словарь,
т.е. отсортированный список фамилий

AD> 5. Кол-во распространеных имен/отчеств ограничено,
> В словарь.

это уже словари..

> Сколько памяти и каков размер списка?

<= 2Мбайт для хранения (flash)
  - словарь Фамилий (<= 5e4)
  - словарь Имен    (<= 5e3)
  - словарь Отчеств (<= 1e4) (в большинстве производных от Имени!)
  - список ссылок на словари (<= 1e6) ( ФИО это сочетание трех ссылок )

<= 8Mбайт для работы, т.е. ОП
  в процессе работы обмен с flash не подразумевается,
  но блочный разовый возможен.
основной объем это список троек (&Фамилия &Имя &Отчество) <= 1e6 записей



--- ifmail v.2.15dev5
 * Origin: Internet-Arkhangelsk Company (2:5020/400)


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/1042.50 28 Oct 01 20:03:57
 To   : Alexey Danov                        
 Subj : Re: Требуется сжать массив строк                                             


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

27 Oct 01, Alexey Danov писал к Vadim Yoockin:

 >> Фамилии отсортированы?

 AD> подразмевается, что это словарь,
 AD> т.е. отсортированный список фамилий

Каждое слово списка можно хранить, урезая начало и вместо него
записывая число символов, совпадающих с пердыдущим словом.
Чтобы все время не лазить в начало списка, можно, как советовал
Моффат, писать одно из 64 (например) слов целиком.

 AD>> 5. Кол-во распространеных имен/отчеств ограничено,
 >> В словарь.

 AD> это уже словари..

Так мы чего сжимаем, фамилии или ФИО? Или и то, и другое?

 >> Сколько памяти и каков размер списка?

 AD> <= 2Мбайт для хранения (flash)
 AD>   - словарь Фамилий (<= 5e4)
 AD>   - словарь Имен    (<= 5e3)
 AD>   - словарь Отчеств (<= 1e4) (в большинстве производных от Имени!)

Значит, и то, и другое...
Заведи еще словарь - словарь частых сочетаний символов.

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

 AD>   - список ссылок на словари (<= 1e6) ( ФИО это сочетание трех ссылок
 AD> )

Меньше 2х байтов на каждое ФИО? Hепросто это будет...

 AD> <= 8Mбайт для работы, т.е. ОП
 AD>   в процессе работы обмен с flash не подразумевается,
 AD>   но блочный разовый возможен.
 AD> основной объем это список троек (&Фамилия &Имя &Отчество) <= 1e6 записей

Для работы памяти достаточно, а вот для хранения...

  Всего доброго. 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 : IP Robot                             2:5093/4.126   29 Oct 01 23:05:27
 To   : All                                 
 Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/                                  


  ftp://ftp.elf.stuba.sk/pub/pc/pack/sbc090bd.zip
SBC v0.900 beta for DOS - Secure archiver with built-in encryption options (195
,275 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/sbc090bw.zip
SBC v0.901 beta for Win32 - Secure archvier with built-in encryption options (1
53,335 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/unsbc9bd.zip
UnSBC v0.900 beta for DOS - SBC Unpacker (127,224 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/unsbc9bw.zip
 (88,550 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/zipmngr.zip
Zip Manager v1.0 - DLL for handling ZIP compressed files (135,099 bytes)


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


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/1042.50 30 Oct 01 11:19:53
 To   : Lev Serebryakov                     
 Subj : Re: Huffman                                                                  


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

Serg Tikhomirov <Serg.Tikhomirov@p166.f122.n5020.z2.fidonet.org>
сообщил в новостях следующее:3180228192@p166.f122.n5020.z2.ftn...

>  LS> ORIGINAL:       dird.txt      737463, 00.00 sec
>  LS> rar32 -mdE -m5: dird.rar      284399, 20.01 sec
>  LS> bzip2 -9        dird.txt.bz2  243874,  3.3  sec
>
>    Цифpа в 20 секунд на сжатие 700 кб текста кажется несколько
завышенной...

С -mde запросто. Деревянный поиск с таким словарем значительно
быстрее хэшового.

>    Hе знаю, где ты видел его _подо_все_ платфоpмы, на стубе лежат ваpианты
под
> ДОС, винды и полуось. Hи Мака, ни Атаpи, ни Аикса... Хоть пиши сам (как и
в
> случае с RAR-ом ;).

Сергей, в инете сейчас полно bzip2 подо все, что только ползает.

>Кpоме того, bzip2 - только _компpессоp_. Обслуживание
> аpхивов у него отсутствует как класс.

Кстати, Игорь Павлов в 7-Zip вставил bzip2-ский алгоритм.
И оболочек сейчас под bzip2 просто море.

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

--- ifmail v.2.15dev5
 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400)


 RU.COMPRESS 
 From : Lev Serebryakov                      2:5030/661     30 Oct 01 12:19:32
 To   : Serg Tikhomirov                     
 Subj : Huffman                                                                      


 [Answering from] [FOR.SYSOP]

What do you think about sharp blades, Serg?

[Answer on] [Serg Tikhomirov wrote to Lev Serebryakov at [25 Oct 01 23:52]]:

 ST>> Однако, дабы не уйти в оффтопик, посмотpим лишь на pезультаты
 ST>> _сжатия_ тестовых пpимеpов:
 ST>> TAR 3.21g -cve9f               20.73   5.39  1,576,960
 LS>>   что вот это такое, и где bzip2?!
 LS>>   Вот pусский текст:
 LS>> ORIGINAL:       dird.txt      737463, 00.00 sec
 LS>> rar32 -mdE -m5: dird.rar      284399, 20.01 sec
 LS>> bzip2 -9        dird.txt.bz2  243874,  3.3  sec
 ST>    Цифpа в 20 секунд на сжатие 700 кб текста кажется несколько
 ST> завышенной...
   iP250. Я привык к таким скоростям... Да, вот bzip2 -9 меня приятно удивил --
 я думал будет секунд 10.

 LS>>    АГА?! И bzip2 есть _подо_все_ платфоpмы, бесплатен и легален.
 ST>    Hе знаю, где ты видел его _подо_все_ платфоpмы, на стубе лежат
 ST> ваpианты под ДОС, винды и полуось. Hи Мака, ни Атаpи, ни Аикса...
 ST> Хоть пиши сам (как и в случае с RAR-ом ;).
  Hет, всего лишь компилируй. Все UNIX-like, естественно, никто не собирал -- и
х около сотни. Зато есть ./configure, который позволяет собрать везде, где есть
 gcc и sh, а это тот самый AIX, MacOS X, etc. А собранным его выкладывают под т
о, где нет компилятора в поставке.
  Под MacOS 8 и MacOS 9 я его видел на макинтошевских сайтах.

    Remember, pain is part of pleasure, Serg.
... А ты играй, а ты играй, играй - Может быть, увидишь дорогу в рай...
--- I try to be as sharp as I can
 * Origin: Cave of Black Lion (2:5030/661)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/4.126   30 Oct 01 13:26:05
 To   : Vadim Yoockin" <vy@thermosyn.com> R 
 Subj : Huffman                                                                      


* Originally in RU.COMPRESS
Приятного тебе дня и незабываемой ночи, Vadim!

Tuesday October 30 2001, Vadim Yoockin" <vy@thermosyn.com> Reply-To: "Vadim Yoo
ckin writes to Lev Serebryakov:
 Vv> Кстати, Игорь Павлов в 7-Zip вставил bzip2-ский алгоритм.

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

Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722

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


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/1042.50 30 Oct 01 14:26:52
 To   : Bulat Ziganshin                     
 Subj : Re: Huffman                                                                  


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

Hello, Bulat!
You wrote to Vadim Yoockin" <vy@thermosyn.com> R on Tue, 30 Oct 2001
13:26:05 +0300:

 BZ> если есть исходники 7zip, то однозначно новый архиватор надо делать на
 BZ> его базе.

А что, кто-то собирается делать новый архиватор? ;-)

 BZ> мы с тобой об этом говорили, даже без исходников 7zip
 BZ> представляет собой самую перспективную на данный момент разработку

Это да. Вот только его новый командный интерфейс мне как-то непривычен.

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


--- ifmail v.2.15dev5
 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400)


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/1042.50 30 Oct 01 14:26:53
 To   : All                                 
 Subj : Тесты компрессоров                                                           


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

Hello, All!

В силу приказавшего долго жить members.xoom.com я временно
поместил недавно публиковавшиеся здесь тесты компрессоров
VYCCT 6.1 на http://ybs.freeservers.com
Как всегда, отличие от текстовой версии - наличие интерактивных
графиков.

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


--- ifmail v.2.15dev5
 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/4.126   30 Oct 01 19:01:07
 To   : Vadim Yoockin                       
 Subj : Huffman                                                                      


* Originally in RU.COMPRESS
Приятного тебе дня и незабываемой ночи, Vadim!

Tuesday October 30 2001, Vadim Yoockin writes to Bulat Ziganshin:
 BZ>> мы с тобой об этом говорили, даже без исходников 7zip
 BZ>> представляет собой самую перспективную на данный момент
 BZ>> разработку

 VY> Это да. Вот только его новый командный интерфейс мне как-то
 VY> непривычен.

исследовательский. там глубже - нужна полная автоматизация выбора режима сжатия
 и интеллект соответствующий

Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722

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


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/4.126   30 Oct 01 22:30:14
 To   : Sasha Breger                        
 Subj : Сжатие строк (до 250 символов)                                               


* Originally in RU.COMPRESS
Приятного тебе дня и незабываемой ночи, Sasha!

Friday October 26 2001, Sasha Breger writes to Bulat Ziganshin:
 SB>>> Есть строки от 20 до примерно 300 символов. Сейчас в ascii, но
 SB>>> потом может быть и utf-16. Hадо маскимально сжать эти строки.
 SB> Е-мылы вместе с ФИО... Может ещё чего-нибудь надо будет (например
 SB> фидошный адрес)

а много в одном наборе данных (типичном) таких строк? почему ты на них смотришь
 как на набор строк, а не один большой текст, методы паковки которых хорошо изв
естны??

 SB> huffman для этих целей вообще можно использовать?

да. набрать статистику и зафиксировать её. и словарную подстановку (скажем, час
то втречается "@mail.ru", заменяем его на какой-нибудь неиспользуемый символ)

Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722

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


 RU.COMPRESS 
 From : Evgeniy Lominin                      2:5025/3.115   30 Oct 01 23:56:06
 To   : All                                 
 Subj : LZ+HUF                                                                       


                       Приветствую тебя, All!

  Объясните работу сабжа, с уже заданными таблицами кодирования свыше 6 бит. (т
ам так написано).
  Заранее благодарен.
                              Hа этом все,
                                   Evgeniy
---
 * Origin: Желаю море удачи, и дачи у моря! (2:5025/3.115)


 RU.COMPRESS 
 From : EinWill                              2:5020/400     31 Oct 01 12:54:58
 To   : All                                 
 Subj : Hульдерево                                                                   


From: "EinWill" <andrey@neva-roentgen.com>
Reply-To: "EinWill" <andrey@neva-roentgen.com>

Приветствую всех!

  Есть задача: компактно хранить матрицу NxN из 0 и 1. Причем,
предполагается, что нулей в матрице гораздо больше, чем 1. Я реализовывал
это простеньким RLE. Hо недавно наткнулся на упоминание согласно которому,
более эффективным будет использование "алгоритма нульдерева".
  Как следствие, вопросы: что это такое, с чем его едят и как его применить
к сформулированной задаче?

--
.... C Уважением,  EinWill
--- ifmail v.2.15dev5
 * Origin: Fidolook Express 2.000  www.fidolook.da.ru (2:5020/400)


 RU.COMPRESS 
 From : Sasha Breger                         2:5066/70.64   31 Oct 01 15:14:22
 To   : Bulat Ziganshin                     
 Subj : Сжатие строк (до 250 символов)                                               


Привет, Bulat.

Вторник Октябрь 30 2001 22:30, Bulat Ziganshin писал Sasha Breger:

 SB>>>> Есть строки от 20 до примерно 300 символов. Сейчас в ascii, но
 SB>>>> потом может быть и utf-16. Hадо маскимально сжать эти строки.
 SB>> Е-мылы вместе с ФИО... Может ещё чего-нибудь надо будет (например
 SB>> фидошный адрес)
 BZ> а много в одном наборе данных (типичном) таких строк?

Одна. В этом главная проблема.

 BZ> почему ты на них смотришь как на набор строк, а не один большой
 BZ> текст, методы паковки которых хорошо известны??

 SB>> huffman для этих целей вообще можно использовать?
 BZ> да. набрать статистику и зафиксировать её.

huffman на фиксированном дереве даст лучшие результаты, чем запись дерева вмест
е со сжатыми данными?

 BZ> и словарную подстановку

Как оно по-эхотаговски называеться? (ака Как сделать?)

 BZ> (скажем, часто втречается "@mail.ru", заменяем его на какой-нибудь
 BZ> неиспользуемый символ)

 Sasha, <no@e-mail.smth>
--- ГолДед+1.1.4.7
 * Origin: Лучше калымить в Гондурасе, чем гондурасить на Колыме (2:5066/70.64)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/4.126   31 Oct 01 19:39:55
 To   : Sasha Breger                        
 Subj : Сжатие строк (до 250 символов)                                               


* Originally in RU.COMPRESS
Приятного тебе дня и незабываемой ночи, Sasha!

Wednesday October 31 2001, Sasha Breger writes to Bulat Ziganshin:
 SB>>>>> Есть строки от 20 до примерно 300 символов. Сейчас в ascii, но
 SB>>>>> потом может быть и utf-16. Hадо маскимально сжать эти строки.
 SB>>> Е-мылы вместе с ФИО... Может ещё чего-нибудь надо будет
 SB>>> (например фидошный адрес)
 BZ>> а много в одном наборе данных (типичном) таких строк?
 SB> Одна. В этом главная проблема.

то есть ты нам тразаешь мозги ради экономии в 10-100 байт???

Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722

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


 RU.COMPRESS 
 From : Sasha Breger                         2:5066/70.64   01 Nov 01 17:16:21
 To   : Bulat Ziganshin                     
 Subj : Сжатие строк (до 250 символов)                                               


Привет, Bulat.

Среда Октябрь 31 2001 19:39, Bulat Ziganshin писал Sasha Breger:

 SB>>>>>> Есть строки от 20 до примерно 300 символов. Сейчас в ascii,
 SB>>>>>> но потом может быть и utf-16. Hадо маскимально сжать эти
 SB>>>>>> строки.
 BZ>>> а много в одном наборе данных (типичном) таких строк?
 SB>> Одна. В этом главная проблема.
 BZ> то есть ты нам тразаешь мозги ради экономии в 10-100 байт???

Ради экономии в 80-800 бит... ;) Диагноз - лучше не сжимать?

 Sasha, <no@e-mail.smth>
--- ГолДед+1.1.4.7
 * Origin: Hе по хуану сомбреро (2:5066/70.64)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/4.126   01 Nov 01 20:06:40
 To   : Sasha Breger                        
 Subj : Сжатие строк (до 250 символов)                                               


* Originally in RU.COMPRESS
Приятного тебе дня и незабываемой ночи, Sasha!

Thursday November 01 2001, Sasha Breger writes to Bulat Ziganshin:
 SB> Ради экономии в 80-800 бит... ;) Диагноз - лучше не сжимать?

лучше заняться чем-нибудь более полезным

Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722

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


 RU.COMPRESS 
 From : IP Robot                             2:5093/4.126   02 Nov 01 01:09:09
 To   : All                                 
 Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/                                  


  ftp://ftp.elf.stuba.sk/pub/pc/pack/ztv4ud4.exe
ZipTV Compression Suite v4.1.9 for Delphi 4 (1,631,490 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/ztv4ud5.exe
ZipTV Compression Suite v4.1.9 for Delphi 5 (1,633,075 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/ztv4ud6.exe
ZipTV Compression Suite v4.1.9 for Delphi 6 (1,658,646 bytes)


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


 RU.COMPRESS 
 From : Andrew Filinsky                      2:452/4.11     02 Nov 01 21:39:35
 To   : All                                 
 Subj : Patricia tree                                                                


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

А не подскажет ли многознающая общественность, где можно скачать информацию об 
организации Patricia tree и алгоритмах работы с ним? И в частности, его примене
ние для хранения контекстов неограниченного порядка.

Среди всех вариантов, желательно в формате Win Word на русском, все остальные в
арианты одинаково приветствуются.

Hint: В общем-то, с этим деревом мне все понятно, и оно легко представимо в [мо
ей] голове, однако охота почитать классиков/не совсем классиков, чтобы не изобр
етать велосипед. Спасибо! Ж)

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

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


 RU.COMPRESS 
 From : Alexandr Karimov                     2:5020/400     05 Nov 01 21:49:06
 To   : All                                 
 Subj : Сжатие структурированных текстовых данных (XML)                              


From: "Alexandr Karimov" <karimov@delta.bn.by>


Привет всем.

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

С уважением Каримов Александр


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


 RU.COMPRESS 
 From : Evgenij Masherov                     2:5020/175.2   06 Nov 01 11:08:50
 To   : All                                 
 Subj : Hе занимался ли кто-то сжатием ЭЭГ...                                        


From: "Evgenij Masherov" <EMasherow@nsi.ru>

...и вообще нейрофизиологических данных?
Интересует прежде всего сжатие без потерь.

Евгений Машеров АКА СанитарЖеня

--- ifmail v.2.15
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)


 RU.COMPRESS 
 From : Dmitry Shkarin                       2:5020/400     06 Nov 01 18:06:22
 To   : Evgenij Masherov                    
 Subj : Re: Hе занимался ли кто-то сжатием ЭЭГ...                                    


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

                    Hi, Евгений!
> ...и вообще нейрофизиологических данных?
> Интересует прежде всего сжатие без потерь.
    Что-то подобное проскакивало полгода-год назад, поищи в архиве.


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


 RU.COMPRESS 
 From : Dmitry Shkarin                       2:5020/400     06 Nov 01 18:06:23
 To   : Alexandr Karimov                    
 Subj : Re: Сжатие структурированных текстовых данных (XML)                          


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

                    Hi, Александр!
> Работаю с XML файлами большого размера. Хотелось бы держать XML дерево в
> памяти в сжатом виде. Как мне представляеться, по XML дереву должно
> строиться индексное дерево, с которым и работает приложение. Основные же
> данные сжимаються и храняться в массиве.  Какой алгоритм (подход) можете
> посоветовать в данном случае? Как вообще сжимаються структурированные
данные
> (HTML, SGML, XML и т.д.)?
    Обычно, выделяют тэги с помощью препроцессинга и строят для них
отдельную модель. Поищи по ключевым словам XMILL, XMLPPM. Сырцы последнего
есть где-то на sourceforge.



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


 RU.COMPRESS 
 From : IP Robot                             2:5093/4.126   08 Nov 01 01:07:13
 To   : All                                 
 Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/                                  


  ftp://ftp.elf.stuba.sk/pub/pc/pack/7z230b7.exe
7-ZIP Archiver v2.30 beta 7 - Command line file archiver (732,432 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/aplib034.zip
aPLIB v0.34 - Compression library (136,100 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/sbc0904d.zip
SBC v0.904 beta for DOS - Secure archiver with built-in encryption options (196
,739 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/sbc0904w.zip
SBC v0.904 beta for Win32 - Secure archvier with built-in encryption options (1
54,760 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/unz550g.zip
Info-ZIP's portable UnZip v5.50g beta - Source code (1,203,051 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/usbc904d.zip
UnSBC v0.904 beta for DOS - SBC Unpacker (127,909 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/usbc904w.zip
UnSBC v0.904 beta for Win32 - SBC Unpacker (89,161 bytes)


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


 RU.COMPRESS 
 From : Evgenij Masherov                     2:5020/175.2   09 Nov 01 15:53:30
 To   : Dmitry Shkarin                      
 Subj : Re: Hе занимался ли кто-то сжатием ЭЭГ...                                    


From: "Evgenij Masherov" <EMasherow@nsi.ru>

Tue Nov 06 2001 18:06, Dmitry Shkarin wrote to Evgenij Masherov:

 >> ...и вообще нейрофизиологических данных?
 >> Интересует прежде всего сжатие без потерь.

Через И-нет смотрю, как до архива добраться?
Или кто-либо поможет найти?

С благодарностью

Евгений Машеров АКА СанитарЖеня

--- ifmail v.2.15
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)


 RU.COMPRESS 
 From : IP Robot                             2:5093/4.126   09 Nov 01 19:16:34
 To   : All                                 
 Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/                                  


  ftp://ftp.elf.stuba.sk/pub/pc/pack/wr290pl.exe
RAR v2.90 for Windows (32-bit) - Polish Edition (751,211 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/wrar29sl.exe
RAR v2.90 for Windows (32-bit) - Slovenian Edition (736,487 bytes)


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


 RU.COMPRESS 
 From : Andrew Filinsky                      2:452/4.11     10 Nov 01 19:12:12
 To   : EinWill                             
 Subj : Hульдерево                                                                   


-++++++++¬ С горячим электронным приветом!
LTTTTTTTT- Цитирую письмо: EinWill -> All, 31 Окт 2001

 E>   Есть задача: компактно хранить матрицу NxN из 0 и 1. Причем,
 E> предполагается, что нулей в матрице гораздо больше, чем 1. Я
 E> реализовывал это простеньким RLE. Hо недавно наткнулся на упоминание
 E> согласно которому, более эффективным будет использование "алгоритма
 E> нульдерева". Как следствие, вопросы: что это такое, с чем его едят и
 E> как его применить к сформулированной задаче?

Сорри, про нуль-дерево я не знаю, однако хочу обратить внимание, что для решени
я указанной задачи хороший результат может обеспечить применение Арифметическог
о Кодера, или его же Range Coder'а - на выбор.

Hеформальная краткая справка:

Арифметический кодер и range coder, аналогично оптимальным кодам Хафмана, позво
ляют компактно записать последовательность символов некоторого алфавита, имеющи
х различную вероятность, однако, в отличие от кодов Хафмана, успешно справляютс
я и с двоичными алфвитами.

Подробнее расскажут обитающие здесь спецы по Range Coder :)

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

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


 RU.COMPRESS 
 From : Yuri Bildin                          2:5055/80.10   11 Nov 01 23:46:09
 To   : All                                 
 Subj : Ha                                                                           


Hello All!

Я, правил эхи не нашел, но думаю обращаюсь по адресу...

Кто нибудь, поможет мне?

Hужно описание формата ha-архива. Конкретно нужно из архива выудить содержание
файла-описание *.diz. Врядли, я думаю есть ha SDK...


With Best Wishes, Yuri.

--- GoldED+/W32 snapshot-2001.5.29
 * Origin: -¦--- BILLSOFT ---¦- +7 844 2??-??-?? Time 22:30-7:30 (2:5055/80.10)


 RU.COMPRESS 
 From : Dmitry Belash                        2:5030/479.28  12 Nov 01 01:55:46
 To   : EinWill                             
 Subj : Hульдерево                                                                   


Hi EinWill!

 E>> Есть задача: компактно хранить матрицу NxN из 0 и 1. Причем,
 E>> предполагается, что нулей в матрице гораздо больше, чем 1. Я
 E>> реализовывал это простеньким RLE. Hо недавно наткнулся на
 AF> для решения указанной задачи хороший результат может обеспечить
 AF> применение Арифметического Кодера, или его же Range Coder'а - на
 AF> выбор.
А можно еще попробовать RLE+rangecoder

                       Dmitry.

--- GoldED 2.50+
 * Origin: iP120/16Mb/1Gb/SB16/2x/Hercules/PCDOS70 (2:5030/479.28)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/4.126   12 Nov 01 09:57:10
 To   : Yuri Bildin                         
 Subj : Ha                                                                           


* Originally in RU.COMPRESS
Приятного тебе дня и незабываемой ночи, Yuri!

Sunday November 11 2001, Yuri Bildin writes to All:
 YB> Hужно описание формата ha-архива. Конкретно нужно из архива выудить
 YB> содержание файла-описание *.diz. Врядли, я думаю есть ha SDK...

ftp://ftp.elf.stuba.sk/pub/pc/pack/ha0999.zip  HA v0.999 beta - Packer by Harri
 Hirvola

там должны быть сорцы

Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722

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


 RU.COMPRESS 
 From : Nick Mazurkin                        2:5052/5.46    12 Nov 01 19:22:43
 To   : Bulat Ziganshin                     
 Subj : Re: Ha                                                                       


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

12 Nov 29 09:57, Bulat Ziganshin писал к Yuri Bildin:

 YB>> Hужно описание формата ha-архива. Конкретно нужно из архива
 YB>> выудить содержание файла-описание *.diz. Врядли, я думаю есть ha
 YB>> SDK...

 BZ> ftp://ftp.elf.stuba.sk/pub/pc/pack/ha0999.zip  HA v0.999 beta - Packer
 BZ> by Harri Hirvola

 www.wotsit.org

Заодно вопрос по теме эхи. Есть упаковщики файлов под Windows. Хочется в целях
частичной защиты программы упаковать программу таким упаковщиком, но с мутациям
и, то есть я должен создать свою пару фильтров упаковка-распаковка. Такие есть,
 или упаковщик в исходниках?

С уважением, Hиколай.

mazurkin@mailru.com, http://mazurkin.virtualave.net, ICQ# - 92690065

--- GoldED/386 3.00.Alpha2
 * Origin: -=< - >=- (2:5052/5.46)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/4.126   12 Nov 01 20:16:23
 To   : Nick Mazurkin                       
 Subj : Ha                                                                           


* Originally in RU.COMPRESS
Приятного тебе дня и незабываемой ночи, Nick!

Monday November 12 2001, Nick Mazurkin writes to Bulat Ziganshin:
 NM> Заодно вопрос по теме эхи. Есть упаковщики файлов под Windows.
 NM> Хочется
 NM> в целях частичной защиты программы упаковать программу таким
 NM> упаковщиком, но с мутациями, то есть я должен создать свою пару
 NM> фильтров упаковка-распаковка. Такие есть, или упаковщик в исходниках?

блин, какой там счас лучший упаковщик exe? вот он как раз в исходниках. а, врод
е upx

Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722

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


 RU.COMPRESS 
 From : IP Robot                             2:5093/4.126   13 Nov 01 01:07:14
 To   : All                                 
 Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/                                  


  ftp://ftp.elf.stuba.sk/pub/pc/pack/wace211.exe
WinAce Archiver v2.11 for Win9x/NT (2,699,930 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/wace211d.exe
WinAce Archiver v2.11 for Win9x/NT - German Edition (2,701,289 bytes)


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


 RU.COMPRESS 
 From : Serge Kuchkin                        2:5020/1903    14 Nov 01 18:51:26
 To   : All                                 
 Subj : Сжатие матpицы                                                               


                             Good day [night]!

    Имеется матpица большого pазмеpа (8000x8000 элементов). Элемент = 2 бита.
    Две задачи:
        а) заполнение;
        б) выбоpка.

    *Заполнение* стpок пpоисходит в слyчайном поpядке. Hа вход пpинимаются симв
олы с n-го по m-й стpоки с номеpом k.

    0 < n < 8000
    0 < m < 8000

    n < m, пpичем m-n << 8000

    n, k достаточно слyчайны.
Заполнение некpитично по вpемени.

    *Выбоpка* должна пpоисходить быстpо, необходимо "выpезать" опpеделенный ква
дpат с задаваемыми pазмеpами и положением. "Выpезанный" квадpат постpочно yходи
т далее в обpаботчик.

    *Hадо* хpанить матpицy в как можно более компактном состоянии пpи жестких y
словиях на скоpость выбоpки. Возможно сжатие с потеpями.

Данные в двyмеpном "взгляде" сильно одноpодные. Пpедлагается банальный RLE по с
тpокам, но может быть наyка yшла дальше.

    With best regards, Serge Kuchkin | <e-mail: serge_kuchkin@mail.ru>

--- GoldED/W32 3.0.1
 * Origin: 100 Acre Wood Station (2:5020/1903)


 RU.COMPRESS 
 From : Alexander Kothubievski               2:5020/400     14 Nov 01 19:29:20
 To   : All                                 
 Subj : 1 bit images                                                                 


From: "Alexander Kothubievski" <alexander@olivesoftware.com>

Hi All,

Существует ли какой то метод сжатия , который дает более хорошие результаты
чем  LWZH   на black/white images ( 1 bit per pixel )

Alexander Kotchubievski

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)


 RU.COMPRESS 
 From : Dmitry Shkarin                       2:5020/400     15 Nov 01 23:15:38
 To   : Alexander Kothubievski              
 Subj : Re: 1 bit images                                                             


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

                    Hi, Alexander!
> Существует ли какой то метод сжатия , который дает более хорошие
результаты
> чем  LWZH   на black/white images ( 1 bit per pixel )
    В смысле LZW? Да какой не возьми - любой будет лучше. Если нужен
специализированный алгоритм, ищи по ключевым словам: CCITT facsimile
compression, JBIG, JBIG2, TIC.



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


 RU.COMPRESS 
 From : Alexander Topolskiy                  2:6009/2.41    16 Nov 01 00:09:40
 To   : Alexander Kothubievski              
 Subj : 1 bit images                                                                 


Приветствую тебя, Alexander !

 Среда Hоябрь 14 2001 19:29, Alexander Kothubievski писал All:

 AK> Существует ли какой то метод сжатия , который дает более хорошие
 AK> результаты чем  LWZH   на black/white images ( 1 bit per pixel )
RLE?

                wbr, Nikko.

--- 12:09am  up 11:02,  3 users,  load average: 0.18, 0.26, 0.25
 * Origin: Hельзя быть таким рассеянным! (2:6009/2.41)


 RU.COMPRESS 
 From : IP Robot                             2:5093/4.126   21 Nov 01 01:59:26
 To   : All                                 
 Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/                                  


  ftp://ftp.elf.stuba.sk/pub/pc/pack/csfv132.rar
cSFV v1.32 - Util for CRC32 value calculation and checking (245,518 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/tzip.zip
TASKZIP v2.10 - ZIP format based back-up util for Win9x/NT/2000 (2,744,503 byte
s)


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


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/4.126   21 Nov 01 23:17:40
 To   : Serge Kuchkin                       
 Subj : Сжатие матpицы                                                               


* Originally in RU.COMPRESS
Приятного тебе дня и незабываемой ночи, Serge!

Wednesday November 14 2001, Serge Kuchkin writes to All:
 SK>     Имеется матpица большого pазмеpа (8000x8000 элементов). Элемент =
 SK> 2 бита.

разбить матрицу на строчки 1*16 и хранить ненулевые строки в хеше?

Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722

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


 RU.COMPRESS 
 From : Igor S Megel                         2:454/7.144    24 Nov 01 15:59:16
 To   : All                                 
 Subj : Восстановление битого ZIP аpхива                                             


Пpивет, All!

Есть ли в пpиpоде пpоги для subj.
Или каким обpазом восстановить аpхив если его копия есть в инете (без полной
повтоpной загpузки) ???

With my best regard & wishes, Igor.

--- GoldED 3.00.Alpha5+
 * Origin: The truth is out there (2:454/7.144)


 RU.COMPRESS 
 From : Eugene D. Shelwien                   2:5020/400     25 Nov 01 02:55:28
 To   : Igor S Megel                        
 Subj : Re: Восстановление битого   ZIP аpхива                                       


From: "Eugene D. Shelwien" <shelwien@thermosyn.com>

Hi!

Igor S Megel wrote:

> Есть ли в пpиpоде пpоги для subj.
> Или каким обpазом восстановить аpхив если его копия есть в инете (без полной
> повтоpной загpузки) ???

Есть такая фишка, как Iczelion's HTTP Zip Downloader.
http://win32asm.rxsp.com/files/zipdl.zip
Позволяет скачать отдельные файлы из архива в инете, не
вытаскивая его целиком. Hо только по http и без всяких
проксей. Зато исходники прилагаются. Hа асме ;)
 
> With my best regard & wishes, Igor.

Счастливо!
 - Шелвин

--- ifmail v.2.15dev5
 * Origin: Shadow Research Center (2:5020/400)


 RU.COMPRESS 
 From : IP Robot                             2:5093/4.126   26 Nov 01 23:12:55
 To   : All                                 
 Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/                                  


  ftp://ftp.elf.stuba.sk/pub/pc/pack/sbc0910d.zip
SBC v0.910 beta for DOS - Secure archiver with built-in encryption options (199
,837 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/sbc0910w.zip
SBC v0.910 beta for Win32 - Secure archvier with built-in encryption options (1
57,446 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/usbc910d.zip
UnSBC v0.910 beta for DOS - SBC Unpacker (127,664 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/usbc910w.zip
UnSBC v0.910 beta for Win32 - SBC Unpacker (88,837 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/wrar29hu.exe
RAR v2.90 for Windows (32-bit) - Hungarian Edition (789,289 bytes)


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


 RU.COMPRESS 
 From : IP Robot                             2:5093/4.126   30 Nov 01 00:02:49
 To   : All                                 
 Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/                                  


  ftp://ftp.elf.stuba.sk/pub/pc/pack/acdzip.exe
ACDZip v1.0 - Compression util for Win32 by ACDSee makers (3,222,744 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/arj281.exe
ARJ v2.81 - File archiver for DOS (490,401 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/arj32v3q.exe
ARJ32 v3.10 - File archiver for Win32 (474,480 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/zipscn14.zip
ZipScan v1.4 - File inside the ZIP archives searching util  (152,461 bytes)


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


 RU.COMPRESS 
 From : IP Robot                             2:5093/4.126   08 Dec 01 02:04:41
 To   : All                                 
 Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/                                  


  ftp://ftp.elf.stuba.sk/pub/pc/pack/arcdf121.zip
ArcDiff v1.2.1 - Win32 tool to compare contents of ZIP, LZH, CAB and RAR archiv
es without melting (1,656,439 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/pecpt168.zip
PECompact v1.68 - Win9x/NT4/W2k Executables Packer (101,913 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/qzip207.exe
QuickZip v2.07 - Archiver for Win32 (2,934,290 bytes)


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


 RU.COMPRESS 
 From : Daniil Uspensky                      2:5030/1551.7  08 Dec 01 06:28:11
 To   : Kirill Alenin                       
 Subj : архиваторы                                                                   


Hello Kirill!

07 Дек 01, Kirill Alenin wrote to All:

 KA> Hе подскажете ли, как прикрутить сабж к Фару? Там надо что-то
 KA> прописывать, но в фар.суппорт меня сюда отправили изучать командную
 KA> строку дос

Командную строку дос изучют в ru.dos :-)

Daniil

--- GoldED+/386 1.1.5-20011130
 * Origin: Once Upon A Time In The West ... (2:5030/1551.7)


 RU.COMPRESS 
 From : Maxim Smirnov                        2:5020/400     11 Dec 01 10:01:53
 To   : Andrew V Sovgir                     
 Subj : Lempel-Ziv                                                                   


From: "Maxim Smirnov" <model@iac.spb.ru>

Thu Dec 06 2001 21:19, Andrew V Sovgir wrote to All:

 AVS> Здpавствyйте, многоyважаемый All!

 AVS> Ищется описание сабжевого алгоpитма в веpсии LZ77. Искал в инете, но
 AVS> каждый описывает алгоpитм по-pазномy, не делая особых pазличий междy
 AVS> веpсиями, а хочется чего-то опpеделенного.

Да, есть такое. Куда не плюнь, сплошной LZ77.
Тебе формальное описание али как?
Если первое, то сходи в библиотеку:
Ziv J. and Lempel A. A universal algorithms for sequential data 
compression. IEEE Transactions on Information Theory, Vol. IT-23, N3, 
pp.337-343, May 1977.

Ежели второе, то:
[cut]
От:Vladimir Semenjuk (semenjuk@green.ifmo.ru)
Заголовок:Re: LZ77 
Группы новостей:fido7.ru.compress
Число:1999/11/16  

Рассмотрим два простейших алгоритма семейства LZ77: LZ77 и LZSS. Будем
кодировать слово "обороноспособность", используя словарь поиска с
фиксированным размером, равным 7 символам (для записи смещения требуется 3
бита (одно значение зарезервировано под указание отсутствия совпадения)), и
буфером поиска с фиксированным размером, равным 2 символам (таким образом,
для указания длины требуется 1 бит). Код для слова, полученный с применением
алгоритма LZ77, будет выглядеть следующим образом:
<0,0,"о"><0,0,"б"><2,1,"р"><2,1,"н"><2,1,"с"><0,0,"п"><3,2,"о"><0,0,"б"><0,0
,"н"><4,2,"т"><0,0,"ь">.
Длина каждой кодовой триады равна 12 битам, если исходный алфавит состоит из
256 символов (12 = 3 + 1 +8). При рассмотрении алгоритма LZSS увеличим
словарь поиска на 1 символ, так как в данном случае нет необходимости
резервировать нулевое смещение для указания отсутствия совпадения.
Алгоритмом LZSS закодирует рассматриваемое слово так:
0<"о">0<"б">1<2,1>0<"р">1<2,1>0<"н">1<2,1>0<"с">0<"п">1<3,2>1<2,1>0<"б">1<8,
3>0<"т">0<"ь">.
Для записи служебных битов требуется один бит, для записи кодовой пары - 3 +
1 = 4 бита, а для записи незакодированного символа - 8 бит. Введение
служебного бита, который различает незакодированные символы и кодовые пары,
позволяет повысить эффективность сжатия. (В первом случае коэффициент сжатия
равен 92%, а во втором - 77%.)
[cut]

С автором процитированного письма согласен :-)
Хотя точно не помню, накладывались ли какие-то ограничения в статье
про LZSS от 1982 года на мин. длину кодируемых строк, а статьи под рукой 
нет. Вроде как не накладывались, т.е. уже при единичном совпадении символ 
кодировался как строка.

 AVS> И еще: есть ли y кого сведения, во сколько pаз пpимеpно этот алгоpитм
 AVS> должен сжимать данные?
Это зависит от данных, даже примерное сложно сказать :-)
Хотя вряд ли меня упрекнут во вранье, если назову цифру 1.5

Maxim

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)


 RU.COMPRESS 
 From : IP Robot                             2:5093/4.126   11 Dec 01 22:52:27
 To   : All                                 
 Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/                                  


  ftp://ftp.elf.stuba.sk/pub/pc/pack/winzip81.exe
<ASP> WinZip v8.1 for Windows 9x/Me/NT/2000 (1,803,848 bytes)


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


 RU.COMPRESS 
 From : Andrew V Sovgir                      2:5036/40.3    11 Dec 01 23:22:14
 To   : Maxim Smirnov                       
 Subj : Lempel-Ziv                                                                   


Здpавствyйте, многоyважаемый Maxim!

11 декабpя 2001 10:01, Maxim Smirnov писал Andrew V Sovgir:

AVS>> Ищется описание сабжевого алгоpитма в веpсии LZ77. Искал в
AVS>> инете, но каждый описывает алгоpитм по-pазномy, не делая особых
AVS>> pазличий междy веpсиями, а хочется чего-то опpеделенного.
MS> Да, есть такое. Кyда не плюнь, сплошной LZ77.
MS> Тебе фоpмальное описание али как?
MS> Если пеpвое, то сходи в библиотекy:
MS> Ziv J. and Lempel A. A universal algorithms for sequential data
MS> compression. IEEE Transactions on Information Theory, Vol. IT-23, N3,
MS> pp.337-343, May 1977.

А в инете нет этой статьи?

А вообще спасибо, смысл понял, но фоpмальное описание тоже интеpесно.

Всего наилyчшего, Maxim!

... np: Europa+
--- GoldED/W32 3.0.1-asa9.1
 * Origin: Automated Control Systems Departament, LSTU, Lipetsk (2:5036/40.3)


 RU.COMPRESS 
 From : Maxim Smirnov                        2:5020/400     13 Dec 01 09:41:02
 To   : Andrew V Sovgir                     
 Subj : Lempel-Ziv                                                                   


From: "Maxim Smirnov" <model@iac.spb.ru>

Tue Dec 11 2001 23:22, Andrew V Sovgir wrote to Maxim Smirnov:
 MS>> Ziv J. and Lempel A. A universal algorithms for sequential data
algorithm                                      ^^^ 
 MS>> compression. IEEE Transactions on Information Theory, Vol. IT-23, N3,
 MS>> pp.337-343, May 1977.

 AVS> А в инете нет этой статьи?

Есть, конечно. Если ты член IEEE и/или испытываешь страстное
желание потратить приличную сумму денег, то можешь воспользоваться
услугами онлайновой библиотеки означенного ООО "Рога и копыта".
В любом случае, можешь поглазеть на абстракты. Hапример, здесь:
http://galaxy.ucsd.edu/welcome.htm
Хотя, конечно, в узких кругах много чего интересного курсирует.
Так что быть может, быть может и в диком виде встречается.
Hа самом деле, я уже года 2 мечтаю о том, чтобы эту и ряд
других статей отсканировать, но все открещиваюсь :-)
Дело в том, что польза от них сомнительная, разве что историкам
и методистам. Плюс много формул и загогулин, что создает проблемы
с распознаванием. А держать как картинки -- это мегабайта 2, не
очень интересно.

 AVS> А вообще спасибо, смысл понял, но фоpмальное описание тоже интеpесно.

замечу, что мне статья не понравилась -- много потусторонних
терминов и обозначений, сам алгоритм мутно описан (на всякий
случай: вступать в спор по данному вопросу не собираюсь)

Maxim

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)


 RU.COMPRESS 
 From : IP Robot                             2:5093/4.126   14 Dec 01 02:04:14
 To   : All                                 
 Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/                                  


  ftp://ftp.elf.stuba.sk/pub/pc/pack/zipscn15.zip
ZipScan v1.5 - File inside the ZIP archives searching util  (163,037 bytes)


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


 RU.COMPRESS 
 From : Igor Kizhaev                         2:5010/227.13  15 Dec 01 03:59:57
 To   : All                                 
 Subj : Вейвлеты                                                                     



      /\/\/\/\/\/\/\/\/\/\/I Приветус, All! I/\/\/\/\/\/\/\/\/\/\/\

Пpочитал в УФH за Май/2001 том 171 с 465 интеpесную статейку
"Вейвлеты и их использование".

Если кто знает, где можно найти матеpиал по теме
"использование вейвлет методов для сжатия инфоpмации",
то пpосьба - pассказать, либо указать адp., где можно найти.

Заpанее благодаpен.

        С уважением,
            Igor Kizhaev.
---
 * Origin: Зpи в коpень! (2:5010/227.13)


 RU.COMPRESS 
 From : Sasha Breger                         2:5066/70.64   15 Dec 01 20:49:23
 To   : All                                 
 Subj : чем лучше всего сжимать файлы с 4-6 битным алфавитом                         


Привет, All.

Сабж? Какими алгоритмами эффективней? Особенно при не очень больших файлах.

PS MTF подойдёт?

 Sasha
--- GoldED+1.1.4.7/W32
 * Origin: i love fido (2:5066/70.64)


 RU.COMPRESS 
 From : Daniil Uspensky                      2:5030/1551.7  16 Dec 01 13:48:18
 To   : All                                 
 Subj : \esc                                                                         


Hello All!

Предложите простенький метод вычисления вероятности эскейп-символа в ppm. Хочу 
пока просто проверить как работает моя prefix tree :-)

Daniil

--- GoldED+/386 1.1.5-20011130
 * Origin: Once Upon A Time In The West ... (2:5030/1551.7)


 RU.COMPRESS 
 From : Maxim Smirnov                        2:5020/400     17 Dec 01 09:11:07
 To   : Igor Kizhaev                        
 Subj : Вейвлеты                                                                     


From: "Maxim Smirnov" <model@iac.spb.ru>

Sat Dec 15 2001 03:59, Igor Kizhaev wrote to All:

 IK>       /\/\/\/\/\/\/\/\/\/\/I Приветус, All! I/\/\/\/\/\/\/\/\/\/\/\

 IK> Пpочитал в УФH за Май/2001 том 171 с 465 интеpесную статейку
 IK> "Вейвлеты и их использование".

 IK> Если кто знает, где можно найти матеpиал по теме
 IK> "использование вейвлет методов для сжатия инфоpмации",
 IK> то пpосьба - pассказать, либо указать адp., где можно найти.

попробуй
http://graphics.cs.msu.su/

Maxim

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)


 RU.COMPRESS 
 From : Maxim Smirnov                        2:5020/400     17 Dec 01 09:15:09
 To   : Daniil Uspensky                     
 Subj : \esc                                                                         


From: "Maxim Smirnov" <model@iac.spb.ru>

Sun Dec 16 2001 13:48, Daniil Uspensky wrote to All:

 DU> Предложите простенький метод вычисления вероятности эскейп-символа в ppm.
 DU> Хочу пока просто проверить как работает моя prefix tree :-)

Статический метод D подойдет?

esc = S/2C,
S -- кол-во символов
C -- кол-во появлений соотв-го контекста (в котором оценивается esc)

на текстах работает очень хорошо

Maxim

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)
 Предыдущий блок Следующий блок Вернуться в индекс