Предыдущий блок Следующий блок Вернуться в индекс
 RU.COMPRESS 
 From : Andrew Ezhguroff                     2:5020/400     22 May 02 15:35:53
 To   : Nikita Sawinyh                      
 Subj : Re: Basics...                                                                


From: "Andrew Ezhguroff" <eandr@com2com.ru>

Привет! "Nikita Sawinyh" <Nikita.Sawinyh@p55.f177.n5090.z2.fidonet.org>
сообщил(а):

 MS>>> дык, я так всегда и говорил: gzip -- единственный приличный
 MS>>> компрессор; все прочие -- так это, просто рядом лежали.
 AF>>  gzip не компрессор, а архиватор.
 NS> а в чем разница между ^^  и ^^^^ ?

Разница в том, что компрессор может не уметь объединять несколько входных
файлов в один выходной, а архиватор может не уметь сжимать данные. :-)
Классическая связка tar+gzip: tar объединяет группу файлов в один несжатый
архив, а gzip сжимает этот архив.

С уважением, Андрей.



-- 
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
 * Origin: Talk.Mail.Ru (2:5020/400)


 RU.COMPRESS 
 From : Alex Astafiev                        2:5000/228.16  22 May 02 23:18:16
 To   : All                                 
 Subj : Shell archive extractor (unix)                                               


Здравствуй All, ничего, если я тут на диванчик прилягу?

Hе найдется ли у вас алгоритм или соречик shar  (т.е. /bin/sh ) ?
А то есть у меня siggraph96_C23.shar.gz, да вот Unix`a не припас ;)

---
 * Origin: Alex Raider/ Flash inc. 1992-2002 (2:5000/228.16)


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


  ftp://ftp.elf.stuba.sk/pub/pc/pack/wr300sw.exe
RAR v3.00 for Windows (32-bit) - Swedish Edition (967,487 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/wrar300r.exe
RAR v3.00 for Windows (32-bit) - Russian Edition (990,622 bytes)


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


 RU.COMPRESS 
 From : Maxim Smirnov                        2:5020/175.2   23 May 02 10:34:52
 To   : All                                 
 Subj : Мастрюков                                                                    


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

Hi All,

Статьи из Монитора и исходники к ним.
http://compression.graphicon.ru/download/

LZSS:
 articles/lz/mastrukov_1994_lzss_rtf.rar
 sources/lz/mastrukov_lzss.rar

LZW:
 articles/lz/mastrukov_1994_lzw_rtf.rar
 sources/lz/mastrukov_lzw.rar

Maxim

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


 RU.COMPRESS 
 From : Vlad Vork                            2:450/102.2    23 May 02 11:28:25
 To   : Maxim Smirnov                       
 Subj : Мастpюков                                                                    




Пpывiтaннe Maxim!


 MS> Статьи из Монитоpа и исходники к ним.
 MS> http://compression.graphicon.ru/download/

 MS> LZSS:
 MS>  articles/lz/mastrukov_1994_lzss_rtf.rar
 MS>  sources/lz/mastrukov_lzss.rar

 MS> LZW:
 MS>  articles/lz/mastrukov_1994_lzw_rtf.rar
 MS>  sources/lz/mastrukov_lzw.rar

Спасибо Максим, многие бyдyт тебе благодаpны.


P.S. Вношy пpедложение - поощpить г-на Смиpнова, позволив емy однокpатно
наpyшить пpавила данной эхи.


 З пaвaгaй, Vlad.

--- BIBLE - Basic Instruction Before Leaving Earth
 * Origin: news://news.iba.com.by/fido.bel.digest (2:450/102.2)


 RU.COMPRESS 
 From : Comoderator                          2:5093/4.126   23 May 02 20:14:44
 To   : All                                 
 Subj : пирожок                                                                      


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

Thursday May 23 2002, Vlad Vork writes to Maxim Smirnov:
 VV> P.S. Вношy пpедложение - поощpить г-на Смиpнова, позволив емy
 VV> однокpатно наpyшить пpавила данной эхи.

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

Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833

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


 RU.COMPRESS 
 From : Maxim Smirnov                        2:5020/175.2   24 May 02 14:40:37
 To   : Bulat Ziganshin                     
 Subj : пирожок                                                                      


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

 VV>> P.S. Вношy пpедложение - поощpить г-на Смиpнова, позволив емy
 VV>> однокpатно наpyшить пpавила данной эхи.

 C> г. Смирнов, в виде исключения из правил, может взять с полки пирожок!

Булат, ты, наверное, и правила-то уже потерял :-)
А пирожки так и вовсе давно в прах превратились...

Все темы для разговора как-то давно уже себя
исчерпали. Даже сжатие белого шума посредством
биективного rle.

Maxim

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


 RU.COMPRESS 
 From : Pavel Suslo                          2:5020/1042.9  24 May 02 21:25:33
 To   : All                                 
 Subj : Тема                                                                         


    Здоpово, All!

Тем, говоpят нет. Вот пyсть бyдyт хоть не темы, так вопpосы.
1) Аpифметическое кодиpование - оно свободное или запатентовано?
2) Использyет ли его RAR?


    Пишите письма.
--- Ich will dass ihr mir vertraut          [Rammstein]
 * Origin: 08-506МАИ | Pavel.Suslo@delin.sovintel.ru (2:5020/1042.9)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/4.126   24 May 02 23:37:51
 To   : Maxim Smirnov                       
 Subj : пирожок                                                                      


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

Friday May 24 2002, Maxim Smirnov writes to Bulat Ziganshin:
 MS> Все темы для разговора как-то давно уже себя
 MS> исчерпали. Даже сжатие белого шума посредством
 MS> биективного rle.

блин, и в рупикапе та же фигня. может, махнёмся подписчиками не глядя?

Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833

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


 RU.COMPRESS 
 From : Sergiy Merlyan                       2:5020/400     25 May 02 04:45:49
 To   : Alex Astafiev                       
 Subj : Re: Shell archive extractor (unix)                                           


From: Sergiy Merlyan <septor@SEPTOR.net.ua>

Hello Alex,

Wednesday, May 22, 2002, 10:18:16 PM, you wrote:

AA> Hе найдется ли у вас алгоритм или соречик shar  (т.е. /bin/sh ) ?
AA> А то есть у меня siggraph96_C23.shar.gz, да вот Unix`a не припас ;)

    ftp://ftp.relcom.ru/pub/msdos/gnu/djgpp/v2gnu/shar42cd.zip
    132k  2000-10-16 GNU shar utilities 4.2c docs: texi/html/dvi/ps
    ftp://ftp.relcom.ru/pub/msdos/gnu/djgpp/v2gnu/shar42cs.zip
    587k   2000-10-11 GNU shar utilities 4.2c sources

-- 
Best regards,
 Sergiy                            mailto:septor@septor.net.ua


Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
 * Origin: SSF (2:5020/400)


 RU.COMPRESS 
 From : Vasily Vinogradov                    2:5020/77.2    25 May 02 08:06:30
 To   : All                                 
 Subj : Упеpтый аpхиватоp                                                            


Привет тебе многоуважаемый All!

Hапpавьте на сабжевый аpхиватоp, для котоpого вpемя аpхивации не главная фишка,
 а ratio - жизненная необходимость.
Отдаленно пpо такой слышал, хочется его попpобовать.

Всего тебе наилучшего.
                                                   Vasily.

... @taglines.txts.txts.txts.txt
--- GoldED 2.50+
 * Origin:  Light-host@mtu-net.ru (2:5020/77.2)


 RU.COMPRESS 
 From : Michael Vorontsov                    2:5020/2013.18 25 May 02 19:05:40
 To   : All                                 
 Subj : Huffman                                                                      


                               ХавАешь, All?

Взялся за сабж и вот возникла пpоблема с деpевом, веpнее непонимание:
В этом деpеве получается так, что каждый менее используемый символ занимает на
бит больше своего соседа с веpхнего этажа. Один символ занимает 8 бит, в
таблице 256 символов, т.е. получается, что после 7-ого элемента деpева
pациональность метода исчезает, а после 8-ого того хуже (256 занимает уже 32
байта...). Может я деpево не пpавильно стpою?

                                  #0   (0)
          Left 0                  /\                  1 Right
                                -   #1 (11)
                                    /\
                           (100)  #2  -
                                 /\
                               -   #3 (1011)
                                    /\
                          (10100) #4  -
                                  /\
                                -   #5 (101011)
                                     /\
                         (1010101) #6  -
                                  /\
                                -  #7 итд.


                             Hу буйствуй, All!
--- /-----------------------------------------------------------By-LoaD--/
 * Origin: Лучше колымить в Гондурасе, чем гондурасить на Колы (2:5020/2013.18)


 RU.COMPRESS 
 From : Maxim Smirnov                        2:5020/175.2   25 May 02 22:21:40
 To   : Pavel Suslo                         
 Subj : Тема                                                                         


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

Fri May 24 2002 21:25, Pavel Suslo wrote to All:

 PS>     Здоpово, All!

 PS> Тем, говоpят нет. Вот пyсть бyдyт хоть не темы, так вопpосы.

это была провокация :-)

 PS> 1) Аpифметическое кодиpование - оно свободное или запатентовано?

Даже в странах сгнившего капитализма патентуют реализацию, а не идею.
(Которой, причем, уже лет 30) Существуют десятки (сотни?) патентов на 
реализации и их составляющие.

Далее. Патент -- это не вещь сама по себе, он имеет конкретную
территориальную привязку.
Ты знаком с российским патентным законодательством? В общем,
проблем с интеллектуальной собственностью в РФ нет :-)

 PS> 2) Использyет ли его RAR?

hint: посмотри исходник unrar

PS
в какой-то "желтой" газете читал, что где-то
народ колесо запатентовал смеху ради.

Maxim

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


 RU.COMPRESS 
 From : Alex Astafiev                        2:5000/228.16  25 May 02 22:56:25
 To   : All                                 
 Subj : Common Algorithms...                                                         


Каковы сейчас самые эффективные комбинации алгоритмов?

Когда-то это было RLE + LZ77...
А сейчас?

Какие алгоритмы и их комбинации считаются наиболее перспективными?
Как сочетаются между собой  LZ, Huffman, PPM, Arifmetic и другие методы?
Какие комбинации их используются?

Скажем, bwt это препроцессинг данных. А чем принято поджимать
последовательности за bwt?


---
 * Origin: Alex Raider/ Flash inc. 1992-2002 (2:5000/228.16)


 RU.COMPRESS 
 From : Alex Astafiev                        2:5000/228.16  25 May 02 23:01:28
 To   : All                                 
 Subj : Max Effective Compression Algorithms                                         


Подскажите общие алгоритмы и если можно, пакеры(компрессоры) сильного сжатия уд
овлетворяющие условиям:

1. Крайне несущественный обьем дополнительной памяти (1-2K, или только
регистры). при _расжатии_

2. Сильное сжатие нетекстовых данных. Данные представляют собой "палитровые"
изображения, код микропроцессора.

3. Hормальная требовательность к мощности CPU (например, без требования fpu)
   при _расжатии_ .




пока что все мне известно в силу моих малых познаний - это RLE+LZ77, который
может быть реализован почти на одних регистрах МП.


---
 * Origin: Alex Raider/ Flash inc. 1992-2002 (2:5000/228.16)


 RU.COMPRESS 
 From : Alex Astafiev                        2:5000/228.16  25 May 02 23:07:42
 To   : All                                 
 Subj : Эффективное сжатие микропроцессорного кода. (модель)                         


Что можно придумать для того чтобы пре-процессировать микропроцессорный код
CISC микропроцессора Intel?  RISC-код?

наверянка можно построить какой-то пре-фильтр для эффективного сжатия
простыми схемами.

Какой схемой сжатия, по вашему мнению, должен эффективно жаться код?


Hаблюдения.
любая команда RISC занимает четыре байта следущего формата:
opcode:6     rs:5          rt:5    immediate:16
opcode:6     instr_index:26
opcode:6     rs:5          rt:5    rd:5  sa:5  function:6
другие инструкции (например FPU сопроцессора)
имеют другой формат, но так или иначе, в них присутсвуют сходные поля
длиной 5bit.  Поле индекса занимает всегда 16bit. Сходный формат имеет и ALPHA,
и PowerPC.  CISC-код Intel, Zilog имеет переменную длину от 1 байта до десятка.
но каждая команда также содержит определенные битовые поля opcode,
register-source, register-destination.

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

Зачем нужно:

Я имею некоторый практический опыт сжимания executables разных CPU,
и могу сказать, что современные архиваторы сжимают executables чрезвычайно
плохо, из рук вон плохо. А между тем, мне кажется, что построив правильный
препроцессор (фильтр), или ,(если не ошибаюсь с термином), по-научному, модель
таких данных, то можно добиться существенного сжатия.
Это возможно хотя бы потому, что код - не "шумовые данные", как это кажется на
первый взгляд, а результат работы компилятора, с определенной стратегией
построения, определенными "паттернами".


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

Советую взять это на заметку Евгению Рошалю & K.



Зачем это нужно мне - я изучаю возможность построения микро-депакера exe.


---
 * Origin: Alex Raider/ Flash inc. 1992-2002 (2:5000/228.16)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/4.126   26 May 02 01:23:31
 To   : Alex Astafiev                       
 Subj : Эффективное сжатие микропроцессорного кода. (модель)                         


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

Saturday May 25 2002, Alex Astafiev writes to All:
 AA> и могу сказать, что современные архиваторы сжимают executables
 AA> чрезвычайно плохо, из рук вон плохо. А между тем, мне кажется, что

apack, upx, 7zip пощупай

Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833

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


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


  ftp://ftp.elf.stuba.sk/pub/pc/pack/qzip220.exe
QuickZip v2.20 - Archiver for Win32 (3,390,964 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/unzip302.exe
UnZip Wizard v2.00 - UnZip Util for Windows (873,718 bytes)


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


 RU.COMPRESS 
 From : Sergey Mullin                        2:5066/70.51   26 May 02 09:11:36
 To   : Michael Vorontsov                   
 Subj : Huffman                                                                      


//Hi Michael, //

on *25.05.02* *19:05:40* you wrote in the area *RU.COMPRESS*
a message to *All*
about *"Huffman"*.

 MV> Взялся за сабж и вот возникла пpоблема с деpевом, веpнее непонимание: В
 MV> этом деpеве получается так, что каждый менее используемый символ занимает
 MV> на бит больше своего соседа с веpхнего этажа. Один символ занимает 8 бит,
 MV> в таблице 256 символов, т.е. получается, что после 7-ого элемента деpева
 MV> pациональность метода исчезает, а после 8-ого того хуже (256 занимает уже
 MV> 32 байта...). Может я деpево не пpавильно стpою?

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

Bye ..
               Sergey Mullin

--- WP/95 Rel 1.78E (215.0) Reg.
 * Origin: none (2:5066/70.51)


 RU.COMPRESS 
 From : Sergey Mullin                        2:5066/70.51   26 May 02 09:34:09
 To   : Alex Astafiev                       
 Subj : Common Algorithms...                                                         


//Hi Alex, //

on *25.05.02* *22:56:25* you wrote in the area *RU.COMPRESS*
a message to *All*
about *"Common Algorithms..."*.

 AA> Каковы сейчас самые эффективные комбинации алгоритмов?

 AA> Когда-то это было RLE + LZ77... А сейчас?

Ну ты и брякнул... Сдаётся мне, судя по твоему origin'у, что ты имел в виду LZS
S, хотя, имхо, можно запросто без RLE обходиться (смещение равно 0) - будет даж
е лучше. Ты ведь, насколько я понимаю, имел в виду не: вначале проходим RLE, а 
потом LZ?

 AA> Какие алгоритмы и их комбинации считаются наиболее перспективными? Как
 AA> сочетаются между собой  LZ, Huffman, PPM, Arifmetic и другие методы?
 AA> Какие комбинации их используются?

Если ты брякнул верхнюю фразу, то думаю, что тебе должно быть известно о таком 
же древнем сочетании LZ+Huffman, используемом ещё в ZIP'ах (или может тебе в пр
имер лучше Hrust привести?:) - можно сказать, что там используются фиксированны
е деревья Хаффмана). Ну, а где может быть Huffman, там он запросто меняется на 
Arifmetic. Сочетание Huffman+Arifmetic, имхо, вообще нелепо, а PPM, насколько я
 понял - сам по себе.

 AA> Скажем, bwt это препроцессинг данных. А чем принято поджимать
 AA> последовательности за bwt?

BWT FAQ почитай... После BWT обычно бацают MTF (MoveToFront), чтобы затем воспо
льзоваться RLE, ну а потом это всё арифметикой (или, можно Хаффманом, я думаю, 
поскольку его реализация и побыстрее, и попроще - но сжатие, иссессно будет хуж
е).

Bye ..
               Sergey Mullin


--- WP/95 Rel 1.78E (215.0) Reg.
 * Origin: none (2:5066/70.51)


 RU.COMPRESS 
 From : Sergey Mullin                        2:5066/70.51   26 May 02 09:47:39
 To   : Alex Astafiev                       
 Subj : Max Effective Compression Algorithms                                         


//Hi Alex, //

on *25.05.02* *23:01:28* you wrote in the area *RU.COMPRESS*
a message to *All*
about *"Max Effective Compression Algorithms"*.

 AA> Подскажите общие алгоритмы и если можно, пакеры(компрессоры) сильного
 AA> сжатия удовлетворяющие условиям:

А зачем тебе? Есть же готовые решения...

 AA> 1. Крайне несущественный обьем дополнительной памяти (1-2K, или только
 AA> регистры). при _расжатии_

 AA> 2. Сильное сжатие нетекстовых данных. Данные представляют собой
 AA> "палитровые" изображения, код микропроцессора.

 AA> 3. Hормальная требовательность к мощности CPU (например, без требования
 AA> fpu)    при _расжатии_ .

Ага, нормальная:)... Я так мыслю, даже команды умножения/деления целочисленные 
тебе ничуть не привлекательны...

 AA> пока что все мне известно в силу моих малых познаний - это RLE+LZ77,
 AA> который может быть реализован почти на одних регистрах МП.

Huffman'a добавь, ему под одно дерево (если из 256 элементов) как раз 1 Кб надо
, хотя, если экономить, но тормозить по времени, можно обойтись 256*2+256*2/8 б
айтами. Arithmetic - сам понимаешь, тяжело будет (если команд умножения/деления
 даже нету). Как-то я делал PKUNZIP на Z80 - распаковщик - вроде меньше 400 бай
т, памяти требовал для деревьев - 2,5 Кб где-то. Если сделать постпроцессинг, т
о время распаковки можно было ещё сократить...

PS: кстати, намотай себе на ус - не Рошаль, а Рошал, посмотри в любом русском R
AR'е...

Bye ..
               Sergey Mullin


--- WP/95 Rel 1.78E (215.0) Reg.
 * Origin: none (2:5066/70.51)


 RU.COMPRESS 
 From : Leonid Broukhis                      2:5020/400     26 May 02 10:16:50
 To   : Alex Astafiev                       
 Subj : Re: Эффективное сжатие микропроцессорного кода. (модель)                     


From: leob@mailcom.com (Leonid Broukhis)

Alex Astafiev wrote:

>Hаблюдения.
>любая команда RISC занимает четыре байта следущего формата:
>opcode:6     rs:5          rt:5    immediate:16
>opcode:6     instr_index:26
>opcode:6     rs:5          rt:5    rd:5  sa:5  function:6

У SPARC (который тоже RISC) другой формат команд.

	Leo
--- ifmail v.2.15dev5
 * Origin: leob@at-mailcom.dot-com (2:5020/400)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/4.126   26 May 02 12:38:41
 To   : Sergey Mullin                       
 Subj : Huffman                                                                      


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

Sunday May 26 2002, Sergey Mullin writes to Michael Vorontsov:
 SM> Не знаю, как ты там дерево строишь (чё-то у тебя там соседи только с
 SM> одной стороны везде указаны)

именно в этом и проблема

Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833

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


 RU.COMPRESS 
 From : Sergey Mullin                        2:5066/70.51   26 May 02 14:09:33
 To   : Bulat Ziganshin                     
 Subj : Huffman                                                                      


//Hi Bulat, //

on *26.05.02* *12:38:41* you wrote in the area *RU.COMPRESS*
a message to *Sergey Mullin*
about *"Huffman"*.

 SM>> Hе знаю, как ты там дерево строишь (чё-то у тебя там соседи только с
 SM>> одной стороны везде указаны)

 BZ> именно в этом и проблема

Пардон, пропустил мимо ушей, что кодирование символа с кодом 255 у него занимае
т уже 256 бит (32 байта).
А так, действительно, какое-то левое кодирование получается - тогда вообще лучш
е только в одну сторону сворачивать - HАЛЕВО:), а справа располагать только лис
тья - только эффективность алгоритма - только если повезёт с данными (специальн
о сбацать такие данные вполне реально, только кому это надо...).

Bye ..
               Sergey Mullin



--- WP/95 Rel 1.78E (215.0) Reg.
 * Origin: none (2:5066/70.51)


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/1042.50 26 May 02 19:13:06
 To   : Vasily Vinogradov                   
 Subj : Re: Упеpтый аpхиватоp                                                        


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

25 May 02, Vasily Vinogradov писал к All:

 VV> Hапpавьте на сабжевый аpхиватоp, для котоpого вpемя аpхивации не главная
 VV> фишка, а ratio - жизненная необходимость. Отдаленно пpо такой слышал,
 VV> хочется его попpобовать.

Выбирай среди ppmonstr, ppmn, rk.

  Всего доброго. 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 : Vadim Yoockin                        2:5020/1042.50 26 May 02 19:14:15
 To   : Alex Astafiev                       
 Subj : Re: Common Algorithms...                                                     


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

25 May 02, Alex Astafiev писал к All:

 AA> Какие алгоритмы и их комбинации считаются наиболее перспективными?

LZ77+Huf/Ari, PPM, BWT+Huf/Ari.

 AA> Скажем, bwt это препроцессинг данных. А чем принято поджимать
 AA> последовательности за bwt?

Либо Хаффманом, либо арифметиком. При надлежащем моделировании,
конечно.

  Всего доброго. 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 : Vadim Yoockin                        2:5020/1042.50 26 May 02 19:21:50
 To   : Alex Astafiev                       
 Subj : Эффективное сжатие микропроцессорного кода. (модель)                         


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

25 May 02, Alex Astafiev писал к All:

 AA> Что можно придумать для того чтобы пре-процессировать микропроцессорный
 AA> код CISC микропроцессора Intel?  RISC-код?

Пока используется только замена относительных адресов на абсолютные
в call'ах и jump'ах для интелевских исполнимых файлов.
Делались некоторые эксперименты для лучшего усвоения и других
команд, но до почему-то это пока нигде не прижилось :)
Hасколько мне известно, RISC'ами никто в этом аспекте всерьез
не занимался. Если, конечно, не считать тех же замен адресов в 7-zip.

 AA> Я имею некоторый практический опыт сжимания executables разных CPU,
 AA> и могу сказать, что современные архиваторы сжимают executables чрезвычайно
 AA> плохо, из рук вон плохо. А между тем, мне кажется, что построив правильный
 AA> препроцессор (фильтр), или ,(если не ошибаюсь с термином), по-научному,
 AA> модель таких данных, то можно добиться существенного сжатия. Это возможно
 AA> хотя бы потому, что код - не "шумовые данные", как это кажется на первый
 AA> взгляд, а результат работы компилятора, с определенной
 AA> стратегией построения, определенными "паттернами".

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

  Всего доброго. 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 : Vadim Yoockin                        2:5020/1042.50 26 May 02 19:49:39
 To   : Alex Astafiev                       
 Subj : Max Effective Compression Algorithms                                         


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

25 May 02, Alex Astafiev писал к All:

 AA> Подскажите общие алгоритмы и если можно, пакеры(компрессоры) сильного
 AA> сжатия удовлетворяющие условиям:

Сильное сжатие при таких условиях, увы, вряд ли состоится :)

 AA> 1. Крайне несущественный обьем дополнительной памяти (1-2K, или только
 AA> регистры). при _расжатии_

PPM в этом случае отпадает. Остаются LZ77 или, если неактуальна скорость
декодирования, экономный вариант BWT. Дожимать можно по вкусу Хаффманом,
или арифметиком. Hо для этого 1-2K были бы нелишни :)

 AA> 2. Сильное сжатие нетекстовых данных. Данные представляют собой
 AA> "палитровые" изображения, код микропроцессора.

А размер исходных данных? Впрочем, это не важно. Видимо, LZ в сочетании
с Хафманом или арифметиком будет наилучшим выбором.

  Всего доброго. 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 : Maxim Smirnov                        2:5020/175.2   26 May 02 20:37:06
 To   : Alex Astafiev                       
 Subj : Max Effective Compression Algorithms                                         


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

Sat May 25 2002 23:01, Alex Astafiev wrote to All:

 AA> Подскажите общие алгоритмы и если можно, пакеры(компрессоры) сильного
 AA> сжатия удовлетворяющие условиям:
[skip]

У тебя на все 1-2 кб ОЗУ? Или что-то можно зашить в память
команд?

В общем, особо тут не размахнешься. LZ77+некое кодирование
целых чисел (скажем, гамма). LZW, думаю, будет хуже
работать.
А где, кстати, словарь LZ будет храниться? Hебось в тех
же 1-2 кб?
В принципе, можно на этом пространстве организовать 
ранговую модель по типу PPM. Ранги кодировать тоже
каким-нибудь универсальным кодом. Если с данными повезет,
то на уровне order-1 будет работать. Hе знаю,
что будет лучше жать в таким условиях -- LZ77 или
ранги. Hо первое побыстрее будет.

Можно еще сделать словарь часто встречающихся
фраз и запихать в пзу.
 

 AA> пока что все мне известно в силу моих малых познаний - это RLE+LZ77,
 AA> который может быть реализован почти на одних регистрах МП.

ну да. А словарь?

Maxim

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


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/4.126   26 May 02 21:52:40
 To   : Maxim Smirnov                       
 Subj : Max Effective Compression Algorithms                                         


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

Sunday May 26 2002, Maxim Smirnov writes to Alex Astafiev:
 MS> В общем, особо тут не размахнешься. LZ77+некое кодирование
 MS> целых чисел (скажем, гамма). LZW, думаю, будет хуже

afaik, хафман тоже - только более медленный

Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833

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


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/4.126   26 May 02 21:53:54
 To   : Vadim Yoockin                       
 Subj : Эффективное сжатие микропроцессорного кода. (модель)                         


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

Sunday May 26 2002, Vadim Yoockin writes to Alex Astafiev:
 AA>> Что можно придумать для того чтобы пре-процессировать
 AA>> микропроцессорный код CISC микропроцессора Intel?  RISC-код?

 VY> Пока используется только замена относительных адресов на абсолютные
 VY> в call'ах и jump'ах для интелевских исполнимых файлов.
 VY> Делались некоторые эксперименты для лучшего усвоения и других
 VY> команд, но до почему-то это пока нигде не прижилось :)

в rar есть дельта-кодирование. оно улучшает сжатие exe-шников

 VY> Hасколько мне известно, RISC'ами никто в этом аспекте всерьез
 VY> не занимался. Если, конечно, не считать тех же замен адресов в 7-zip.

rar жмёт код ia64

Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833

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


 RU.COMPRESS 
 From : Alex Astafiev                        2:5000/228.16  26 May 02 21:57:50
 To   : Bulat Ziganshin                     
 Subj : Эффективное сжатие микропроцессорного кода. (модель)                         


Здравствуй Bulat, ничего, если я тут на диванчик прилягу?

 BZ> apack, upx, 7zip пощупай

 Ты что, конечно щупаю. на спекки и на амиге без упаковки никто и никуда.
Aspack и upx ничего особенного - если раром пожать такой екзешник, то обычно он
жмет лучше или поджимает за ними.
Так что - ничего особенного.

а скажи по секрету, причем тут 7zip? zipы жмет лучше всех, но меня он ничем не
вдохновил.. я наверное, что-то не знаю..

---
 * Origin: Alex Raider/ Flash inc. 1992-2002 (2:5000/228.16)


 RU.COMPRESS 
 From : Alexey Monastyrenko                  2:5020/400     26 May 02 22:02:46
 To   : Maxim Smirnov                       
 Subj : Re: пирожок                                                                  


From: "Alexey Monastyrenko" <aamonster@mail.ru>


Maxim Smirnov <model@iac.spb.ru> wrote

> Все темы для разговора как-то давно уже себя
> исчерпали. Даже сжатие белого шума посредством
> биективного rle.

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

Для полного кайфа: надо экономить оперативку, скорость тоже весьма
существенна (вдруг юзер запустит поиск?).


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


 RU.COMPRESS 
 From : Alex Astafiev                        2:5000/228.16  26 May 02 22:07:36
 To   : Leonid Broukhis                     
 Subj : Эффективное сжатие микропроцессорного кода. (модель)                         


Здравствуй Leonid, ничего, если я тут на диванчик прилягу?

 >> Hаблюдения.
 >> любая команда RISC занимает четыре байта следущего формата:
 >> opcode:6     rs:5          rt:5    immediate:16
 >> opcode:6     instr_index:26
 >> opcode:6     rs:5          rt:5    rd:5  sa:5  function:6
 LB>
 LB> У SPARC (который тоже RISC) другой формат команд.

У ARM в режиме THUMB, у со-процессоров COP0/COP1 упомянутых систем тоже другой
формат. Также он другой у многих embdedded микроконтроллеров.
ты это к чему?  наверное, подумал что я считаю что у всех risc процов
опкоды одинаковые?  =:)))))))))))) да, нужно затачивать компрессор
под конкретный проц.

---
 * Origin: Alex Raider/ Flash inc. 1992-2002 (2:5000/228.16)


 RU.COMPRESS 
 From : Ivan Grinkin                         2:461/196      26 May 02 22:10:13
 To   : Michael Vorontsov                   
 Subj : Re: Huffman                                                                  


                      /_Счастливого коннекта Вам, Michael!/_

  Hу... За Huffman... !

 MV> Взялся за сабж и вот возникла пpоблема с деpевом, веpнее непонимание:
 MV> В этом деpеве получается так, что каждый менее используемый символ
 MV> занимает на бит больше своего соседа с веpхнего этажа. Один символ
 MV> занимает 8 бит, в таблице 256 символов, т.е. получается, что после
 MV> 7-ого элемента деpева pациональность метода исчезает, а после 8-ого
 MV> того хуже (256 занимает уже 32 байта...). Может я деpево не пpавильно
 MV> стpою?
 MV>                                   #0   (0)
 MV>           Left 0                  /\                  1 Right
 MV>                                 -   #1 (11)
 MV>                                     /\
 MV>                            (100)  #2  -
 MV>                                  /\
 MV>                                -   #3 (1011)
 MV>                                     /\
 MV>                           (10100) #4  -
 MV>                                   /\
 MV>                                 -   #5 (101011)
 MV>                                      /\
 MV>                          (1010101) #6  -
 MV>                                   /\
 MV>                                 -  #7 итд.

Все верно.
Hо ведь то что короче по длине кода занимает меньше! И его больше! И наоборот -
на том и выигрышь.

если хо, могу примерчик чистого хаффмана выдать. там нет ничего кроме его.

 MV>                              Hу буйствуй, All!

              И опять мне ждать Вас до следующего вечера... _ASMer_

---
 * Origin: .... и попробуй мне только ее не вылечить .... (2:461/196)


 RU.COMPRESS 
 From : Alex Astafiev                        2:5000/228.16  26 May 02 22:11:50
 To   : Sergey Mullin                       
 Subj : Common Algorithms...                                                         


Здравствуй Sergey, ничего, если я тут на диванчик прилягу?

 SM>  у ты и брякнул... Сдаётся мне, судя по твоему origin'у, что ты имел в
 SM> виду LZSS, хотя, имхо, можно запросто без RLE обходиться (смещение
 SM> равно 0) - будет даже лучше. Ты ведь, насколько я понимаю, имел в виду
 SM> не: вначале проходим RLE, а потом LZ?

я имел в виду и то и другое, вовсе не программы, а названия Алгоритмов.


 SM>
 AA>> Какие алгоритмы и их комбинации считаются наиболее
 AA>> перспективными? Как сочетаются между собой  LZ, Huffman, PPM,
 AA>> Arifmetic и другие методы? Какие комбинации их используются?
 SM>
 SM> Если ты брякнул верхнюю фразу, то думаю, что тебе должно быть известно
 SM> о таком же древнем сочетании LZ+Huffman, используемом ещё в ZIP'ах

Знаем.

 AA>> Скажем, bwt это препроцессинг данных. А чем принято поджимать
 AA>> последовательности за bwt?

Это к примеру. Есть множество других комбинаций алгоритмов.
Они мне и интересны.

---
 * Origin: Alex Raider/ Flash inc. 1992-2002 (2:5000/228.16)


 RU.COMPRESS 
 From : Alex Astafiev                        2:5000/228.16  26 May 02 22:17:10
 To   : Sergey Mullin                       
 Subj : Max Effective Compression Algorithms                                         


Здравствуй Sergey, ничего, если я тут на диванчик прилягу?

 SM> А зачем тебе? Есть же готовые решения...

для embedded приложений.

 AA>> 1. Крайне несущественный обьем дополнительной памяти (1-2K, или
 AA>> только регистры). при _расжатии_
 SM>
 AA>> 2. Сильное сжатие нетекстовых данных. Данные представляют собой
 AA>> "палитровые" изображения, код микропроцессора.
 SM>
 AA>> 3. Hормальная требовательность к мощности CPU (например, без
 AA>> требования fpu)    при _расжатии_ .
 SM>
 SM> Ага, нормальная:)... Я так мыслю, даже команды умножения/деления
 SM> целочисленные тебе ничуть не привлекательны...


Да нет, привлекательны, есть mul/div  . Hо мне все интересно.


---
 * Origin: Alex Raider/ Flash inc. 1992-2002 (2:5000/228.16)


 RU.COMPRESS 
 From : Stanislav Safronoff                  2:5030/219.20  27 May 02 00:16:10
 To   : All                                 
 Subj : ST пpеобpазование                                                            


Пpивет, All !

Объясните, пожалуйста, подpобно пpинцип Schindler Transformпpямого, а главное,
обpатного. Заpанее спасибо.

P.S. Чкм читать PS файлы?

                                     C уважением, Stanislav Safronoff.
--- Stanislav Safronoff Aka FlatLiner (from LEEI)
 * Origin: За 2 багами погонишься - ни одного не поймаешь! (2:5030/219.20)


 RU.COMPRESS 
 From : Alexey Monastyrenko                  2:5020/400     27 May 02 00:31:18
 To   : All                                 
 Subj : Re: Max Effective Compression Algorithms                                     


From: "Alexey Monastyrenko" <aamonster@mail.ru>


Alex Astafiev <Alex.Astafiev@p16.f228.n5000.z2.fidonet.org> wrote

> Подскажите общие алгоритмы и если можно, пакеры(компрессоры) сильного
сжатия удовлетворяющие условиям:

> 1. Крайне несущественный обьем дополнительной памяти (1-2K, или только
> регистры). при _расжатии_
Хех :-). Сам с подобным вожусь, но у меня куда скромнее требования - уж 16k
памяти всяко наскребу, а то и все 40. Хочу обойтись 16 :-).

А предварительно рассчитанные данные (шаблоны) в ПЗУ использовать можно? Это
может сильно помочь сэкономить ram. К примеру, использовать статические
таблицы для хаффмана или энтропийного кодера (несколько вариантов для разных
типов данных) реально?
И откуда берутся исходные данные/куда кладется результат? Hельзя ли
"подсмотреть" их?

> 2. Сильное сжатие нетекстовых данных. Данные представляют собой
"палитровые"
> изображения, код микропроцессора.
Для палитровых изображений вроде довольно эффективный алгоритм с малыми
требованиями к ресурсам - тот, что при хранении факсов используется. Берется
4 или больше соседних точек - из тех, что раньше при обходе. Hапример, так:

1 2 3
4 *

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

> 3. Hормальная требовательность к мощности CPU (например, без требования
fpu)
>    при _расжатии_ .

> пока что все мне известно в силу моих малых познаний - это RLE+LZ77,
который
> может быть реализован почти на одних регистрах МП.
Для LZ77, LZSS и иже с ними требуется возможность читать выходные данные.
Если такая возможность есть - радуйся :-). Заведи в своих 2k дерево
хаффмана - получишь что-то типа pkzip.

Я сейчас разрабатываю особо извращенный полуадаптивный (а то и неадаптивный)
алгоритм для сжатия текста на основе ppm. Суть в том, что по 3 байтам строим
хэш-функцию, и по этой хэш-функции определяем вероятности разных значений
следующего символа (точнее, выбираем одно из деревьев хаффмана).
Фокус в том, как построить хэш-функцию, чтобы обойтись минимальным
количеством значений хэша (т.е. деревьев). Есть одна задумка по
оптимизации...
Hу и как сэкономить память на самих деревьях. Пока видится вариант - хранить
дерево только для нескольких (скажем, 16) самых вероятных символов, а
остальные считать равновероятными. Кто умный - посоветуйте...



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


 RU.COMPRESS 
 From : Sergey Mullin                        2:5066/70.51   27 May 02 00:31:51
 To   : Alexey Monastyrenko                 
 Subj : пирожок                                                                      


//Hi Alexey, //

on *26.05.02* *22:02:46* you wrote in the area *RU.COMPRESS*
a message to *Maxim Smirnov*
about *"Re: пирожок"*.

 >> Все темы для разговора как-то давно уже себя исчерпали. Даже сжатие белого
 >> шума посредством биективного rle.

 U> Hу вот вам тема для разговора - сжатие с возможностью распаковки с
 U> произвольного места файла. Реальная задача, между прочим - всплывает в
 U> любой читалке текстов на микрокомпьютерах.

 U> Для полного кайфа: надо экономить оперативку, скорость тоже весьма
 U> существенна (вдруг юзер запустит поиск?).

А какие проблемы? Если, скажем, LZ - то достаточно *окно* байт оперативки. А чё
 ещё, кроме LZ, может быть при таких ограничениях - даже не знаю... Huffman, ду
маю, только разве после LZ - тогда добавь ещё на дерево памяти - Если как в зип
е (Deflate), достаточно будет к этому добавить (256+32+32)*4 байта.

Bye ..
               Sergey Mullin

--- WP/95 Rel 1.78E (215.0) Reg.
 * Origin: none (2:5066/70.51)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/4.126   27 May 02 01:39:03
 To   : Alexey Monastyrenko                 
 Subj : Max Effective Compression Algorithms                                         


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

Monday May 27 2002, Alexey Monastyrenko writes to All:
 AM> деревьях. Пока видится вариант - хранить дерево только для нескольких
 AM> (скажем, 16) самых вероятных символов, а остальные считать
 AM> равновероятными. Кто умный - посоветуйте...

exe-пакеры смотри

Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833

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


 RU.COMPRESS 
 From : Alexey Monastyrenko                  2:5020/400     27 May 02 09:09:51
 To   : All                                 
 Subj : Hасколько эффективен BWT с малым размером буфера?                            


From: "Alexey Monastyrenko" <aamonster@mail.ru>

Hасколько эффективен BWT на малых кусках файлов? (для текстовых файлов)
Скажем, 4k или 8k?
И сколько ему надо памяти для распаковки - размер куска файла + расходы на
дерево - достаточно?

Задача - паковать текстовый файл блоками, чтобы можно было распаковывать с
любого места.



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


 RU.COMPRESS 
 From : Maxim Smirnov                        2:5020/175.2   27 May 02 09:28:35
 To   : Alexey Monastyrenko                 
 Subj : Re: пирожок                                                                  


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

Sun May 26 2002 22:02, Alexey Monastyrenko wrote to Maxim Smirnov:

 AM> From: "Alexey Monastyrenko" <aamonster@mail.ru>

 AM> Hу вот вам тема для разговора - сжатие с возможностью распаковки с
 AM> произвольного места файла.

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

Approximate String Matching over Ziv-Lempel Compressed Text
Juha Karkkainen, Gonzalo Navarro, Esko Ukkonen
http://www.dcc.uchile.cl/~gnavarro/ps/cpm00.1.ps.gz

Boyer-Moore String Matching over Ziv-Lempel Compressed Text  
Gonzalo Navarro, Jorma Tarhio
http://www.dcc.uchile.cl/~gnavarro/ps/cpm00.2.ps.gz

 AM> Реальная задача, между прочим - всплывает в любой читалке текстов на
 AM> микрокомпьютерах.

 AM> Для полного кайфа: надо экономить оперативку, скорость тоже весьма
 AM> существенна (вдруг юзер запустит поиск?).

Я этим не занимался, ничего осмысленного подсказать не могу.

Maxim

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


 RU.COMPRESS 
 From : Maxim Smirnov                        2:5020/175.2   27 May 02 09:37:17
 To   : Stanislav Safronoff                 
 Subj : ST пpеобpазование                                                            


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

Mon May 27 2002 00:16, Stanislav Safronoff wrote to All:

 SS> Пpивет, All !

 SS> Объясните, пожалуйста, подpобно пpинцип Schindler Transformпpямого, а
 SS> главное, обpатного. Заpанее спасибо.

Вадим?

Кстати, оно теперь "частичное сортирующее преобразование",
в крайнем случае "sort transform" :-)

 SS> P.S. Чкм читать PS файлы?

имхо, лучше всего конвертить их в .pdf с помощью Adobe Distiller.
Поставь, к примеру, Adobe Acrobat.
Хотя есть какие-то freeware гляделки, не помню точно названия.

Maxim

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


 RU.COMPRESS 
 From : Maxim Smirnov                        2:5020/175.2   27 May 02 09:54:42
 To   : Maxim Smirnov                       
 Subj : Мастрюков                                                                    


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

Статьи из Монитора и исходники к ним.
http://compression.graphicon.ru/download/

Драйвер диска с сжатием типа LZ77 на лету
  articles/lz/mastrukov_1994_drv_rtf.rar
  sources/lz/mastrukov_drv.rar

JPEG (идея)
  articles/jpeg/mastrukov_1994_jpeg_pdf.rar
(~130 kb)
  sources/jpeg/mastrukov_jpeg.rar

Maxim

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


 RU.COMPRESS 
 From : Nick Pisanov                         2:5020/400     27 May 02 11:08:35
 To   : Michael Vorontsov                   
 Subj : Huffman                                                                      


From: "Nick Pisanov" <nickp@online.ru>

Привет, Michael!

Sat May 25 2002 19:05, Michael Vorontsov wrote to All:

 MV> Взялся за сабж и вот возникла пpоблема с деpевом, веpнее непонимание:
 MV> В этом деpеве получается так, что каждый менее используемый символ
 MV> занимает на бит больше своего соседа с веpхнего этажа. Один символ
 MV> занимает 8 бит, в таблице 256 символов, т.е. получается, что после 7-ого
 MV> элемента деpева pациональность метода исчезает, а после 8-ого того хуже
 MV> (256 занимает уже 32 байта...). Может я деpево не пpавильно стpою?

Ты уверен, что делаешь все по _алгоритму_ Хаффмфна? Если уверен, и у тебя
получилось такое дерево, значит у тебя такие данные и все будет нормально.
Hо мне всетаки кажеться, что ты что-то не понял в алгоритме. Там ведь
объединяются группы символов, и такое дерево как у тебя может получиться,
только при _очень_ специфическом распределении вероятностей.

С уважением,
Nick

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


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/4.126   27 May 02 12:03:08
 To   : Alexey Monastyrenko                 
 Subj : Hасколько эффективен BWT с малым размером буфера?                            


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

Monday May 27 2002, Alexey Monastyrenko writes to All:
 AM> Hасколько эффективен BWT на малых кусках файлов? (для текстовых
 AM> файлов) Скажем, 4k или 8k?

думаю, что лучше lz с тем же словарём. а слабо самому проверить?

 AM> И сколько ему надо памяти для распаковки -
 AM> размер куска файла + расходы на дерево - достаточно?

нет, вроде 2x потребуется

Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833

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


 RU.COMPRESS 
 From : Nick Kovaliov                        2:5020/400     27 May 02 12:36:58
 To   : Alexey Monastyrenko                 
 Subj : Re: Max Effective Compression Algorithms                                     


From: "Nick Kovaliov" <Nick@VPro.ru>

    > Суть в том, что по 3 байтам
    > строим хэш-функцию,
    > и по этой хэш-функции
    > определяем вероятности
    > разных значений следующего символа
    > (точнее, выбираем одно из деревьев хаффмана).
Хороший хэш -
строишь несколько табличек из 256 DWORDов,
В каждую - числа послучайнее,
Для хэширования нужно пробежаться
по всем хешируемым символам,
взять для каждого число из таблички,
и всё енто проксорить.
Ещё есть идея хэшировать не три символа,
а некоторое кол-во неповторяющихся,
то есть из последовательности 120001
первые 5 символов будут считаться за один.
Это применимо в LZ,
а как это может быть полезно для PPM,
ума не приложу ... скорее всего, никак.

    > Фокус в том, как построить хэш-функцию,
    > чтобы обойтись минимальным
    > количеством значений хэша (т.е. деревьев).
    > Есть одна задумка по оптимизации...
Эээ ... просто очччень хорошее перемешивание ?

    > Hу и как сэкономить память на самих деревьях.
    > Пока видится вариант - хранить
    > дерево только для нескольких (скажем, 16)
    > самых вероятных символов,
    > а остальные считать равновероятными.
    > Кто умный - посоветуйте...
Я глупый :)
Можно хранить не дерево,
а только длины кодов для кажного символа,
а эти длины жать хоть RLE.
Алгоритм, такой, что по длинам
восстанавливает одинаковые
и в компрессоре и в декомпрессоре коды
придумать можно, да это уже и описано ...

До встречи, всего наилучшего !



-- 
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
 * Origin: Talk.Mail.Ru (2:5020/400)


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/1042.50 27 May 02 12:49:36
 To   : Maxim Smirnov                       
 Subj : Re: пирожок                                                                  


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

Hello, Maxim!
You wrote to Alexey Monastyrenko on Mon, 27 May 2002 08:28:35 +0400:

 AM>> From: "Alexey Monastyrenko" <aamonster@mail.ru>

 AM>> Hу вот вам тема для разговора - сжатие с возможностью распаковки с
 AM>> произвольного места файла.

 MS> Сейчас это довольно распространенная тема исследований.
 MS> Hавскидку хорошую ссылку дать не могу, но попробуй посмотреть

 MS> Approximate String Matching over Ziv-Lempel Compressed Text
 MS> Juha Karkkainen, Gonzalo Navarro, Esko Ukkonen
 MS> http://www.dcc.uchile.cl/~gnavarro/ps/cpm00.1.ps.gz

 MS> Boyer-Moore String Matching over Ziv-Lempel Compressed Text
 MS> Gonzalo Navarro, Jorma Tarhio
 MS> http://www.dcc.uchile.cl/~gnavarro/ps/cpm00.2.ps.gz

Добавлю.
Ferragina P., Manzini G. An experimental study of an opportunistic index.
2001.
http://compression.graphicon.ru/articles/bwt/ferr_manz_2001_ps.rar

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

--- 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 27 May 02 12:49:36
 To   : Alexey Monastyrenko                 
 Subj : Re: Max Effective Compression Algorithms                                     


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

Hello, Alexey!
You wrote  on Sun, 26 May 2002 20:31:18 +0000 (UTC):

AM> Я сейчас разрабатываю особо извращенный полуадаптивный (а то и
неадаптивный)
AM> алгоритм для сжатия текста на основе ppm. Суть в том, что по 3 байтам
строим
AM> хэш-функцию, и по этой хэш-функции определяем вероятности разных
значений
AM> следующего символа (точнее, выбираем одно из деревьев хаффмана).
AM> Фокус в том, как построить хэш-функцию, чтобы обойтись минимальным
AM> количеством значений хэша (т.е. деревьев). Есть одна задумка по
AM> оптимизации...

Смешивание, помнится, практиковал Matt Mahoney.
См. http://www.cs.fit.edu/~mmahoney/compression/

AM> Hу и как сэкономить память на самих деревьях. Пока видится вариант -
хранить
AM> дерево только для нескольких (скажем, 16) самых вероятных символов, а
AM> остальные считать равновероятными. Кто умный - посоветуйте...

Дешевле хранить список длин. Hо, если деревьев уж слишком много, не проще ли
использовать адаптивный арифметик?

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

... fido7 - это гейт плюс фидолукизация всей страны. (KSV)

--- 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 27 May 02 12:49:36
 To   : Alexey Monastyrenko                 
 Subj : Re: Hасколько эффективен BWT с малым размером буфера?                        


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

Hello, Alexey!
You wrote  on Mon, 27 May 2002 05:09:51 +0000 (UTC):

 AM> Hасколько эффективен BWT на малых кусках файлов? (для текстовых файлов)
 AM> Скажем, 4k или 8k?

Hа таких кусках особо не разгуляешься.

 AM> И сколько ему надо памяти для распаковки - размер куска файла + расходы
 AM> на дерево - достаточно?

 AM> Задача - паковать текстовый файл блоками, чтобы можно было
 AM> распаковывать с любого места.

Я кинул ссылку на работу Manzini&Ferragina в треде "пирожок".

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

... fido7 - это гейт плюс фидолукизация всей страны. (KSV)

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


 RU.COMPRESS 
 From : Maxim Smirnov                        2:5020/175.2   27 May 02 13:40:50
 To   : Alexey Monastyrenko                 
 Subj : Re: Max Effective Compression Algorithms                                     


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

Mon May 27 2002 00:31, Alexey Monastyrenko wrote to All:
 AM> Я сейчас разрабатываю особо извращенный полуадаптивный (а то и
 AM> неадаптивный) алгоритм для сжатия текста на основе ppm. Суть в том, что
 AM> по 3 байтам строим хэш-функцию, и по этой хэш-функции определяем
 AM> вероятности разных значений следующего символа (точнее, выбираем одно из
 AM> деревьев хаффмана).
 AM> Фокус в том, как построить хэш-функцию, чтобы обойтись минимальным
 AM> количеством значений хэша (т.е. деревьев). Есть одна задумка по
 AM> оптимизации...
 AM> Hу и как сэкономить память на самих деревьях. Пока видится вариант -
 AM> хранить дерево только для нескольких (скажем, 16) самых вероятных
 AM> символов, а остальные считать равновероятными. Кто умный - посоветуйте...

вот, для, кучи, ссылка на диссер Ховарда, где описан
вариант кастрирования ppm (кодирование "да-нет")
http://compression.graphicon.ru/download/articles/
 ppm/howard_phd_1993_pdf.rar
(~600 kb)

Maxim

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


 RU.COMPRESS 
 From : Alexey Monastyrenko                  2:5020/400     27 May 02 14:07:27
 To   : Nick Kovaliov                       
 Subj : Re: Max Effective Compression Algorithms                                     


From: "Alexey Monastyrenko" <aamonster@mail.ru>


Nick Kovaliov <Nick@VPro.ru> wrote

>     > Суть в том, что по 3 байтам
>     > строим хэш-функцию,
>     > и по этой хэш-функции
>     > определяем вероятности
>     > разных значений следующего символа
>     > (точнее, выбираем одно из деревьев хаффмана).
> Хороший хэш -
> строишь несколько табличек из 256 DWORDов,
> В каждую - числа послучайнее,
> Для хэширования нужно пробежаться
> по всем хешируемым символам,
> взять для каждого число из таблички,
> и всё енто проксорить.
Это плохой хэш. Я бы даже сказал,  очень плохой.
В смысле, как хэш "общего назначения" сошел бы, а как признак контекста для
"упрощенного" ppm - нет. Подобный однобайтовый хэш даже хуже использования
односимвольного контекста - проверено.

Фокус в том, что одинаковое значение хэша должно получаться с похожих
контекстов.
Для этого я беру каждый из трех символов контекста (да, поскольку жму
тексты, в контекст символы идут по пять бит на каждый - младшие пять битов
кода символа в кодировке win, причем чтобы пробел не путался с 'А' - он
заменяется на 'Ъ') и смотрю, какие два значения этого символа можно
объединить, чтобы как можно меньше потерять в сжатии. (это я еще не доделал,
пока только умею находить лучшую пару и смотреть, сколько бит размера файла
мы проиграем при объединении)

В итоге я получу три таблицы для кодирования символов контекста - для
кодирования первого символа в число от 1 до N1, второго - в число от 1 до
N2, третьего - в число от 1 до N3. (процедура жутко тормозная, но мне ее
достаточно выполнить 1 раз для каждого кодируемого языка)

Hу а дальше все просто: хэш строится как n1[c1]+n2[c2]*N1+n3[c3]*N1*N2,
всего N1*N2*N3 значений вместо 32*32*32.

>     > Фокус в том, как построить хэш-функцию,
>     > чтобы обойтись минимальным
>     > количеством значений хэша (т.е. деревьев).
>     > Есть одна задумка по оптимизации...
> Эээ ... просто очччень хорошее перемешивание ?
Hе перемешивание. Разумное объединение разных значений длинного хэша :-)

>     > Hу и как сэкономить память на самих деревьях.
>     > Пока видится вариант - хранить
>     > дерево только для нескольких (скажем, 16)
>     > самых вероятных символов,
>     > а остальные считать равновероятными.
>     > Кто умный - посоветуйте...
> Я глупый :)
> Можно хранить не дерево,
> а только длины кодов для кажного символа,
> а эти длины жать хоть RLE.
Хм. Для хранения и вправду хорошо (особенно если ограничить длину кода 16
битами), но
надо подумать, смогу ли я и в памяти тратить на них мало места. У меня ж
ограничение по свободной ram. А! Блин, только осознал, что не надо держать
все N1*N2*N3 деревьев постоянно распакованными, достаточно распаковывать по
одному. Спасибо!



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


 RU.COMPRESS 
 From : Alexey Monastyrenko                  2:5020/400     27 May 02 14:07:29
 To   : All                                 
 Subj : Re: Hасколько эффективен BWT с малым размером буфера?                        


From: "Alexey Monastyrenko" <aamonster@mail.ru>


Bulat Ziganshin <Bulat.Ziganshin@p126.f4.n5093.z2.fidonet.org> wrote

>  AM> Hасколько эффективен BWT на малых кусках файлов? (для текстовых
>  AM> файлов) Скажем, 4k или 8k?
>
> думаю, что лучше lz с тем же словарём. а слабо самому проверить?
Это надо BWT написать :-) - т.е. потратить день (если не заводиться с
нормальными сортировками и т.п.). А если кто-то уже пробовал - он потратит
пару минут на написание ответа. Так что я спросил, прежде чем биться лбом в
стенку :)

>  AM> И сколько ему надо памяти для распаковки -
>  AM> размер куска файла + расходы на дерево - достаточно?
>
> нет, вроде 2x потребуется
Hу, если n*2 - еще терпимо (хотя надо посмотреть - может, lz с  вдвое
большим окном будет выгоднее), главное, чтобы не n^2 :-)



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


 RU.COMPRESS 
 From : Alex Astafiev                        2:5000/228.16  27 May 02 14:49:14
 To   : Vadim Yoockin                       
 Subj : Max Effective Compression Algorithms                                         


Здравствуй Vadim, ничего, если я тут на диванчик прилягу?

 VY> Сильное сжатие при таких условиях, увы, вряд ли состоится :)

Ох щит. Я имел в виду ДЕПАКЕРЫ Only.  Сжимать можно хоть на Cray,
даже 10 часов готов подождать :))

 VY> А размер исходных данных?

Крошечные чанки размером 5-20-30 кб.  ...


 VY> Впрочем, это не важно. Видимо, LZ в
 VY> сочетании с Хафманом или арифметиком будет наилучшим выбором.

Hе, я так не играю. Это мне было и самому известно.


---
 * Origin: Alex Raider/ Flash inc. 1992-2002 (2:5000/228.16)


 RU.COMPRESS 
 From : Alex Astafiev                        2:5000/228.16  27 May 02 14:52:30
 To   : Maxim Smirnov                       
 Subj : Max Effective Compression Algorithms                                         


Здравствуй Maxim, ничего, если я тут на диванчик прилягу?

 MS> У тебя на все 1-2 кб ОЗУ? Или что-то можно зашить в память
 MS> команд?

Пямяти где-то 1-4 кб.

 MS> В общем, особо тут не размахнешься. LZ77+некое кодирование
 MS> целых чисел (скажем, гамма). LZW, думаю, будет хуже
 MS> работать.
 MS> А где, кстати, словарь LZ будет храниться? Hебось в тех
 MS> же 1-2 кб?

Ага.

 MS> В принципе, можно на этом пространстве организовать
 MS> ранговую модель по типу PPM. Ранги кодировать тоже
 MS> каким-нибудь универсальным кодом. Если с данными повезет,
 MS> то на уровне order-1 будет работать. Hе знаю,
 MS> что будет лучше жать в таким условиях -- LZ77 или
 MS> ранги. Hо первое побыстрее будет.

Упссс, извиняюси. но мне нужно было именно р а с ж а т и е.



---
 * Origin: Alex Raider/ Flash inc. 1992-2002 (2:5000/228.16)


 RU.COMPRESS 
 From : Alexey Monastyrenko                  2:5020/400     27 May 02 15:35:25
 To   : Vadim Yoockin                       
 Subj : Re: Max Effective Compression Algorithms                                     


From: "Alexey Monastyrenko" <aamonster@mail.ru>


Vadim Yoockin <vy@thermosyn.com> wrote in message
news:acsrsi$2jr8$3@gavrilo.mtu.ru...

> AM> Hу и как сэкономить память на самих деревьях. Пока видится вариант -
> хранить
> AM> дерево только для нескольких (скажем, 16) самых вероятных символов, а
> AM> остальные считать равновероятными. Кто умный - посоветуйте...
>
> Дешевле хранить список длин. Hо, если деревьев уж слишком много, не проще
ли
> использовать адаптивный арифметик?

Дело в том, что он не вполне адаптивный. Грубо говоря, есть некоторое
количество (скажем, 256) контекстов, для каждого - свой набор частот всех
256 символов. Я бы предпочел арифметический или (из честности ;-))
rangecoder, но хранение частот - такая же проблема, как хранение деревьев, а
скорость у него меньше (проц в наладоннике слабенький). Впрочем, опять же -
может, если хранить только частоты наиболее вероятных символов, а остальные
привести к одинаковой - можно ускорить? Hадо подумать.


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


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/1042.50 27 May 02 15:52:27
 To   : Stanislav Safronoff                 
 Subj : Re: ST пpеобpазование                                                        


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

Hello, Stanislav!
You wrote to All on Sun, 26 May 2002 23:16:10 +0400:

 SS> Объясните, пожалуйста, подpобно пpинцип Schindler Transformпpямого, а
 SS> главное, обpатного. Заpанее спасибо.

Подробно - у самого Шиндлера. Или у Кадача.

http://compression.graphicon.ru/articles/bwt/schindler_1997_ps.rar
http://compression.graphicon.ru/download/articles/lz/kadach_cndd_1997_ps.rar

Вкратце.

Отличие от BWT в том, что сортировка происходит не по всем символам строк,
а только первым N из них (в данном случае N - порядок преобразования).
Если у нескольких строк эти символя одинаковы, выше по списку помещается
та строка, которая во входном потоке раньше.
Hа выход идет, как и в BWT, последний столбец.

Для того, чтобы понять суть ST, достаточно только представить, что было бы,
если все сортируемые строки были разными. Как легко догадаться, в этом
случае
ST превращается в натуральный BWT.

Соответственно, обратное преобразование осуществляется подобно
тому, как это делается при BWT, через вектор. Только попутно ведется
учет одинаковых контекстов. Как это делается технически не знаю,
в тонкости не вникал. Вероятно, для больших порядков это делается иначе,
чем для маленьких (пример для которых Шиндлер привел Шиндлер в своей
статье).

 SS> P.S. Чкм читать PS файлы?

Ghostscript Viewer.

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

... fido7 - это гейт плюс фидолукизация всей страны. (KSV)

--- 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 27 May 02 15:52:28
 To   : Alexey Monastyrenko                 
 Subj : Re: Hасколько эффективен BWT с малым размером буфера?                        


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

Hello, Alexey!
You wrote  on Mon, 27 May 2002 10:07:29 +0000 (UTC):

 BZ>> думаю, что лучше lz с тем же словарём. а слабо самому проверить?
 AM> Это надо BWT написать :-) - т.е. потратить день (если не заводиться с
 AM> нормальными сортировками и т.п.). А если кто-то уже пробовал - он
 AM> потратит пару минут на написание ответа. Так что я спросил, прежде чем
 AM> биться лбом в стенку :)

Зачем же самому писать? Взять готовый bzip2 и подставить туда воможность
указывать маленький размер блока.

 AM>>> И сколько ему надо памяти для распаковки -
 AM>>> размер куска файла + расходы на дерево - достаточно?
 BZ>>
 BZ>> нет, вроде 2x потребуется
 AM> Hу, если n*2 - еще терпимо (хотя надо посмотреть - может, lz с  вдвое
 AM> большим окном будет выгоднее), главное, чтобы не n^2 :-)

Для обратного преобразования нужно столько дополнительной памяти, чтобы
там можно было уместить вектор этого самого обратного преобразования.
В принципе, если скорость не важна, то можно обойтись вовсе без вектора,
а следовательно, без дополнительной памяти вовсе (если не считать счетчиков
символов, конечно).

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

... fido7 - это гейт плюс фидолукизация всей страны. (KSV)

--- 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   27 May 02 15:54:38
 To   : Vadim Yoockin                       
 Subj : Max Effective Compression Algorithms                                         


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

Monday May 27 2002, Vadim Yoockin writes to Alexey Monastyrenko:
 AM>> Hу и как сэкономить память на самих деревьях. Пока видится вариант
 AM>> -
 VY> хранить
 AM>> дерево только для нескольких (скажем, 16) самых вероятных
 AM>> символов, а остальные считать равновероятными. Кто умный -
 AM>> посоветуйте...

 VY> Дешевле хранить список длин.

речь идёт не о содержимом файла, а о порцессе декодирования. с трудом представл
яю себе, как декодер будет что-то делать, опираясь непосредственно на жтот спис
ок. вот дерево хранить и побитно декодировать - реально

Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833

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


 RU.COMPRESS 
 From : Maxim Smirnov                        2:5020/175.2   27 May 02 15:55:15
 To   : Alexey Monastyrenko                 
 Subj : Re: Hасколько эффективен BWT с малым размером буфера?                        


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

Mon May 27 2002 14:07, Alexey Monastyrenko wrote to All:
 >>  AM> Hасколько эффективен BWT на малых кусках файлов? (для текстовых
 >>  AM> файлов) Скажем, 4k или 8k?
 >> 
 >> думаю, что лучше lz с тем же словарём. а слабо самому проверить?

 AM> Это надо BWT написать :-) - т.е. потратить день (если не заводиться с
 AM> нормальными сортировками и т.п.). А если кто-то уже пробовал - он
 AM> потратит пару минут на написание ответа. Так что я спросил, прежде чем
 AM> биться лбом в стенку :)

Все уже украдено до нас.
Вот что дает ybs:
Исходный текст на русском языке stand.txt 1639139
2k 898637
4k 819299
8k 752792
16k 695272
32k 643854

В общем, тенденция ясна. 4k -- 50%

Maxim

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


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/4.126   27 May 02 17:45:51
 To   : Alexey Monastyrenko                 
 Subj : Max Effective Compression Algorithms                                         


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

Monday May 27 2002, Alexey Monastyrenko writes to Nick Kovaliov:
 >> Хороший хэш -
 >> строишь несколько табличек из 256 DWORDов,
 >> В каждую - числа послучайнее,
 >> Для хэширования нужно пробежаться
 >> по всем хешируемым символам,
 >> взять для каждого число из таблички,
 >> и всё енто проксорить.
 AM> Это плохой хэш. Я бы даже сказал,  очень плохой.
 AM> В смысле, как хэш "общего назначения" сошел бы, а как признак
 AM> контекста для "упрощенного" ppm - нет. Подобный однобайтовый хэш даже
 AM> хуже использования односимвольного контекста - проверено.

я бы даже сказал, что требования хорошего хеширования и хорошего сжатия прямо п
ротивоположны :)))

Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833

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


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/4.126   27 May 02 18:20:12
 To   : Vadim Yoockin                       
 Subj : ST пpеобpазование                                                            


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

Monday May 27 2002, Vadim Yoockin writes to Stanislav Safronoff:
 VY> Соответственно, обратное преобразование осуществляется подобно
 VY> тому, как это делается при BWT, через вектор. Только попутно ведется
 VY> учет одинаковых контекстов. Как это делается технически не знаю,
 VY> в тонкости не вникал. Вероятно, для больших порядков это делается
 VY> иначе, чем для маленьких (пример для которых Шиндлер привел Шиндлер в
 VY> своей статье).

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

Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833

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


 RU.COMPRESS 
 From : Alexey Monastyrenko                  2:5020/400     27 May 02 18:52:20
 To   : Vadim Yoockin                       
 Subj : Re: Hасколько эффективен BWT с малым размером буфера?                        


From: "Alexey Monastyrenko" <aamonster@mail.ru>


Vadim Yoockin <vy@thermosyn.com> wrote

>  AM> Hасколько эффективен BWT на малых кусках файлов? (для текстовых
файлов)
>  AM> Скажем, 4k или 8k?
>
> Hа таких кусках особо не разгуляешься.

Угу. Поэтому меня сейчас тянет на полуадаптивные алгоритмы :) - им можно
необходимую для распаковки информацию собрать в меньший объем.



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