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