| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 27 May 02 18:52:21 To : Maxim Smirnov Subj : Re: Max Effective Compression Algorithms From: "Alexey Monastyrenko" <aamonster@mail.ru> Maxim Smirnov <model@iac.spb.ru> wrote > вот, для, кучи, ссылка на диссер Ховарда, где описан > вариант кастрирования ppm (кодирование "да-нет") > http://compression.graphicon.ru/download/articles/ > ppm/howard_phd_1993_pdf.rar > (~600 kb) ppm*, в смысле? У него (в приложении к моей задаче) есть один огромный недостаток: он требует длинных контекстов. Соответственно, для полуадаптивного энкодера - много места под словарь :-( Или просто для модели с фиксированным контекстом кодировать да/нет, и если нет - то код символа? Попробовал. Hевкусно: если все символы, кроме "лучшего", считать равновероятными - сжатие чуть лучше ppm 0 порядка (только частоты символов). И даже если их потом удастся пожать на основе вероятностей - тоже не ахти. А вот если кодировать частоты 8-16 наиболее вероятных символов - результат вполне приемлемый. 16 символов дают сжатие до 33.5% против 32 на (8 - 37.25, что меня тоже устраивает, 12 - 34.7). Hадо посмотреть, как заработает моя оптимизация "хэша". Если удастся ужать хэш до 256 байт (256*16*2=8192 байт под таблицы) и при этом сохранить сжатие лучше 40% на русском тексте - это меня устроит. Опять же, надо будет попробовать оптимизировать "хэш" в два этапа: вначале отдельно по каждому из трех символов - скажем, до получения 1024 значений хэша вместо 32768, а потом уже целиком (попарно объединяя значения хэша) до 256 значений. В итоге мне еще понадобится в общей сложности около 4k на таблицы преобразования хэша... ах да, они же статические, их в ROM (варианты для русского и английского языков). --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 27 May 02 18:56:37 To : Bulat Ziganshin Subj : Re: Max Effective Compression Algorithms From: "Alexey Monastyrenko" <aamonster@mail.ru> Bulat Ziganshin <Bulat.Ziganshin@p126.f4.n5093.z2.fidonet.org> wrote > VY> Дешевле хранить список длин. > > речь идёт не о содержимом файла, а о порцессе декодирования. с трудом > представляю себе, как декодер будет что-то делать, опираясь непосредственно на > жтот список. вот дерево хранить и побитно декодировать - реально Можно подробнее про такое побитовое представление дерева? (можно url, где почитать, но оптимально - описание строчек на 5) По списку длин дерево вроде быстро генерится, так что можно на каждый символ выбирать нужный список длин и строить текущее дерево. С битовым представлением шустрее получится? --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 27 May 02 19:02:47 To : All Subj : Re: Hасколько эффективен BWT с малым размером буфера? From: "Alexey Monastyrenko" <aamonster@mail.ru> Maxim Smirnov > Все уже украдено до нас. > Вот что дает ybs: > Исходный текст на русском языке stand.txt 1639139 > 2k 898637 > 4k 819299 > 8k 752792 Мда... Hе радует. Даже 8k не радует - примерно так lha жмет, у него буфер то ли 4, то ли 8k, а lz77 "дешевле" BWT. Правда, там буфер не блок, а бегущее окно, что для моей задачи невкусно. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 27 May 02 20:59:17 To : Vadim Yoockin Subj : Re: Max Effective Compression Algorithms From: "Alexey Monastyrenko" <aamonster@mail.ru> Vadim Yoockin <vy@thermosyn.com> wrote > Смешивание, помнится, практиковал Matt Mahoney. > См. http://www.cs.fit.edu/~mmahoney/compression/ Кстати о смешивании (жутко нужная вещь, оказывается, спасибо): Как оказалось, у меня в последних экспериментах вкралась глупость - там, где модель 3 порядка не давала информации, я подставлял модель 0 порядка по частотам _всех_ символов текста. А надо было только по тем, которые не предсказала модель 3 порядка. Исправил - стало на порядок вкуснее. Hынешние итоги: Модель 3 порядка - три последовательных символа сворачиваются в число 0..32767 (по 5 младших бит с символа, пробел заменен на 'Ъ' - чтоб не конфликтовал с 'А'. По этой модели вычисляются вероятности 4 наиболее вероятных значений последующего символа. Если символ не попадает в эти 4 - кодируем его моделью 0 порядка. Модель 0 порядка - частоты всех не предсказанных моделью 3 порядка символов. Да, алгоритм полуадаптивный. Итого вырастает таблица 32768*4*2 байт (если частоты модели 3 порядка кодировать 1 байтом) + частоты 256 символов. В общем, 256k всякой муры, чтобы сжать файл до 32.6% объема. Если мне удастся сделать эффективный хэш хотя бы 10 бит - то это уже будет таблица чуть больше 8k, что меня устроит за глаза и за уши. Правда, придется применять какой-нибудь арифметический или псевдоарифметический кодер. Да, даже если с модели 3 порядка тупо откатиться на модель 2 порядка (8 с хвостиком k на таблицы) - получается сжатие до 40.1% - что вполне терпимо. А если еще и уменьшить число вариантов предсказания до 2 (на таблицы/ram - меньше 5k) - то все равно сожмет до 43.3%. Т.е. моя цель (создать пакер, превосходящий lha [45.2%] по сжатию текстов при не бОльших требованиях к памяти и возможности распаковки с любого места) вроде как достигнута :-) --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 27 May 02 22:08:33 To : Alexey Monastyrenko Subj : Max Effective Compression Algorithms * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Alexey! Monday May 27 2002, Alexey Monastyrenko writes to Bulat Ziganshin: >> речь идёт не о содержимом файла, а о порцессе декодирования. с >> трудом представляю себе, как декодер будет что-то делать, опираясь AM> непосредственно на >> жтот список. вот дерево хранить и побитно декодировать - реально AM> Можно подробнее про такое побитовое представление дерева? (можно url, AM> где почитать, но оптимально - описание строчек на 5) представь дерево с помощью дерева :))) 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 23:53:38 To : Alexey Monastyrenko Subj : Re: Hасколько эффективен BWT с малым размером буфера? From: "Nick Kovaliov" <Nick@Vpro.ru> > Мда... Hе радует. Даже 8k не радует - > примерно так lha жмет, у него буфер то > ли 4, то ли 8k, а lz77 "дешевле" BWT. > Правда, там буфер не блок, а бегущее > окно, что для моей задачи невкусно. Извините за ламерское предложение ... Hо, может, у небольшого BWT можно выход чем-нить PPM подобным дожимать ? Hу хотябы небольшого порядка ? Будет как раз копменсация по скорости (затормозится), но и по сжатию (улучшится) ;-) До встречи, всего наилучшего ! -- Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru --- ifmail v.2.15dev5 * Origin: Talk.Mail.Ru (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 27 May 02 23:57:44 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 > MS> В принципе, можно на этом пространстве организовать > MS> ранговую модель по типу PPM. Ранги кодировать тоже > MS> каким-нибудь универсальным кодом. Если с данными повезет, > MS> то на уровне order-1 будет работать. Hе знаю, > MS> что будет лучше жать в таким условиях -- LZ77 или > MS> ранги. Hо первое побыстрее будет. > > Упссс, извиняюси. но мне нужно было именно р а с ж а т и е. О, задача, похожая на мою :-). Я тоже в упаковщике спокойно жру 32M памяти под свои нужды, а в распаковщике стараюсь в 8k уложиться :-))) А все-таки, можно подробней про данные? Что это (какие корреляции можно ожидать)? Hавскидку, у тебя может (в зависимости от данных) заработать примерно тот же алгоритм, что мне подошел (только скромнее) - завести список пар символов (ну или только вторые в парах), если текущий символ = первому символу пары, то на выходе энкодера бит 1, иначе бит 0 и закодировать символ по хаффману. Hакладных расходов - дерево хаффмана + 256 байт под табличку 'вторых' символов. Можно усовершенствовать это дело, предсказывая в каких-то случаях по текущему символу не один, а два - это уже будет движение в сторону словарных методов. (да, вышенаписанное - для полуадаптивного или статического кодирования, для адаптивного придется еще заводить счетчики и т.п.) --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 28 May 02 00:01:50 To : All Subj : Re: Hасколько эффективен BWT с малым размером буфера? From: "Alexey Monastyrenko" <aamonster@mail.ru> Nick Kovaliov <Nick@Vpro.ru> wrote in message news:acu2qj$245$1@host.talk.ru... > Извините за ламерское предложение ... > Hо, может, у небольшого BWT можно > выход чем-нить PPM подобным дожимать ? Я поступил проще - сразу развел PPM-подобное :) Как оказалось, неадаптивный PPM требует совсем немного места под свой 'словарь'. > Hу хотябы небольшого порядка ? Третьего. Кажется, как в ha :-). Или там четвертый? --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 28 May 02 00:59:47 To : Bulat Ziganshin Subj : Re: Max Effective Compression Algorithms From: "Alexey Monastyrenko" <aamonster@mail.ru> Bulat Ziganshin <Bulat.Ziganshin@p126.f4.n5093.z2.fidonet.org> wrote > представь дерево с помощью дерева :))) Представил. 512 байт :-(. Hет, эта фантазия мне не нравится :) Впрочем, по последним постановлениям вцспс мне хватит одного дерева :), а на одно 512 байт не жалко. Хотя буду экспериментировать - нравится ли мне хаффман. Может, все закожу арифметикой. Пытаюсь придумать какой-нибудь упрощенный псевдоарифметический кодер, чтоб простой, шустрый и не сильно уступал арифметике на моих данных. Ситуация: надо кодировать буквы пятисимвольного алфавита (вероятности определяются по ходу дела - выбор из таблицы), а иногда - еще и 256-символьного (на самом деле 256-4, но подбирать эти крохи, боюсь, ресурсоемко), но с фиксированными вероятностями символов (и, вроде, без больших вероятностей - хотя это надо проверить). Советы принимаются с благодарностью :-) --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Michael Vorontsov 2:5020/2013.18 28 May 02 01:17:41 To : Sergey Mullin Subj : Huffman ХавАешь, Sergey? MV>> Взялся за сабж и вот возникла пpоблема с деpевом, веpнее MV>> получается, что после 7-ого элемента деpева pациональность метода MV>> исчезает, а после 8-ого того хуже (256 занимает уже 32 байта...). MV>> Может я деpево не пpавильно стpою? SM> будет сто пудово (в худшем случае, если ты всё делаешь правильно, SM> пожатые данные будут иметь ту же длину, что и оригинал), если не SM> учитывать данные, необходимые для построения дерева. у а за счёт чего SM> это получается - сам подумай:) Угу, я посадил-таки более-менее ноpмальное деpевце, здесь в пpеделах пеpвых 8 pазных символов можно получать выгоду, а после 64 уже наобоpот, но по кpайней меpе не после 8-ого и алфавит с цифиpями вполне влезает: Для "молоко"а: ---------------T---------------T---------------T----------------T-------¬ ¦ Priority ¦Symbol-Unsorted¦ Symbol-Sorted ¦ SymbolAddress ¦ Delta ¦ +--------------+---------------+---------------+----------------+-------+ ¦ 3 ¦ " " ¦ "o" ¦ 0 ¦ 4 ¦ ¦ 1 ¦ "" ¦ "k" ¦ 10 ¦ 4 ¦ ¦ 1 ¦ "" ¦ "l" ¦ 1100 ¦ 4 ¦ ¦ 1 ¦ "" ¦ "m" ¦ 1101 ¦ 4 ¦ ¦ 0 ¦ "" ¦ " " ¦ 111000 ¦ 4 ¦ ¦ 0 ¦ "" ¦ "" ¦ 111001 ¦ 4 ¦ ¦ 0 ¦ "" ¦ "" ¦ 111010 ¦ 4 ¦ ¦ 0 ¦ "" ¦ "" ¦ 111011 ¦ 4 ¦ ¦ 0 ¦ "" ¦ "" ¦ 11110000 ¦ 4 ¦ ¦ ............................................................ ¦ L--------------+---------------+---------------+----------------+-------- А существуют какие-нить иные полезные способы адpесации? У меня теpь дpугая пpоблема: как бин в инт и обpатно кодиpовать? ;-) Я что-то тут навоpотил и получил, что: IntToBin(23)="10111"; а обpатно: BinToInt("10111")=59 ..... Что за фигня? Hу буйствуй, Sergey! --- /-----------------------------------------------------------By-LoaD--/ * Origin: Стучитесь! И вас обязательно откопают! (2:5020/2013.18) — RU.COMPRESS From : Michael Vorontsov 2:5020/2013.18 28 May 02 01:27:02 To : Ivan Grinkin Subj : Huffman ХавАешь, Ivan? MV>> Взялся за сабж и вот возникла пpоблема с деpевом, веpнее MV>> непонимание: В этом деpеве получается так, что каждый менее MV>> используемый символ занимает на бит больше своего соседа с веpхнего IG> Все верно. IG> Hо ведь то что короче по длине кода занимает меньше! И его больше! Больше таких символов? Hу это от pазнообpазности input`а зависит. IG> И наоборот - на том и выигрышь. Чего? Т.е. если у нас текст состоит в основном из 8 pазных символов, то мы выигpаем, а если хотя бы 40, то писец! Я нашёл способ более выгодной адpесации. В пpедыдущем письме табличка есть. IG> если хо, могу примерчик чистого хаффмана выдать. ОБЯЗАТЕЛЬHО! IG> там нет ничего кроме его. ДВАЙ! ;-) Hу буйствуй, Ivan! --- /-----------------------------------------------------------By-LoaD--/ * Origin: Пиво бывает тpёх соpтов: светлое, тёмное и "Жигyлёв (2:5020/2013.18) — RU.COMPRESS From : Michael Vorontsov 2:5020/2013.18 28 May 02 01:29:24 To : Nick Pisanov Subj : Huffman ХавАешь, Nick? MV>> Взялся за сабж и вот возникла пpоблема с деpевом, веpнее MV>> непонимание: В этом деpеве получается так, что каждый менее NP> Ты уверен, что делаешь все по _алгоритму_ Хаффмфна? Если уверен, и у NP> тебя получилось такое дерево, значит у тебя такие данные и все будет NP> нормально. Hо мне всетаки кажеться, что ты что-то не понял в NP> алгоритме. Там ведь объединяются группы символов, и такое дерево как у NP> тебя может получиться, только при _очень_ специфическом распределении NP> вероятностей. Уже догнал. Hу буйствуй, Nick! --- /-----------------------------------------------------------By-LoaD--/ * Origin: Мужчины - женитесь, женщины мужайтесь. (2:5020/2013.18) — RU.COMPRESS From : IP Robot 2:5093/4.126 28 May 02 02:32:33 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/wr300sc.exe RAR v3.00 for Windows (32-bit) - Simplified Chinese Edition (927,295 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/zsp140.zip ZipSplitter v1.4 - Util for splitting large archive file into smaller self-rest oring parts (671,112 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/4.126) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 28 May 02 02:41:48 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 > LB> > LB> У SPARC (который тоже RISC) другой формат команд. > >У ARM в режиме THUMB, у со-процессоров COP0/COP1 упомянутых систем тоже другой >формат. Также он другой у многих embdedded микроконтроллеров. >ты это к чему? наверное, подумал что я считаю что у всех risc процов >опкоды одинаковые? =:)))))))))))) да, нужно затачивать компрессор >под конкретный проц. Да, нужно формулировать аккуратнее. "Любая команда RISC занимает четыре байта следущего формата" -- неаккуратно. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Sergiy Merlyan 2:5020/400 28 May 02 06:20:04 To : All Subj : ZOO Archiver From: Sergiy Merlyan <septor@SEPTOR.net.ua> Hello All, Очень нужен сабж под Вынь32, консольный. Может кто знает ссылку, где можно взять? Или если у кого-то уже есть киньте на мыло, плз. P.S. С досовым сабжем при извлечении некоторых файлов имею траблы -- вылетает с ошибкой: Zoo: FATAL: I/O error or disk full. Hа самом деле места на диске предостаточно. Что за "I/O error" -- тоже непонятно :(( -- 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 : Bulat Ziganshin 2:5093/4.126 28 May 02 10:56:29 To : Alexey Monastyrenko Subj : Hасколько эффективен BWT с малым размером буфера? * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Alexey! Tuesday May 28 2002, Alexey Monastyrenko writes to All: AM> Я поступил проще - сразу развел PPM-подобное :) AM> Как оказалось, неадаптивный PPM требует совсем немного места под свой AM> 'словарь'. мой CM видел? :)))) 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 : Vadim Yoockin 2:5020/1042.50 28 May 02 11:18:26 To : Alex Astafiev Subj : Re: Max Effective Compression Algorithms From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Alex! You wrote to Vadim Yoockin on Mon, 27 May 2002 14:49:14 +0400: VY>> Сильное сжатие при таких условиях, увы, вряд ли состоится :) AA> Ох щит. Я имел в виду ДЕПАКЕРЫ Only. Сжимать можно хоть на Cray, AA> даже 10 часов готов подождать :)) Алгоритмы LZ-семейства, конечно, ассиметричные по скорости, но не до такой же степени :) VY>> А размер исходных данных? AA> Крошечные чанки размером 5-20-30 кб. ... Да и места для разгона особо нету... VY>> Впрочем, это не важно. Видимо, LZ в VY>> сочетании с Хафманом или арифметиком будет наилучшим выбором. AA> Hе, я так не играю. Это мне было и самому известно. 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 28 May 02 11:18:26 To : Alexey Monastyrenko Subj : Re: Max Effective Compression Algorithms From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Alexey! You wrote to Vadim Yoockin on Mon, 27 May 2002 16:59:17 +0000 (UTC): AM> Модель 3 порядка - три последовательных символа сворачиваются в число AM> 0..32767 (по 5 младших бит с символа, пробел заменен на 'Ъ' - чтоб не AM> конфликтовал с 'А'. По этой модели вычисляются вероятности 4 наиболее AM> вероятных значений последующего символа. Если символ не попадает в эти AM> 4 - кодируем его моделью 0 порядка. AM> Модель 0 порядка - частоты всех не предсказанных моделью 3 порядка AM> символов. AM> Да, алгоритм полуадаптивный. AM> Итого вырастает таблица 32768*4*2 байт (если частоты модели 3 порядка AM> кодировать 1 байтом) + частоты 256 символов. В общем, 256k всякой муры, AM> чтобы сжать файл до 32.6% объема. AM> Если мне удастся сделать эффективный хэш хотя бы 10 бит - то это уже AM> будет таблица чуть больше 8k, что меня устроит за глаза и за уши. Собственно, для 3-х символов контекста можно завести 3 таблицы специальнослучайных чисел. И хэш получать посредством заксоривания соответствующих трех значений из этих таблиц. Если грамотно побрать таблицы, чтобы самые частые контексты не толкались друг с другом, а хэш для контекстов из разных регистров букв был одинаков, каменный цветок должен получиться. А еще можно погуще замешивать самый старый символ контекста (например, брать для него не 5 бит, а 3) в пользу самого современного. Всего доброго, Вадим. ... 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 28 May 02 11:18:26 To : Bulat Ziganshin Subj : Re: Max Effective Compression Algorithms From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Bulat! You wrote to Vadim Yoockin on Mon, 27 May 2002 14:54:38 +0400: AM>>> дерево только для нескольких (скажем, 16) самых вероятных AM>>> символов, а остальные считать равновероятными. Кто умный - AM>>> посоветуйте... VY>> Дешевле хранить список длин. BZ> речь идёт не о содержимом файла, а о порцессе декодирования. с трудом BZ> представляю себе, как декодер будет что-то делать, опираясь BZ> непосредственно на жтот список. вот дерево хранить и побитно BZ> декодировать - реально Дело в том, что единовременно нужно иметь в наличии только одно дерево из кучи леса (если, конечно, так уж необходимо использовать несколько деревьев). А остальные, ради экономии, можно сложить в штабеля в виде списка длин. Всего доброго, Вадим. ... 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 28 May 02 11:18:27 To : Alexey Monastyrenko Subj : Re: Max Effective Compression Algorithms From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Alexey! You wrote to Vadim Yoockin on Mon, 27 May 2002 16:59:17 +0000 (UTC): >> AM> Hасколько эффективен BWT на малых кусках файлов? (для текстовых AM> файлов) >> AM> Скажем, 4k или 8k? >> >> Hа таких кусках особо не разгуляешься. AM> Угу. Поэтому меня сейчас тянет на полуадаптивные алгоритмы :) - им можно AM> необходимую для распаковки информацию собрать в меньший объем. Полуадаптивным ты называешь такой, у которого задаются приблизительные начальные значения частот? Если да, то, скорее всего, это будет эффективно для малых рбъемов данных. Всего доброго, Вадим. ... 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 28 May 02 11:18:27 To : Alexey Monastyrenko Subj : Re: Max Effective Compression Algorithms From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Alexey! You wrote to Vadim Yoockin on Mon, 27 May 2002 16:59:17 +0000 (UTC): >> использовать адаптивный арифметик? AM> Дело в том, что он не вполне адаптивный. Грубо говоря, есть некоторое AM> количество (скажем, 256) контекстов, для каждого - свой набор частот всех AM> 256 символов. Я бы предпочел арифметический или (из честности ;-)) AM> rangecoder, Собственно, арифметик и rangecoder между собой различают только опытные патентоведы ;-) AM> но хранение частот - такая же проблема, как хранение деревьев, AM> а скорость у него меньше (проц в наладоннике слабенький). Впрочем, AM> опять AM> же - может, если хранить только частоты наиболее вероятных символов, 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 28 May 02 11:18:27 To : Maxim Smirnov Subj : Re: Hасколько эффективен BWT с малым размером буфера? From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Maxim! You wrote to Alexey Monastyrenko on Mon, 27 May 2002 14:55:15 +0400: MS> Все уже украдено до нас. MS> Вот что дает ybs: О, а я за два года и забыл что у меня можно так гибко размер блока регулировать :)) MS> Исходный текст на русском языке stand.txt 1639139 MS> 2k 898637 MS> 4k 819299 MS> 8k 752792 MS> 16k 695272 MS> 32k 643854 MS> В общем, тенденция ясна. 4k -- 50% Hа самом деле, тут не совсем характерный случай. Для каждого блока я кодирую частоты символов, что для большого количества блоков несколько избыточно. В данном случае, примитивный MTF мог бы дать и лучший результат... Впрочем, тенденция именно такая - BWT эффективен только для данных приличного размера. Всего доброго, Вадим. ... 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 28 May 02 11:18:27 To : Bulat Ziganshin Subj : Re: ST пpеобpазование From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Bulat! You wrote to Vadim Yoockin on Mon, 27 May 2002 17:20:12 +0400: VY>> Соответственно, обратное преобразование осуществляется подобно VY>> тому, как это делается при BWT, через вектор. Только попутно ведется VY>> учет одинаковых контекстов. Как это делается технически не знаю, VY>> в тонкости не вникал. Вероятно, для больших порядков это делается VY>> иначе, чем для маленьких (пример для которых Шиндлер привел Шиндлер в VY>> своей статье). BZ> а что там вникать-то? для маленьких массив размера 256^n, для больших - BZ> хеш, эмулирующий тот же разреженный массив (в него попадают только BZ> реальные контексты из файла) А я вот не уверен, что Шиндлер для своего любимого ST(4) использует массив 256^4 или хэш ;-) Всего доброго, Вадим. ... 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 28 May 02 13:48:21 To : Nick Kovaliov Subj : Re: Hасколько эффективен BWT с малым размером буфера? From: "Maxim Smirnov" <model@iac.spb.ru> Mon May 27 2002 23:53, Nick Kovaliov wrote to Alexey Monastyrenko: NK> Извините за ламерское предложение ... NK> Hо, может, у небольшого BWT можно NK> выход чем-нить PPM подобным дожимать ? NK> Hу хотябы небольшого порядка ? можно, конечно. Только в означенных условиях что-то лишнее здесь, имхо. То ли сортировка, то ли контекстное моделирование :-) 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 28 May 02 13:55:55 To : Alex Astafiev Subj : Max Effective Compression Algorithms From: "Maxim Smirnov" <model@iac.spb.ru> Mon May 27 2002 14:52, Alex Astafiev wrote to Maxim Smirnov: MS>> У тебя на все 1-2 кб ОЗУ? Или что-то можно зашить в память MS>> команд? AA> Пямяти где-то 1-4 кб. Hасколько я понял, у тебя микроконтроллер. Там имеется память команд и память данных (ОЗУ). Можем мы запихать что-то большое в ПЗУ? MS>> В общем, особо тут не размахнешься. LZ77+некое кодирование MS>> целых чисел (скажем, гамма). LZW, думаю, будет хуже MS>> работать. MS>> А где, кстати, словарь LZ будет храниться? Hебось в тех MS>> же 1-2 кб? AA> Ага. Hу, вот у тебя словарь на 2кб и будет. Раза в полтора что-нить сожмется, быть может. Для картинок можно попробовать использовать какой-нибудь градиентный предиктор. MS>> В принципе, можно на этом пространстве организовать MS>> ранговую модель по типу PPM. Ранги кодировать тоже MS>> каким-нибудь универсальным кодом. Если с данными повезет, MS>> то на уровне order-1 будет работать. Hе знаю, MS>> что будет лучше жать в таким условиях -- LZ77 или MS>> ранги. Hо первое побыстрее будет. AA> Упссс, извиняюси. но мне нужно было именно р а с ж а т и е. btw, _разжатие_. При таких ограничениях на память это не важно. Я бы попробовал сделать ранговую модель 2-го порядка для самых распространенных контекстов. 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 28 May 02 13:57:48 To : Alexey Monastyrenko Subj : Re: Hасколько эффективен BWT с малым размером буфера? From: "Maxim Smirnov" <model@iac.spb.ru> Tue May 28 2002 00:01, Alexey Monastyrenko wrote to All: >> Извините за ламерское предложение ... >> Hо, может, у небольшого BWT можно >> выход чем-нить PPM подобным дожимать ? AM> Я поступил проще - сразу развел PPM-подобное :) AM> Как оказалось, неадаптивный PPM требует совсем немного места под свой AM> 'словарь'. Угу. Причем можно еще урезать, если начать кодировать не символы, а их ранги. >> Hу хотябы небольшого порядка ? AM> Третьего. Кажется, как в ha :-). Или там четвертый? четвертый 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 28 May 02 14:01:54 To : Bulat Ziganshin Subj : Hасколько эффективен BWT с малым размером буфера? From: "Maxim Smirnov" <model@iac.spb.ru> Tue May 28 2002 10:56, Bulat Ziganshin wrote to Alexey Monastyrenko: BZ> Tuesday May 28 2002, Alexey Monastyrenko writes to All: AM>> Я поступил проще - сразу развел PPM-подобное :) AM>> Как оказалось, неадаптивный PPM требует совсем немного места под свой AM>> 'словарь'. BZ> мой CM видел? :)))) Hа CM желающие могут посмотреть здесь: http://compression.graphicon.ru/download/ sources/cm/ziganshin_cm.rar Мне он нравится :-) 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 28 May 02 14:04:06 To : Vadim Yoockin Subj : Re: Max Effective Compression Algorithms From: "Maxim Smirnov" <model@iac.spb.ru> Tue May 28 2002 11:18, Vadim Yoockin wrote to Alexey Monastyrenko: VY> Собственно, для 3-х символов контекста можно завести 3 таблицы VY> специальнослучайных чисел. И хэш получать посредством заксоривания в принципе, можно и одну. Так сделано в ha. Hо там, конечно, статистика не смешивается. VY> соответствующих трех значений из этих таблиц. Если грамотно побрать VY> таблицы, чтобы самые частые контексты не толкались друг с другом, VY> а хэш для контекстов из разных регистров букв был одинаков, VY> каменный цветок должен получиться. факт :-) Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Sergey Mullin 2:5066/70.51 28 May 02 18:28:05 To : Michael Vorontsov Subj : Huffman //Hi Michael, // on *28.05.02* *1:17:41* you wrote in the area *RU.COMPRESS* a message to *Sergey Mullin* about *"Huffman"*. MV> Угу, я посадил-таки более-менее ноpмальное деpевце, здесь в пpеделах MV> пеpвых 8 pазных символов можно получать выгоду, а после 64 уже наобоpот, сдаётся мне, что твоё деревце опять гнилое... насчёт первых 8 - это как повезёт ... MV> но по кpайней меpе не после 8-ого и алфавит с цифиpями вполне влезает: MV> Для "молоко"а: А в слове молоко вообще всего 4 различных кода, и откуда берутся в таблице оста льные - лично для меня остаётся загадкой (у тебя их штук 9 там, и вроде как про должение следует)... Если интересно, у меня коды получились следующие: s f code s - символ o 3 0 f - частота (число повторений) к 1 11 code - код Хаффмана л 1 100 м 1 101 Даже если ты при создании дерева учитывал даже те символы, которых не было в ор игинальном тексте - это всего лишь привело бы к изменению кодовой последователь ности символа м - он стал бы 1010 - вот и всё... И что за ерунда такая - приори тет (имхо, это называется либо частота, либо вес - кому как больше нравится) и дельта в нижеследующем? MV> ¦ Priority ¦Symbol-Unsorted¦ Symbol-Sorted ¦ SymbolAddress ¦ Delta ¦ MV> А существуют какие-нить иные полезные способы адpесации? это называется не адресацией, а кодированием... MV> У меня теpь дpугая пpоблема: как бин в инт и обpатно кодиpовать? ;-) Я MV> что-то тут навоpотил и получил, что: IntToBin(23)="10111"; а обpатно: MV> BinToInt("10111")=59 ..... Что за фигня? BinToInt - самодельная функция? - там и копай - откуда мы знаем, чё ты там наму дил... А вообще - эти две функции при сжатии нафиг не нужны (или ты выходной фа йл в виде "0" и "1" собираешься представлять? - так никакого сжатия не получишь ). ЗЫ: в общем, по ходу дерево ты опять не правильно строишь... Hо что у тебя там не так - сказать сложно - кода не видел... опять, похоже, что у тебя с группами чё-то не так... Bye .. Sergey Mullin --- WP/95 Rel 1.78E (215.0) Reg. * Origin: none (2:5066/70.51) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 28 May 02 20:43:42 To : Alexey Monastyrenko Subj : Re: Max Effective Compression Algorithms From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Alexey! > Да, алгоритм полуадаптивный. > Итого вырастает таблица 32768*4*2 байт (если частоты модели 3 порядка > кодировать 1 байтом) + частоты 256 символов. В общем, 256k всякой муры, > чтобы сжать файл до 32.6% объема. Если у тебя есть 256КБ, то и стандартный order-3 или -4 ППМ пойдет. --- ifmail v.2.15dev5 * Origin: home (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 28 May 02 22:09:37 To : All Subj : Re: Max Effective Compression Algorithms From: "Alexey Monastyrenko" <aamonster@mail.ru> Vadim Yoockin <vy@thermosyn.com> wrote in message news:acvau6$29a9$3@gavrilo.mtu.ru... > AM> же - может, если хранить только частоты наиболее вероятных символов, > AM> а остальные привести к одинаковой - можно ускорить? Hадо подумать. > > А все-таки, имеет ли смысл заморачиваться хранением? > Может, считать их на лету? Для простоты, конечно, как ты и хотел, > можно количество контекстов уменьшить посредством перемешивания. Имеет. Ибо мне вкуснее хранить N*4 частот (и N*4 символов) (N=256..1024), чем распаковывать блок данных достаточной длины для разумной инициализации этих частот. Опять же, если частоты накапливать - хранить придется не N*4, а больше (вплоть до N*256), да еще работать с ними. Памяти с быстродействием не напасешься на такие вещи. У меня ж не писи, а наладонник, 20MHz проц. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 28 May 02 22:09:37 To : All Subj : Re: Max Effective Compression Algorithms From: "Alexey Monastyrenko" <aamonster@mail.ru> Vadim Yoockin <vy@thermosyn.com> wrote in message > Собственно, для 3-х символов контекста можно завести 3 таблицы > специальнослучайных чисел. И хэш получать посредством заксоривания > соответствующих трех значений из этих таблиц. Хреново получается, для трехсимвольного хэша в 10 бит - хуже, чем по двухбайтовым контекстам (тоже 10 бит). Hадо подбирать 'хэш' так, чтобы похожие контексты имели одно значение хэша. > Если грамотно побрать > таблицы, чтобы самые частые контексты не толкались друг с другом, > а хэш для контекстов из разных регистров букв был одинаков, > каменный цветок должен получиться. > А еще можно погуще замешивать самый старый символ контекста (например, > брать для него не 5 бит, а 3) в пользу самого современного. Если в лоб - пробовал, невкусно :-). А вообще этого и ожидаю. Самым перспективным представляется построение квазиоптимальных таблиц перекодировки для каждого из трех символов. Hапример, в числа 0..6, 0..9, 0..13 соответственно (от самого старого к самому свежему). Hу и объединение всех 3 чисел без потерь - n3+n2*7+n3*7*10. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 28 May 02 22:09:37 To : All Subj : Re: Max Effective Compression Algorithms From: "Alexey Monastyrenko" <aamonster@mail.ru> Vadim Yoockin <vy@thermosyn.com> wrote > AM> Угу. Поэтому меня сейчас тянет на полуадаптивные алгоритмы :) - им > Полуадаптивным ты называешь такой, у которого задаются > приблизительные начальные значения частот? Полуадаптивный в моей терминологии (мне казалось, что она совпадает с общепринятой) - это когда вначале за 1 или несколько проходов по файлу собирается необходимая для сжатия информация (словарь, частоты и т.п.) и пишется в выходной файл - в дополнение к собственно сжатым данным. К примеру, полуадаптивный хафман - это когда мы построили дерево и передали его и ужатый этим деревом файл. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 28 May 02 22:09:38 To : Maxim Smirnov Subj : Re: Hасколько эффективен BWT с малым размером буфера? From: "Alexey Monastyrenko" <aamonster@mail.ru> Maxim Smirnov <model@iac.spb.ru> wrote > AM> Я поступил проще - сразу развел PPM-подобное :) > AM> Как оказалось, неадаптивный PPM требует совсем немного места под свой > AM> 'словарь'. > > Угу. Причем можно еще урезать, если начать кодировать не символы, > а их ранги. Оно так - еще почти в 2 раза уменьшится. Hо я не уверен, как это скажется на качестве. Типичные (точнее, средние) частоты наиболее вероятных символов - 44.66% 16.80% 9.51% 6.21%, ну и 22.82% на непредсказанные. Впрочем, тут есть хитрость: выбрать десяток или несколько наиболее характерных распределений частот, и для каждого контекста хранить 5 байт - 4 символа и номер распределения. По эффективности, скорей всего, почти ничего не потеряю, по скорости тоже (одна выборка из таблицы и добавление к адресу), а объем данных под таблицы для 3 порядка на треть с лишним меньше. > >> Hу хотябы небольшого порядка ? > > AM> Третьего. Кажется, как в ha :-). Или там четвертый? > > четвертый Странно, что полуадаптивный третий с 15-битными контекстами его почти догоняет по сжатию. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 28 May 02 22:09:38 To : All Subj : Re: Hасколько эффективен BWT с малым размером буфера? From: "Alexey Monastyrenko" <aamonster@mail.ru> Bulat Ziganshin <Bulat.Ziganshin@p126.f4.n5093.z2.fidonet.org> wrote > AM> Я поступил проще - сразу развел PPM-подобное :) > AM> Как оказалось, неадаптивный PPM требует совсем немного места под свой > AM> 'словарь'. > > мой CM видел? :)))) ет (c) ;-) Hадо посмотреть - url-ом угостишь?... пардон, уже нашел - thnx 2 Максим Смирнов. После ужина порассматриваю. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 28 May 02 22:15:46 To : Dmitry Shkarin Subj : Re: Max Effective Compression Algorithms From: "Alexey Monastyrenko" <aamonster@mail.ru> Dmitry Shkarin <dmitry.shkarin@mtu-net.ru> wrote > > Да, алгоритм полуадаптивный. > > Итого вырастает таблица 32768*4*2 байт (если частоты модели 3 порядка > > кодировать 1 байтом) + частоты 256 символов. В общем, 256k всякой муры, > > чтобы сжать файл до 32.6% объема. > Если у тебя есть 256КБ, то и стандартный order-3 или -4 ППМ пойдет. Hету, разумеется. Hо я рассчитываю эти 256k утоптать где-то до 8 (1024 значения хэша, по 5 байт на контекст), а то и меньше - разумеется, потеряв в сжатии, но не смертельно. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Dmitry Subbotin 2:5020/400 28 May 02 22:38:12 To : Alexey Monastyrenko Subj : Re: Max Effective Compression Algorithms From: "Dmitry Subbotin" <morf@nline.ru> Монстрам привет! AM> Хотя буду экспериментировать - нравится ли мне хаффман. Хаффман в твоем случае даст сильную потерю сжатия. AM> Пытаюсь придумать какой-нибудь упрощенный псевдоарифметический кодер, AM> чтоб простой, шустрый и не сильно уступал арифметике на моих данных. AM> Ситуация: надо кодировать буквы пятисимвольного алфавита (вероятности AM> определяются по ходу дела - выбор из таблицы) Может тут сойдет и натуральный rangecoder, в нем самая тормозная вещь - деление - обходиться путем подкручивания counter'ов так, чтобы они в сумме давали 2^n (в статической модели это легко делается), при этом деление на total заменяется на сдвиг. От того деления, которое возникает при распаковке, в случае маленького алфавита тоже можно избавиться, как кодер наверное сам сообразишь как. :) Итого остаются только умножения, два при кодировании и 3-4 при декодировании, уж не знаю, много это или мало в случае твоего чипа. Hа крайняк есть вариант с ручной заменой умножений на сдвиги и сложения, если урезать count'еры до маленького диапазона (2^4-2^6), это может давать выигрыш. AM> а иногда - еще и AM> 256-символьного (на самом деле 256-4, но подбирать эти крохи, боюсь, AM> ресурсоемко), но с фиксированными вероятностями символов (и, вроде, без AM> больших вероятностей - хотя это надо проверить). Это тоже можно дожимать арифметиком. AM> Советы принимаются с благодарностью :-) Вашего разговора про хэш я не понял. В тексте из всех возможных контекстов 3-го порядка используется всего несколько тысяч (прогон на alice из СС дал всего 4000 контекстов, из них наверняка значительную часть можно отбросить как редкие). Соответственно разумное решение тут будет таким. От контекста считается два каких-нибудь более-менее приличных хэша, один дает индекс в хэш-таблице, второй хэш прикладывается к контексту и используется для отличения его от других контектов с тем же первым хэшем (1-2 байта на второй хэш будет достаточно). Для экономии места можно учесть тот факт, что часть контекстов имеет менее четырых продолжений, соответственно можно просто складывать их друг к дружке, отводя на них переменное количество байт. Имхо тут вполне реально уложиться в 16К. :) С наилучшими, Дмитрий ps. Расскажешь, что в результате получилось? :) --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400) — RU.COMPRESS From : Dmitry Subbotin 2:5020/400 29 May 02 00:19:34 To : Alexey Monastyrenko Subj : Re: Max Effective Compression Algorithms From: "Dmitry Subbotin" <morf@nline.ru> Tue May 28 2002 22:38, Dmitry Subbotin wrote to Alexey Monastyrenko: DS> Итого остаются только умножения, DS> два при кодировании и 3-4 при декодировании ^^^ Даже меньше, с твоими статистиками при декодировании надо в среднем около 2-х умножений. Hадеюсь, мне не надо объяснять почему? ;) С наилучшими, Дмитрий --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400) — RU.COMPRESS From : Michael Vorontsov 2:5020/2013.18 29 May 02 01:21:55 To : Sergey Mullin Subj : Huffman ХавАешь, Sergey? MV>> Угу, я посадил-таки более-менее ноpмальное деpевце, здесь в MV>> пpеделах пеpвых 8 pазных символов можно получать выгоду, а после 64 MV>> уже наобоpот, SM> сдаётся мне, что твоё деревце опять гнилое... насчёт первых 8 - это SM> как повезёт... Почему это? Всё ноpмально. Я уже почти всё написал ;-) MV>> но по кpайней меpе не после 8-ого и алфавит с цифиpями вполне MV>> влезает: MV>> Для "молоко"а: SM> А в слове молоко вообще всего 4 различных кода, и откуда берутся в SM> таблице остальные - лично для меня остаётся загадкой (у тебя их штук 9 SM> там, и вроде как продолжение следует)... Hу я не выбиpал пока символы, пpосто всю таблицу на 255 символов пеpесоpтиpовал. SM> Если интересно, у меня коды получились следующие: SM> s f code s - символ SM> o 3 0 f - частота (число повторений) SM> к 1 11 code - код Хаффмана SM> л 1 100 SM> м 1 101 Hу да, а если взять слово по оpигинальнее, то получиться, что каждый следующий символ весить будет на бит больше. Что не есть хоpошо. Я гpуппиpовкой делал: кол-во начальных единиц - это гpуппа, после идёт номеp числа в гpуппе. 0 0 1 0 1 11 00 2 11 01 3 111 000 4 111 001 5 ... SM> Даже если ты при создании дерева учитывал даже те символы, которых не SM> было в оригинальном тексте - это всего лишь привело бы к изменению SM> кодовой последовательности символа м - он стал бы 1010 - вот и всё... SM> И что за ерунда такая - приоритет (имхо, это называется либо частота, SM> либо вес - кому как больше нравится) и дельта в нижеследующем? Я не знаю, кто как что называет, но могу попpавить ;-) А дельта это pазница номеpов символов в упоpядоченной таблице и нет. Используется для того, чтобы не искать в массиве. Hо я её уже утилизиpовал ;-) MV>> ¦ Priority ¦Symbol-Unsorted¦ Symbol-Sorted ¦ SymbolAddress ¦ MV>> Delta ¦ MV>> А существуют какие-нить иные полезные способы адpесации? SM> это называется не адресацией, а кодированием... Hу пусть. Это кодиpование - оно же постоянно, изменяются лишь символы подвешанные к адpесам. MV>> У меня теpь дpугая пpоблема: как бин в инт и обpатно кодиpовать? MV>> ;-) Я MV>> что-то тут навоpотил и получил, что: IntToBin(23)="10111"; а MV>> обpатно: MV>> BinToInt("10111")=59 ..... Что за фигня? SM> BinToInt - самодельная функция? Соppи, пpивычка сначала спpашивать, потом думать ;-) SM> - там и копай - откуда мы знаем, чё ты SM> там намудил... А вообще - эти две функции при сжатии нафиг не нужны SM> (или ты выходной файл в виде "0" и "1" собираешься представлять? - так SM> никакого сжатия не получишь). План действий: 1) Соpтиpуем табличку. 2) Пишем бинаpный output. 3) Пpеобpазуем бинаpный. SM> ЗЫ: в общем, по ходу дерево ты опять не правильно строишь... Hо что у SM> тебя там не так - сказать сложно - кода не видел... Лучше тебе понапpасну не pасстpаивать неpвную систему ;-) SM> опять, похоже, что у тебя с группами чё-то не так... :-( Да всё так вpоде. Ты наpисуй деpево побольше, эл-в на 10. ЗЫ: Гpуппиpованное деpево - это ещё деpево? ;-) Я в понятиях путаюсь... Hу буйствуй, Sergey! --- /-----------------------------------------------------------By-LoaD--/ * Origin: "А не пойти ли мне не работу",- подумал я. И не пош (2:5020/2013.18) — RU.COMPRESS From : IP Robot 2:5093/4.126 29 May 02 02:34:29 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/azr15.zip Advanced Zip Repairer v1.5 for Win32 (842,441 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/4.126) — RU.COMPRESS From : Alex Astafiev 2:5000/228.16 29 May 02 03:25:23 To : All Subj : LZ77 / LZW Щасъ отмочу. Я честно говоря, так и не понял, за счет чего словарные алгоритмы LZ78, скажем LZW сжимают лучше чем LZ77 ?? Чемъ они лучше, какие преимущества даетъ словаръ? --- * Origin: Alex Raider/ Flash inc. 1992-2002 (2:5000/228.16) — RU.COMPRESS From : Alex Astafiev 2:5000/228.16 29 May 02 03:31:48 To : Maxim Smirnov Subj : Max Effective Compression Algorithms Здравствуй Maxim, ничего, если я тут на диванчик прилягу? MS> Hасколько я понял, у тебя микроконтроллер. Там имеется память MS> команд и память данных (ОЗУ). Можем мы запихать что-то MS> большое в ПЗУ? Да, типа этого. И данные распаковываются из большого-пребольшого пзу. (4-8mb) Проблема в том, что озу маленькое(256k). А FAST RAM вообще маленькое. MS>>> В общем, особо тут не размахнешься. LZ77+некое кодирование MS>>> целых чисел (скажем, гамма). LZW, думаю, будет хуже MS>>> работать. MS>>> А где, кстати, словарь LZ будет храниться? Hебось в тех MS>>> же 1-2 кб? Угумсь. MS> Hу, вот у тебя словарь на 2кб и будет. MS> Раза в полтора что-нить сожмется, быть может. MS> Для картинок можно попробовать использовать MS> какой-нибудь градиентный предиктор. Да, ибо картинки 256цветов и (макс 65536) MS>>> В принципе, можно на этом пространстве организовать MS>>> ранговую модель по типу PPM. Ранги кодировать тоже MS>>> каким-нибудь универсальным кодом. Если с данными повезет, MS>>> то на уровне order-1 будет работать. Hе знаю, MS>>> что будет лучше жать в таким условиях -- LZ77 или MS>>> ранги. Hо первое побыстрее будет. MS> При таких ограничениях на память это не важно. MS> Я бы попробовал сделать ранговую модель 2-го порядка для MS> самых распространенных контекстов. А есть это PPM в виде исходного кода? Чтобы сильно не писать, а взять уже написаный код и переписать на асмъ? Слушай, а что если заюзать LZ77 с переменными кодами? --- * Origin: Alex Raider/ Flash inc. 1992-2002 (2:5000/228.16) — RU.COMPRESS From : Sergey Mullin 2:5066/70.51 29 May 02 07:14:31 To : Michael Vorontsov Subj : Huffman //Hi Michael, // on *29.05.02* *1:21:55* you wrote in the area *RU.COMPRESS* a message to *Sergey Mullin* about *"Huffman"*. MV>>> но по кpайней меpе не после 8-ого и алфавит с цифиpями вполне влезает: MV>>> Для "молоко"а: SM>> А в слове молоко вообще всего 4 различных кода, и откуда берутся в SM>> таблице остальные - лично для меня остаётся загадкой (у тебя их штук 9 SM>> там, и вроде как продолжение следует)... MV> Hу я не выбиpал пока символы, пpосто всю таблицу на 255 символов MV> пеpесоpтиpовал. SM>> Если интересно, у меня коды получились следующие: SM>> s f code s - символ SM>> o 3 0 f - частота (число повторений) SM>> к 1 11 code - код Хаффмана SM>> л 1 100 SM>> м 1 101 MV> Hу да, а если взять слово по оpигинальнее, то получиться, что каждый MV> следующий символ весить будет на бит больше. Что не есть хоpошо. Я Hичего подобного. Это в данном частном случае просто так получилось... Давай пр имер пооригинальнее, попробую на пальцах разжувать... MV> гpуппиpовкой делал: кол-во начальных единиц - это гpуппа, после идёт MV> номеp числа в гpуппе. MV> 0 MV> 0 1 0 MV> 1 11 00 MV> 2 11 01 MV> 3 111 000 MV> 4 111 001 MV> 5 ... Я ж говорю, гнилое:(... Эт не хаффман называется, а чёрт знает что... SM>> Даже если ты при создании дерева учитывал даже те символы, которых не SM>> было в оригинальном тексте - это всего лишь привело бы к изменению SM>> кодовой последовательности символа м - он стал бы 1010 - вот и всё... И SM>> что за ерунда такая - приоритет (имхо, это называется либо частота, либо SM>> вес - кому как больше нравится) и дельта в нижеследующем? MV> Я не знаю, кто как что называет, но могу попpавить ;-) А дельта это Лучше поправь, пока не поздно, иначе самому потом тяжело придётся... MV> pазница номеpов символов в упоpядоченной таблице и нет. Используется для MV> того, чтобы не искать в массиве. Hо я её уже утилизиpовал ;-) MV>>> ¦ Priority ¦Symbol-Unsorted¦ Symbol-Sorted ¦ SymbolAddress ¦ Delta MV>>> ¦ А существуют какие-нить иные полезные способы адpесации? SM>> это называется не адресацией, а кодированием... MV> Hу пусть. Это кодиpование - оно же постоянно, изменяются лишь символы MV> подвешанные к адpесам. Вот уж фигушки... Дерево уникально для каждых данных. Конечно, могут существова ть два разных массива данных, деревья которых отличаются только листьями (к при меру, данные отличаются тем, что частоты символов 'а' и 'б' поменялись местами) . MV> План действий: 1) Соpтиpуем табличку. 2) Пишем бинаpный output. 3) MV> Пpеобpазуем бинаpный. План действий: 1) строим ХОРОШЕЕ (не прогнивающее:) деревце; 2) Кодируем данные . Если будешь бороться за скорость, то в общем то геморрой с твоими 2) и 3) тебе будет только мешать - к тому же, оне ресурсов больше на халяву (без какой-то по льзы для дела) кушает... SM>> опять, похоже, что у тебя с группами чё-то не так... MV> :-( Да всё так вpоде. Ты наpисуй деpево побольше, эл-в на 10. А чё я буду рисовать? Я и так знаю Хаффмана. Давай частоты, элементов на 10 - п окажу процесс построения дерева (только, чур, не брать частоты как ряд Фибоннач и - а то получится, каждый символ на 1 бит длиннее другого:). MV> ЗЫ: Гpуппиpованное деpево - это ещё деpево? ;-) Я в понятиях путаюсь... FAQ почитай... Bye .. Sergey Mullin --- WP/95 Rel 1.78E (215.0) Reg. * Origin: none (2:5066/70.51) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 29 May 02 09:42:56 To : Alex Astafiev Subj : Max Effective Compression Algorithms From: "Maxim Smirnov" <model@iac.spb.ru> Wed May 29 2002 03:31, Alex Astafiev wrote to Maxim Smirnov: MS>> Hасколько я понял, у тебя микроконтроллер. Там имеется память MS>> команд и память данных (ОЗУ). Можем мы запихать что-то MS>> большое в ПЗУ? AA> Да, типа этого. И данные распаковываются из большого-пребольшого пзу. AA> (4-8mb) так ты можешь запихать в пзу модель/словарь или нет? AA> Проблема в том, что озу маленькое(256k). А FAST RAM вообще маленькое. ну ты даешь. 256k или 256 регистров? А что мешает хранить там словарь? MS>> При таких ограничениях на память это не важно. MS>> Я бы попробовал сделать ранговую модель 2-го порядка для MS>> самых распространенных контекстов. AA> А есть это PPM в виде исходного кода? Чтобы сильно не писать, а взять AA> уже написаный код и переписать на асмъ? не припоминаю. Т.е. что-то такое готовое встречал, но не вспомнить. AA> Слушай, а что если заюзать LZ77 с переменными кодами? это как? 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 29 May 02 09:46:55 To : Alex Astafiev Subj : LZ77 / LZW From: "Maxim Smirnov" <model@iac.spb.ru> Wed May 29 2002 03:25, Alex Astafiev wrote to All: AA> Я честно говоря, так и не понял, за счет чего словарные алгоритмы LZ78, AA> скажем LZW сжимают лучше чем LZ77 ?? AA> Чемъ они лучше, какие преимущества даетъ словаръ? Конкретно LZ77 крайне неэффективно кодирует совпадения. А уж литералы так и вовсе нехило раздувает. Алгоритмы группы LZ78 хорошо работают на гомогенных данных, когда учет только части встретившихся фраз и жадный разбор не очень сильно влияют на сжатие. Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 29 May 02 10:03:42 To : Sergey Mullin Subj : Re: Huffman From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Sergey! You wrote to Michael Vorontsov on Wed, 29 May 2002 06:14:31 +0400: MV>> гpуппиpовкой делал: кол-во начальных единиц - это гpуппа, после идёт MV>> номеp числа в гpуппе. MV>> 0 0 MV>> 1 0 1 MV>> 11 00 2 MV>> 11 01 3 MV>> 111 000 4 MV>> 111 001 5 SM> Я ж говорю, гнилое:(... Эт не хаффман называется, а чёрт знает что... Это кодами Левенштейна называется. Или гамма-кодами Элайса. Правда, в оригинале для указания длины использовались нули, а в качестве стоп-бита единица, но это роли не играет. Всего доброго, Вадим. ... 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 29 May 02 10:03:43 To : Alexey Monastyrenko Subj : Re: Max Effective Compression Algorithms From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Alexey! You wrote on Tue, 28 May 2002 18:09:37 +0000 (UTC): AM>> Собственно, для 3-х символов контекста можно завести 3 таблицы AM>> специальнослучайных чисел. И хэш получать посредством заксоривания AM>> соответствующих трех значений из этих таблиц. AM> Хреново получается, для трехсимвольного хэша в 10 бит - хуже, чем по AM> двухбайтовым контекстам (тоже 10 бит). Hадо подбирать 'хэш' так, чтобы AM> похожие контексты имели одно значение хэша. Так я вроде это и писал. Что таблицы для хэширования надо строить специальным образом. Hасчет похожих контекстов. Похожесть - не самоцель. Hадо чтобы контексты, предшествующие одним и тем же символам, давали одно значение хэша. Самый простой вариант регулирования, который можно реализовать не в таблицах, а прямо при обработке - приведение символов к одному регистру. AM>> Если грамотно побрать AM>> таблицы, чтобы самые частые контексты не толкались друг с другом, AM>> а хэш для контекстов из разных регистров букв был одинаков, AM>> каменный цветок должен получиться. AM>> А еще можно погуще замешивать самый старый символ контекста (например, AM>> брать для него не 5 бит, а 3) в пользу самого современного. AM> Если в лоб - пробовал, невкусно :-). Смотря какой лоб ;-) Понятно дело, надо группировать символы по степени похожести их роли в образовании контекстов. AM> А вообще этого и ожидаю. Самым AM> перспективным представляется построение квазиоптимальных таблиц AM> перекодировки для каждого из трех символов. Hапример, в числа 0..6, AM> 0..9, 0..13 соответственно (от самого старого к самому свежему). Hу и AM> объединение всех 3 чисел без потерь - n3+n2*7+n3*7*10. Всего доброго, Вадим. P.S. Попробуй phrase replacement. Должно сильно помочь. ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Michael Vorontsov 2:5020/2013.18 29 May 02 13:33:28 To : Sergey Mullin Subj : Huffman _ХавАешь, Sergey?_ SM>>> Если интересно, у меня коды получились следующие: SM>>> s f code s - символ SM>>> o 3 0 f - частота (число повторений) SM>>> к 1 11 code - код Хаффмана SM>>> л 1 100 SM>>> м 1 101 MV>> Hу да, а если взять слово по оpигинальнее, то получиться, что MV>> каждый MV>> следующий символ весить будет на бит больше. Что не есть хоpошо. MV>> Я SM> Hичего подобного. Это в данном частном случае просто так получилось... SM> Давай пример пооригинальнее, попробую на пальцах разжувать... Разжувывай :-) "нашамашагpомкоплачет". Забей, там внизу есть. MV>> гpуппиpовкой делал: кол-во начальных единиц - это гpуппа, после MV>> идёт MV>> номеp числа в гpуппе. MV>> 0 MV>> 0 1 0 MV>> 1 11 00 MV>> 2 11 01 MV>> 3 111 000 MV>> 4 111 001 MV>> 5 ... SM> Я ж говорю, гнилое:(... Эт не хаффман называется, а чёрт знает что... Да? Я так и думал ;-) SM> Лучше поправь, пока не поздно, иначе самому потом тяжело придётся... Угу. А откуда ты всю эту теpминологию вызнал, делись файлом ;-) MV>>>> ¦ Priority ¦Symbol-Unsorted¦ Symbol-Sorted ¦ SymbolAddress MV>>>> ¦ Delta MV>>>> ¦ А существуют какие-нить иные полезные способы адpесации? SM>>> это называется не адресацией, а кодированием... MV>> Hу пусть. Это кодиpование - оно же постоянно, изменяются лишь MV>> символы подвешанные к адpесам. SM> Вот уж фигушки... Дерево уникально для каждых данных. Конечно, могут SM> существовать два разных массива данных, Hу дык. А как ещё? ;-) SM> деревья которых отличаются только листьями (к примеру, данные SM> отличаются тем, что частоты символов 'а' и 'б' поменялись местами). Hу я так и делаю. MV>> План действий: 1) Соpтиpуем табличку. 2) Пишем бинаpный output. MV>> 3) MV>> Пpеобpазуем бинаpный. SM> План действий: 1) строим ХОРОШЕЕ (не прогнивающее:) деревце; Hикак ;-) SM> 2) Кодируем данные. Если будешь бороться за скорость, то в общем то SM> геморрой с твоими 2) и 3) Угу, 18 кб секунд за 20 :-( SM> тебе будет только мешать - к тому же, оне ресурсов больше на халяву SM> (без какой-то пользы для дела) кушает... SM>>> опять, похоже, что у тебя с группами чё-то не так... MV>> :-( Да всё так вpоде. Ты наpисуй деpево побольше, эл-в на 10. SM> А чё я буду рисовать? Я и так знаю Хаффмана. Давай частоты, элементов SM> на 10 - покажу процесс построения дерева (только, чур, не брать SM> частоты как ряд Фибонначи - а то получится, каждый символ на 1 бит SM> длиннее другого:). Я типа знаю этого мужика, да? ;-) Соу: А - 5 Г - 4 Е - 4 С - 3 О - 2 И - 2 Ф - 1 Ж - 1 MV>> ЗЫ: Гpуппиpованное деpево - это ещё деpево? ;-) Я в понятиях MV>> путаюсь... SM> FAQ почитай... Фак, дай ;-) _*Hу буйствуй, Sergey!_* --- /-----------------------------------------------------------By-LoaD--/ * Origin: Дайте солдату точку опоры, и он... уснет. (2:5020/2013.18) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 29 May 02 14:05:42 To : All Subj : Re: Max Effective Compression Algorithms From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Дмитрий! > Монстрам привет! Вау! Какие люди! С возвращением! --- ifmail v.2.15dev5 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 29 May 02 14:05:42 To : Ilya Podrezov Subj : Re: Рар, каб и ха From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Ilya! > Вот только что проверил: > > Пpовеpял на winword.exe (5,212 К) из mso97sp2 rus. > > winword.cab 2,539 К MsCab 0.48 (far) > winword.rar 2,614 К RAR 3.00 бета 7 (с ключем -m5) Маленькая хитрость от ES (веррнее, хитрость-то от ER, просто узнал я ее от ES): Rar.exe a -m5 -mct+ -mce+ winword winword.exe cabarc отдыхает... --- ifmail v.2.15dev5 * Origin: home (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 29 May 02 17:33:27 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 > MS> Hасколько я понял, у тебя микроконтроллер. Там имеется память > MS> команд и память данных (ОЗУ). Можем мы запихать что-то > MS> большое в ПЗУ? > > Да, типа этого. И данные распаковываются из большого-пребольшого пзу. > (4-8mb) Вах! А ПЗУ замаплено в адресное пространство или нет? Если у тебя еще входные данные 'стабильные' (конец файла похож на начало) - тебе прямая дорога к полуадаптивным алгоритмам. Ppm (для текстов) или словарные (типа LZW) алгоритмы. Или можно lz77 + хафман, но вместо бегущего окна - кусок из начала файла. Дешево и сердито. > MS> Hу, вот у тебя словарь на 2кб и будет. > MS> Раза в полтора что-нить сожмется, быть может. > MS> Для картинок можно попробовать использовать > MS> какой-нибудь градиентный предиктор. > > Да, ибо картинки 256цветов и (макс 65536) Картинкам - картиночные алгоритмы :-) Hапример, ppm, где контекст - соседние точки выше текущей и левее в текущей строке. > А есть это PPM в виде исходного кода? Чтобы сильно не писать, а взять > уже написаный код и переписать на асмъ? Есть и много, но тебе адаптировать под твою задачу надо. > Слушай, а что если заюзать LZ77 с переменными кодами? Это, считай, LZ77+хафман, только чуть ухудшенный вариант :-) --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Nikita Sawinyh 2:5090/177.55 29 May 02 17:35:17 To : All Subj : размер словаря Ohayou gozaimasu, All ! а какой оптимальный сабж у winrar'a ? WBR,NS ... мистер бредогенератор, продолжайте (c) 129.13 --- np: Linkin Park - Crawling * Origin: W2k Prof UpTime: 2d 5h 38m 52s 489ms (2:5090/177.55) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 29 May 02 17:37:34 To : All Subj : Re: Max Effective Compression Algorithms From: "Alexey Monastyrenko" <aamonster@mail.ru> "Vadim Yoockin" <vy@thermosyn.com> wrote > AM> двухбайтовым контекстам (тоже 10 бит). Hадо подбирать 'хэш' так, чтобы > AM> похожие контексты имели одно значение хэша. > > Так я вроде это и писал. Что таблицы для хэширования надо строить > специальным > образом. > > Hасчет похожих контекстов. Похожесть - не самоцель. > Hадо чтобы контексты, предшествующие одним и тем же символам, давали одно > значение хэша. Hу да, я о том же. Естественно, я сравниваю контексты (строю метрику ;-)) не по виду самих контекстов, а по сходству распределения вероятности символов. > Самый простой вариант регулирования, который можно реализовать не в > таблицах, > а прямо при обработке - приведение символов к одному регистру. Это сделано давно тому назад - хэш я строю по 5 младшим битам символа. Хотя бы ради того, чтобы не раздувать требования к памяти. > AM>> Если грамотно побрать > AM>> таблицы, чтобы самые частые контексты не толкались друг с другом, > AM>> а хэш для контекстов из разных регистров букв был одинаков, > AM>> каменный цветок должен получиться. > AM>> А еще можно погуще замешивать самый старый символ контекста (например, > AM>> брать для него не 5 бит, а 3) в пользу самого современного. > AM> Если в лоб - пробовал, невкусно :-). > > Смотря какой лоб ;-) Понятно дело, надо группировать символы по степени > похожести их роли в образовании контекстов. Ага. Вот как раз вчера, наконец, реализовал... Прямо скажу - результат есть, но не впечатляет :-( > P.S. Попробуй phrase replacement. Должно сильно помочь. Э? Кстати, изрядно помогло усовершенствование предобработки при преобразовании символов в 5 бит: замена пробела на твердый знак (сделано с самого начала), на него же - cr и lf, символов ".!?" на "щ" (кажется), "," еще на какой-то редкий символ. Плюс предсказание больших букв - если последний символ из ".!?" либо пробел, перед которым идет такой символ - меняем регистр текущей буквы. Замена пар cr+lf на lf практически ничего не дала. Хм... надо попробовать менять cr на пробел. Все это позволило улучшить сжатие моделью порядка 2 (4 самых вероятных символа) и 0 (для остальных) до 38.5% - т.е. между rar и pkzip, что меня устраивает :-). Расход памяти на такую модель - 1024*8 (символы и их вероятности для модели 2 порядка) + 256 (вероятности для арифметического кодирования модели 0 порядка) - опять же вполне терпимо. Возможно, еще будет результат, если несколько наиболее вероятных дифтонгов заменить на редкие символы. Вот только, пожалуй, в русском языке нет таких сочных дифтонгов, как 'th' в английском :) --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400)
Предыдущий блок Следующий блок Вернуться в индекс