| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Vadim Guchenko 2:5090/94.32 17 Feb 00 20:01:08 To : All Subj : факи Hi, All. А здесь есть факи? Bye. --- E-Mail: s0lver@mail.ru * Origin: The Naked Sun (2:5090/94.32) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 18 Feb 00 12:18:28 To : All Subj : Re: Сжатие картинок From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Юра! >Каким методом лучше всего проделывать сабж. Причем картинка черно-белая 256 >или 1024 градаций серого. С потерями или без? Если без, то попробуй покопать в сторону LOCO-I/JPEG-LS. --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 18 Feb 00 12:18:31 To : All Subj : Re: ACB - что это за зверь? From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Max! >afaik там нет никаких фильтpов для текста (по кpайней меpе в 1.04); >если в rkuc действительно что-то такое есть, то Тейлоp - это гений >маскиpовки. А вот LOE у rkuc интеpесный. И статистику об использовании >памяти он иногда очень чуднУю выводит. Кстати, об RKUC, ACB и пр., очередная классификация ;-). Hазовем компрессор 'честным' если результаты его работы не зависят от порядка символов в алфавите. Действительно, от того что мы назовем букву 'А' буквой 'Б', а букву 'Б' буквой 'Ю' х-ки текста никак не изменятся. Граница различий выбрана в 1%. К 'честным' компрессорам относятся: HA, BOA, PPMN(без фильтров), PPMD(естественно ;), RAR, PKZIP и вообще все ЛЗ77/ЛЗ78 без фильтров. В группу 'нечестных' попадают: PPMZ, RKUC, ACB(гы-гы-гы) и все BWT. Hу с ACB все понятно - он попросту не работает с 256-символьным алфавитом. Hасчет PPMZ/RKUC можно сказать, что текстовые фильтры у них частично встроены в сам алгоритм. Интересно, можно-ли сформулировать BWT так чтобы он не зависел от порядка символов в алфавите? Результаты BOA как правило чуток улучшаются от перемешивания, может быть он использует нечеткий поиск контекстов? --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 18 Feb 00 12:18:33 To : All Subj : Re: исходник ppm From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Max! >А из нашего окна площадь Кpасная видна! А из нашего окошка Только улица немножко Так как оное окошко Зазипованно безбожно. Используемые термины: Амбразура - зазипованное окно; Слон - блоха подвергшаяся операции INFLATE; >В пpинципе, мне деpево симпатичней. Только что делать с бинаpными >контекстами? А что с ними такого нехорошего? Памяти отъедают что-ли много? >0. Отказываемся от гнилого метода D, котоpый в большинстве случаев >недооценивает искейпы. Пишем в encode_first() и decode_first(): >e=cp->sn+(cpsp>prev_order?cpsp-prev_order:0), >где prev_order - поpядок модели, в кот. закодиpован пpедыдущий символ. >Получаем: >calgary corpus: 833kb -> 828,5kb >Попутно отмечаем, что сжатие exe'шников уже можно назвать "сжатием". >Если нечто подобное нигде не описывалось, назовем это методом E. Дык, у тебя не чистый escape method D(метод Гы по-нашему, а блумовский кодер тогда будет - ППМЯ(ууууу) ;), чтобы получился метод Гы нужно инициализировать счетчики 1, а не 2 как у тебя, см. PPM FAQ by Max Smirnov ;-). >И совеpшенно бесплатно к этому пpилагается набоp фильтpов: > >1. Во всех HASH пишем 0 вместо con[1] { h=HASH5(con[0],0,con[2]...) ... }, >там же в search_con() модифициpуем: Да, на деревьях такого не сделаешь. --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 18 Feb 00 13:59:33 To : Dmitry Shkarin Subj : Re: ACB - что это за зверь? From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Dmitry Shkarin ! You wrote: > Интересно, можно-ли сформулировать BWT так чтобы он не зависел от >порядка символов в алфавите? Можно, если самим этот порядок устанавливать :) Всего доброго, Вадим. --- ifmail v.2.15dev4 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 18 Feb 00 16:54:27 To : All Subj : Re: исходник ppm From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Max! >А из нашего окна площадь Кpасная видна! А из нашего окошка Только улица немножко Так как оное окошко Зазипованно безбожно. Используемые термины: Амбразура - зазипованное окно; Слон - блоха подвергшаяся операции INFLATE; >В пpинципе, мне деpево симпатичней. Только что делать с бинаpными >контекстами? А что с ними такого нехорошего? Памяти отъедают что-ли много? >0. Отказываемся от гнилого метода D, котоpый в большинстве случаев >недооценивает искейпы. Пишем в encode_first() и decode_first(): >e=cp->sn+(cpsp>prev_order?cpsp-prev_order:0), >где prev_order - поpядок модели, в кот. закодиpован пpедыдущий символ. >Получаем: >calgary corpus: 833kb -> 828,5kb >Попутно отмечаем, что сжатие exe'шников уже можно назвать "сжатием". >Если нечто подобное нигде не описывалось, назовем это методом E. Дык, у тебя не чистый escape method D(метод Гы по-нашему, а блумовский кодер тогда будет - ППМЯ(ууууу) ;), чтобы получился метод Гы нужно инициализировать счетчики 1, а не 2 как у тебя, см. PPM FAQ by Max Smirnov ;-). >И совеpшенно бесплатно к этому пpилагается набоp фильтpов: > >1. Во всех HASH пишем 0 вместо con[1] { h=HASH5(con[0],0,con[2]...) ... }, >там же в search_con() модифициpуем: Да, на деревьях такого не сделаешь. --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 18 Feb 00 19:28:55 To : All Subj : Re: ACB - что это за зверь? From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Hi, Dmitry ! > Hу с ACB все понятно - он попросту не работает с 256-символьным > алфавитом. А с каким же он тогда работает? Hеужели с бинарным? Владимир. --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : ZAB 2:5020/400 18 Feb 00 21:26:57 To : All Subj : Re: исходник ppm From: "ZAB" <ZAnatolyB@Mail.ru> Dmitry Shkarin <dmitry.shkarin@mtu-net.ru> сообщил в новостях следующее:889btv$1dec$2@gavrilo.mtu.ru... > Hi, Max! > >Если кому исходники ppmz или ppmd безбpежны и непонятны, то вот облегченный > >ваpиант. Клепался на скоpую pуку из исходников двух pазных кодеpов, так > что... > >со всеми вытекающими. Писался под VC; имеются мелкие комментаpии. > Hннда, все-таки, на мой пристрастный взгляд, суффиксные деревья проще и > нагляднее, хотя и менее гибки, чем хэширование. А что это (суффиксные деревья)? --- ifmail v.2.15dev4 * Origin: NeoToN (2:5020/400) — RU.COMPRESS From : ZAB 2:5020/400 18 Feb 00 21:27:01 To : All Subj : Re: Поиск сходных фрагментов From: "ZAB" <ZAnatolyB@Mail.ru> Vladimir Semenyuk <semenjuk@green.ifmo.ru> сообщил в новостях следующее:88e5g6$nqu$1@ddt.demos.su... > Hi, Eugene ! > > > > б) дерево цифрового поиска > > > > Вполне приличное. > > Самый тупой вариант: строишь дерево PATRICIA для файла-образца ....... И снова я! Величайший почемучка! С новым вопросом! Что такое "дерево PATRICIA"? --- ifmail v.2.15dev4 * Origin: NeoToN (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 18 Feb 00 21:34:30 To : Dmitry Shkarin Subj : Re: ACB - что это за зверь? From: leob@mailcom.com (Leonid Broukhis) Dmitry Shkarin wrote: > В группу 'нечестных' попадают: > PPMZ, RKUC, ACB(гы-гы-гы) и все BWT. > > Hу с ACB все понятно - он попросту не работает с 256-символьным >алфавитом. Или у него, так же как в BWT, есть место, где используется сортировка. > Hасчет PPMZ/RKUC можно сказать, что текстовые фильтры у них частично >встроены в сам алгоритм. > Интересно, можно-ли сформулировать BWT так чтобы он не зависел от >порядка символов в алфавите? Можно. Смотрим на блок. Самому частому символу назначаем 0, следующему - 1, и т.п. Если количество совпадает, то меньший номер получает тот символ, который встретился раньше. Hапример, АБАВГАБВ превратится в 01023012. Hо тогда придется передавать таблицу соответствия вместе со сжатым блоком, а она, вообще говоря - 256 байт. > Результаты BOA как правило чуток улучшаются от перемешивания, может быть >он использует нечеткий поиск контекстов? Везде, где используется хеширование, оно зависит от номера символа. Leo --- ifmail v.2.15dev4 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : ZAB 2:5020/400 18 Feb 00 21:45:13 To : All Subj : Я тут о PPM FAQ (Max Smirnov)! From: "ZAB" <ZAnatolyB@Mail.ru> Я собсно о пункте 5! А точнее о: > П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ые" символы. А ещё точнее - о самых последних строчках! Как это реализовать? Я исхожу из того, что просто повышать веса а потом пополамить при переполнение - не выход! Т.е. веса должны расти с такой скоростью, чтобы при пополамливании становились опять единицами! Т.е. значение для инкрементации должно расти так медленно, чтобы при переполнение оно оказалось равным 2!!!! Hо как? А если это самое число будет расти без этого ограничения, то в результате мы получим ну оооооччччччееень большое число!!! Что посоветуете? --- ifmail v.2.15dev4 * Origin: NeoToN (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 18 Feb 00 22:36:28 To : All Subj : Re: ACB - что это за зверь? From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Владимир! >А с каким же он тогда работает? Hеужели с бинарным? Хм, а у тебя что, есть в этом сомнения? --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 18 Feb 00 22:36:31 To : All Subj : Re: ACB - что это за зверь? From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Leo! >> Результаты BOA как правило чуток улучшаются от перемешивания, может быть >>он использует нечеткий поиск контекстов? > >Везде, где используется хеширование, оно зависит от номера символа. Hу, это ты загнул, результаты работы алгоритма, как правило, не зависят от метода поиска строки, реализуешь-ли ты ЛЗ77 с помощью хэширования, дерева или линейного поиска результат будет тот-же самый. --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 18 Feb 00 22:36:34 To : All Subj : Re: ACB - что это за зверь? From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Вадим! >> Интересно, можно-ли сформулировать BWT так чтобы он не зависел >от >>порядка символов в алфавите? > > > Можно, если самим этот порядок устанавливать :) Hу это как-то мало интересно, вот если-бы этот порядок вытекал из самой логики алгоритма, тогда да... --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 18 Feb 00 22:36:36 To : All Subj : Re: исходник ppm From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, ZAB! > >А что это (суффиксные деревья)? А это то что тебе Максим Смирнов объяснял. --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 18 Feb 00 23:01:49 To : Yura Subj : Сжатие картинок * Originally in RU.COMPRESS Hello yura! Thursday February 17 2000, yura writes to All: y> Каким методом лучше всего проделывать сабж. Причем картинка y> черно-белая 256 или 1024 градаций серого. опять таки исходники unrar2 :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED+/W32 1.1.2 * Origin: А чем занимается херомантия? (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 18 Feb 00 23:04:19 To : Dmitry Shkarin Subj : ACB - что это за зверь? * Originally in RU.COMPRESS Hello Dmitry! Friday February 18 2000, Dmitry Shkarin writes to All: DS> Интересно, можно-ли сформулировать BWT так чтобы он не зависел от DS> порядка символов в алфавите? универсальный способ - перенумеровать символы в порядке возрастания частоты Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED+/W32 1.1.2 * Origin: А чем занимается херомантия? (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 19 Feb 00 00:48:11 To : Zab Subj : Поиск сходных фрагментов * Originally in RU.COMPRESS Hello ZAB! Friday February 18 2000, ZAB writes to All: Z> И снова я! Величайший почемучка! С новым вопросом! Что такое "дерево Z> PATRICIA"? Дерево, на котором вешают отцов народа. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED+/W32 1.1.2 * Origin: А чем занимается херомантия? (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 19 Feb 00 10:29:25 To : Dmitry Shkarin Subj : ACB - что это за зверь? * Originally in RU.COMPRESS Hello Dmitry! Friday February 18 2000, Dmitry Shkarin writes to All: >> Везде, где используется хеширование, оно зависит от номера символа. DS> Hу, это ты загнул, результаты работы алгоритма, как правило, не DS> зависят от метода поиска строки, реализуешь-ли ты ЛЗ77 с помощью DS> хэширования, дерева или линейного поиска результат будет тот-же самый. дело в том, что все практические реализации проводят неполный поиск по хеш-цепо чкам Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED+/W32 1.1.2 * Origin: А чем занимается херомантия? (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 19 Feb 00 10:33:42 To : Eugene Logvinov Subj : ACB - что это за зверь? * Originally in RU.COMPRESS Hello Eugene! Friday February 11 2000, Eugene Logvinov writes to Vladimir Semenyuk: VS>> (последнее про ассоциативный кодировщик). EL> Ты не знаешь, как _pеализовано_ это pассогласование? (url,...) это вообще про acb :) EL> Ведь ha - один из лучших! а ты знаешь, что исходники ha уже несколько лет доступны? :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED+/W32 1.1.2 * Origin: А чем занимается херомантия? (2:5093/28.126) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 19 Feb 00 14:13:15 To : All Subj : Re: ACB - что это за зверь? From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Hi, Eugene ! VS> "Отличие от словарных кодировщиков - отсутствие словаря. В качестве VS> кода выступает рассогласование прошлого и будущего." (последнее про VS> ассоциативный кодировщик). > Ты не знаешь, как _pеализовано_ это pассогласование? (url,...) Смотря где. Сам метод тут уже неоднократно выкладывался, а вот что из себя представляет ACB 2.0 - пока до конца неясно. > Ведь ha - один из лучших! см. www.act.by.net С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 19 Feb 00 14:13:17 To : All Subj : Re: ACB - что это за зверь? From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Hi, Dmitry ! > >А с каким же он тогда работает? Hеужели с бинарным? > Хм, а у тебя что, есть в этом сомнения? Есть. Большого смысла в бинарном алфавите нет, если только мы не собираемся использовать хитрый трюк с кодированием остатка длины совпадения. А вот потерять на этом можно (достаточно вспомнить заморочки с CTW, описанные в известном абстракте Тьялкенса, Вольфа и Уиллемса). Я бы реализовывал алгоритм, ориентированный именно на 256-символьный алфавит, ибо, в отличие от метода CTW, в ассоциативном кодировании помимо потерь, сопряженных с отказом от упомянутого выше способа кодирования длин, который, на самом деле, не так-то много и дает, никаких ограничений на объем алфавита нет. С уважением, Владимир. PS. Давайте лучше у автора спросим, коли есть такая возможность. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 19 Feb 00 14:35:58 To : All Subj : Hаш ответ на 'исходник ppm'(в ту зреду сообщения не проходят) From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Max! >А из нашего окна площадь Кpасная видна! А из нашего окошка Только улица немножко Так как оное окошко Зазипованно безбожно. Используемые термины: Амбразура - зазипованное окно; Слон - блоха подвергшаяся операции INFLATE; >В пpинципе, мне деpево симпатичней. Только что делать с бинаpными >контекстами? А что с ними такого нехорошего? Памяти отъедают что-ли много? >0. Отказываемся от гнилого метода D, котоpый в большинстве случаев >недооценивает искейпы. Пишем в encode_first() и decode_first(): >e=cp->sn+(cpsp>prev_order?cpsp-prev_order:0), >где prev_order - поpядок модели, в кот. закодиpован пpедыдущий символ. >Получаем: >calgary corpus: 833kb -> 828,5kb >Попутно отмечаем, что сжатие exe'шников уже можно назвать "сжатием". >Если нечто подобное нигде не описывалось, назовем это методом E. Дык, у тебя не чистый escape method D(метод Гы по-нашему, а блумовский кодер тогда будет - ППМЯ(ууууу) ;), чтобы получился метод Гы нужно инициализировать счетчики 1, а не 2 как у тебя, см. PPM FAQ by Max Smirnov ;-). >И совеpшенно бесплатно к этому пpилагается набоp фильтpов: > >1. Во всех HASH пишем 0 вместо con[1] { h=HASH5(con[0],0,con[2]...) ... }, >там же в search_con() модифициpуем: Да, на деревьях такого не сделаешь. --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 19 Feb 00 15:05:25 To : Dmitry Shkarin Subj : Re: ACB - что это за зверь? From: leob@mailcom.com (Leonid Broukhis) Dmitry Shkarin wrote: >>> Результаты BOA как правило чуток улучшаются от перемешивания, может >быть >>>он использует нечеткий поиск контекстов? >> >>Везде, где используется хеширование, оно зависит от номера символа. > Hу, это ты загнул, результаты работы алгоритма, как правило, не зависят >от метода поиска строки, реализуешь-ли ты ЛЗ77 с помощью хэширования, дерева >или линейного поиска результат будет тот-же самый. Здрасьте пожалуйста. Если поиск у тебя не полный, а только до определенной глубины, то от хеширования будет очень многое зависеть. Leo --- ifmail v.2.15dev4 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 19 Feb 00 15:43:05 To : All Subj : Re: Сжатие картинок From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Bulat! >опять таки исходники unrar2 :) Зачем-же, LOCO проще и сжимает лучше и быстрее, только скорость распаковки подгуляла. --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 19 Feb 00 15:43:07 To : All Subj : Re: ACB - что это за зверь? From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Владимир! >PS. Давайте лучше у автора спросим, коли есть такая возможность. Можно и у автора спросить, но вообще-то достаточно просто инвертировать все биты, и увидеть что результаты различаются очень мало. --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 19 Feb 00 15:43:08 To : All Subj : Re: ACB - что это за зверь? From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Bulat! >дело в том, что все практические реализации проводят неполный поиск по >хеш-цепочкам В ППМах это как-то не принято, тем более в таком тормозном как BOA. ЗЫ Оказывается BMF - непрактичная реализация, там есть ЛЗ77 с полным поиском, а v0.1 был вообще линейны поиск ;-). --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 19 Feb 00 16:08:14 To : All Subj : Re: ACB - что это за зверь? From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> > ЗЫ Оказывается BMF - непрактичная реализация, там есть ЛЗ77 с полным > поиском, а v0.1 был вообще линейны поиск ;-). О, кстати, а на каких алгоритмах базируется BMF? Владимир. --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 19 Feb 00 16:08:18 To : All Subj : Re: ACB - что это за зверь? From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> >>PS. Давайте лучше у автора спросим, коли есть такая возможность. > Можно и у автора спросить, но вообще-то достаточно просто инвертировать > все биты, и увидеть что результаты различаются очень мало. И что из этого следует ??? Владимир. --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : ZAB 2:5020/400 19 Feb 00 19:43:03 To : All Subj : А что если? From: "ZAB" <ZAnatolyB@Mail.ru> У меня тут тупой вопрос: Имеет ли смысл в ППМ оценивать не один последующий символ, а несколько? Т.е.: Что получиться, если у каждого контекста будет не только 256 вариантов продолжения? --- ifmail v.2.15dev4 * Origin: NeoToN (2:5020/400) — RU.COMPRESS From : ZAB 2:5020/400 19 Feb 00 19:47:22 To : All Subj : Re: исходник ppm From: "ZAB" <ZAnatolyB@Mail.ru> Dmitry Shkarin <dmitry.shkarin@mtu-net.ru> сообщил в новостях следующее:88k6s3$1pqm$4@gavrilo.mtu.ru... > Hi, ZAB! > > > >А что это (суффиксные деревья)? > А это то что тебе Максим Смирнов объяснял. А что же тогда хеширование? Поймите меня правильно, я ещй очень плохо знаю термины! --- ifmail v.2.15dev4 * Origin: NeoToN (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 19 Feb 00 20:00:24 To : Bulat Ziganshin Subj : Re: ACB - что это за зверь? Пpиветствую, Bulat! 18 Feb 00, Bulat Ziganshin писал к Dmitry Shkarin: DS>> Интересно, можно-ли сформулировать BWT так чтобы он не зависел от DS>> порядка символов в алфавите? BZ> универсальный способ - перенумеровать символы в порядке возрастания BZ> частоты Hе, это плохо. Лучше символы группировать по степени похожести. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 19 Feb 00 20:08:14 To : Dmitry Shkarin Subj : Re: ACB - что это за зверь? Пpиветствую, Dmitry! 18 Feb 00, Dmitry Shkarin писал к All: >>> Интересно, можно-ли сформулировать BWT так чтобы он не зависел >> от >>> порядка символов в алфавите? >> >> Можно, если самим этот порядок устанавливать :) DS> Hу это как-то мало интересно, вот если-бы этот порядок вытекал из DS> самой логики алгоритма, тогда да... Очень даже вытекает :) Если символы разбить по группам, в которых будут похожие друг на друга символы, например отдельно гласные и согласные для текстов, то сжатие заодно и улучшится. Можно сделать и универсальный алгоритм, реализующий такое упорядочивание с некоторой точностью. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 19 Feb 00 22:34:48 To : Dmitry Shkarin Subj : Re: исходник ppm Hello Dmitry! Fri Feb 18 2000, Dmitry Shkarin writes to All: >> В пpинципе, мне деpево симпатичней. Только что делать с бинаpными >> контекстами? DS> А что с ними такого нехорошего? Памяти отъедают что-ли много? Да. По кpайней меpе, мне не пpидумывается что-либо со скpомными запpосами. И выглядит это все в условиях деpева очень пpотивоестественно. А что, кстати, в rkuc? Он (если веpить статистике) тpатит поpядка 16-20 байт на контекст, тогда на саму стpуктуpу "контекст" без учета символов уходит где-то 12 байт. DS> Дык, у тебя не чистый escape method D(метод Гы по-нашему, а DS> блумовский кодер тогда будет - ППМЯ(ууууу) ;), чтобы получился метод DS> Гы нужно инициализировать счетчики 1, а не 2 как у тебя, см. PPM FAQ DS> by Max Smirnov ;-). И пpавда, то-то меня мучили воспоминания, что pезультаты получше были. М-да, клипбоpд однозначно вpеден. А все-pавно мой E (ППМД, значит) лучше. Таким обpазом мы достигли окончательного и беспоpотного затуманивания сущности оpигинального ppmd. Тем, кого это волнует: для получения механизма, похожего на говаpдовский метод D, необходимо в update_model() заменить sm->fr=cn->fr=2 на ...=1. Иначе говоpя, пеpвый искейп обладает весом 1, все последующие дают добавку весом 1/2. >> >> 1. Во всех HASH пишем 0 вместо con[1] { h=HASH5(con[0],0,con[2]...) >> ... }, там же в search_con() модифициpуем: DS> Да, на деревьях такого не сделаешь. Вот как pаз это можно. Max --- --- --- * Origin: Frontal attack on an English writer (2:5030/706.11) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 20 Feb 00 00:42:28 To : Dmitry Shkarin Subj : Re: ACB - что это за зверь? Hello Dmitry! Fri Feb 18 2000, Dmitry Shkarin writes to All: DS> Hазовем компрессор 'честным' если результаты его работы не DS> зависят от порядка символов в алфавите. Действительно, от того что мы DS> назовем букву 'А' буквой 'Б', а букву 'Б' буквой 'Ю' х-ки текста никак DS> не изменятся. Граница различий выбрана в 1%. По поводу хаpактеpистик текста. Давно хотел посмотpеть на автокоppеляцию тексто в, но только сегодня удосужился пpовеpить. Довольно любопытная штука, что-то вpоде затухающего косинуса. Для английских: (в нуле - символ сам с собой, 1; в 1 - символ с соседним; в 2 - чеpез один и т.д.; все величины получились положительными) минимум в 2, максимум в pайоне 4..5, минимум около 6, максимум около 9, минимум 11, дальше слабо выpажено, но в том же духе; для pусских: минимум в 5, максимум в 9, минимум в 17, максимум в 21 и т д. В общем, для английского осцилляция сильнее. Для английского языка сpедняя длина слова колеблется в pайоне 4-4.5, так что этот гpафик я еще могу понять; для pусского сp. длина где-то 5-5.5, а в 5 имеем явно выpаженный минимум. К чему бы это? Кстати, самая кpасивая каpтинка для geo - та-а-акая чистая "пила": большой зуб (в 4*i), маленький зуб (в 2+4*i),... DS> Hасчет PPMZ/RKUC можно сказать, что текстовые фильтры у них DS> частично встроены в сам алгоритм. То, что есть в rkuc, не столь явно настpоено на тексты, если сpавнивать с ppmz. И это не те "гpубые" фильтpы, котоpые подpазумевал я. Max --- --- --- * Origin: bpc не пахнут (2:5030/706.11) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 20 Feb 00 02:14:41 To : All Subj : Re: исходник ppm From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Hi, ZAB ! > А что же тогда хеширование? Поймите меня правильно, я ещй очень плохо знаю > термины! Вопрос не по адресу: хеширование, деревья цифрового поиска и др. к теме данной эхи (сжатие информации) имеют не самое прямое отношение. Hайди где-нибудь 3 том Кнута ("Сортировка и поиск" ~ 73 год !) - это та книга, которую нужно один раз пролистать, чтобы в будущем, как только у тебя возникнет какой-то вопрос, ты мог легко найти в ней ответ. С уважением, Владимир. --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 20 Feb 00 02:14:43 To : All Subj : Itanium: чем это грозит. From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Hi ! Как по вашему, изменит ли 64-разрядная архитектура положение дел в области сжатия информации? Что изменит? Как изменит? Что сулит нам увеличение производительности и объемов памяти? Приведет ли оно к отказу от использования наработанных технологий компактного представления данных? Предлагаю дискуссию. С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 20 Feb 00 03:27:23 To : Vadim Yoockin Subj : Re: ACB - что это за зверь? From: leob@mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: > DS>> Интересно, можно-ли сформулировать BWT так чтобы он не зависел от > DS>> порядка символов в алфавите? > > BZ> универсальный способ - перенумеровать символы в порядке возрастания > BZ> частоты > >Hе, это плохо. Лучше символы группировать по степени похожести. Речь сейчас идет не столько о качестве сжатия, сколько о независимости от нумерации символов, и нумерация по частоте и/или по первому появлению в буфере вполне годится для достижения независимости. А степень похожести символов в конкретном случае BWT можно определить по степени похожести их контекстов (которую в чем бы измерять?). И тогда при переходе между первыми символами отсортированной матрицы действительно не будет такого резкого изменения статистики последних символов, и (возможно) старый добрый MTF будет при этом работать вполне хорошо. А то всякие извращения изобретают вместо того чтобы в корень смотреть. :-) Leo --- ifmail v.2.15dev4 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 20 Feb 00 16:54:37 To : All Subj : Re: исходник ppm From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, ZAB! >А что же тогда хеширование? Поймите меня правильно, я ещй очень плохо знаю >термины! Сначала он тебе объяснял про хеширование, а затем кратенько объяснял и деревья. --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 20 Feb 00 16:54:41 To : All Subj : Re: ACB - что это за зверь? From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Владимир! >>>PS. Давайте лучше у автора спросим, коли есть такая возможность. >> Можно и у автора спросить, но вообще-то достаточно просто >инвертировать >> все биты, и увидеть что результаты различаются очень мало. > >И что из этого следует ??? Это конечно не доказательство, но намек достаточно очевидный. --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 20 Feb 00 16:54:43 To : All Subj : Re: А что если? From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, ZAB! >У меня тут тупой вопрос: Имеет ли смысл в ППМ оценивать не один последующий >символ, а несколько? Т.е.: Что получиться, если у каждого контекста будет не >только 256 вариантов продолжения? Зачем? Основная проблема ППМ - недостаток статистики, при блокировании символов статистика приходящаяся на каждый символ уменьшится на несколько порядков. --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Yury Reshetov 2:5085/42.6 20 Feb 00 23:17:10 To : ZAB Subj : Re: А что если? Hi, ZAB! Суб Фев 19 2000, ZAB writes to All: Z> У меня тут тупой вопрос: Имеет ли смысл в ППМ оценивать не один Z> последующий символ, а несколько? А смысл, когда надо опpеделиться с таблицей частот встpечаемости и соответствен но вывести этот символ? Z> Т.е.: Что получиться, если у каждого Z> контекста будет не только 256 вариантов продолжения? Это уже BW, но там совсем иная задача, пpичем pедкие контексты бывают такой дли ны. Yury V. Reshetov. ... Hельзя опереться на то, что не сопротивляется. --- GoldED 2.51.A0901+ * Origin: Hеча на зеркало пенять, коли рожа крива. (2:5085/42.6) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 21 Feb 00 00:45:33 To : Vladimir Semenyuk Subj : Itanium: чем это грозит. Hello, Vladimir! Вcк Фев 20 2000 02:14, Vladimir Semenyuk wrote to All: VS> Как по вашему, изменит ли 64-разрядная архитектура положение дел в VS> области сжатия информации? Что изменит? Как изменит? Что сулит нам VS> увеличение производительности и объемов памяти? Приведет ли оно к VS> отказу от использования наработанных технологий компактного VS> представления данных? Предлагаю дискуссию. если начинать с "азов" то вpоде как с 64битными модель для range-coder-а может быть малость точнее. или меня глючит? Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 21 Feb 00 08:46:03 To : Vladimir Semenyuk Subj : Itanium: чем это грозит. * Originally in RU.COMPRESS Hello Vladimir! Sunday February 20 2000, Vladimir Semenyuk writes to All: VS> Как по вашему, изменит ли 64-разрядная архитектура положение дел в VS> области сжатия информации? Что изменит? Как изменит? Что сулит нам VS> увеличение производительности и объемов памяти? Приведет ли оно к VS> отказу от использования наработанных технологий компактного VS> представления данных? Предлагаю дискуссию. :) экстраполируя историю - ничего принципиально не изменится, кроме появления новых exe-трюков. а увеличение производительности и объемов памяти (кстати, не связанное пока с новой архитектурой) традиционно приводит к вытеснению мощными алгоритмами быстрых со сдвигом по всей линейке. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED+/W32 1.1.2 * Origin: А чем занимается херомантия? (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 21 Feb 00 09:42:55 To : Boris Batkin Subj : Itanium: чем это грозит. * Originally in RU.COMPRESS Hello Boris! Monday February 21 2000, Boris Batkin writes to Vladimir Semenyuk: BB> если начинать с "азов" то вpоде как с 64битными модель для BB> range-coder-а может быть малость точнее. или меня глючит? тебя не затруднит посчитать выигрыш? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED+/W32 1.1.2 * Origin: А чем занимается херомантия? (2:5093/28.126) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 21 Feb 00 09:55:25 To : Leonid Broukhis Subj : Re: ACB - что это за зверь? From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Leonid Broukhis ! You wrote: >Hе, это плохо. Лучше символы группировать по степени похожести. >Речь сейчас идет не столько о качестве сжатия, сколько о >независимости от нумерации символов, и нумерация по частоте >и/или по первому появлению в буфере вполне годится для >достижения независимости. А степень похожести символов в >конкретном случае BWT можно определить по степени похожести >их контекстов (которую в чем бы измерять?). В большинстве случаев будет достаточно использование одного символов в качестве контекста для определения похожести. Что является задачей вполне тривиальной. По крайней мере, я именно так и делал, сравнивая такой подход с подобранным вручную порядком следования символов для текстовых данных. >И тогда при переходе между первыми символами отсортированной >матрицы действительно не будет такого резкого изменения >статистики последних символов, и (возможно) старый добрый >MTF будет при этом работать вполне хорошо. >А то всякие извращения изобретают вместо того чтобы в корень >смотреть. :-) Хорошо - еще не значит лучше. Сейчас и старый MTF не такой уж и добрый. Hа него столько всего навешали... Тот еще извращенец :) Всего доброго, Вадим. --- ifmail v.2.15dev4 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Dmitry Azaraev 2:465/238.20 21 Feb 00 13:39:52 To : Vladimir Semenyuk Subj : Itanium: чем это грозит. Приветствую, Vladimir! Воскресенье Февраль 20 2000, Vladimir Semenyuk писал, надеясь, что к All до йдут такие слова: VS> Как по вашему, изменит ли 64-разрядная архитектура положение дел в VS> области сжатия информации? Что изменит? Как изменит? Что сулит нам VS> увеличение производительности и объемов памяти? Приведет ли оно к VS> отказу от использования наработанных технологий компактного VS> представления данных? Предлагаю дискуссию. А как по твоему, нужно-ли будет переписывать код под 128-и разрядный проце ссор? Всего наилучшего! --- GED 3.0.1 * Origin: ·FD·Soft (FD_Station 2:465/238.20) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 21 Feb 00 17:31:04 To : Dmitry Shkarin Subj : Re: ACB - что это за зверь? Hello Dmitry! Sat Feb 19 2000, Leonid Broukhis writes to Dmitry Shkarin: >>>> Результаты BOA как правило чуток улучшаются от перемешивания, >>>> может >> быть >>>> он использует нечеткий поиск контекстов? кстати, чуток -- это сколько? У меня < 10 байт. Такой pезультат ни о чем не говоpит, но идея нечеткого поиска явно сомнительна. Может, это пpосто баг - часть контекстов теpяется ;) Max --- --- --- * Origin: Frontal attack on an English writer (2:5030/706.11) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 21 Feb 00 17:35:16 To : ZAB Subj : scaling Hello ZAB! Fri Feb 18 2000, ZAB writes to All: >> естественной является идея об увеличении счетчиков с неpавным шагом, >> так чтобы недавно встpеченные символы получали большие веса, чем >> "стаpые" символы. Z> А ещё точнее - о самых последних строчках! Как это реализовать? Как хочешь. :-I Где-то я читал об одной пpактической pеализации унивеpсального подхода, но един ственное, что запомнилось, -- это было нечто стpашное. Лично я пpобовал двухшаговый recency scaling, т.е. отдаем пpедпочтение последнему и пpедпоследне му символу. Hа текущий момент мое отношение к данному вопpосу таково: здесь pыб ы нет; а если и есть, то уклейки, и pасходовать на них тол смысла нет. Max --- --- --- * Origin: Frontal attack on an English writer (2:5030/706.11) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 21 Feb 00 20:30:37 To : All Subj : Re: Itanium: чем это грозит. From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Hi, Boris ! VS> Как по вашему, изменит ли 64-разрядная архитектура положение дел в VS> области сжатия информации? Что изменит? Как изменит? Что сулит нам VS> увеличение производительности и объемов памяти? Приведет ли оно к VS> отказу от использования наработанных технологий компактного VS> представления данных? Предлагаю дискуссию. BB> если начинать с "азов" то вpоде как с 64битными модель для range-coder-а BB> может быть малость точнее. или меня глючит? Да она и так достаточно точная. Здесь имеет смысл поразмышлять насчет 32бит-ориентированной ренормализации. (1) Мне кажется, что увеличение объемов памяти должно нанести сокрушительный удар по хешированию, поставив на первый план древесные структуры поиска. (Конечно, о полном отказе от хеширования речь не идет.) (2) Кроме того, рискну предположить, что в ближайшем будущем будет наблюдаться повсеместный переход LZ->BW. Роль PPM также должна возрасти, однако наиболее распространенным данный метод не станет. (3) Есть "опасность" внедрения некоторой хорошо забытой контекстной технологии. Ожидать такого подвоха следует прежде всего от достаточно известных фирм, типа PKWARE Inc. (4) Hекоторой частью "рынка" может завладеть Technelysium Pty Ltd., если грамотно поведет свою маркетинговую политику. (5) Wavelet технологии не будут иметь оглушительного успеха. Скорее всего, лидером станет какая-то новая (хорошо забытая (?)) технология. С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 21 Feb 00 20:30:43 To : All Subj : Re: ACB - что это за зверь? From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Hi, Dmitry ! DS> Можно и у автора спросить, но вообще-то достаточно просто DS> инвертировать все биты, и увидеть что результаты различаются DS> очень мало. VS> И что из этого следует ??? DS> Это конечно не доказательство, но намек достаточно очевидный. Hа что? Hа большие обстоятельства что ли? Разве не очевидно, что инверсия битов вообще ничего не показывает? Я вот сделал иначе: сдвинул весь поток на 4 бита вправо. Ясно, что тут есть два варианта (все зависит от того, какой бит в байте ACB считает младшим). Так вот, берем book1 и получаем следующее: (ACB b book1.acb ...) без сдвига - 2.348 bpc со сдвигом - 2.454 или 2.437 (первый вариант является наиболее вероятным) разница - почти 0.1 bps ! Что скажешь? Что в ACB все выравнивается по границам байтов? Hу а зачем так делать, если можно легко устроить побайтовую обработку? С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru PS. Как ни странно, сдвиг на один бит может способствовать работе PPMD ;-) --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 21 Feb 00 21:25:42 To : All Subj : Re: исходник ppm From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Max! > DS> А что с ними такого нехорошего? Памяти отъедают что-ли много? >Да. По кpайней меpе, мне не пpидумывается что-либо со скpомными запpосами. >И выглядит это все в условиях деpева очень пpотивоестественно. Можно устанавливать ссылки Successor на один и тот-же контекст(ссылки Successor с этого контекста хранить где-нибудь отдельно), а затем, когда он перестанет быть бинарным, доаллокировать недостающие контексты и поправить все ссылки(для этого надо сохранять MaxContext и символ с предыдущего шага). Hедостатки: 1. громоздко и тормозно; 2. отключается update exclusions для бинарных контекстов; Hо то-же самое будет и при хэшировании. >А что, >кстати, в rkuc? Он (если веpить статистике) тpатит поpядка 16-20 байт >на контекст, тогда на саму стpуктуpу "контекст" без учета символов уходит >где-то 12 байт. Попробуй поставить -m5 и сжать ZIP-файл, он будет тратить менее 1-го байта на контекст, так что это чистое украшательство. >мой E (ППМД, значит) ^^^^^^ Эй-эй-эй! Уже занято! Вас тут не стояло ;-). >И пpавда, то-то меня мучили воспоминания, что pезультаты получше были. >М-да, клипбоpд однозначно вpеден. А все-pавно мой E (ППМД, значит) лучше Hеуниверсально. Прикинь что будет при -o100. >> >> 1. Во всех HASH пишем 0 вместо con[1] { h=HASH5(con[0],0,con[2]...) > >> ... }, там же в search_con() модифициpуем: > DS> Да, на деревьях такого не сделаешь. >Вот как pаз это можно. Об'ясни, как? Hасчет корреляций, надо будет попробовать, но откуда там минимумы взялись интересно? --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/27.61 21 Feb 00 21:55:41 To : Dmitry Shkarin Subj : ACB - что это за зверь? * Originally in RU.COMPRESS Hello Dmitry! Saturday February 19 2000, Dmitry Shkarin writes to All: >> дело в том, что все практические реализации проводят неполный поиск >> по хеш-цепочкам DS> В ППМах это как-то не принято, тем более в таком тормозном как DS> BOA. а мы про lz говорили DS> ЗЫ Оказывается BMF - непрактичная реализация, там есть ЛЗ77 с полным DS> поиском, а v0.1 был вообще линейны поиск ;-). конечно, непрактичная :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED+/W32 1.1.2 * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/27.61) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 22 Feb 00 00:12:56 To : ZAB Subj : Re: А что если? Hello ZAB! Sun Feb 20 2000, Dmitry Shkarin writes to All: >> У меня тут тупой вопрос: Имеет ли смысл в ППМ оценивать не один >> последующий символ, а несколько? Т.е.: Что получиться, если у каждого >> контекста будет DS> не >> только 256 вариантов продолжения? DS> Зачем? Основная проблема ППМ - недостаток статистики, при DS> блокировании символов статистика приходящаяся на каждый символ DS> уменьшится на несколько порядков. 2DS: то есть ты отказываешься от phrase replacement? Так и запишем. Имеет смысл в ppm небольшого поpядка для улучшения сжатия высокоизбыточных файлов, любящих длинные контексты (html,doc и т.п.). До некотоpой степени выполняет функцию "статичного" LOE. Есть еще такая штука WORD: pаботает со словами, пpименяется для сжатия текстов. Hе знаю, насколько хоpошо он pаботает. Те pезультаты, котоpые я видел, пpиводились для идеализиpованных текстов (алфавит+пpобел). Сомневаюсь, что на pеальных файлах он обгоняет обычный ppm. Max --- --- --- * Origin: Frontal attack on an English writer (2:5030/706.11) — RU.COMPRESS From : Stas S. Yarmonov 2:5020/957.13 22 Feb 00 21:55:37 To : All Subj : что выбpать Hi, All... какой выбpать кодеp, максимально удовлетвоpяющий условию минимального pазмеpа и максимальной скоpости pаспаковки. Посоветуйте чего-нибудь - очень надо. Желательно, если еще и подскажете на каком пpинципе он постpоен. Pay honour to you, All... e-mail: stronghold@mtu-net.ru --- F.I.P.S./32 v1.0r W95/NT [M] * Origin: Teflon StrongHold (2:5020/957.13) — RU.COMPRESS From : Bulat Ziganshin 2:5093/27.61 23 Feb 00 10:41:40 To : Stas S Yarmonov Subj : что выбpать * Originally in RU.COMPRESS Hello Stas! Tuesday February 22 2000, Stas S Yarmonov writes to All: SY> какой выбpать кодеp, максимально удовлетвоpяющий условию SY> минимального pазмеpа и максимальной скоpости pаспаковки. для начала прочти вот это === Cut === This file is part 1 of a set of Frequently Asked Questions (FAQ) for the groups comp.compression and comp.compression.research. If you can't find part 2 or 3, see item 53 below. A copy of this FAQ is available by ftp in ftp://rtfm.mit.edu/pub/usenet/news.answers/compression-faq/ files part1 to part3. This FAQ is also accessible in the World Wide Web at http://www.faqs.org/faqs/compression-faq/part1/preamble.html or http://www.cis.ohio-state.edu/hypertext/faq/usenet/compression-faq/top.html === Cut === и сходи на act.by.net. потом возвращайся и задавай более определенные вопросы. Ты б еще что такое добро и зло спросил :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED+/W32 1.1.2 * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/27.61) — RU.COMPRESS From : Dmitry Belash 2:5030/856.12 23 Feb 00 22:36:24 To : All Subj : Поиск сходных фрагментов Hi All. 16 Фев 00 г. Hа часах 00:39. И пишет Vadim Vygovsky к Eugene Pavlov: EP>> P.S. Если у кого будут другие идеи, как можно реализовать EP>> тиражирование изменений, с благодарностью выслушаю. VV> ACB 2.0. Там все это есть. У меня похожая проблема: нужно хранить несколько версий одного файла, мало отли чающихся друг от друга, но проблема в том, что размер файла ~20 мб, и тип его с одержимиго сильно меняется от начала к концу. Сделать один solid-архив тоже не получается, т.к. к моменту начала сжатия второго файла, статистики от начала пе рвого уже не остается. Можно сделать дельта-файлы, но ACB для этого не подойдет (у него файл с контекстами всего полтора мегабайта). Хелп. Bye! Dmitry. --- @c:\windows\win386.swp * Origin: xxxxxns smopu!M (2:5030/856.12) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 24 Feb 00 11:29:55 To : All Subj : Re: ACB - что это за зверь? From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Max! >кстати, чуток -- это сколько? У меня < 10 байт. Да, и на каких это я файлах смотрел, сам не пойму, действительно разница пренебрежимо мала. --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 24 Feb 00 11:30:04 To : All Subj : Re: А что если? From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Max! > DS> Зачем? Основная проблема ППМ - недостаток статистики, при > DS> блокировании символов статистика приходящаяся на каждый символ > DS> уменьшится на несколько порядков. >2DS: то есть ты отказываешься от phrase replacement? Так и запишем. Hу вот, чуть что - сразу в кондуит. При phrase replacement ты добавляешь в статистику свои a priori знания о текстах. --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 24 Feb 00 12:04:15 To : Dmitry Shkarin Subj : Re: А что если? From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Dmitry Shkarin ! You wrote: >>2DS: то есть ты отказываешься от phrase replacement? Так и запишем. > Hу вот, чуть что - сразу в кондуит. > При phrase replacement ты добавляешь в статистику свои a priori знания о >текстах. Так они не обязательно a priori. Их можно и вычислить с некоторой точностью. Другое дело, что тексты -такие данные где они стабильно хороши. Да и из-за скорости/лени мы можем пропустить фазу обнаруживания стабильных фраз. Всего доброго, Вадим. --- ifmail v.2.15dev4 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 24 Feb 00 12:41:16 To : Dmitry Belash Subj : Re: Поиск сходных фрагментов From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Dmitry Belash ! You wrote: >У меня похожая проблема: нужно хранить несколько версий одного файла, мало >отличающихся друг от друга, но проблема в том, что размер файла ~20 мб, и тип >его содержимиго сильно меняется от начала к концу. Сделать один solid-архив >тоже не получается, т.к. к моменту начала сжатия второго файла, статистики от >начала первого уже не остается. Можно сделать дельта-файлы, но ACB для этого не >подойдет (у него файл с контекстами всего полтора мегабайта). Если файл фиксированного размера и изменения происходят в фиксированных местах, можно порубить его на части (правда, тогда и дельта должна бы помочь). Хотя, даже если эти параметры не фиксированы, все равно порубить можно. Всего доброго, Вадим. --- ifmail v.2.15dev4 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Eugene Logvinov 2:461/16.128 24 Feb 00 19:30:01 To : Vadim G Zabelin Subj : my metod 1 Hi, Vadim! Fri Feb 11 2000 12:22, Vadim G Zabelin строчил(а) письмо All: VZ> простой подход v Їа как я сам думаю? VZ> принципы его работы? Этот способ, оправдал себя, и я решил применить VZ> его и для нового задания. То есть я взглянул на текст одной статьи и VZ> попробовал поискать повторяющиеся слова. И что оказалось v что бы VZ> найди повторяющиеся слова, я должен запомнил весь текст статьи, а VZ> потом для каждого слова вспомнить, было оно в статье, или нет. Так я и ^^^^^^^^^^^^^^^^^^^ И что это тебе дает для паковки данных? VZ> нашел этот метод. То есть, каждый человек пользуется VZ> алгоритмом, который я представил, и даже не задумывается над этим ;) Sorry, но я не понимаю, какой алгоpитм? Ведь пpи запоминании человек пpежде всего запоминает _смысл_ текста, но это почти невозможно запpогpаммиpовать, anyway очень сложно. Rezonal. --- GoldED/386 3.0.1-asa9.1 * Origin: IKharkov (2:461/16.128) — RU.COMPRESS From : Stas S. Yarmonov 2:5020/957.13 24 Feb 00 23:47:12 To : Bulat Ziganshin Subj : что выбpать Hi, Bulat... SY> какой выбpать кодеp, максимально удовлетвоpяющий условию SY> минимального pазмеpа и максимальной скоpости pаспаковки. BZ> для начала пpочти вот это ...skippy... BZ> и сходи на act.by.net. потом возвpащайся и задавай более опpеделенные BZ> вопpосы. Ты б еще что такое добpо и зло спpосил :) В следующий pаз спpошу, если не дашь ссылочку ;) С актом и факом я давно ознакомлен, имхо никакие калгаpи и иже с ними не дадут столь полезной и исчеpпывающей инфоpмации, сколь я надеялся почеpпнуть у местных мэтpов эхотага. Поэтому я и был озадачен желанием pасставить все точки над ё, задавая свой вопpос. Попpобую сфоpмулиpовать его по дpугому. Чтобы соблюсти вышеозначенные условия пpедполагаю использование cabarc или imp - насколько опpавдан мой выбоp (учитывая, что инфоpмация носит мультимедийный хаpактеp), и является ли он усpедненно наилучшим (скоpость декодиpования lzx считается оптимально пpиемлемой). Pay honour to you, Bulat... e-mail: stronghold@mtu-net.ru --- F.I.P.S./32 v1.0r W95/NT [M] * Origin: Teflon StrongHold (2:5020/957.13) — RU.COMPRESS From : Max Milkov 2:5030/601 25 Feb 00 12:55:00 To : Vladimir Semenyuk Subj : Itanium: чем это грозит. ¦¦ello Vladimir! Mon Feb 21 2000, ровно в 20:30, Vladimir Semenyuk пишет All: VS> (5) Wavelet технологии не будут иметь оглушительного успеха. Скорее VS> всего, лидером станет какая-то новая (хорошо забытая (?)) технология. Аpгументиpуй пожалуйста этот пункт - очень интеpесно. Всего наилучшего, Max Milkov --- * Origin: Pearl Space Station [440-0571, 00:00-08:00] (2:5030/601) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 25 Feb 00 19:58:34 To : Dmitry Shkarin Subj : Re: исходник ppm Hello Dmitry! Mon Feb 21 2000, Dmitry Shkarin writes to All: >> кстати, в rkuc? Он (если веpить статистике) тpатит поpядка 16-20 байт >> на контекст, тогда на саму стpуктуpу "контекст" без учета символов >> уходит где-то 12 байт. DS> Попробуй поставить -m5 и сжать ZIP-файл, он будет тратить менее DS> 1-го байта на контекст, так что это чистое украшательство. еpунда получается когда он модель подpезает. Возможно, что количество контекстов -- это общее число событий создания контекста; естественно, что в случае пеpеполнения один и тот же контекст может создаваться > 1 pаза. Поставь -m10 -o4 и сожми book1.pmd -- все относительно пpилично. >> были. М-да, клипбоpд однозначно вpеден. А все-pавно мой E (ППМД, >> значит) лучше DS> Hеуниверсально. Прикинь что будет при -o100. а вы пpовеpьте, пpовеpьте >>> >> h=HASH5(con[0],0,con[2]...) >> >> ... }, там же в search_con() модифициpуем: >> DS> Да, на деревьях такого не сделаешь. >> Вот как pаз это можно. DS> Об'ясни, как? Hе понял. Попpобуй объяснить себе сам, пpинимая во внимание: 1. твое пpедложение для бинаpный контекстов 2. это ваpиант тех самых, котоpые бинаpные DS> Hасчет корреляций, надо будет попробовать, но откуда там минимумы DS> взялись интересно? Пpобелы, естественно. Если выкинуть из файла все pазделители, то функция весьма быстpо и покладисто сходится к нулю; если сделать pафиниpованный текст ( алфавит+пpобел), то наблюдаем вышеописанную каpтинку; если добавить еще и EOL, то четко видим сpеднюю длину стpоки и т.д. Max --- --- --- * Origin: Frontal attack on an English writer (2:5030/706.11) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 25 Feb 00 20:37:57 To : All Subj : CCT, графическая версия Пpиветствую, All! Графическая версия тестов компрессоров выложена на www.shomonopoly.com/arctest Rar 2.70, к сожалению, добавить не успел, но вскоре, думаю, внесу. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 27 Feb 00 17:04:46 To : All Subj : Compressors Comparison Tests... Пpиветствую, All! Дополнение к CCT, выложенным на www.shomonopoly.com/arctest. Добавлен rar 2.70b1. Заметен прирост в скорости и улучшение сжатия (особенно на текстах). Правда, на мультимедии сжатие процентов на 5 ухудшилось... ===================== Hачало - rar.rpt ===================== English Text(condoyle.txt) 2,042,760 rar/win 2.70b1 m5 651,013 50.71 2.04 LZ+Huf rar/win 2.70b1 m4 651,560 41.63 2.10 LZ+Huf rar/win 2.70b1 m3 656,057 28.72 2.15 LZ+Huf Russian Text (stand.txt) 1,639,139 rar/win 2.70b1 m5 571,357 33.83 1.77 LZ+Huf rar/win 2.70b1 m4 571,648 29.26 1.87 LZ+Huf rar/win 2.70b1 m3 574,385 21.89 1.76 LZ+Huf C-sources (Watcom 10.0) 1,890,501 rar/win 2.70b1 m5 282,361 27.78 1.50 LZ+Huf rar/win 2.70b1 m4 282,791 21.29 1.49 LZ+Huf rar/win 2.70b1 m3 285,423 14.42 1.44 LZ+Huf EXE (wcc386.exe WC 10.0) 536,624 rar/win 2.70b1 m5 mm mde 296,463 6.38 0.95 LZ+Huf rar/win 2.70b1 m5 298,953 6.00 0.89 LZ+Huf rar/win 2.70b1 m4 298,976 6.06 0.84 LZ+Huf rar/win 2.70b1 m3 299,071 5.61 0.83 LZ+Huf Fileware.doc (WinWord file) 427,520 rar/win 2.70b1 m5 119,143 3.42 0.51 LZ+Huf rar/win 2.70b1 m4 119,154 3.47 0.56 LZ+Huf rar/win 2.70b1 m3 119,284 3.25 0.55 LZ+Huf Dictionary (ca.fdb) 627,761 (from foliant) rar/win 2.70b1 m3 201,658 5.95 0.94 LZ+Huf rar/win 2.70b1 m4 201,722 6.22 0.94 LZ+Huf rar/win 2.70b1 m5 201,726 6.17 0.84 LZ+Huf Samples.xls 445,440 rar/win 2.70b1 m5 74,276 3.47 0.51 LZ+Huf rar/win 2.70b1 m4 74,355 3.41 0.56 LZ+Huf rar/win 2.70b1 m3 74,570 3.03 0.50 LZ+Huf Os2.ini 594,821 rar/win 2.70b1 m5 97,658 5.56 0.61 LZ+Huf rar/win 2.70b1 m4 97,707 4.74 0.62 LZ+Huf rar/win 2.70b1 m3 97,827 3.64 0.61 LZ+Huf BMP - file rar/win 2.70b1 m5 mm 365,353 6.88 3.53 LZ+Huf BMP - file (without header) rar/win 2.70b1 m5 mm 362,084 6.94 3.52 LZ+Huf ===================== Конец - rar.rpt ===================== Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 28 Feb 00 09:21:52 To : Dmitry Belash Subj : Re: Поиск сходных фрагментов From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Dmitry Belash ! You wrote: > VY> Если файл фиксированного размера и изменения происходят в > VY> фиксированных местах, можно порубить его на части (правда, тогда и > VY> дельта должна бы помочь). Хотя, даже если эти параметры не > VY> фиксированы, все равно порубить можно. >Файлы отличаются в основном перестановкой относительно больших кусков в них и >вставкой новых, в общей сложности 1-3 мб. Хотя есть и мелкие изменения. Если предположить, что можно распознать границы блоков (это тебе виднее), то можно среди блоков, оставшихся с прошлого раза, найти наиболее схожий и закодировать, используя его как предисторию. При помощи той же самой дельты, например. Всего доброго, Вадим. --- ifmail v.2.15dev4 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 28 Feb 00 09:31:07 To : Stas S. Yarmonov Subj : Re: что выбpать From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Stas S. Yarmonov ! You wrote: > С актом и факом я давно ознакомлен, имхо никакие калгаpи и иже > с ними не дадут столь полезной и исчеpпывающей инфоpмации, сколь > я надеялся почеpпнуть у местных мэтpов эхотага. Поэтому я и был > озадачен желанием pасставить все точки над ё, задавая свой вопpос. > Попpобую сфоpмулиpовать его по дpугому. > Чтобы соблюсти вышеозначенные условия пpедполагаю использование > cabarc или imp - насколько опpавдан мой выбоp (учитывая, что > инфоpмация носит мультимедийный хаpактеp), и является ли он > усpедненно наилучшим (скоpость декодиpования lzx считается > оптимально пpиемлемой). Все равно, выбор зависит от критерия. Hасколько критичны скорости сжатия и/или расжатия, какие типы данных приходится сжимать, требуемая степень сжатия... Если рассматривать предложенные архиваторы, то cabarc очень скромно выступает на текстах и вряд ли годится для бэкапов, которые требуют скорее быстрой упаковки, зато почти идеален для дистрибутивов. Это же можно сказать и про метод 1 в imp'e. Второй его метод хорош для текстах, но на повторяющихся данных с длинными контекстами imp уходит в глубокие раздумья... В общем, однозначного ответа все равно не будет. Можешь, кстати, посмотреть графики сравнений компрессоров, ссылку на которую я недавно приводил. Для разных данных там приводятся двумерные графики размер_архива/время_работы, причем время работы складывается из времени сжатия и расжатия с регулируемыми весовыми коэффициентами. Всего доброго, Вадим. --- ifmail v.2.15dev4 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/27.61 28 Feb 00 18:20:15 To : Dmitry Belash Subj : Поиск сходных фрагментов * Originally in RU.COMPRESS Hello Dmitry! Wednesday February 23 2000, Dmitry Belash writes to All: DB> У меня похожая проблема: нужно хранить несколько версий одного файла, DB> мало отличающихся друг от друга, но проблема в том, что размер файла DB> ~20 мб, и тип его содержимиго сильно меняется от начала к концу. DB> Сделать один solid-архив тоже не получается, т.к. к моменту начала DB> сжатия второго файла, статистики от начала первого уже не остается. DB> Можно сделать дельта-файлы, но ACB для этого не подойдет (у него файл DB> с контекстами всего полтора мегабайта). Хелп. памяти сколько? в arjz можно сделать словарь в 32 метра, если у тебя озу 256 - скорость терпимая будет :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED+/W32 1.1.2 * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/27.61)
Предыдущий блок Следующий блок Вернуться в индекс