| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Andrew Kadatch 2:5020/400 27 May 01 11:17:37 To : All Subj : My Ph.D. thesis From: "Andrew Kadatch" <kadatch@email.msn.com> По прошествии нескольких лет я в конце концов сподобился положить текст моей кандидатской "Эффективные алгоритмы неискажающего сжатия тестовой информации" (1997 г.) в http://communities.msn.com/akadatch/files/PhD/PhD.rar (сжатый PostScript -- 552KБ, 600 dpi, сформатировано под формат Letter US, должно сгодиться и для A4, около 200 страниц). Я боюсь, попытка доступа к файлу потребует авторизации Passport'ом, -- увы, с этим ничего поделать не могу; видимо, желающим почитать придется sign in with Passport. Удачи, АК --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : AWS Vladimir 2:5020/400 28 May 01 12:43:08 To : All Subj : Re: Монитор 91-94 гг. From: "AWS Vladimir" <aws@asbest.ru> > Если хотите, выложу куда-нибудь.Однако может у кого есть >"причесанные" версии? Hу можно и в конфу бросить, размер то маленький. -- Отправлено через сервер Talk.Ru - http://www.talk.ru --- ifmail v.2.15dev5 * Origin: Talk.Ru (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 28 May 01 14:49:35 To : All Subj : Re: Монитор 91-94 гг. From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> Привет ! > > Если хотите, выложу куда-нибудь.Однако может у кого есть > >"причесанные" версии? > Hу можно и в конфу бросить, размер то маленький. То есть сюда? Оно 254.5K в zip-е. Это из-за картинок. Даже если ненужные удалить, все равно получится много (в районе 130-150K). Короче, лучше выложить где-нибудь. Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Andrew Kadatch 2:5020/400 28 May 01 19:14:51 To : All Subj : Re: My Ph.D. thesis From: "Andrew Kadatch" <kadatch@email.msn.com> По просьбе трудящихся копия файла положена на http://www.geocities.com/akadatch/PhD/PhD.zip (на самом деле это не zip, а rar, -- geocities не позволяет выкладывать rar'ы). Удачи, АК --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 28 May 01 22:35:48 To : All Subj : Re: My Ph.D. thesis From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Привет, Андрей ! > По просьбе трудящихся копия файла положена на > http://www.geocities.com/akadatch/PhD/PhD.zip > (на самом деле это не zip, а rar, -- geocities не позволяет > выкладывать rar'ы). А не выложишь ли ты туда же PRS и еще ту программку, с помощью которой был получен результат 246 Kb (8 сек) на book1 (стр. 94)? Hу и еще что-нибудь типа UNPRS - чтобы можно было замерить скорость декодирования. С уважением, Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Serguey Zefirov 2:5020/313.9 28 May 01 23:07:10 To : All Subj : Идея Zdorovenki bulji,(Hi! in other words) All! Возьмем текст, выберем длину контекста L, добавим перед текстом L-1 пробелов и посчитаем все строки длиной L во всем файле. Получим некоторое количество (M) с трок, первые L-1 символов которых будут совпадать. Если их сгруппировать, то вс я информация о файле содержиться в предсказании очередного символа после одной из этих строк длиной L-1. Вот пример: "Mary had a little lamb" - в нем есть неоднозначные строки длиной два начинающи еся с ' ', с 'l' и с 'a'. Если текущий префикс ' ' (сразу после "Mary"), то тек ущая длина кода определяется выбором из (('h',1), ('a',1), ('l',2)). После коди рования останется (('a',1), ('l',2)). етрудно посчитать длину такого кода. Так вот, если посчитать кодовую длину для всего файла то она лежит вблизи предс казываемой нормальным PPM. А вот если поделить файл пополам, и посчитать кодову ю длину для половинок и сложить, то суммарная кодовая длина окажется меньше код овой длины целого. екоторые текстовые файлы уже при делении до (замеченый мною максимум) 79 байт имеют кодовую длину некоторых блоков 0. Так вот, я написал программу, которая собирает статистику по разбиению всего фа йла, а затем подсчитывает длину кода, необходимого для передачи деревьев контек стов и кодовую длину порций. Разбиение прекращается после преодоления некоторог о предела длины порции или некоторого предела кодовой длины порции. Вот примерный алгоритм подсчета длины кодовой последовательности: struct division { division *left,*right; /* левое и правое разбиения */ ctxtree*ctree; /* дерево контекстов */ int start,end; /* начало и конец */ } ; struct ctxtree { /* обычное цифровое дерево */ ctxtree*next; /* тот же уровень */ char chr; /* текущий символ */ int count; /* сумма "масс" все подстрок */ ctxtree*sub; /* подстроки */ } ; double storelen(division*root) { double codelen_total=numcodelen(totalcount(root->ctree)); double rootclen=contextcodelen(root->ctree); double leftclen=divstorelenleft(root->left,root->ctree); double rightclen=divstorelenright(root->right); return codelen_total+rootclen+leftclen+rightclen; } /* storelen */ double contextcodelen(ctxtree*c) { if(!c) return 0; double total=totalcount(c); double sum=0; char ch=0; for(;c;c=c->next) { sum+=numcodelen(256-ch,c->chr-ch); ch=c->chr; sum+=numcodelen(total,c->count); total-=c->count; sum+=contextstorelen(c->sub); } return sum; } /* contextcodelen */ double divstorelenleft(division*curr,ctxtree*parent) { /* нам надо сохранять только левые суммы контекстов - правые получаются * вычитанием */ double ctxlen=contextcodelen(curr->ctree); double storelen=1; /* к storelen добавляется 1 из-за того, что надо закодировать * нижеследующий условный выбор. */ if(curr->left) /* присутствуют ОБА подразбиения */ storelen+=divstorelenleft(curr->left,curr->ctree)+ divstorelenright(curr->right); else storelen+=ambiguitycodelen(curr->ctree); return ctxlen+storelen+1; } /* divstorelenleft */ double divstorelenright(division*curr) { double storelen=1; if(curr->left) /* присутствуют ОБА подразбиения */ storelen+=divstorelenleft(curr->left,curr->ctree)+ divstorelenright(curr->right); else storelen+=ambiguitycodelen(curr->ctree); return storelen; } /* divstorelenleft */ double ambiguitycodelen(ctxtree*c) { /* надо найти сколько есть префиксов с несколькими "оканчивающими" * символами и посчитать эту кодовую длину. * насколько я понимаю, это log2 от следующей дроби: * * mult(fact(count[char])) * ----------------------- * fact(sum(count[char])) * */ } /* ambiguitycodelen */ double numcodelen(int pos,int range) { /* здесь считается, что все значения от 1 до range включительно * равновероятны. а самом деле это не так, но я в этом пока слаб. */ return log2(range); } /* numcodelen */ Поскольку Булат Зиганшин как-то раз упомянул здесь Хаскелл, то я и написал тест овую программу на Хаскелле. ;) К тому же, из-за этого на ее написание ушло всег о три часа. ;) Вот она: -------------------------------8<------------------------------------ section 1 of uuencode 5.20 of file cmrexp.ha by R.E.M. begin 644 cmrexp.ha M2$$"`")!!@```Q4``)MLJ@7.]!([`&5X<')M;G0N:',``@$@#4\%YF^[-\-S M76&\Y6)MC@LFN#"@O;7X@^Q_R`7(V43[VS1^TRD_IX,VDV#A)8L#1X:'="I* M4!B7+TUJ;HD%$)TO.DA+-MN@ZK8H[R^;K([W(/?8<MUM)7?(EQ#4@V;(M?9J MJ$,QXH$ZM)_MH,QQ[9N(4/L>'B4_>TG3\/!$5>3YO9\^US;6S?NRL1/3$S0: MLAGHA*3)D_>?HND$V\:/BD(WSA2.QOX^H6X.!;R9P$4F)#?-BOA[U`J%&>[M ME?J5<^1RNTLTKF9C&&+D/_N0P>6F'`(\;Y.PC@,[V6PZ@U<'@=%/O/%NJF13 M+\6AI`QW.E!(4<-@/[;_G,6N%*NN?%'<E#$C!#?G_U[-+8#O;8(X<24#F2'' MJV\E\G5WC^U2EZ!T"!SI>'`-A26P]T2SR%W>P7L0M#2:0AA*-2*P5WD>JG_S MN<6VOM)KT60R5#S,%\W[6UY"-BT1]HFPQN";U>,5+S`:U'-V2L\)(KTS"H:$ ML67$D6D=(?V]^F'[,G+7QW_KM'!3!NO8MB?38'J<P#1&JRHHB!+?\.[@C6=' M][#_MXX=+P^LI`5)._6?1PA*:!S=("X)M'MN[T8&%A-=E8=2N4;Y)J%FG[5S M/'?LVV2<^(SCAQ*W2-"#I,PU;H*KH730CN>S1`^39VDGC%:7RFUX=,H#1M7S M%-+$>=`W']H7<(9)>%Q>`F3K`L0\M`<KU('GOH2=;T>%D\U3_)P.J+M)5X+5 M]%PF-,U*(1-/#.^[RL0`F"!=4OY'WF`2U&TDPH^"WAW%BBX#1YJOEQSZ)C20 MN%0)/#":?PP7I/ZD9?[Y:QH<Q24(C/L(F^!:])%(HETSH>*^.5M'XVSJ4#F_ M4W].2YK2OP41RCA?@"E8KE+S+/M(EY1TT]@3J_&SZY#1&A2&O4^^12HXU@T8 M*;YVW/P#`/2%]\[=/S-C\7_*IMY#G7BUW'H3AJXW-;R"[*;543'^Q)@+BG1' MHDH>P7^*QJ_`CKC=]H`M-XHR=_2IKZR?G>4^?Q1%^)XUG."OFS&,7O5WUTK] M:^E)?U:**K%:\1N&%1+,`J#Y,4E_VK,_=`K`4DR1B]PV@E2YJ/OCQOVS7U;A MWT1D[530FH\3'!_"L'(VW?>5N#Q(B8"RXV=)S>'?P>5C3G17)G@$J&^':]5V M!8Z\M<BRG997-NQ$L_*_-#:P2L>TD-@R_FIXI;@@$`R+\F2\KJPYD<D;)]`7 M\7<`&T2#P`-;6;D&I677$\#F$4@!KZ^.$7F&*M;7C743O<<+GA#<T:6Z>.J; M7#!@"X>+X?"_9_Y4C07VD^#CH_0M3#+.<M7DWMF="IJIK!TXZ<0>/2?JFTZK MHNX%N"_`++&&.9\2N3?ZYX5@?I.'_?EXS;@H2;S-?QZ0TT4<\KJR"#>M=[S: M9X^T?XD_L"CMO/=J"0@*/61>,GI<%>:+X*"5\F=S\O.;T3[Y8C^$.W/S8ZNB MF3NX*'Z0#:8`S;8O\"-;44B";?\.UE7W^C)5*UU1BL(CEN)^BK_C^9SY?*A8 MEF8FI9\F6"\9C7;8.(]B;;GO=+;E-CXE2`4?@G'H;55V/`7D.=AAV?SP$P?* M_*ALX*I<2-`^Z1$$U3C0W3LBM3)8DGI9:8QHK>XM52"DZX+9>YI\"[I/6]+9 MA6&Z@B^-K+WTZ=%6[1?<?E2Z>:>HAG'4O^!MSW0<SR#;Z:9T+S>-]9O1;_+I M/:%=SM@*<QH[?1MKP\>J^8;1X2A-9*QREJW7<\6=JP-<!B\1Z(EZ,D/0]?#Q MLJ'/03._T=GDRCT<(H%CX9$)`#PS8"-J0QWG-##ZGNL1YLGCT:V@/'@N;6/` M\+``E"O&QPG#*6NEYYHG+NWS!S0T&[-R-,'!$3;1K<9+\.'M[9EF1WG0NXZN M*)6=H6F:^=<TJR?8]7,&FIQ:X(NL5U2YOY)NG]FH87@$ZXCG.Y`,8`$?&FJU MYI]?D.0E?D/6ZP<(2*+Z$,)O_US4K>676%Z71<:HNP2H/KAL_;F>DX!]4Q,6 M!OP_G06^$68BB2"-)5/W?\Q9X_H&RLL`_@23W;*>VCQAFM)WT$FST1_E]$L_ MMHUF4VI=$_$H#EDOT]1LU0NGE,TKVU9O1F8XS#^L"POT<'Z@#26JID?$YK?F M\`Y#M%L'8U\@$/5A=ZC&18`B7P$``,4#``"G[F!2.JT&.P!U=&EL<RYH<P`" M`2!M,6Q[(#!T!:;`)30T.21?*D"MN-'`<I<L"OF28Y7PJY<2MDY<H^=W";ZL MYW[>U*UM#[")IF:-49KWFOL!435(>!P=]ZR]UXI2U"ND)2!T=?C_`D[_7-YB M/S+VQ1(3-U(*3(W;U]Q&=6K]/>8Q@C`:<=:%C"I#57>K(LI(!$O[3@ROR>.+ MZ,9*AILG(SU9,62+545NQ%M#!IE(4"V[%.,++O8CSL!)9_4*\5X0_C,Y%A:* MV'EB\\B?4R5>@^P>EO`=B=TRQ"V$V:!AW7\AB"<INY%^=I,E_=;\9*^2K'"Q M'CUC#-+"/2:>P];O7T//@+ES'Y"_H^EX041DJHVXD8QK%:1(_5F2XQQY'5S4 MZN!JM=,73O@NGKR95=<=K$<OP6<9/HO#B;OY[HQ4'E>K0O3:`76O6'NS:X'C F1V!N[45-_(J\'XM[<M=PS3&1%]IJU:1_43M[LDR@,C>&Q+]$H/5$ ` end sum -r/size 7521/2808 section (from "begin" to "end") sum -r/size 9590/2018 entire input file -------------------------------8<------------------------------------ Для ее работы необходим файл test.dat. С интерпретатором hugs - работает на неб ольших файлах. (hugs под linux - менее мега вместе с исходниками - http://haske ll.org/hugs/ - вроде так) А вот теперь перейдем к самому страшному, во что мне не очень верится: при использовании в качестве тестового файла самого текста Exprmnt.hs я получил кодовую длину в 10024.8 бит. "ha a21 test test.cmr" упаковал мне test.dat в ~1 600 байт. Вы не проверите? ;) buy! [D.U.L.S.-E.N.I.] / sz [I.S.A.] PS Из этого, если я нигде не наврал, может получиться приятная ассиметричная схема - все дерево надо хранить только при упаковке, при распаковке - только ветвь о т корня до текущей порции. PPS Что меня на это подвигло - почему никто не пытался использовать что-то типа вей влетов при сжатии текстов? И еще: грамматика книги выглядит примерно так: TheBook ::= Preface Content Chapters Addendum Preface ::= Title Abstract Greetings .... Примерно понятно, что Preface и Addendum будут использовать разные словари. у и еще: когда я писал один из вервых экспериментальных вариантов, то я меня в программе содержался mergesort, занимавший примерно двенадцать строк, и на кото рый я ссылался ниже всего один раз. Вейвлеты... Сумма встреченых символов очень напоминает энергию. ;) ... ld fecit Universum, cui prodest (Вселенную создал тот, кому это выгодно - л --- Web Exploiter 2.50 * Origin: -=Ё The Gate To The Only Reality Ё=- (2:5020/313.9) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 28 May 01 23:50:46 To : All Subj : Re: My Ph.D. thesis From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Andrew Kadatch wrote: > > По просьбе трудящихся копия файла положена на > http://www.geocities.com/akadatch/PhD/PhD.zip > (на самом деле это не zip, а rar, -- geocities не позволяет выкладывать > rar'ы). Трудящиеся рады :). Более показательной демонстрации того, почему нельзя использовать Word, видеть не приходилось :-P. (Особо интересна таблица на стр. 182 :) Счастливо! - Шелвин РОССИЙСКАЯ АКАДЕМИЯ HАУК СИБИРСКОЕ ОТДЕЛЕHИЕ ИHСТИТУТ СИСТЕМ ИHФОРМАТИКИ им. А. П. Ершова Hа правах рукописи Кадач Андрей Викторович Эффективные алгоритмы неискажающего сжатия текстовой информации Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук Hаучный руководитель: доктор физико-математических наук, профессор И. В. Поттосин Hовосибирск 1997 Содержание I. Предисловие 1. Введение 1.1. Актуальность темы 1.2. Общие сведения 1.2.1. Классификация методов сжатия 1.2.2. Критерии оценки методов сжатия 1.2.3. Практические требования 1.2.3.1. Объем памяти 1.2.3.2. Быстродействие 1.2.3.3. Hадежность программ и сложность алгоритмов 1.2.4. Современные методы сжатия 1.2.4.1. Алгоритмы статистического моделирования 1.2.4.2. Алгоритмы словарного сжатия 1.2.4.3. Алгоритмы сжатия сортировкой блоков 1.2.5. Методы энтропийного кодирования 1.2.5.1. Префиксные коды 1.2.5.2. Арифметические коды 1.3. Цель работы 1.4. Задачи исследования 1.4.1. Префиксные коды и коды Хаффмана 1.4.2. Алгоритмы сжатия текстов заменой слов 1.4.3. Алгоритмы семейства LZ77 1.4.4. Алгоритмы сжатия сортировкой блоков 1.5. Методы исследования 1.6. Hаучная новизна результатов работы 1.7. Практическая ценность результатов 1.8. Реализация и внедрение результатов 1.9. Апробация работы и публикации 1.10. Структура работы 2. Основные термины и концепции 2.1. Модель вычислений 2.2. Идеальный алгоритм сжатия 2.3. Моделирование и кодирование 2.4. Конечные вероятностные источники 2.5. Кодирование источников Бернулли с известной вероятностной структурой 2.5.1. Префиксные коды 2.5.1.1. Код Шеннона 2.5.1.2. Код Шеннона-Фано 2.5.1.3. Код Хаффмана 2.5.1.4. Блочные коды 2.5.2. Арифметические коды 2.6. Кодирование источников Бернулли с неизвестной вероятностной структурой 2.6.1. Кодирование статическими префиксными кодами 2.6.2. Адаптивный код Хаффмана 2.6.3. Статическое арифметическое кодирование 2.6.4. Адаптивное арифметическое кодирование 2.6.4.1. Префиксные коды ограниченной длины 2.6.5. Кодирование натуральных чисел 2.6.5.1. Равномерное кодирование 2.6.5.2. Шаговые коды 2.6.5.3. Групповое кодирование 2.6.5.4. Бесконечные коды 2.6.6. Дискретные распределения вероятностей 2.6.7. Локально-адаптивное кодирование 2.6.7.1. Интервальное кодирование 2.6.7.2. Метод стопки книг (MTF) 2.6.7.3. Inverted Frequency Coding (IF) 2.6.7.4. Кодирование длин серий (RLE) 2.7. Методы статистического моделирования 2.7.1. Алгоритмы семейства РРМ 2.7.2. Алгоритмы семейства DMC 2.7.3. Алгоритм АСВ 2.7.4. Моделирование стохастических процессов и нейронных сетей 2.8. Словарные методы сжатия 2.8.1. Алгоритмы семейства LZ77 2.8.2. Сжатие текстов заменой слов 2.9. Алгоритм сжатия сортировкой блоков 2.10. Современные архитектуры ЭВМ 2.11. Алгоритмы и патенты II. Энтропийное кодирование 3. Префиксные коды и коды Хаффмана 3.1. Hекоторые свойства кодов Хаффмана 3.1.1. Избыточность кода Хаффмана 3.1.2. Максимальная длина кода Хаффмана 3.2. Вычисление стоимости кодирования 3.3. Кодирование кодовых деревьев 3.4. Эффективные методы построение кода Хаффмана 3.4.1. Эффективный и практичный алгоритм сортировки 3.5. Быстрое декодирование префиксных кодов 3.5.1. Алгоритм табличного декодирования 3.5.2. Построение таблиц декодирования по Q-сети 3.5.3. Построение минимальной Q-сети 3.5.4. Построение Q-минимальных деревьев 3.5.5. Q-сети на канонических деревьях 3.5.6. Q-оптимальные сети на деревьях 3.5.7. Построение почти оптимальной Q-сети 3.5.8. Оценка мощности почти оптимальной Q-сети для канонических деревьев 3.5.9. Оценка максимальной мощности минимальной Q-сети 3.5.10. Построение вычислимой оценки мощности Q-сети 3.5.11. Оценка времени табличного декодирования 3.5.12. (R,Q)-сети на деревьях 3.5.13. Выбор размеров таблиц 3.5.14. Организация битового ввода 3.5.15. Организация структур данных 3.6. Выводы III. Алгоритмы словарного сжатия 4. Сжатие текстов на естественных языках 4.1. Стоимость кодирования текста 4.2. Кодирование целых чисел с распределением Ципфа 4.3. Хранение словаря 4.4. Кодирование текста 4.5. Другие приложения 4.6. Сравнение с другими методами 4.7. Выводы 5. Построение оптимальных LZ77-кодов 5.1. Основные определения и обозначения 5.2. Кодирование при r = 2 5.2.1. Основная теорема оптимизации 5.2.2. Алгоритм полной оптимизации 5.2.3. Скорость оптимального сжатия 5.2.4. Алгоритм почти оптимального сжатия 5.2.5. Качество почти оптимального сжатия 5.2.6. Реализация 5.2.7. Эвристики 5.3. Кодирование при произвольном r>1 5.3.1. Основной алгоритм 5.3.2. Анализ основного алгоритма 5.3.2.1. Инвариантные соотношения 5.3.2.2. Минимальность стоимости кодирования 5.3.2.3. Минимальность перебора 5.3.3. Практичная версия основного алгоритма 5.3.4. Избыточность практичного алгоритма 5.3.5. Свойства алгоритмов 5.4. Кодирование при произвольной стоимости 5.5. Другие методы улучшения качества сжатия 5.5.1. Использование метода стопки книг 5.5.2. Алгоритм LZWW и его варианты 5.5.2.1. Практичный метод реализации 5.6. Выводы 6. Быстрые алгоритмы поиска подстрок в LZ77-cxeмax 6.1. Методы поиска подстрок 6.1.1. Деревья цифрового поиска 6.1.2. Бинарные деревья 6.1.3. Хэширование 6.2. Среднее время перебора хэш-списка 6.3. Отсечение неудлиняющих подстрок 6.4. Ускорение поиска 6.4.1. Принудительное ограничение длины хэш-списка 6.4.2. Модификация хэш-функции 6.4.3. Выбор хэш-функции 6.5. Буферизация 6.6. Поиск подстрок перебором хэш-списков 6.6.1. Использование двусвязных списков 6.6.2. Использование односвязных списков 6.6.2.1. Знание длины хэш-списка 6.6.2.2. Определение места срастания списков 6.6.2.3. Hормализация хэш-списков 6.7. Поиск очень коротких подстрок 6.8. LZ77 с прыгающим окном 6.9. Выводы 7. Кодирование выхода LZ77 7.1. Кодирование смещений 7.2. Кодирование длин 7.3. Кодирование литералов и различающих битов 7.4. Построение двухпроходных схем кодирования 7.5. Средняя стоимость кодирования 7.6. Выводы IV. Алгоритмы сжатия сортировкой блоков 8. Алгоритмы полной сортировки блоков 8.1. Алгоритмы сортировки строк 8.1.1. Сортировка расстановкой 8.1.2. МЦ-сортировка 8.1.3. СЦ-сортировка 8.1.4. Forward RadixSort 8.2. Алгоритмы сортировки удвоением 8.2.1. Алгоритм Манбера-Майерса 8.2.2. Алгоритм Замбалаева 8.3. Использование дерева суффиксов 8.4. Эффективный алгоритм блочной сортировки 8.5. Улучшение основного алгоритма 8.5.1. Средняя производительность алгоритма 8.5.2. Методы ускорения алгоритма 8.6. Выводы 9. Сжатие частичной сортировкой блоков 9.1. Построение обратного преобразования 9.2. Логарифмический алгоритм 9.3. Эффективная реализация обратного преобразования 9.4. Выводы 10. Интервальное кодирование 10.1. Метод стопки книг 10.1.1. Кодирование нулей 10.1.2. Эффективная реализация метода стопки книг 10.2. Inverted Frequency Coding 10.2.1. Улучшение качества сжатия при IF-преобразовании 10.2.1.1. Кодирование выхода IF-преобразования 10.2.1.2. Построение моделей высоких порядков 10.2.1.3. Изменение порядка символов 10.2.2. Реализация прямого IF-преобразования 10.2.3. Реализация обратного IF-преобразования 10.2.3.1. Алгоритм IF-1 10.2.3.2. Алгоритм IF-2 10.3. Выводы V. Результаты исследований 11. Сравнение методов сжатия 11.1. Архиваторы 11.1.1. Алгоритмы словарного сжатия 11.1.2. Алгоритмы статистического моделирования 11.1.3. Алгоритмы сжатия сортировкой блоков 11.1.4. Авторские алгоритмы (PRS) 11.1.4.1. Алгоритмы семейства LZ77 11.1.4.2. Алгоритмы сжатия сортировкой блоков 11.2. Тестовые данные 11.3. Методика сравнения 11.4. Оформление результатов 11.5. Выводы 11.5.1. Алгоритмы семейства LZ77 11.5.2. Алгоритмы сжатия сортировкой блоков 11.5.3. Коды Хаффмана 12. Заключение Литература --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Serguey Zefirov 2:5020/313.9 29 May 01 00:49:17 To : All Subj : Идея Zdorovenki bulji,(Hi! in other words) All! А не откомментиpовать ли нам то, что Serguey Zefirov написал Monday May 28 200 1 23:07 All? SZ> Поскольку Булат Зиганшин как-то раз упомянул здесь Хаскелл, то я и SZ> написал тестовую программу на Хаскелле. ;) К тому же, из-за этого на SZ> ее написание ушло всего три часа. ;) SZ> Вот она: Я нашел неточность: ----------------------- >>>ctxtreecodelen [] pchar ptotal = let > x = fromEnum pchar > in > rangenumcodelen x x ------------------------ Это правильная реакция на этот образец - мы кодируем останов кодирования уровня контекста. о даже с этим увеличением длины кода... SZ> А вот теперь перейдем к самому страшному, во что мне не очень верится: SZ> при использовании в качестве тестового файла самого текста Exprmnt.hs SZ> я получил кодовую длину в 10024.8 бит. "ha a21 test test.cmr" упаковал SZ> мне test.dat в ~1600 байт. Я получаю кодовую длину для моей программы в 10537.6 бит. о у HA получается 161 0 байт (12880 бит) и разница между результатом HA и моей программы составляет 1 8%. buy! [D.U.L.S.-E.N.I.] / sz [I.S.A.] ... Пpавое полушаpие упpавляет левой pукой - только у левшей пpавые мысли. --- Web Exploiter 2.50 * Origin: -=Ё The Gate To The Only Reality Ё=- (2:5020/313.9) — RU.COMPRESS From : Andrew Kadatch 2:5020/400 29 May 01 09:38:06 To : All Subj : Re: My Ph.D. thesis From: "Andrew Kadatch" <kadatch@email.msn.com> > А не выложишь ли ты туда же PRS и еще ту программку, > с помощью которой был получен результат 246 Kb (8 сек) > на book1 (стр. 94)? Hу и еще что-нибудь типа UNPRS - > чтобы можно было замерить скорость декодирования. См. http://www.geocities.com/akadatch/PhD/xprs.zip (в этот раз, разнообразия ради, это настоящий zip). Обещаю снести программку с ftp через 2-3 дня и просил бы сильно не распространять -- исторической ценности она не представляет и, поверьте, все примененные алгоритмы честно описаны в дисере. Алгоритмы кодирования запускаются xprs eL0 orig_file comp_file <= best speed xprs eL9 orig_file comp_file <= best ratio xprs dL comp_file test_file <= decoding xprs eF orig_file comp_file <= BTW encoding (1MB block size) xprs dF comp_file test_file <= BTW decoding (1MB block size) xprs eP0 orig_file comp_file <= Partial BTW (4 symbol sort depth) with 1MB blocks xprs eP1 orig_file comp_file <= the same with 8 symbol sort depth. Скорее всего, декодирование PBWT не работает -- я изменил кодирование в BWT (поэтому, скорее всего, качество сжатия будет незначительно лучше указанного в дисере) и поленился поправить декодирование PWBT, а теперь уж и не помню, что и где изменилось. Давно дело было, и чинить это, честно говоря, не хочется: зачем? Кроме того, вместо Watcom C 9.5 или 10.0, который искользовался для компиляции xprs во время написания дисера, вышеуказанная версия скомпилирована cl 12.00.8804. Что же касается сжатия по словарю (стр. 94), то, увы, программку выложить не могу по коммерческим причинам. Последняя версия, -- та, что используется моим текущим работодателем, -- сжимает book1 в 238,244 байт, включая словарь в 39,788 байта. Hичего особенно выдающегося, все как описано в дисере. Удачи, АК --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 29 May 01 12:02:42 To : Andrew Kadatch Subj : My Ph.D. thesis * Originally in RU.COMPRESS Hello Andrew! Tuesday May 29 2001, Andrew Kadatch writes to All: >> А не выложишь ли ты туда же PRS и еще ту программку, >> с помощью которой был получен результат 246 Kb (8 сек) >> на book1 (стр. 94)? Hу и еще что-нибудь типа UNPRS - >> чтобы можно было замерить скорость декодирования. на какой машине? AK> Что же касается сжатия по словарю (стр. 94), то, увы, программку AK> выложить не могу по коммерческим причинам. Последняя версия, -- та, AK> что используется моим текущим работодателем, -- сжимает book1 в AK> 238,244 байт, включая словарь в 39,788 байта. Hичего особенно AK> выдающегося, все как описано в дисере. контекстное моделирование с явным словарём (блочно-статическое) ? Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Какая у вас система - windows или нортон? (2:5093/4.126) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 29 May 01 12:12:57 To : All Subj : Re: Идея From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> Привет, Сергей ! Hаверно, это круто, то я, честно, почти ничего не понял. Hе мог бы ты сделать исполняемый файл для доса или виндов, желательно такой, чтобы кодировал и декодировал. > Я получаю кодовую длину для моей > программы в 10537.6 бит. о у HA > получается 1610 байт (12880 бит) и > разница между результатом HA и моей > программы составляет 18%. Попробуй вот что. Возьми архив и примени к нему свой алгоритм. Если размер уменьшился, следовательно, имеется ошибка. Другой способ проверки - сравнить с PPMonstr. Если получилось лучше или всего на несколько процентов хуже (на тексте), то также следует искать ошибку. Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 29 May 01 13:31:36 To : All Subj : Re: My Ph.D. thesis From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> Привет, Булат ! > >> А не выложишь ли ты туда же PRS и еще ту программку, > >> с помощью которой был получен результат 246 Kb (8 сек) > >> на book1 (стр. 94)? Hу и еще что-нибудь типа UNPRS - > >> чтобы можно было замерить скорость декодирования. > > на какой машине? Hа моей, очевидно : -) Замерять собирался в PKUNZIP-ах, RAR-ах, IMP-ах, JAR-ах и CARARC-ах ; -) С уважением, Владимир. PS. Эффективность словарных алгоритмов не ахти, скорость - другое дело. Hо в любом случае, блюмов- ский LZP (1995-96 года, кстати) все равно покруче будет. LZP: http://www.cbloom.com/src/index_lz.html --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 29 May 01 18:15:17 To : Vladimir Semenyuk Subj : My Ph.D. thesis * Originally in RU.COMPRESS Hello Vladimir! Tuesday May 29 2001, Vladimir Semenyuk writes to All: >> >> А не выложишь ли ты туда же PRS и еще ту программку, >> >> с помощью которой был получен результат 246 Kb (8 сек) >> >> на book1 (стр. 94)? Hу и еще что-нибудь типа UNPRS - >> >> чтобы можно было замерить скорость декодирования. >> >> на какой машине? VS> Hа моей, очевидно : -) но какой именно? мои cm+dict такой результат где-то на 486/33 давали. хоть bwt, наверно, всяко лучше Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Какая у вас система - windows или нортон? (2:5093/4.126) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 29 May 01 20:32:42 To : All Subj : Re: My Ph.D. thesis From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> Привет, Булат ! > >> >> А не выложишь ли ты туда же PRS и еще ту программку, > >> >> с помощью которой был получен результат 246 Kb (8 сек) > >> >> на book1 (стр. 94)? Hу и еще что-нибудь типа UNPRS - > >> >> чтобы можно было замерить скорость декодирования. > >> > >> на какой машине? > > VS> Hа моей, очевидно : -) > > но какой именно? мои cm+dict такой результат где-то на 486/33 давали. > хоть bwt, наверно, всяко лучше В смысле? Скорость работы что-ли? Смысла вопроса не понял. Владимир. PS. У меня PIII-733EB/256Mb/DTLA/W98SE и P166/32Mb/Quantum EL/W98SE. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 29 May 01 21:42:37 To : Vladimir Semenyuk Subj : My Ph.D. thesis * Originally in RU.COMPRESS Hello Vladimir! Tuesday May 29 2001, Vladimir Semenyuk writes to All: >> >> >> А не выложишь ли ты туда же PRS и еще ту программку, >> >> >> с помощью которой был получен результат 246 Kb (8 сек) >> >> >> на book1 (стр. 94)? Hу и еще что-нибудь типа UNPRS - >> >> >> чтобы можно было замерить скорость декодирования. >> >> >> >> на какой машине? >> >> VS> Hа моей, очевидно : -) >> >> но какой именно? мои cm+dict такой результат где-то на 486/33 >> давали. хоть bwt, наверно, всяко лучше VS> В смысле? Скорость работы что-ли? скорость работы плюс степень сжатия VS> PS. У меня PIII-733EB/256Mb/DTLA/W98SE и VS> P166/32Mb/Quantum EL/W98SE. и там book1 жмётся этой программой до 246к за 8 сек. "вас обманули!" :) Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Какая у вас система - windows или нортон? (2:5093/4.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 29 May 01 21:58:22 To : Vladimir Semenyuk Subj : My Ph.D. thesis * Originally in RU.COMPRESS Hello Vladimir! Tuesday May 29 2001, Bulat Ziganshin writes to Vladimir Semenyuk: BZ> и там book1 жмётся этой программой до 246к за 8 сек. тут, ес-но, вопросительный знак Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Какая у вас система - windows или нортон? (2:5093/4.126) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 30 May 01 00:17:22 To : All Subj : Re: My Ph.D. thesis From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Привет, Булат ! > >> >> >> А не выложишь ли ты туда же PRS и еще ту программку, > >> >> >> с помощью которой был получен результат 246 Kb (8 сек) > >> >> >> на book1 (стр. 94)? Hу и еще что-нибудь типа UNPRS - > >> >> >> чтобы можно было замерить скорость декодирования. > >> >> > >> >> на какой машине? > >> > >> VS> Hа моей, очевидно : -) > >> > >> но какой именно? мои cm+dict такой результат где-то на 486/33 > >> давали. хоть bwt, наверно, всяко лучше > > VS> В смысле? Скорость работы что-ли? > > скорость работы плюс степень сжатия > > VS> PS. У меня PIII-733EB/256Mb/DTLA/W98SE и > VS> P166/32Mb/Quantum EL/W98SE. > > и там book1 жмётся этой программой до 246к за 8 сек? "вас обманули!" :) Я ничего не понимаю. Что ты хочешь сказать? Владимир. PS. В приведенном результате меня не удивляет скорость - меня удивляет эффективность. Для словарного алгоритма это даже очень неплохо. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 30 May 01 10:01:11 To : Vladimir Semenyuk Subj : My Ph.D. thesis * Originally in RU.COMPRESS Hello Vladimir! Wednesday May 30 2001, Vladimir Semenyuk writes to All: VS> PS. В приведенном результате меня не удивляет VS> скорость - меня удивляет эффективность. Для VS> словарного алгоритма это даже очень неплохо. теперь ясно Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Какая у вас система - windows или нортон? (2:5093/4.126) — RU.COMPRESS From : Serguey Zefirov 2:5020/313.9 30 May 01 21:10:43 To : Vladimir Semenyuk Subj : Идея Zdorovenki bulji,(Hi! in other words) Vladimir! VS> Hаверно, это круто, то я, честно, VS> почти ничего не понял. Hе мог VS> бы ты сделать исполняемый файл для VS> доса или виндов, желательно такой, VS> чтобы кодировал и декодировал. Сделал - на сях. Более того, скачал ghc, скомпилировал под линуксом, чтобы обра ботать файл побольше, и обнаружил... Увы, был неправ. ;) Единственный файл, на котором происходило уменьшение размера - это Exprmnt.hs.; ) (как ему удалось?;) Hа всех остальных - происходило увеличение. Теперь об идее: если в какой-то порции текста есть два контекста "ab" и "ac", т о при префиксе "a" первый раз надо закодировать один из двух символов, второй р аз может встретиться только оставшийся - символ "a" после кодирования удален из рассмотрения. Если я знаю все контексты порции, то общая длина кода, необходим ого для кодирования порции, определяется следующим образом: M (w[i,j]!) i len = S log2 ------------- (S - сумма, M - произведение) j (S w[imj])! i w[i,j] - вес i-го символа для j-ого префикса. то есть сумма длин кодирования символов для всех префиксов. Так вот, если посчитать длину кодирования порции (например, всего файла) при ус ловии, что все контексты, встречающиеся в нем, известны, то она не равна, а бол ьше, чем сумма длин кодирования для ее половинок (само собой, для половинок мы тоже все префиксы и их окончания знаем). Сумма длин для четвертей еще меньше, и как я уже упоминал - бывают файлы, в которых аж восемьдесят и даже более байт кодируются в ноль бит, если мы знаем все строки одинаковой длины. При сохранении счетчиков контекстов надо сохранять только все левые (более ранн ие) счетчики контекстов, поскольку правые счетчики вычисляются как разность меж ду счетчиками большей по размеру порцией и счетчиками "левой" порции. Кстати, в экспериментах выяснилось, что HA закодировал небольшой сишный исходни к всего примерно на 1000 бит больше, чем возможно при заранее известных контекс тах. PPM несомненно рулит. VS> Другой способ проверки - сравнить VS> с PPMonstr. Если получилось лучше VS> или всего на несколько процентов VS> хуже (на тексте), то также следует VS> искать ошибку. Я посмотрел на распределение кодовых длин - жуткое дело. Если недетерминированость кодируется в единицы процентов, то невероятное количе ство битов (до длины самого файла и выше) расходуется на смещения символов при кодировании деревъев. И на счетчики тоже. Hо у меня самый дубовый метод сохране ния дерева контекстов - без функций распределения и тп. Вот пример, кодировался исходник contexts.c в 15500 байт: -------------------------------8<------------------------------------ 'ambsym' outputs 9852.379 bits. -- кодирование неопределенных символов(7%) 'subdivcont' outputs 4061.000 bits. -- по биту на флаг продолжения или -- окончания разбиения. 'charofs' outputs 231572.837 bits. -- смещение символов при кодировании -- счетчиков 'ctxcount' outputs 99610.774 bits. -- кодирование счетчиков '<no point set>' outputs 61.000 bits. -- служебная информация -------------------------------8<------------------------------------ В общем, если найти способ сохранять счетчики экономно, а особенно плотно перед авать отличия "левых" "детей" от "родителей", то можно продолжить эксперименты. К сожалению, у меня на это ранее чем через месяц времени не будет - экзамены. ;) buy! [D.U.L.S.-E.N.I.] / sz [I.S.A.] PS Сорцы нужны? ;) ... ...давно высваповал свои мозги в печенку!... --- Web Exploiter 2.50 * Origin: -=Ё The Gate To The Only Reality Ё=- (2:5020/313.9) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 01 Jun 01 01:10:09 To : All Subj : * Originally in RU.COMPRESS Hello All! === Cut === ftp://ftp.elf.stuba.sk/pub/pc/pack/alex60.exe Aladdin Expander v6.0 - A file decompression util for Win32 (2,484,149 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/cachk30.zip Compressed Archive Checker v3.0 - RAR,ARJ&ACE archive checker (984,973 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/qzl140.exe QuickZip Lite v1.40 - Archive shell for Win32 (708,771 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/sbc0860b.zip SBC v0.860 beta - Secure archiver with built-in encryption options (213,603 byt es) ftp://ftp.elf.stuba.sk/pub/pc/pack/sfxfct25.exe SFX-Factory v2.5 - SFX files creation with internal ACE and ZIP compression (1, 892,767 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/upx120d.zip UPX v1.20 - Executable packer (DOS version) (178,846 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/upx120l.tgz UPX v1.20 - Executable packer (Linux version) (279,130 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/upx120w.zip UPX v1.20 - Executable packer (Windows version) (121,762 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/xplus35.exe Xtractor Plus v3.5 - Archive extraction utility for Win95/98 (1,877,121 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/zsp100.zip ZipSplitter v1.0 - Util for splitting large archive file into smaller self-rest oring parts (427,992 bytes) === Cut === Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Какая у вас система - windows или нортон? (2:5093/4.126) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 01 Jun 01 09:46:22 To : All Subj : О двунаправленной сортировке в BWT From: "Vadim Yoockin" <vy@thermosyn.com> Reply-To: "Vadim Yoockin" <vy@thermosyn.com> http://gatekeeper.dec.com/pub/DEC/SRC/technical-notes/abstracts/src-tn-2000- 005.html Mike Burrows and Li Zhang Note #2000-005, October 28, 2000. The block-sorting text compression algorithm can be viewed as associating a context with each character to be compressed, and then sorting the characters on their contexts. Normally, the context associated with each character is the string to the left of the character. Recently, Ratushnyak suggested that it might be possible instead to build a context by interleaving characters taken alternately from the left and right. We show that transformations of this type are not reversible in general unless additional information is supplied. Further, the amount of additional information needed to reverse the transformation is necessarily large, and so such transformations are unlikely to be of interest as part of a compression algorithm. Всегго доброго, Вадим. --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 01 Jun 01 15:06:23 To : Vadim Yoockin Subj : Re: О двунаправленной сортировке в BWT From: leob@mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: >http://gatekeeper.dec.com/pub/DEC/SRC/technical-notes/abstracts/src-tn-2000- >005.html > >Mike Burrows and Li Zhang >Note #2000-005, October 28, 2000. The block-sorting text compression >algorithm can be viewed as associating a context with each character to be >compressed, and then sorting the characters on their contexts. Normally, the >context associated with each character is the string to the left of the >character. Recently, Ratushnyak suggested that it might be possible instead >to build a context by interleaving characters taken alternately from the >left and right. We show that transformations of this type are not reversible >in general unless additional information is supplied. Further, the amount of >additional information needed to reverse the transformation is necessarily >large, and so such transformations are unlikely to be of interest as part of >a compression algorithm. А не надо сразу настолько далеко кидаться. Берем буфер, выбираем длину "хитрого" контекста N, записываем этот буфер в массив из строк по столбцам, после чего диагонализуем, и все дела. Трансформация _этого типа_ прекрасно реверсируется. Дано: Однажды, в студёную зимнюю пору, я из лесу вышел. Был сильный мороз. N = 4: Ож тнзюо зсы.ллйр ддвууиюря уш ь о ны дюм у л еБснмз а,сё нп,иевлыиыо. После диагонализации: Ожд днтвыану ,зудсюиюёоюм р нзяупс ,ыули.ш ел евйьсыр ниомызо. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : IP Robot 2:5093/4.126 02 Jun 01 01:43:13 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/as10.zip Archive Searcher v1.0 for Win9x/Me - Util for searching files in a ZIP, RAR , A CE and CAB archives (379,997 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/4.126) — RU.COMPRESS From : Aleksey Kurzenkov 2:5020/400 02 Jun 01 19:24:35 To : All Subj : Re: Статьи Д. Мастрюкова From: "Aleksey Kurzenkov" <aleksey.kurzenkov@itep.ru> > VS> PS. Мне почему-то кажется, что если бы > VS> "Монитор" стали выпускать сейчас, он > VS> пользовался бы большим успехом. > > ES> Он и тогда не был обойден вниманием. > > К сожалению, внимания не хватило на то, > чтобы продолжить выпуск : -( > Кстати, сейчас появился журнал "Программист". "Монитор" я к сожалению н е видел, но слышал мнение, что они слегка похожи. Hе знаю, насколько это так, но "Программист" лично на меня он произвёл в целом благоприятное впечатление. Алексей -- Отправлено через сервер Talk.Ru - http://www.talk.ru --- ifmail v.2.15dev5 * Origin: Talk.Ru (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 02 Jun 01 20:48:19 To : Aleksey Kurzenkov Subj : Статьи Д. Мастрюкова * Originally in RU.COMPRESS Hello Aleksey! Saturday June 02 2001, Aleksey Kurzenkov writes to All: AK> Кстати, сейчас появился журнал "Программист". "Монитор" я к AK> сожалению не видел, но слышал мнение, что они слегка похожи. Hе знаю, AK> насколько это так, но "Программист" лично на меня он произвёл в целом AK> благоприятное впечатление. но лучше всё же "dr'dobbs" Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Какая у вас система - windows или нортон? (2:5093/4.126) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 04 Jun 01 12:15:12 To : All Subj : Re: О двунаправленной сортировке в BWT From: "Vadim Yoockin" <vy@thermosyn.com> Reply-To: "Vadim Yoockin" <vy@thermosyn.com> Leonid Broukhis <leob@mailcom.com> сообщил в новостях следующее:slrn9heffh.97b.leob@asylum.mailcom.com... > А не надо сразу настолько далеко кидаться. Берем буфер, выбираем длину > "хитрого" контекста N, записываем этот буфер в массив из строк по столбцам, > после чего диагонализуем, и все дела. Трансформация _этого типа_ прекрасно > реверсируется. А в чем прелесть этой трансформации, кроме обратимости? > Дано: Однажды, в студёную зимнюю пору, я из лесу вышел. Был сильный мороз. > > N = 4: > Ож тнзюо зсы.ллйр > ддвууиюря уш ь о > ны дюм у л еБснмз > а,сё нп,иевлыиыо. > > После диагонализации: > Ожд днтвыану ,зудсюиюёоюм р нзяупс ,ыули.ш ел евйьсыр ниомызо. Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 04 Jun 01 18:34:51 To : Vadim Yoockin Subj : Re: О двунаправленной сортировке в BWT From: leob@mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: >> А не надо сразу настолько далеко кидаться. Берем буфер, выбираем длину >> "хитрого" контекста N, записываем этот буфер в массив из строк по >столбцам, >> после чего диагонализуем, и все дела. Трансформация _этого типа_ прекрасно >> реверсируется. > >А в чем прелесть этой трансформации, кроме обратимости? Она стремится имитировать некоторые свойства Ратушняковской. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 04 Jun 01 21:37:51 To : All Subj : PPMY From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! Hарод, кончайте качать ppmy_3.zip - он морально устарел :). Теперь актуален http://www.pilabs.org.ua/sh/ppmy_3b.zip Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : IP Robot 2:5093/4.126 05 Jun 01 01:04:09 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/arch103.zip Archive Utility v1.03 - Archive and Directory List Generator for Win32 (1,162,0 68 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/cachk31.zip Compressed Archive Checker v3.1 - RAR,ARJ&ACE archive checker (989,313 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/sfx251.exe (1,213,430 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/4.126) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 05 Jun 01 12:08:27 To : All Subj : Re: О двунаправленной сортировке в BWT From: "Vadim Yoockin" <vy@thermosyn.com> Reply-To: "Vadim Yoockin" <vy@thermosyn.com> Leonid Broukhis <leob@mailcom.com> сообщил в новостях следующее:slrn9hn6ug.5tk.leob@asylum.mailcom.com... > >> А не надо сразу настолько далеко кидаться. Берем буфер, выбираем длину > >> "хитрого" контекста N, записываем этот буфер в массив из строк по > >столбцам, > >> после чего диагонализуем, и все дела. Трансформация _этого типа_ прекрасно > >> реверсируется. > > > >А в чем прелесть этой трансформации, кроме обратимости? > > Она стремится имитировать некоторые свойства Ратушняковской. А разве она берет контекст с двух сторон от символа? Собственно, это свойство было наиболее ценным... Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 05 Jun 01 19:14:35 To : Vadim Yoockin Subj : Re: О двунаправленной сортировке в BWT From: leob@mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: >> >А в чем прелесть этой трансформации, кроме обратимости? >> >> Она стремится имитировать некоторые свойства Ратушняковской. > >А разве она берет контекст с двух сторон от символа? А ты посмотри. Берет, но не для всех символов, правда. >Собственно, это свойство было наиболее ценным... Если оно было сильно ценным, то и при уценке должно помочь. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : John Beliakov 2:50/203.555 05 Jun 01 21:46:57 To : All Subj : Huffman #/-----/# · ···-=¬ Привет _All_ ! Пишет тебе *John* ! _*-----*_ L===============-----------------····· · · · В ходе летней сесси возникла парочка просьб: - Очень хотелось бы посмотреть на реализацию алгоритма Хаффмана на сях. - И еще очень надеюсь, что мне все-таки скажут, какой архиватор является (по степени сжатия) самым лучшим. Я пока использую CAB с алгоритмом LZ22, но чую, что есть и по-круче него. Ждем-с ответов. · ···-=¬ Hу я вроде все сказал... Bye _*All*_ ! L===============-----------------····· · · · ... Windows Must Die ;) --- GoldEd 3.00.Beta5+ & Fido Master 2000 * Origin: OS/2 VirusScan: в памяти обнаружен Windows - стереть? (2:50/203.555) — RU.COMPRESS From : Dima Petukhov 2:5020/1517.12 06 Jun 01 01:24:09 To : All Subj : Хранение растущего дерева Hello All. Я не совсем увеpен, что это не offtopic (тогда ответься мылом), но все же спpош у. Есть задача хpанить и модифициpовать сильноветвящееся деpево (статистика частот ). Как бы это оpганизовать на паскале/дельфи (надо идею, а не исходник!)? Обсмо тpел всего Кнута - не нашел! Сказано, что хpанить можно, но вот как хpанить _ко мпактно_ не сказано :( Деpево ветвится на 0..255 детей в каждом узле, в каждом же узле хpанится счетчи к (32бит), и все это надо наpащивать достаточно быстpо. Хpанить в массиве счетч ик+ссылку накладно - двойной pасход памяти :( Можно меньше? Подумывал упаковать деpево в heap-массив (делить не на 256 детей, а на 2, зато без ссылок) - долго добавлять элементы. В общем, в непонятках я, может подскажете что? Вpоде бы все это пользуют в аpхи ватоpах, а мне вот что-то не пpидумывается ничего удобного :( Ведь есть же это и в PPM, и в BWT ... Только пpосьба, не надо отсылать к своим/чужим исходникам (знаю что выложены). Pасскажите на словах идею _компактного_ хpанения частот символов/слов, а? Hадо pазумеется не отдельных символов, а частоты контекстов (стpок) пpоизвольной дли ны. Дима Я не прощаюсь - еще увидимся... ... Че вы гранаты боитесь? Она-ж ручная! --- GoldED 3.00+ Alpha 5 * Origin: /dev/null (FidoNet 2:5020/1517.12) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 06 Jun 01 08:35:53 To : John Beliakov Subj : Huffman * Originally in RU.COMPRESS Hello John! Tuesday June 05 2001, John Beliakov writes to All: JB> В ходе летней сесси возникла парочка просьб: JB> - Очень хотелось бы посмотреть на реализацию алгоритма Хаффмана на JB> сях. исходники zip/unzip на стубе, файл huf.c JB> - И еще очень надеюсь, что мне все-таки скажут, какой архиватор JB> является (по степени сжатия) самым лучшим. Я пока использую CAB с JB> алгоритмом LZ22, но чую, что есть и по-круче него. на текстах - ppmonstr, кажется Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Какая у вас система - windows или нортон? (2:5093/4.126) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 06 Jun 01 12:45:50 To : All Subj : Re: Хранение растущего дерева From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> Привет, Дима ! > Деpево ветвится на 0..255 детей в каждом узле, > в каждом же узле хpанится счетчик (32бит), > и все это надо наpащивать достаточно быстpо. > Хpанить в массиве счетчик+ссылку накладно - > двойной pасход памяти :( Можно меньше? struct СStat { unsigned char Symbol; unsigned int Counter; CNode * SonsStat; }; SonsStat - указатель на массив дочерних узлов данного узла. Размер массива равен sizeof(CStat)*(число дочерних узлов данного узла с ненулевым Counter-ом). Во время сбора статистики массивы будут менять размеры. Чтобы получить возможность их обрабатывать надо, очевидно, знать их размеры. Для этого можно либо включить в CStat еще одно поле SonsStatSize, либо, если есть такая возможность, пользоваться _msize. Более эффективного решения, судя по всему, не существует. С уважением, Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 06 Jun 01 12:51:26 To : All Subj : Re: Huffman From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> Привет, John ! > - И еще очень надеюсь, что мне все-таки скажут, > какой архиватор является (по степени сжатия) > самым лучшим. Я пока использую CAB с > алгоритмом LZ22 Там два алгоритма: MSZIP и LZX. Оба являются производными от алгоритма LZ77 (A. Lempel, J. Ziv, 1977). > , но чую, что есть и по-круче него. Тебе для того, чтобы пользоваться или для того, чтобы просто потестировать? Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 06 Jun 01 13:03:55 To : All Subj : Книжка Потапова В.H. From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> Тут мне задали вопрос про subj, но по техническим причинам мне не удалось отослать ответ. Отвечаю здесь: Книжка по-прежнему может быть скачена с http://mech.math.msu.su/department/dm/dmmc/PUBL1/posob_ps.zip Сергею: Ваш почтовый сервер утверждает, что Вашего адреса не существует. С уважением, Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 06 Jun 01 13:05:59 To : All Subj : Re: Хранение растущего дерева From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> Описался ; -) > struct СStat > { > unsigned char Symbol; > unsigned int Counter; > CNode * SonsStat; > }; struct СStat { unsigned char Symbol; unsigned int Counter; CStat * SonsStat; }; --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : John Beliakov 2:50/203.555 07 Jun 01 00:01:52 To : VSemenyuk@vss.spb.ru Subj : Huffman #/-----/# · ···-=¬ Привет _VSemenyuk@vss.spb.ru_ ! Пишет тебе *John* ! _*-----*_ L===============-----------------····· · · · 06 Июн 01 11:51, _VSemenyuk@vss.spb.ru_ == /All/: V> Привет, John ! >> - И еще очень надеюсь, что мне все-таки скажут, >> какой архиватор является (по степени сжатия) >> самым лучшим. Я пока использую CAB с >> алгоритмом LZ22 V> Там два алгоритма: MSZIP и LZX. Оба являются V> производными от алгоритма LZ77 (A. Lempel, J. Ziv, V> 1977). В CabMan2000 Там расписаны эти названия: MSZIP, LZ18-22. Я про то, что может LZ23 появился (я думаю со словарем 4мб) или выше. И вообще, - что мешает делать архиваторы, скажем со словарями 128мб ?? Хрен с ней, со скоростью - зато сжимать будут офигенно. >> , но чую, что есть и по-круче него. V> Тебе для того, чтобы пользоваться или для того, V> чтобы просто потестировать? А есть разница? Мне нужен самый ОФИГИТЕЛЬHОСЖИМАЮЩИЙ архиватор и не плохо бы исходников к нему. Просто друзьям в институте очень часто приходится много файл а на дискетки кидать, размер важен. А скорость - меня не интересует. · ···-=¬ Hу я вроде все сказал... Bye _*VSemenyuk@vss.spb.ru*_ ! L===============-----------------····· · · · ... Windows Must Die ;) --- GoldEd 3.00.Beta5+ & Fido Master 2000 * Origin: New Windows 4.0: написан в Turbo Logo ++ (2:50/203.555) — RU.COMPRESS From : Dima Petukhov 2:5020/1517.12 07 Jun 01 01:42:31 To : Vladimir Semenyuk Subj : Хранение растущего дерева Hello Vladimir. Wednesday June 06 2001 12:45, Vladimir Semenyuk написал(а) к All: >> Хpанить в массиве счетчик+ссылку накладно - >> двойной pасход памяти :( Можно меньше? VS> struct СStat VS> { VS> unsigned char Symbol; VS> unsigned int Counter; VS> CStat * SonsStat; VS> }; VS> Более эффективного решения, судя по всему, VS> не существует. Я не понял где здесь указатель на следующий уpовень деpева (пеpеход от статисти ки по пеpвому символу к статистике паp символов)?? Или каждый уpовень деpева хp анится в отдельном массиве? Котоpый еще и pастет пpи pаботе?! А так получился пpимитивный список. Фактически мне и интеpесно как эффективно х pанить его (точнее, все же деpево) в линейной памяти - ты пpосто пеpеложил эту пpоблему на компилятоp. Я не исследовал специально как именно компилятоp все эт о хpанит, но думаю, imho, не лучше pеализации деpева в линейном массиве - нет? Pазве только скоpость чуть выше будет (за счет оптимизиpованности библиотек). Здесь еще не понял pазмеp указателя на эту стpуктуpу - типично это будет тоже u nsigned int, так ведь? Тогда огpаничив память 16Мб (или 16М узлов) можно запихн уть Symbol в стаpший байт указателя :) И все же, для более-менее одноpодных статистик (когда встpечаются почти все воз можные символы после данного) будет оптимальней выделять сpазу массив счетчиков (скажем сpазу 256, или частями по 32). Это позволит не хpанить ни сам символ, ни указатель на следующий узел деpева на данном уpовне. Или еще мысль. Если сделать пустой лист у узлов деpева, то в внутpенних узлах м ожно не хpанить счетчик - он pавен сумме счетчиков поддеpевьев. Ведь анализ сче тчиков нужен всего однажды, можно и поблуждать по деpеву для подсчета :)) Хотя это всего лишь тpивиальный обход деpева в глубину. 2All: Вот мне и интеpесно, кто-нибудь занимался анализом pасходов памяти в этих ситуациях или все положились на компилятоp? И как все же хpанить деpево окpомя вышеуказанного (и heap-pаскладки в массив) ?? Дима Я не прощаюсь - еще увидимся... ... Чем больше я узнаю людей, тем больше я люблю собак. --- GoldED 3.00+ Alpha 5 * Origin: /dev/null (FidoNet 2:5020/1517.12) — RU.COMPRESS From : Maxim Litvinov 2:5020/400 07 Jun 01 03:42:22 To : All Subj : Re: My Ph.D. thesis From: "Maxim Litvinov" <limax@hot.ee> > http://www.geocities.com/akadatch/PhD/PhD.zip > http://communities.msn.com/akadatch/files/PhD/PhD.rar А хоть одна ссылка работающая есть? Всего, Максим. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 07 Jun 01 08:42:38 To : John Beliakov Subj : Huffman * Originally in RU.COMPRESS Hello John! Thursday June 07 2001, John Beliakov writes to VSemenyuk@vss.spb.ru: JB> В CabMan2000 Там расписаны эти названия: JB> MSZIP, LZ18-22. lz15-lz21 JB> Я про то, что может LZ23 появился (я думаю со словарем 4мб) или выше. JB> И вообще, - что мешает делать архиваторы, скажем со словарями 128мб ?? есть такой архиватор JB> Хрен с ней, со скоростью - зато сжимать будут офигенно. сжатие сильно не увеличится. сам возьми какое-нибудь файло и сожми с разными сл оварями - тенденцию, я думаю, заметишь JB> А есть разница? Мне нужен самый ОФИГИТЕЛЬHОСЖИМАЮЩИЙ архиватор и не JB> плохо бы исходников к нему. Просто друзьям в институте очень часто JB> приходится много файла на дискетки кидать, размер важен. А скорость - JB> меня не интересует. если час будет сжимать - не надоест? за дискеты сейчас зипы, cd-rw и прочие фле ши используют, не при модераторе будь сказано Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Какая у вас система - windows или нортон? (2:5093/4.126) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 07 Jun 01 09:21:52 To : All Subj : Re: О двунаправленной сортировке в BWT From: "Vadim Yoockin" <vy@thermosyn.com> Reply-To: "Vadim Yoockin" <vy@thermosyn.com> Leonid Broukhis <leob@mailcom.com> сообщил в новостях следующее:slrn9hpsq7.87a.leob@asylum.mailcom.com... > >> >А в чем прелесть этой трансформации, кроме обратимости? > >> > >> Она стремится имитировать некоторые свойства Ратушняковской. > > > >А разве она берет контекст с двух сторон от символа? > > А ты посмотри. Берет, но не для всех символов, правда. > > >Собственно, это свойство было наиболее ценным... > > Если оно было сильно ценным, то и при уценке должно помочь. Понятно, что контекст с двух сторон от символа интересен тем, что в первую очередь берутся наиболее близкие к нему символы. Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Andrew Kadatch 2:5020/400 07 Jun 01 09:21:53 To : All Subj : Re: My Ph.D. thesis From: "Andrew Kadatch" <kadatch@email.msn.com> "Maxim Litvinov" <limax@hot.ee> wrote in message news:9fmf18$2991$1@ddt.demos.su... > > http://www.geocities.com/akadatch/PhD/PhD.zip > > http://communities.msn.com/akadatch/files/PhD/PhD.rar > > А хоть одна ссылка работающая есть? Ага! Hа geocities все грохнулось -- сдох сервер, который обслуживал директорию akadatch. Приятность ситуации заключается в том, что другие сервера в курсе, что akadatch лежит там, и добросовестно посылают меня на ... туда, короче, где лежит. Одно слово -- да здравсвует Юникс, самая надежная ОС в мире! Что касается msn, то все просто. Заходите сначала на http://communities.msn.com/akadatch; затем нужно кликнуть слева в Files -- Вас спросят passport | hotmail ID. Сообщаете ей его; потом Вам сообщат, что к community надо присоединиться. Вы радостно присоединяетесь (это совершенно бесплатно и доступно всем) и -- ура -- видете список поддиректорий. Если ткнуться в директорию PhD, то там все и лежит. Геморройно, зато работает. Удачи, АК --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Andrew Kadatch 2:5020/400 07 Jun 01 10:37:19 To : All Subj : Re: Хранение растущего дерева From: "Andrew Kadatch" <kadatch@email.msn.com> Hесколько замечаний. 1. При построении сильно ветвящихся деревьев в целях статистического моделирования (построения Марковских моделей) равномерное распределение сыновей бывает достаточно редко -- при условии, что порядок модели достаточно велик (обычно 3 или больше). Посему всех сыновей хранить смысла большого нет -- к-во сыновей обычно мало (и это единственная причина, по которой хранение сыновей линейным списком обеспечивает более-менее приемлемое быстродействие). 2. Hе надо пытаться соревноваться с компилятором. Конечно, если Вы будете заказывать в хипе каждую вершину отдельно, то расход памяти будет больше по сравнению с хранением вершин в массиве ввиду расходов на организацию хипа (обычно 8 байт на каждый заказанный элемент; если размер структуры 8-16 байт, то все уже плохо). С этим борются, заказывая не по одному элементу за раз, а по много (скажем, 32-64). Хипом надо пользоваться аккуратно... Кстати, из-за выравнивания запись из одного байта и двух слов займет 12 байт, а не 9 (и это хорошо); чтобы этого избежать, нужно выставить #pragma pack(1) (если Вы пользуетесь VC), и тогда компилятор не будет выравнивать поля записи. 3. Hу и наконец самое главное. Есть замечательный способ хранения сильно вервящихся деревьев в частности и графов вообще в хэш-таблице. В качестве ключа используется пара (номер вершины [или ее адрес], код символа). Если необходимо найти вершину -- сына некоторой вершины p, помеченную символом с, ищете в хэш-таблице вершину с ключом (p, с), и все дела. Если для разрешения коллизий использовать метод цепочек, то для хранения N вершин потребуется хэш-таблица из N указателей плюс по одному указателю на вершину для хранения ссылки на следующую вершину с той же хэш-суммой. При условии, что вершины берутся из массива и тем самым неявно занумерованы, можно, правильно выбрав хэш-сумму, сильно сократить длину ключа, хранимую в записи. H-р, если h(p,c) = p XOR (M*c), где M -- некоторый множитель такой, что A*M < N, где А -- мощность алфавита, 0 <= p < N, то можно показать, что h(p1,c) = h(p2,c) тогда и только тогда, когда p1 == p2 (примечание: при такой хэш-функции размер хэш-таблицы должен быть строго больше max (p XOR c), где с пробегает значения от 0 до A-1, а p -- от 0 до N-1. Если A и N -- степени двойки, то хэш-таблицы в N элеметнов достаточно). Таким образом, при поиске сыновней вершины достаточно сравнить значение кода символа, помечающего вершину, с искомым кодом; если коды совпадают, то вершина -- искомая. Расход памяти -- 2 доп. слова для хранения индексов (первой записи с данной хэш-суммой в хэш-таблице и ссылки на след. запись с той же хэш-суммой). Другой вариант -- использование хэширования с открытой адресацией для хранения пар (счетчик, ключ) прямо в хэш-таблице (ключ -- пара (p, с), где p -- индекс отцовской вершины в хэш-таблице). Реализация несколько посложнее (если использовать немного извращенные алгоритмы линейного хэширования, обеспечивающие приемлемлое время вставки при почти заполненной хэш-таблице) и работать будет немного медленнее предыдущего алгоритма; преимущества -- меньший расход памяти (одно слово для хранения ключа) и возможность обхода дерева не только сверху вниз, но и снизу вверх. Чем такие методы представления графов лучше, чем хранение сыновей линейным списком? -- тем, что если не повезло и сыновей много, сложность линейного поиска нужного сына становится пропорциональной мощности алфавита; при использовании хэширования среднее время поиска и вставки будет оставаться константным (при правильной реализации, в особенности первого метода, хэширование быстрее линейного поиска). Кроме того, при хэшировании разрешением коллизий цепочками (первый способ) время поиска в наихудшем случае будет не хуже линейного поиска сына по односвязному списку, т.к. длина хэш-цепочки не может превышать размер алфавита. Уфф... Вроде все. Удачи, АК --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 07 Jun 01 10:56:19 To : All Subj : Re: Huffman From: "Vadim Yoockin" <vy@thermosyn.com> Reply-To: "Vadim Yoockin" <vy@thermosyn.com> John Beliakov <John.Beliakov@p555.f203.n50.z2.fidonet.org> сообщил в новостях следующее:991876043@p555.f203.n50.z2.FidoNet.ftn... > V> Там два алгоритма: MSZIP и LZX. Оба являются > V> производными от алгоритма LZ77 (A. Lempel, J. Ziv, > V> 1977). > > В CabMan2000 Там расписаны эти названия: > MSZIP, LZ18-22. LZ18-22 - это не метод. 18-22 характеризует размер словаря. А именно, 2 в степени этого числа и есть размер. > Я про то, что может LZ23 появился (я думаю со словарем 4мб) или выше. И вообще, > - что мешает делать архиваторы, скажем со словарями 128мб ?? Хрен с ней, со > скоростью - зато сжимать будут офигенно. Сила сжатия с ростом словаря после некоторого предела растет довольно медленно. Hа скорость влияние гораздо больше. Поэтому увеличивать словарь имеет смысл очень редко - только когда жмется несколько очень похожих файлов гигантского размера. > >> , но чую, что есть и по-круче него. > V> Тебе для того, чтобы пользоваться или для того, > V> чтобы просто потестировать? > > А есть разница? Мне нужен самый ОФИГИТЕЛЬHОСЖИМАЮЩИЙ архиватор и не плохо бы > исходников к нему. Просто друзьям в институте очень часто приходится много > файла на дискетки кидать, размер важен. А скорость - меня не интересует. PPMonstr, RK. Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 07 Jun 01 12:43:19 To : All Subj : Re: Хранение растущего дерева From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> Привет, Dima ! > VS> struct СStat > VS> { > VS> unsigned char Symbol; > VS> unsigned int Counter; > VS> CStat * SonsStat; > VS> }; > > VS> Более эффективного решения, судя по всему, > VS> не существует. > > Я не понял где здесь указатель на следующий > уpовень деpева (пеpеход от статистики по пеpвому > символу к статистике паp символов)?? Или каждый > уpовень деpева хpанится в отдельном массиве? > Котоpый еще и pастет пpи pаботе?! Именно так. > А так получился пpимитивный список. Фактически мне > и интеpесно как эффективно хpанить его (точнее, все же > деpево) в линейной памяти - ты пpосто пеpеложил эту > пpоблему на компилятоp. Я не исследовал специально > как именно компилятоp все это хpанит, но думаю, imho, > не лучше pеализации деpева в линейном массиве - нет? > Pазве только скоpость чуть выше будет (за счет оптими- > зиpованности библиотек). А при чем здесь компилятор? Если я добавлю в структуру размер следующего уровня дерева и память буду выделять сам - в заранее выделенной для этого достаточно большой области (то есть просто очень большой массив CStat-ов), то это скомпилится на любом C/C++ компиляторе. > Здесь еще не понял pазмеp указателя на эту стpуктуpу - > типично это будет тоже unsigned int, так ведь? Тогда > огpаничив память 16Мб (или 16М узлов) можно > запихнуть Symbol в стаpший байт указателя :) Я же просто высказал идею. > И все же, для более-менее одноpодных статистик > (когда встpечаются почти все возможные символы > после данного) будет оптимальней выделять сpазу > массив счетчиков (скажем сpазу 256, или частями > по 32). Это позволит не хpанить ни сам символ, > ни указатель на следующий узел деpева на данном уpовне. Hа самом деле разумно делать так. Первые два уровня хранятся в хэш-таблицах, а оставшиеся - как и прежде. Элементы хэш-таблиц являются корневыми узлами для соответствующих кустов. > Или еще мысль. Если сделать пустой лист у узлов деpева, > то в внутpенних узлах можно не хpанить счетчик - он pавен > сумме счетчиков поддеpевьев. Ведь анализ счетчиков нужен > всего однажды, можно и поблуждать по деpеву для подсчета :)) > Хотя это всего лишь тpивиальный обход деpева в глубину. Я ведь изложил наиболее общий подход. Для каждой конкретной задачи, естественно, можно найти более выгодное решение. Задачу-то ты до конца не расписал. Кстати, PPMd/PPMonstr используют структуры данных, эквивалентные описанным. Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 07 Jun 01 12:43:19 To : All Subj : Re: Хранение растущего дерева From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> Привет, Андрей ! > Чем такие методы представления графов лучше, чем хранение сыновей линейным > списком? -- тем, что > если не повезло и сыновей много, сложность линейного поиска нужного сына > становится пропорциональной > мощности алфавита; при использовании хэширования среднее время поиска и > вставки будет оставаться > константным (при правильной реализации, в особенности первого метода, > хэширование быстрее линейного поиска). Кроме того, при хэшировании > разрешением коллизий цепочками (первый способ) > время поиска в наихудшем случае будет не хуже линейного поиска сына по > односвязному списку, т.к. > длина хэш-цепочки не может превышать размер алфавита. Еще есть прикольный метод - хэширование с последующим расслаиванием. То есть имеется хэш-таблица, которая содержит указатели на какие-то хэш-множества. Если множество мало, оно хранится просто как массив. Если оно становится достаточно большим, на его месте появляется еще одна хэш-таблица (множество расслаивается). И так далее. Hасколько я понимаю, так работает IMP (а работает он очень быстро). В конечном итоге, все, безусловно, зависит от задачи. Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 07 Jun 01 13:07:56 To : All Subj : Re: Huffman From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> Привет, John ! > V> Тебе для того, чтобы пользоваться или для того, > V> чтобы просто потестировать? > > А есть разница? Понимаешь, PPMonstr и RK это, конечно, очень круто, но первый имеет минимум чисто архиваторных возможностей (он, например, не умеет создавать архив из нескольких файлов), а второй - сильно тормозит, да и глючит время от времени (распаковывает с ошибками). Поэтому я для собственных нужд пользуюсь IMP-ом, а для нужд окружающих - PKZIP-ом. (Hу еще иногда RAR-ом и CABARC-ом.) Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400)
Предыдущий блок Следующий блок Вернуться в индекс