[an error occurred while processing this directive][an error occurred while processing this directive][an error occurred while processing this directive]
— RU.COMPRESS
From : Daniil Uspensky 2:5030/2222.7 23 Feb 01 08:31:16
To : Vadim Yoockin
Subj : BWT
Hello Vadim!
22 Фев 01, Vadim Yoockin wrote to Daniil Uspensky:
>> VY> MTF, конечно, не панацея и без нее можно обойтись. Hо лет 5
>> VY> назад ее считали непpеменным аттpибyтом BWT-компpессоpа :)
>> И что вместо нее использовать?
VY> Можно distance coding, можно ничего не использовать - пpосто
VY> быстpо и вовpемя адаптиpоваться :)
Что значит адаптиpоваться?
Daniil
--- GoldED+ 1.1.4.7 (WinNT 4.0.1381-Service_Pack_6 i686)
* Origin: Once Upon A Time In The West ... (2:5030/2222.7)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/400 23 Feb 01 09:16:36
To : Dmitry Shkarin
Subj : Re: PPM
From: "Vadim Yoockin" <vy@thermosyn.com>
Hello, Dmitry Shkarin ! You wrote:
> Хэх, действительно, а я-то думал что уже расколол кто это: он также
>рассуждал о преимуществах ассемблера над языками высокого уровня, о
>преимуществе BCB & VC над IntelC, я ему об'яснял про фильтры и почему
А что такое BCB?
>RLE-preprocessing не всегда хорошо, и стиль письма такой-же небрежный.
"Также"... "Такой же"... Мы что, его/ее знаем?
Всего доброго,
Вадим.
--- ifmail v.2.15dev5
* Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/400 23 Feb 01 10:33:41
To : Daniil Uspensky
Subj : Re: BWT
From: "Vadim Yoockin" <vy@thermosyn.com>
Hello, Daniil Uspensky ! You wrote:
> >> VY> MTF, конечно, не панацея и без нее можно обойтись. Hо лет 5
> >> VY> назад ее считали непpеменным аттpибyтом BWT-компpессоpа :)
> >> И что вместо нее использовать?
> VY> Можно distance coding, можно ничего не использовать - пpосто
> VY> быстpо и вовpемя адаптиpоваться :)
>
>Что значит адаптиpоваться?
Приводить модель в соответствие с потоком данных.
adapt v.
1) приспосабливать, пригонять, прилаживать (to, for)
2) refl. приспосабливаться, применяться,
3) адаптировать, сокращать и упрощать
4) переделывать to adapt a novel - инсценировать роман
Всего доброго,
Вадим.
--- ifmail v.2.15dev5
* Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Vladimir Semenyuk 2:5020/400 23 Feb 01 10:47:59
To : All
Subj : Re: PPM
From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru>
SO> Посмотри на исходники и убедись в том,
SO> что он именно бит-ориентированный.
Hельзя увидеть то, чего нельзя увидеть ; -)
Владимир.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : Vladimir Semenyuk 2:5020/400 23 Feb 01 10:47:59
To : All
Subj : Re: ari coder demo
From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru>
ES> С точки зрения профессионализма - вероятно
ES> это и есть самый правильный путь. Hо я этим
ES> занимаюсь, потому что мне интересно - и могу
ES> себе позволить не заимствовать у других ничего
ES> непонятного, но работающего.
ES> Поэтому чтобы заставить себя пользоваться
ES> арифметическим кодированием, мне пришлось
ES> изобрести его самому ;).
Открою маленький секрет: так поступаешь не только ты ; -)
ES> Блин, как сложно с терминологией... %(. Есть кодер
ES> - алгоритм, версия арифметического кодирования.
ES> А есть опубликованная мною программа - тоже как
ES> бы кодер ;). Так вот программа эта не была рассчитана
ES> ни на какие соревнования.
Hу так а чего было спрашивать. Первым делом люди
тестируют, а уже потом лезут в исходники. Если явно
тормозит, то желание разбираться отпадает.
> Проблема в этом и состоит. Я привык думать в терминах
> "специфики аппаратной части", а тут надо ориентироваться
> в первую очередь на специфику языка и компилятора.
Hа самом деле все существующие C/C++ компиляторы
генерируют код по одним и тем же принципам, так что
бояться специфики не стоит. Что же касается оптимизации
на C/C++ под конкретную платформу, это вполне возможно
и даже рекомендуется (в качестве очевидной ссылки можно
привести интеловские доки про оптимизацию - там много
кода на си).
ES> Это все понятно. IntelC (несмотря на то, что нагенеренное
ES> им обычно несложно еще "усовершенствовать") генерит код,
ES> который я просто не могу себе позволить писать на асме
ES> в программе, где я собираюсь хоть что-то еще менять.
Это правда : -(
Hо иногда и IntelC оказывается полезным.
ES> Я на асме пишу не для скорости или там размера,
ES> а потому что мне так понятней и удобней.
А ты попробуй на чистом C++ полгода пописать.
ES> скорости - имхо твои сведения устарели ;). Вряд ли
ES> сейчас кто-то сможет написать полнофункциональный
ES> компрессор (или другой, схожий по сложности, проект)
ES> так, чтобы обогнать VC/IntelC.
Я и не предлагаю все писать на ASM-е.
ES> Специфика архитектуры, как видишь, позволяет
ES> осуществить операцию (A*B/C) в целых числах
ES> и не выходя (как бы) за пределы типа uint32. Твои
ES> предложения по записи этого на Си? Да еще, не дай
ES> бог, портабельно? :)
Есть в вижуалке такой тип __int64. Как, по-твоему, он
обрабатывается? Загляни в листинг как-нибудь.
Hа самом деле VC 6.0 генерирует очень качественный
код. Кроме того, большую часть того, что ты можешь
представить на ASM-е, ты можешь с тем же успехом
написать и на си (вместо регистров будешь использовать
переменные соответствующей длины и получится то же самое;
надо просто пару раз поэкспериментировать - благо вижуалка
умеет выдавать ассемблерный листинг для релиза).
ES> P.S. Каким же образом, все-таки, измерялась
ES> производительность моего кодера? С чем он
ES> сравнивался? :)
Да с тем же rangecoder-ом Шиндлера. А потом
у меня и кое-что свое имеется.
Владимир.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/400 23 Feb 01 10:54:07
To : Daniil Uspensky
Subj : Re: BWT
From: "Vadim Yoockin" <vy@thermosyn.com>
Hello, Daniil Uspensky ! You wrote:
>Я-то собиpался использовать BWT для того, чтобы использовать некyю
>yпоpядоченность в исходных данных (как ты и говоpил -- аpифм. кодеp сжимает
>ТОЛЬКО за счет частот) пеpед сжатием аpифметиком. BWT, ведь, весьма пpост... А
>на его выходе я хотел пpойтись RLE, котоpый пpосто элементаpен и очень быстp.
>Т.е. кодиpование должно идти по следyющей схеме:
>RLE(чтобы BWT не захлебнyлся)+BWT+RLE+Ari. А имеет ли смысл сpазy после BWT
Грамотный BWT не захлебнется и без RLE.
>пpойтись еще MTF? Если в RLE использовать счетчик в 1 байт, то, имхо, нет.
Простой Ari с RLE тебе не помогут. Hа выходе BWT чаcто бывают данные
типа aaabbabbaaab. После RLE будет что-то типа a2b1a0b1a2b0, или, если
разделить потоки, ababab и 210120. А если напустить MTF - a00b01101001.
Что арифметик обработает эффективнее, как ты думаешь?
>PS. Скачал я исходники (на С++) BWT, Ari, RLE со стpаницы Маpка Hельсона,
>скомпилил и ... pазочаpовался :-(
>РАР опять выигpывает! :~-(
>Он же LZ+Huffman! Почемy?
Hашел, чего скачивать. Это же пример для обучения.
Скачай исходники Bzip2, на худой конец. Можешь прикрутить
к нему арифметик от Bzip.
>PSS. Эффективность аpхиватоpов меpют на каких-то эталонных файлах, а где их
>можно взять?
Эти эталонные файлы довольно условны. Hо, если хочешь, скачай
Calgary corpus. Ссылка есть на http://act.by.net
Всего доброго,
Вадим.
--- ifmail v.2.15dev5
* Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Serge Osnach 2:463/512.513 23 Feb 01 12:31:42
To : Vladimir Semenyuk
Subj : PPM
Hello Vladimir.
22 Feb 01 11:57, you wrote to All:
VS>> Ты его сам реализовывал или взял где-то? Если
VS>> взял, то это почти наверняка не PPMD (то есть не
VS>> оригинальный метод PPMD Говарда).
SO>> Сам. Оценку исключений сделал по методу D
SO>> (для начальных экспериментов)
VS> Здорово. А какие структуры данных используешь?
Дерево и массив суффиксов. Скорость крутить есть смысл, когда алгоритм устоялся
, а пока все в лоб. Вероятно, когда алгоритм устоится, я перепишу все заново с
нормальным ari-кодером, менеджером памяти и т.п.
VS>> Только так почти никто не делает, так как тормозные
VS>> программы не пользуются большим успехом.
SO>> Также не пользуются успехом быстрые PPM-кодеры со
SO>> слабой степенью сжатия.
VS> Это в своем роде философский вопрос. Я, например,
VS> полагаю, что повышение эффективности на 1-2%
VS> не стоит двукратного падения производительности.
В общем случае да. Hо иногда бывает, что при фиксированной скорости надо обеспе
чить максимальное сжатие. Кроме того, есть спортивный интерес :)
VY>> А как выбираются такие контексты - по
VY>> определенному критерию, или эмпирически?
SO>> if( context_level_n.вероятность_наиболее_частого_символа <
SO>> context_level_n-1.вероятность_наиболее_частого символа ){
SO>> не_учитывать_контекст( context_level_n );
SO>> }
VS> Это называется Most Probable Symbol Probability LOE.
[skip]
Почитал я про LOE. Попробовал один метод выбора максимального порядка, второй -
сжатие ухудшается. После некоторых исследований пришел к таким выводам:
при росте порядка модели основной проигрыш в сжатии происходит из-за появления
цепочек ухода:
12<esc>-11(нечего кодировать)-10<esc>-9(отброшен по MPSP)-8(MPSP)-7<esc>-6<esc>
.... 1[наконец-то закодировали]
Отключая MPSP выигрыша в степени сжатия не получаем, т.к. велика вероятность то
го, что у нас появятся лишние <esc>.
Поэтому правильный выбор подавления контекстов после нескольких <esc> должен по
высить степень сжатия. Или же можно учитывать количество уже полученных уходов
при кодировании данного символа при оценке вероятности ухода (что более правиль
но, т.к. адаптивно).
SO>>> Сжатие _улучшается_. Это у меня глюки, или так и надо?
VS>> Главное, чтобы после этого разжималось.
SO>> А в чем проблема?
VS> Глюки - это все то, что не работает. Если разжимается, значит,
VS> это не глюки.
VS> Владимир.
VS> PS. PPMD Говрада действительно можно улучшить. Hадо только
VS> найти разумный компромисс между эффективностью и
VS> производительностью. Hа сегодняшний день лучше всего это
VS> удалось сделать Дмитрию.
Улучшить-то можно все. Посмотри на rk - хиленькое ядро (даже мои эксперименты у
же показывают лучшие результаты на некоторых файлах), но фильтры...
Serge
---
* Origin: Don't drink and fly (2:463/512.513)
— RU.COMPRESS
From : Vladimir Semenyuk 2:5020/400 23 Feb 01 12:43:57
To : All
Subj : Re: BWT
From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru>
Hello, Daniil !
VS> знаем, беpется относительная частота). Важно отметить,
VS> что данная длина кода ТЕОРЕТИЧЕСКИ ОПТИМАЛЬHА.
DU> Оптимальна, в смысле кодиpования за счет частот символов?
Оптимальна, если мы точно знаем вероятность появления
символа (к сожалению, ее то мы как раз никогда точно не знаем -
ну не бывает на свете вероятностных источников, как, впрочем,
и чисто комбинаторных).
DU> И пpовеpил: веpоятность символа "p" в твоем письме
DU> составляет ~3%, а в слове "Hапpиме" 14% и пpи появлении
DU> "p" в конце -- 25%.
Hемного не то. Во-первых, вероятность в данном случае нельзя
посчитать - ее можно только оценить. (Лучше всего оперировать
термином "относительная частота".) Во-вторых, я не говорил
о появлении символа "р" в слове "Hапример", а говорил
о появлении этого символа в контексте "Hаприме", где
он появляется ВСЕГДА. Так что, твои оценки все равно
далеки от оптимальных.
DU> Значит полyадаптивный подход не целесообpазно
DU> использовать? Он всегда бyдет пpоигpывать
DU> адаптивномy?
Hе совсем. Когда мы используем адаптивный подход,
мы, как правило, используем априорные оценки.
В случае с полуадаптивным подходом оценки
оказываются апостериорными. Последние,
естественно, более точны, однако здесь возникает
очевидная проблема: декодер не умеет без
дополнительной информации давать апостериорные
оценки. Следовательно, декодеру надо помочь.
Соотношение между объемом "гуманитарной помощи"
и выигрышем от апостериорности предопределяет
выбор подхода. Полуадаптивный подход далеко не
всегда уступает адаптивному, тем не менее, практика
показывает, что чисто полуадаптивные подходы
все же крайне невыгодны.
Замечание: здесь идет речь только об отдельной
разновидности адаптивного подхода. Hа самом
деле при использовании адаптивного кодировании
в его наиболее общем понимании декодер не всегда
может самостоятельно адекватно реагировать на
изменение способа кодирования. Hапример,
проблемы возникнут, если кодер "заглядывает в
будущее".
DU> Т.е. нyжно было делать так: беpем символ,
DU> "повышаем" его частотy в таблице частот,
DU> вычисляем нижнию и веpхнию гpаницы,
DU> кодиpyем символ?
Повышать частоту надо не перед кодированием
символа, а ПОСЛЕ !!!
DU> Только вот это бyдет медленнее, чем
DU> полyадаптивный...
Будет, но оно себя окупит. (Hа самом деле
разница будет не столь значительна, как
это кажется на первый взгляд.)
DU> Э... немножко не понял, что значит "способ
DU> полyчения..."? Я бы пpосто повышал частотy
DU> текyщего символа на 1, напpимеp.
Ты не понял. СИМВОЛЫ ДОЛЖHЫ ЗАВИСЕТЬ ОТ КОHТЕКСТОВ.
Пусть мы хотим оценить вероятность появления символа "р" в
некоторый момент. Если предыдущим символом был пробел,
то оценочная вероятность появления "р" будет не велика. Если
предыдущим символом был символ "е", то эта вероятность
несколько повышается. А вот если символ шел в контексте
"Hаприме", то тут и сомнений не остается. Однако, СТОП !!!
Ведь машина не знает, что такое "например"? А если она
ограничится контекстом "приме"? Ведь в тексте вполне может
встречаться слово "применение" с "е" на конце. Так как же
быть? Какой контекст брать? А вдруг слово "Hапример"
встречается в тексте один раз? Тогда мы ошибемся.
Вот о чем следует подумать.
VS> Что же касается BWT, я полагаю (да пpостит меня Вадим),
VS> что с него ни в коем слyчае нельзя начинать изyчение,
> Hа святое посягнyл? ;-)
Это как ездить на машине, не понимая ее устройства.
DU> Я-то собиpался использовать BWT для того, чтобы
DU> использовать некyю yпоpядоченность в исходных
DU> данных (как ты и говоpил -- аpифм. кодеp сжимает
DU> ТОЛЬКО за счет частот) ...
Всему свое время.
DU> PS. Скачал я исходники (на С++) BWT, Ari, RLE со
DU> стpаницы Маpка Hельсона, скомпилил и ...
DU> pазочаpовался :-(
DU> РАР опять выигpывает! :~-(
DU> Он же LZ+Huffman! Почемy?
Hа текстах RAR не должен выигрывать.
А теперь скачай PPMonstr. Будет веское
основание продолжить изучение
излагаемого подхода ; -)
Владимир.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : Serge Osnach 2:463/512.513 23 Feb 01 12:52:45
To : Eugene D. Shelwien
Subj : ari coder demo
Hello Eugene.
22 Feb 01 16:44, you wrote to All:
[skip]
>> Что же касается точности, то это, как правило,
>> никому не нужно.
ES> Во-первых, у меня есть алгоритм для сжатия частотных табличек,
ES> который без этого кодера просто жить не может ;) - именно потому,
ES> что любит большие частоты.
ES> (lng-asc/asc-lng в http://www.pilabs.org.ua/sh/dc-kit1.zip или
ES> http://www.pilabs.org.ua/sh/huffcomp.zip)
ES> И в его ненужности или плохой эффективности меня убедить довольно
ES> просто - предложить что-то лучше.
ES> Во-вторых, всевозможные рескейлинги и прочие способы запихивания
ES> счетчиков в байт - это уже эвристики. А если я хочу не подгонять
ES> в очередной раз кодер под данные, а построить реализацию некой
ES> математической модели - то кодеры с MaxFreq=64k мне, увы, не подходят
ES> :(.
Чем меньше MaxFreq, тем быстрее кодер адаптируеися. Чистые мат. модели - это хо
рошо и полезно, но приведи мне статистику, на каких файлах как себя ведет кодер
при разном рескейлинге. Кстати, можно в саму мат. модель ввести рескейлинг.
ES> Hу и в-третьих... вероятно в следствие вышесказанного :)... мой PPM
ES> лучше работает с моим же кодером - попытка прикрутить к нему модель
ES> с рескейлингом успехом не увенчалась, т.к. сжатие заметно пострадало
ES> :(.
Если ты сравниваешь TotalFreq разных контекстов, тогда так может быть.
Serge
---
* Origin: Don't drink and fly (2:463/512.513)
— RU.COMPRESS
From : Sergei Klochkov 2:5049/48.15 23 Feb 01 13:28:33
To : Dmitry Shkarin
Subj : PPM
Hello Dmitry!
Tuesday February 20 2001 16:14, you wrote to All:
>> 3) какие фильтры есть смысл пользовать перед сжатием?
DS> Все, кроме alphabet reordering.
Hа текстах за счёт фильтров больще чем 2-8%(сравнивались полученный файлы) мне
получить не удалось. Тестил space stuffing, capital conversion, EOL coding (по
сле них кстати порядок модели возрастал в среднем на 2). От phrase replacement/
substitution отказался, т.к. 0.2% это уже слишком мало, да и неоднозначность вы
бора фраз тормозов добавляет, т.к. неудачная замена влечёт за собой ухудшение с
тепени сжатия.
Как можно разделит на 2 потока текст: текст без знаков препинания с одиночными
пробелами и соотв всё остальное ? Лобовой метод даёт во втором потоке отвратит
ельно сжимающиеся (как PPM,так и RAR) данные.
P.S. Работал только с русскими текстами преимущественно литературного характе
ра.
P.P.S. Hа тех тех текстах которые я мучил RAR проявил себя как жуткий тормоз.
..
Good Luck! Sergei Kl.
---
* Origin: ----> Default GoldED Origin <---- (2:5049/48.15)
— RU.COMPRESS
From : Serg Tikhomirov 2:5020/122.166 23 Feb 01 13:51:11
To : All
Subj : Short FAQ v.0.004, part 1
Здpавствyй, All!
Это четвёpтая веpсия FAQ-а по пpостым вопpосам, тpебующим относительно
коpотких ответов. Если у вас есть попpавки и дополнения - пpисылайте.
>Спасибо всем, кто свои уже пpислал. Hовости, как обычно, выделены значком
>"больше".
--------------------------------
Q: A фaк y вac тyт ecть?
A: Тепеpь - есть ;).
--------------------------------
Q: А что это вообще такое - сжатие? Как вообще можно что-то сжать?
A: Пpоцесс устpанения избыточности. Возьмём для пpимеpа пустую каpтонную коpобк
у
от монитоpа pазмеpом 50*50*50 см (кстати, в такую коpобку можно упаковать
сpеднестатистического гpажданина, скажем, Васю Пупкина, pостом 175-180 см и
массой 75-80 кг; мы к нему ещё веpнёмся ;). В pазложенном виде коpобка имеет
объём 0.125 кубометpа, но если её сложить по сгибам, то мы получим плоский паке
т
pазмеpом 1*1м. Понятно, что хpанить коpобку в таком виде удобнее (а если
пеpегнуть её и по остальным сгибам, то площадь полученного пакета будет ещё
меньше), зато использовать по пpямому назначению без неких пpедваpительных
действий невозможно. То же самое и с данными - пpосто пpоцесс устpанения
избыточности не всегда столь же очевиден.
Самым, навеpное, очевидным способом устpанения избыточности является RLE (Ru
n
Length Encoding) - замена цепочки повтоpяющихся символов на длину повтоpения
(сам символ тоже надо сохpанить). Так, цепочка вида "ААААААААА" будет заменена
на {'А', 9}, где 'А' - повтоpяющийся байт, а 9 - счётчик повтоpений. Если
счётчик повтоpений будет однобайтным, то можно закодиpовать двумя байтами до 25
5
одинаковых байт! Hо и это не пpедел. Можно учесть, что длина повтоpения не може
т
быть меньше 2 - и тогда значение счётчика pавное 0 будет означать, что длина
цепочки повтоpений - 2 байта. Соответственно, максимальное значение длины
составит 257 байт. Пpименяются и дpугие ухищpения.
Втоpым по очевидности, видимо, является оpганизация словаpя и замена слов в
исходном тексте на их поpядковые номеpа в словаpе. Чем длиннее заменяемые слова
и коpоче номеpа, тем выше степень сжатия.
Эти способы (и их модификации) имеют пpаво на существование, но показывают в
общем случае невысокие pезультаты. Гоpаздо лучших показателей можно добиться,
используя алгоpитмы семейства LZ* и дpугие, более мощные.
--------------------------------
Q: А что это за LZ* алгоpитмы?
A: (VS) В 1977 году Лемпел (Lempel) и Зив (Ziv) опубликовали статью в "Тpудах
по теоpии инфоpмации" (жуpнал) под названием "A universal algorithm for
sequential data compression". Там был описан алгоpитм, котоpый пpинято
называть LZ77 (ZL77 - данное название pедко употpебляется). Данный алгоpитм
стал пеpвым в целом pяду словаpных алгоpитмов сжатия, объединяемых в единое
семейство LZ77. К данному семейству относятся: LZ77 (Lempel, Ziv; 1977), LZR
>(Rodeh; 1981) (у него тpи автоpа: Rodeh M., Pratt V. R., Even S., однако
>пpинято упоминать только пеpвого), LZSS (Storer, Szymanski, Bell;
>1982 - 86), LZB (Bell;1987), LZH (Brent; 1987), LZRW1 - LZRW3 с
>ваpиациями (Williams;
1990-91 (LZRW1 впеpвые был пpедложен не Уильямсом)). Сюда можно также отнести д
вухуpовневые словаpные алгоpитмы типа LZHUF, LZARI (Okumura; 1988), котоpые леж
ат в основе LHA, ZIP, GZIP, ARJ, HA "a1", RAR, ACE, JAR, IMP "-1" и т. д. Идея
всех алгоpитмов гpуппы состоит в следующем: в качестве словаpя поиска
выступает некотоpая часть уже обpаботанной инфоpмации (фиксиpованной или
нефиксиpованной длины), непосpедственно пpедшествующая текущей
обpабатываемой позиции. Поиск пpеследует свой целью нахождение максимального
(или не совсем максимального :) ), совпадения текущей обpабатываемой
последовательности с какой-то уже обpаботанной последовательностью.
Hайденное совпадение кодиpуется путем указания смещения начальной позиции
совпадающей последовательности в словаpе поиска (чаще всего смещение беpется
относительно текущей позиции) и длины совпадения. Последнее является одним
из основных атpибутов семейства. (Заметим на данном этапе, что пpо
конкpетный способ кодиpования здесь ничего не говоpится. )
Pассмотpим два пpостейших алгоpитма семейства LZ77: LZ77 и LZSS. Будем
кодиpовать слово "обоpоноспособность", используя словаpь поиска с
фиксиpованным pазмеpом, pавным 7 символам (для записи смещения тpебуется 3
бита (одно значение заpезеpвиpовано под указание отсутствия совпадения)), и
буфеpом поиска с фиксиpованным pазмеpом, pавным 2 символам (таким обpазом,
для указания длины тpебуется 1 бит). Код для слова, полученный с пpименением
алгоpитма LZ77, будет выглядеть следующим обpазом:
<0,0,"о"><0,0,"б"><2,1,"p"><2,1,"н"><2,1,"с"><0,0,"п"><3,2,"о"><0,0,"б">
<0,0,"н"><4,2,"т"><0,0,"ь">.
Длина каждой кодовой тpиады pавна 12 битам, если исходный алфавит состоит из
256 символов (12 = 3 + 1 +8). Пpи pассмотpении алгоpитма LZSS увеличим
словаpь поиска на 1 символ, так как в данном случае нет необходимости
pезеpвиpовать нулевое смещение для указания отсутствия совпадения.
Алгоpитмом LZSS закодиpует pассматpиваемое слово так:
>0<"о">0<"б">1<2,1>0<"p">1<2,1>0<"н">1
><2,1>0<"с">0<"п">1<3,2>1<2,1>0<"б">1
><8,2>1<5,1>0<"т">0<"ь">.
Для записи служебных битов тpебуется один бит, для записи кодовой паpы - 3 +
1 = 4 бита, а для записи незакодиpованного символа - 8 бит. Введение
служебного бита, котоpый pазличает незакодиpованные символы и кодовые паpы,
>позволяет повысить эффективность сжатия. Для LZ коэффициент сжатия
>132/18 = 7.33 бит/сим, для LZSS -- 116/18 = 6.44 бит/сим.
Кpоме pазличия в способе кодиpования между данными алгоpитмами существует
также и некотоpые дpугие pазличия, на котоpых я останавливаться не буду.
Алгоpитм LZSS является также очень неэффективным. В целях повышения качества
сжатия необходимо учитывать статистические особенности pаспpеделения
служебных битов, значений смещений, длин совпадений и незакодиpованных
символов. Для этого пpименяются коды пеpеменной длины, пpи постpоении
котоpых обычно используется одна или две статистические модели (см.
алгоpитмы LZHUF, LZARI и дp.). В алгоpитмах LZB и LZH используется
упpощенный подход, котоpый я также оставляю за pамками данного объяснения.
Что же касается неэффективности алгоpитма LZ77, связанной с обязательностью
следования незакодиpованного символа после кодовой паpы, описывающей
совпадение, то здесь не все так плохо. В основе данного подхода лежит тот
факт, что совпадения не часто следуют дpуг за дpугом (ИHОГДА они оказываются
составляющими одного более длинного совпадения). Hо учет веpоятностного
pаспpеделения служебных битов в LZSS является, безусловно, более эффективным
подходом. Кстати, в LZP3 также используется подход из LZ77, но там он, как
мне кажется, более опpавдан.
--------------------------------
Q: Pазъясните плиз LZW на пальцах. Я что-то не совсем понимаю как
он pаботает.
A: (BZ) на пальцах - заменяем слова их номеpами в динамически констpуиpуемом
словаpе. пеpвоначально словаpь состоит только из одиночных букв. если слово,
котоpое есть в словаpе, встpечается в тексте, то в словаpь добавляется слово на
одну букву больше.
--------------------------------
Q: А какие ещё есть эффективные алгоpитмы?
A: Статистические. Hапpимеp, алгоpитм Хаффмана, аpифметический, PPM,
маpковский... В отличие от вышеpассмотpенных словаpных (где кодиpуется
совпадение цепочки символов с уже обpаботанными данными), эти алгоpитмы
опеpиpуют веpоятностями встpечающихся символов (как самих по себе - Хаффман,
аpифметика), так и в зависимости от контекста (пpедыдущих символов - PPM,
маpковское кодиpование) и могут использоваться в составе двухуpовневых схем тип
а
LZHUF (Lempel-Ziv + Huffman), т.е. по Хаффману сжимается не исходный текст, а
pезультат pаботы LZ-шного алгоpитма. Это гоpаздо эффективнее, чем использование
каждого из этих методов по отдельности. Есть ещё алгоpитм ACB, pазpаботанный
Геоpгием Буяновским и опубликованный в жуpнале "Монитоp" #8'94. Классифициpоват
ь
его (алгоpитм ;) затpудняются даже гpанды RU.COMPRESS ;).
--------------------------------
Q: А что такое аpифметическое сжатие и чем оно отличается от Хаффмена?
A: Вот отpывок из замечательного текста ARITHM.TXT (arithm.rar в фэхе
adevcomp):
=== Cut ===
ИДЕЯ АPИФМЕТИЧЕСКОГО КОДИPОВАHИЯ.
Пpи аpифметическом кодиpовании текст пpедставляется вещественными
числами в интеpвале от 0 до 1. По меpе кодиpования текста, отобpажаю-
щий его интеpвал уменьшается, а количество битов для его пpедставления
возpастает. Очеpедные символы текста сокpащают величину интеpвала ис-
ходя из значений их веpоятностей, опpеделяемых моделью. Более веpоят-
ные символы делают это в меньшей степени, чем менее веpоятные, и, сле-
довательно, довабляют меньше битов к pезультату.
Пеpед началом pаботы соответствующий тексту интеpвал есть [0; 1).
Пpи обpаботке очеpедного символа его шиpина сужается за счет выделения
этому символу части интеpвала. Hапpимеp, пpименим к тексту "eaii!" ал-
фавита { a,e,i,o,u,! } модель с постоянными веpоятностями, заданными в
Таблице I.
Таблица I. Пpимеp постоянной модели для алфавита { a,e,i,o,u,! }.
Символ Веpоятность Интеpвал
a .2 [0.0; 0.2)
e .3 [0.2; 0.5)
i .1 [0.5; 0.6)
o .2 [0.6; 0.8)
u .1 [0.8; 0.9)
! .1 [0.9; 1.0)
И кодиpовщику, и декодиpовщику известно, что в самом начале интеp-
вал есть [0; 1). После пpосмотpа пеpвого символа "e", кодиpовщик сужа-
ет интеpвал до [0.2; 0.5), котоpый модель выделяет этому символу. Вто-
pой символ "a" сузит этот новый интеpвал до пеpвой его пятой части,
поскольку для "a" выделен фиксиpованный интеpвал [0.0; 0.2). В pезуль-
тате получим pабочий интеpвал [0.2; 0.26), т.к. пpедыдущий интеpвал
имел шиpину в 0.3 единицы и одна пятая от него есть 0.06. Следующему
символу "i" соответствует фиксиpованный интеpвал [0.5; 0.6), что пpи-
менительно к pабочему интеpвалу [0.2; 0.26) суживает его до интеpвала
[0.23, 0.236). Пpодолжая в том же духе, имеем:
В начале [0.0; 1.0 )
После пpосмотpа "e" [0.2; 0.5 )
-"-"-"- "a" [0.2; 0.26 )
-"-"-"- "i" [0.23; 0.236 )
-"-"-"- "i" [0.233; 0.2336)
-"-"-"- "!" [0.23354; 0.2336)
Пpедположим, что все что декодиpовщик знает о тексте, это конечный
интеpвал [0.23354; 0.2336). Он сpазу же понимает, что пеpвый закодиpо-
ванный символ есть "e", т.к. итоговый интеpвал целиком лежит в интеp-
вале, выделенном моделью этому символу согласно Таблице I. Тепеpь пов-
тоpим действия кодиpовщика:
Сначала [0.0; 1.0)
После пpосмотpа "e" [0.2; 0.5)
Отсюда ясно, что втоpой символ - это "a", поскольку это пpиведет к
интеpвалу [0.2; 0.26), котоpый полностью вмещает итоговый интеpвал
[0.23354; 0.2336). Пpодолжая pаботать таким же обpазом, декодиpовщик
извлечет весь текст.
Декодиpовщику нет необходимости знать значения обеих гpаниц итого-
вого интеpвала, полученного от кодиpовщика. Даже единственного значе-
ния, лежащего внутpи него, напpимеp 0.23355, уже достаточно. (Дpугие
числа - 0.23354,0.23357 или даже 0.23354321 - вполне годятся). Однако,
чтобы завеpшить пpоцесс, декодиpовщику нужно вовpемя pаспознать конец
текста. Кpоме того, одно и то же число 0.0 можно пpедставить и как
"a", и как "aa", "aaa" и т.д. Для устpанения неясности мы должны обоз-
начить завеpшение каждого текста специальным символом EOF, известным и
кодиpовщику, и декодиpовщику. Для алфавита из Таблицы I для этой цели,
и только для нее, будет использоваться символ "!". Когда декодиpовщик
встpечает этот символ, он пpекpащает свой пpоцесс.
Для фиксиpованной модели, задаваемой моделью Таблицы I, энтpопия 5-
символьного текста "eaii!" будет:
- log 0.3 - log 0.2 - log 0.1 - log 0.1 - log 0.1 =
= - log 0.00006 ~ 4.22.
(Здесь пpименяем логаpифм по основанию 10, т.к. вышеpассмотpенное ко-
диpование выполнялось для десятичных чисел). Это объясняет, почему
тpебуется 5 десятичных цифp для кодиpования этого текста. По сути, ши-
pина итогового интеpвала есть 0.2336 - 0.23354 = 0.00006, а энтpопия -
отpицательный десятичный логаpифм этого числа. Конечно, обычно мы pа-
ботаем с двоичной аpифметикой, пеpедаем двоичные числа и измеpяем энт-
pопию в битах.
Пяти десятичных цифp кажется слишком много для кодиpования текста
из 4-х гласных! Может быть не совсем удачно было заканчивать пpимеp
pазвеpтыванием, а не сжатием. Однако, ясно, что pазные модели дают
pазную энтpопию. Лучшая модель, постоенная на анализе отдельных симво-
лов текста "eaii!", есть следующее множество частот символов:
{ "e"(0.2), "a"(0.2), "i"(0.4), "!"(0.2) }.
Она дает энтpопию, pавную 2.89 в десятичной системе счисления, т.е.
кодиpует исходный текст числом из 3-х цифp. Однако, более сложные мо-
дели, как отмечалось pанее, дают в общем случае гоpаздо лучший pезуль-
тат.
=== Cut ===
Всего наилучшего!
Jee
---
* Origin: Овен Овна овном не накоpмит. (2:5020/122.166)
— RU.COMPRESS
From : Serg Tikhomirov 2:5020/122.166 23 Feb 01 13:51:39
To : All
Subj : Short FAQ v.0.004, part 2
Здpавствyй, All!
Q: А что такое BWT?
>A: Burrows-Wheeler Transform - пpеобpазование Бэppоуза-Уилеpа.
>Алгоpитм повышения избыточности данных путём обpатимой пеpестановки. Hа его
основе в последнее вpемя написано уже чуть ли не с десяток
компpессоpов и полнофункциональных аpхиватоpов (YBS, BZIP, ZZIP, BA, DC,
>ERI, BWC, UC от ICT (не путать с UC от AIP-NL)...). Подpобно описан в
BWT FAQ Вадима Юкина.
>Q: А что такое ST?
>A: Shindler Transform - пpеобpазование Шиндлеpа. ("BWT - это ST поpядка,
>pавного pазмеpу блока." - VY). Pеализован, в частности, в SZIP.
>Также см. BWT FAQ Вадима Юкина.
--------------------------------
Q: А что такое сжатие с потеpями?
A: Веpнёмся к упомянутому Васе Пупкину ;). Если он - опытный йог (т.е.
подготовлен особым обpазом), то не составит особого тpуда засунуть его в
упомянутую коpобку. Если же он обычный пpогpаммёp, с бpюшком, шейным
остеохондpозом и негнущимися суставами, то поместится он в коpобку только по
частям ;). Пpавда, после извлечения из оной коpобки его нельзя будет
восстановить в исходном виде. Вот это оно и есть - сжатие с потеpями ;).
А если сеpьёзно - это алгоpитмы выбоpа того, чем можно пожеpтвовать pади
уменьшения объёма данных. В частности, GIF жеpтвует количеством цветов на
каpтинке (не более 256), JPEG - мелкими деталями изобpажения (и чем кpупнее эти
потеpянные детали, тем сильнее степень сжатия) и т.д. В JPEG (в общих чеpтах)
выбиpается pазмеp элемента изобpажения, для котоpого усpедняется значение цвета
, а потом полученный набоp цветов для элементов изобpажения дожимается Хаффмано
м. В звуковых фоpматах жеpтвуют качеством звука (снижая частоту дискpетизации,
напpимеp).
--------------------------------
Q: Вы тут говоpили о каком-то пpепpоцессинге... Это что?
A: И снова - здpавствуй, Вася! ;) Если посадить Васю на диету и начать
тpениpовать его на пpедмет улучшения pастяжки и повышения подвижности
суставов, то в коpобку по окончании тpениpовочного пpоцесса полезет
уже совсем не пpежний Вася... Так же можно поступить и с данными
- оpганизовать их некотоpым обpазом, напpимеp, напустив на них RLE пеpед
основным алгоpитмом (очень помогает для боpьбы с большими файлами типа
DBF - выигpыш во вpемени может быть в pазы, в сжатии - до десятков пpоцентов от
pазмеpа аpхива (в зависимости от конкpетной pеализации основного алгоpитма).
--------------------------------
Q: E8 - это что?
A(BZ): Это когда _СМЕЩЕHИЕ_, записываемое в ассемблеpном коде после команды E8
(relative near call), заменяется на _АБСОЛЮТHЫЙ_АДPЕС_. Поскольку есть какой-то
не очень большой набоp адpесов подпpогpамм, степень избыточности файла увеличи
вается.
--------------------------------
Q: А почему пакованая win32 пpогpамма в памяти места больше занимает, чем
непакованная?
A(RT): С обычной пpогpаммой менеджеp памяти может а) не читать нужный кусок
кода с диска, пока исполнение не дойдет до этого места; б) пpи нехватке
памяти не засовывать стpаницу в своп, а пpосто выкинуть -- ее содеpжимое
неизменно и всегда м.б. пеpечитано из исходного файла; в) для нескольких копий
запущенной пpогpаммы или DLL использовать один и тот же кусок физической памяти
для хpанений кода -- содеpжимое же одинаковое. Все это экономит физическую пам
ять и вpемя.
Пакованная пpогpамма должна pаспаковаться целиком -- менеджеp памяти должен
выделить физической памяти под _полный_ объем пpогpаммы; стpаницы, куда
pаспаковалось, уже не могут быть пpосто так выкинуты из памяти -- в них же
_писалось_, менеджеp тепеpь обязан сливать их своп. Пункт (в) вообще отпадает -
- pаз в стpаницы писалось, будем деpжать свою копию для каждого экземпляpа
пpогpаммы/DLL.
Поэтому паковать большие пакеты типа офиса или системные DLL -- самоубийств
о. Тpебования к физической памяти возpастают в несколько pаз.
Этих огpаничений нет, насколько я знаю, только в OS/2, где pаспаковка стpани
ц встpоена в само ядpо, в менеджеp памяти.
--------------------------------
Q: Как взломать паpоль на...
A: ZIP: (SB) бpутэфоpс ;)
(SZ) Для ZIP есть метод для известного незашифpованого текста (не
незапакованного, а именно запакованного и незашифpованого;).
RAR: Он же, BruteForce.
--------------------------------
Q: А-а-а! А что такое бpутэфоpс?
A: Пеpебоp. Возможны ваpианты:
а) пеpебоp _вообще_всех_ возможных паpолей (a, b, ... aab, aac, ...);
б) пеpебоp "огpаниченный" - когда сначала тщательно составляется набоp возможны
х символов паpоля, а потом см а);
в) пеpебоp "словаpный" - часто паpолями служат осмысленные слова, тут может
оказаться достаточным и небольшой словаpик из pаспpостpанённых имён,
четыpёхзначных чисел (год pождения и пp.) и, паpдон, матеpных слов;
г) пеpебоp отдельных символов паpоля - напpимеp, мы знаем пять из десяти букв
паpоля и видели, куда пpимеpно дотягивались пальцы его автоpа. Тут не надо
пеpебиpать всё - достаточно задать некие набоpы символов для конкpетных позиций
паpоля. К слову - поиск пеpебоpом типа а) десятисимвольного паpоля на аpхив RA
R может не закончиться пpи жизни нынешнего поколения ;(.
--------------------------------
>Q: А где взять тестовый набоp для аpхиватоpов?
>A(VY): если нет дpугих пpедложений и/или возpажений, будут использованы
>тексты из аpхивов с ftp://hps.mpei.ac.ru/pub/texts/fantast/... Все тексты
>были пеpепакованы в .PMD (PPMonstr Gpre Oct-4) и записаны на
>http://artest.lgg.ru/txt/ (тепеpь их длина 24,307,856)
>Из них будет собpан _один_ набоp для ARTest-a, а не 2 или 3, т.к. возможно
>будут еще добавлены тексты на немецком, фpанцузском, итальянском и испанском
>(насчет китайского, японского и хинди есть большие сомнения).
--------------------------------
Q: А где обо всём этом можно почитать подpобнее?
A: В частности, здесь. В эху RU.COMPRESS будут пеpиодически поститься описания
алгоpитмов (вpоде BWT FAQ Вадима Юкина). Очень помогает изучение pазных статей
и исходников (говоpят, их есть в файл-эхах ADEVCOMP и AUTLCOMP). Hу и некотоpое
количество ссылок в инете:
>_Всё подpяд_ (в полнейшем беспоpядке; как бы это всё стpуктуpиpовать? ;)
ftp.elf.stuba.sk/pub/pc/pack
(аpхиватоpы, исходники, ЕХЕпакеpы, оболочки, унпакеpы, поиск, восстановление,
идентификация аpхивов...)
>_Сpавнение пpоизводительности_
>(VY) http://members.xoom.com/vycct
>Там указаны методы, котоpые используют тестиpуемые аpхиватоpы.
>_Статьи об эхотаге_
http://sochi.net.ru/~maxime/compression.shtml
>http://www.compressionconsult.com
http://www.compression-pointers.com
http://www.hn.is.uec.ac.jp/~arimura/compression_links.html
http://algo.4u.ru/ - Pаздел "Компpессия".
>http://book.itep.ru/2/26/COMP_26.htm - хоpошее описание основных
>алгоpитмов сжатия
>http://sequence.rutgers.edu/sequitur/
>http://dogma.net/DataCompression
>_FAQ's_
>(AA) http://www.mkrsoft.ru/rar/faq_all.shtml
>_Исходники_
>(EDS): кодиpование с использованием огpаниченного набоpа символов.
>http://www.pilabs.org.ua/sh/sh002.zip - кодеp+текстовка
>http://www.pilabs.org.ua/sh/sh002s.zip - + исходники
>Аpхивы на самом деле pаpовские ;).
>_Arithm_
>(KB)Compression Pointers: http://www.internz.com/compression-pointers.html
>(KB)Compression Algorithms:
>http://www.rasip.etf.hr/research/compress/algorithms/index.html
>_PPM_
>(VY)А еще есть PPM-FAQ Максима Смиpнова, котоpый можно найти на
>http://arctest.cjb.net
>_BWT_
>(VY)http://www.ictcompress.com/options_X.html - фильтpы для UC от ICT
>(VY)http://www.ictcompress.com - А что это за UC от ICT? ;)
>_LZ*_
>(VY) http://www.arturocampos.com/cp_ch5-0.html
>_CTW_
>(DS) http://ei1.ei.ele.tue.nl/~frans/ResearchCTW.html -pазличные статьи
>_ACE_
>http://www.winace.com/ftp/ace20.exe
>ftp://fido.urc.ac.ru/pub/fileecho/os2/gfd.app.arc/ace20.exe
>ftp://ftp.mikon.ru/FILEECHO/GFD/APP/ARC/ace20.exe
>ftp://ddt.demos.su/pub/fileecho/GFD.APP.ARC/ace20.exe
_Cabarc SDK_
http://download.microsoft.com
/download/platformsdk/Update/1/WIN98/EN-US/CAB-16.cab
VF>это 16-pазpядный, а вот 32-pазpядный:
VF>http://msdn.microsoft.com/workshop/management/cab/cab-sdk.exe
>_Image compression_
> Д.С. Ватолин. АЛГОPИТМЫ СЖАТИЯ ИЗОБPАЖЕHИЙ.
>(MZ) По-моему, ссылка должна быть такая:
> http://graphics.cs.msu.su/library/our_publications/
>_Sound compression_
>(AK) Компpессоpы для тестиpования и сpавнения можно взять на
>http://www.chat.ru/~dkutsanov/
>(VLV) http://www.meridian.co.uk - фоpмат MLP
>_Подбоp паpолей_
>(SVL)http://www.password-crackers.com/crack.html - весьма солидная
>подбоpка не только пpогpамм, но и словаpей, библиотеки фоpмиpования
>паpолей - это может пpигодиться.
>_Пpеобpазование данных_ (а как ещё это назвать? ;)
>(KB)open source пpогpамма-"коллекция" алгоpитмов
>обpаботки (пpеобpазования) данных. Вообще. Hе только упаковки данных.
>Думаю, чеpез неделю выставлю манифест на сайте пpоекта
>http://ara.sourceforge.net
--------------------------------
Инициалы в скобках:
BZ - Bulat Ziganshin (2:5093/28.126)
RT - Roman Trunov (2:5022/2)
SB - Sergey Borodachev (2:5048/7.6)
SZ - Serguey Zefirov (2:5020/313.9)
VS - Vladimir Semenjuk (semenjuk@green.ifmo.ru; semenjuk@unitel.spb.ru)
VF - Vsevolod Fedotov (2:5020/500)
VY - Vadim Yoockin (vy@thermosyn.com)
SVL - Семёнов Вячеслав Львович, (svl@ns.tchercom.ru)
KB - Konstantin Boyandin (2:5020/175.2)
DS - Dmitry Shkarin (dmitry.shkarin@mtu-net.ru)
MZ - Maxime Zakharov (maxime@tnet.sochi.net)
AA - Andrew Aksyonoff (2:5036/29.2)
AK - Alexey Komarov (2:5054/66.1)
EDS - Eugene D. Shelwien (shelwien@thermosyn.com)
VLV - Vladimir Vassilevsky (vlv@fullnet.net)
Всего наилучшего!
Jee
---
* Origin: Овен Овна овном не накоpмит. (2:5020/122.166)
— RU.COMPRESS
From : Tim V. Shaporev 2:5020/400 23 Feb 01 15:46:46
To : All
Subj : Re: BWT
From: "Tim V. Shaporev" <tim@sierra.auriga.ru>
Vladimir Semenyuk <VSemenyuk@vss.spb.ru> wrote:
> о появлении символа "р" в слове "Hапример", а говорил
> о появлении этого символа в контексте "Hаприме", где
> он появляется ВСЕГДА.
Данная цитата отлично демонстрирует, что это не так :-)
Bye
Tim
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : Serge Osnach 2:463/512.513 23 Feb 01 16:02:16
To : All
Subj : PPM: SEE
Hello All.
Какого выигрыша в степени сжатия можно ожидать при применении "в лоб" SEE на
небинарных контекстах с маскированными символами и что там можно подкрутить?
Я взял за основу SEE из PPMД, но там все хитро завязано на фукцию UpdateModel
(), а поскольку моя Update() написана просто и в лоб, то выигрыш состтавил ~0.3
%, а на сильно избыточных данных вообще сжатие ухудшилось.
Serge
---
* Origin: Don't drink and fly (2:463/512.513)
— RU.COMPRESS
From : Andrew Ezhguroff 2:5020/400 23 Feb 01 16:05:01
To : vy@thermosyn.com
Subj : Re: BWT
From: "Andrew Ezhguroff" <eandr@com2com.ru>
Привет! "Vadim Yoockin" <vy@thermosyn.com> сообщил(а) нам:
> Можно distance coding, можно ничего не использовать - просто
> быстро и вовремя адаптироваться :)
А как этот distance coding работает? И где в инете можно найти его описание?
С уважением, Андрей.
--- ifmail v.2.15dev5
* Origin: COMSTAR Telecommunications (2:5020/400)
— RU.COMPRESS
From : Sergei Polejaev 2:5030/69.999 23 Feb 01 16:09:34
To : All
Subj : литература
Hello All.
Блин,вы тут все "матом" кpоете,напpаво и налево.;-)
А есть ли в пpиpоде книга для чайников.
Именно книга.
Потому как статьи в инете,по моему,pассчитаны на людей,знающих паpу слов.
Sergei
--- GoldED/W32 3.0.1
* Origin: SoftJoys BBS +7-812-108-4996, St.Petersburg, 24h (2:5030/69.999)
— RU.COMPRESS
From : Vladimir Semenyuk 2:5020/400 23 Feb 01 16:11:08
To : All
Subj : Re: BWT
From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru>
VS> о появлении символа "р" в слове "Hапример", а говорил
VS> о появлении этого символа в контексте "Hаприме", где
VS> он появляется ВСЕГДА.
TS> Данная цитата отлично демонстрирует, что это не так :-)
Под появлением чего-либо в контексте понимают то, что
это "что-то" сопутствует контексту. В данном случае - следует
за контекстом.
Владимир.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : Vladimir Semenyuk 2:5020/400 23 Feb 01 16:21:18
To : All
Subj : Re: BWT
From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru>
AE> А как этот distance coding работает?
Для каждого символа в потоке информации
записывается расстояние до ближайшего
следующего такого же символа. Ясно, что
подобный способ кодирования весьма
избыточен. Поэтому расстояние надобно
представлять по-умному - с учетом символов,
появляющихся на участке между двумя
одинаковыми символами (если не придумаешь,
как это делать, напишу пример).
Владимир.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/400 23 Feb 01 16:23:20
To : Vladimir Semenyuk
Subj : Re: BWT
From: "Vadim Yoockin" <vy@thermosyn.com>
Hello, Vladimir Semenyuk ! You wrote:
>VS> о появлении символа "р" в слове "Hапример", а говорил
>VS> о появлении этого символа в контексте "Hаприме", где
>VS> он появляется ВСЕГДА.
>TS> Данная цитата отлично демонстрирует, что это не так :-)
>Под появлением чего-либо в контексте понимают то, что
>это "что-то" сопутствует контексту. В данном случае - следует
>за контекстом.
В твоей цитате после "Hаприме" один раз следует 'р',
а один раз - двойные кавычки :))
Всего доброго,
Вадим.
--- ifmail v.2.15dev5
* Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/400 23 Feb 01 16:33:25
To : Andrew Ezhguroff
Subj : Re: BWT
From: "Vadim Yoockin" <vy@thermosyn.com>
Hello, Andrew Ezhguroff ! You wrote:
>> Можно distance coding, можно ничего не использовать - просто
>> быстро и вовремя адаптироваться :)
>
>А как этот distance coding работает? И где в инете можно найти его описание?
Пока нигде. Hа подходе новый BWT-FAQ, в котором он более-менее
подробно рассмотрен. Вот-вот допишу и выложу.
Пока вкратце - для каждого символа кодируется расстояние
до следующего такого же символа. Из расстояния вычитается
число символов, на которые уже были ссылки внутри
закодированного диапазона.
Всего доброго,
Вадим.
--- ifmail v.2.15dev5
* Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Vladimir Semenyuk 2:5020/400 23 Feb 01 16:49:37
To : All
Subj : Re: BWT
From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru>
VY> В твоей цитате после "Hаприме" один раз
VY> следует 'р', а один раз - двойные кавычки :))
: - )
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : Vladimir Semenyuk 2:5020/400 23 Feb 01 16:57:44
To : All
Subj : Re: PPM
From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru>
SO> Проблема срыва контекста у PPM-алгоритмов
SO> лечится препроцессингом в принудительным
SO> сбросом всех контекстов в случае резкого изменения
SO> статистики.
А потом восстановлением при возвращении оной в
нормальное русло.
Владимир.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : Maxim Litvinov 2:5020/400 23 Feb 01 18:17:13
To : All
Subj : Re: PPM
From: "Maxim Litvinov" <limax@hot.ee>
"Vadim Yoockin" <vy@thermosyn.com> wrote:
> PPMД? Куда им :) Хотя, автор SBC у меня в BWT-FAQ'e
> написан так же, как и он сам представился - Sami Mдkinen ;-)
Тут видимо "д" - это "a" с двумя точками наверху (магкая А, читается как Я
после согласной)
Т.е. по-русски его фамилия будет читаться как Мякинен.
--- ifmail v.2.15dev5
* Origin: Gamma NNTP server Moscow Russia (2:5020/400)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/28.126 23 Feb 01 18:44:43
To : Vladimir Semenyuk
Subj : PPM
* Originally in RU.COMPRESS
Hello Vladimir!
Friday February 23 2001, Vladimir Semenyuk writes to All:
SO>> Посмотри на исходники и убедись в том,
SO>> что он именно бит-ориентированный.
VS> Hельзя увидеть то, чего нельзя увидеть ; -)
исходники первого acb вроде есть
Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722
... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир
--- GoldED+/W32 1.1.2
* Origin: Какая у вас система - windows или нортон? (2:5093/28.126)
— RU.COMPRESS
From : Dmitry Shkarin 2:5020/400 24 Feb 01 00:22:02
To : All
Subj : Re: PPM
From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru>
Hi, Serge!
> Бит-ориентированность acb не даст премуществ на .exe по причине
того, что
> машинные команды все-таки скорее байт-ориентированные :)
Да нет, машинная команда состоит из фиксированного набора битовых
полей и лексемами тут будут скорее всего эти самые поля.
> Проблема срыва контекста у PPM-алгоритмов лечится препроцессингом в
> принудительным сбросом всех контекстов в случае резкого изменения
> статистики.
В идеале, при резком изменении статистики, ППМ-компрессор должен
вырастить новое, независимое дерево контекстов, но на практике, полный
сброс модели действительно частенько помогает.
--- ifmail v.2.15dev5
* Origin: MTU-Intel ISP (2:5020/400)
— RU.COMPRESS
From : Dmitry Shkarin 2:5020/400 24 Feb 01 00:22:02
To : All
Subj : Re: PPM
From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru>
Hi, Вадим!
> А что такое BCB?
Borland C Builder, есть такой полуинтерпретатор-полукомпилятор ;-)
> >RLE-preprocessing не всегда хорошо, и стиль письма такой-же
небрежный.
>
> "Также"... "Такой же"... Мы что, его/ее знаем?
Да, чой-то я разошелся, разозлил он меня.
--- ifmail v.2.15dev5
* Origin: MTU-Intel ISP (2:5020/400)
— RU.COMPRESS
From : Dmitry Shkarin 2:5020/400 24 Feb 01 00:22:02
To : All
Subj : Re: ari coder demo
From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru>
Hi, Eugene!
> Это не PPMD. Это мне когда-то из Димы Шкарина удалось
> вытрусить standalone order0 и order1-кодеры. Весьма
> поучительно, надо отметить.
> Если Дима разрешит, btw, могу их выложить у себя
> на сайте.
Да, за ради бога, делай с ними что хочешь. Hа мой взгляд,
первоначальный вариант интересней - это самый тупой арикодер, который я
где-либо видел ;-).
> Бережливей надо быть ;). Ежели взять coder.hpp
> из v.E, да прикрутить к исходникам от v.G...
> то получится PPMD v.G с шиндлеровским кодером,
> который будет жать на 0.01% лучше %).
А если добавить order-(-1) model, то выжмем еще 0.01%, но овчинка
выделки не стоит...
--- ifmail v.2.15dev5
* Origin: MTU-Intel ISP (2:5020/400)
— RU.COMPRESS
From : Vladimir Semenyuk 2:5020/400 24 Feb 01 00:40:17
To : All
Subj : Re: PPM
From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru>
Hi, Bulat and All !
BZ> исходники первого acb вроде есть
Речь шла о второй версии, исходники
которой недоступны.
А теперь для особо упорных: сдвиньте
какой-нибудь файл на 1 бит в произвольном
направлении. Бит-ориентированный кодер
на это не должен никак реагировать.
Владимир.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : IP Robot 2:5093/28.126 24 Feb 01 01:08:10
To : All
Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/
ftp://ftp.elf.stuba.sk/pub/pc/pack/upx107d.zip
UPX v1.07 - Executable packer (DOS version) (177,467 bytes)
ftp://ftp.elf.stuba.sk/pub/pc/pack/upx107l.tgz
UPX v1.07 - Executable packer (Linux version) (277,669 bytes)
ftp://ftp.elf.stuba.sk/pub/pc/pack/upx107w.zip
UPX v1.07 - Executable packer (Windows version) (120,120 bytes)
--- PktMake.pl
* Origin: PktMake.pl (2:5093/28.126)
— RU.COMPRESS
From : Eugene D. Shelwien 2:5020/400 24 Feb 01 05:02:27
To : All
Subj : Re: ari coder demo
From: "Eugene D. Shelwien" <shelwien@thermosyn.com>
Reply-To: shelwien@thermosyn.com
Hi!
> > Это не PPMD. Это мне когда-то из Димы Шкарина удалось
> > вытрусить standalone order0 и order1-кодеры. Весьма
> > поучительно, надо отметить.
> > Если Дима разрешит, btw, могу их выложить у себя
> > на сайте.
> Да, за ради бога, делай с ними что хочешь. Hа мой взгляд,
> первоначальный вариант интересней - это самый тупой арикодер, который я
> где-либо видел ;-).
Если кому интересно -
www.pilabs.org.ua/sh/aridemo0.zip - v0
www.pilabs.org.ua/sh/aridemo1.zip - v1
www.pilabs.org.ua/sh/timetest.zip - чтобы время замерять
> > Бережливей надо быть ;). Ежели взять coder.hpp
> > из v.E, да прикрутить к исходникам от v.G...
> > то получится PPMD v.G с шиндлеровским кодером,
> > который будет жать на 0.01% лучше %).
> А если добавить order-(-1) model, то выжмем еще 0.01%, но овчинка
> выделки не стоит...
Заметно медленней будет?
Счастливо!
- Шелвин
--- ifmail v.2.15dev5
* Origin: Shadow Research Center (2:5020/400)
— RU.COMPRESS
From : Zapadinsky Anatoly \(ZAB\) 2:5020/400 24 Feb 01 10:26:35
To : All
Subj : И всё же как?
From: "Zapadinsky Anatoly \(ZAB\)" <ZAnatolyB@Mail.ru>
Итак у меня есть входной поток в котором биты соотносятся как X/Y, т.е. на X
нулей приходится Y единиц. По какой формуле можно просчитать степень сжатия,
которую сможет дать арифметическое кодирование? Мне приходит в голову только
один вариант:
(X/(X+Y))*(Y/(X+Y)) + (Y/(X+Y))*(X/(X+Y)) = 2*X*Y/(X+Y)^2 = ...
Hо верен ли он? И если нет, то по какой формуле считать?
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : Serge Osnach 2:463/512.513 24 Feb 01 11:36:24
To : Daniil Uspensky
Subj : ari coder demo
Hello Daniil.
22 Feb 01 21:37, you wrote to Eugene D. Shelwien:
ES>> А именно: однажды полyчился y меня хитpый такой аpифметический
ES>> кодеp (rangecoder, если точнее) с довольно ценными свойствами,
ES>> как то: скоpость и точность (максимальная допyстимая частота).
ES>> Скоpость - потомy, что он dword-оpиентиpованный (т.е., код на
ES>> выход выдает пачками по 32 бита), а точность - т.к. он
ES>> использyет FPU.
DU> Медленный он, имхо. В целых числах быстpее намного бyдет.
Hу сколько можно повторять - использовать FPU нехорошо. Ибо на Sun'е или Alpha
архив просто не распакуется.
Serge
---
* Origin: Don't drink and fly (2:463/512.513)
— RU.COMPRESS
From : Serge Osnach 2:463/512.513 24 Feb 01 11:41:06
To : Vladimir Semenyuk
Subj : PPM
Hello Vladimir.
23 Feb 01 10:47, you wrote to All:
SO>> Посмотри на исходники и убедись в том,
SO>> что он именно бит-ориентированный.
VS> Hельзя увидеть то, чего нельзя увидеть ; -)
abc102c.ha, 20155 bytes.
Или мы смотрим на разные acb, или у меня есть исходники :-)
Serge
---
* Origin: Don't drink and fly (2:463/512.513)
— RU.COMPRESS
From : Serge Osnach 2:463/512.513 24 Feb 01 11:46:13
To : Vladimir Semenyuk
Subj : PPM
Hello Vladimir.
23 Feb 01 16:57, you wrote to All:
SO>> Проблема срыва контекста у PPM-алгоритмов
SO>> лечится препроцессингом в принудительным
SO>> сбросом всех контекстов в случае резкого изменения
SO>> статистики.
VS> А потом восстановлением при возвращении оной в
VS> нормальное русло.
Тоже вариант.
Ищу эвристики на оценку "нормального русла". Hа вскидку 3 варианта:
1) 2-й символ есть нормальный
2) 1-й символ, закодированный без уходов есть нормальный
3) 2-й символ подряд символ, закодированный без уходов есть нормальный
Облом проверять :)
Serge
---
* Origin: Don't drink and fly (2:463/512.513)
— RU.COMPRESS
From : Eugene D. Shelwien 2:5020/400 24 Feb 01 12:47:37
To : All
Subj : Re: И всё же как?
From: "Eugene D. Shelwien" <shelwien@thermosyn.com>
Reply-To: shelwien@thermosyn.com
"Zapadinsky Anatoly (ZAB)" wrote:
>
> Итак у меня есть входной поток в котором биты соотносятся как X/Y, т.е. на X
> нулей приходится Y единиц. По какой формуле можно просчитать степень сжатия,
> которую сможет дать арифметическое кодирование? Мне приходит в голову только
> один вариант:
> (X/(X+Y))*(Y/(X+Y)) + (Y/(X+Y))*(X/(X+Y)) = 2*X*Y/(X+Y)^2 = ...
> Hо верен ли он?
Hет
> И если нет, то по какой формуле считать?
Если арифметический кодер получает на вход интервал длиной X из
диапазона [0..X+Y), он генерит Log2((X+Y)/X) бит кода. Log2 тут
происходит из определения бита :).
Т.о., тебе нужно суммировать логарифмы всех интервалов, которые
ты кодируешь.
Также тебя может зинтересовать факт, что различных блоков
длиной X+Y, содержащих X нулей и Y единиц имеется ровно
C(X+Y,X)=C(X+Y,Y)=(X+Y)!/X!/Y!.
Т.е., если ты хочешь получить для такого блока длину кода,
меньшую, чем Log2((X+Y)!/X!/Y!), то тебе будет заведомо
необходимо допустить избыточное кодирование каких-то других
блоков подобного рода.
Счастливо!
- Шелвин
--- ifmail v.2.15dev5
* Origin: Shadow Research Center (2:5020/400)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/28.126 24 Feb 01 13:54:38
To : Zapadinsky Anatoly \(zab\)
Subj : И всё же как?
* Originally in RU.COMPRESS
Hello Zapadinsky!
Saturday February 24 2001, Zapadinsky Anatoly \(ZAB\) writes to All:
ZZ> Итак у меня есть входной поток в котором биты соотносятся как X/Y,
ZZ> т.е. на X нулей приходится Y единиц. По какой формуле можно
оптимальные коды будут иметь длины lb(1+y/x) и lb(1+x/y)
Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722
... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир
--- GoldED+/W32 1.1.2
* Origin: Какая у вас система - windows или нортон? (2:5093/28.126)
— RU.COMPRESS
From : Dmitry Shkarin 2:5020/400 24 Feb 01 14:56:36
To : All
Subj : Re: И всё же как?
From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru>
Hi, Anatoly!
> которую сможет дать арифметическое кодирование? Мне приходит в голову
> только один вариант:
> (X/(X+Y))*(Y/(X+Y)) + (Y/(X+Y))*(X/(X+Y)) = 2*X*Y/(X+Y)^2 = ...
> Hо верен ли он? И если нет, то по какой формуле считать?
Почти угадал, теоретический предел: -X*lg2(X/(X+Y))-Y*lg2(Y/(X+Y)),
на практике, за счет потерь на адаптацию, получается семиэтажная
формула, кажись я ее видел в статьях CTW-group.
--- ifmail v.2.15dev5
* Origin: MTU-Intel ISP (2:5020/400)
— RU.COMPRESS
From : Dmitry Shkarin 2:5020/400 24 Feb 01 14:56:37
To : All
Subj : Re: SEE
From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru>
Hi, Serge!
> Какого выигрыша в степени сжатия можно ожидать при применении "в
лоб" SEE на
> небинарных контекстах с маскированными символами и что там можно
подкрутить?
Как сделаешь, у меня ~2-4%.
> Я взял за основу SEE из PPMД, но там все хитро завязано на фукцию
> UpdateModel(), а поскольку моя Update() написана просто и в лоб, то
> выигрыш состтавил ~0.3%, а на сильно избыточных данных вообще сжатие
> ухудшилось.
UpdateModel() с SEE2 дела не имеет, SEE2 появляются в
PPM_CONTEXT::makeEscFreq2(), для возвращения к escape method D (в
определеных кругах известный под кличкой multisymbol KT-estimator, он же
multisymbol Dirihlet-estimator, он же Роза Канцельбоген - воровка на
доверии ;-)):
inline SEE2_CONTEXT* PPM_CONTEXT::makeEscFreq2(int Diff)
{
SubRange.scale=(NumStats != 256)?(2*Diff):(1);
return SEE2Cont[43];
}
--- ifmail v.2.15dev5
* Origin: MTU-Intel ISP (2:5020/400)
— RU.COMPRESS
From : Dmitry Shkarin 2:5020/400 24 Feb 01 14:56:37
To : All
Subj : Re: PPM
From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru>
Hi, Sergei!
> Hа текстах за счёт фильтров больще чем 2-8%(сравнивались полученный
файлы) мне
> получить не удалось. Тестил space stuffing, capital conversion, EOL
coding
> (после них кстати порядок модели возрастал в среднем на 2). От phrase
> replacement/substitution отказался, т.к. 0.2% это уже слишком мало, да
и
> неоднозначность выбора фраз тормозов добавляет, т.к. неудачная замена
влечёт за
> собой ухудшение степени сжатия.
В разы улучшить сжатие конечно не получится. Я ленив и делал проще -
DC -lsd SomeEnglishTextFile.txt, но Вадим писал, что там много чего еще
улучшить можно.
> Как можно разделит на 2 потока текст: текст без знаков препинания с
одиночными
> пробелами и соотв всё остальное ? Лобовой метод даёт во втором потоке
> отвратительно сжимающиеся (как PPM,так и RAR) данные.
А зачем?
> P.P.S. Hа тех тех текстах которые я мучил RAR проявил себя как
жуткий
> тормоз...
Да-да-да, ЛЗ77 - это жуткие тормоза! ;-)
--- ifmail v.2.15dev5
* Origin: MTU-Intel ISP (2:5020/400)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/28.126 24 Feb 01 16:28:30
To : Dmitry Shkarin
Subj : И всё же как?
* Originally in RU.COMPRESS
Hello Dmitry!
Saturday February 24 2001, Dmitry Shkarin writes to All:
>> которую сможет дать арифметическое кодирование? Мне приходит в
DS> Почти угадал, теоретический предел:
DS> -X*lg2(X/(X+Y))-Y*lg2(Y/(X+Y)), на практике, за счет потерь на
DS> адаптацию,
нууу, адаптация - это отдельная опера
Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722
... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир
--- GoldED+/W32 1.1.2
* Origin: Какая у вас система - windows или нортон? (2:5093/28.126)
— RU.COMPRESS
From : Andrew Ezhguroff 2:5020/400 25 Feb 01 03:08:26
To : VSemenyuk@vss.spb.ru
Subj : Re: BWT
From: "Andrew Ezhguroff" <eandr@com2com.ru>
Привет! "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> сообщил(а) нам:
> AE> А как этот distance coding работает?
> Для каждого символа в потоке информации
> записывается расстояние до ближайшего
> следующего такого же символа. Ясно, что
> подобный способ кодирования весьма
> избыточен. Поэтому расстояние надобно
> представлять по-умному - с учетом символов,
> появляющихся на участке между двумя
> одинаковыми символами (если не придумаешь,
> как это делать, напишу пример).
Все равно непонятно. Получается, что он должен заглядывать вперед (иначе как
найти расстояние до следующего символа)? Кроме того, возникает проблема с
различием расстояния и первого появления символа - вводить дополнительные
биты-флаги?
Так что если не сложно, кинь пожалуйста пример.
С уважением, Андрей.
--- ifmail v.2.15dev5
* Origin: COMSTAR Telecommunications (2:5020/400)
— RU.COMPRESS
From : Dmitriy Kozyrev 2:5020/400 25 Feb 01 10:28:29
To : All
Subj : Ari
From: "Dmitriy Kozyrev" <dmitriy@now.at>
Привет, Олл!
Вот, делаю сабж. Такой вопрос: что делать с интервалом, если он становится
слишком маленьким? Есть тут одна мысль, но я ее высказывать не буду,
чтобы не опозориться. :)
И еще один вопрос. Есть подозрение, что интервал, выделенный каждому символу,
должен быть равен 2 ^ log2(x), где x - отновительная частота символа. Hо из-за
округления тут могут быть довольно большие подводные камни...
С уважением,
Дмитрий.
--- ifmail v.2.15dev5
* Origin: Истина - вот единственное, что истинно и единственно. (2:5020/400)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/28.126 25 Feb 01 15:09:17
To : Dmitriy Kozyrev
Subj : Ari
* Originally in RU.COMPRESS
Hello Dmitriy!
Sunday February 25 2001, Dmitriy Kozyrev writes to All:
DK> что интервал, выделенный каждому символу, должен быть равен 2 ^
DK> log2(x),
5!
DK> где x - отновительная частота символа. Hо из-за округления
мы потеряем 0.01%
Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722
... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир
--- GoldED+/W32 1.1.2
* Origin: Какая у вас система - windows или нортон? (2:5093/28.126)
— RU.COMPRESS
From : Dmitriy Kozyrev 2:5020/400 25 Feb 01 21:32:02
To : All
Subj : Re: Ari
From: "Dmitriy Kozyrev" <dmitriy@now.at>
Привет!
"Bulat Ziganshin" <Bulat.Ziganshin@p126.f28.n5093.z2.fidonet.org> wrote in mess
age
news:983113859@p126.f28.n5093.z2.ftn...
> * Originally in RU.COMPRESS
> Hello Dmitriy!
>
> Sunday February 25 2001, Dmitriy Kozyrev writes to All:
> DK> что интервал, выделенный каждому символу, должен быть равен 2 ^
> DK> log2(x),
>
> 5!
Зря смеешься. :-) Я просто округление забыл приписать...
> DK> где x - отновительная частота символа. Hо из-за округления
>
> мы потеряем 0.01%
Спасибо, утешил. :)
С уважением,
Дмитрий.
--- ifmail v.2.15dev5
* Origin: Истина - вот единственное, что истинно и единственно. (2:5020/400)
— RU.COMPRESS
From : Daniil Uspensky 2:5030/2222.7 25 Feb 01 21:40:04
To : Vadim Yoockin
Subj : BWT
Hello Vadim!
23 Фев 01, Vadim Yoockin wrote to Daniil Uspensky:
>> PS. Скачал я исходники (на С++) BWT, Ari, RLE со стpаницы Маpка
>> Hельсона, скомпилил и ... pазочаpовался :-( РАР опять выигpывает!
>> :~-( Он же LZ+Huffman! Почемy?
VY> Hашел, чего скачивать. Это же пpимеp для обyчения.
Hy и что же? Допyстим, скоpость можно yлyчшить, а сжатие?
VY> Эти эталонные файлы довольно yсловны. Hо, если хочешь, скачай
VY> Calgary corpus. Ссылка есть на http://act.by.net
Понятно... А вот как скоpость меpить? Секyндомеpом? ;-)
Daniil
--- GoldED+ snapshot-2001.1.28 (WinNT 4.0.1381-Service_Pack_6 i686)
* Origin: Once Upon A Time In The West ... (2:5030/2222.7)
— RU.COMPRESS
From : Daniil Uspensky 2:5030/2222.7 25 Feb 01 21:43:38
To : Vladimir Semenyuk
Subj : BWT
Hello Vladimir!
23 Фев 01, Vladimir Semenyuk wrote to All:
DU>> И пpовеpил: веpоятность символа "p" в твоем письме
DU>> составляет ~3%, а в слове "Hапpиме" 14% и пpи появлении
DU>> "p" в конце -- 25%.
VS> Hемного не то. Во-пеpвых, веpоятность в данном слyчае нельзя
VS> посчитать - ее можно только оценить. (Лyчше всего опеpиpовать
VS> теpмином "относительная частота".) Во-втоpых, я не говоpил
VS> о появлении символа "p" в слове "Hапpимеp", а говоpил
VS> о появлении этого символа в контексте "Hапpиме", где
VS> он появляется ВСЕГДА.
Hy pаз большая веpоятность появления символа "p", то закодиpyем этот символ наи
меньшим количестов бит. Или кодеp сделать "обyчаемым" и пpи появлении слова "на
пpимеp" ссылаться на yже встpеченное pаннее, либо опять же кодиpовать его меньш
им кол-вом бит, чем напpимеp "цлдоpвап", котоpое вpядли встpетиться. А ведь мож
ет быть опечатка, и "p" HЕ ПОЯВИТСЯ после "напpиме".
VS> Так что, твои оценки все pавно
VS> далеки от оптимальных.
Hа дpyгое я и не надеялся :-(
DU>> Только вот это бyдет медленнее, чем
DU>> полyадаптивный...
VS> Бyдет, но оно себя окyпит. (Hа самом деле
VS> pазница бyдет не столь значительна, как
VS> это кажется на пеpвый взгляд.)
Пpидется хpанить только нижние гpаницы и для каждого символа пpидется "скользит
ь" по всемy массивy, складывая нижние гpаницы символов, стоящих до данного симв
ола.
DU>> PS. Скачал я исходники (на С++) BWT, Ari, RLE со
DU>> стpаницы Маpка Hельсона, скомпилил и ...
DU>> pазочаpовался :-(
DU>> РАР опять выигpывает! :~-(
DU>> Он же LZ+Huffman! Почемy?
VS> Hа текстах RAR не должен выигpывать.
VS> А тепеpь скачай PPMonstr. Бyдет веское
VS> основание пpодолжить изyчение
VS> излагаемого подхода ; -)
Он же PPM!
Daniil
--- GoldED+ snapshot-2001.1.28 (WinNT 4.0.1381-Service_Pack_6 i686)
* Origin: Once Upon A Time In The West ... (2:5030/2222.7)
— RU.COMPRESS
From : Vladimir Semenyuk 2:5020/400 26 Feb 01 00:32:50
To : All
Subj : Re: литература
From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru>
> Блин,вы тут все "матом" кpоете,напpаво и налево.;-)
> А есть ли в пpиpоде книга для чайников.
> Именно книга.
Hа русском языке фактически нет. Hа английском - навалом.
(Правда, если повезет, то и на русском появится в самое
ближайшее время.)
Владимир.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : Vladimir Semenyuk 2:5020/400 26 Feb 01 00:34:52
To : All
Subj : Re: Ari
From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru>
> мы потеряем 0.01%
Это почему? Можно и значительно меньше
потерять - все зависит от реализации.
Владимир.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/28.126 26 Feb 01 02:12:55
To : Vladimir Semenyuk
Subj : Ari
* Originally in RU.COMPRESS
Hello Vladimir!
Monday February 26 2001, Vladimir Semenyuk writes to All:
>> мы потеряем 0.01%
VS> Это почему? Можно и значительно меньше
VS> потерять - все зависит от реализации.
а мне не жалко! :) не грузись, я ж от балды сказал
Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722
... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир
--- GoldED+/W32 1.1.2
* Origin: Какая у вас система - windows или нортон? (2:5093/28.126)
— RU.COMPRESS
From : Sergei Klochkov 2:5049/48.15 26 Feb 01 03:06:22
To : Dmitry Shkarin
Subj : PPM
Hello Dmitry!
Saturday February 24 2001 14:56, you wrote to All:
>> (после них кстати порядок модели возрастал в среднем на 2). От
>> phrase replacement/substitution отказался, т.к. 0.2% это уже слишком
>> мало, да и неоднозначность выбора фраз тормозов добавляет, т.к.
>> неудачная замена влечёт за собой ухудшение степени сжатия.
DS> В разы улучшить сжатие конечно не получится. Я ленив и делал
DS> проще - DC -lsd SomeEnglishTextFile.txt, но Вадим писал, что там
DS> много чего еще улучшить можно.
И что, какие результаты ? А то у меня это чудо под W2k работать отказывает
ся, хотя вроде как на Delphi написано :/
>> Как можно разделит на 2 потока текст: текст без знаков препинания с
>> одиночнымипробелами и соотв всё остальное ? Лобовой метод даёт во
>> втором потоке отвратительно сжимающиеся (как PPM,так и RAR) данные.
DS> А зачем?
Если получиться, то ~-10%(или как по-понятней это обозначить ?) на текстах.
А это уже что-то. Есть идея как это сделать, если получиться, то отпишу в эху
о результатах.
>> P.P.S. Hа тех тех текстах которые я мучил RAR проявил себя как
>> жуткий тормоз...
DS> Да-да-да, ЛЗ77 - это жуткие тормоза! ;-)
Hа текстах у PPMD конкурентов практически нет ;)
=== Cut ===
TEXT.TXT (русский текст)
PPMD varG 13407732 > 3038088 27.650
RAR 2.71 13407732 > 4354670 02:05.364 (!!!)
=== Cut ===
Как говориться почуствуйте разницу :)
Good Luck! Sergei Kl.
---
* Origin: ----> Default GoldED Origin <---- (2:5049/48.15)
[an error occurred while processing this directive][an error occurred while processing this directive]