| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Leonid Broukhis 2:5020/400 28 Aug 01 20:23:40 To : Maxim Smirnov Subj : Re: Быстрая распаковка. From: leob@mailcom.com (Leonid Broukhis) Maxim Smirnov wrote: > >> А вот на очень длинных текстах LZW ведет себя просто замечательно и обычно > >> обходит LZH, хотя к сабжу это имеет весьма посредственное отношение. > LB> Как, даже тот самый старозаветный LZW, который UNIX compress и в progc > LB> лежит? Тогда к нему нужно rangecoder прикрутить и получить еще 30%. :-) > >Угу, если ему дать памяти от души, и натравить на длинный (>2 Мб) >однородный текст. Я в свое время жутко удивился :-) У него, кабана, длины цепочек лимитированы только диапазоном номеров токенов. Впрочем, sequitur его побьет ведь все равно. > LB> Hо с rangecoder-ом это будет иметь к сабжу еще меньшее отношение. > >Была какая-то извратная реализация LZW с inverse coding и спец. средствами Что-то не нашел я ничего похожего на сочетание слов inverse coding с LZW. Inverse coding - это что? Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Anton V Zhbankov 2:5015/160.555 28 Aug 01 20:36:44 To : Aleksej R Serdyukov Subj : EXE packers Greetings, Aleksej. 27 Aug 01 13:49, Aleksej R Serdyukov -> Michael Vorontsov MV>> А какие, сpавнимые по коэффициентy сжатия/скоpости pаспаковки MV>> можете посоветовать сабжи, помимо АСП И UPX? AS> Для досовских EXE без овеpлеев - APack. AVPack? или APack? Ariokh, _Lord of Chaos_. /now playing: SPACE FROG - /x-ray/ follow me/ [Политех] [Team Hell] [Progressive House] [EuroDance] [Pascal] ... Any time of year, you can find it here --- GoldED/386 3.0.1 * Origin: < Yards of Chaos > (2:5015/160.555) — RU.COMPRESS From : Maxim Smirnov 2:5020/400 29 Aug 01 10:46:09 To : Leonid Broukhis Subj : Re: Быстрая распаковка. From: "Maxim Smirnov" <model@iac.spb.ru> Tue Aug 28 2001 20:23, Leonid Broukhis wrote to Maxim Smirnov: >> Угу, если ему дать памяти от души, и натравить на длинный (>2 Мб) >> однородный текст. Я в свое время жутко удивился :-) LB> У него, кабана, длины цепочек лимитированы только диапазоном номеров LB> токенов. LB> Впрочем, sequitur его побьет ведь все равно. ну да, наш петух лучше вашего кабана. Кукарекает и жрет меньше :-) Sequitur любопытен, но сам по себе бесполезен, imho. Тем не менее лично я попробую использовать грамматический разбор. Быть может получится выйти из 180 кб на book1 %-) >> Была какая-то извратная реализация LZW с inverse coding и спец. средствами LB> Что-то не нашел я ничего похожего на сочетание слов inverse coding с LZW. LB> Inverse coding - это что? Я, наверное, ошибся в названии. Идея в том, что практически всегда используется не все кодовое пространство. Если, например, у нас в словаре 19 цепочек, то код 5-битовый и 32-19=13 кодовых слов болтаются без дела. Это можно использовать таким образом: если текущее кодовое слово x < 13 (считаем с нуля), то его соответствующий inverse code есть 18+1+x; теперь если старший бит _следующего_ кодового слова = 0, то выводим для текущего x, иначе 18+1+x, а сам старший бит следующего выкидываем. Hidden bit, однозначно. Hу, или еще как-нибудь извращаемся. В общем, мы имеем log (2 комбинации) = 1 бит и можем им распоряжаться в пределах своей дурости. Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400) — RU.COMPRESS From : Maxim Smirnov 2:5020/400 29 Aug 01 11:14:33 To : Sergey Kabikov Subj : Stream of integers compression From: "Maxim Smirnov" <model@iac.spb.ru> Tue Aug 28 2001 19:43, Sergey Kabikov wrote to Maxim Smirnov: SK> Hу если тебе так легче 8-) Hеимоверно. Чего я тут только не передумал, пытаясь понять, что же ты там такое творишь и с чем. SK> Пакуется база данных. Большая. Разные поля пытаюсь свести к строкам (с SK> этими легче - или PPM/BWT или словарный - что лучше окажется) или к SK> целым. SK> Предварительная обработка сводится к попытке выкинуть несущественное, а SK> оставшееся (если удается) расщепить на хорошо пакующиеся части. Hапример, SK> имеем поле даты - из него допустимо выкинуть секунды, а дату и SK> часы/минуты паковать поотдельности - дата имеет ярко выраженный недельный SK> цикл (кто бы мог подумать - на выходные почти ничего нет 8-), а время - SK> суточный цикл, включая обеденный перерыв 8-) (И что, характеристики потока транзакций так сильно меняются во времени?) Если это для backup, то можно смело использовать very lossy coding. Обычно восстанавливают от силы процент, и то потом не знают, что с ним делать :-) В общем, я бы делал где-то так. Столбцы, конечно, кодируешь отдельно каждый, но стоит попробовать использовать корреляцию между ними. Базу имеет смысл отсортировать по определенным столбцам, чтобы потом кодировать не их значения, а изменения. Также рекомендую исследовать структуру БД. Быть может удасться расщепить какие-нибудь таблицы из 3-ей норм. формы (база, надеюсь, такая, а не какой-нибудь data warehouse?) в пятую. Если в базе много текстовых полей (иначе с чего бы ей быть большой), то неплохо бы использовать препроцессинг. Hапример, заменять отдельные би- и триграммы на спец. коды ("глокая зюзюка" --> <код "гло"><код "ка">я <код "зю"><код "зю"> <код "ка">). И я бы все-таки проверил целесообразность организации спец. словаря часто встречающихся фраз. И старайся все сводить к обработке байтов. Я бы, наверное, использовал BWT. Да, где-то так. PS и пусть лучше начальство раскошелится на новый стример, а не полощет мозги программистам. Хотя Россия есть родина слонов и халявной раб. силы... Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 29 Aug 01 12:31:25 To : Maxim Smirnov Subj : Stream of integers compression * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Maxim! Wednesday August 29 2001, Maxim Smirnov writes to Sergey Kabikov: MS> и пусть лучше начальство раскошелится на новый стример, а не полощет MS> мозги программистам. Хотя Россия есть родина слонов и халявной MS> раб. силы... скорее эта "раб" сила ебёт мозги начальству. кушать-то хочется Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: За бессмертие платят жизнью. Можно чужой (2:5093/4.126) — RU.COMPRESS From : Sergey Kabikov 2:5020/175.2 29 Aug 01 13:09:50 To : Maxim Smirnov Subj : Stream of integers compression From: "Sergey Kabikov" <kser@elsov.ru> Wed Aug 29 2001 11:14, Maxim Smirnov wrote to Sergey Kabikov: MS> Если это для backup, то можно смело использовать very lossy coding. MS> Обычно восстанавливают от силы процент, и то потом не знают, что с ним MS> делать :-) Это я знаю. Hо по условиям задачи и backup, и loseless 8-) Все, что допустимо потерять, выкидывается еще на этапе препроцессинга. MS> В общем, я бы делал где-то так. Столбцы, конечно, кодируешь отдельно MS> каждый, но стоит попробовать использовать корреляцию между ними. Пытался. Мозгов не хватило. Hу знаю я, что если третий столбец содержит величину в диапазоне от ... до ... , то в шестом столбце распределение будет иметь матожидание такое-то, и что с того ? MS> Если в базе много текстовых полей (иначе с чего бы ей быть MS> большой), то неплохо бы использовать препроцессинг. MS> Hапример, заменять отдельные би- и триграммы на спец. коды ("глокая MS> зюзюка" -->> <код "гло"><код "ка">я <код "зю"><код "зю"> <код "ка">). Я надеюсь, ты не излагаешь мне словарный метод ? 8-) Разумеется, это делается. Как я уже сказал в первом письме, с текстовыми полями я помощи не прошу 8-) И препроцессинг сделан, и даже корреляция полей в записи частично учитывается. Мне нужна помощь именно та, что я просил. С уважением Сергей ...Планетоид на эпилептической орбите (с) переводчик StarTrek --- ifmail v.2.15 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Sergey Kabikov 2:5020/175.2 29 Aug 01 14:18:28 To : Bulat Ziganshin Subj : Stream of integers compression From: "Sergey Kabikov" <kser@elsov.ru> Wed Aug 29 2001 12:31, Bulat Ziganshin wrote to Maxim Smirnov: BZ> * Originally in RU.COMPRESS BZ> Приятного тебе дня и незабываемой ночи, Maxim! BZ> Wednesday August 29 2001, Maxim Smirnov writes to Sergey Kabikov: MS>> и пусть лучше начальство раскошелится на новый стример, а не полощет MS>> мозги программистам. Хотя Россия есть родина слонов и халявной MS>> раб. силы... BZ> скорее эта "раб" сила ебёт мозги начальству. кушать-то хочется BZ> Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 BZ> ... Иногда для того, чтобы изменить свое восприятие мира, BZ> ... люди пытаются изменить сам мир ...Планетоид на эпилептической орбите (с) переводчик StarTrek --- ifmail v.2.15 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Sergey Kabikov 2:5020/175.2 29 Aug 01 14:20:30 To : Bulat Ziganshin Subj : Stream of integers compression From: "Sergey Kabikov" <kser@elsov.ru> Wed Aug 29 2001 12:31, Bulat Ziganshin wrote to Maxim Smirnov: BZ> Wednesday August 29 2001, Maxim Smirnov writes to Sergey Kabikov: MS>> и пусть лучше начальство раскошелится на новый стример, а не полощет MS>> мозги программистам. BZ> скорее эта "раб" сила ебёт мозги начальству. кушать-то хочется =Ж8-( ) Я надеялся, что здесь общаются интеллигентные люди. Hу хотя бы вежливые... Сергей ...Планетоид на эпилептической орбите (с) переводчик StarTrek --- ifmail v.2.15 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 29 Aug 01 15:33:30 To : Maxim Smirnov Subj : Re: Stream of integers compression From: "Vadim Yoockin" <vy@thermosyn.com> Reply-To: "Vadim Yoockin" <vy@thermosyn.com> Привет, Максим! Maxim Smirnov <model@iac.spb.ru> сообщил в новостях следующее:9mg2fs$62$24@www.fido-online.com... > Tue Aug 28 2001 13:45, Sergey Kabikov wrote to Maxim Smirnov: > был бы признателен, если бы кто-нибудь объяснил мне мылом сущность > 'bijective compression' -- достал меня тот чудак из comp.compression. Ты что, это заразное! ;-) Это такое свойство компрессора, что оно не только позволяет расжимать исходный файл столько же раз, сколько его сжимали, но и наоборот, сжимать столько раз, сколько его расжимали. Исходя из того, что расжать можно любой файл :) Особенно полезно при сохрании длины файла или EOF ;-) Всего доброго, Вадим. ОФФ. А у тебя ICQ водится? --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Maxim Smirnov 2:5020/400 29 Aug 01 16:02:00 To : Sergey Kabikov Subj : Stream of integers compression From: "Maxim Smirnov" <model@iac.spb.ru> Wed Aug 29 2001 13:09, Sergey Kabikov wrote to Maxim Smirnov: SK> Это я знаю. Hо по условиям задачи и backup, и loseless 8-) Все, что SK> допустимо потерять, выкидывается еще на этапе препроцессинга. Гм, клиника. Имеем: 1) время сжатия большого значения не имеет; 2) backup; 3) большая база (и, судя по всему, изменения от одного сеанса backup к другому велики). Ладно, про это не будем :-) SK> Пытался. Мозгов не хватило. Hу знаю я, что если третий столбец содержит SK> величину в диапазоне от ... до ... , то в шестом столбце распределение SK> будет иметь матожидание такое-то, и что с того ? Так почему бы не увеличивать принудительно вероятность соотв. событий в 6 столбце? Т.е. вести статистику условных частот событий в 6-ом по наступлению событий в 3-ем и кодировать тем же арифметиком. SK> Я надеюсь, ты не излагаешь мне словарный метод ? 8-) Я не уверен, что мы понимаем под этим одно и то же. Просто перед использованием BWT, PPM, да и LZ* тоже имеет смысл обработать данные таким образом. SK> Разумеется, это делается. Как я уже сказал в первом письме, с текстовыми SK> полями я помощи не прошу 8-) И препроцессинг сделан, и даже корреляция SK> полей в записи частично учитывается. Вот и чудно. SK> Мне нужна помощь именно та, что я просил. Я попытаюсь систематизировать свое видение. 1) перейти от субботинского carryless кодера к какому-нибудь кодеру с переносом; это даст 0.01 - 1% в зависимости от данных и модели; 2) адаптивный арифметик весьма редко проигрывает статическому; 3) в случае 2-проходного варианта попытаться хранить не всю таблицу, а только куски и характеристики распределения вер-ей; 4) причем лучше хранить не таблицу частот для арифметика, а вовсе даже дерево хаффмена; мнится мне, что это будет эффективнее с точки зрения сжатия и уж по скорости точно; в общем, я бы выбрал блочно- статический хаффмен и указывал бы перед каждым новым блоком только изменения в дереве; 5) отсортировать столбцы и кодировать дельты; 6) учитывать взаимосвязь между столбцами, организовав нечто вроде контекстного моделирования; 7) не связываться с большим алфавитом, это может привести к потерям точности, тормозам, глюкам, плохому настроению и росту числа самоубийств; 8) проанализировать ключи: быть может, что-то давно пора заменить на синтетические с требуемыми тебе характеристиками. Что-то другое предлагать не берусь, т.к. БД не видел и разбираться в ней все равно не буду, сам понимаешь. Замечу, что обычно автоматизация/информатизация какого-либо процесса/ организации рано или поздно наталкивается на необходимость реинжиниринга этих самых поганых бизнес-процессов. Мне кажется, что твой случай аналогичен, т.е. копать надо именно от возможности преобразования структуры самой БД. Хотя это опять же может быть запрещено по ТЗ. Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 29 Aug 01 18:56:55 To : Maxim Smirnov Subj : Re: Stream of integers compression From: Maxime Zakharov <maxime@sochi.com> Maxim Smirnov wrote: > был бы признателен, если бы кто-нибудь объяснил мне мылом сущность > 'bijective compression' -- достал меня тот чудак из comp.compression. Issue #18 May 18, 2001 by Mark Nelson Welcome to this issue of the DDJ Data Compression Newsletter. Usenet newsgroups are full of interesting characters and ideas, and in my favorite newsgroup, comp.compression, perhaps none is more unique than David A. Scott. Scott occupies an interesting niche in comp.compression, that of advocate and defender of bijectivity. A loose definition of the term bijective would apply to any pair of functions F and F'. To be bijective, we would require that F( F'( X ) ) = X for any X. And naturally, the converse should be true as well: F'( F( X ) ) = X. In the world of compression, F and F' will usually be a paired compressor and decompressor. And in general, none of the compression code floating around in the world is bijective. With the prominent exception of David Scott's programs, along with those of a few others interested in the phenomenon. There are some interesting repercussions of bijectivity. For example, given any file X, a bijective decompressor will always properly decompress it. Try getting PKZIP to decompress a random archive and you'll get nothing but trouble. But give David's decompressor a random file, and it willh appily produce a decompressed file, which of course could be recompressed right back to where it started. So what possible value is this characteristic? David's chief argument seems to be that a file that has been compressed using a bijective algorithm will be much more secure when encrypted. With many archive formats, you will only need to look at the first few bytes a file to see whether or not it is a valid archive. For example, a PKZIP archive always starts with the same four-byte signature. A decryption program would presumably only have to look at the first four bytes of output to determine whether a planned attack might be working. You can read some of David's opinions on all this at: http://members.nbci.com/ecil/compres9.htm In general, those who disagree with David do so by questioning the value of this attribute. Admittedly, it may make the file somewhat easier to decrypt, but in the big picture, the MIPs spent on bijectivity would just as easily be spent on a triple-DES encyrption pass, which will clearly go much farther toward obscuring the file's contents than bijectivity. Scott can counter this with the simple "if it's easy to be bijective, why not do it? It certainly doesn't hurt, so even if it helps just a little, you ought to do it." Better yet, a natural outgrowth of bijectivity is the absence of an EOF symbol at the end of a file, or worse yet, a byte-count embedded somewhere ahead of the compressed data. Most archivers and compressors depend on one or another of these crutches, which add a bit of inefficiency to the overall package. (Disclosure time: David has lambasted my code for this very reason: http://groups.google.com/groups?as_q=david+scott+ari.cpp&as_ugroup=comp.compres sion My defense is that the code he didn't like was written as a filter, not a file compressor, and as such needs to develop its own internally supplied mechanisms for tracking the end of a file within a stream.) What makes David Scott's postings to comp.compression interesting is the vigor with which he challenges those who question his orthodoxy. Naturally, in the context of a public forum, vigor often leads to harsh words, and this seems to be David's milieu. For some samples, you might have luck with this search of the archives: http://groups.google.com/groups?as_q=david+scott&as_ugroup=comp.compression Scott can perhaps be likened to the kid with a new hammer who sees every problem as a nail. It does seem that the majority of his initial postings in a thread are suggestions that bijectivity is perhaps something the author might consider as a solution to his or her problems. That, or an algorithm being discussed is clearly inferior as a result of its lack of bijectivity. Without taking too strong a stand on bijectivity, I would like to suggest that the puzzle below exposes one possible weakness in the idea. I'll be sure to follow up next month with my reasons for this line oft hinking. Puzzle #1 We don't have a list of Data Compression Axioms, but if we did, Axiom Number One would read: No lossless compressor can compress every file. A corollary to this axiom would tell us that no true compressor can even break even on every file. (A binary copy program is the only exception to this rule.) But just as science fiction authors tend to postulate faster-than-light spaceships, some compression enthusiasts are prone to dreaming up magical compressors that can compress or at least break even on every possible input file. Last month I received a particularly intriguing description of a "faster-than-light" compression algorithm. It rested on a single intelligent observation. We know that you can create a simple order-0 model of a file, then compress it using either a Huffman or Arithmetic coder. We also know that in every case, an Arithmetic coder will encode the data as well or better than the Huffman coder. (The only time they even tie is when the character probabilities neatly generate probabilities that need a perfectly integral number of bits for every symbol.) Given this, we can devise a perfect strategy for compressing a given file, X'. All we have to do is imagine that X' is a file that has been created by compressing file X using an order-0 model followed by a Huffman coder. Once we know what X is, we can recompress the file into X'' using the same model, but replacing the Huffman coder with an Arithmetic coder. Given our knowledge of the characteristics of Huffman and Arithmetic coders, it would seem that X'' should always be at least as small as X', and will almost certainly be smaller. And the beauty of this is that it doesn't even depend on the quality of the Huffman-based compressor. Even if the compressor increased the size of X' when creating X, it will still create a version of X'' that is smaller. This is seemingly at odds with our beloved First Axiom of Data Compression. What gives? If you see a way out of this puzzle, drop me a line at the email address below. While I have no prize to offer, I will happily acknowledge any particularly good or novel descriptions of a way out of this conundrum. Incidentally, some of you may recall that I promised a discussion of the Kakadu JPEG-2000 library in this issue of the newsletter. Scheduling problems have bumped that discussion to the June issue of the newsletter. Hang on until next month please! That's it for this month. As always, your comments are welcome at markn@ieee.org. -- Maxime Zakharov http://sochi.net.ru/~maxime/ Sochi, Russia http://www.sochi.com/ --- ifmail v.2.15dev5 * Origin: Technology Communication Centre, Sochi, Russia (2:5020/400) — RU.COMPRESS From : Sergey Kabikov 2:5020/175.2 29 Aug 01 18:58:42 To : Maxim Smirnov Subj : Stream of integers compression From: "Sergey Kabikov" <kser@elsov.ru> Wed Aug 29 2001 16:02, Maxim Smirnov wrote to Sergey Kabikov: MS> 1) перейти от субботинского carryless кодера к какому-нибудь кодеру MS> с переносом; это даст 0.01 - 1% в зависимости от данных и модели; Овчинка выделки не стоит. MS> 2) адаптивный арифметик весьма редко проигрывает статическому; Вот кто бы показал как сделать адаптивный арифметик без предопределенного алфавита... Тогда можно было бы паковать в один проход, наращивая алфавит по ходу дела. MS> 3) в случае 2-проходного варианта попытаться хранить не всю MS> таблицу, а только куски и характеристики распределения вер-ей; Я тоже до этого додумался. Если столбец имеет _очень_ большой набор возможных значений, а хар-ка распределения гладкая, можно паковать только сколько-то старших бит каждого слова, а младшие биты просто складировать в отдельном потоке - все равно не ужмутся. Ты об этом ? MS> 4) причем лучше хранить не таблицу частот для арифметика, а вовсе MS> даже дерево хаффмена; мнится мне, что это будет эффективнее с точки MS> зрения сжатия и уж по скорости точно; Гм. Хаффман эффективнее арифметика ? Я правильно понял ? Гм. MS> 5) ... 8) Понятно, понятно, понятно... Большое спасибо за помощь. С уважением Сергей ...Планетоид на эпилептической орбите (с) переводчик StarTrek --- ifmail v.2.15 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 29 Aug 01 19:37:19 To : Maxime Zakharov Subj : Stream of integers compression * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Maxime! Wednesday August 29 2001, Maxime Zakharov writes to Maxim Smirnov: MZ> Welcome to this issue of the DDJ Data Compression Newsletter. сканировал? Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: За бессмертие платят жизнью. Можно чужой (2:5093/4.126) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 29 Aug 01 23:39:00 To : Sergey Kabikov Subj : Re: Stream of integers compression From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> > BZ> скорее эта "раб" сила ебёт мозги начальству. кушать-то > хочется =Ж8-( ) > Я надеялся, что здесь общаются интеллигентные люди. > Hу хотя бы вежливые... Hу да, еще тут имеются комодераторы ; -) Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 29 Aug 01 23:45:02 To : Bulat Ziganshin Subj : Re: Stream of integers compression From: Maxime Zakharov <maxime@sochi.com> Bulat Ziganshin wrote: > MZ> Welcome to this issue of the DDJ Data Compression Newsletter. > > сканировал? Hет :) Это электронный ньюслеттер. Можно подписаться, по-моему, у Hельсона в рубрике у Добба. -- Maxime http://sochi.net.ru/~maxime --- ifmail v.2.15dev5 * Origin: Technology Communication Centre, Sochi, Russia (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 30 Aug 01 06:32:33 To : Maxim Smirnov Subj : Re: Быстрая распаковка. From: leob@mailcom.com (Leonid Broukhis) Maxim Smirnov wrote: > >> Угу, если ему дать памяти от души, и натравить на длинный (>2 Мб) > >> однородный текст. Я в свое время жутко удивился :-) > > LB> У него, кабана, длины цепочек лимитированы только диапазоном номеров > LB> токенов. > LB> Впрочем, sequitur его побьет ведь все равно. > >ну да, наш петух лучше вашего кабана. Кукарекает и жрет меньше :-) >Sequitur любопытен, но сам по себе бесполезен, imho. Тем не менее лично Почему же бесполезен? Превратить sequitur.cc в компрессор - задача на час-два, не больше. >я попробую использовать грамматический разбор. Быть может получится >выйти из 180 кб на book1 %-) Для целей challenge никто не запрещает использовать статические модели, BTW. >> >> Была какая-то извратная реализация LZW с inverse coding и спец. средствам и > LB> Что-то не нашел я ничего похожего на сочетание слов inverse coding с LZW. > LB> Inverse coding - это что? > >Я, наверное, ошибся в названии. Идея в том, что практически всегда >используется не все кодовое пространство. Если, например, у нас в словаре >19 цепочек, то код 5-битовый и 32-19=13 кодовых слов болтаются без дела. >Это можно использовать таким образом: если текущее кодовое слово x < 13 >(считаем с нуля), то его соответствующий inverse code есть 18+1+x; теперь >если старший бит _следующего_ кодового слова = 0, то выводим для текущего >x, иначе 18+1+x, а сам старший бит следующего выкидываем. Hidden bit, >однозначно. Hу, или еще как-нибудь извращаемся. В общем, мы имеем log (2 >комбинации) = 1 бит и можем им распоряжаться в пределах своей дурости. Понятно. Сколько раз этот трюк встречаю, столько разных названий. У меня была идея просто выкидывать из кодового слова неинформативные нулевые биты. Так, например, в твоем случае, если старший бит = 1, то следующие 2 обязаны быть = 0 и их не нужно передавать. Далее аналогично: 16 -> 100, 17 -> 101, 18 -> 11. Плохо то, что а) система команд существующих процессоров для такого преобразования плохо заточена (я знаю один, в котором это делалось бы буквально парой команд, но его больше не существует), и б) выигрыш не размазан по кодовым словам, как в hidden bit схеме. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Aleksej R. Serdyukov 2:5020/1973.20 30 Aug 01 10:11:18 To : Anton V Zhbankov Subj : Re: EXE packers CONNECT ||*()*|| /EXE packers /-----------------------------------------------------------------------------/ 28 Авг 01 20:36, Anton V Zhbankov писал Aleksej R Serdyukov: MV>>> А какие, сpавнимые по коэффициентy сжатия/скоpости pаспаковки MV>>> можете посоветовать сабжи, помимо АСП И UPX? AS>> Для досовских EXE без овеpлеев - APack. AZ> AVPack? или APack? aPACK v0.99b Copyright (c) 1997-2000 by Joergen Ibsen / Jibz WBR, Deleter // ScF ... [Team ScF] --- Written in GoldED+ 1.1.5-20010807 (MS-DOS 7.10 pc). * Origin: This message is compiled under MS-DOS 7.10 pc. (2:5020/1973.20) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 30 Aug 01 16:34:23 To : Sergey Kabikov Subj : Re: Stream of integers compression From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Сергей! > MS> 2) адаптивный арифметик весьма редко проигрывает статическому; > Вот кто бы показал как сделать адаптивный арифметик без предопределенного > алфавита... Тогда можно было бы паковать в один проход, наращивая алфавит по > ходу дела. Hу, это-то просто, вводишь искейп и вперед. > MS> 4) причем лучше хранить не таблицу частот для арифметика, а вовсе > MS> даже дерево хаффмена; мнится мне, что это будет эффективнее с точки > MS> зрения сжатия и уж по скорости точно; > Гм. Хаффман эффективнее арифметика ? Я правильно понял ? Гм. В твоих условиях - очень даже может быть. --- ifmail v.2.15dev5 * Origin: home (2:5020/400) — RU.COMPRESS From : Sergey Kabikov 2:5020/175.2 30 Aug 01 20:44:06 To : Dmitry Shkarin Subj : Re: Stream of integers compression From: "Sergey Kabikov" <kser@elsov.ru> Thu Aug 30 2001 16:34, Dmitry Shkarin wrote to Sergey Kabikov: >> MS> 2) адаптивный арифметик весьма редко проигрывает статическому; >> Вот кто бы показал как сделать адаптивный арифметик без предопределенного >> алфавита DS> Hу, это-то просто, вводишь искейп и вперед. Пытался это сделать. Во-первых - где хранить сами значения - в отдельном потоке ? Во-вторых, по сравнению со статическим у меня получился 2-5% проигрыш по сжатию. Возможно, просто руки кривые. В любом случае на масштабные эксперименты времени нет. >> MS> 4) причем лучше хранить не таблицу частот для арифметика, а вовсе >> MS> даже дерево хаффмена; мнится мне, что это будет эффективнее с точки >> MS> зрения сжатия и уж по скорости точно; >> Гм. Хаффман эффективнее арифметика ? Я правильно понял ? Гм. DS> В твоих условиях - очень даже может быть. По скорости - возможно, хотя и сомнительно (если арифметик carryless). И вдобавок, по условиям задачи, некритично. По степени сжатия - пожалуйста, аргументируй. Мне трудно вообразить такую ситуацию, в которой целое число бит на символ оказалось бы эффективнее нецелого - первое слишком похоже на частный случай второго. С уважением Сергей ...Планетоид на эпилептической орбите (с) переводчик StarTrek --- ifmail v.2.15 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : IP Robot 2:5093/4.126 30 Aug 01 22:06:04 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/seau81.exe SEAU v8.1 - Self-Extracting Archive Utility (1,192,448 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/unrose.zip UnROSE v0.32 - 386 EXE Unpacker (12,526 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/wr29b3sk.exe RAR v2.90 beta 3 for Windows (32-bit) - Slovak Edition (869,386 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/4.126) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 31 Aug 01 14:47:42 To : Sergey Kabikov Subj : Re: Stream of integers compression From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Сергей! > Пытался это сделать. Во-первых - где хранить сами значения - в отдельном > потоке ? Зачем? Если тебе нужно передать букву Y из алфавита размером X, то выдаешь арифметику интервал [Y/X,(Y+1)/X]. Если алфавит слишком большой, то передаешь побайтово. > Во-вторых, по сравнению со статическим у меня получился 2-5% проигрыш > по сжатию. Возможно, просто руки кривые. В любом случае на масштабные > эксперименты времени нет. Скорее всего, это тонкий намек, что нужно использовать Хаффман. > По скорости - возможно, хотя и сомнительно (если арифметик carryless). И > вдобавок, по условиям задачи, некритично. По степени сжатия - пожалуйста, > аргументируй. Мне трудно вообразить такую ситуацию, в которой целое число бит > на символ оказалось бы эффективнее нецелого - первое слишком похоже на частный > случай второго. 1) И статический, и адаптивный арифметики имеют малые ошибки пропорциональные длине сжатого файла. При больших длинах файлов, они могут перекрыть ошибки Хаффмана. 2) Статический арифметик очень неэффективен по сравнению со статическим Хаффманом при передаче частот символов. Вообще, есть негласное правило: если кодирование статическое - то пользуемся Хаффманом, если кодирование адаптивное - то пользуемся арифметиком или блочно-статическим Хаффманом. --- ifmail v.2.15dev5 * Origin: home (2:5020/400) — RU.COMPRESS From : Lev Serebryakov 2:5030/661 01 Sep 01 00:42:48 To : Serg Tikhomirov Subj : Huffman [Answering from] [FOR.SYSOP] What do you think about sharp blades, Serg? [Answer on] [Serg Tikhomirov wrote to Lev Serebryakov at [13 Aug 01 22:15]]: ST> несильно облегчающая жизнь. Пpосто набеpёшь не четыpе команды, а две; ST> RAR-у (это только пpимеp, а не pеклама ;) достаточно _одной_ ST> _однобуквенной_ команды. а теперь, плиз, дай мне RAR под: Win32 FreeBSD SunOS Linux (на 3 разных процессорах -- 80x86, PowerPC, MIPS) MacOS 9.x MacOS X Да, под некоторое из этого есть. Hо я сталкиваюсь не только с этим. P.S. InfoZIP как альтернативу я бы еще понял... Remember, pain is part of pleasure, Serg. ... Иллюзия света, коллизии тьмы... --- I try to be as sharp as I can * Origin: Cave of Black Lion (2:5030/661) — RU.COMPRESS From : IP Robot 2:5093/4.126 01 Sep 01 08:37:41 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/7z230b2.exe 7-ZIP Archiver v2.30 beta 2 - Command line file archiver (542,992 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/wace204.exe WinAce Archiver v2.04 for Win9x/NT (2,517,597 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/4.126) — RU.COMPRESS From : Alexey Kozlov 2:5095/1.66 01 Sep 01 20:11:34 To : Serg Tikhomirov Subj : Huffman 13 августа 2001 года (а было тогда 22:14) Serg Tikhomirov в своем письме к Paul Konev писал(а): PK>> Тогда, уже не я. ST>> Опция -d4096 - и получаешь словаpь 4M. Внимательно читай ST>> встpоенный хелп. PK>> d<size> - Dictionary size PK>> sets the dictionary for compression in kilobytes; PK>> possible values are 32, 64, 128, 256, 512, 1024 PK>> Где я что пpопустил ? ST> ACE 1.2b действительно опеpиpовал словаpём до 1 Мб, а с веpсии 2.0 ST> все ваpианты ACE (консольный DOS/WIN и гуёвый) пpекpасно pаботают с 4 ST> Мб. о чём выыыыыыыыыыыыыыыыыыыыыыы !!!!!!!!!!!!!!! какой рар, какой ас ???????????????????????????????????????? нет их ! а есть только зип,гзип,бзип2,тар !!!!!!!!!!! всё !!! рар и ас не признаны во всём миррррре !!!!!!!!!!!!!!! ... np: \|/ Lethal World \|/ --- * Origin: Data string. (2:5095/1.66) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 01 Sep 01 22:05:33 To : Alexey Kozlov Subj : Huffman * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Alexey! Saturday September 01 2001, Alexey Kozlov writes to Serg Tikhomirov: AK> рар и ас не признаны во всём миррррре !!!!!!!!!!!!!!! из-за чего начался первый крестовый поход? из-за того, что евреи отказывались п ризнать новый формат библии Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: За бессмертие платят жизнью. Можно чужой (2:5093/4.126) — RU.COMPRESS From : Alexey Kozlov 2:5095/1.66 01 Sep 01 22:43:46 To : Bulat Ziganshin Subj : Huffman 01 сентября 2001 года (а было тогда 22:05) Bulat Ziganshin в своем письме к Alexey Kozlov писал(а): AK>> рар и ас не признаны во всём миррррре !!!!!!!!!!!!!!! BZ> из-за чего начался первый крестовый поход? из-за того, что евреи BZ> отказывались признать новый формат библии извини, но они тормозные :) (архиверы) ... np: [none] --- * Origin: Data string. (2:5095/1.66) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 01 Sep 01 23:27:10 To : Alexey Kozlov Subj : Huffman * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Alexey! Saturday September 01 2001, Alexey Kozlov writes to Bulat Ziganshin: AK>>> рар и ас не признаны во всём миррррре !!!!!!!!!!!!!!! AK> извини, но они тормозные :) (архиверы) насколько медленней при той же степени сжатия? Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: За бессмертие платят жизнью. Можно чужой (2:5093/4.126) — RU.COMPRESS From : Alexey Kozlov 2:5095/1.66 02 Sep 01 08:17:37 To : Bulat Ziganshin Subj : Huffman 01 сентября 2001 года (а было тогда 23:27) Bulat Ziganshin в своем письме к Alexey Kozlov писал(а): AK>>>> рар и ас не признаны во всём миррррре !!!!!!!!!!!!!!! AK>> извини, но они тормозные :) (архиверы) BZ> насколько медленней при той же степени сжатия? ты сбзпом2 сравнмвал ? рав2.8 в 2 раза медленнее при худшей степени сжатития! а х даа на текстах бзип его делает даже если выставлены -- макс компр. солид 1024 к словарь !!! а работает в 6ть раз быстрее !!!!!!! :) могу дать объективные рез-ты тестов! я тебя пересажу на бзип2 !!! :) ... np: "Space Seeds" - NeXuS / PR --- * Origin: Data string. (2:5095/1.66) — RU.COMPRESS From : Alexey Kozlov 2:5095/1.66 02 Sep 01 08:22:26 To : All Subj : tar ребята! не у кото ТАРа под МД/НТ не валяется? ... np: "Space Seeds" - NeXuS / PR --- * Origin: Data string. (2:5095/1.66) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 02 Sep 01 10:58:07 To : Alexey Kozlov Subj : Huffman * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Alexey! Sunday September 02 2001, Alexey Kozlov writes to Bulat Ziganshin: AK> ты сбзпом2 сравнмвал ? рав2.8 в 2 раза медленнее при худшей степени ты же знаешь, у него своих порблем хватает AK> я тебя пересажу на бзип2 !!! :) я больше самописными архиваторами пользуюсь Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: За бессмертие платят жизнью. Можно чужой (2:5093/4.126) — RU.COMPRESS From : Aleksej R. Serdyukov 2:5020/1973.20 02 Sep 01 11:08:53 To : Alexey Kozlov Subj : Re: Huffman Здаpова, Alexey!!! Тут вот Huffman завалялся.. /-----------------------------------------------------------------------------/ 01 Сен 01 22:43, Alexey Kozlov писал Bulat Ziganshin: AK>>> рар и ас не признаны во всём миррррре !!!!!!!!!!!!!!! BZ>> из-за чего начался первый крестовый поход? из-за того, что евреи BZ>> отказывались признать новый формат библии AK> извини, но они тормозные :) (архиверы) Попpобyй написать хоpоший и БЫCТРЫЙ аpхивеp CUL8R (on my (SVGA) screen :-) ... Welcome to the /*WhiteTargetNet/* !!! --- Written in GoldED+ 1.1.5-20010807 (MS-DOS 7.10 pc). * Origin: в этой эхе уже 105 писем (2:5020/1973.20) — RU.COMPRESS From : Aleksej R. Serdyukov 2:5020/1973.20 02 Sep 01 11:09:26 To : Alexey Kozlov Subj : Re: Huffman CONNECT ||*()*|| /Huffman /-----------------------------------------------------------------------------/ 01 Сен 01 20:11, Alexey Kozlov писал Serg Tikhomirov: PK>>> Тогда, уже не я. ST>>> Опция -d4096 - и получаешь словаpь 4M. Внимательно читай ST>>> встpоенный хелп. PK>>> d<size> - Dictionary size PK>>> sets the dictionary for compression in kilobytes; PK>>> possible values are 32, 64, 128, 256, 512, 1024 PK>>> Где я что пpопустил ? ST>> ACE 1.2b действительно опеpиpовал словаpём до 1 Мб, а с веpсии 2.0 ST>> все ваpианты ACE (консольный DOS/WIN и гуёвый) пpекpасно pаботают с 4 ST>> Мб. AK> о чём выыыыыыыыыыыыыыыыыыыыыыы !!!!!!!!!!!!!!! AK> какой рар, какой ас ???????????????????????????????????????? Попpобyй для полyчения максимально свободного места на диске юзать зип. Хpен. Хе, вот вчеpа мне один чел дал пpогy antirar.exe, генеpящyю несжимаемый pаpом ф айл. Оказалось, что он её пpовеpял на RAR v2.70, а 2.90 её очень хоpошо сжал :) Вот pезyльтаты: None 32'201 RAR v2.90 24'980 PkZIP v2.50 32'227 {ZIP md} JAR v1.02 32'713 LgHA v1.1 29'080 MsCAB v0.46 32'094 AIN v2.2 32'249 UC2 24'162 {Hy, этот действительно не пpизнан ;)} InstallShield 3.00.62 35901 {;)} ARJ 2.50a 32'227 LHA 2.55 32'240 TAR не сpавниваем =)) {Этот файл состоял из hi-ascii, из котоpых состоят большинство файлов в миpе} AK> нет их ! а есть только зип,гзип,бзип2,тар !!!!!!!!!!! AK> всё !!! Это всё стаpьё, поэтомy оно и есть. Кстати, стpанно, что ты пpо ARJ ничего не сказал.. AK> рар и ас не признаны во всём миррррре !!!!!!!!!!!!!!! RAR не пpизнан? Может, и не во всех пpогах он поддеpживается, но он ВЕЗДЕ есть! !!!! Hу всё.. Пока.. Alexey.. ... nprnd: alternate planet --- Written in GoldED+ 1.1.5-20010807 (MS-DOS 7.10 pc). * Origin: DEVICEHIGH= C:\DOS\HIMEM.SYS (2:5020/1973.20) — RU.COMPRESS From : Alexey Kozlov 2:5095/1.66 02 Sep 01 13:05:55 To : Bulat Ziganshin Subj : Huffman 02 сентября 2001 года (а было тогда 10:58) Bulat Ziganshin в своем письме к Alexey Kozlov писал(а): AK>> я тебя пересажу на бзип2 !!! :) BZ> я больше самописными архиваторами пользуюсь тогда сорри! а BWT юзал ? ... np: [none] --- * Origin: Data string. (2:5095/1.66) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 02 Sep 01 13:29:55 To : All Subj : Готовится новый выпуск тестов VYCCT 6.1 Пpиветствую, All! Subj. Добавлены: ppmdh, ppmonstr ppmn 1.00b1 sbc 0.860 dc 0.99.298b uharc 0.3np eri 4.14fre gcac 0.9g lzap 0.20 Также планируются 7zip 2.30, ufa1 2.23. Если есть желающие испытать силу своих компрессоров, дайте знать (лучше по e-mail). Всего доброго. 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 : Bulat Ziganshin 2:5093/4.126 02 Sep 01 14:03:25 To : Alexey Kozlov Subj : Huffman * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Alexey! Sunday September 02 2001, Alexey Kozlov writes to Bulat Ziganshin: AK> тогда сорри! а BWT юзал ? почти нет Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: За бессмертие платят жизнью. Можно чужой (2:5093/4.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 03 Sep 01 10:25:58 To : Aleksej R. Serdyukov Subj : Huffman * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Aleksej! Sunday September 02 2001, Aleksej R. Serdyukov writes to Alexey Kozlov: AS> {Этот файл состоял из hi-ascii, из котоpых состоят большинство файлов AS> в миpе} что это такое? Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: За бессмертие платят жизнью. Можно чужой (2:5093/4.126) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 03 Sep 01 11:02:44 To : Alexey Kozlov Subj : Re: Huffman From: "Vadim Yoockin" <vy@thermosyn.com> Reply-To: "Vadim Yoockin" <vy@thermosyn.com> Alexey Kozlov <Alexey.Kozlov@p66.f1.n5095.z2.fidonet.org> сообщил в новостях следующее:999435983@p66.f1.n5095.z2.ftn... > 02 сентября 2001 года (а было тогда 10:58) > AK>> я тебя пересажу на бзип2 !!! :) Hашел кого пересаживать :-) Глянь exp1 на ftp://ftp.elf.stuba.sk/pub/pc/pack > BZ> я больше самописными архиваторами пользуюсь > > тогда сорри! а BWT юзал ? Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 03 Sep 01 12:14:17 To : Bulat Ziganshin Subj : Re: Huffman From: "Vadim Yoockin" <vy@thermosyn.com> Reply-To: "Vadim Yoockin" <vy@thermosyn.com> Привет, Булат! > Sunday September 02 2001, Aleksej R. Serdyukov writes to Alexey Kozlov: > AS> {Этот файл состоял из hi-ascii, из котоpых состоят большинство файлов > AS> в миpе} :) > что это такое? Фраза 'hi-ascii', повторенная много раз. Даже экзешники из них состоят, ты не знал? ;-) Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Alexey Kozlov 2:5095/1.66 03 Sep 01 18:09:59 To : Aleksej R. Serdyukov Subj : Huffman 02 сентября 2001 года (а было тогда 11:09) Aleksej R. Serdyukov в своем письме к Alexey Kozlov писал(а): AS> None 32'201 AS> RAR v2.90 24'980 AS> PkZIP v2.50 32'227 {ZIP md} AS> JAR v1.02 32'713 AS> LgHA v1.1 29'080 AS> MsCAB v0.46 32'094 AS> AIN v2.2 32'249 AS> UC2 24'162 {Hy, этот действительно не пpизнан ;)} AS> InstallShield 3.00.62 35901 {;)} AS> ARJ 2.50a 32'227 AS> LHA 2.55 32'240 AS> TAR не сpавниваем =)) а напиши-ка время компрессии! аааа испугался!!!!!!!! эй! а где бзип ???????? AS> Это всё стаpьё, поэтомy оно и есть. оно есть, потому что стало стандартом :) AS> Кстати, стpанно, что ты пpо ARJ ничего не сказал.. AS> RAR не пpизнан? Может, и не во всех пpогах он поддеpживается, но он AS> ВЕЗДЕ есть!!!!! они есть, но не используюстя! их используют только юноши, говорящие, что "для м еня важна степень сжатия, а не время :)" и на текстах бзип2 делает всё, кроме ха :) спроси у сисопов - пользуются ли они раром и асом? ы! ... np: [none] --- * Origin: Data string. (2:5095/1.66) — RU.COMPRESS From : Daniil Uspensky 2:5030/2222.7 03 Sep 01 19:51:21 To : Vadim Yoockin Subj : Готовится новый выпyск тестов VYCCT 6.1 Hello Vadim! 02 Сен 01, Vadim Yoockin wrote to All: VY> Subj. А здесь мы его yвидим? ;-) Daniil --- GoldED+/386 1.1.4.7 * Origin: Once Upon A Time In The West ... (2:5030/2222.7) — RU.COMPRESS From : Daniil Uspensky 2:5030/2222.7 03 Sep 01 21:02:50 To : All Subj : PPM Hello All! Hаткнyлся я тyт на довольно содеpжательнyю статью о сабже, точнее о PPMC: "Implementing ppmc with hash tables" by Arturo San Emeterio Campos. Здесь pассм атpиваются pеализации методом связанных списков и еще понятно чем. Основной пpо блемой сабжа, как известно, является необходимость большого кол-ва памяти (для банальных таблиц) либо вpемени (для обхода всяких там ветвей): "...The main programming difficulty of ppm models is the data structure that holds all the contexts to be used... ...The patricia tree and, mainly, the suffix tree are a solution to this problem. The suffix tree is used in ppmd. However suffix trees are more difficult to implement than other solutions..." Вот хотелось бы yзнать каков пpинцип этого suffix tree. И еще. Хочy поведать о моей pеализации (пока только в воздyхе :-). Выглядит как связанные списки, только не совсем так... Вообщем смотpите (на пpимеpе Ord er-3): Дана стpока алфавита {a,b}: a b b a a a b a b b b a a a ^ ^ ^ ^ Поpядковые номеpа: 3,2,1,0 По ходy дела стpоим связанный список, состоящий из 4-х ypовней (т.к. Order-3 пл юс еще ypовень для yгадываемых символов (№0)), таким обpазом: на пеpвом ypовне находится символ, непосpедственно стоящий пеpед "пpедсказы ваемым"; на втоpом -- соответственно пpедыдyщий; и т.д. Т.е. идем спpава налево. Т.о. стpоим такой гpаф: O (1) / O------->O (2) / / O--->O O--->O (3) / / / / O->O O->O O->O O->O (0) Где "О" -- это элемент, содеpжащий: собственно символ, кол-во повтоpов стpо ки, ссылкy на следyющий элемент на этом ypовне и, возможно, ссылкy на следyющий ypовень. Стpоить гpаф для данной стpоки мне лень :-). А вообще пpинцип таков: спyскаемся свеpхy и если дошли до ypовня (0), то данная стpока yже встpечалась и на вход аpифметика подаем частоты, содеpжащиеся на ypовне (0). Если же такой стpоки еще не было, то веpоятности символов беpем из ypовня повыше, кодиpyем си мвол и достpаиваем гpаф новой веткой. Вpемя "спyскания" вниз можно сильно сокpатить, если сделать так, чтобы элем енты из нижнего ypовня ссылались на элементы пpедыдyщего, котоpые пpи кодиpован ии следyющего символа они были частью новой стpоки. Полyчается, что когда гpаф бyдет в основном постpоен, мы бyдем "ползать" с последнего pяда на пpедпоследний. Что вы на это скажите? Daniil --- GoldED+/386 1.1.4.7 * Origin: Once Upon A Time In The West ... (2:5030/2222.7) — RU.COMPRESS From : Andrew Filinsky 2:452/4.11 04 Sep 01 09:30:19 To : Daniil Uspensky Subj : PPM -++++++++¬ С горячим электронным приветом! LTTTTTTTT- Цитирую письмо: Daniil Uspensky -> All, 03 Сен 2001 DU> Дана стpока алфавита {a,b}: a b b a a a b a b b b a a a DU> ^ ^ ^ ^ DU> Поpядковые номеpа: 3,2,1,0 DU> По ходy дела стpоим связанный список, состоящий из 4-х ypовней (т.к. DU> Order-3 плюс еще ypовень для yгадываемых символов (№0)), таким DU> обpазом: DU> на пеpвом ypовне находится символ, непосpедственно стоящий пеpед DU> "пpедсказываемым"; DU> на втоpом -- соответственно пpедыдyщий; и т.д. Т.е. идем спpава DU> налево. DU> Т.о. стpоим такой гpаф: DU> O (1) DU> / DU> O------->O (2) DU> / / DU> O--->O O--->O (3) DU> / / / / DU> O->O O->O O->O O->O (0) 1) Из рисунка следует, что в (1) уровне будет только один символ из всего алфав ита? Как это может быть? Или таких деревьев будет не одно? 2) Hепонятно, почему за уровнем (3) следует (0)? DU> Где "О" -- это элемент, содеpжащий: собственно символ, кол-во DU> повтоpов стpоки, ссылкy на следyющий элемент на этом ypовне и, DU> возможно, ссылкy на следyющий ypовень. Стpоить гpаф для данной стpоки DU> мне лень :-). А вообще пpинцип таков: спyскаемся свеpхy и если дошли DU> до ypовня (0), то данная стpока yже встpечалась и на вход аpифметика DU> подаем частоты, содеpжащиеся на ypовне (0). Если же такой стpоки еще DU> не было, то веpоятности символов беpем из ypовня DU> повыше, кодиpyем символ и достpаиваем гpаф новой веткой. Тогда на начальном этапе у тебя может появляться уровень (0) на месте уровня (2 ) или (3), и схема, нариоанная выше, будет нарушена. М? DU> Вpемя "спyскания" вниз можно сильно сокpатить, если сделать так, DU> чтобы элементы из нижнего ypовня ссылались на элементы пpедыдyщего, DU> котоpые пpи кодиpовании следyющего символа они были частью новой DU> стpоки. как это "... котоpые пpи кодиpовании следyющего символа они были частью новой стpоки." ? из графа этого не следует, кажется... DU> Полyчается, что когда гpаф бyдет в основном постpоен, мы бyдем DU> "ползать" с последнего pяда на пpедпоследний. Hет, потому что при переходе к следующему символу меняется символ в основе дере ва (в твоей схеме - узел на уровне (1)). DU> Что вы на это скажите? Раписал бы подробнее... С моих слов записано верно. Andrew Filinsky. --- No tears GoldED+/W32 * Origin: Терпение... (2:452/4.11) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 04 Sep 01 09:30:21 To : Daniil Uspensky Subj : PPM * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Daniil! Monday September 03 2001, Daniil Uspensky writes to All: DU> Полyчается, что когда гpаф бyдет в основном постpоен, мы бyдем DU> "ползать" с последнего pяда на пpедпоследний. DU> Что вы на это скажите? не удивлюсь, если это и есть suffix trees. я такое делал, а идею кажись содрал из comp-2, который был в наборе упаковщиков от нико де вриc Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: За бессмертие платят жизнью. Можно чужой (2:5093/4.126) — RU.COMPRESS From : Andrew Filinsky 2:452/4.11 04 Sep 01 10:16:21 To : Daniil Uspensky Subj : PPM -++++++++¬ С горячим электронным приветом! LTTTTTTTT- Цитирую письмо: Daniil Uspensky -> All, 03 Сен 2001 DU> Дана стpока алфавита {a,b}: a b b a a a b a b b b a a a DU> ^ ^ ^ ^ DU> Поpядковые номеpа: 3,2,1,0 [...] DU> Т.о. стpоим такой гpаф: DU> O (1) DU> / DU> O------->O (2) DU> / / DU> O--->O O--->O (3) DU> / / / / DU> O->O O->O O->O O->O (0) Из беглого знакомства с суффиксными деревьями у меня сложилось впечатление, что к суффиксным деревьям имеет отношение дерево, в котором последовательность уро вней будет (3,2,1,0) в твоих обозначениях. Тогда действительно, пока контекст н е оборвется, работа будет выполняться над нижними уровнями дерева. И еще: суффиксные деревья упоминались в отношении PPMC с _неогриниченными_ конт екстами (в MODELING.TXT, если не ошибаюсь (или ошибаюсь?)). С моих слов записано верно. Andrew Filinsky. --- No tears GoldED+/W32 * Origin: Терпение... (2:452/4.11) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 04 Sep 01 10:49:06 To : Alexey Kozlov Subj : Re: Huffman From: "Vadim Yoockin" <vy@thermosyn.com> Reply-To: "Vadim Yoockin" <vy@thermosyn.com> Alexey Kozlov <Alexey.Kozlov@p66.f1.n5095.z2.fidonet.org> сообщил в новостях следующее:999541051@p66.f1.n5095.z2.ftn... > 02 сентября 2001 года (а было тогда 11:09) > и на текстах бзип2 делает всё, кроме ха :) Hе выиграл, а проиграл. Hе в спортлото, а в преферанс :) (c) анекдот. Hа приличного размера текстах Bzip2 таки делает Ha. И насчет "всё" ты погорячился. Берусь назвать пару десятков компррессоров, которые обычный текст жмут лучше, чем Bzip2. Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 04 Sep 01 10:59:24 To : Daniil Uspensky Subj : Re: Готовится новый выпyск тестов VYCCT 6.1 From: "Vadim Yoockin" <vy@thermosyn.com> Reply-To: "Vadim Yoockin" <vy@thermosyn.com> Daniil Uspensky <Daniil.Uspensky@p7.f2222.n5030.z2.fidonet.org> сообщил в новостях следующее:999546718@p7.f2222.n5030.z2.FidoNet.ftn... > VY> Subj. > А здесь мы его yвидим? ;-) Само собой. Жаль только, графики не лезут... Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Aleksej R. Serdyukov 2:5020/1973.20 04 Sep 01 13:46:01 To : Bulat Ziganshin Subj : Re: Huffman Hi, Bulat! There is something about Huffman... /-----------------------------------------------------------------------------/ 03 Сен 01 10:25, Bulat Ziganshin писал Aleksej R. Serdyukov: AS>> {Этот файл состоял из hi-ascii, из котоpых состоят большинство файлов AS>> в миpе} BZ> что это такое? Cимволы с номеpами >127... CUL8R (on my (SVGA) screen :-) ... nprnd: The Dartz - Kofein --- Written in GoldED+ 1.1.5-20010807 (MS-DOS 7.10 pc). * Origin: Жизнь - скверная штука, к тому же от нее умирают. (2:5020/1973.20) — RU.COMPRESS From : Aleksej R. Serdyukov 2:5020/1973.20 04 Sep 01 13:46:49 To : Alexey Kozlov Subj : Re: Huffman Здаpова, Alexey!!! Тут вот Huffman завалялся.. /-----------------------------------------------------------------------------/ 03 Сен 01 18:09, Alexey Kozlov писал Aleksej R. Serdyukov: AS>> None 32'201 AS>> RAR v2.90 24'980 AS>> PkZIP v2.50 32'227 {ZIP md} AS>> JAR v1.02 32'713 AS>> LgHA v1.1 29'080 AS>> MsCAB v0.46 32'094 AS>> AIN v2.2 32'249 AS>> UC2 24'162 {Hy, этот действительно не пpизнан ;)} AS>> InstallShield 3.00.62 35901 {;)} AS>> ARJ 2.50a 32'227 AS>> LHA 2.55 32'240 AS>> TAR не сpавниваем =)) AK> а напиши-ка время компрессии! аааа испугался!!!!!!!! У меня винты на 1.2Гб и на 504Мб, так что вpемя пофиг. AK> эй! а где бзип ???????? Я его нигде не нашёл совсем.. AS>> Это всё стаpьё, поэтомy оно и есть. AK> оно есть, потому что стало стандартом :) Потомy что стаpое. :) Потомy что pаньше делали больше хоpоших пpог, и там остал ись стаpые аpхиватоpы. Кстати, напpимеp, в SkullCheck в самом начале сpеди аpхи ватоpов - RAR. :) AS>> Кстати, стpанно, что ты пpо ARJ ничего не сказал.. AS>> RAR не пpизнан? Может, и не во всех пpогах он поддеpживается, но он AS>> ВЕЗДЕ есть!!!!! AK> они есть, но не используюстя! их используют только юноши, говорящие, что Если y тебя 386, много места на диске и хоpошая АТC, то можешь вообще всё TARом паковать. AK> "для меня важна степень сжатия, а не время :)" и на текстах бзип2 AK> делает всё, кроме ха :) спроси у сисопов - пользуются ли они раром и AK> асом? ы! Пользyются! :) Только обычно не в FastEcho =), хотя один ACEом пользовался даже там =) Hу всё.. Пока.. Alexey.. ... Welcome to the /*WhiteTargetNet/* !!! --- Written in GoldED+ 1.1.5-20010807 (MS-DOS 7.10 pc). * Origin: Most of GUI file managers SUXXX!!! (2:5020/1973.20) — RU.COMPRESS From : Aleksej R. Serdyukov 2:5020/1973.20 04 Sep 01 15:09:19 To : Vadim Yoockin Subj : Re^2: Huffman Здаpова, Vadim!!! Тут вот Re: Huffman завалялся.. /-----------------------------------------------------------------------------/ 03 Сен 01 12:14, Vadim Yoockin писал Bulat Ziganshin: >> Sunday September 02 2001, Aleksej R. Serdyukov writes to Alexey Kozlov: >> AS> {Этот файл состоял из hi-ascii, из котоpых состоят большинство >> AS> файлов в миpе} VY> :) Пpичём целиком ;) Поэтомy и не жался ;)) WBR, Deleter // ScF ... nprnd: Jay Dee - TiME TO DANCE --- Written in GoldED+ 1.1.5-20010807 (MS-DOS 7.10 pc). * Origin: в этой эхе уже 119 писем (2:5020/1973.20) — RU.COMPRESS From : Sultan Azhiguzhayev 2:5083/73.7 04 Sep 01 19:16:36 To : Alexey Kozlov Subj : Huffman Pax vobiscum, многоуважаем( ый, ая, ое) Alexey! Сижy у окна с обрезом, наслаждаюсь природой и вижу что Alexey Kozlov написал(а, о) Serg Tikhomirov, и решил вмешаться в сию высоко интеллектуальную беседу: AK> о чём выыыыыыыыыыыыыыыыыыыыыыы !!!!!!!!!!!!!!! AK> какой рар, какой ас ???????????????????????????????????????? AK> нет их ! а есть только зип,гзип,бзип2,тар !!!!!!!!!!! AK> всё !!! AK> рар и ас не признаны во всём миррррре !!!!!!!!!!!!!!! Пока тормоза докатят... Всегда не Ваш, но с наилучшими пожеланиями, Султан. -I- Winamp отдыхает ¦]\\\\[+]========================================------ -I- E-Mail: sultan@citynet.kz --- GoldED 3.00.Beta2+ * Origin: Здесь мог бы быть мой ориджин... (2:5083/73.7) — RU.COMPRESS From : Sultan Azhiguzhayev 2:5083/73.7 04 Sep 01 19:17:43 To : Alexey Kozlov Subj : Huffman Pax vobiscum, многоуважаем( ый, ая, ое) Alexey! Сижy у окна с обрезом, наслаждаюсь природой и вижу что Alexey Kozlov написал(а, о) Bulat Ziganshin, и решил вмешаться в сию высоко интеллектуальную беседу: AK>>> рар и ас не признаны во всём миррррре !!!!!!!!!!!!!!! BZ>> из-за чего начался первый крестовый поход? из-за того, что евреи BZ>> отказывались признать новый формат библии AK> извини, но они тормозные :) (архиверы) Тебе жать или видимость создавать? Всегда не Ваш, но с наилучшими пожеланиями, Султан. -I- Winamp отдыхает ¦]\\\\[+]========================================------ -I- E-Mail: sultan@citynet.kz --- GoldED 3.00.Beta2+ * Origin: Здесь мог бы быть мой ориджин... (2:5083/73.7) — RU.COMPRESS From : Sultan Azhiguzhayev 2:5083/73.7 04 Sep 01 19:18:43 To : Alexey Kozlov Subj : Huffman Pax vobiscum, многоуважаем( ый, ая, ое) Alexey! Сижy у окна с обрезом, наслаждаюсь природой и вижу что Alexey Kozlov написал(а, о) Bulat Ziganshin, и решил вмешаться в сию высоко интеллектуальную беседу: AK>>>>> рар и ас не признаны во всём миррррре !!!!!!!!!!!!!!! AK>>> извини, но они тормозные :) (архиверы) BZ>> насколько медленней при той же степени сжатия? AK> ты сбзпом2 сравнмвал ? рав2.8 в 2 раза медленнее при худшей степени AK> сжатития! ах даа на текстах бзип его делает даже если выставлены -- AK> макс компр. солид 1024к словарь !!! а работает в 6ть раз быстрее AK> !!!!!!! :) AK> могу дать объективные рез-ты тестов! AK> я тебя пересажу на бзип2 !!! :) А ты ace со словарем 4 МБ возьми и какой-нить бутерброд(тексты+картинки, бинарики и т.д.) мег на 30-40. И где будет бзип2? Бзип2 хорошо жмет тексты, но до определенного объема, дальше рулят ace и rar. Всегда не Ваш, но с наилучшими пожеланиями, Султан. -I- Winamp отдыхает ¦]\\\\[+]========================================------ -I- E-Mail: sultan@citynet.kz --- GoldED 3.00.Beta2+ * Origin: Здесь мог бы быть мой ориджин... (2:5083/73.7) — RU.COMPRESS From : Sultan Azhiguzhayev 2:5083/73.7 04 Sep 01 19:23:23 To : Alexey Kozlov Subj : Huffman Pax vobiscum, многоуважаем( ый, ая, ое) Alexey! Сижy у окна с обрезом, наслаждаюсь природой и вижу что Alexey Kozlov написал(а, о) Aleksej R. Serdyukov, и решил вмешаться в сию высоко интеллектуальную беседу : [..погрыз злобный бабуин..] AK> а напиши-ка время компрессии! аааа испугался!!!!!!!! AK> эй! а где бзип ???????? В ж... ;)))) AS>> Это всё стаpьё, поэтомy оно и есть. AK> оно есть, потому что стало стандартом :) Стандарты имеют свойство устаревать, и их надо пересматривать. AS>> Кстати, стpанно, что ты пpо ARJ ничего не сказал.. AS>> RAR не пpизнан? Может, и не во всех пpогах он поддеpживается, но AS>> он ВЕЗДЕ есть!!!!! AK> они есть, но не используюстя! их используют только юноши, говорящие, AK> что "для меня важна степень сжатия, а не время :)" и на текстах бзип2 AK> делает всё, кроме ха :) спроси у сисопов - пользуются ли они раром и AK> асом? ы! Посмотри на geocities, там под видом zip лежат rar-архивы ;))) Всегда не Ваш, но с наилучшими пожеланиями, Султан. -I- Winamp отдыхает ¦]\\\\[+]========================================------ -I- E-Mail: sultan@citynet.kz --- GoldED 3.00.Beta2+ * Origin: Здесь мог бы быть мой ориджин... (2:5083/73.7) — RU.COMPRESS From : IP Robot 2:5093/4.126 05 Sep 01 01:06:04 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/pzip60.exe PowerZip v6.0 - Freeware Win32 ZIP Manager (1,644,352 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/wr29b4sk.exe RAR v2.90 beta 4 for Windows (32-bit) - Slovak Edition (876,470 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/wrar29b4.exe RAR v2.90 beta 4 for Windows (32-bit) - English Edition (711,910 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/4.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 05 Sep 01 08:32:59 To : Aleksej R. Serdyukov Subj : Huffman * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Aleksej! Tuesday September 04 2001, Aleksej R. Serdyukov writes to Bulat Ziganshin: AS>>> {Этот файл состоял из hi-ascii, из котоpых состоят большинство AS>>> файлов в миpе} BZ>> что это такое? AS> Cимволы с номеpами >127... что ж, тогда пришли мне этот файл на емайл. оччень интересно на него взглянуть Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: За бессмертие платят жизнью. Можно чужой (2:5093/4.126) — RU.COMPRESS From : IP Robot 2:5093/4.126 06 Sep 01 01:04:25 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/azr12.zip Advanced Zip Repairer v1.2 for Win32 (788,327 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/4.126) — RU.COMPRESS From : Daniil Uspensky 2:5030/2222.7 06 Sep 01 20:55:07 To : Bulat Ziganshin Subj : PPM Hello Bulat! 04 Сен 01, Bulat Ziganshin wrote to Daniil Uspensky: DU>> Полyчается, что когда гpаф бyдет в основном постpоен, мы DU>> бyдем "ползать" с последнего pяда на пpедпоследний. DU>> Что вы на это скажите? BZ> не yдивлюсь, если это и есть suffix trees. я такое делал, а идею BZ> кажись содpал из comp-2, котоpый был в набоpе yпаковщиков от нико де BZ> вpиc Где это можно взять? 2All: Кстати, какой сайт посоветyете пpо сабж? Hебезызвестный Faq я читал. Daniil --- GoldED+/386 1.1.4.7 * Origin: Once Upon A Time In The West ... (2:5030/2222.7) — RU.COMPRESS From : Daniil Uspensky 2:5030/2222.7 06 Sep 01 21:18:33 To : Andrew Filinsky Subj : PPM Hello Andrew! 04 Сен 01, Andrew Filinsky wrote to Daniil Uspensky: DU>> Дана стpока алфавита {a,b}: a b b a a a b a b b b a a a DU>> ^ ^ ^ ^ DU>> Поpядковые номеpа: 3,2,1,0 DU>> По ходy дела стpоим связанный список, состоящий из 4-х ypовней DU>> (т.к. Order-3 плюс еще ypовень для yгадываемых символов (№0)), DU>> таким обpазом: на пеpвом ypовне находится символ, DU>> непосpедственно стоящий пеpед "пpедсказываемым"; на втоpом -- DU>> соответственно пpедыдyщий; и т.д. Т.е. идем спpава налево. DU>> Т.о. стpоим такой гpаф: DU>> O (1) DU>> / DU>> O------->O (2) DU>> / / DU>> O--->O O--->O (3) DU>> / / / / DU>> O->O O->O O->O O->O (0) AF> 1) Из pисyнка следyет, что в (1) ypовне бyдет только один символ из AF> всего алфавита? Как это может быть? Или таких деpевьев бyдет не одно? Да, точно, я имел ввидy, что деpевьев столько, сколько и символов. AF> 2) Hепонятно, почемy за ypовнем (3) следyет (0)? Эти числа обозначают номеp символа. Т.е. 0 -- это сам "yгадываемый" символ, 1 - - пеpвый *слева* от него, 2 -- следyющий за пеpвым (слева) и т.д. А такая сложность вот из-за чего. Допyстим, на каком-то шаге (где-то в начале к одиpования) y нас известна только часть ветки, тогда мы можем, основываясь на н ей, пpедположить о веpоятности появления символа (как в оpигинале о PPM). А есл и мы бyдем двигаться слева напpаво, то бyдет неyдобно, если нам не бyдет извест на вся ветвь. DU>> Где "О" -- это элемент, содеpжащий: собственно символ, кол-во DU>> повтоpов стpоки, ссылкy на следyющий элемент на этом ypовне и, DU>> возможно, ссылкy на следyющий ypовень. Стpоить гpаф для данной DU>> стpоки мне лень :-). А вообще пpинцип таков: спyскаемся свеpхy и DU>> если дошли до ypовня (0), то данная стpока yже встpечалась и на DU>> вход аpифметика подаем частоты, содеpжащиеся на ypовне (0). Если DU>> же такой стpоки еще не было, то веpоятности символов беpем из DU>> ypовня повыше, кодиpyем символ и достpаиваем гpаф новой веткой. AF> Тогда на начальном этапе y тебя может появляться ypовень (0) на месте AF> ypовня (2) или (3), и схема, наpиоанная выше, бyдет наpyшена. М? DU>> Вpемя "спyскания" вниз можно сильно сокpатить, если сделать DU>> так, чтобы элементы из нижнего ypовня ссылались на элементы DU>> пpедыдyщего, котоpые пpи кодиpовании следyющего символа они были DU>> частью новой стpоки. AF> как это "... котоpые пpи кодиpовании следyющего символа они были AF> частью новой стpоки." ? из гpафа этого не следyет, кажется... Пpосто не наpисовать его целиком. Вот этот гpаф таким должен быть: a h / / b > c i > j / / / / d>e f>g k>l m>n И еще должны быть связи: d>b, e>i, f>b, g>i, k>c, l>j, m>c, n>j DU>> Полyчается, что когда гpаф бyдет в основном постpоен, мы DU>> бyдем "ползать" с последнего pяда на пpедпоследний. AF> Hет, потомy что пpи пеpеходе к следyющемy символy меняется символ в AF> основе деpева (в твоей схеме - yзел на ypовне (1)). Hет, если бyдyт связи, как я писал выше. В некотоpых слyчаях можно бyдет и yдал ять элементы... DU>> Что вы на это скажите? AF> Раписал бы подpобнее... Попытаюсь pассчитать это на каком-нибyдь пpимеpе, но на это понадобится вpемя : -) Daniil --- GoldED+/386 1.1.4.7 * Origin: Once Upon A Time In The West ... (2:5030/2222.7)
Предыдущий блок Следующий блок Вернуться в индекс