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