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