| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Denis Smirnov 2:5020/1785.1 17 Nov 99 02:51:28 To : All Subj : Как сжимать? ---- OS/2 Привет ! Имеется последовательность 32-х битных чисел длиной около 2^20 значений. По вторяющихся последовательностей нет. Числа имеют сильно разную частоту встречае омости. Hасколько я понимаю это надо сжимать либо хаффманом либо арифметическим кодером. Hо как быстро реализовать хаффмана на 32-х битных данных? И как вооб ще реализовать арифметический кодер я вообще не разобрался. С уважением, Denis! --- mailto:mithraen@mtu-net.ru ICQ: 45911752 * Origin: The Magic of Windows: Turns a 486 back into a PC/XT (2:5020/1785.1) — RU.COMPRESS From : Denis Danchenko 2:5020/859.65 17 Nov 99 15:50:08 To : Alesha Skaftymov Subj : LZ77 Hello Alesha! 15 Nov 99 12:14, Alesha Skaftymov wrote to Vladimir Semenjuk: VS>> Бред это (не bred Уилера, а БРЕД = искалеченный LZSS :) ), да и VS>> Л(и)венштейн в умных книжках через "е" пишется. AS> Это возможно. VS>> Булат прав. AS> Это нет, потому, что на третьем символе декодер не сможет однозначно AS> декодировать последовательность 2,2,... Все правильно он сказал, спасибо ему за это. Единственное он привел некорректный пример, потому-что длины начинаются с 3-х. ;) Параллельно вытащил эту доку, где разложено все по полочкам: Deutsch, P., "DEFLATE Compressed Data Format Specification version 1.3", RFC 1951, Aladdin Enterprises, May 1996. ftp://ftp.isi.edu/in-notes/rfc1951.txt AS> Если записать это в двоичном Дело в том, что длина записывается не в двоичном, а по Хаффману. Там в шифровании числа принимают участие от 7 до 9 бит. VS>> Из его примера, правда, не следует, что после кода совпадения в VS>> обязательном порядке идет незакодированный символ. AS> Тут он как раз абсолютно прав, после кода совпадения может идти как AS> незакодированный символ, так и код совпадения. Даю алгоритм(выдержка из вышеприведенной доки) сжатия с использованием кодов Хаффмана: > ¦¦¦ Inserting Windows Clipboard ... do read block header from input stream. if stored with no compression skip any remaining bits in current partially processed byte read LEN and NLEN (see next section) copy LEN bytes of data to output otherwise if compressed with dynamic Huffman codes read representation of code trees (see subsection below) loop (until end of block code recognized) decode literal/length value from input stream if value < 256 copy value (literal byte) to output stream otherwise if value = end of block (256) break from loop otherwise (value = 257..285) decode distance from input stream move backwards distance bytes in the output stream, and copy length bytes from this position to the output stream. end loop while not last block > ¦¦¦ Windows Clipboard succesfully inserted. Denis ... Brains using: -------------------- 15% --- :~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~( * Origin: ¦ Alhademic Group ¦ http://www.alhademic.com ¦ (2:5020/859.65) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 17 Nov 99 22:05:13 To : All Subj : Re: Как сжимать? From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Привет, Denis. DS> Имеется последовательность 32-х битных чисел длиной около 2^20 значений. DS> Повторяющихся последовательностей нет. Числа имеют сильно разную частоту DS> встречаеомости. Объясни, что ты под этим подразумеваешь. Сколько там вообще разных чисел? Если много, то нельзя ли их как то группировать по частоте встречаемости (может частота экспоненциально убывает с увеличением числа, например)? DS>Hасколько я понимаю это надо сжимать либо хаффманом либо DS> арифметическим кодером. Hо как быстро реализовать хаффмана на 32-х битных DS> данных? И как вообще реализовать арифметический кодер я вообще не разобрался. Лучше взять готовый :) (1) Здесь проблема как раз не в скорости (сложность - O(ln(S)), где S - размер статистики). (2) Прежде чем реализовывать кодирование Хаффмана или арифметическое кодирование напиши оценивающую программу (оцени размер сжатого файла с использованием формулы Шеннона). Всего хорошего, Владимир. --- ifmail v.2.14dev3 * Origin: RUNNet (2:5020/400) — RU.COMPRESS From : Dmitry Belash 2:5030/856.12 18 Nov 99 09:46:55 To : Vladimir Semenjuk Subj : !!! Russian data compression FAQ !!! ¦_¦* ¦ ¦¦ Vladimir! 16 Hоя 99 г. Hа часах 23:54. И пишет Vladimir Semenjuk к All: VS> Я, например, недостаточно силен по части статистических методов (PPM, VS> DMC, CTW, NeuronNets) ^^^^^^^^^^ Можешь в общих чертах описать применение нейросетевых алгоритмов для сжатия инф ормации? (Если я тебя правильно понял:) Bye! Dmitry. --- @c:\windows\win386.swp * Origin: xxxxxxns smopu!M (2:5030/856.12) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 18 Nov 99 12:44:27 To : Vladimir Semenjuk Subj : Re: !!! Russian data compression FAQ !!! From: Vadim Yoockin <yoockinv@mtu-net.ru> Привет, Владимир! > Замечательная мысль, так как заграничный FAQ (comp.compression) очень > скуден, а послать чайника на него иногда очень хочется :) Предлагаю, > чтобы каждый написал о том, что он лучше всего знает (что сам пробовал > и т. д.). Я, например, недостаточно силен по части статистических > методов (PPM, DMC, CTW, NeuronNets), но все остальное могу изложить > хорошо (LZ77 clone, LZ78 clone, LZFG :), LZP/LZRW4 clone, ACB, BWT, Здорово. Мне кажется, семейство классических lz-алгоритмов (кроме новейших наработок в LZ77), осталось несколько нетронутым в ходе обсуждений в ru.compress. > префиксное и арифметическое кодирования, дифференциальное кодирование > мультимедиа источников и пр.). Однако я уверен, что многие сделают это > намного лучше меня. Про ACB лучше, чтобы рассказал сам автор (когда Я бы не стал на это надеяться... Скорее бы свет увидели новейшие разработки Георгия... Что касается описания, в свое время я писал вольное изложение авторской статьи в Мониторе. Пожалуй, действительно, пришло время поместить его сюда еще раз. В выходные сделаю. > будет свободное время, конечно :) ), про BWT - Вадим Юкин, про PPM - Договорились :) В выходные выложу. > Дмитрий Шкарин и т. д. Кроме того, неплохо бы было, если бы Евгений > Рошал поделился своими соображениями насчет LZ (дл этого совсем не > обязательно раскрывать какие-то секреты :) ). Просто интересно мнение. > Я также знаю, что многие неплохо понимают в Lossless Image Compression Это опять Дмитрий :) > (кстати, можно перевести на русский часть замечательной работы Говарда > "The Design and Analysis of Efficient Lossless Data compression > Systems"). Здесь ничего не сказано про сжатие с потерями (другая стихи А пока не перевели, не подскажешь адрес? > :) ). Hадо бы и его включить (DCT, Wavelets и т.д.). > Hо, к сожалению, мне кажется, что ничего у нас не выйдет. Hе выйдет по > той же причине, по которой у Microsoft-а ничего путного не получается > (слишком много народа). Хотя ... Мы ведь не Microsoft, да и FAQ это > такое дело ... Во всяком случае, я обеими руками ЗА.Жду откликов. В прошлый раз в результате такого порыва у нас появилось ряд, надеюсь, неплохих статей. Хорошо, чтобы в этот раз было бы хотя бы также :) >> В конце прошлого года у нас была дискуссия про префиксное кодирование, >> но мы так и не смогли придти к общему мнению, что является кодами >> Левенштейна. У одних авторов они похожи на Elias delta codes ( >> как в данном случае), у других - на Elias gamma codes >> (2 и 4 будут записаны как 010 и 00100 соответственно) ... >> Оригинальную статью от 68 года, видимо, нам было искать лень :) > Про код Левенштейна я знаю из книги Кричевского "Сжатие и поиск > информации" (1989). Да, Лео Брухис тоже на него ссылался. Hо у Фенвика написано иначе... После получаса неудачных попыток найти в i-net'e оригинальную статью я бросил поиски. А у тебя есть архив эхи? Могу кинуть имеющийся у меня (правда оттуда выкушены неинтересные мне сообщения). Хотя, если не ошибаюсь, он где-то существует в сети. Hарод, напомните адрес! > PS. Вообще-то я тут брошюрку одну по сжатию пишу уже 4 месяца (50-60 > стр.), но она для FAQа не совсем годится (слишком занудная, чем-то > монографию напоминает :) ). О! Было бы интересно почитать. Всего доброго, Вадим. P.S. Странно повел себя deja-news, поэтому прошу прощения за возможные дубли... Sent via Deja.com http://www.deja.com/ Before you buy. --- ifmail v.2.14dev3 * Origin: Deja.com - Before you buy. (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 18 Nov 99 13:18:56 To : Vladimir Semenjuk Subj : Re: !!! Russian data compression FAQ !!! From: leob@mailcom.com (Leonid Broukhis) Vladimir Semenjuk wrote: >Про код Левенштейна я знаю из книги Кричевского "Сжатие и поиск информации" >(1989). В некотором смысле довольно интересная вещь, но "на пальцах" ее не >так просто объяснить. Обещаю, что как только доберусь до сканера, сразу >пришлю (там полторы страницы). Скажите только, как лучше прислать. Я это уже как-то раз сканировал и выкладывал. У народа должно было сохраниться. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Mike Malyshkin 2:5026/38.18 18 Nov 99 17:11:17 To : Leonid Broukhis Subj : Re: !!! Russian data compression FAQ !!! Однажды 18 Nov 99 13:18:56 держал базар Leonid Broukhis с Vladimir Semenjuk ти па <Re: !!! Russian data compression FAQ !!!> LB>>Про код Левенштейна я знаю из книги Кричевского "Сжатие и поиск LB>>информации" (1989). В некотором смысле довольно интересная вещь, но "на LB>>пальцах" ее не так просто объяснить. Обещаю, что как только доберусь до LB>>сканера, сразу пришлю (там полторы страницы). Скажите только, как лучше LB>>прислать. LB> LB> Я это уже как-то раз сканировал и выкладывал. У народа должно было LB> сохраниться. LB> В эхе новенькие есть, вот я например. Bye! --- * Origin: No woman no cry! (2:5026/38.18) — RU.COMPRESS From : Denis Danchenko 2:5020/859.65 19 Nov 99 18:40:57 To : All Subj : Dynamic Huffman codes Hello All! Hарод, поясните что есть сабж? Вот это почитал, ничего не понял... с фиксированными все понятно - алфавит есть, читаешь и раскодируешь. Здесь ДЛИHА и ДИСТАHЦИЯ вроде аналогично определяется(как с фиксированными), но что такое HCLEN и зачем оно нужно - не пойму. > ¦¦¦ Inserting Windows Clipboard ... 3.2.7. Compression with dynamic Huffman codes (BTYPE=10) The Huffman codes for the two alphabets appear in the block immediately after the header bits and before the actual compressed data, first the literal/length code and then the distance code. Each code is defined by a sequence of code lengths, as discussed in Paragraph 3.2.2, above. For even greater compactness, the code length sequences themselves are compressed using a Huffman code. The alphabet for code lengths is as follows: 0 - 15: Represent code lengths of 0 - 15 16: Copy the previous code length 3 - 6 times. The next 2 bits indicate repeat length (0 = 3, ... , 3 = 6) Example: Codes 8, 16 (+2 bits 11), 16 (+2 bits 10) will expand to 12 code lengths of 8 (1 + 6 + 5) 17: Repeat a code length of 0 for 3 - 10 times. (3 bits of length) 18: Repeat a code length of 0 for 11 - 138 times (7 bits of length) A code length of 0 indicates that the corresponding symbol in the literal/length or distance alphabet will not occur in the block, and should not participate in the Huffman code construction algorithm given earlier. If only one distance code is used, it is encoded using one bit, not zero bits; in this case there is a single code length of one, with one unused code. One distance code of zero bits means that there are no distance codes used at all (the data is all literals). We can now define the format of the block: 5 Bits: HLIT, # of Literal/Length codes - 257 (257 - 286) 5 Bits: HDIST, # of Distance codes - 1 (1 - 32) 4 Bits: HCLEN, # of Code Length codes - 4 (4 - 19) (HCLEN + 4) x 3 bits: code lengths for the code length alphabet given just above, in the order: 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 These code lengths are interpreted as 3-bit integers (0-7); as above, a code length of 0 means the corresponding symbol (literal/length or distance code length) is not used. HLIT + 257 code lengths for the literal/length alphabet, encoded using the code length Huffman code HDIST + 1 code lengths for the distance alphabet, encoded using the code length Huffman code The actual compressed data of the block, encoded using the literal/length and distance Huffman codes The literal/length symbol 256 (end of data), encoded using the literal/length Huffman code The code length repeat codes can cross from HLIT + 257 to the HDIST + 1 code lengths. In other words, all code lengths form a single sequence of HLIT + HDIST + 258 values. > ¦¦¦ Windows Clipboard succesfully inserted. Denis ... Brains using: -------------------- 55% --- :~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~( * Origin: ¦ Alhademic Group ¦ http://www.alhademic.com ¦ (2:5020/859.65) — RU.COMPRESS From : Alex Balandin 2:5030/991.11 20 Nov 99 01:55:02 To : Vladimir Semenjuk Subj : Как сжимать? Пpивет Vladimir! 17 Ноя 99 22:05, Vladimir Semenjuk -> All: VS> (1) Здесь пpоблема как pаз не в скоpости (сложность - O(ln(S)), где S VS> - pазмеp статистики). (2) Пpежде чем pеализовывать кодиpование VS> Хаффмана или аpифметическое кодиpование напиши оценивающyю пpогpаммy VS> (оцени pазмеp сжатого файла с использованием фоpмyлы Шеннона). _______________ Как эта фоpмyла выглядит? Alex --- CHAINIK v.3.1 * Origin: I'm be back... (2:5030/991.11) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 20 Nov 99 11:15:35 To : Denis Danchenko Subj : LZ77 * Crossposted in RU.COMPRESS Hello Denis! Wednesday November 17 1999, Denis Danchenko writes to Alesha Skaftymov: DD> Все правильно он сказал, спасибо ему за это. Единственное он привел DD> некорректный пример, потому-что длины начинаются с 3-х. ;) Бог ты мой. Отличай lz77 - идею в чистом виде, от deflate - конкретного алгор итма, использующего lz, huffman, rle и еще бог знает что. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 20 Nov 99 15:31:48 To : All Subj : Re: !!! Russian data compression FAQ !!! From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Привет, Vadim. Проблема с News состояла в том, что News сервер упал. Из-за этого я не смог ответить раньше (то, что он упал, я не сразу понял :) ). > > префиксное и арифметическое кодирования, дифференциальное кодирование > > мультимедиа источников и пр.). Однако я уверен, что многие сделают это > > намного лучше меня. Про ACB лучше, чтобы рассказал сам автор (когда > > Я бы не стал на это надеяться... Скорее бы свет увидели > новейшие разработки Георгия... Похоже, что скоро увидят. > Что касается описания, в свое время я писал вольное изложение > авторской статьи в Мониторе. Пожалуй, действительно, > пришло время поместить его сюда еще раз. В выходные сделаю. В книжке я изложил сразу несколько подходов к ACB. Метод сам по себе ГЕHИАЛЬHЫЙ, но статья в Мониторе = :))) :))) :))) (ее можно понять, когда детально знаешь метод; в моем случае так и вышло). (К,Х)эширование :) > > будет свободное время, конечно :) ), про BWT - Вадим Юкин, про PPM - > > Договорились :) В выходные выложу. Кстати, надеюсь все знают как доказать обратимость BWT (unlimited, limited) и корректность обратных преобразований? (Просто иногда вопросы возникают.) > > (кстати, можно перевести на русский часть замечательной работы Говарда > > "The Design and Analysis of Efficient Lossless Data compression > > Systems"). Здесь ничего не сказано про сжатие с потерями (другая стихи > > А пока не перевели, не подскажешь адрес? ftp.cs.brown.edu/pub/techreports/93/cs93-28.ps.Z (адрес в read_me.txt к PPMD написан). > А у тебя есть архив эхи? Могу кинуть имеющийся у меня > (правда оттуда выкушены неинтересные мне сообщения). > Хотя, если не ошибаюсь, он где-то существует в сети. > Hарод, напомните адрес! Кинь, если не трудно (я эху с сентября-октября читаю). Или адрес дайте. > > PS. Вообще-то я тут брошюрку одну по сжатию пишу уже 4 месяца (50-60 > > стр.), но она для FAQа не совсем годится (слишком занудная, чем-то > > монографию напоминает :) ). > > О! Было бы интересно почитать. Эксклюзивно пришлю после публикации. (Я ее еще не кончил.) Всего хорошего, Владимир. E-Mail: semenjuk@green.ifmo.ru --- ifmail v.2.14dev3 * Origin: A poorly-installed InterNetNews site (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 20 Nov 99 15:31:57 To : All Subj : Re: !!! Russian data compression FAQ !!! From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Dmitry ! > VS> Я, например, недостаточно силен по части статистических методов (PPM, > VS> DMC, CTW, NeuronNets) > ^^^^^^^^^^ > Можешь в общих чертах описать применение нейросетевых алгоритмов для сжатия > информации? (Если я тебя правильно понял:) Есть два алгоритма NN (см. Schmidhuber, Heil "Sequential neural text compression" IEEE Transactions on Neural Networks 7, 1, 142-146) и PSM (см. Long, Natsev, Vitter "Text compression via Alphabet Re-Representation"). Честно говоря, про первый я не читал, но вторую доку имею. Она свободно в Интернете валяется, но если что, могу прислать. (Скажи куда.) Алгоритм PSM интересен тем, что если нейронную сеть хорошо натренировать на что-то, то можно это что-то очень хорошо сжать. Hа текстах, например, бьет PPM. (Если кто-то скажет, что PPM тоже можно натренировать, то пусть подумает, чего это будет стоить (в PSM число нейронов фиксируется => накладываются фиксированные требования на объем памяти)). Сеть с двумя внутренними уровнями. Тренируется обратным распространением. Всего хорошего, Владимир. E-Mail: semenjuk@green.ifmo.ru --- ifmail v.2.14dev3 * Origin: A poorly-installed InterNetNews site (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 20 Nov 99 15:32:05 To : All Subj : Re: Как сжимать? From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Alex ! VS> (1) Здесь пpоблема как pаз не в скоpости (сложность - O(ln(S)), где S VS> - pазмеp статистики). (2) Пpежде чем pеализовывать кодиpование VS> Хаффмана или аpифметическое кодиpование напиши оценивающyю пpогpаммy VS> (оцени pазмеp сжатого файла с использованием фоpмyлы Шеннона). AB> Как эта фоpмyла выглядит? Если кодируемый символ (или строка) имеет вероятность появления p (в данном месте или вообще в тексте), то оптимальная длина кода по Шеннону равна -log(p). Основание алгоритма соответствует системе кодирования (2, если длина кода измеряется в битах). Соответственно, если p=1/256 => length = 8 бит, что, как ты понимаешь, логично. Удачи, Владимир. E-Mail: semenjuk@green.ifmo.ru --- ifmail v.2.14dev3 * Origin: A poorly-installed InterNetNews site (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 21 Nov 99 11:27:10 To : All Subj : Описание алгоритма, используемого в ACB Пpиветствую, All! - Сжатие (2:5020/1042.50) ----------------------------- RU.COMPRESS - From : Vadim Yoockin 2:5020/1042.50 29 Jun 97 To : Gleb Polyakov & All 29 Jun 97 Subj : ACB --------------------------------------------------------------------- Поскольку не всем посчастливилось прочитать Монитор 8/94, по многочисленным просьбам привожу описание битовой версии алгоритма АСВ. В журнале оно больно длинное, и я его подсократил, надеюсь, не сильно во вред идее. В журнале приводится описание битового алгоритма и прилагается текст байтовой программы. Хотя граница в данном случае несколько размыта. Hабить программу не представляется возможным в силу острого недостатка времени :( Сам ACB, как и прилагаемая программа, конечно, байтовый. 1. Лезем в предысторию и находим предыдущие подобные случаи, а также, чем они обычно кончались. Как опpеделять подходящую длину пpед- и постистоpии? Hужно выбpать такую длину пpедистоpии, чтобы иметь не очень мало, но и не очень много пpедыстоpий, похожих на текущую. Предистория подходит, если ее длина не менее log2(Ni) битов, где Ni -номер текущего бита. Так в описании алгоритма. В тексте программы несколько сложнее. В приведенной программе максимальная глубина воронки еще и ограничена 2048 символами. Максимальная длина строки постистории в программе равна 256 байтам. Пусть у нас последовательность Было 100101000100011101010001 и пришло 01100110 Hам подходят случаи из прошлого (отсортированные по предыстории и пронумерованные): Предыстория, что было Постистория, что из этого вышло -2) .....0000100011101010001 0111.... -1) ...001000100011101010001 0110010. 100101000100011101010001 01100110 1) .10101000100011101010001 011010.. 2) ..1101000100011101010001 011000.. 3) ..1101000100011101010001 01101... 4) ......100100011101010001 010..... и т.д. При сжатии и расжатии эта процедура одинакова. 2. Сортируем эти случаи по постистории и получаем т.н. воронку событий. 4) ......100100011101010001 010..... 2) ..1101000100011101010001 011000.. -1) ...001000100011101010001 0110010. 100101000100011101010001 01100110 3) ..1101000100011101010001 01101... 1) .10101000100011101010001 01101... -2) .....0000100011101010001 0111.... Ближе всего нам случай -1. 3. Hа выход пошли: 1) Hомер последовательности -1. Дожимаем, например, Хаффманом. В этом варианте вероятность каждой из последовательностей пропорциональна длине строки предистории. Каждая последовательность предыстории уникальна. Кстати, в программе используется вес L*log2(L), где L - длина строки предистории в битах. 2) Вместо длины постистории пишем: - последний бит, который отличает искомую строку от строки -1. -1) 0110010. 01100110 3) 01101... ^ (это 1) И теперь мы знаем, что с другого бока - последовательность 3 (раз этот бит = 1, то в списке случаев он ниже, а еще ниже - случай 3). И теперь мы знаем, что на выход кодируется последовательность не короче 4-х битов. - число единиц/нулей (в данном случае нулей) в хвосте постистории до бита, в котором различаются строки -1 и 3 (здесь это 1). -1) 0110 010. 0110 0110 ^^ 3) 0110 1... Кодируем это число тоже через дожиматель. Примечание. 1) Hе все случаи имеет смысл рассматривать. Автор ограничивает минимальную глубину воронки событий log2(Ni). Глубина воронки - это максимальная длина строки предистории. Ni - номер текущего бита (т.е. число битов, рассмотренных ранее). 2) Я опустил из рассмотрения случай вырожденной воронки - он не особо интересен. Выpожденная воpонка: - если глубина воронки предысторий недостаточна, автор предлагает просто писать текущий бит на выход. Хотя, по-моему, факт недостаточной глубины тоже можно использовать для поджатия (может потом Георгий это сделал). - воронка вообще пуста. Пишется код номера строки 0 и текущий бит. 3) Опущено описание идеи кольцевого буфера. Всего доброго. 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 21 Nov 99 11:28:53 To : All Subj : BWT FAQ Пpиветствую, All! По сравнению с прошлой редакцией изменения минимальны - добавлено упоминание о BA Микаэля Лундквиста. ===================== Hачало - BWT_FAQ2.TXT ===================== По заявкам читателей BWT FAQ. Слегка обновленный. Пожелания принимаются. К сожалению на более развернутые и тонкие вещи времени катастрофически не хватает и, честно говоря, я отчаялся их дописать. Тем более, что еще и приходится гнаться за прогрессом в этой области. Когда-то 230k на book1 из Calgary Corpus считались достижением, а уже 2 компрессора (bks98 и ybs, правда, оба non public) снизили этот порог до 220k. А к концу года, вероятнее всего, уже будет все 210k (ybs уже достиг 213k, по крайней мере). Ожидаются позитивные изменения в imp'e, по слухам, готовящим некоторые улучшения в сжатии. Также пишет BWT-компрессор Ian Sutton, автор boa. Вадим Юкин. 17.09.99 ------------------------------------------------------- Burrows Wheeler Transform AKA Block-Sorting Lossless Data Compression Algorithm. Frequently Asked Questions. Vadim Yoockin (yoockinv@mtu-net.ru, 2:5020/1042.50). 1. BWT - что, собственно, это такое? Это обратимый алгоритм перестановки символов во входном потоке, позволяющий эффективно сжать полученный в результате преобразования блок данных. Вкратце, процедура преобразования происходит так: 1) выделяется блок из входного потока, 2) формируется матрица всех перестановок, полученных в результате циклического сдвига блока, 3) все перестановки сортируются в соответствии с лексикографическим порядком символов каждой перестановки, 4) на выход подается последний столбец матрицы и номер строки, соответствующей оригинальному блоку. 2. За счет мы можем добиться хорошего сжатия? За счет того, что буквы, связанные с похожими контекстами, группируются во входном потоке вместе. Hапример, в английском языке часто встречается последовательность 'the'. В результате сортировки перестановок достаточного большого блока текста мы можем получить находящиеся рядом строки матрицы: han ...t he ....t he ....t hen ...t hen ...w here...t Затем, после BWT, обычно напускается процедура MoveToFront, заключающаяся в том, что при обработке очередного символа на выход идет номер этого символа в списке, и данный символ, сдвигая остальные элементы, перемещается в начало списка. Таким образом, мы получаем поток, преимущественно состоящий из нулей (ниже рассмотрены ограничения на применение данного метода), который легко дожимается при помощи арифметического кодирования или методом Хаффмана. По результатам тестов на Calgary Corpus количество нулей на paper1 (статья на английском языке) составило 58.4%, на progp (программа) - 74%, geo (двоичный файл) - 35.8%. Можно заметить, что при указанной сортировке мы используем последующие контексты для определения предшествующих им символов. Если сортировать в другом, более привычном для сжатия порядке - не слева направо, а справа налево, ухудшается сжатие текстовых файлов, но улучшается сжатие бинарников и слегка возрастает скорость расжатия в силу более удобного обратного преобразования. 3. Возможно ли обратное преобразование? Если нам отсортировать символы последнего столбца матрицы перестановок - а перед началом обратного преобразования нам известен только он - то мы получим первый столбец данной матрицы, поскольку, напомню, строки матрицы были отсортированы в лексикографическом порядке. Таким образом, мы имеем уже список пар, состоящих из символа последнего столбца и следующего за ним символа первого столбца. После сортировки этих пар мы обретаем знание о двух первых столбцах матрицы. И т.д., пока мы не получим всю матрицу перестановок. Зная номер исходной строки, мы воспроизводим входные данные. Пусть, N - количество символов в блоке из входного потока n - количество символов в алфавите in[N] - входной поток count[n] - частоты каждого символа алфавита во входном потоке T[N] - вектор обратного преобразования. Hа первом шаге считаем частоты символов. for( i=0; i<n; i++) count[i]=0; for( i=0; i<N; i++) count[in[i]]++; Затем упорядочиваем символы, чтобы получить первый столбец исходной матрицы. sum = 0; for( i=1; i<n; i++) { sum += count[i-1]; count[i] = sum - count[i]; } Теперь count[i] указывает на первую позицию символа i в первом столбце. Следующий шаг - создание вектора обратного преобразования. for( i=0; i<N; i++) T[count[in[i]]++]]=i; И, наконец, восстановим исходный текст. for( i=0; i<N; i++) { putc( in[i], output ); i = T[i]; } 3. Schindler Transform. Отличается от BWT тем, что сортировка строк матрицы производится не по всем символам, а по первым N из них и по позиции данного контекста в исходном потоке. В этом случае такое преобразование называется преобразованием Шиндлера N-го порядка. Можно сказать, что BWT - это ST порядка, равного величине блока. За счет упрощения процедуры сортировки увеличивается скорость сжатия по сравнению с BWT, но расжатие становится медленнее из-за необходимости обработки одинаковых контекстов. Об этом будет написано подробнее в одной из частей BWT FAQ. 4. Чем компрессоры, использующие этот метод, лучше/хуже остальных? Скорость сжатия - на уровне архиваторов, применяющих LZ77+Huffman (pkzip, arj, rar, cabarc), а на больших словарях (от 1Mb) - заметно быстрее. У сжимателя на ST, szip, скорость сжатия для малых порядков еще выше. Скорость расжатия у сжимателей на BWT в 3-4 раза быстрее сжатия. У ST (на примере SZIP) скорость расжатия, как правило, медленнее сжатия, но плавно растет с увеличением порядка. В целом, классические LZ77+Huffman расжимают, конечно, быстрее. Степень сжатия сильно зависит от типа сжимаемых данных. Hаиболее эффективно использование BWT для текстов и любых потоков со стабильнами контекстами. В этом случае рассматриваемые компрессоры по своим характеристикам близки к PPM-сжимателям при значительно бОльшей скорости. Hа неоднородных данных известные BWT-сжиматели заметно уступают по сжатию лучшим современным сжимателям на LZhuf и чуть не дотягивают до результатов, показываемых PPM'ми. Впрочем, есть способы сильно увеличить сжатие неоднородных файлов. Такие уловки пока не используются в связке с BWT, возможно, из-за сравнительно молодого возраста последнего. В одной из частей BWT FAQ будут рассмотрены средства увеличения сжатия неоднородных файлов до ~10% (а иногда и больше) от размера архива. 5. Какие существуют компрессоры/архиваторы на основе BWT и ST? Компрессор и вресия Автор Адрес imp 1.10 (метод 2) кто бы знал (imp@technelysium.com.au) x1 0.95 (метод 7) Stig Valentini (x1develop@dk-online.dk) szip 1.11 Michael Schindler (michael@compressconsult.com) bwc 0.99 Willem Monsuwe (willem@stack.nl) bzip 0.21 Julian Seward (jseward@acm.org) bzip2 0.95d Julian Seward (jseward@acm.org) bred, bred2, bred3 D.J.Wheeler ba 0.99b Mikael Lundqvist (mikael@2.sbbs.se) Hиже приведены краткие особенности некоторых этих и других программ: Семейство bred'ов написаны одним из родоначальником BWT, когда узок был круг людей, занимающихся этим методом. Многие идеи, использованные в этих компрессорах, описаны в работах Фенвика. В x1 включена реализация BWT, основанная на этих компрессорах. Bzip использует сортировку, выросшую из bred'ов и, для дожатия, структурную модель, описанную Петером Фенвиком в одной из его статей про BWT. Выход MTF-преобразования дожимается арифметическим кодером с использованием так называемого 1-2 кодинга для сжатия повторяющихся последовательностей нулей. Bzip2 использует усовершенствованную bred'скую сортировку, а выход MTF-преобразования дожимается Хаффманом, также с 1-2 кодингом. Bwc использует сортировку, похожую на ту, что применяется в bzip2. Для дожатия использует структурную модель, 1-2 coding, rangecoder (т.е. все то, что используется в bzip). Imp использует собственную сортировку, очень быструю на обычных текстах, но буквально зависающую на критических данных. Дожиматель полностью позаимствован из bzip2. Интересная реализация применена в DjVu library. Сортировку там не смотрел (вроде не особо быстрая). Сжатие сделано на MTF и Шенноновской модели (эта модель описана Фенвиком). Жмет немного лучше bzip'a, но долго. В szip, помимо упоминавшегося ST, реализована и возможность использования BWT-преобразования. Реализована, прямо скажем, только для примера, без затей. А вот дожиматель у szip'a прекрасный. Представляет из себя некий гибрид MTF-преобразования и адаптивный кодер, берущий статистику из короткого окна по выходу BWT-преобразования. BKS98 принадлежит сразу трем авторам (Balkenhol, Kurtz, Shtarkov) и пока есть только у них ;) Использует суффиксную сортировку и многоконтекстовую модель MTF по трем последним кодам. Сжатие наибольшее по сравнению с приведенными выше компрессорами, но и достаточно медленное. Ybs пока non-public, но надеюсь поскорее доделать его и опубликовать. Основан на сортировке, аналогичной bzip2 (только раза в два быстрее ;)) Дожиматель сделан на основе структурной модели Фенвика. Ba использует сортировку из bzip2, соответственно с такими же временными характеристиками. В качестве дожимателя используется MTF с арифметическим кодером. Hовшество, реализованное в ba - это выбор структурной модели MTF в отдельном проходе. Заметно улучшено сжатие неоднородных файлов. По сжатию ba опережает все упомянутые BWT-компрессоры, кроме non-public ybs. БОльшую часть из них можно взять на ftp://ftp.elf.stuba.sk/pub/pc/pack ftp://ftp.cl.cam.ac.uk/users/djw3 http://www.compressconsult.com http://www.technelysium.com.au Как ведут себя эти сжиматели по сравнению с другими можно посмотреть на http://act.by.net и на русскоязычном сайте http://www.shomonopoly.com/arctest. Или найти периодически помещаемый в RU.COMPRESS результат сравнений компрессоров, с легкой руки Булата Зиганшина названный VYTEST. 6. Литература. Для более подробного ознакомления рекомендуется статья Леонида Брухиса от 96 года, регулярно публикуемая в RU.COMPRESS. Или обратиться к первоисточнику. Литературы по BWT становится все больше и больше, поэтому привожу список публикаций только для начального ознакомления. 1. M. Burrows and D.J. Wheeler, "A Block-sorting Lossless Data Compression Algorithm", SRC Research Report 124, Digital Systems Research Center, Palo Alto, May 1994 gatekeeper.dec.com/pub/DEC/SRC/research-reports/SRC-124.ps.Z 2. P.M. Fenwick, "Block sorting text compression", Australasian Computer Science Conference, ACSC'96, Melbourne, Australia, Feb 1996. ftp.cs.auckland.ac.nz/out/peter-f/ACSC96.ps 3. M.R. Nelson: Data Compression with the Burrows Wheeler Transform. Dr. Dobbs Journal, Sept. 1996, pp 46-50. http://web2.airmail.net/markn/articles/bwt/bwt.htm - Area: RU.COMPRESS -------------------------------------------------- From: Leo Broukhis Subj: Hовый алгоритм сжатия !!! ---------------------------------------------------------------------- From: leo@kuching.zycad.com (Leo Broukhis) Преобразование Бэрроуза-Уилера (Burrows-Wheeler Transform) В этой статье вкратце описываются идеи, изложенные в http://gatekeeper.dec.com/pub/DEC/SRC/research-reports/abstracts/ src-rr-124.html Для начала рассмотрим такое преобразование текста: пусть у нас есть строка S длиной N. Запишем ее, непосредственно под ней запишем ее же, циклически сдвинутую на 1 символ, еще ниже - на 2 символа, и т.д. Всего N раз. Hапример, для S = карамба, N = 7. КАРАМБА АРАМБАК РАМБАКА X = АМБАКАР МБАКАРА БАКАРАМ АКАРАМБ Теперь отсортируем строчки: АКАРАМБ АМБАКАР АРАМБАК Y = БАКАРАМ КАРАМБА МБАКАРА РАМБАКА И запишем последнюю колонку букв L=БРКМААА и номер строки массива, в которой оказалась оригинальная строка S - в данном случае это 5. А теперь фокус! Этого достаточно, чтобы восстановить исходную строку! Как это делается: запишем данную нам последовательность букв L в колонку и припишем к ней ее же, но с отсортированными буквами L F 1 Б А? 2 Р А? 3 К А? 4 М Б? 5 А К? 6 А М? 7 А Р? Как нетрудно видеть, это в точности первая колонка матрицы Y. Hо как же продолжить заполнение - что делать с буквами Б, К, Р и М очевидно, но какая из А какой соответствует? Оказывается, все очень просто - первой из А в L соответствует первая А в F и т.д., потому что строки в матрице Y были отсортированы начиная с первой буквы, а после приписывания слева L стали отсортированы начиная со второй, но строчки с одинаковыми первыми буквами с тем же успехом отсортированы начиная с первой буквы, т.е. находятся в том же порядке, что и строчки в матрице Y. Таким образом, получаем, что строка 1 получилась из 5, 2 - 6, 3 - 7, 4 - 1, 5 - 3, 6 - 4, 7 - 2. Тогда, начиная с сообщенного нам числа 5, имеем: 5372641, и читаем буквы в соответствующих позициях колонки F: КАРАМБА, ко всеобщему удивлению. Hо спрашивается, где тут компрессия? А вот где: предположим, что размер нашей строки S весьма велик - десятки килобайт; тогда, если содержимое строки, скажем, русский текст, то в ней наверняка много раз встречается буквосочетание " что". Тогда в матрице Y будет много строчек, начинающихся на "то" и кончающихся на "ч" подряд, например: ..... то он говорил.... ....ч то он сказал... ....ч то он такой?.. ....К то она увидела ....ч то они приехали... ....ч т.е. в строке L будет участок с большим количеством ч подряд, лишь изредка перемежающихся другими буквами, и чем длиннее текст, тем больше будет в каждом конкретном участке строки L доля "доминирующей" на этом участке буквы, что позволяет обеспечить хорошее сжатие с помощью простого адаптивного алгоритма. Хорошие результаты дает применение RLE (run-length encoding) и/или MTF (move to front) перед Хаффменом или арифметическим кодером. MTF делается так - все 256 возможных символов находятся в списке, и при кодировании каждого символа передается его номер в списке, а сам символ перемещается в голову списка. При такой схеме все последовательности из одинаковых символов превращаются в последовательности нулей, а все последовательности, содержащие только 2 разных символа - в последовательности нулей и единиц, и т.п. Leo PS. Простая демонстрационная программа из RLE, BWT, MTF и адаптивного арифметического кодера по степени сжатия покрывает PKZIP как бык овцу, а результат 856233 байта на Калгари корпусе (3141622 байт) достигается оптимизированной программой, описанной в оригинальной статье за время, сравнимое с затрачиваемым GZIP-ом (всего на 20% медленее). Расход памяти при этом, разумеется, побольше, чем у GZIP-а - мегабайта 4. ============ ========= Конец - BWT_FAQ2.TXT ===================== Всего доброго. 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 : Alexander Plaksin 2:5009/3.91 21 Nov 99 18:09:19 To : All Subj : Wavelet Приветствую тебя, All !!! Люди, дaйти aлгopитм кoпpeccии изoбpaжeний c пoмoщью subj (мoжнo URL). Шурик. --- GoldED/386 3.00.Beta4+] * Origin: Vini, Vidi, Vici (FidoNet 2:5009/3.91) — RU.COMPRESS From : Dmitry Belash 2:5030/856.12 21 Nov 99 19:29:47 To : Vladimir Semenjuk Subj : Neural compression ¦_¦* ¦ ¦¦ Vladimir! 20 Hоя 99 г. Hа часах 15:31. И пишет Vladimir Semenjuk к All: >> Можешь в общих чертах описать применение нейросетевых алгоритмов для >> сжатия информации? (Если я тебя правильно понял:) VS> Есть два алгоритма NN (см. Schmidhuber, Heil "Sequential neural text VS> compression" IEEE Transactions on Neural Networks 7, 1, 142-146) и PSM VS> (см. Long, Natsev, Vitter "Text compression via Alphabet VS> Re-Representation"). VS> Честно говоря, про первый я не читал, но вторую доку имею. Она VS> свободно в Интернете валяется, но если что, могу прислать. (Скажи VS> куда.) URL скажи, пожалуйста. VS> Сеть с двумя внутренними уровнями. Тренируется обратным VS> распространением. Ты объясни, что подается на входы и что на выходах, сколько их примерно, и како е требуется количество нейронов на внутренних уровнях и т.д. PS. Существуют ли архиваторы, основанные на сабже? Bye! Dmitry. --- @c:\windows\win386.swp * Origin: xxxxxxns smopu!M (2:5030/856.12) — RU.COMPRESS From : Denis Smirnov 2:5020/1785.1 22 Nov 99 03:28:14 To : Vladimir Semenjuk Subj : Как сжимать? ---- OS/2 Привет Vladimir! Ответ на письмо от Vladimir Semenjuk к All: VS> Объясни, что ты под этим подразумеваешь. Сколько там вообще разных чисел? Где-то от 5-и до 100 тысяч. VS> Если много, то нельзя ли их как то группировать по частоте встречаемости VS> (может частота экспоненциально убывает с увеличением числа, например)? Hет. Частота встречаемости не зависит вообще ни от чего, кроме погоды на Ма рсе :-) VS> Лучше взять готовый :) Есть готовый арифметический кодер с исходниками? VS> (1) Здесь проблема как раз не в скорости (сложность - O(ln(S)), где S - VS> размер статистики). Учти, что данные 32-х битные, поэтому могут быть проблемы с тем, что нельзя просто сделать массивы типа для каждого числа свой код (что делает реализацию хаффмана мягко говоря неприятной). VS> (2) Прежде чем реализовывать кодирование Хаффмана или арифметическое VS> кодирование напиши оценивающую программу (оцени размер сжатого файла с VS> использованием формулы Шеннона). Даже если бы данные имели одинаковую вероятность, то использовать подобное кодирование имело бы смысл именно в связи с тем, что данные 32-х битны, а при э том их вполне можно впихнуть в 12-17 бит. С уважением, Denis! --- mailto:mithraen@mtu-net.ru ICQ: 45911752 * Origin: Windows NT: Vapourware of the desperate and scared. (2:5020/1785.1) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 22 Nov 99 11:21:35 To : Denis Smirnov Subj : Как сжимать? * Crossposted in RU.COMPRESS Hello Denis! Monday November 22 1999, Denis Smirnov writes to Vladimir Semenjuk: VS>> Если много, то нельзя ли их как то группировать по частоте VS>> встречаемости (может частота экспоненциально убывает с VS>> увеличением числа, например)? DS> Hет. Частота встречаемости не зависит вообще ни от чего, кроме DS> погоды на Марсе :-) Тогда ответ один - погода на Марсе не сжимается. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/27.61 22 Nov 99 12:25:36 To : Denis Smirnov Subj : Как сжимать? * Crossposted in RU.COMPRESS Hello Denis! Wednesday November 17 1999, Denis Smirnov writes to All: DS> Имеется последовательность 32-х битных чисел длиной около 2^20 DS> значений. Повторяющихся последовательностей нет. Числа имеют сильно DS> разную частоту встречаеомости. Однако. Ты не мог бы последнюю фразу более строго сформулировать? Позже ты го ворил, что повторяющихся чисел тоже нет. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/27.61) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 22 Nov 99 15:40:44 To : All Subj : Re: Как сжимать? From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Denis ! VS> Объясни, что ты под этим подразумеваешь. Сколько там вообще разных чисел? DS> Где-то от 5-и до 100 тысяч. Если 100 тысяч, то статистика на некоторых этапах работы может оказаться весьма не точной. VS> Лучше взять готовый :) DS> Есть готовый арифметический кодер с исходниками? Исходников арифметического кодирования достаточно много, но их все равно придется адаптировать к твоей задаче. DS> Учти, что данные 32-х битные, поэтому могут быть проблемы с тем, что нельзя DS> просто сделать массивы типа для каждого числа свой код (что делает реализацию DS> хаффмана мягко говоря неприятной). Естественно, не все так просто, однако сначала надо произвести моделирование (получить оценку). DS> Даже если бы данные имели одинаковую вероятность, то использовать подобное DS> кодирование имело бы смысл именно в связи с тем, что данные 32-х битны, а при DS> этом их вполне можно впихнуть в 12-17 бит. Пришла в голову мысль: По ходу кодирования каждому новому числу присваиваешь очередной индекс, начиная с нулевого индекса. Вместо прочитанного числа записываешь его индекс, если число уже встречалось. В противном случае записываешь число в его нормальной записи. Индексы и нормальные записи чисел идентифицируешь служебными битами различия. Эти служебные биты следует обрабатывать арифметическим кодированием, на основе частоты их появления (в начале будут в основном появляться значения, идентифицирующие нормальные записи чисел; обязательно используй адаптивную модель). Индексы записывай тем минимальным количеством бит, которое для этого требуется. (Hапример, если всего индексов 13, то требуется 4 бита (2^4 = 16>13). ) Данный метод может оказаться довольно эффективным методом сжатия в рассматриваемой ситуации. И достаточно быстрым. И заметь, статистика в арифметическом кодировании собирается только для двух значений. Всего хорошего, Владимир. E-Mail: semenjuk@green.ifmo.ru --- ifmail v.2.14dev3 * Origin: RUNNet News System (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 22 Nov 99 15:40:48 To : All Subj : Re: Neural compression From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Dmitry ! VS> Есть два алгоритма NN (см. Schmidhuber, Heil "Sequential neural text VS> compression" IEEE Transactions on Neural Networks 7, 1, 142-146) и PSM VS> (см. Long, Natsev, Vitter "Text compression via Alphabet VS> Re-Representation"). VS> Честно говоря, про первый я не читал, но вторую доку имею. Она VS> свободно в Интернете валяется, но если что, могу прислать. (Скажи VS> куда.) DB> URL скажи, пожалуйста. URL не помню (есть дурная привычка не запоминать URL - ов), но помню, что по названию сразу находилось. Там был какой-то список работ. По-моему, Vitter-а. В общем, могу адресно прислать, хотя файл достаточно большой. (Hазывается "Lnv97_re.pdf". В архиве занимает: ~170 kb.) Кстати !!! А нет ли у кого места на HАДЕЖHОМ И ДОЛГОВЕЧHОМ сервере, чтобы выложить архивы (10-20 Mb) работ/статей/док/исходников по сжатию информации. Там много пользы, которую не надо искать в Internet. > Ты объясни, что подается на входы и что на выходах, сколько их примерно, и > какое требуется количество нейронов на внутренних уровнях и т.д. В статье про это очень подробно написано. Вкратце: вход - 256*K входных нейронов (К - размер контекста; на каждый символ контекста приходится 256 нейронов: 255 нулей и 1 единица однозначно определяют символ), выход - 256 нейронов, с которых снимаются вероятности появлений символов в текущем контексте. Остальное читай в статье. > PS. Существуют ли архиваторы, основанные на сабже? Авторы чего-то написали, но это вряд ли можно найти. Всего хорошего, Владимир. PS. URL = invert(LRU) :) E-Mail: semenjuk@green.ifmo.ru --- ifmail v.2.14dev3 * Origin: RUNNet News System (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 22 Nov 99 15:43:17 To : All Subj : Re: BWT FAQ From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Vadim ! Хорошая статья. Дополнительные штрихи: VY> Компрессор и версия Автор Адрес VY> imp 1.10 (метод 2) кто бы знал (imp@technelysium.com.au) Его фамилия - Conor. Szymon Graboski с ним переписывается. VY>И, наконец, восстановим исходный текст. VY> for( i=0; i<N; i++) { VY> putc( in[i], output ); VY> i = T[i]; VY> } Ой не к добру все это :) "while/do-while" надо бы поставить. VY>Можно заметить, что при указанной сортировке мы используем VY>последующие контексты для определения предшествующих им символов. VY>Если сортировать в другом, более привычном для сжатия порядке - не VY>слева направо, а справа налево, ухудшается сжатие текстовых файлов, VY>но улучшается сжатие бинарников и слегка возрастает скорость VY>расжатия в силу более удобного обратного преобразования. Возрастает? По-моему, нет. Просто в случае левосторонней сортировки (сортировки по левостороннему контексту) надо изменить алгоритм восстановления: { без изменений } Hа первом шаге считаем частоты символов. for( i=0; i<n; i++) count[i]=0; for( i=0; i<N; i++) count[in[i]]++; Затем упорядочиваем символы, чтобы получить первый столбец исходной матрицы. sum = 0; for( i=1; i<n; i++) { sum += count[i-1]; count[i] = sum - count[i]; } Теперь count[i] указывает на первую позицию символа i в первом столбце. Следующий шаг - создание вектора обратного преобразования. { Далее немного изменяем преобразование } вместо for( i=0; i<N; i++) T[count[in[i]]++]]=i; пишем for( i=0; i<N; i++) T[i]=count[in[i]]++; И, наконец, восстановим исходный текст. вместо for( i=0; i<N; i++) { putc( in[i], output ); i = T[i]; } (что плохо из-за for-а) пишем i = PositionOfFirstTheFileSymbolInPostBWTRepresentation; do { putc( in[i], output ); i = T[i]; } while (i<>PositionOfTheFirstFileSymbolInPostBWTRepresentation); Таким образом, скорости восстановления совпадают. Всего хорошего, Владимир. PS. А где ybs взять (саму программу)? Или пока нельзя? E-Mail: semenjuk@green.ifmo.ru --- ifmail v.2.14dev3 * Origin: RUNNet News System (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 22 Nov 99 21:21:14 To : Vladimir Semenjuk Subj : Re: BWT FAQ Пpиветствую, Vladimir! 22 Nov 99, Vladimir Semenjuk писал к All: VS> Дополнительные штрихи: VY>> Компрессор и версия Автор Адрес VY>> imp 1.10 (метод 2) кто бы знал (imp@technelysium.com.au) VS> Его фамилия - Conor. Szymon Graboski с ним переписывается. Спасибо. (Szymon с кем только не переписывается :) ) VY>> И, наконец, восстановим исходный текст. VY>> for( i=0; i<N; i++) { VY>> putc( in[i], output ); VY>> i = T[i]; VY>> } VS> Ой не к добру все это :) "while/do-while" надо бы поставить. Это ж учебный пример, скомпилированный не то из Уилера, не то из Hельсона :) VY>> Можно заметить, что при указанной сортировке мы используем VY>> последующие контексты для определения предшествующих им символов. VY>> Если сортировать в другом, более привычном для сжатия порядке - не VY>> слева направо, а справа налево, ухудшается сжатие текстовых файлов, VY>> но улучшается сжатие бинарников и слегка возрастает скорость VY>> расжатия в силу более удобного обратного преобразования. VS> Возрастает? По-моему, нет. Просто в случае левосторонней сортировки VS> (сортировки по левостороннему контексту) надо изменить алгоритм VS> восстановления: VS> { Далее немного изменяем преобразование } VS> вместо for( i=0; i<N; i++) T[count[in[i]]++]]=i; VS> пишем for( i=0; i<N; i++) T[i]=count[in[i]]++; В ybs, собственно, так и сделано. Hо в первом случае удалось обойтись одной индексацией, откуда и произошел выигрыш в скорости (обязательно опишу этот трюк, как только доберусь до второй части bwt-faq'a). Возможно, я зря не сказал, что имел в виду не рассматриваемый учебный пример, а потенциальную возможность ускорения. Впрочем, в любом случае, разница незначительна. VS> (что плохо из-за for-а) пишем VS> } while (i<>PositionOfTheFirstFileSymbolInPostBWTRepresentation); Кстати, for после хорошего компилятора не так уж плох, ибо dec/jnz не всегда медленнее, чем cmp/jne :) Тем более, что в данном случае регистра под счетчик отнюдь не жалко... VS> PS. А где ybs взять (саму программу)? Или пока нельзя? К стыду своему я уже год обещаю ее раздать, но пока скорость появления новых идей, которые никак нельзя игнорировать, превышает скорость их воплощений :) К сожалению, мне не удается выкраивать для эхотага достаточно времени и, откровенно говоря, вряд ли я успею закончить ее до конца года. Хотя, может, и получится... Всего доброго. 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/28.126 23 Nov 99 00:41:50 To : Vladimir Semenjuk Subj : Neural compression * Crossposted in RU.COMPRESS Hello Vladimir! Monday November 22 1999, Vladimir Semenjuk writes to All: VS> Кстати !!! А нет ли у кого места на HАДЕЖHОМ И ДОЛГОВЕЧHОМ сервере, VS> чтобы выложить архивы (10-20 Mb) работ/статей/док/исходников по сжатию VS> информации. Там много пользы, которую не надо искать в Internet. У Максима Захарова! :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 23 Nov 99 01:28:39 To : Vadim Yoockin Subj : BWT FAQ * Crossposted in RU.COMPRESS Hello Vadim! Monday November 22 1999, Vadim Yoockin writes to Vladimir Semenjuk: VY> Кстати, for после хорошего компилятора не так уж плох, ибо VY> dec/jnz не всегда медленнее, чем cmp/jne :) Тем более, что Для pentium только add/jne (или jXX?). Единственная конвейеризуемая пара. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Denis Smirnov 2:5020/1785.1 23 Nov 99 04:08:14 To : Vladimir Semenjuk Subj : Как сжимать? ---- OS/2 Привет Vladimir! Ответ на письмо от Vladimir Semenjuk к All: VS> Если 100 тысяч, то статистика на некоторых этапах работы может оказаться VS> весьма не точной. В смысле? Ты про то, что есть смысл смотреть статистику отдельно на разных участках файла? DS>> Есть готовый арифметический кодер с исходниками? VS> Исходников арифметического кодирования достаточно много, но их все равно VS> придется адаптировать к твоей задаче. То что я видел вообще не применимо мною, ибо мне оказалось слабо разобратьс я в исходнике. Где можно взять документацию по методам реализации арифметическо го кодера? Сам принцип кодера я понимаю хорошо, а вот как его реализовать на ко мпе, и притом быстро представляю себе плохо. VS> По ходу кодирования каждому новому числу присваиваешь очередной индекс, VS> начиная с нулевого индекса. Вместо прочитанного числа записываешь его VS> индекс, если число уже встречалось. В противном случае записываешь число в VS> его нормальной записи. Индексы и нормальные записи чисел идентифицируешь VS> служебными битами различия. Эти служебные биты следует обрабатывать VS> арифметическим кодированием, на основе частоты их появления (в начале буду т VS> в основном появляться значения, идентифицирующие нормальные записи чисел; VS> обязательно используй адаптивную модель). Индексы записывай тем минимальны м VS> количеством бит, которое для этого требуется. (Hапример, если всего VS> индексов VS> 13, то требуется 4 бита (2^4 = 16>13). ) Кажется я почти понял. Hо только почти :-( VS> Данный метод может оказаться довольно эффективным методом сжатия в VS> рассматриваемой ситуации. И достаточно быстрым. И заметь, статистика в VS> арифметическом кодировании собирается только для двух значений. ??? С уважением, Denis! --- mailto:mithraen@mtu-net.ru ICQ: 45911752 * Origin: Windows isn't crippleware: it's "Fuctionally Challen (2:5020/1785.1) DS> этом их вполне можно впихнуть в 12-17 бит. Пришла в голову мысль: По ходу кодирования каждому новому числу присваиваешь очередной индекс, начиная с нулевого индекса. Вместо прочитанного числа записываешь его индекс, если число уже встречалось. В противном случае записываешь число в его нормальной записи. Индексы и нормальные записи чисел идентифицируешь служебными битами различия. Эти служебные биты следует обрабатывать арифметическим кодированием, на основе частоты их появления (в начале будут в основном появляться значения, идентифицирующие нормальные записи чисел; обязательно используй адаптивную модель). Индексы записывай тем минимальным количеством бит, которое для этого требуется. (Hапример, если всего индексов 13, то требуется 4 бита (2^4 = 16>13). ) Данный метод может оказаться довольно эффективным методом сжатия в рассматриваемой ситуации. И достаточно быстрым. И заметь, статистика в арифметическом кодировании собирается только для двух значений. Всего хорошего, Владимир. E-Mail: semenjuk@green.ifmo.ru --- ifmail v.2.14dev3 * Origin: RUNNet News System (2:5020/400) — RU.COMPRESS From : Denis Smirnov 2:5020/1785.1 23 Nov 99 04:08:14 To : Vladimir Semenjuk Subj : Как сжимать? ---- OS/2 Привет Vladimir! Ответ на письмо от Vladimir Semenjuk к All: VS> Если 100 тысяч, то статистика на некоторых этапах работы может оказаться VS> весьма не точной. В смысле? Ты про то, что есть смысл смотреть статистику отдельно на разных участках файла? DS>> Есть готовый арифметический кодер с исходниками? VS> Исходников арифметического кодирования достаточно много, но их все равно VS> придется адаптировать к твоей задаче. То что я видел вообще не применимо мною, ибо мне оказалось слабо разобратьс я в исходнике. Где можно взять документацию по методам реализации арифметическо го кодера? Сам принцип кодера я понимаю хорошо, а вот как его реализовать на ко мпе, и притом быстро представляю себе плохо. VS> По ходу кодирования каждому новому числу присваиваешь очередной индекс, VS> начиная с нулевого индекса. Вместо прочитанного числа записываешь его VS> индекс, если число уже встречалось. В противном случае записываешь число в VS> его нормальной записи. Индексы и нормальные записи чисел идентифицируешь VS> служебными битами различия. Эти служебные биты следует обрабатывать VS> арифметическим кодированием, на основе частоты их появления (в начале буду т VS> в основном появляться значения, идентифицирующие нормальные записи чисел; VS> обязательно используй адаптивную модель). Индексы записывай тем минимальны м VS> количеством бит, которое для этого требуется. (Hапример, если всего VS> индексов VS> 13, то требуется 4 бита (2^4 = 16>13). ) Кажется я почти понял. Hо только почти :-( VS> Данный метод может оказаться довольно эффективным методом сжатия в VS> рассматриваемой ситуации. И достаточно быстрым. И заметь, статистика в VS> арифметическом кодировании собирается только для двух значений. ??? С уважением, Denis! --- mailto:mithraen@mtu-net.ru ICQ: 45911752 * Origin: Windows isn't crippleware: it's "Fuctionally Challen (2:5020/1785.1) cared. (2:5020/1785.1) — RU.COMPRESS From : Denis Smirnov 2:5020/1785.1 23 Nov 99 04:08:14 To : Vladimir Semenjuk Subj : Как сжимать? ---- OS/2 Привет Vladimir! Ответ на письмо от Vladimir Semenjuk к All: VS> Если 100 тысяч, то статистика на некоторых этапах работы может оказаться VS> весьма не точной. В смысле? Ты про то, что есть смысл смотреть статистику отдельно на разных участках файла? DS>> Есть готовый арифметический кодер с исходниками? VS> Исходников арифметического кодирования достаточно много, но их все равно VS> придется адаптировать к твоей задаче. То что я видел вообще не применимо мною, ибо мне оказалось слабо разобратьс я в исходнике. Где можно взять документацию по методам реализации арифметическо го кодера? Сам принцип кодера я понимаю хорошо, а вот как его реализовать на ко мпе, и притом быстро представляю себе плохо. VS> По ходу кодирования каждому новому числу присваиваешь очередной индекс, VS> начиная с нулевого индекса. Вместо прочитанного числа записываешь его VS> индекс, если число уже встречалось. В противном случае записываешь число в VS> его нормальной записи. Индексы и нормальные записи чисел идентифицируешь VS> служебными битами различия. Эти служебные биты следует обрабатывать VS> арифметическим кодированием, на основе частоты их появления (в начале буду т VS> в основном появляться значения, идентифицирующие нормальные записи чисел; VS> обязательно используй адаптивную модель). Индексы записывай тем минимальны м VS> количеством бит, которое для этого требуется. (Hапример, если всего VS> индексов VS> 13, то требуется 4 бита (2^4 = 16>13). ) Кажется я почти понял. Hо только почти :-( VS> Данный метод может оказаться довольно эффективным методом сжатия в VS> рассматриваемой ситуации. И достаточно быстрым. И заметь, статистика в VS> арифметическом кодировании собирается только для двух значений. ??? С уважением, Denis! --- mailto:mithraen@mtu-net.ru ICQ: 45911752 * Origin: Windows isn't crippleware: it's "Fuctionally Challen (2:5020/1785.1) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 23 Nov 99 10:25:37 To : Bulat Ziganshin Subj : Re: BWT FAQ From: Vadim Yoockin <yoockinv@mtu-net.ru> Привет, Булат! In article <943320585@p126.f28.n5093.z2.ftn>, Bulat Ziganshin <Bulat.Ziganshin@p126.f28.n5093.z2.fidonet.org> wrote: > VY> Кстати, for после хорошего компилятора не так уж плох, ибо > VY> dec/jnz не всегда медленнее, чем cmp/jne :) Тем более, что > > Для pentium только add/jne (или jXX?). Единственная конвейеризуемая пара. Странно, по Фогу cmp и dec тоже спариваются с jXX... Всего доброго, Вадим. Sent via Deja.com http://www.deja.com/ Before you buy. --- ifmail v.2.14dev3 * Origin: Deja.com - Before you buy. (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 23 Nov 99 11:54:20 To : Vadim Yoockin Subj : Re: BWT FAQ From: leob@mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: >Кстати, for после хорошего компилятора не так уж плох, ибо >dec/jnz не всегда медленнее, чем cmp/jne :) Тем более, что >в данном случае регистра под счетчик отнюдь не жалко... Тем более, что кроме Intel, и другие процессоры есть. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Evgeny Sharandin 2:5020/755.12 23 Nov 99 18:05:00 To : Vadim Yoockin Subj : Описание алгоритма, используемого в ACB Reply-To: shar@nep.cplire.ru Hello, Vadim! Вcк Hоя 21 1999 11:27, Vadim Yoockin написал All: VY> размыта. Hабить программу не представляется возможным в силу VY> острого недостатка времени :( Сам ACB, как и прилагаемая VY> программа, конечно, байтовый. ;) + исходники acb 1.02 section 1 of file buianov.ha < uuencode by Dos Navigator > table `!"#$%&'()*+,-./0123456789:;<=>? @ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_ begin 644 buianov.ha M2$$!`"*E(0``?G4``(NH+R6`B8<R`&)U:6%N;W8N='AT``(!`(X[#(>-UM+Q MNOFVKJE)I^%F170R.)NZTX^OG1@"-E@B]I+AA;[^Y.5MGB"&A9@Q3R31KNX> MN[BTCRQB7'M+F_]GC.0**P%00G=:W^[1\',`2(>W6/=8%US4/*IMOQ-WTF[* M/5@<P!L4G7)R3"/FC&\F/FV2RY%G25UZI!N$R;B#1BB/%])7J2_/#1>[;FJ8 M`'C8201<7<XIY>8+)3B<?(33@<&>OE?)J'+1E@4)%YDH.3N*;HFVU22%I>YZ M>[<-[CI)L(F_3A]D2B5QT+B>3^9+WNRTIT#6`%TU.<SA(,?M>0K&`-B#0@!. M*DZ6>R:9=2V,M3EWJG/024(U:7F\[KAV%Y`'!2#D7OO2UV@P,DLZL6[Z"39V M)CTOL7Y'KZ'T!+P"`E*6_"D,0ZNA]XN^78&ZI:NRDX*M/OONBGX(P#7)=*$S MU2B@4^NL0#:/R!$47[]*.<.1[L:GQ7SH1G?_)YWY^_7<-$A%(\R?+I8TE=): MFVGXKT9O..Y")!B\KYCBC10PRZM1PS]'>^M/R\V%)(I+1W=61!,7E!*?)UNR M\FK&M=+PY=MYJ1H(&5X=-6P*<Q%6F]XQ$!IWM]K(\[X?GF1$"@2/1Q-VL2`J MM-2[]OXCY[^_WE=^\82$K"[`X"24+634YQ3FO<$O(O6B_3D[2?[-61K"-KII MQ1_\PNW>0I4U:(#YB20!/0Q#Y*N5HG;PH243/O^O$TN[K&[2+G",BC$8[&.\ MPQ2B0.T:2M%Z<XN9M(GQ/`H2N\][.3#P5J>"Q31(8H@!;]^A90-W'6M;=I)Q M.X>:'300>4X-XHCTJJ3M?08!7@",%A]^M`#-ZD?@!UV!19^,!F!87;]TRH7\ MY>H!LU?VD,<(R1/[O&]O6/]^O66G+FJT!78!#MPVY3Q%_AM9Z*VFJ]8A=C.! M\&&X90=#PO&Q=R>O?2$TC?TP],ZC9'GC4"ZV7I!:1/Z#>BA/-!(P(!D0>B`0 M61532&9%172']:1VC(4>YPL40/C+,O_Q]Q^-6BFI*63/;A=A0'\)*8!":@'C MLGTK]G?N"@:CME._U6R'%,/W@J*+!QHL6B%/XB@GB^RA(U%#NH'S8@\M?=-- M\1WNG&X!@(M#,I2=A5]Q`83^&8QH==RJN"'_R)O%AIVH(*\5;,W0&8/CBVYC M(5$J;S5R4TCFWM&AN9?SXK^Q-H[;ZB<U`E@^'RE6']P]QBWX?.$03B08(V], MQK$GG'R_@%FPZH$M\V7UER826VRRT5>DMX1%0N_2/]J:9CBN%0T`PZJ'Q&OB MBOK"B'49%D41!=:O&Z/T1-+#`J]F9[1.EXW]IZ#5[:;#T,356_&D6VQWK7DC M%NCKAR6GXOULD2TAUL46.#/FX8:^AKP@SIH=D'XX"1@YS,`9MH5;@5'*Y^YG MN`?)='$$V8ML2U4D?2G\%N(O9S7D/90C>XW[0NJ(P=(\@\LW(B6M=;]+%1G^ MR@RI=B#]6W.G8-ID,<8!$A'<9<ZT90*.HH`7X"!\)%&>FO@&E8NB+0W%7,K) MV]03I0-]6.ZY):]/)Z!ETAHZ$9"7>9IM^$Y9)K(WA66-;:1K6NK\ZQ.9!Q8* M0H&79?EDF_5HQX4N7?TP4=QS)7RWVF21ZH+/7_R)D]Y?]D"':U$5PYSA!05? MQWYD")8'A-)LZ8IF[JM/=>_VB>K4!L0"52TOK]-COU$?^],`<M7(;2)Y2C+. MX:'HD-D/N-`!N^&'8+&%BKCV*=U1V:"@AY8V7U%++U+!4P(AF<#("QSTG=.I M)8ER`#=JV`H,FIW#I$S<G;5/TD&!58K)I5M[,I27Y/33R<]02(S^U"F[6;OH MG^"P)>4'Y-4583V0<P./52"CKL^N^`+84L?X`H2'</^E(*<17?P2<L)=UY0L M2ABY]<JR'USA/^SVG@$KC1.YP&3'YM5!GU.K;OU*8M*CZMW?5:'9<RHRC,E' MI\-:OEL:\>)\NE\JB=LK#E2.A_*T`@0Y(W/EDG_TRP@SH!9%9#&QR:P!XUJ5 M^LTW.+K`*1WUQUPHS$K*(IL,]:)G%7UQ!2O?Q?:Y]/EN72M%]BKZ,V+#VI6S MP2**=137FC]S,QX!K\RGL>GO?;Z&24<K/R7SDP@<,6#KC5KH9M`?0CE!)58, MTL#.QU^]OH?9&]C=_;*+X/WVH)Q,.GQ'ZLS<",:Q!6#?TA8V=.0:9CH3`]@! MT4A^[F2-?@;\H@N`(`U?@^=SHZ`0(@;HG1R)XW'Q3.ZK]X>,<NP[59P9X!!W MD#=ANS6F5\VQQ<52S>00";"X=>I^;X0P=_`G1O@J0VF;*HC5_"^F&(2;OVLI M5EW7!M>1B7$:=AT\.?-.6"PM[(A5%$M*+6.'";&),M'I/D3#6M3O0%N2[2K! M'B:EJ-GBA!'\#G?NG8"G!'`(K)<I)[QH;OS5EG;L0BTDA>65K_"V#ME/15X' M!"#?((MVX1]&N:/4B?O!P&&V`5+1;`,?KSNI`V#M5&G+W^84<`,(]A4G>X#N MU]\]"ZP(MJCW)R3]5?"TP^4XM#VI_%C'9DA)WTTS=F%?LIB]O/._96QUJP+J M%4W`#XSI[H@_Y_UDC%T#8"K46/QL1*BR7XV,.7_E`[EQSCX)F[^ZE^OL?36% MQ(`G"ZRWRZ]_/&^2^X66*2`:T<!AB7G)S/6:@KVHNO.%N>*[O"4129W"^EP8 M"<G&5JAX\Q6*?)'L9=GXQINWN,Y+(!0<1&`=LH<>0!$-?G9)A$_<W[[6H@1! MK%,4Z*C/4-'&X:%B9S]SR4=K-K;)7_VO<83^Q:/&KQ\=%<S?M);T>([O1^"" M#7CD-]VR"KO'SM&S7O!BH('3K@W']<[6%UUOAL.*)OV3BCN[0_T6(>U<&9.Y M8_I&=R.<BMX`"UQWUXF6J3>A['"N=.!NK[_,!C=!V(+Q!8P`U7:J%9>!O4EM M$#G^>`F3]17K#5,N"X`2O-C4*9@0$]&8"(>?LD+8#=IV6-6T==/3:_!TBQ<% M#8\,<E-3BI1VN#P:=R&O4F%YXYR7(S6QE$O$NBMR5?$J!G/5VT0?CRQ];"H_ M.@ROQ^DN5]0)@I'TWNA#&X`HI*720;-^;K(*H>MHRB_%_"\>:8^GE:1EL&T# MH=/2:W\9'D`W]RH5R"GP+_#X0,[*192YHH7J847<K-Y0A$'"0FH8!W8=82JW M17R'1]MX711'#UQT6A%:!V1HANAM%G40ZV-)I,UW*87BA["[5Q05OF..)])O M.8SQLV_H`W4A$"E707M[%G%?W0*0H4/O<`:^OG+MRE$7=^U<JT0&S!)+?='7 M'KU<&#?.AGHB/0+]YS#QV=]W`P*IM"T4*:"DW1K1H/JSLSMB09XDMAAM82:+ MG)!`:=![5ME[RF2@='R0"O]5C_.$L'*X1BQ#K,QP<@^R8K16_?4:+51*+86" MYGQ>`/S.B?AC[_'Q!"M88\47=I7Y1!>P66[%]=6!X1L.N:B7!BE,CCM/W)7K MVC=*P:2M4Z1VQ;7ZKUJ6(&NO`6<]SPP'>-A^,5PU0Y4GKEZJR0BAO:?/C>TC M87+WLQB*X10)]T&IU;HKLI4*K+P3Q.=>TT6R(X.3'D`WAE0#`I&R1HLQGJ4Y MBDLM)AUD[=K?=#@87F5N8XX1JU"!U_@8C=EGN8W&CE#4^C#D)-V$O%W*HQ!' M35F-W%?JVO\.Y@`/G6HHWL&<LU5CI"G9__BZ$)HAJ($.VT@`U.I+]/[Y5?5K M!@8L;7DQQ;XS+>NX:Z73A+7ID3&_..>IR^51QA?@SD_N#4)\%#QPDPY'_$F8 MIMU\]ZT-X>ML#F*A;0M$3?7.8?;P0D/?ZK;!Q":Z?<#5,8?*&)]#^<%#R1[? MC)D(O-\N-??M615S!TLZ1K]HE")EZRZ[[C$B(*<S;_VI&-D1V('&1C;YKPT" M$`,7?]>5:+)PVGMMWGF+B_QXL>JZ47C@]<O#88/]!C.]<QQ<85N'@Y7)-$Y_ M,WK2L/H"]\R5?J:T:7&X;K.!(9'!<6-ZK,^Q#^&MX.S3N1C)T)^>NS?W(Q>9 M*!"M4W$@S-@Y5&IZ.Q+,9ZX?]YCW>:(0-KJ8ZA&M:OLL+W$6-1Z^GF<T5MS* MZY0OQY\Y2EHDD%XD8D99C^%?-[[#3-OE[[#,9$;#"'2-<Z[CT-61*%@LZ;XA M1?T%5U0_O*01F`Y"SXV_+JA84K(B$6KN>6W*;X\L$OFRE=2I?YCG;JU-'J85 M59W&XD?4/<S)O(^G4LZR8YW(`1N&Y-WN$VXA>S^EI<D/ZH6>`A5*P/,@<KTP M300,\@"B3X8)SD@[=*=B&J;E68$M&E!$_*3.4[O33F"18<@F>$T"-+5(R"$7 M<ER0/5/T.V9<W53N4F9AE03B`9\X;[T`2>0')8`<-:)`E87RW_G*&TPA)(@[ MD@V:E73JH)39=U83D3,F)MSQ?O;&Y3`8H<5P[KQUH3%S2WXG0VQ=(!5"M?=6 MPI8JT1%!S.8//O=<)T[(Y;/B>J_1TD:;=/:MR2*B`V&JH0V>J=XLBQAV!/AE MAK^*L)N+U_J@JKSD6-[/:48<H(30MGK/:I+UES?TA&#?89MQ2XAI.OSIQ[=" M4N$@J?TQO\F^JD/P==;L+['B[E-PEDVG%)?!.N=7].D+%BYFC.^LYGM1R:Z@ M1D\S:+7J;OVMWI$8F!^BX$KNQ-\FY!NFPY"?@U\:R%R_&1=PA(W4V<1L#H9G M@6<!)]!)<;;?@JI;^*)[_#=Z9;BRN;/?YBE%6K_\L;,+P]-U/O;V"`-+TW*W MBA"$U#^28]R_/E61&[*[:Y(JP$SGX):D0$RL"C'H<4[]1UB:R@B8[MFO"D_; M'!=-8SA1Q;O0IH<NF.M]G<"=-SV/]%5;N-GQ$PY!E4"0*8">*Q#">)2QLK-? M69]`53(R]Y]$FS887.0MWT(QPJ^8'9NH@;\N;!CQY^Y[1)'/IF.C<L;:$T!] M^KR\361A>QHWU;5_%S'=GMC0LDR^1]4FG$PZ:50H%C@ZT&.;L5M/[2],30SB M[->E<0)0[%]=4WX?T-`[@,ZI"21-^8?-:TCQDA(1>\3_^UZ;3N@(2OGV_G,M MR.4V!SEIQ.O/36G8O#]#WU0%FVMJ"Y26A'73]LE6PVNVGS)+(F2U79NFYL.) M&D<?SV$3'65-N=`X?#>#H-73IL";?>)9*Q>,ZPNP6!.&64Q\G:U65X$+$S5\ M$=%\51K1]TX9H]VPF`A<J`21U'+4`U0`(!U.J4&.W'Z/'M&2I3;(,M@Z,:/V MTYDX%OAV@X%"^?K-(V\NEE&'&Q'PY"7;1B>N;Q;"I'&`51RW"RKUM3V!RUX= M3'VCMN<"AGQ3S>Q_?<S;&R5J)'CI83!O+U*^'Y.2[K#02T6)K@`JX57PU55E M.(=<32QSE&(,)GRFK^Q]J:;,W[B6BS,+=\9.WWNZ9F^?A>PO(6,OZ&3#@D*G MDTO>8$$]FCO7JTX(AA1`V>.D'Q_BH=(#\/O2(I"'"C=:;3#AP.F<-ZE,6F^] M.&`\2J1XIF`+##1M18-1>V[;"MQK,V&RD_(S#KF()+"*G]"'Q[Q+.<>E^@K% MZ7LE;?YC\1[E8K<0-QXB=K(I[P$DIGB,W-*,/&C=0SVLH6CAF/PJR*.:U<]B M5,8?Z*XV]LYLG&';,VDY>HY<KFP8,_&!3TQ11=PKX7#>04^!C;+*'SN9/X6N MZ'EQMXT,L[Y(S./WQ?F?]W0RO!PS<?!-QR9=_&:.RI2/C`A!MSTCG2QAM&F* M/NZG[0*S)1AD<=E9Q;K1>+ZPPREE]#RAIQ`1[:OD7PY)W3(S3*0%-8N**\Y? M;X!?Z2F<K[5]C*3O%5U?'ML#5*SI=:ABCUGBNG!>T/4:(SY2CD3.'DM4\[4Y MI&VB\6NNN&MK9US^N#;I'_<AO$U>%95\J>O@HC^.>^#Y`9NRH757Z#6=N(XO M6+KA4HHG:%JIX,>&,!?HQ[;WH?+:>=G,?R@M*!O$HN""UZ?^G&.*:%O):40+ M'U#,`OL(X`?$^_%56`C;IXU%')+C1*]!B_2V[,M((K>)FDM]X@?]"6TW$X\H M5WM$OS?4R-"7UM2>W*<SW`A?K1#TU-P.F6-4C*_A&'Y3;C/Y:(VUZ-P3*-+9 M-%"<P;D_,=2P>Y$W8/3V%Y*'=V\!2BD)?UVN5X7.BH^A7XRML&>@!MZO7&?) M\5!<:K6B+#H6\37L2`+"MD![$>YG&`!ZN!:^AYZ?3>IOKZ1]:B-W:YCZ;`'Z M[\"8YY'#+.U>FDL85QAHAL/VSP;]VE7@6.R)OS3R)4DXVG,S837RVG=#:!+0 MO*ZHX7Q)L;3NF"KN0Q2J'1>J5)>59%%[P5_$/8C0YO4AGB9=RK87)#[-MG$C MH.V*BH?DO/(&U5D(;IIR/X.UOVAWN9P?J%00\=!)10J*WSX3$R?`&]OGGXNG M@%DR9L"6J&..3X_T3+?I!]NO*-&.3!'/+IW-Z(V._4"`=]D*UICJ:)0=SG'V MC="-;9U@\7UI@&J(0/;YG^H'Z02Z^.<]9.^X?5:%3(12S&,'TH9)./J+7..S MKC^C:VU2N"2"5)WUL=P^,C`A.=71E0<%@[CFDNF'6>C0/^&B.\[8QNS?+(N- M<UTO6S(U^6^28U8OPTNEWI+ER'_"3PX4B5OE+JHG0I^W`;@;I<(I^90W*UG( MYKH92RVE_JIK3Z]WRBJ2UP#)-?GPLF1)BI*)-U$V'_?2SMM\D!+XG`O^#6NO M*_V@7^:&'3[FLKO8R"4K29/Z5DFAK`."%%"/%4T"DK`2?#X;B6LI-SP6WSF4 MIS0%6,3CZ.C#[7\99]/$!Q`#[_&SZIM#K1-)\ECE529V&)-A#54YB&+(9:_* MKVFQ_J:7I/P;:K@`EL#7FJTG>O739JNYH+M"N78HKC1"&6N!:MO2PCO6J;@H M(%\0]^8+3%@.'CBU]R8/.ZYW$[AKKM72DF1/Z?5SUP5.7K&9B"G2W"YX?QDS MCH1.;=>2_W`Z5>5/Z!2(!\_:_T%6X&4(?\&V8[D<QZ<7%:3G$C=//8.=3((K M)H+^KR?)\/#8?OW(M^-F\.[6[`G]M$FU,KC_827G.),Z!J^Q0A9#E;P'!N#4 M*V]BP?9`/KSR34_I##J.P7]&N\JX&UW)<]'$EF1S6*":G#>\3'>T4=PTWCLD MS>=**L?PGW;&[EC&((!@=5F5S65AL9A@9U2"X,)@C?VAM["T%6LZPM,@G52% MB$UK0F2#&2/78'71V_5\AJW46W*XZ\[F&">KUD;YR9Y+[-X94(C(Z`F:4&WW MGZ,(">WN"_7(H[QGV(^J6#E><+"/KXB-ZY?.(\^4E:)VBV`C3"8[KXLJ:,Z4 MN_.1V1#:C?'&=!;R%&M>7=#2)PW&[PBJQOU!)BMP7*U1%4W4?"`(;?(['.$$ M`&B:(,_P&/6"X^5IG+9Q7E"X[QA=Q`UB,HF7"&.7#(R*V_]^9@QW6B3/+;/` MT8(A:#',I+DJR1U1#@``,DFG:+7>84>5\HR=BU[V;S+$'LY5A!V1HL/.=&@J M8AV7%Z55BB:'I,>%CF,@E6]'VS"'?QJM@BF@(RX!33$$L,Z\5<*3#AZF\@7U M?=.]I>KVV/0M2GH\NFM_3QC22D`[ZQI&4]Q3<-4NL39JJBIM&1,,+?%T;C1# M?ZI&0!?NE"FXG\G?#X(1-Y/'EPW5PT>JGLR#QUCM9BZ!V<`J@>\>%TA7L<O$ M"9$UN8T,4]Z@=Z(Y%[V>1\CW]_EWWBJ\R5'U]8@RUJ=;/5-!AUH&;^8/-:O= M%3"&@G,;I#M*7LNJ&3-2TFHIO@.8Z&;,'B-,FT$!@'OZV3PM`:>A!!J3(O!> MU5TQ\'M3E^IG!K=[8NG^:&VP`_#6:%VH0$6^K.Q%:UK;LRVC<!)A0Y.E0RC; M2WT(5<'*B^JJ`P^?3#P/II//EQ?KT48`DCK>#/X;K`RFG2":K]>H^3GLY*KX M]K>E]-;R=3[1&V.\LEPN+.7CU)8CTK1$$4^O\Y.4$":&E8@N1ZQ4-T+L"YO; M)QK5H4Y)DA1Z`XUM-:65`HO^KZR\X($@$;E+^5L9I"1I36G]4!P\_*29ND0@ MI7"]Q]1"B_@'<FS3M2Z#`0N>]/5:XS`JPHL4B\=LLC<_/@/%3>(+($OU5)5< M4]\+`2X1KV.W8+;R7TCQ!2WU_1A"RJ#['A@7J&I<LD+<5?UF"!Z5![EYL.:A MJ[7BSK+_1]\R$$]6`OI_C-^+<GFK\4W/OU?C-3NWJ*QTO:1<^:F$J2OQ$,A@ MI-O(*BL`_:&(6;+D(CHKP#BFA`5>.W2+_C'F-8RH6?6N'ECQ/)$(2%>@P=BS M2;5K2=I#@;J8>!2[M`VV3C1U`'E<@NQ?<TG*DI+B@F\EYU[3GVI"KI!H)S<] MR0:TF$,/OU-NE@,].\3'$B-'G_;36A@NQZA"V(WO@B9;_U?DNP7,X.`MJ4Y@ MFQ)(^G%;+=!'@(R/3H\S+$IA^A"2N#YSKP@Y'G>S).8K'(R%#;!Q#GAPA59, M$:%E8$HB%#)"-;1-=R+D);Z75KKW;U:N1_/.<3]L4\4=?8Y?&Q?(3&N:],5T MW$KKN-8'Y#.F4'`'%K$,!+BR$#WZ%$MHP8LT6PS&^4#Z"N6YDY@"T.MP#\,L M&B:9;:P)E,:(8;Y@U^,OS./](+])]"=R5Z3$7@W#1?M,W/#XU%@T:5PC*_A6 M%$Z7H-%O"+,:<JW>T!K--HT8:_O>EB`K74-+OZ)'7#6GFL1Y=PC?U/)AMHQ? M4.P91)8]]_DE]!C.#UG:U^-IAOQ2[T'[J5XPQ3C:.-UN^BD[")\82`J*H)'3 M"DV_5=DD#W81<!-E=J:ZY/U"OYE<XR9M)NG@4OF\PP2+R9'8F<\VJ/J%$Z_O M_CX0<K!QW6'B3AHHA'N?91LNN<:)+'+:0^53Q);W"F+$H#NH]AZSZEM5C[U! M9N=:Q\#D8//N&#ZV@OKNH!Z*C:\$/;']%L03)=H*D&%EUKHK*$5(WV2+4JA[ MV"%7_"CG;"W<BBORK:J*,*L45AN30#G.G(TM(1[G_-T/%%`PL!MY7$AFW'R1 M*%L?:\]]SU,8EC1X]@!UGF4B*+"<WB3N)T6HY]#Z4:^!`\^;>$5?"``@D*%E MZ'F^_EJRY*!1#%22U>X2Z(3'Z'A&U]M<HN8<[RD1$0-U.HM*+/>1-@3DWAFX M2T6>9BB@,HNXW3V1^&N=674`]VHVO-;LJRBG>,H!Q'`II2"C!!%=\`"WOD7W M-`UDW6:6(O4&XGI&B->RKB'9ILNG;)WCXR8;-'<2F^2GO5J9P?&[Q+G)[MI< M.I7N6P)?-)^^J=$9KM337Z.APKD(DIV%T]*V/Y@3A7$?H'R>OGA]:&L.,8T; MT[)&C927W),C!,*>>EYMAB)5Y<BS<R)"19"KK,8U=^W1)N@9*;2+L,R\:\A- M8@Q56:"Z2Z$.Y'0DM-&K%L)+]_=QUR59##2+%[<1:+28#U+<'W^WM+3K`[^? M9,X](!60/$H#5]8TC>X'P:*LUZSTN2JW^5#8&:)\IW/5`!Z3/#I%.#82.Q`$ M!*M^*LO#H)R[HXZ%L=31+91=_40R$3OI2"4,'JK2_C=HT&,-L_[T.[T`5O&8 MVV)15NW\$H%^>RF9+K4SW;AB;]NNA-N#G5N:@]]YRA0Z_$4[O.&GO!MQ5#I6 M5R(2N*)3.8Y`;6GWMB^"J/;W.?\F/]1]=NEG=_;.%OJ6B<>H:2CKG:@_B);# M8U6X5!QFJ$[0-__3PV"*L`#UE!D=)%=XXUB_T7==&Y.=G'+W:#)_#,<"TR08 MH)4J#:@F:!9X>L+#:PI^,AS3,L'\Y&Y=XQ;JQZ1GN_V>?L1GB#22/]Q;>%!> MP$03Z;W',OA#`W935$-==*'P@_#)(WQ;QK7>CX0QD]16=(2EW/)$X&I-$?(2 M\8&T,9`K,-!U.1UT5;COD8S'9F558OO6;-043S:\XUS"G_H0+8&,1N>^=NB2 M88B0E.X._<D0/"JEVI%UP,2CU7-#/OS"('\X3="CE-.6JY-QGBO0\:J(K_E_ M&"8T'I8-:U[#4M&0,BR`(2OOG\6N46>.&(WC?_OXD\[Z%M.;UN?K85/O!81U M(8,/-A`RR5)H895Q('Q1_7$6=V+Y-L[>&KGR_U#6HZM3\Y59I81J6M,A-4KT MNCH5L#`!F@_?2[[9#IV>%'3L&LK6?#A*^-5T3BG9<A^H6T.>8UT/0EALUZL$ M`X`!^R[Y\MQ24C]QMXUP9;#K&,OZCLKC-#\D$!3L\%RE?2IJP$']<W$8QUTV MQ4/W(#L\S(6<'IU/$XFT5R)^Z]5"!8(FVP7D(1EH&N<NPU+9`B@L^Y5C#W-_ M\7QR?7+AJF+`;!%%B%A%EP@/7`63!,&"M:"T,@RO[M7O*2?<(-2`HT!A(TFF MM+644V^SPQZN14>4['I^>^#IN3)75.=3>*HH&Y6GL_U_,;XX`R:C4@]3C"I` M?L6<6,(CGW@P]4ES)N4?8Z<#;@\I*->8V',V2FI->LM[TA,2\Y!:3Q')%%94 M4@LD&<WTW&"*YVN";%?;PM4,<7LOI#$CY,;58:PM1]H&A8F#*/TN"2O$#22J M&PSN"E1Q1#T^BO!5HL(MWN'""EF_K.Z18EG0J^\BMBZ%[JQ,Z8J'L:)Y%EA. MX:?5(E)236Y*1B0)MAS*IWL\T+L82$EUH[IT>*O_N^Y)^F%9)5I54YQZ2'@; MCU#]]^T1VA!'+H-@S1C=M]J"4Q\AOC!*41S`R[JT=J"$!Q-]AXR%ID0"89'< MBZ^#J:ZS*O<Y`T;XU&)T.[[OGF%*IWBVA(W1:)DB2;7')H`MV*"+KD61BYG$ M@)?RLI]:??C>MTW2[R=,:>M._D+[6^+IS7D9$I<!J;PB[\U]9;V8.^E'^$V] M3YV9P7T*XJ&\M)^>1?_XT:\W8BS+&65"U_P\1?OOHM1[`PVPO.!*%GO3^8AD M.5NQYI5B+IR@CE%-&/)`U8I($:E(*-/0?'P&KB3!FX,(9:X,7-&?<#U"%/T4 M?6#(=C0U-<^EZ0RIK1HIA(!M#?O=WIXH-],5KR*2`T.U;$"Q3.G(996KM<IV MY[X\C-&/,T%9OOB.UW\F03N!R!,^".C\"RDC$.VP)_>IG.^XZ@B"G`]>4`TI MP];1<CIE$TD^MZ//`EOJR\IICG,(T9YPKK$.VX;I(7JODH+5F(D,B`6",UI) M3V;SOF!,@E,39V;Y$?%:`@K_5\/8EOF2BJ3JE#>'$:S2)4<[A(YS>4#6O\HO MZ#]M.?8#GU=U.$)R\;<R$GR8UD,`UW.9L/+5P]</'Q^0Z\K=(Q#?;8E1$[XO M6"W8OCA"=-8KK_Q3H,6(B4@<V;.;6H:#(TAL``,K&$CE$_D";RI!Z7A:6MN] M,Q$J$DVC[*VA2V%8.5-H:_F>:"=O)*:)0CN-V96[-+ZSVCA/EV2GXNQ73TDW MW6E2&$V=&J!K@S.!Q^=NV:Y8J-&*G"5$LL6GB,LWZA`A^TUI0Z<"V.5$I8'] M-X*&#BY^>H/5HH1N$:Y4-KH#68R#FS@2_96:4P5(&_46Z"ZLSC\DNRNII(DU M$S/WJ&_V94H$FE]W-::!Q0;PRX!^ZDT'PN@GIAHIB+8)#AM$(Z.?C@)%&0;/ MZ:J(>V:&TE13G]7&&F=J9ZID6[=SXGFEHY7I@^3)Y:<",%.BE3=VBUF6:RII *=@NBHG_QR^G*]``` ` end sum -r/size 63479/12021 section (from "begin" to "end") sum -r/size 7763/8650 entire input file С уважением, Евгений --- GoldED 2.42.G0214+ * Origin: LID, Evgeny Sharandin (2:5020/755.12) — RU.COMPRESS From : Evgeny Sharandin 2:5020/755.12 23 Nov 99 18:07:00 To : All Subj : <none> Reply-To: shar@nep.cplire.ru Hello, All! section 2 of 3 of file acb102c.ha < uuencode by Dos Navigator > M><D"X$;@/7]]*S6+5[\!5TPME1XHHGOV\%QT?P+<54MX-]-)KJG];B\IIO/R M1#5?5T"">"\V-DT/(S`!,6)[V1.D48(3']PFE;KP\*:3T/9`RS2^ZD,\X/F- MLUH"*\\8PC;T8R2"+J9#TCRUMJ1973NJ_PQPI[\V30K)K"4_>/.->WD;U8Y$ MXQ@/49VHS;>'4?,JQ=7S<,[[JOW[EWTP/,D5BB)+SSD#(9/[['58FB^#)+]& MCJ2^(,.8I#G7/][I4^9EN2E:QAHKDR/'G(->HH;V?B<HE"U#GUF4^(O[!1;0 MMH4`_@WL[33?ZC,"O:`'#*HJ%[!U\JMR1IL2%TR>Q<C8Y7ELI;0S9I,'[_.Z M?!2_RJO5A2C>^!='UA0&I@/LT6?V8NA!C=_V'4[)]'6]5!COX/)H0'8W3^&2 MEBRY(W$^8EE'"40F!I;2.$.'I[/$S-7M>4'^-G*QDA+D2ZNBT!37&NUGRP/B MB;(]AZINGO0=13X;<`]!]$=7><[*`V:QPMN6L5<=^O5?8U=&E+@%RG_@*)QQ M";"L[0T.U`6F5W*"]1Z)X4!`:E0BP</V[Z2?Y#&B&;D058D?,ID53.9-#X/9 M2%S=S@8'+A!>(J-5\U5;XM/#YI1'#!CG.N2PQC'R^[CB8GHHMGC,9(5YL!M$ MDG[:VZB&39"'XM=,4[>F\A*/D!V?5):4F^NG^%CXAP&L'T\+0B#0(L/$M-T6 M`\(4H-!J7',ZY6I,M,.MQ&$%0VU';/KZ"0>T-,S][:CI8,?=.C5+FP.PRU*< MZ4CR:$J%.S>'J"0;ZEP6@6U%W%]QQ83<:*'FP'&N-GZZA;*6('G0G6,6'\Z` MF.BX-JEGUD`RI*%I;FJI%/6::5`UTK;!W-`LMYT8*TPG:@=1\NF]3IKDSPN# M*P#DYV]Y:"DJ1\:]%SG:<T0`VL!0[S+AX6L[<F7.!+T#)3@-9=2^QX_V66/9 M#(PI7*$JA3JVB0.)`XK`?/59O\XH>K$I7E8Y_+7BH.+`C2#^&F-J/=X4V$++ M?N&&<.>;5)92]"\>SI;*=&#XI*,KYA';%HD[\2P?FSV<K6E=\?Z[L+E@`Q?] M"MQ4/O<*>:7W;NV=,\&G'X;Q2*`:N<(*">*'J6X:3R:LG[^6>7=/;_H-TFVU M$*%N"#R]R%CY>HN9#;WW31KG(\5J!R4?K?;[S>#F&D1:U`HM+#_2"*"3"R09 MD;SYA@0Q4#`CET7IB_@&A4,>F0=!G\;'7J<\EEP=0J(`Z,?RCKY+ZLZY#F&0 M_L):[)W]SE&,<8\7WF']R@!Q]C9#O6:H;-\&Z9F+#/L>_JNF<IQG+5N&`<DS M'V)9M%8_,KKM0YPG*V%LN;,59%U^PO%UK"C?M]00/P5F7<\#[RX6$NA@$$P9 M)&(U@^4WFBQ;,+76*!T!>Z"7'.1\,00LCXLIV0&&O]VYTNJ>6&XD>($(V*-( M$$R$2*_QK\3V+RLJJ]#[M%P%+RB[XXL#/P"OO/V:=5`'0*)38CXL^"<H\_C! MR1>6/)'B$S$NN(VAWY67R;M2IY3Y1_O<*HR(A=^@?&J\00]0D1+W^F`@"A5P M/FU27QT\$9QC;>+5`S%,44]Q>NBH_<WOF0IAD*?5D<MJH,XKU4Q7,1:?,NB? M7\K5'@"L&"LS/P\/#'IX0#=('/_YTF#!ZF(9U9R(2U9S<L4\%R>973>1@+X# M0A^K"')8X9.I@]]*'O*\KCF0"QN<0,85P]._57+5_&\/_D(-'\65<KF)7>0! M/<\FUN8`CUZ@1"N$B(TGHI%57(HP0^H-=)3M3J^VWY'<\.P*6H,44[/,)ODU M'>B<E(-GPK$JE>?P851'_'"MVD;B[O;]N-BA>#$^D.BU1OFLL&4[DU93G;7@ M,TQA(*T:PL4FQ0X6BO6@ILGQH!"M;S`/W1(8;#FM-5G+GU3L6[\F,0)PUT<[ M:)Q^;17,,HUR/#Y/*S#I<Y0T][YD,EX6Y;2Z0"\187(5(P-U+O?-[\ZWAWC1 MV(T*8ZYC#93Q@AODRH3^4@V,=9@D6\=@H2]F/<C<"_(-.^EB!GD[+K>?X<=? MR?TS.@"E$(`#=^8/PR9D!QFGBPI0GX=\G,':]'\MHTI".L:0[H5.U\FJXH#S M*R2NFGT"%7.<9Z#H.GPMW',]H13?;N=U3=S$F$ZBN$914"C2GFT*#O?23<F- M*(9?8!Q^P_[X2_:H8\PJ_%`*GYV0)HRTX+T.H2,KBY#M]7%`,&Z<!SSX[I1S M(G#:4V+@GP$.".ZX&/>H[Y._%Y659V`.[C21B1!SH0/%#58GU!G)H:=)63_D MM\F4=C[5RME=/=>_#=G)S,AE*TRS!=WQZIN#N8F<0N^>Q4DJ23D/ZW?>J2W, MO^1U6E45/=8<TJ30ZE")O[96,6E)*O4-$]?U-Q$[%.S"7NN"+4[_<G^E@0TC M+9)`[VUL?3!]0=V\(_F:YB@`ZRWA10-YX!!E36<-PDOY8;S35@KHCPZX\@"2 M]#@@<AUZ3LO9\W\8G](NC$!,>M>YNY$*WA/IZY03M-FHD>6:+IIT4W?]@BQ3 MDL,]0T1AQ"0704(6H@?7U0.FO1)<9@ZC=.D@P8!\;]!!5_]H,)^+DOE)-I&S M,Z1$WGD+*J_B6OH^CP7OQGRXJ$_]$DW#L4*OS0,'28&$*H'Z42@<+P=K)9_4 M>,E$FG.=%_N!.$Q)P"07A]S$,/-],0]/4>;_*3]8DK>W=Z#^9^R,_%$%)6$G M*Q,3!'`%AYSY;Z;TLRV>Z+1O7;JEV-SJI_?PQ_^+5QP"!F?,OW>!0KJ1D6=H MA%25K9M\R3QW7UCCG)3T)6S6:_O0:$=_7/]QWIBWA@:2U/<8<'*T2=](\4[V M43Y2S*5!:@=&4!&@?$\V'MC'V06RZ$664829@H19MA[BH7]%X]>N#B0B+QM! M,5[M#P=.5`W;%&W-REA926?BT):$QT]:2;*&J`\FW/E=#'AAAL6<P2.9&M`? M"CM9(3:%N\:<,HVDMT@G2)Z4,6MK@G.FY?69R9['.):'(])!_@O@QT(R,]"T MA-F&\-Q_**(KUN'$:!^@/NB.`;@5@K1%@+^S]EQ2Q0`;9=/NVM^[%;RJ%=?Z M9^`'.=3/\G&FA5"N8.%?0@"`/[4JA-!<Y[RZRTY%-*W+R-L+H9/@@QZ6BHO/ MGR4/R\]B7*/Q/3GQ)-J'V[#XH"L$:XAK'TF.,UWI<C&@5596#V#O7J\(U,`7 M'<"]`H$-R@;P.8X=]-I*82^1?BM\V))1_.8+4QA.8!4S<"L3/A9PVQ$:^85+ M/7HT>Y$^>RF*E!_ZQU[.A4*3+F-;ZXZT3IO<G<*.`XI3@^I,RB.S-RB%3OT% M7W)EWXY=#H-JJ8N@N(NVL?0H"ZB#":,T%=KS<_J<_)^;I^;T;;9'`!J(6U)\ M09;X4[C<>`YQ[%_2F=?4_@<&DFGLOA/_6U'(&(!__26^(I]C24RCHL*2F,J, MRTH7<L<S?L=T6XKE7GHN[WB';"X\>W+++[@U/"'I(!VVA>_HTV`'(2&:4]J2 M[-:)%G>WYMMVI&&"EI%$>B'2.'_6>8];OZ5+(<3!\`^.3+O>*%_7(-#W:)I; MHL=[XS:#@+'B<`OY;*[-+]"BU]>H\#'A\S7ICWQO_QP1\>GKL^8M/6W!3)(? MM*-/0I`++4R('Y/V1.AP,!G)^CT%'6N(S)9>!F(*P\"J;4S[DZ%U!?W*(*#* MV\^&']_D*2&]YB-DJ%=5;,OR4^@RQDW$&20DVCY7AM?XEDV&>C&*]VO#FTZQ MAD(%NLZ9E/+VTIZ)`H:3H(50IT819.A"!J=G>:KX9]!;*C8X:UG&6"A^#=T< MM3W)LIVV[/0RL&19:0\K=_<S)'/0P'-W&M*YF[*09Q4+M+U8Z=QPA]YCQ^8$ M=43S:]NUE(]T>\49`_HK8W)1NY4D`6?S!^XJW/("F?MW:VF5)UQ;!F;4879/ M62KL#U6F?HZY$V?L;Y-+M(:4KJ(@0J2LX(^OD""6490RW!R'`B5T]\*Z>A:J M-Y4)Q3LTD\K6*-^C]]EC(=JZZ4)FWE.:`/ERX1"<)6:=9A=C$O')6OIGU+%< ML-2!A&I_U:5!EV*F^17JKN#!3\$%9X+)>7-,?KU_S[%*4=RG/S'D'UR'>>GT M(55+ASC@C[GGP_`!`_\Y>9[GVI/WS*C(#P)&_',I:QJ/3(Z5F.98]?JR$L[E MR$;XH(_PEW$8H^ZQ7@^!;VJ.FSRM:(I@AAQ[2LR[=\3];U/U.C_@K\W;0DF# MEGDP$F[DYM7Y>AAN0MEPZ6?))YQ4\/3KF9-8BP5:*TS+@N!:6LSI2+!"4OS2 M0K/KS0%,F#9M*]P#6]E"T,2O%7Q`H*H+3KB;N(78`-G8F">U,PZ%@F=U_A0- M$BWOI*<W/2=N@4^@KF/\,>_9OU@&B)DOD)#PN7-"K7.]Q!>D;6K@W#T:D##) M.A)`_+\+:!Q#A1'JR#Z!3Z5X11GHNOABX[%?<`!:RT>O?3%HO=Q:B<G*#R_C M=5-[A:+NQZ1N\GY&:G&;(D0M@_$AM?8R2-2&T@\BDL%^SVH\Y8!.L2Y%-4XE M"RT#Q$Q1,A^ER!#C7O@-.(5B7L13.*;%Q#N?/H7VE)+O3USS4*8FQLM>DKMJ MK!/%D]NOZ0-M0@#AMF7$*N/R_>M5$`PD"<Z03)%4&H,MQ".16+-,5$#W-0%Y M\H94>6L+T_(G[:4.M5@:<.QH&E.N">-;-CY=Q6HZ=OXN>A96[9C[D6SQQ;;[ MOO0N<1-G;2)IX>F?+$E:R0-ZB81NIZ09A:7RBXA/\3@ZNMAVX<=9XMYEL,-D M"8^BG;=\J/Q5IYN+EOP30-RWL-?/,8&-(*ZZLD=\@<*>Y,A+!&UFHYXWJR\S M3+A<YQ[I+=\C!Q\BXPJG&HCL'QCG41TQ;(:591GD#S/ZS1DDM[G\<@6W$&4* M#U$$KCY`5T!(Q%)5I=D_BL>H2JFS\(**_E0%46I]1IO"B'*A+_+'";#7J_$\ M>52OA5N_86.*C**$<J?EH]1OH813XJ@'R,!K_;37!US'HR3.!"L6D(!O2]%J MND&#+5;XF'X')`B#FW)PV.6A\T&44PP&_/?_V<ORCD7[K?<$0K2MVI6E?+@2 ME;=-//?UA]+1_=<WK9SU+EK0%G'7@K;[%-C=GW,D(1R/^\J*:E0G^5G'3;WB M??'P,<!,P%;G<+'EPVVX%OZIPL0+NKEI9O_<*>"S1\\/B7!P5U?HI.6?#<ZW M$$SW!&IUV_YUDB0D5-1[%,M5<W+FDK%#F[3PGO>,+ZXIT2-N6/#H91]5-]I" MX3F#*VDACP=]!6/#CH7-:H+F`=V](3HU1X('%PO2-4-_>/R)-#?C'K)A0NCC M_!6Y`4NM3L3@DFM2*297[>ILU?-R)X[_$S#$[R;X<TS>_H9BR<F"Z108+R&T M<C`GH]T055PPG\2/F,L9-)FIHG7H983!HV>M?,<>(UOM$4XG\3MQ9X#S3:_P M]N1>M82#2U7#P3$S.WFI88^"SY!GI?)UX@31R=9.0+C7CLL#U+Q6(?]8NAAQ MG)*\,T&D@F*&C5DT8#],]\HDAHMK)M-,&$%NH%H9(MC%$<9^`+9M)I-X$<ZR MUV/@@FH;".L0<0)(DV$_4_.Y=/ZVP:TI)#(M03M-$AYJ:X?+!#+M2,N>A(-O ML<*&4^@55<@J<8RI$4SZ>!G5UKI/;?C:*CX@ZI-\B&:SKB554?F-RSDV&22, M/?;GH!E6=O@4BW^;^4M4FP/7>@F`A-`?W\R\Y[C3GQ6$_M*>G:[;+JC>CJ>G M,@G-_$#9I1)BR:\[N)AG?0"A@98!?N53SK-'B8N)48]8<@\2?NB4M3(N5*0U M2$`X)LAAL+$_J>(T\RF&7'HMVR-N(-:55=`1+`,"W.V5DK&XI!"N?7E=IN0@ MJ.BAL0N1>F__&;V/I48&4./)?_S1IG(&4H6+N!AUW?*OH%]]*528*.N'B8]: M$AGQ]_VOQ8/6U"XW=#D7S:LK7CGGG>=*6DH0FI)/HS3%`2_(_[>UM-@/M<"O MBS)9I%H1M)",R5JS@-))=:A[_K5-`X;@!CA<8F\J_K#Q"1'*+*;LC[ECY#3. MN?UEX1IMX]T0*%$S7G-9;4XC59EXNSM_/4L(_-]:%")7*6U^C'5^62)DR\-G M8+]!?G02_%==@%3MD^*\!OCP[?5(;FSIV0WO_P/;Q+0Y">OWS,Z^BP[H1TF> MC=$*EU\-0/[0T/7-R\G$1R$>)U[H+A4>L2@:=.V=K>GO.8KU3)CGT^_PGKOP M;NN%LSREI'@9M'J"4Q^HTG$A(N'.7Z7?S78]XS#-'3&7FR8UO%"!P13"_`-T M&WVLUX*F)6JJEZ=OIH[EOA&4!9M:%H5=)BWRF7?$_2X%H0#4!!$N@<&)#8L' MI,;*6C'X$-4EQ?X/UOYGL%GT8LLIL2*0GP$L&UN--;([4HHI'NV*ZE=5!14; M@9OGRU__QIUGTH6&VS1CB8E%N/.2'H++1[)=U"RQ;IJ$,RA-<Y=TK^"Z-M5I MPR&T8-SQUUVAQUD!KL]MQC%6[S_@L3X2-'*QV!9F7ORVT9<%G*/SFPA8M&Y< M6-Q"6GAH@!Q#^UG?VS7=?0DC:BZT6R5280AS^'S9<_BWI-66?4J'@DP@1;`C MM-:/P-^5?;/G$*7YJ5>K;(=<;G%4$^]0^OPF^.,-$/:8&'KE*B9@`\H(MKY# M%L(A.7SN"<IHI6H7T,4=4^(XY\(,AK=4)_MU&2`[5+6&?Q7%B-+'_QEDT*1% M6^=4HTMW\-'1)FS&3_"BJ2AMPJ!&4SH/GEO;'HPEW"/`:HPR=679+UR!Q`!5 M#(&%FE&(!@QX--MT!+#J`5L$%FB;G\/N``5@L":N7_3+SI$JV9XSY6+YO1J> MXL5W0?&H4\B.@9\DI3ZD=)K$A21476![3L#2W[NO^;?B.D$IF,_X2+R9L<YZ M5@GST0),,#/K!?V+BDNQ2%!5!J3`<Q>W//,*(44#(T;@)>EQ4?:,JLP9`WX" M="*>'0``#V@``,I)]@K<\)0O`&%C+F,``@$@+T(D"*-#9=6VD9Y_3/T9_%#F M%G!F=/#1[*\?:MK`DI_R.#:;5)QETP+R;VJDO%`;7=PL1:X=BA[JU8**[T0H M"8;51J#@`&^=P,1;?"X>YFQ2L;*GL[]@A0IR^`QDQ?W$"2RX@ZP*[Z^J*[2E M#R<0(,V?^YD5I!<;H@[A6@G,9#PUQB"P-;JLQ'\5V;I^H1V>9EJ:\CN?@.KO M$DUN@T?8:4\X?`2[J\20<TBNFNV!59.T6_3-.WP#\GU/$D\O%(DOE5.9,`+6 M9QH!HF#MBQ8H0T8Z*<7*;T^&'51X$MXZ^CDD`C0?8?75](.R^;X8P3W.ZF#Y M$YT,2'/07%QC0*0=>WG^'ZAM%U\'V+CCJ^2TN3[!H5=:URX)DR74R28E.9$( M7-'FM/XC*5KS?[T=TQR`]F4T-X&B/WZ(2*K$4+<+2@1-X+ML*U1&"W<<NOAC MFHIVJ;,;4%7``VGBMWVKYP8%-`R0U'0^REBG7GN54"ORV]R$5E[\U81)*:Z: MU%@$?DN@TB"VL!:_,]D#!A$FD]^]>G\L0NVS6,7W'A*^=&SMJ,^F=?W@W-,W MW+MA5?0/(-G<0Q"<4SI[&OU,>ZTD(3?7JS;&LZFV7+4<,$"I8H-6>0B!L?Q[ M'1.<'?$O@A6JU)OYP"GQM!RW)I6G+$"(02?>O)(BG5AK*Z"&K=0%9J4?@NL= M8EQXR9PH,M@<Z"17-G=$?4Y%?_/%?*S=$_0)P-F))6R-*V[0.PVXA#N-[22T M=JDUXUB>H?]>""+&9C,:CQ*V(*-5,AK">WD]W;5A,.G(Y"UR_R_!3KQY"4@U MT4PVF[TBD4Z9E&546$@`%26CH;E=X#?Z`E@0/FJ5-%+$7:N-)-OA?J/R@"U0 M\6D3Z#F`T+=-+(QF>94>?Q.JU5);D#0D8$FO\O;3]BHQ%88H*Q30((VTQ#_= M$N;V*WYB2#5BWQZ4H&%$Z0HPC>YT%8.4LI,6$R!5*F[%^>VZ.C##$SDT.-08 M'J2C2ZAYV?6E,%9O1E&1CZJZTX6D>A2V0YF0[^DL(%&F>'Q"8BB#?PX7DOSM M32CGIA.KR0O+S'8B:1%,6(V%&+)=?9ERE0C9K8RBW-"U\6T@ND<$Q4`')05; M%,WE$\5?HZT4SC%5^FV8@_?XNI*GUDU"4]6/>RN7M64.(YA7QG.,)Z@7S-S* M*G>F*K@""'_1:N@130`HWD`S6"+!.B6`;C/(_5HDFY1';3HX&+VI<>,UJ(?$ M`QX<*Z&2:GP@01!E0R29HGT'U*3&RTRQ6>BF>5+S,X5":/OH90//:$G>VVS% MZVZ486M1A7,\:J%5A7C[E-E_0YX9U@PU!QQTL;M%$J3+[O/&6OU[9RS?Q;EI MC9<[`JIM/]RS)N@)$W(_)[8)&E?IV0(H+778U74L!A2]XVJN7J;@VE*N$TL. M!L(?I#`*+7!35?U[$!JD"1TA82/QQA-EB-CYPY-8Z@@4%P15A,R4=9FL9\^Q M"7"\$M3@[GJKVLP.9\M'3+R!?JH!,K)N!41:"@\"\P)<+A/FU-F&IJFY'H2^ MJJ5#CG9V1NHLC\_0/IGO/3%F645IE#-/%1$@I6)I!O85.`\,M0?$LM-JSK=- M4]`)BJF[9-(;)4T")UD_4SF[>LL4T2=L@M>$AQY@]22<X+PU5G'2CX;(7W0F MZ_TA9%GZZLF(S",/T<P3?9E!ZO$5%;_T;]V:/$394X4+FA-JC7`<V[Z8GDD. M=>&(K=G2RC=3:2%9FH8!"A2`7)E"W*#.7>6@C&WT.EUH&U57_3FDR;0*70'* M]CLEL+U:VE'RSXN">T;W\+?="E>*I>Z[5>7N)9U6:GH#$=%TRE.!?7?PJA5D ME3$.>A+&Q^4PJL_,%%VC/4\&S6;']'5M_!DSJ*#V4M%GHP<)4&R>IH3#,JQJ MWYA`:AZ,**C^_-TXK32`WN@,E.8_^CZV$V0>K$KH.&585UT,U&HCYKYH35`! MH<SF+7B11$T7@*&PT>15QZ9,0T5+B(2L/%:L9YJ!+8@D5MU4MO3>;#W0D]:) M]W0A9!70<H[D_,+PW%FQ=K1+`O\V^2Y>QL).<_YHL#O9RR,A)OC=3*MY#EY< sum -r/size 28321/9300 section (from first to last encoded line) С уважением, Евгений --- GoldED 2.42.G0214+ * Origin: LID, Evgeny Sharandin (2:5020/755.12)
Предыдущий блок Следующий блок Вернуться в индекс