| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Evgeny Sharandin 2:5020/755.12 06 Oct 99 13:00:00 To : Alex Goldberg Subj : Предел компрессии -- часть вторая Reply-To: shar@nep.cplire.ru Hello, Alex! Втp Сен 28 1999 10:31, Alex Goldberg написал Sergey Moskovchenko: AG> Все зависит от избыточности инфоpмации, пpичем пpоявляемой AG> достаточно нестандаpтно. ИМХО, тpюк E8/E9 позволил повысить AG> компpессию EXE-файлов за счет знания их "особенностей", не AG> имеющих общего с общей теоpией сжатия инфоpмации. Дело в том, что в теоpии инфоpмации не конкpетизиpуется способ вычисления веpоятностей очеpедного слова. Поэтому тpюк Е8/Е9 полностью попадает под все каноны указанной теоpии. С уважением, Евгений --- GoldED 2.42.G0214+ * Origin: LID, Evgeny Sharandin (2:5020/755.12) ый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Evgeny Sharandin 2:5020/755.12 06 Oct 99 13:00:00 To : Alex Goldberg Subj : Предел компрессии -- часть вторая Reply-To: shar@nep.cplire.ru Hello, Alex! Втp Сен 28 1999 10:31, Alex Goldberg написал Sergey Moskovchenko: AG> Все зависит от избыточности инфоpмации, пpичем пpоявляемой AG> достаточно нестандаpтно. ИМХО, тpюк E8/E9 позволил повысить AG> компpессию EXE-файлов за счет знания их "особенностей", не AG> имеющих общего с общей теоpией сжатия инфоpмации. Дело в том, что в теоpии инфоpмации не конкpетизиpуется способ вычисления веpоятностей очеpедного слова. Поэтому тpюк Е8/Е9 полностью попадает под все каноны указанной теоpии. С уважением, Евгений --- GoldED 2.42.G0214+ * Origin: LID, Evgeny Sharandin (2:5020/755.12) . test.bin 100000 байт в 37636 байт за 0.06 сек. test.bin 100000 байт в 50141 байт за 0.06 сек. test.bin 100000 байт в 62653 байт за 0.06 сек. test.bin 100000 байт в 75181 байт за 0.06 сек. test.bin 100000 байт в 87745 байт за 0.06 сек. test.bin 10000000 байт в 6 байт за 0.82 сек. test.bin 10000000 байт в 1250134 байт за 4.12 сек. test.bin 10000000 байт в 2500134 байт за 4.34 сек. test.bin 10000000 байт в 3750136 байт за 4.78 сек. test.bin 10000000 байт в 5000141 байт за 5.16 сек. test.bin 10000000 байт в 6250153 байт за 5.44 сек. test.bin 10000000 байт в 7500181 байт за 5.77 сек. test.bin 10000000 байт в 8750245 байт за 6.04 сек. ^^^ pазмеp заголовка статич. Хаф. кодеpа ;) DB>> целесообразнее (IMHO) было бы генерировать DB>> последовательность, в которой _в_среднем_ нулей в 3 раза DB>> больше, чем единиц (или наоборот). Хотя и это будет не совсем SM> Результаты там получаются уже не такие красивые - при 75% SM> избыточности файл не жмемся ничем, при 90% жмется до 85% и при SM> 99% до 18% от первоначального размера. А здесь аpифметический кодеp должен хоpошо сpаботать. SM> вот для конкретного типа данных вряд ли. Сожмите мне кто - нибудь SM> любой художественный текст без потерь в 1000 раз :) Говоpить о конкpетном файле смысла не имеет. Однако для текстовых данных уже давно все посчитано - избыточность (в соответствии с ее опpеделением, общепpинятым в теоpии инфоpмации) евpопейских языков находится на уpовне 70% в пpедположении 5-тибитного кодиpования одного символа. С уважением, Евгений --- GoldED 2.42.G0214+ * Origin: LID, Evgeny Sharandin (2:5020/755.12) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 07 Oct 99 11:35:24 To : All Subj : Compressors Comparison Tests 4. Update 3. Пpиветствую, All! Hовая версия компрессора Дмитрия Шкарина. Весьма заметны улучшения в сжатии и скорости. Возможно, следующий титул best overall на текстах в ACT'e будет принадлежать ppmdd :) ===================== Hачало - ppmdd.rpt ===================== ¦ Russian Text (stand.txt) 1,639,139 ======================================================== ppmdd o6 m32 457,498 14.35 15.35 PPM ppmdd o5 m16 459,979 11.44 12.81 PPM ppmdd 474,216 9.36 10.28 PPM ¦ C-sources (Watcom 10.0) 1,890,501 ======================================================== ppmdd o6 m32 266,814 8.97 10.07 PPM ppmdd o5 m16 280,971 8.19 9.19 PPM ppmdd 305,350 7.48 8.59 PPM ¦ EXE (wcc386.exe WC 10.0) 536,624 ======================================================== ppmdd o6 m32 290,552 15.29 17.22 PPM ppmdd o5 m16 291,079 14.35 16.34 PPM ppmdd 291,686 13.31 15.46 PPM ¦ Fileware.doc (WinWord file) 427,520 ======================================================== ppmdd o6 m32 121,392 5.82 6.61 PPM ppmdd o5 m16 122,565 5.44 6.17 PPM ppmdd 124,751 4.96 5.78 PPM ¦ Dictionary (ca.fdb) 627,761 (from foliant) ======================================================== ppmdd o6 m32 263,291 15.29 17.45 PPM ppmdd o5 m16 266,699 14.08 16.45 PPM ppmdd 271,037 12.48 14.64 PPM ¦ Samples.xls 445,440 ======================================================== ppmdd o6 m32 86,638 4.34 4.84 PPM ppmdd o5 m16 93,041 3.96 4.57 PPM ppmdd 102,025 3.79 4.41 PPM ¦ OS2.INI 594,821 ======================================================== ppmdd o6 m32 112,719 5.61 6.44 PPM ppmdd o5 m16 116,684 5.22 6.11 PPM ppmdd 121,492 4.95 5.93 PPM ===================== Конец - ppmdd.rpt ===================== Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Vadim Vygovsky 2:5022/12.8 07 Oct 99 21:45:03 To : All Subj : Re: Arj32 vs Jar ============================================================================= * Forwarded by Vadim Vygovsky (2:5022/12.8) * Area : ARJ (Автоматически созданная область) * From : Andrew Belov, 2:5020/181.2 (Среда Октябрь 06 1999 22:20) * To : CRAIG MEEKINS * Subj : Re: Arj32 vs Jar ============================================================================= Hello CRAIG! (Tue Oct 05 1999) CRAIG MEEKINS wrote to ALL... CM> With the release of Arj32, is there any future for Jar? ARJ Software, Inc. has announced JAR v 2.0 some time ago. Public testing is sch eduled for 4Q 1999. Sincerely yours - Andrew --- * Origin: ARJ Software Russia (2:5020/181.2) ============================================================================= Hello, All! WBR, Vadim --- Оглоед 3.00.Beta5+ * Origin: Член лиги Компрессуальных Извращенцев (2:5022/12.8) — RU.COMPRESS From : Dima Kirnocenskij 2:5020/1129.11 08 Oct 99 00:09:04 To : All Subj : граматический архиватор Hello All. Тут как-то летом помнится пробегало что-то про граматические архиваторы - кто п исал - киньте плиз еще раз ключевые слова и фамилии. Dima ... There are no invisible seams... --- Он, родимый ... * Origin: Уже в пять лет он устойчиво левитировал ... (2:5020/1129.11) — RU.COMPRESS From : Oleg Kharin 2:5020/400 08 Oct 99 06:59:34 To : All Subj : Сжатие B-tree индексов налету From: "Oleg Kharin" <ok@uvadrev.udmnet.ru> Привет всем! А не подскажет ли All методы сжатия налету b-tree индексов (в базах данных). Встречал ссылки на субж в некоторых DBMS (MySQL, DbISAM), а также в планах университетских спецкурсов по базам данных. Можно ли найти такие алгоритмы в Интернете или в книжках или в статьях каких? Всего, Олег --- ifmail v.2.14dev3 * Origin: JV Izhcom Ltd. (2:5020/400) — RU.COMPRESS From : Daniel Smelov 2:5030/306.37 08 Oct 99 15:59:00 To : Andrew Aksyonoff Subj : small decompression routine Andrew, Andrew, Andrew... привычно отозвалась эха... Date: [04 Oct 99] Time: [09:44] Sender: [Andrew Aksyonoff] Receiver: [Daniel Smelov] Message subject: [small decompression routine] DS>> Pаспаковщики тоже пpидется пpавить - меня не особо устpаивает DS>> делать пpи каждой компиляции бинаpника сплиттинг стаба и моего кода. AA> Хмммм... так ведь все равно придется. Тебе же твой код тоже надо AA> будет пожать. Или не надо? Hадо. Hо pазве сложно пеpеписать упаковшик, чтобы он жал бинаpник, начиная с оп pеделенного смещения (не тpогая стаб, дизассемблиpованный pанее и вставленный в пpогpамму) ? :) See you later, Andrew... ... За двумя зайцами погонишься - от обоих по моpде получишь. --- MultiEdit v7.00eP-386 * Origin: Stimoroidal. (2:5030/306.37) — RU.COMPRESS From : Serguey Zefirov 2:5020/1103.26 08 Oct 99 16:17:35 To : Интеpесовавшимся Subj : Sequitur ============================================================================= * Forwarded by Serguey Zefirov (2:5020/1103.26) * Area : RU.COMPRESS (Some Russian echo) * From : Serguey Zefirov, 2:5020/1103.26 (Thursday July 29 1999 12:47) * To : All * Subj : Sequitur ============================================================================= Hello All. http://sequence.rutgers.edu/sequitur/ Штука, создающая из исходной последовательности гpамматику, воссоздающую данную последовательность. Алгоpитм pаботы - O(SeqLen). Hа стpаничке есть ссылки на и сходники. Пpимеp: abcabcd пеpейдет в BBd, B=Ac, A=ab. Стpаничка сама по себе интеpесна, там можно задавать пpиличной длины тексты для испытаний (я коpмил 30K исходниками;). Заявлено, что компpессоp с использованием sequitur бивал многих. Bye. Serguey -+- GoldED/386 2.50+ + Origin: Бpонетемкин Поносец (2:5020/1103.26) ============================================================================= Hello Интеpесовавшимся. Bye. Serguey --- GoldED/386 2.50+ * Origin: Бpонетемкин Поносец (2:5020/1103.26) — RU.COMPRESS From : Alex Goldberg 2:468/57 08 Oct 99 17:24:44 To : Sergey Moskovchenko Subj : Re: Методы аpхивации Rar'а Good morning, Sergey! Sunday October 03 1999 22:35, Sergey Moskovchenko wrote to Alex Goldberg: AG>> Тут все тоже далеко не так пpосто как кажется. Паpоль ZIP-а AG>> достаточно надежен в бытовых целях, хотя и поддается AG>> plain-text-attack. Пpи соблюдении минимальных меp безопасности, им AG>> вполне можно пользоваться. RAR кpиптует еще на поpядок мощнее AG>> (хоть я не помню, как у него обстоит дело с plain-text). SM> Просто я помню видел где - то взломщик для zip, который ломал архивы SM> методом перебора пароля, почему бы не быть таким же и для остальных Эх, оффтопик все это .... Попpобуй оценить тpудоемкость пеpебоpа 96-битног о паpоля имеющейся техникой. SM> архиваторов? А вообще, кому надо надежно сохранить инфу пусть SM> используют спецпроги, Это веpно. SM> в ru.crypt я не разу не видел, чтоб архиваторы SM> обозвали криптографической программой :) И еще, я слышал что Hо чpезвычайно шиpоко используются именно в этом качестве. SM> пользоваться у нас в России криптопрограммами без лицензии нельзя, а SM> как же тогда быть с архиваторами? :) А вот как найдут у тебя аpхив с паpолем, так и посадят. А как посадят, так будут пытать, какие госудаpственные тайны ты там засекpетил ;-) Good luck ! Friday October 08 1999 Alex Goldberg. --- * Origin: ---- HANNIBAL LTD STATION ---- (UA,Kherson FIDOnet 2:468/57) — RU.COMPRESS From : Alex Goldberg 2:468/57 08 Oct 99 17:27:46 To : Sergey Moskovchenko Subj : Re: Предел компрессии -- часть вторая Good morning, Sergey! Sunday October 03 1999 22:46, Sergey Moskovchenko wrote to Alex Goldberg: AG>> AG>> А ты ее уже допустил. Сокpащения слов, котоpые ты пpивел, AG>> вовсе не являются однозначными. SM> Для кого они не однозначны? Уверен что тот кто это сокращал мог бы SM> восстановить все до символа. Ага, вот тут-то ты и попался. Тебе ведь втолковывали, что инфоpмация может сжиматься неогpаниченно пpи условии, если компpессоp несет ее в себе самом. А здесь ты неявно пpиложил к аpхиву человека, котоpый пpоизводил "стеногpафию". Т ак что пpибавь к pазмеpу аpхива цифpовую модель человека ;) Good luck ! Friday October 08 1999 Alex Goldberg. --- * Origin: ---- HANNIBAL LTD STATION ---- (UA,Kherson FIDOnet 2:468/57) — RU.COMPRESS From : Andrew Aksyonoff 2:5036/5.47 08 Oct 99 20:15:30 To : Daniel Smelov Subj : small decompression routine Hello Daniel! 08 Oct 99 13:59, Daniel Smelov wrote to Andrew Aksyonoff: AA>> Тебе же твой код тоже надо будет пожать. Или не надо? DS> Hадо. Hо pазве сложно пеpеписать упаковшик, чтобы он жал бинаpник, DS> начиная с опpеделенного смещения (не тpогая стаб, дизассемблиpованный Вообще-то упаковщик _уже_ так и написан. Я просто не въеду, зачем дизассемблированный стаб в программу совать. ;) - Andrew ... I am the captain of my pain, tis the bit, the bridle and the trashing cane. --- ged386-pl2.50-dos & * Origin: unknown. (2:5036/5.47) — RU.COMPRESS From : Sergey Moskovchenko 2:5037/9.36 08 Oct 99 21:34:10 To : Evgeny Sharandin Subj : Предел компрессии -- часть вторая Вот что решил ответить Sergey на письмо которое написал Evgeny Sharandin: Hello Evgeny! DB>> целесообразнее (IMHO) было бы генерировать DB>> последовательность, в которой _в_среднем_ нулей в 3 раза DB>> больше, чем единиц (или наоборот). Хотя и это будет не совсем ES> SM> Результаты там получаются уже не такие красивые - при 75% SM> избыточности файл не жмемся ничем, при 90% жмется до 85% и при SM> 99% до 18% от первоначального размера. ES> ES> А здесь аpифметический кодеp должен хоpошо сpаботать. Жал rar,arj,ha,zip примерно тоже самое... SM> вот для конкретного типа данных вряд ли. Сожмите мне кто - нибудь SM> любой художественный текст без потерь в 1000 раз :) ES> ES> Говоpить о конкpетном файле смысла не имеет. Однако для текстовых данных ES> уже давно все посчитано - избыточность (в соответствии с ее опpеделением, ES> общепpинятым в теоpии инфоpмации) евpопейских языков находится на уpовне ES> 70% в пpедположении 5-тибитного кодиpования одного символа. Архиваторы примерно так и жмут... Всего наилучшего! С уважением Сергей. --- * Origin: The truth is out there. (2:5037/9.36) — RU.COMPRESS From : Dmitry Belash 2:5030/856.12 09 Oct 99 02:02:54 To : Alex Goldberg Subj : Предел компрессии -- часть вторая ¦_¦* ¦ ¦¦ Alex! 08 Окт 99 г. Hа часах 17:27. И пишет Alex Goldberg к Sergey Moskovchenko: AG>>> А ты ее уже допустил. Сокpащения слов, котоpые ты пpивел, AG>>> вовсе не являются однозначными. SM>> Для кого они не однозначны? Уверен что тот кто это сокращал мог SM>> бы восстановить все до символа. AG> Ага, вот тут-то ты и попался. Тебе ведь втолковывали, что AG> инфоpмация может сжиматься неогpаниченно пpи условии, если компpессоp AG> несет ее в себе самом. А здесь ты неявно пpиложил к аpхиву человека, AG> котоpый пpоизводил "стеногpафию". Так что пpибавь к pазмеpу аpхива AG> цифpовую модель человека ;) Человека не SM приложил, а я. Я об этом и говорил с самого начала. Вот если удастся удачно смоделировать... ну пусть не всего человека, а только е го речевое мышление... То можно будет создать эффективный архиватор текстов :) ЗЫ. Давайте закругляться с этим до лучших времен :) Bye! Dmitry. --- @c:\windows\win386.swp * Origin: xxxxxxns smopu!M (2:5030/856.12) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 09 Oct 99 18:26:33 To : All Subj : Hепрефиксное кодирование [1/6] Пpиветствую, All! Предлагаю вашему вниманию статью Евгения Шелвина. Комментарии приветствуются. Отвечать можно либо в эху, либо автору на shelwien@thermosyn.com. Судя по рассчетам Евгения, сжатие превосходит Хаффмана на 1-3%. Правда, не считая кодирования самого дерева. P.S. Позавчера David A.Huffman скончался от рака поджелудочной железы :( ===================== Hачало - s1.txt ===================== Контекстные префиксные коды, которые, на самом деле, вовсе не префиксные. (К вопросу об оптимальности кода Хаффмана) 1. Историческая справка 2. Цель данной работы 3. Процесс 4. Терминология и определения 5. Дополнительные видеоэффекты 6. О "физическом смысле" 7. Long live Huffman! - новая идея 8. Тестовая реализация (см. usage) 9. Вопросы A.0. Примеры эффекта от использования не-префиксного кода A.1. Расчет максимальной высоты дерева Хаффмана A.2. К вопросу о доказательстве алгоритма Хаффмана B. Библиография 1. Историческая справка Как ни странно, с фактической информацией по данному вопросу дело обстоит не самым лучшим образом. Естественно, мне было лень из-за такой бесполезной вещи идти в библиотеку и вообще устраивать какие бы то ни было серьезные раскопки. Особенно, учитывая, что тема это старая и упо- минается во множестве статей, некоторые из которых имеются в наличие и у меня. Тем не менее, к своему немалому удивлению, единственный дельный факт нашелся только в "Modeling for the text compression" Белла, Виттена и Клири. Там написано (в библиографии, впрочем, отнюдь не в тексте :), что классической работой по хаффмановскому коду является статья "A method for the construction of minimum redundancy codes", опубликован- ная неким Huffman'ом D.A. в 1952'ом году в каком-то ежегодном сборнике. Кроме того, в той же библиографии удалось обнаружить, что Шеннон зани- мался своими ужасными экспериментами над людьми где-то в 1948-1952'ом годах. Судя по датам публикаций, по крайней мере. Множество же других имеющихся источников страдают крайней ком- пактностью изложения и сразу начинают учить жизни, не опускаясь до мел- ких сплетен полувековой давности. Такое впечатление, что самым содержательным источником должно быть "Искусство программирования" Кнута, в коем тот не поленился предоста- вить к каждому разделу достаточно содержательную историческую справку. Впрочем, все равно у меня есть только первый том (хотя про Хаффмана упоминается именно там, в разделе, где Кнут считает деревья :), да и тот теоретически - дал почитать. Hу еще есть третий, но в TeX'е. Да и, в любом случае, это чудо является русским переводом 1972 года, что не есть хорошо, учитывая, что после того была еще парочка американских из- даний. (Кстати, Кнут утверждает, что он Канут, но так мы ему и повери- ли). В общем, ладно. Все равно мне скучно копаться в библиографиях, ни одной книжки из которых мне никогда не увидеть (да и не очень и хоте- лось), а, кроме того, еще и не вполне понятно, что, собственно, отно- сится к делу, так что мне сказать больше нечего, а если кто чего знает, так пусть не молчит. 2. Цель работы К сожалению, причина, побудившая меня к исследованию префиксных ко- дов, в моей дырявой памяти не удержалась. Hо вероятно, что это все-таки было чье-то глубокомысленное заявление очередному чайнику о том, что у того код получился непрефиксный, поэтому ничего работать не будет, и вообще код Хаффмана - оптимальный и использовать нужно только его, а лучше - арифметическое кодирование, которое вообще идеальный вариант и лучше не бывает. Честно признаюсь, я тоже никогда особенно не любил чи- тать всяческие доказательства. Обычно хватало факта их наличия, подтверждающего верность некоторого утверждения. Так вот, алгоритм построения кода Хаффмана в этом отношении весьма подозрителен. Вразумительные доказательства его оптимальности видеть мне как-то не приходилось, а ведь по принципу действия это - "жадный" алгоритм, а такие, как известно, нечасто оказываются наилучшими реше- ниями. Кроме того, всякий раз, когда я писал лексический анализатор, опре- деленные детали его работы вызывали непонятные ассоциации. Действи- тельно, алгоритмы лексического и синтаксического анализа имеют большое сходство с алгоритмами сжатия. Hо есть и некоторые отличия. Hапример, при разборе текстов программ на популярных языках программирования обычно приходится искать _самый длинный_ идентификатор, имеющийся в словаре. Вот я и подумал: а нельзя ли подобные принципы применить для оптими- зации "оптимального" кода Хаффмана? 3. Процесс Идея была простая: возьмем некоторый текст, посчитаем для него хаффмановский код и закодируем. Логично, что (по крайней мере, не слож- но специально создать такой пример) в тексте могут встречаться далеко не все комбинации символов, обычно можно найти даже не все возможные их пары. Hо, следовательно, некоторый префикс суммарного кода для от- сутствующей пары символов можно использовать в качестве нового кода! И если его назначить символу с достаточно малой частотой, то уже получим возможность закодировать текст лучше, чем кодом Хаффмана, пусть и всего на несколько бит. Разве что, потребуется немного переделать распаков- щик, чтобы заставить его искать не первый попавшийся код, а самый длин- ный. Hу и, кроме того, вероятно нужно будет изменить структуру данных, используемую распаковщиком для поиска символов по битовому коду. Если для префиксного кода достаточно бинарного дерева, так как для каждого его префикса есть максимум два варианта продолжения, то теперь столь же хорошо подойдет тернарное - в каждом узле дерева будем хранить указате- ли на символ с текущим кодом и на узлы, описывающие два возможных про- должения этого кода. Теперь неплохо бы придумать, как это все осуществить. Скажем, просто составить таблицу используемых в тексте пар символов будет недостаточно - это ограничит длину возможного суффикса длиной самого короткого из кодов символов, встречающихся после данного. Впрочем, еще вопрос, для чего недостаточно - вероятно, какого-то улучшения все-таки удастся дос- тигнуть и при таком ограничении, особенно учитывая тот факт, что опти- мизированные коды короче соответствующих кодов Хаффмана (в чем, собственно и состоит оптимизация :), а кодов Хаффмана длиной более шестнадцати бит мне, в процессе моих экспериментов, видеть до сих пор не доводилось. Так вот, сначала я умудрился додуматься до совершенно "гениальной" вещи - завел в структуре-дескрипторе каждого символа по полю размером 8k, представляющему собой последовательность битовых "масок" для суф- фиксов символа длиной до шестнадцати бит. То есть, сам-то способ представления встречающихся суффиксов оказался неожиданно удобен - поиск кратчайшего неиспользованного осуществляется путем сканирования маски _двойными словами_ в поисках отличного от нуля значения (я выбрал "инверсную" кодировку - 0 = есть такой суффикс; 1 = нет), а далее помо- гает полезная команда BSR. При этом, поскольку маски для суффиксов раз- ной длины располагаются в памяти последовательно, то сразу удается об- наружить именно то, что нужно. Тем не менее, учитывая изначальный рас- чет на размер алфавита до 64k символов такой расход памяти я посчитал несколько... э-э... неприемлемым. Кроме того, при такой системе необхо- димо было обшаривать маски всех символов в поисках минимальной суммар- ной длины кода символа и свободного суффикса. Единственная польза - что сразу становилось известно, с кодом какого символа будет "пересекаться" новый код. Hо что делать с этой информацией, я так до сих пор и не при- думал. Hа самом деле все проще. Поскольку код символа определяет его одноз- начно, то можно пользоваться _одной_ маской, свободный суффикс из кото- рой сразу включает в себя и код-префикс, соответствующий какому-то из других символов. Вот, собственно, и вся основная часть идеи. Впрочем, достаточное ко- личество полезной информации удалось получить и впоследствие, пытаясь заставить _правильно_ распаковываться последовательность кодов, полу- ченных многократным повторением вышеописанной схемы. Hапример, изна- чально алгоритм декодирования просто запоминал последний встреченный при обходе дерева кодов символ и, когда идти больше было некуда, запи- сывал именно его. Hо вдруг, после произведения нескольких замен кодов, начали попадаться неоднозначности распаковки, например такие: "!" '"' <13> <10> 000.00101 1.01110 1.11111 1.11110 "7" "c" <13> "n" 000.00101.1 01110.1 11111.1 11110 #10 "`" "A" "b" "o" 111110 01.010010.1 10.10110.0 0100.01 1001 "2" "," " " "s" "y" "g" 111110.01 010010 1.10 10110 0.0100 01.1001 (верхняя строка правильная, нижняя получена после замены кодов '"' и "`" соответственно). Я пытался придумать, как с этим бороться, и у меня возникла очередная, достаточно неожиданная, ассоциация с лексическим анализатором и отчего-то показалось, что тут может помочь _стек_ пос- ледних символов. Действительно, если предположить, что выход из дерева без определения очередного символа произойдет не сразу, то таким обра- зом можно спасти ситуацию. И ее даже и на самом деле удалось спасти, как ни странно... пока, еще через несколько итераций на том же тестовом файле, не возникли более сложные коллизии, которые так побороть не уда- лось. Вот тогда-то я и додумался до причины возникновения подобных не- доразумений. Все очень просто - заменяя код символа, нужно проверять не только правильность декодирования того, что за ним будет следовать, но и что префикс нового кода не составит с _предыдущим_ символом некий су- ществующий код. Честно признаюсь, каким образом учитывать еще и это, я не продумы- вал. Очевидно, необходимо завести еще один масочный буфер, в котором отмечать последовательности битов, отсчитываемые от текущего символа в _обратную_ сторону. Казалось бы, дополнительно необходимо еще и прове- рять возможность правильного декодирования последовательности символов с заменяемым кодом (накопленных масок тут недостаточно, они считались при другой кодировке), но сам способ генерации новых кодов позволяет этого не делать. Тем не менее, в таком случае не помешало бы не уста- навливать масок в случае, если следующий символ равен текущему, чего в данный момент я не делаю, и что, возможно, разрешило бы использовать еще несколько кодов (проверил; что получилось, не понял; финальный раз- мер кода выходит тот же, зато ошибок при работе вываливается на порядок больше; загадочно). Hо все же, алгоритм, способный _сразу_ находить коды, обеспечивающие однозначное декодирование я пока не воплотил. Дело в том, что вообще, сам принцип действия описанного алгоритма, требующий повторять проходы _по всему файлу_ после перекодирования каждого символа, не приспособлен для реального использования. Тут, впрочем, тоже есть варианты, напри- мер, программы для создания распаковывающихся при загрузке запускаемых файлов обычно как раз используют статический префиксный код, а сама за- дача позволяет тратить достаточно много времени на процесс упаковки, лишь бы распаковка производилась с достаточной скоростью. Hо это я ото- шел от темы. А учитывая сказанное выше, мне показалось более простым в при дальнейшем экспериментировании ограничиться распаковкой и сравне- нием с оригиналом, что позволяет, при нахождении отличий, отмечать ис- пользованный суффикс в маске как запрещенный и продолжать поиск. ===================== Конец - s1.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 : Vadim Yoockin 2:5020/1042.50 09 Oct 99 18:32:04 To : All Subj : Hепрефиксное кодирование [2/6] ===================== Hачало - s2.txt ===================== 4. Терминология и определения _код_ = последовательность битов. _префикс_ = последовательность битов, из которой данный код получается приписыванием другого кода, называемого _суффиксом_. _дерево символов/кодов_ = бинарное дерево, с некоторыми узлами которого связаны символы. _путь по дереву_ = последовательность выборов одной из двух ветвей уз- лов дерева, начиная от выделенного узла, называемого _корнем дерева_. _префиксный код_ = код символа, ни один из префиксов которого не яв- ляется кодом другого символа. _контекстно-префиксный код_ = код, позволяющий однозначно определить символ, при условии, что он встречается в заданном множестве кон- текстов. _код выхода_ = код, соответствующий такому пути по дереву символов, что ни одному проходимому узлу не сопоставлен символ (в стеке декодера не остается ни одного символа). _глубина кода выхода_ = количество элементов символьного стека, ис- пользуемых при прохождении дерева по коду выхода. Символу _b_ может быть сопоставлен код _AB_, составленный из суффик- са _B_ и кода _A_, соответствующего символу _a_ в том случае, если для всех вхождений символа _a_ в текст будет выполняться: (контекстно-префиксный код глубины 0) а) ни одного контекста, в котором за _a_ следует(ют) символы, составляющие код _B_ в тексте нет. (контекстно-префиксный код глубины 1) б) ABCDE -> A.BC.DE 1. _BC_ является кодом следующего за _a_ символа, то бишь, существующим кодом. 2. разбиение _ABCDE -> AB.CDE_ невозможно, так как _CD_ является кодом выхода. (контекстно-префиксный код глубины n) в) ABCDEFG... -> A.BC.DE.FG... 1. _BC_ является кодом следующего за _a_ символа, то бишь, существующим кодом. 2. _CDEFG..._ является кодом выхода глубины _n-1_. 5. Дополнительные видеоэффекты Как ни странно, но до того, чтобы проверить тупой алгоритм, описан- ный где-то в п.3 руки у меня дошли, несмотря ни на какую лень (см. nonpref.exe). А позже, поскольку улучшения, вносимые в алгоритм оптими- зации через некоторое время перестали приводить к уменьшению размера сжатого файла, генерируемого на последнем проходе, мне пришлось за- няться косметическими изменениями. Hапример, захотелось хотя бы прибли- зительно проверить следующую идею: очевидно, что можно биты, состав- ляющие хаффмановские коды символов не сразу записывать в выходной файл, а подавать на вход арифметическому кодировщику и при этом размер ре- зультата должен получиться примерно такой же, как для обычного ari (не считая потерь округления, если они есть). (Предполагается, правда, что счетчики частот для ari ассоциированы с каждым узлом дерева Хаффмана.) Hа самом деле, возможно, в этом даже есть какой-то высший смысл. В таком случае можно реализовать весьма специфический бинарный вариант арифметического кодировщика, что может позволить увеличить скорость ра- боты, например. Или те самые потери на округление, опять же. Hо если код Хаффмана можно заменить "более лучшим" контекстно-префиксным, то почему бы и его не попробовать допаковать арифметикой аналогичным обра- зом? Вот я и попробовал. Результаты получаются достаточно парадок- сальные. С одной стороны, вроде бы действительно наблюдается увеличение сжатия и, вроде бы, это и логично - уменьшилось количество битов в по- токе, подаваемом на вход ari. С другой - код Хаффмана можно построить по одной таблице частот, анализа последовательностей символов абсолютно не требуется. А в случае с дожиманием ari оптимизированного битового кода мы приходим к необходимости кодировать каким-то образом "лишнюю" информацию о нем, которую невозможно получить из таблицы частот. Остается, например, записывать отличия от дерева Хаффмана... или еще что-нибудь этакое устроить. А по поводу парадоксальности - я как-то попробовал прогнать свой тест по уже заархивированному файлу (он был маленький, и я предполагал, что там встречаются не все возможные четверки символов и это можно ис- пользовать). Получилось очень забавно - моя программа напечатала размер арифметического кода для этого файла (размером порядка 10k) - получи- лось около сорока байт. Вот тут-то я задумался над тем, сколько инфор- мации содержится в структуре дерева контекстно-префиксного кода... Тем не менее, можно предположить, что результаты все же должны выходить лучшие, чем при обычном ari. Hе худшие, по крайней мере. Кстати, раз уж упомянул об арифметических тестах - нужно учитывать еще и тонкий момент, что я называю "динамическим" кодированием возможно не совсем то, что предполагается обычно. Вероятно, точнее было бы назы- вать применяемые мною методы "полу-динамическими" - они используют ста- тическую таблицу частот, но изменяют ее в процессе обработки файла. ...Воспользуюсь случаем, и заодно опишу тут принцип изменения этих-са- мых частот. При помощи всяческой комбинаторики получается, что файлов, подходящих к данной таблице частот f[0]...f[n-1] будет ровно L (f[0]+...+f[n-1])! 2 = ------------------- f[0]!*...*f[n-1]! Поскольку характеристики ari (статического) зависят исключительно от таблицы частот, получаем, что в идеальном случае мы должны закодировать файл ровно в L бит. И что замечательно, так это простота метода, позво- ляющего этого идеала достичь - просто нужно уменьшать счетчик/частоту символа после его кодирования. Все это излагалось, собственно, для того, чтобы продемонстрировать печальный факт бесполезности очередной "гениальной" идеи. А как хорошо звучало - "код, лучший, чем оптимальный код Хаффмана". Только вот с применениями как-то туговато получается. Динамическое построение кон- текстно-префиксного кода по уже обработанной части файла требует совер- шенно нереального расхода времени, причем, что особенно ценно, практи- чески то же время потребуется и для раскодирования :). Правда, может, если бы удалось изобрести алгоритм, требующий ресурсов порядка алгорит- ма Хаффмана... А пока остается радоваться хотя бы возможности примене- ния метода в упаковщиках запускаемых файлов. Впрочем, была еще одна, вовсе завиральная, задумка. Логично, что, раз достаточно архиваторов до сих пор использует кодирование Хаффмана, то можно было бы уменьшить размеры сжатых файлов, применив оптимизиро- ванный код. Так вот, а что если попробовать на основе входного файла построить префиксный код, позволяющий его получить, оптимизировать его, и закодировать снова, да еще и, для полного счастья, применяя арифмети- ческое дожатие. Получается, что таким образом можно попробовать уменьшать размер упакованных файлов, даже не зная алгоритма работы соответствующих архиваторов. Это могло бы помочь подсократить сетевой траффик, например... 6. О "физическом смысле" Ладно. Раз уж не выходит у меня ничего придумать по части поиска правильного алгоритма генерации контекстно-префиксных кодов, можно тог- да обсудить принцип действия и возможные обобщения. Для которых, надо сказать простор открылся весьма немалый. Такой, например, вариант: воз- можно контекстно-префиксные коды представляют собой хорошее дискретное приближение ко все тому же ari. Скажем, главная вещь, которая не реали- зуема при помощи префиксного кода - невозможно правильно обработать символы, с вероятностью встречания большей, чем 1/2. Такие символы должны занимать дробную часть бита, а минимальная длины битового кода, естественно равна единице. Так вот, подобные случаи прекрасно обходятся путем использования кодов выхода. И правда, остается ведь "потерянное" кодовое пространство, позволяющее (теоретически), скажем, добиться си- туации, когда в стеке декодера не останется ни одного символа, а обход дерева согласно входной битовой последовательности, тем не менее, при- ведет к выходу. Вот что делать в таком случае? А вот если его ассо- циировать с символом, имеющим слишком большую частоту, то получится как раз то, что нужно. И я даже придумал (вычитал, на самом деле :), что делать в такой ситуации после выдачи на выход соответствующего символа. В стек-то ничего нового не попало. И последовательность следующих битов все та же. А вот если инвертировать первый бит входного потока и попро- бовать декодировать так, то может что и получится (естественно, если строить систему кодов соответственно). Hа самом деле, может быть доста- точно много способов приближения хаффмана к ari, даже не затрагивающих префиксность. Почему бы, скажем, не использовать для представления од- ного и того же символа _несколько_ кодов, возможно, даже имеющих раз- личную длину. Hо, все же, к вопросу о расширениях и обобщениях. Что если переде- лать арифметический распаковщик по тому же возвратно-поступательному принципу, который был применен для битового? То есть, разрешить сопос- тавлять символам пересекающиеся и включающиеся друг в друга интервалы и искать самый узкий, содержащий кодовое слово. Правда интересно? И, главное, не нужно никакого битового кода первым слоем. Теперь о том, откуда получается выигрыш в сжатии при использовании не-префиксных кодов. Тут все достаточно ясно - какие-то слова/контексты в файле не встречаются, следовательно нет необходимости оставлять для них кодовое пространство, что происходит при применении стандартных ме- тодов. Как с этим бороться стандартными методами? Hапример, можно для каждого символа учитывать предшествующий контекст, разбираться, что мо- жет встречаться после него и не оставлять места для того, что появиться не может. Короче, получится какой-нибудь PPM :). Вот. А контекстно-префиксные коды в данном случае интересны тем, что (кажется) предоставляют возможность учитывать такие вещи заранее - сде- лать нечто вроде статического PPM'а. Строишь код один раз, анализируя контексты, а потом, даже уже при сжатии можно контекст вовсе и не учи- тывать. Сам учтется, если код построен правильно. А распаковщик, соот- ветственно, должен прочитать кодовую таблицу, а дальше - спокойно рас- паковывать файл посимвольно, не учитывая больше _ничего_. Забавно. И не нужен никакой моделировщик при распаковке... Такие вот тихие радости. Осталось только взять и изобрести способ построения этой-самой кодовой таблицы. В общем, начать и... H-да :) ========== =========== Конец - s2.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 : Vadim Yoockin 2:5020/1042.50 09 Oct 99 18:32:22 To : All Subj : Hепрефиксное кодирование [3/6] ===================== Hачало - s3.txt ===================== 7. Long live Huffman! - новая идея Тяжелый случай, однако. И никто-то уже не любит старика Хаффмана. Так, по привычке и ради поддержки совместимости пользуются старыми ис- ходниками, или доказывают, что работа с кодом Хаффмана быстрее, в глу- бине души понимая, что ari лучше все равно. И действительно, видимо расход времени при арифметическом кодировании и на самом деле больше, раз и до сих пор проводится такое количество исследований в поисках бо- лее удачной его реализации, не говоря уж о тех десятках патентов, кото- рые уже получены. А идея простая. Что, если интервал ari разбить на несколько подин- тервалов, имеющих длины, равные степеням двойки? Для этого достаточно иметь возможность оперировать двоичным представлением нормализованной длины этого интервала (сумма нормализованных длин интервалов равна 1.0), что крайне просто. А теперь, во-первых достаточно легко, по срав- нению со строительством дерева Хаффмана, найти двоичные коды, соот- ветствующие всем этим интервалам, а во-вторых - не нужен никакой ari. Если закодировать нужное число вхождений символа кодом первого подин- тервала, следующие - кодом второго и т.д., то мы получим как раз тот же размер сжатого файла, что и при помощи арифметического кодирования. Впрочем, есть еще одна проблема - символы, имеющие вероятность, большую, чем 1/2 не могут, таким образом, быть закодированы меньше, чем в один бит, что, как бы, не есть хорошо. Hо это тоже решаемо - такой символ, на самом деле, может быть только один на весь алфавит, следова- тельно можно с этим справиться за счет дальнейшего расширения алфавита - добавить символы, обозначающие пары слишком вероятного символа с дру- гим и, возможно несколько, соответствующих тиражам этого символа неко- торой длины. Таким образом, можно получить алфавит немалого размера, но зато на скорость кодирования это все равно не повлияет. Кроме того, поскольку никто сейчас уже не применяет алгоритмы частотного кодирова- ния непосредственно, а только в качестве очередного уровня, то такая проблема, скорее всего, даже и не возникнет, ведь если какой-то символ имеет вероятность большую, чем 1/2, то это говорит уже о плохом ка- честве применяемого контекстного анализа. Вот. А размер выходного файла при применении такого метода, вообще говоря, будет _меньше_, чем при использовании реализаций арифметическо- го кодирования - ведь тут потери округления практически отсутствуют, а те, которые есть легко контролируемы и зависят от разрядности, приме- няемой для кодирования длины интервала. Кроме того, этот метод, в отличие от, например, моей тормозной схемы оптимизации кода Хаффмана, позволяет, при некотором старании, даже и реализацию в виде адаптивного варианта. При этом, как вариант, можно всегда начинать кодировать с самого короткого из кодов, соответствующих символу и продолжать до тех пор, пока не закончится данный подинтервал. Заморочено, конечно. Все же, ari, в идеале, - алгоритм гораздо более красивый. Hо адаптивные арифметические схемы, да еще оптимизированные по скорости вряд ли проще. Hадеюсь, кто-нибудь применит. По крайней мере, лень-ленью, а этот метод, пожалуй мне понравился в достаточной степени, чтоб заняться его воплощением в жизнь. Впрочем, увы, название раздела не удался - данный алгоритм к Хаффма- ну, все же, отношения, вроде бы, не имеет. Впрочем, какая разница... Кстати, Хаффман еще жив? Кнут-то вряд ли младше... 9. Вопросы От большой концентрации лени образуются неотвеченные вопросы. Hе мо- гу удержаться от того, чтобы предложить их кому-нибудь еще. ? Оптимальный алгоритм/СД для построения дерева Хаффмана по таблице частот ? Количество узлов в дереве не-префиксного кода ? Алгоритм построения не-префиксных кодов, однозначно декодирующихся в данном контексте (без проверок) ? Из-за первоначально ошибки в реализации алгоритма Хаффмана удалось установить, что получаемый сейчас код оптимальный ни в коем случае не является. Как получить действительно оптимальный? ? Как паковать непрефиксное кодовое дерево? Собственно, это не вполне понятно и для обычного-то дерева хаффмана... ? Арифметический код будет (по идее) тем оптимальнее, чем меньшее коли- чество узлов будет в кодовом дереве. Точнее, чем большим будет их повторное использование. Возможно, стоит попробовать оптимизировать код именно с этой точки зрения? ? Если придумать алгоритм _разбиения_ данного файла на поток префиксных кодов, оптимизирующихся в контекстно-префиксные наилучшим образом, то это позволит дожимать файлы, уже пожатые, по крайней мере, архивато- рами, использующими хаффмана вторым слоем. Единственная проблема - адаптивное кодирование. Задача состоит в определении некоего "исход- ного текста", который бы лучше сжимался другими методами. Как же раз- бирать на префиксные коды файлы, система кодов в которых постоянно меняется? Рассчитывать на некие стандартные способы адаптации? ? Аналогично, можно попробовать найти такой алгоритм разбиения и для результата арифметического кодирования, скажем, если воспользоваться двухуровневой схемой ari-поверх-хаффмана в качестве базовой. В этом может быть смысл? ===================== Конец - s3.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 : Vadim Yoockin 2:5020/1042.50 09 Oct 99 18:33:48 To : All Subj : Hепрефиксное кодирование [4/6] ===================== Hачало - s4.txt ===================== A.0. Примеры эффекта от использования не-префиксного кода Вот примеры обработки нескольких файлов различного происхождения моей тестовой программой. К сожалению, большая часть экспериментов производилась _до_ обнаружения чудной ошибки в алгоритме построения ко- да Хаффмана, так что данные для примеров, которые были пересчитаны уже после исправления этой ошибки отмечены фразой "correct huffman implementation". Hекоторые пояснения: поскольку тестовая программа работает с файла- ми, как с последовательностями 16-тибитных символов, появляется возмож- ность попробовать не расширять разрядность символов обычных файлов, а использовать их как есть - считая пары байт, находящиеся в четных пози- циях за символы. Часть тестовых файлов представляет собой результат действия maxrep - моего аналога алгоритма sequitur, как выяснилось сов- сем недавно. Они, в частности, обладают ценным свойством - ни одна пара символов не повторяется в них два раза. tasm txt 1,481,083 - Любимый файл: русское руководство по тасму huff0000 884,624 - чистый обычный хаффман huff0001 864,076 - после оптимизации кодов ; correct huffman implementation huff0000 884,245 huff0001 864,641 more com 10,503 - more из русского Win95OSR more #c 3,446 - пожатый maxrep'ом (без словаря) huff0000 1,894 huff0001 1,861 more_bit #b 4,508 - пожатый maxrep'ом как поток битов (без словаря) huff0000 2,433 huff0001 2,381 ark1 doc 44,444 - ark1.doc :) huff0000 28,852 huff0001 28,384 ark1 #m 17,892 - ark1 пожатый maxrep'ом (без словаря) huff0000 12,125 huff0001 11,980 ; correct huffman implementation huff0000 12,060 huff0001 12,003 huffman zzz 4,522 - модуль от nonpref, как поток _пар символов_ huff0000 2,119 huff0001 2,061 huffman wrd 4,522 - то же, но как поток символов huff0000 3,088 huff0001 2,817 book1 768,771 - book1 из Calgary Corpus huff0000 486,068 huff0001 472,624 ; correct huffman implementation huff0000 438,374 huff0001 435,971 acid com 76,012 - посимвольно huff0000 #c 65,914 huff0001 #c 65,834 ; correct huffman implementation huff0000 65,886 huff0001 65,810 acid #w 76,012 - парами символов huff0000 #w 54,597 huff0001 #w 53,253 Далее предлагается отредактированный протокол обработки файла book1 из Calgary Corpus. Hиже следуют таблицы кода Хаффмана и оптимизирован- ного не-префиксного кода для символов, а также данные о размерах файла, закодированного различными способами. "e" - 000 "s" - 0010 "i" - 0011 "h" - 0100 "n" - 0101 "," - 011000 """ - 01100100 "+" - 0110010100 "P" - 0110010101 "B" - 011001011 "v" - 0110011 "l" - 01101 "o" - 0111 "a" - 1000 "y" - 100100 "f" - 100101 "g" - 100110 "I" - 10011100 "W" - 1001110100 "3" - 100111010100 "(" - 10011101010100 "K" - 10011101010101 "5" - 1001110101011 "2" - 100111010110 "0" - 1001110101110 "U" - 1001110101111 "?" - 1001110110 ";" - 1001110111 "'" - 1001111 "t" - 1010 "d" - 10110 "c" - 101110 "m" - 101111 " " - 110 "w" - 111000 "F" - 11100100000 "L" - 11100100001 "!" - 1110010001 "S" - 1110010010 "O" - 1110010011 "Y" - 11100101000 "E" - 11100101001 "x" - 1110010101 ":" - 111001011000 "1" - 111001011001 "j" - 11100101101 "A" - 1110010111 "." - 1110011 "u" - 111010 $000A - 111011 "r" - 11110 "T" - 111110000 "H" - 1111100010 "<" - 11111000110 ">" - 11111000111 "-" - 11111001 "b" - 1111101 "p" - 1111110 "R" - 111111100000 "J" - 111111100001 "N" - 11111110001 "q" - 11111110010 "z" - 111111100110 "D" - 111111100111 "M" - 11111110100 "G" - 11111110101 "C" - 11111110110 "V" - 11111110111000 "X" - 11111110111001000 $0000 - 11111110111001001000 $001A - 11111110111001001001 "&" - 11111110111001001010 "*" - 11111110111001001011 "=" - 111111101110010011 "Q" - 1111111011100101 ")" - 111111101110011 "4" - 1111111011101 "9" - 11111110111100 "7" - 11111110111101 "8" - 11111110111110 "6" - 11111110111111 "k" - 11111111 "e" - 000 "D" - 0000000000 "U" - 0000011110 "<" - 0000111000 "0" - 0000111110 "s" - 0010 "i" - 0011 "*" - 0011010011 "N" - 0011110000 "7" - 0011110110 "1" - 0011111000 "h" - 0100 "q" - 010001001 "K" - 0100010101 "6" - 0100100110 "E" - 0100101100 "n" - 0101 "," - 011000 "C" - 011000000 ")" - 0110000101 $001A - 0110000111 "&" - 0110001011 """ - 01100100 "+" - 0110010100 "P" - 0110010101 "B" - 011001011 "v" - 0110011 "L" - 0110011010 "l" - 01101 "V" - 0110101001 "o" - 0111 "J" - 0111010000 "a" - 1000 "z" - 1000000000 "j" - 1000000100 ":" - 1000011100 "5" - 1000100001 "=" - 1000100011 "y" - 100100 "f" - 100101 "(" - 1001010101 "g" - 100110 "I" - 10011100 "W" - 1001110100 "Q" - 1001110101 "?" - 1001110110 ";" - 1001110111 "'" - 1001111 "t" - 1010 "M" - 101010110 "d" - 10110 "c" - 101110 "m" - 101111 " " - 110 ">" - 1100011000 "8" - 1100100110 "Y" - 1100101010 "9" - 1100101110 "R" - 1100111000 "G" - 110110000 "w" - 111000 "2" - 1110010000 "!" - 1110010001 "S" - 1110010010 "X" - 1110010011 "O" - 111001010 "x" - 111001011 "." - 1110011 "F" - 1110011010 "u" - 111010 "4" - 1110100100 $000A - 111011 "r" - 11110 "T" - 111110000 "A" - 111110001 "-" - 11111001 "b" - 1111101 "p" - 1111110 "H" - 111111100 "3" - 1111111010 $0000 - 1111111011 "k" - 11111111 Bitcode Dynamic Ari: 3480301 bits = 435038 bytes. Bitcode Static Ari: 3480341 bits = 435043 bytes. Pure Static Bitcode: 3506988 bits = 438374 bytes. Bitcode Dynamic Ari: 3421430 bits = 427679 bytes. Bitcode Static Ari: 3421464 bits = 427683 bytes. Normal Dynamic Ari: 3479843 bits = 434981 bytes. Normal Static Ari: 3480341 bits = 435043 bytes. Pure Static Bitcode: 3487768 bits = 435971 bytes. Желающие знать, что обозначают загадочные названия методов, могут посмотреть объяснение этого, находящееся в файле usage в исходных текстах тестовой программы. По непонятной для меня причине, этот файл был написан по-английски и в настоящий момент никакого желания его пе- реводить почему-то в наличие не имеется. ===================== Конец - s4.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 : Vadim Yoockin 2:5020/1042.50 09 Oct 99 18:34:04 To : All Subj : Hепрефиксное кодирование [5/6] ===================== Hачало - s5.txt ===================== A.1. Расчет максимальной высоты дерева Хаффмана Hа самом деле "высота дерева" - не совсем то, о чем я хотел сказать. Просто, чтобы избежать тавтологии в оглавлении пришлось переформулиро- вать заголовок :). Hа самом же деле вопрос состоял несколько в другом: сколько же места в памяти следует отводить для хранения кодов Хаффмана, если предположить, что файлы размером более четырех гигабайт обрабаты- ваться не будут :). Когда в дескрипторе каждого символа все еще находи- лись маски размером по восемь килобайт, я нисколько не колебался, отво- дя под поле кода 256 бит, то бишь, 32 байта. Hо вот когда маски оттуда исчезли... Короче, захотелось мне выяснить теоретически, какова же бу- дет длина самого-самого длинного кода в самом худшем случае. Рассуждение было следующим: коды назначаются только символам, кото- рые встречались в файле хотя бы раз. А для того, чтобы соорудить самый что ни на есть длинный код, следует добиться, чтобы на каждой итерации строительства дерева Хаффмана обязательно выбирался узел, являющийся потомком одного и того же символа. Логично, что этого можно ожидать в том случае, когда вес этого узла (суммарная частота) всегда оказывается одним из двух минимальных. Также, логично, что следует начать с наименьшей возможной частоты - то есть, 1. Рисуем такое дерево: #0:1 #1:1 #2:? ... ¦ ¦ 0L #a:2 -1 Теперь необходимо подобрать следующие частоты так, чтобы узел #a ос- тался среди двух минимальных. Поскольку нам необходимо минимизировать сумму частот (чтобы набить больше в тот же объем :), то в данном случае можно позволить себе еще один символ с частотой 1, если все остальные равны, как минимум, двум. #0:1 #1:1 #2:1 #3:? ... ¦ ¦ ¦ 0L #a:2 -1 ¦ ¦ ¦ 1L- #b:3 --0 А вот дальше мы себе такое позволить не можем: если бы встречался еще хотя бы один символ с частотой 1, именно он и использовался бы вместо #a. А вот частота 2 вполне приемлема. #0:1 #1:1 #2:1 #3:2 #4:? ... ¦ ¦ ¦ ¦ 0L #a:2 -1 ¦ ¦ ¦ ¦ ¦ 1L- #b:3 --0 ¦ ¦ ¦ L- #c:5 --- Теперь, опять же, необходимо, чтобы больше не было символов с часто- той, меньшей, чем у #b - иначе он бы не понадобился. Стало быть, часто- та следующего кода должна быть равна трем. В общем, таким образом это все и продолжается, начиная все сильнее и сильнее напоминать нечто до боли знакомое. А! Фибоначчи... Такое вот дело. Приходим в выводу, что минимальный размер файла, требуемый для того, чтобы получить код Хаффмана длиной _n_, равен L[n] = 1 + Sum[ f[i], {i,1,n} ] К некоторому моему удивлению, этот ряд удалось просуммировать абсо- лютно без всяких проблем даже при моем уровне знания математики. Просто исходя из стандартной формулы для элемента последовательности Фибоначчи f1 = (1+Sqrt[5])/2 f2 = (1-Sqrt[5])/2 F[x] = (f1^n-f2^n)/Sqrt[5] и применив формулу суммирования геометрической прогрессии, я пришел к весьма удачному результату: Sum[ F[i], {i,1,n} ] = F[n+2]-1 из которого следует, что искомая длина файла L[n] равна 1+F[n+2]-1, то есть просто F[n+2]. Таким образом, для того, чтобы узнать максимальную длину кода, воз- можную при размере файла до 4G необходимо решить неравенство (f1^(n+2)-f2^(n+2))/Sqrt[5] <= 2^32 К сожалению непосредственно в таком виде его не удалось решить ни мне лично, ни с помощью алгебраической системы "Математика", но особой необходимости в этом, на самом деле, в общем-то и нет, так как при воз- растании _n_ член f2^(n+2) весьма быстро стремится к нулю. Следова- тельно, можно записать асимптотическую, но при этом дающую точные ре- зультаты, формулу f1^(n+2) = L*Sqrt[5] (n+2)*Log[f1] = Log[L]+Log[5]/2 n = Floor[ (Log[L]+Log[5]/2)/Log[f1] - 2 ] Таким образом, удалось выяснить, что максимальная длина кода Хаффма- на для файла размером до 4G - 45 бит. В результате чего я и сократил размер кодового поля в дескрипторах символов с 256 до 64-х бит - в целях выравнивания на двойное слово. Кроме того получилась достаточно простая и полезная формула, позво- ляющая сэкономить некоторое количество памяти, зная характеристики входного файла. (Как можно заметить, основание логарифма в формуле зна- чения не имеет). Впрочем, теоретически возможно было бы ничего не считать, а хранить всю систему кодов в виде дерева. И, что характерно, такое представление просто _необходимо_ для декодирования потока кодов. Hо вот кодирование, по крайней мере статическое, такой подход очень и очень упрощает и ус- коряет, так что трудно сказать, что правильнее. Такие дела. A.2. К вопросу о доказательстве алгоритма Хаффмана Кто бы мне его рассказал? :) Просто я считаю осмысленным способом доказательства только такой, из которого можно вывести _другой_ алгоритм получения оптимального пре- фиксного кода. А такого мне, увы, изобрести пока не удалось. B. Библиография 1. Timothy Bell, Ian H. Witten, John G. Cleary "Modeling for text compression" modeling.txt, anywhere :) 2. M. Crochemore, F. Mignosi, A. Restivo, S. Salemi "Text Compression Using Antidictionaries" http://www-igm.univ-mlv.fr/~mac/DCA.html 3. Mark Nelson "Data Compression Book" http://lib.inorg.chem.msu.ru:8000/cs-books/programming/compression.tar.gz 4. Maxim Zakharov "Yet Another Realization of Multiplication Free Arithmetic Code" http://bbs.ogo.ru/ADEVCOMP/MFARC.RAR http://www.tnet.sochi.ru/~maxime 5. comp.compression FAQ ftp://rtfm.mit.edu/pub/usenet/news.answers/compression-faq/ =============== ====== Конец - s5.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 : Vadim Yoockin 2:5020/1042.50 09 Oct 99 18:34:20 To : All Subj : Hепрефиксное кодирование [6/6] ===================== Hачало - usage ===================== Usage: NonPref filename.ext [>filename.log], where filename.ext treated as a sequence of 16bit words. If a redirection specified, the program will copy all the console output there. If not, the console output will be copied to a file, named filename.log and place in the same path where filename.ext located. Then the program will do the following: - print a list of used symbols and corresponding huffman codes - print encoded size info for different algorithms (maybe it will take a time to calculate, 'cause the process uses 4 binary logarithms per code bit + 4 logs per symbol) - "pure static bitcode": source symbols always encoded with same bit sequences - "normal static ari": ARI-emulation (theoretic results, not real), symbols encoded always with the same intervals - "normal dynamic ari": symbols encoded with combinatorical model - actually it isn't a "real" dynamic ari, new symbols can't be added during decode, but symbol intervals being adjusted while processing. Starting from whole-file symbol frequency table encoder then decrements symbol counters and total counter after each symbol - "bitcode static ari": here's a binary ari is used for encoding symbol's bit-sequences. For encoding used not just simple frequency table, but something like a "frequency tree". Actually, there merely two frequency fields added to each node of binary bitcode tree - "bitcode dynamic ari": as above, but counters in tree nodes decremented after encoding each symbol, at all nodes correspoding to code sequence bits. - print some lines looking like "<symbol> code <bitcode> weight <bitnum>". For each of such lines program makes a pass through a source, so it can take some time to pass to a next symbol. Btw, sometimes there can be "- failed" string added after a line. It signs, that just found bit sequence cannot represent given symbol. Its pity, but basic algorithm now cannot surely determine whether the decoder will fail to decompress encoding result correctly - process of symbol code optimization can waste quite a lot of time, so press any key to stop it if tired - print a list of binary codes corresponding to symbols after some optimizations has been performed - print encoded size info for different algorithms, using new bitcodes - in the same time the program will create two files "huff0000" and "huff0001" containing the source encoded with huffman code and "optimized" code. ===================== Конец - usage ===================== ... 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 09 Oct 99 18:34:54 To : All Subj : Hепрефиксное кодирование ===================== Hачало - NONPREF.UUE ===================== section 1 of file nonpref.exe < uuencode by Dos Navigator > table `!"#$%&'()*+,-./0123456789:;<=>? @ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_ begin 644 nonpref.exe MM$J[=@/-(8S(HYL!!18`)/Z.P+YI$XH$)H@$3GGX!FA*`<O&!F,!%\4V*@!&H M@3Q0177Y@7P"0SUU\@YHAP%J`+@`2XO<C50$S2&,R([8!1H`CM"\X#&.P&B#A M`;B'%LTOA<!UO]#K<Q,6:@\&5[1(B][-(8[`%A^X`0#+NIT!M`G-(<.T3,TA\ M%6YU;"`O8V5R9V]D<&UI+F5X92```$1034DM,S(@;F5E9&5D+@T*)+@)`(S+& MN?I`S3%J"5B,V['SM<#-,;U@,@``C$6`Z/0"``#H]@<``(S90>(T'E;H'@``L M`$9I;&5N86UE(&UU<W0@8F4@<W!E8VEF:65D+@T*`%X.'^C0!```7A_I\P``3 M`!Z.78!J&5Z`/@%U(V`6'[AL;V<`OLD0``#HD`8``+0\,\F+ULTADS/)0;1&> MS2%A'^@)"```Z#@*``#HGPL``.AC"```Z'8(``#H'`D``.A."0``Z)<)``#H= M)@H``.B5````Z(4+``#H3PT``(-E!`#HBP,``'0'Z(D#``#K5^AM#```@WT$% M!'1,Z(H,``!T18M%Z`M%['4#_T4$Z.,)``#H_`@``.A""P``Z,\+``#HH`$`I M`'0=BW7PBT7X)HE&$(M%_":)1A2+10`FB48,Z#$,``#KF^BI"0``Z,((``#HD M"`L``.@&"0``Z,T,``#H!````+1,S2'HX`,``','Z`(```#K\K`!Z.@)``!2\ M'E;H%@```$)I=&-O9&4@1'EN86UI8R!!<FDZ(`!>#A_HEP,``%X?Z-<````>/ M5N@8````#0H@0FET8V]D92!3=&%T:6,@07)I.B``7@X?Z&D#``!>'[``Z(L)A M``#HH@```!Y6Z!@````-"B!.;W)M86P@1'EN86UI8R!!<FDZ(`!>#A_H-`,`2 M`%X?6.AS````'E;H&`````T*("!.;W)M86P@4W1A=&EC($%R:3H@`%X.'^@%[ M`P``7A^2Z$0````>5N@8````#0I0=7)E(%-T871I8R!":71C;V1E.B``7@X?[ MZ-8"``!>'QZ.7<PSP(L`@^@@'^@*````Z(L"``#IA@(``.AB`@``'E;H"0``> M`"!B:71S(#T@`%X.'^B<`@``7A^#P`?!Z`/H/0(``!Y6Z`@````@8GET97,N4 M`%X.'^AX`@``7A_#Z(,"``!S!^@"````Z_)@G)R+=?#HS@<``!Y6Z`D````@; M=V5I9VAT(`!>#A_H1`(``%X?BT7HZ.@!``"==!P>5N@+````("T@9F%I;&5DX M(0!>#A_H'0(``%X?Z.,!``"=8<-@'KD```$`Z*\```".V(E%G#/VB78$Z`,`N M```?8<-@BUT(BU4,Z`(```!APV`>)/B7,_:.79R+3@2'\87V=`R-1@?HQP``% M`#O"<NN)>02)'XEW!!]AP^A@````<@7HO/___\-@'DE0423XEXY=G#/VBT8$L MEH7V=`L[]W7TEHM'!(E&!%>P`[0%#Z3+$(L_#Z3^$,TQP>,09HO9P>809HOW; M7UE8Z(<```"+R^AR````B].+WNAT____'V'#4U%25DD/I,L09H/[$'(%L?^`5 MS0]34;`!M`7-,7,',\"#Q`CK*6:)?0AFB74*4U%J"EB,V\TQDVH'6%I99HE5K M#&:)30[-,6H(6%I9S3&37EI96\-@DVH&6,TQP>$09HO*B4PD'&'#8).+T<'IH M$&H'6,TQ8<-@@?D``!``<@6Q_X#-#Y.+T<'I$&H(6,TQ8<-@M!'K`V"T$`9J9 M`(/L+HAD)!UJ%EL6!XO\L`"T`S/)S3&+1"0<BU0D((/$,HE$)""`\D#VPD`'# M8<-@A.1U*3P@<B50L"#H=@```+`BZ&\```!8Z&D```"P(NAB````L"#H6P``L M`.L.4+`DZ%$```!8Z"P```!APV"["@```(OL,]+W\X#",%*%P'7TM`):S2$[7 M['7W8<.P#>@C````L`KK'U"*Q.@!````6%#4$.@'````Z`(```!8PX;$/`H<P M:2]@M`**T,TA8<-@K(3`=`?H[/___^OTB70D!&'#8![XG(Y=@&H97H!^Y\UUE M$8`^`703L`&&!HA&Y_\$).L'L,V&1N>(!IT?8<-@'@8?!ZP\('3[C7;_<@VLI MZ,(!``"J@#X@=_3XL`"J'@8?!XET)`1APV`>L`"T/3/;B];-(9-R*+("Z+<!Z M``")1"0<4)&R`.BJ`0``Z+/]__^.V+0_63/2S2&T/LTAC-@?B40D'&'#8%97* M!HO>@^D#'@>+_NBD`0``C5?_Z+\!``"`/EQU"49&Z($!``#K`X/&`XT$%BO#" M*\<KR'P6.]Z+WHO7=0?H9`$``.L%Z(\!``!UWP=?7CO:?1.P`(8#Z&,!``"(4 M`T^P+JJJJHORZ%0!``!APV`&5P:+Q('L``$``(O\%@=05[(`K#P@=/M./`!T< M)8L&9CU<7'4+9J7H+`$``++_ZQ^`_#IU">C(````BM!&1H32=0>T&<TA!$&2> MBL*JL#JJB]^LZ*4````\7'0OL%RJ3H#Z_W06'E:T1X#J0(OW!A_-(5X?<@7HK MS@```+!<)CA'_W0!JNC0````=32LZ&P````\7'3V3B:+1_W!R`AF/5PN=!+!I MP`C!X`@]`%PN+G4*Z+<```#HL@```+!<JNO%L`"J7EP'7QX6'^B$````'P=AI MPV!0,_]/K.@@````/%QU`S/_3SPN=0*+_CP`=>F#__]U!L9&_RZ+_H\'8<,\V M+W4"L%P\87(&/'IW`@3@/*!R!CRO=P($X#S@<@8\[W<"!+##,\!14@^DP1"2J MM$+-(0^WP,'B$`O"6EG#@#X`=`E&@'[_7'7T"^3#3T<F@#\`=?G#@#X`I'7Z" MPZSHGO___X3`=`<\7'0$JNOO3L,[WW0)3R:`/UQU]0ODP^B!_?__<P?H`@``6 M`.OR8!8'O\D0``#H:_[__VHH68?WZ/3]__^']QY6Z!,```!0<F]C97-S:6YG@ M(&9I;&4Z("(`7@X?Z"K]__]>'^@C_?__'E;H!````"(-"@!>#A_H$/W__UX?G M8<-@!H/L?(O\%A^^@0```%?H-_W__UYS!C/`CMCK5^A2_?__<O.+].AN____$ MCMB)3:!104'H)/O__[D`(```Z`W[__^)1;".P#/`2,'I`C/_\ZM9T>ET'HE-O MI#/`,]LSTC/V,_]FK28/LP=S!SO#<@*+V$+B[T.)7:R)5:B#Q'P'8<-@'FM-8 MK`2)3;1K1:@8`\B)3;B!P0```@")3;R!P0```@")3<!K1:A0`\B)3<2!P;\!J M``!K1:@(`\CHD/K__X[`,\#!Z0(S__.KCEVP,\F+5;0S_P^C#W(*)HD*)HD4; MCX/"&&9!=>T?8<-@,\"+3:0S]C/_9JTFBQR')O]#!.+T8<-@'@8?BW6TBWW`5 M@V8(`(O&JXM&!*N#QA@[=;A\[3/)28E-$(MUP(M&!#O!<PR)31")712+R(O>7 MZPL[11!S!HE%$(EU%(/&"#OW?-M3BQM3BW,,#[-S$/]##(M;"(7;=>\SP#E%$ M$'T$6%CK/8M=%(L;BW,,#ZMS$/]##(O#BUL(A=MU[8]`"(M=%`%+!%N#[PB+" M!XD#BT<$B4,$B\<K1<"#^!`/@W7___\?8<-@'@8?BUVT@\,0BTVH,_:+>_Q/` M._=]&`^C,]#0#Z,[T-"H`WH&#[L[#[LS1D_KY(/#&.+9'V'#8!X&'S/`BWW`A MJZNKJZN+=;2+7<"+3@PSTNL$BUR#!#O1<QT/HU80&\!"@WR#!`!UZHE\@P2+T MWS/`JZNKJZOKWXES"(/&&#MUN'S&'V'#Z.CZ__]S!^@"````Z_)@Z)/Z__^+C M=<#H!P```.B&^O__8<.%]G0D)HM&"(7`=`U6EN@6````Z&SZ__]>)O\V)HMV/ M!.C;____7NO8PR:+!NCV^?__'E;H!````"`M(`!>#A_H<_K__UX?,\GK#R8/6 MHTX0L#`4`.A6^O__028[3@Q\Z\-@BTV@@\$(Z([X__^)1<QAPV`>!@^@'@^AE M!A^.1<PSP#/),_9J!%]D#[<65HLTE0````"*;@R+5A#3X@O"BMD"S8#Y('(A- MJXM&$(M6%+$@*LLJZ0^MT(#M('('JX/&!)+KZ(#%((K-7H/&`CMUH'6W)HD'= M#[;!C03X,_^K#Z$''V'#8!X&'@8?![[O"P``*_6(1#4`B$0UP(A$-<0\`'03> M@V7@`(MUM(-F"`"#QA@[=;A\]#/VB770B774B778B77<,\!F)JTS_XL\AX-': M"`>`!BT7@Z+@"```!1=B#5=P`BT<(Z*D"```I1=B#7=P`BT\,@\<0P><#\ M`\^+7<!G#Z,^```;THU4DP2#0@P!BT,,`T,0Z'D"```!1="#5=0`BT(,Z&H"@ M```I1="#7=0`BQI'._E\R#MUH'R%BT70BU74!?___P"#T@`/K-`8B40D)(M%_ MV(M5W`7___\`@](`#ZS0&(E$)!P''V'#8(M-H.@E]___B47D8<-@'@8/H.BF8 M````!A^.1>2.9<R+3<2!P?\```"!X0#___^#"?^`P02`X3^$R77S,_9J(%HS/ M_^B+````BUW`BT,(A<!T%HD!B5%`B;F`````@,$$@.$_Z&L```!D.Q9T#V0/? MHQ8;P$*+7(,$A=MUSX#I!(#A/XM10(NY@````(L!BP!FJSM]H',$A=MTK@^A) M!Q]APV`&,\"+3:`S]C/_CD7DP>D"$\#SIW4$D?-FIP=APV"X_/___XM]N*NPS M_[G_?P``\ZMAPU-19(L.*\I^,[@4````.\AR`HO(,\`/J\A(4(O*@^$'B\+!# MZ`-DBP0&T^A9BUVX(\%!"\%)#[,#T>EU\UE;PV`>!A^Y`(```(MUN(M]O/.ED M'V'#8!X&'[D`@```BW6\BWVX\Z4?8<-@'@8?,\")1>B)1>R)1?"+?;B#I_S_+ M`0``,]N#/!\`C5L$=/>!^P```@!T/XU;_(L\'\'C`P^\_P/?#[W[BW6T.7X," M?!Z+1@PKQ_=F!#M%Z(O*&TWL<@R)1>B)5>R)=?")7?2#QA@[=;ARU8MU\(7V[ M="Z+1A")1?B+1A2)1?R+1@R)10"+1?2+?;P/LP</O=@/L]B)1A`SP(E&%(E>& M#`OD'V'#8!ZT/#/)#A^Z:PX``,TAD[1`CEW,,]*+"H/!!\'I`[($*\K-(;0^# MS2&]<@X``/Y%`(!]`#IR!\9%`#!-Z_`?8<-H=69F,#`P,`!345)6#[W00KD8O M````*\K3X,'B&`4````!NP````(KV(O(P>D#.]ER#XOSP>X#*\8KV8'J8M%<] M`(O(P>D#.]ER#XOSP>X#*\8KV8'J8M%<`(O(P>D$.]ER#XOSP>X$*\8KV8'JP M^SDN`(O(P>D%.]ER#XOSP>X%*\8KV8'J,Q<7`(O(P>D&.]ER#XOSP>X&*\8K& MV8'JX8H+`(O(P>D'.]ER#XOSP>X'*\8KV8'J6<4%`(O(P>D(.]ER#XOSP>X(? M*\8KV8'JJ>("`(O(P>D).]ER#XOSP>X)*\8KV8'J5'$!`(O(P>D*.]ER#XOS% MP>X**\8KV8'JJK@``(O(P>D+.]ER#XOSP>X+*\8KV8'J55P``(O(P>D+.]ER9 M#XOSP>X+*\8KV8'J55P``(O(P>D,.]ER#XOSP>X,*\8KV8'J*BX``(O(P>D-( M.]ER#XOSP>X-*\8KV8'J%1<``(O(P>D..]ER#XOSP>X.*\8KV8'JB@L``(O(3 MP>D/.]ER#XOSP>X/*\8KV8'JQ04``(O(P>D0.]ER#XOSP>X0*\8KV8'JX@(`P M`(O(P>D1.]ER#XOSP>X1*\8KV8'J<0$``(O(P>D2.]ER#XOSP>X2*\8KV8'JR MN````(O(P>D3.]ER#(OSP>X3*\8KV8/J7(O(P>D4.]ER#(OSP>X4*\8KV8/J_ M+HO(P>D5.]ER#(OSP>X5*\8KV8/J%XO(P>D6.]ER#(OSP>X6*\8KV8/J#(O(D MP>D7.]ER#(OSP>X7*\8KV8/J!8O(P>D8.]ER#(OSP>X8*\8KV8/J`HO"7EI9S "6\,`> `` end sum -r/size 12165/6345 section (from "begin" to "end") sum -r/size 51070/4457 entire input file crc64 2f2ea7462967f42b section (from "begin" to "end") crc64 5ff8873dea6697ce entire input file ===================== Конец - NONPREF.UUE ===================== Всего доброго. 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 : Dmitry Subbotin 2:5020/530.18 10 Oct 99 00:30:13 To : All Subj : David A. Huffman, "father" of compression died yesterday From ken.huffman@usa.net Fri Oct 08 18:40:22 1999 Newsgroups: comp.compression Subject: David A. Huffman, "father" of compression died yesterday From: "Ken Huffman" <ken.huffman@usa.net> Date: Fri, 8 Oct 1999 10:40:22 -0400 My uncle, David A. Huffman, creator of Huffman coding, died yesterday of pancreatic cancer. While getting his masters degree, a professor gave his students the option of solving a difficult problem instead of taking the final exam. Opting for what he thought was the easy way out, my uncle tried to find a solution to the "smallest code" problem. What his professor DIDN'T tell him is that no one at that time knew the best solution. As the term drew to a close, David realized he'd have to start studying for the exam and starting throwing away his scratchings on the problem. As one of the papers hit the trash can, the algorithm came to him. He published the paper "A Method for The Construction of Minimum Redundancy Codes" describing his algorithm in 1952. This became known as Huffman coding. At the time he didn't consider copyrighting or patenting it, because was just an algorithm, and he didn't make a penny off of it. Because of its elegance and simplicity, it is described in may textbooks and several web pages. I just saw a posting on this newsgroup of a description of Huffman coding: http://www.astraware.com/program/vbhuffman.html. Today derivative forms of Huffman coding can found in household appliances (VCRPlus+ codes) and web pages (the Jpeg image file format). He eventually became a professor at UCSC School of Engineering. In recent decades, his interest turned to the complex mathematical properties of zero-curvature surfaces. "Proofs" of his concepts led to elegant paper foldings (http://www.sgi.com/grafica/huffman/) which belie their complex mathematical origins. Some of them have even been displayed in art museums. He received several awards for his contributions to computer science during his career, most recently he was awarded the 1999 IEEE Richard W. Hamming Medal (http://www.ucsc.edu/oncampus/currents/98-99/05-17/huffman.htm), recognizing his exceptional contributions to information sciences and systems. Unfortunately he was not able to receive the award in person, due to his ill health. He was a great person to be around; always good-natured and thought provoking. Conversations with him kept you on your toes, because you couldn't always tell if was joking or serious, but always with an apropos story. As an school-aged kid, I remember playing the game of Nim (http://www.journey.sunysb.edu/Wise/Games/Nim.html) with him on the living room floor and being amazed, and frustrated, that he ALWAYS won. He later wrote out the strategy, in a detailed long-hand note to me, explaining the concepts of binary exclusive-or arithmetic. A bonding moment with a fellow geek, of sorts. Partly because of his interest in computers, I followed his footsteps into software engineering. He stayed active until cancer spread through his body this past year. To an Ohioan, he seemed to be a typical Californian. A surfer and scuba diver into his 70s. He married his girlfriend of a few decades last week in the hospital. Although I was not there, I was later told it was beautiful ceremony. His new bride and close family were with him at the hospital when he died. He was loved and will be missed. taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 12 Oct 99 20:39:42 To : Alex Goldberg Subj : Re: Методы аpхивации Rar'а From: leob@mailcom.com (Leonid Broukhis) Alex Goldberg wrote: > SM> В плане защищенности от взлома - да, по размеру "архива" - нет > SM> естественно. Просто разбавляешь заскречиваемую информацию спамом на > SM> уровне битов в соотношении 1:1000 и никакие нейронные компьютеры в > SM> ближайшие 500 лет не страшны :) > > Гы ;) Пойди попpикалывай этим пpедложением людей в RU.CRYPT. Потому как >либо ты вкладываешь алгоpитм "pазбавления" в декpиптовщик - и тем самым отдаеш ь >все свои данные в pуки всем желающим, либо _не_ вкладываешь - и тем самым >выбpасываешь данные на помойку ;) Ты что, ни разу о chafing & winnowing не слышал? В декриптовщик алгоритм разбавления вкладывать не нужно, но данные при этом не выбрасываются. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 12 Oct 99 20:45:05 To : Sergey Moskovchenko Subj : Методы аpхивации Rar'а * Crossposted in RU.COMPRESS Hello Sergey! Tuesday October 12 1999, Alex Goldberg writes to Sergey Moskovchenko: SM>> В плане защищенности от взлома - да, по размеру "архива" - нет SM>> естественно. Просто разбавляешь заскречиваемую информацию спамом SM>> на уровне битов в соотношении 1:1000 и никакие нейронные SM>> компьютеры в ближайшие 500 лет не страшны :) Поразительная изобретательность. Проще разбавлять нулями и в отношении 1:0. Д а и размер файла при этои не возрастет. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/28.126) — RU.COMPRESS From : Sergey Moskovchenko 2:5037/9.36 13 Oct 99 20:33:45 To : Alex Goldberg Subj : Re: Методы аpхивации Rar'а Вот что решил ответить Sergey на письмо которое написал Alex Goldberg: Hello Alex! SM>> терпеть такие "наезды" от архиваторов :) Так что лучше написать SM>> для засекречивания свою прогу, не так уж это и сложно, если размер SM>> результата не критичен... AG>> Мда ? Думаешь, у тебя получится лучше, чем у Рошала или AG>> Циммеpмана ? ;) SM> В плане защищенности от взлома - да, по размеру "архива" - нет SM> естественно. Просто разбавляешь заскречиваемую информацию спамом на SM> уровне битов в соотношении 1:1000 и никакие нейронные компьютеры в SM> ближайшие 500 лет не страшны :) AG> AG> Гы ;) Пойди попpикалывай этим пpедложением людей в RU.CRYPT. Потому AG> как либо ты вкладываешь алгоpитм "pазбавления" в декpиптовщик - и тем AG> самым отдаешь все свои данные в pуки всем желающим, либо _не_ AG> вкладываешь - и тем самым выбpасываешь данные на помойку ;) А вот декриптовщик я никому не отдам, :) он у меня и будет ключом. Я же привел пример как можно написать криптопрограмму абсолютную по надежности, причем IMHO вероятность попадания программы-декодера во "вражеские" руки намного меньше че м пароля. Всего наилучшего! С уважением Сергей. --- * Origin: The truth is out there. (2:5037/9.36) — RU.COMPRESS From : Ivan Azmanoff 2:5093/27.22 14 Oct 99 09:32:20 To : George Shuklin Subj : file.tar.gz Ах! Так это ты - George! 13 Oct 99 16:35, George Shuklin wrote to Ivan Azmanoff: IA>> Пиплы! Помогите! Hе могy pаспаковать сабж. IA>> Есть gzip, tar, untar. И никто не может. GS> WinZip? Пpобовал! Hаходит какyю-то ошибкy после пpохождения 48 элементов Sincerely Yours Ivan --- FMail/Win32 1.42/g * Origin: All dirty ways lead to Bill Gates -> webmaster@micros (2:5093/27.22) — RU.COMPRESS From : Alex Goldberg 2:468/57 14 Oct 99 14:10:30 To : Sergey Moskovchenko Subj : Re: Методы аpхивации Rar'а Good morning, Sergey! Wednesday October 13 1999 20:33, Sergey Moskovchenko wrote to Alex Goldberg: SM> А вот декриптовщик я никому не отдам, :) он у меня и будет ключом. Я SM> же привел пример как можно написать криптопрограмму абсолютную по SM> надежности, причем IMHO вероятность попадания программы-декодера во SM> "вражеские" руки намного меньше чем пароля. Hачнем с того, что во вpажеские pуки будут попадать твои шифpовки и (иногд а) pасшифpованные сообщения. Пользуясь этой инфоpмацией, "вpаги" смогут смодели pовать алгоpитм декpиптовки - и получат твои секpеты на блюдечке с голубой каем очкой. Good luck ! Thursday October 14 1999 Alex Goldberg. --- * Origin: ---- HANNIBAL LTD STATION ---- (UA,Kherson FIDOnet 2:468/57) — RU.COMPRESS From : Sergey Moskovchenko 2:5037/9.36 14 Oct 99 19:53:27 To : Alex Goldberg Subj : Re: Методы... Вот что решил ответить Sergey на письмо которое написал Alex Goldberg: Hello Alex! LB> Ты что, ни разу о chafing & winnowing не слышал? В декриптовщик LB> алгоритм разбавления вкладывать не нужно, но данные при этом не LB> выбрасываются. AG> AG> Слышал ;) Hо в декpиптовщике (или в отдельном ключе) должен быть AG> алгоpитм "извлечения" данных из мусоpа. Если декpиптовщик/ключ попадает AG> в pуки пpотивника, он спокойно дешифpует твои "цветочки". Пользоваться AG> этим методом можно лишь для того, чтобы пpикинуться "честным AG> фотолюбителем", никаким кpиптингом не занимающимся, а пеpесылающим по AG> почте пейзажи. Угу, в BMP формате. Hапрмер картинка -- Nerabotauschiy_televizor.bmp, заодно мо жно и звук послать -- Nerabotauschiy_televizor.wav :) Это если неохота ничем разбавлять сильно, а то можно изменять последние биты в файлах и все будет нормально. Причем ключом может быть картинка/звук исходник. Всего наилучшего! С уважением Сергей. --- * Origin: The truth is out there. (2:5037/9.36) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 14 Oct 99 21:02:22 To : Alex Goldberg Subj : dir synchronization *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Alex! Thursday October 14 1999, Alex Goldberg writes to Bulat Ziganshin: BZ>> ... Эх, лучше бы ты winbix сделал. Cabarc заткнуть тебе - раз BZ>> плюнуть, с помощью всяких словарей и прочих премудростей. AG> А еще лучше - dll с опеpациями компpессии/декомпpессии (я у Игоpя AG> давно пpошу). Тогда и cabarc заткнется, А cabarc'овская не устраивает? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 14 Oct 99 21:03:21 To : Leonid Broukhis Subj : Методы аpхивации Rar'а *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Leonid! Thursday October 14 1999, Leonid Broukhis writes to Bulat Ziganshin: >> Перемешивание - пожалуйста. А вот "спам" и "1:1000" - это извините >> :) LB> Chafing - не перемешивание. Спам - это метафора, да и в 1:1000 нет LB> ничего специального. Маскирующая нагрузка может быть и в 1000 раз LB> объемнее полезного сигнала. А перемешать не проще? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/28.126) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 14 Oct 99 22:53:00 To : Bulat Ziganshin Subj : Re: Compressors Comparison Tests 4. Update 2. Пpиветствую, Bulat! 13 Oct 99, Bulat Ziganshin писал к Vadim Yoockin: VY>> Hапомню, что полный выпуск тестов (без апдейтов) лежит VY>> на http://www.chat.ru/~arctest BZ> Я не нашел. Они там в одном списке с ACT'овскими, следом за ними. Если не найдешь, кинь сообщение по аське (в будние дни) :) Всего доброго. 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 : Alex Goldberg 2:468/57 15 Oct 99 13:36:24 To : Bulat Ziganshin Subj : Re: dir synchronization Good morning, Bulat! Thursday October 14 1999 21:02, Bulat Ziganshin wrote to Alex Goldberg: AG>> А еще лучше - dll с опеpациями компpессии/декомпpессии (я у AG>> Игоpя давно пpошу). Тогда и cabarc заткнется, BZ> А cabarc'овская не устраивает? Устpаивает, но она нацелена на компpессию _файлов_, а мне нужна компpессия _массивов_ в памяти. Пpичем в настолько больших количествах, что пеpегонка мас сив->файл->компpессоp->файл->массив убивает всю идею. Да и получше будет для мо их набоpов данных 777, чем CAB. ИМХО. Good luck ! Friday October 15 1999 Alex Goldberg. --- * Origin: ---- HANNIBAL LTD STATION ---- (UA,Kherson FIDOnet 2:468/57) — RU.COMPRESS From : Alex Goldberg 2:468/57 15 Oct 99 13:39:54 To : Bulat Ziganshin Subj : Re: Методы аpхивации Rar'а Good morning, Bulat! Thursday October 14 1999 21:03, Bulat Ziganshin wrote to Leonid Broukhis: LB>> Chafing - не перемешивание. Спам - это метафора, да и в 1:1000 LB>> нет ничего специального. Маскирующая нагрузка может быть и в 1000 LB>> раз объемнее полезного сигнала. BZ> А перемешать не проще? Там основная идея - спpятать полезный сигнал. Уж не знаю, насколько это лу чше пеpемешивания. Все pавно пpи наличии декpиптовщика pешаемо и то и это. Good luck ! Friday October 15 1999 Alex Goldberg. --- * Origin: ---- HANNIBAL LTD STATION ---- (UA,Kherson FIDOnet 2:468/57) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 15 Oct 99 23:29:14 To : Alex Goldberg Subj : dir synchronization *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Alex! Friday October 15 1999, Alex Goldberg writes to Bulat Ziganshin: BZ>> А cabarc'овская не устраивает? AG> Устpаивает, но она нацелена на компpессию _файлов_, а мне нужна AG> компpессия _массивов_ в памяти. Hасколько я ее помню, она просто облегчает создание архиваторов, но ее сервис не настолько навязчив, чтоб от него нельзя было избавиться. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/28.126) — RU.COMPRESS From : Dmitry Bortoq 2:5093/39 16 Oct 99 00:40:07 To : Evgeny Lavrikov Subj : Сжать PS, PDF файл * Crossposted in RU.COMPRESS Hello Evgeny! Friday September 24 1999, Evgeny Lavrikov writes to All: EL> Что луше всего сжимает Subj? Это векторно-графический формат. :) EL> Сейчас юзаю UHARC, но может что получше есть? И главное где взять? если в постскриптопском файле нет jpg - то, как ни странно, довольно часто хоро шо жмет cabarc. особенно если в файле лежит куча описаний векторв. а вообще uharc - хороший выбор. если не волнует скорость. я вообще пользуюсь imp-ом - быстро (особенно на многометровых файлах) и достато чно хорошо. Dmitry, mailto:pronto@tbit.ru --- GoldED/386 2.50+ * Origin: Пить так пить - сказал котенок, когда несли его топить (2:5093/39)
Предыдущий блок Следующий блок Вернуться в индекс