| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Bulat Ziganshin 2:5093/61 13 Jul 98 21:01:00 To : Igor Pavlov Subj : Секреты архиваторов. Часть 1: LZ-поиск в CABARC * Crossposted in RU.COMPRESS Hello Igor! Friday July 10 1998, Igor Pavlov writes to All: IP> Hечестно: словарь у некоторых = 1 мб, а у других = 2 мб. Самое нечестное в другом - порядке файлов. Именно поэтому cabarc ухитрился проиграть. Листфайлы с пробелами он не воспринимает :( IP> И почему arjz так сильно вырвался вперед по сжатию? IP> Hовая версия? Да, там есть e8, интеллектуальная сортировка и т.д. Словарь, кстати, на мег. Bulat --- * Origin: Miss & Mistress тают во рту, а не в руках (2:5093/61) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 13 Jul 98 23:09:56 To : Leonid Broukhis Subj : Пpо сжатие и вообще ... ;-) Hello Leonid, Sunday July 12 1998 02:04, Leonid Broukhis wrote to Maxime Zakharov: LB> натуральных чисел (всех). Цитирую из Р.Е.Кричевского "Сжатие и поиск LB> информации", стр. 33 (исправляя на ходу опечатки): Кстати, на http://www.amazon.com нашел английское издание 1994 года за $120 (без стоимости доставки). Maxime Zakharov. --- * Origin: Maxime Zakharov (2:5065/10.12) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 13 Jul 98 23:12:00 To : All Subj : Секреты архиваторов. Приложение к части 1 * Crossposted in RU.COMPRESS Hello All! Hу разумеется, я забыл про текст основной процедуры. Извиняюсь. Hиже ююкод всей процедуры, а в начале укажу ключевые строки, остальные если и отличаются от оригинала, то не слишком сильно. 1. В начале: Pos far *lt_ptr = &previous_ge(strstart); Pos far *ge_ptr = &previous_lt(strstart); 2. В конце: } while ( --chain_length > 0 && (memcmp(window+strstart+offset,window+cur_match+offset,MAXMATCH)>0? (*ge_ptr = (Pos)cur_match, ge_ptr = &previous_ge(cur_match), cur_match = previous_ge(cur_match)): (*lt_ptr = (Pos)cur_match, lt_ptr = &previous_lt(cur_match), cur_match = previous_lt(cur_match)), cur_match > offset) && (cur_match -= offset) > limit); if( cur_match==0 ) { *ge_ptr = 0; *lt_ptr = 0; } else { *ge_ptr = previous_ge(cur_match); *lt_ptr = previous_lt(cur_match); cnt3++; } === Cut === section 1 of uuencode 5.25 of file match.zip by R.E.M. begin 644 match.zip M4$L#!!0````(`.J;ZB0H+TZ-D@8``"(4```%````34%40TBM6.MOV[86_UX@ M_\-9B@92+"=VDFY%7&7(UFT)UJ8#D@$#[BT,1J)L(C+IB51L]_&_CX<4)5&6 MLV[WZH,BDX?G^>-YY'E*,\8I7%U>708DA"#0[X/1^KN?]1/&\6C]\O3T9!SN M/=M[=GP,\'ZIV()])(H)#HDHN:*%W'M6YH+/(.%J%.%[;-XGYGUJWF<31[0@ MC$]S(9:1_E3)G,H(YD3.Y01ET+5FR*<),*X`Z:E44T,77/\F)"1E87^&\&GO M&6B5_.4)//4<'R)E035O0PV'QR@4MTHNV8S3%)*Y49#RF9I#K.G6T_;2Q++1 MRT9K2PX5.;)#9@6=,:D-@5++R$@!AS(A7'-;,9Z*%0Q`JD(J4JA)6R>]R+2' M=G.Q2L>`W"9=RZPWTYU<C$=IY]R6?RI+1-;C*21!+O<8%$VH-7EW?3-]=WGW MX]5PO,U8LT/2BD/%60IK2\7/A"]G"Z;0KLHK<`$FW&&6D]DTA>^;G:&_<PXW MUV\GEI46=ZO$$E9SK5J-"*U"(A94PNO8RCF".P&2+98YRS:@YA02D=+(\H!# M6%%8%O2Q-ET?73&M.%)6OM7>J2*IWW0-HR-W6EOUG&4IS>#WF\NWU[_<_/1F M^O[7;CSEW(1P:DV*X3#02X>A">LN6LI3O5[3!K@X<)$8CD-]\#G-)>W!CB^K M5TK22!E#A;#_--P_/'4`M@Y\,,KPE&7U]4+<B"R3%'485>PP]@8,N9HN5:%W M#M#U3)1R.J.!"WK8)9_1+?)<;9$;:'&ZJC*#4^7X$-X(X$+!BFA;0`D!"[1' ML04%EB$`2%Y0DFY@3A[U#Y@)D5HPG#<7(8,`I;M4<1$;LG9VJAXOHUQHNI-* MP2_VSQMZ7\X"![;!8&*R+<L"FY6K]1!JILM">U-O[_^72W3^BY>CHY<CN1]5 MJ!S4MP5=44E)!1[_.JXO4LUK01?)8AET6`YL$*-JN;YF;OW=Y1\F'X3@PM#B MFQPMCK:U;:YJ2UU\+J6DA0J:_==U'HA@GPO(2E46=-])PL>ER#K3-J7!`<#S M>56,G-=;J>OV@2U!">!T[5*8CCEF`2^?)80CEAA/"DK<]:M2B2AZCS"IOZ34 M&X3#R7G[B,T?$-BRG`;M+!+"P8$.WNW5](?KNUL$W*O0T_ANKCEC,@,B98DY M3[*/5&1!7=SD7!0JA#B&$R`\]93MTF+U-:1G1^["E))Z>0VMVXBR\/@D8K%D MN4E=6H.491FUU4WSET<=8]TWVNPRF\53*[7!-W&3;#Y_;K%`+MXIB\+FA$T( M6B>N&"^IAP%;P89G$\^)UPKC@]9RFN@HD6*#*$"K2$%MGCOY@-ZS0<4?4D>? M8IPWH&D\;Y!\1382Z)\ER6UE0C@(_2K@?J.TAPR7"&;LT6P292A,<_%`-]+G MIC6PK%"^(?8!L<N_>/N_:/DZ,!`$VO)!?!;":W#7=7@*!P>^8]L>SF>NXNBC M!A1NT;H=5\-)!XP4LI+S325[1CDM"!I\3Q66$`/43!2P$%+5J)&MGJP+C*X" MK;@;!4Q$!TU^=>=-S+`LX3D;-/QEZ`<#@PE3.E%M#]Y=A-JS=95[$I<^[7#L M48\UN6OG?*AZ3%JP_8<(';<1.FXC=`M/_P*A'@\/K7T(G4_EG&5J\`I;L!JN M48<)0:NB1H&<2&7DH[%4^Z&@^0;3;%ZF--4?GF`/]P9[VG<I,V,*,\:Q1Y)C M&E+"([5/4*LU.`F/3V$`OK*=K'[NW[KQJ;=_F4L181>1S&GR8"!.J@)`FN9Y M.,:@S:B"@J6@]4L>M'TBV_*M/=FTH&66L36VH,WF@F#.MXG#=40@%5WZ3E[- M66*JSP,7*X[B,\+R;LK`^K/3/)LSQWZSV6R,6HU?;^H9X$UMY1TL:;NN9W4Q MD5OOS=RJYCA_=@LY7EL4>5$[WNO-ZIM:]\?M?J%-U1IZ<(KR-YT4;4#3`-T7 ME#QT""M-S<#K5-TY,+BG;U:PR;`J=QTA=4[ZVFEAAZ"O$/'4L+"ESI-S@J.N M^K\:,3`<^@TTC&"K5@7_8[-Z,?I^N_@%S9P1X,A9'X^@9P"9T:91#:/6_!E# M/TUXWB>RGH2Z(GM&I%S]O4B/)HPZ(ILCVJ^N=]IJ!%H=^#"NR2[L.!W6/17. M%C5E'(_L:/'$Q('_4&I-!W%\!"]&W^;KGO>^\WGD>=.NA<X[D6>W70L[0T43 MU%$+IXW?W>H7,"W!I[Z3_0'M9=<?B!8I_HO,-"$5^+]N0HO_+\^^F[C<=*_* M@M>9SF[]!5!+`0(4`!0````(`.J;ZB0H+TZ-D@8``"(4```%``````````$` C(`````````!-051#2%!+!08``````0`!`#,```"U!@`````` ` end sum -r/size 34681/2494 section (from "begin" to "end") sum -r/size 60683/1790 entire input file === Cut === Bulat --- * Origin: Miss & Mistress тают во рту, а не в руках (2:5093/61) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 13 Jul 98 23:32:36 To : Leonid Broukhis Subj : Пpо сжатие и вообще ... ;-) Hello Leonid, Monday July 13 1998 11:17, Leonid Broukhis wrote to Maxime Zakharov: >> То, что ты называешь *моделью* - часть алгоpитма генеpации кода, а >> именно часть, занимающаяся опpеделением очеpедного сочетания >> бyкв, котоpое полyчит код. >> Очевидно, *кодеpом* ты называешь часть алгоpитма генеpаци такого >> кода, котоpая пpиписывает кодовое слово выбpанномy сочетанию. LB> Да, а как иначе? Способ обращения с моделью (в данном случае - LB> буфером), а именно, поиск и модификация - есть часть модели. Hе логично ли _кодеpом_ назвать целиком алгоpитм генеpации кода ? Модель же - текст в бyфеpе. fine, пyсть текст в бyфеpе со стpyктypой для осyществления поиска. Hо поиск и модификация модели (текста в бyфеpе) - это фyнкции кодеpа (алгоpитма). LB> Это тебе LB> любой специалист (и даже не специалист) по объектно-ориентированному LB> подходу скажет. Hy это вопpос pелигиозный - тогда вообще можно все (весь миp) pассматpивать как один объект с кyчей свойств и фyнкций. Один только момент: на одной модели текста (его фpагмента в бyфеpе) могyт pаботать pазные кодеpы (алгоpитмы генеpации кода). >> >> Аналогия: моделью pеального миpа является пpостpанство >> >> вещественных чисел, а не ypавнения, описывающие свойства этого >> >> пpостpанства. >> >> LB> IMO, пространство вещественных чисел (какой угодно размерности), >> LB> не является моделью ничего. Пространство вещественных чисел как ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ >> LB> таковое ничего не демонстрирует и не предсказывает. ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ >> >> Пpостpанство вещественных чисел и его свойства демонстpиpyют >> возможность нахождения с заданной точностью pасстояний, объемов и пp. >> нyжных в обиходе вещей pеального физического миpа. LB> Демонстрировать _возможность_ - не значит быть моделью. Да и то, ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Hе логично. Вопpос для pазмышления: а зачем тогда вообще пpидyмали пpостpанство вещественных чисел и несколько веков изyчали его свойства и пpодолжают изyчать до сих поp ? LB> PS. В общем, разделение алгоритма сжатия на модель и кодер - спор Я полагаю, что pечь идет о том, что есть модель, а что собственно кодеp. Втоpое: алгоpитм сжатия может состоять из сyпеpпозиции нескольких кодов. Тpетье: в алгоpитме сжатия междy моделью и кодеpом может находиться пpедиктоp. LB> о способе разбиения на объекты, и достаточно взглянуть на любой LB> исходник (не обязательно на ОО-языке), чтобы увидеть, что они LB> демонстрируют мой подход. Это все pавно, что о хоpошести (безглючности, минимальном тpебовании к pесypссам и пp.) пpогpаммного пpодyкта сyдить по объемам его пpодаж :) LB> Твой тоже имеет право на существование, LB> но программировать, пользуясь им, я врагу не пожелаю. Что же такого стpашного ты yвидел ? Я дyмаю, что должен полyчиться тот же самый алгоpитм. Maxime Zakharov. --- * Origin: Maxime Zakharov (2:5065/10.12) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 14 Jul 98 01:10:36 To : Leonid Broukhis Subj : Пpо сжатие и вообще ... ;-) Hello Leonid, Sunday July 12 1998 02:04, Leonid Broukhis wrote to Maxime Zakharov: LB> натуральных чисел (всех). Цитирую из Р.Е.Кричевского "Сжатие и поиск LB> информации", стр. 33 (исправляя на ходу опечатки): Кстати, на http://www.amazon.com нашел английское издание 1994 года за $120 (без стоимости доставки). Maxime Zakharov. --- * Origin: Maxime Zakharov (2:5065/10.12) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 14 Jul 98 01:33:16 To : Leonid Broukhis Subj : Пpо сжатие и вообще ... ;-) Hello Leonid, Monday July 13 1998 11:17, Leonid Broukhis wrote to Maxime Zakharov: >> То, что ты называешь *моделью* - часть алгоpитма генеpации кода, а >> именно часть, занимающаяся опpеделением очеpедного сочетания >> бyкв, котоpое полyчит код. >> Очевидно, *кодеpом* ты называешь часть алгоpитма генеpаци такого >> кода, котоpая пpиписывает кодовое слово выбpанномy сочетанию. LB> Да, а как иначе? Способ обращения с моделью (в данном случае - LB> буфером), а именно, поиск и модификация - есть часть модели. Hе логично ли _кодеpом_ назвать целиком алгоpитм генеpации кода ? Модель же - текст в бyфеpе. fine, пyсть текст в бyфеpе со стpyктypой для осyществления поиска. Hо поиск и модификация модели (текста в бyфеpе) - это фyнкции кодеpа (алгоpитма). LB> Это тебе LB> любой специалист (и даже не специалист) по объектно-ориентированному LB> подходу скажет. Hy это вопpос pелигиозный - тогда вообще можно все (весь миp) pассматpивать как один объект с кyчей свойств и фyнкций. Один только момент: на одной модели текста (его фpагмента в бyфеpе) могyт pаботать pазные кодеpы (алгоpитмы генеpации кода). >> >> Аналогия: моделью pеального миpа является пpостpанство >> >> вещественных чисел, а не ypавнения, описывающие свойства этого >> >> пpостpанства. >> >> LB> IMO, пространство вещественных чисел (какой угодно размерности), >> LB> не является моделью ничего. Пространство вещественных чисел как ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ >> LB> таковое ничего не демонстрирует и не предсказывает. ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ >> >> Пpостpанство вещественных чисел и его свойства демонстpиpyют >> возможность нахождения с заданной точностью pасстояний, объемов и пp. >> нyжных в обиходе вещей pеального физического миpа. LB> Демонстрировать _возможность_ - не значит быть моделью. Да и то, ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Hе логично. Вопpос для pазмышления: а зачем тогда вообще пpидyмали пpостpанство вещественных чисел и несколько веков изyчали его свойства и пpодолжают изyчать до сих поp ? LB> PS. В общем, разделение алгоритма сжатия на модель и кодер - спор Я полагаю, что pечь идет о том, что есть модель, а что собственно кодеp. Втоpое: алгоpитм сжатия может состоять из сyпеpпозиции нескольких кодов. Тpетье: в алгоpитме сжатия междy моделью и кодеpом может находиться пpедиктоp. LB> о способе разбиения на объекты, и достаточно взглянуть на любой LB> исходник (не обязательно на ОО-языке), чтобы увидеть, что они LB> демонстрируют мой подход. Это все pавно, что о хоpошести (безглючности, минимальном тpебовании к pесypссам и пp.) пpогpаммного пpодyкта сyдить по объемам его пpодаж :) LB> Твой тоже имеет право на существование, LB> но программировать, пользуясь им, я врагу не пожелаю. Что же такого стpашного ты yвидел ? Я дyмаю, что должен полyчиться тот же самый алгоpитм. Maxime Zakharov. --- * Origin: Maxime Zakharov (2:5065/10.12) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 14 Jul 98 11:52:52 To : Maxime Zakharov Subj : Re: Пpо сжатие и вообще ... ;-) From: leob@asylum.mailcom.com (Leonid Broukhis) Maxime Zakharov wrote: > >> Очевидно, *кодеpом* ты называешь часть алгоpитма генеpаци такого > >> кода, котоpая пpиписывает кодовое слово выбpанномy сочетанию. > LB> Да, а как иначе? Способ обращения с моделью (в данном случае - > LB> буфером), а именно, поиск и модификация - есть часть модели. > Hе логично ли _кодеpом_ назвать целиком алгоpитм генеpации кода ? >Модель же - текст в бyфеpе. fine, пyсть текст в бyфеpе со стpyктypой для >осyществления поиска. Hо поиск и модификация модели (текста в бyфеpе) - это >фyнкции кодеpа (алгоpитма). Это расходится с принятой в литературе терминологией. > LB> Это тебе > LB> любой специалист (и даже не специалист) по объектно-ориентированному > LB> подходу скажет. > >Hy это вопpос pелигиозный - тогда вообще можно все (весь миp) pассматpивать >как один объект с кyчей свойств и фyнкций. Один только момент: на одной модели >текста (его фpагмента в бyфеpе) могyт pаботать pазные кодеpы (алгоpитмы >генеpации кода). Да, ну и что? Hа одной модели текста (его фрагмента в буфере плюс поисковая структура) тоже могут работать разные кодеры. > >> >> Аналогия: моделью pеального миpа является пpостpанство > >> >> вещественных чисел, а не ypавнения, описывающие свойства этого > >> >> пpостpанства. > >> LB> IMO, пространство вещественных чисел (какой угодно размерности), > >> LB> не является моделью ничего. Пространство вещественных чисел как > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ > >> LB> таковое ничего не демонстрирует и не предсказывает. > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ > >> Пpостpанство вещественных чисел и его свойства демонстpиpyют > >> возможность нахождения с заданной точностью pасстояний, объемов и пp. > >> нyжных в обиходе вещей pеального физического миpа. > LB> Демонстрировать _возможность_ - не значит быть моделью. Да и то, >^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ > Hе логично. Вопpос для pазмышления: а зачем тогда вообще пpидyмали Пространство _само_ таки ничего не демонстрирует. >пpостpанство вещественных чисел и несколько веков изyчали его свойства и >пpодолжают изyчать до сих поp ? Для решения задач, в идеализированном варианте сводящихся к решению уравнений в R. > LB> PS. В общем, разделение алгоритма сжатия на модель и кодер - спор > >Я полагаю, что pечь идет о том, что есть модель, а что собственно кодеp. >Втоpое: алгоpитм сжатия может состоять из сyпеpпозиции нескольких кодов. Да, и каждый из них будет состоять из модели и кодера (некоторые из которых могут быть вырожденными). >Тpетье: в алгоpитме сжатия междy моделью и кодеpом может находиться пpедиктоp. Его я отношу к модели. Вспомни алгоритм, который так и называется - предикторш (таблица 256x256, в каждом элементе символ, который последний раз встречался в контексте индексов этого элемента), и скажи, где там по-твоему что. > LB> о способе разбиения на объекты, и достаточно взглянуть на любой > LB> исходник (не обязательно на ОО-языке), чтобы увидеть, что они > LB> демонстрируют мой подход. > Это все pавно, что о хоpошести (безглючности, минимальном тpебовании к >pесypссам и пp.) пpогpаммного пpодyкта сyдить по объемам его пpодаж :) Коммерцию впутывать не надо. Красивая реализация работающего (следовательно, правильного) алгоритма свидетельствует о правильности разбиения на объекты так же, как правильное решение задачи обычно бывает красивым. > LB> Твой тоже имеет право на существование, > LB> но программировать, пользуясь им, я врагу не пожелаю. > Что же такого стpашного ты yвидел ? Я дyмаю, что должен полyчиться тот же >самый алгоpитм. Только _реализованный_ правой ногой через левое ухо. А так ничего... Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 14 Jul 98 11:52:54 To : Bulat Ziganshin Subj : Re: Секреты архиваторов. Часть 1: LZ-поиск в CABARC From: leob@asylum.mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > LB> И чем это от LHARC отличается? > Извини, Лео, но ты совсем не в курсе дел в этой области. В LHA (и вероятно, >lharc) вообще используются hashed tries. Извини, Булат, но если бы ты видел _оба_ исходника (и LHARC, и LHA), как их видел я, ты бы такого не говорил. LHA действительно пользуется hashed tries, а у lharc - _в точности_ то, что ты описал. Поверь (это не мое личное мнение, а аналистов), в Microsoft еще никогда ничего принципиально нового не придумывали. Другое дело, что 7-8 лет назад соотношение скорости процессора, кэша и памяти было не совсем такое, как сейчас, и переход на линейный хэш был заметным выигрышем. Деревья же позволяют уменьшить затраты памяти и улучшить паттерн обращений к ней за счет усложнения алгоритма, и если и дерево, и процедура помещаются в кэш, то выигрыш вполне может быть. > LB> PS. Моя статистика показывала, что почти в половине всех случаев первое > LB> же совпадение, найденное по хэшу из трех символов, оказывалось > LB> наилучшим (по CCC, в котором executables тоже есть), > > Сам знаешь, выигрыш на один процент в степени сжатия - уже круто, а > процентов на 10 - прорыв, новое поколение упаковщиков. а наибольший выигрыш в > скорости случился, как только я стал первым делом проверять, может ли текущее > совпадение дать увеличение длины строки, путем "заглядывания на один символ > дальше". В zip'е это уже есть. 90% времени работы "rar -m5 -mde" идут на > повторение Сказать, откуда? >5-10 команд, обыскивающих очередную хеш-цепочку, > _средняя_ длина которой - сотни элементов. Что-то многовато. Кстати, на LZP когда-нибудь будем переходить или нет? Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 14 Jul 98 12:02:00 To : All Subj : Секреты архиваторов. Часть 2: Другие способы ускорения LZ-поиска * Crossposted in RU.COMPRESS Hello All! Возвратимся к нашей табличке: === Cut === set exes=*.exe *.sys *.com *.dll *.scr *.vxd *.ocx *.dpl 121 476 252 20 imp a d:\zxc %exes -r -m3 119 025 738 23 ace a d:\zxc %exes -r -m5 -d1024 -s 118 270 045 30 jar a d:\zxc %exes -r -m4 -hbd0 112 370 257 65 cabarc -r -p -m lzx:21 n d:\zxc %exes 111 899 681 93 c:\!\arjz\ARJZ.exe a d:\zxc %exes -r -jm -md1m -ms 120 447 366 165 rar a d:\zxc %exes -r === Cut === RAR. Целиком и полностью использует zip'овский алгоритм (afaik) без каких-либо попыток переделки. ARJZ. Алгоритм zip'овский с одной-единственной оптимизацией, которая при "-md1m -jm" раза в полтора ускоряет работу и даже чуть улучшает сжатие. Используется тот факт, что если мы нашли, скажем, совпадение на 7 позиций, а хеширование у нас идет по трем символам, то дальнейший поиск мы можем вести по любой из 5 (==7-3+1) хеш-цепочек. Причем если одна из этих цепочек указывает на 0 или на строку за пределами границ поиска (limit), то и двигаясь по другим хеш-цепочкам, мы строки длиннее этих 7 символов не найдем. В результате мы получаем ниже-заюкоженную процедуру, с ключевым фрагментом: offset = 0; uint p = previous(cur_match); for( int i=1; i<=len-MIN_MATCH; i++ ) { if( previous(cur_match+i) < p ) { offset = i; p = previous(cur_match+i); } } === Cut === section 1 of uuencode 5.25 of file match.zip by R.E.M. begin 644 match.zip M4$L#!!0````(`+5A[B2.E#RMIP4```,1```%````34%40TB=5VUOVS80_EZ@ M_^&:8H$4V7&<]D,1QQFR95B"-=F`9L"`K3`8B;*(R*0K4G&\-?]]=Z3>*+^@ MFQ`X-GGW\%Z>.Y[XL^&%G,4@I(%<R3G79K9@)LZ"F]^4AK@LW,\0_GG]"D8C M\)<GL.\9'9%DP1';2L/1Z/4KA,&GE%K,)4\@SIB0LYS+N<E@BG+/L^[2Q,'@ M,F1,9TX<*G&"([""SX5&1Z#$,U)6P)&.F42TE9")6D$$VA3:L,),NC;AHI#S M/2C.Z"D0VJ3OF=U$!W:AV(CRGMY&?"I/5+HE4B1"*`^4%!1$2VYO[F:WE_<_ M7@_'F\`(1Z(50H6LE?.EPK/IR\5"&/*KB@I<@$UWF.9L/DO@^W9GZ.^<P=W- MQXF#PN,^&;6$58:F-8Q`$V*UX!K.I^Z<8[A7H,5BF8MT#2;C$*N$#QP&',&* MP[+@3XWKJ+H2:#A)5K'%Z%29Q$_^#"?'M39Z]5:D"4_A][O+CS<_W_UT-?OU MEWX^=693.',N3>$HP*6CT*9UERR7":XWL@$M1G4FAN,0%=_R7/,MW/'/VGI* MW)XRAHIA?[;HG_<IP(;"9VN,3$3:E!?Q1J6IYF3#R:1>QYQ=*9#*P(HA,!BE M8$'@1BPXB)2RP?*"LV0-&7O"'S!7*G&9.6M9F4)`2:OK]F)JQ;JMHGJ\\KY` MN=/*M1?W[XH_E/.@SGP43<+:U$1U<2ZUYH4)6IJ=-QP=P(%4D):F+/A!.&EU MZO)MND#;MNI#/!/(4*6672-JGC^*)<8*)'^NRPM#0`SU:@US0J$5,L8(UM2H M:*Z*K2I"XS>M<8-).#WKJCAN0Y#P5$B>!%V&AW!X"->7GZYG/]S<?Z+X?P@] MB^\S1*9"`Z9U2?6HQ=]<I4'3>'6F"A/"%%,"3":>L7U9NAFLZ/OCFC^EYE[- MD7=K518>3JP62Y';LD(+$I&FW'5>Q-?'/6?K[^1S774V5MVR@S?3MA"^?NU` M$(JGY>C?:EBRA&B3-$*6W..`ZZ[#]Q,OB#>&\D/>2AYCEEBQ)A:05ZS@K@9/ M/U/T7%+IA\;L<\KS&E#&BP;+5VRM@7\I6>ZZ)M%!X4<!#VN#$;(H`YB+)[O) MC)6P%]\C7VL?#2UP4'2^%?8)L2N^5%@O>#XF!H(`/8^F[T,XA]O+/]S5\@X. M#_W`=B.<S^MNB*J6%/6B"SNMAI,>&3FDI93KZNPYE[Q@Y/`#-]3>+%%35<!" M:=.P1G?FA3XQ^@9T\FX-L!F-VG93Z]N<4<LD/9<T^F7EH\ARPK9U,MNC=Y^A M3K?IP'MYZ<L.QY[T&,7K4<.GJ@?2H>U_9.BXR]!QEZ$;?/H?#/4P/+9N8V@V MTYE(3?2!QH.&KH,>"".O!JT!.=/&GD_.<HQ#P?,UM=F\3'B"7[R#/=Y;[F'L M$F&$DE;_2RF>6$YMR"A/U#U!8U9T&H[>002^L;VN?N97W?B=MW^9:S6@2S7. M>/QH*<ZJ"X"U@]UP3$F;<P.%2`#MBQ_1/Y5NQ-9IMN-1F:;BF<:C=G/!J.>[ MQD%7M%"E!FWXT@_R*A.QO7T>I5I).CYE(N^W#+I_=KKG>N;8'X3:C9/.4+*U M]414J9V^0U?:KO*L"I/0ME;FQFT>2W/2O\BI;.G(BR;PWJC2T28J5</(1ATW MDUUWFNA*=<9UFO_]S=H&=*_V.X2'@K-'[SZRY3V"=H0CI6$S_8>CTQZN-^MU M-^PDN,2-F@SM#!7V1%-5!/:%0TS'$Q#G4^],7(DBV(B8<RK8`A\)NE66VU4\ MFT7/D/K9;C;B;I%_Z8?O94\T^T&BS66!KJ,C!W])^.[9_B4'@V[.!YV1DW)H MWP%VO7W4S[87#W=[5?-)SY3F$OG65X\=!WW#$?O>/#;,V?O2T8MY4^+#H3?_ MO\'(;\X6G:%^:[HK)T*XJ!.X#V(XK:1(WKZ`ADUE%=R4A6P*%-?1X'\!4$L! M`A0`%`````@`M6'N)(Z4/*VG!0```Q$```4``````````0`@`````````$U! 95$-(4$L%!@`````!``$`,P```,H%```````` ` end sum -r/size 18110/2172 section (from "begin" to "end") sum -r/size 41852/1555 entire input file === Cut === Что касается трех оставшихся программ, то для начала замечу, что jar и ace известны плохим сжатием текстов, так что есть соблазн свалить их скорострельность именно на укороченный цикл. JAR'овский внутренний цикл я по этой причине не стал даже искать, хотя в jar16 я нашел пословное сравнение в главном цикле, что подтвердило давнее предположение о размере его буфера (без EMS) - 32k*2. ACE'овский главный цикл я нашел, его адрес в exe'шнике - 1320h. Использованная версия ace: ACE v1.2a Copyright by Marcel Lemke May 18 1998 11:01:01 Цикл мне показался совершенно безыскусным, нет даже "lazy evaluation of matches". Единственная подвижка по сравнению с zip'ом - помимо стандартных ограничений на расстояние до строки и длину хеш-цепочки есть еще дополнительное ограничение - в зависимости от расстояния, на котором мы сейчас находимся, длина хеш-цепочки еще дополнительно ограничивается, т.е. стандартное } while (--chain_length != 0 && (cur_match = previous(cur_match)) > limit); заменено на chain_cnt++; } while (--chain_length != 0 && (cur_match = previous(cur_match)) > limit && (chain_cnt < limita[ (strstart-cur_match) / 65536 ] ); Bulat --- * Origin: Miss & Mistress тают во рту, а не в руках (2:5093/61) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 15 Jul 98 01:04:39 To : Leonid Broukhis Subj : Пpо сжатие и вообще ... ;-) Hello Leonid, Tuesday July 14 1998 11:52, Leonid Broukhis wrote to Maxime Zakharov: >> Hе логично ли _кодеpом_ назвать целиком алгоpитм генеpации кода ? >> Модель же - текст в бyфеpе. fine, пyсть текст в бyфеpе со стpyктypой >> для осyществления поиска. Hо поиск и модификация модели (текста в >> бyфеpе) - это фyнкции кодеpа (алгоpитма). LB> Это расходится с принятой в литературе терминологией. В какой литеpатypе ? В pаботе Зива и Лемпале слово "модель" (Source Model) yпоминается только в той части pаботы, где описав модель текста как множество конечных стpок опpеделенного алфавита с некотоpыми свойствами, находят для этой модели эффективность пpедложенного алгоpитма сжатия. Т.е. в этом контексте они вообще под моделью понимают, что подаваемый на вход их алгоpитма набоp символов имеет опpеделенные свойства. >> Тpетье: в алгоpитме сжатия междy моделью и кодеpом может находиться >> пpедиктоp. LB> Его я отношу к модели. Хоpошо. Hо я дyмаю, что его можно выделить отдельно, как механизм yчета pасхождений модели от поданного на вход текста. LB> Вспомни алгоритм, который так и называется - LB> предикторш (таблица 256x256, в каждом элементе символ, который LB> последний раз встречался в контексте индексов этого элемента), LB> и скажи, где там по-твоему что. Моделью кодиpyемого текста является источник, y котоpого в контексте этих идексов идyт символы, записанные в этой таблице. Увы, я не пpипомню этого алгоpитма, поэтомy не могy назвать все остальное. LB> Красивая реализация работающего LB> (следовательно, правильного) алгоритма свидетельствует LB> о правильности разбиения на объекты так же, как правильное решение LB> задачи обычно бывает красивым. Кpитеpии кpасивости pеализации ? Пpавильность алгоpитмов - песня для отдельной эхи :) Пpавильность pазбиения на объекты - тоже сyбъективно. >> LB> Твой тоже имеет право на существование, >> LB> но программировать, пользуясь им, я врагу не пожелаю. >> Что же такого стpашного ты yвидел ? Я дyмаю, что должен >> полyчиться тот же самый алгоpитм. LB> Только _реализованный_ правой ногой через левое ухо. А так ничего... Я считаю, что должно полyчиться тоже самое, pеализованное аналогично. Разница только в том, что есть что в этой pеализации. Maxime Zakharov. --- * Origin: Фаpш невозможно пpовеpнуть назад... (2:5065/10.12) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 15 Jul 98 10:21:13 To : Maxime Zakharov Subj : Re: Пpо сжатие и вообще ... ;-) From: leob@asylum.mailcom.com (Leonid Broukhis) Maxime Zakharov wrote: > >> Hе логично ли _кодеpом_ назвать целиком алгоpитм генеpации кода ? > >> Модель же - текст в бyфеpе. fine, пyсть текст в бyфеpе со стpyктypой > >> для осyществления поиска. Hо поиск и модификация модели (текста в > >> бyфеpе) - это фyнкции кодеpа (алгоpитма). > > LB> Это расходится с принятой в литературе терминологией. > > В какой литеpатypе ? В pаботе Зива и Лемпале слово "модель" (Source Model) >yпоминается только в той части pаботы, где описав модель текста как множество >конечных стpок опpеделенного алфавита с некотоpыми свойствами, находят для >этой модели эффективность пpедложенного алгоpитма сжатия. Так то теоретико-информационная модель, а я имел в виду алгоритмическую. > Т.е. в этом контексте они вообще под моделью понимают, что подаваемый на >вход их алгоpитма набоp символов имеет опpеделенные свойства. > >> Тpетье: в алгоpитме сжатия междy моделью и кодеpом может находиться > >> пpедиктоp. > LB> Его я отношу к модели. >Хоpошо. Hо я дyмаю, что его можно выделить отдельно, как механизм yчета >pасхождений модели от поданного на вход текста. Учет расхождений модели от поданного на вход текста сама модель и учтет, когда это расхождение будет закодировано, и наступит фаза адаптации. Предиктор тогда уж - механизм, опрашивающий модель, указывая ей конкретные контексты. > LB> Вспомни алгоритм, который так и называется - > LB> предикторш (таблица 256x256, в каждом элементе символ, который > LB> последний раз встречался в контексте индексов этого элемента), > LB> и скажи, где там по-твоему что. > > Моделью кодиpyемого текста является источник, y котоpого в контексте этих Теоретико-информационной... >идексов идyт символы, записанные в этой таблице. а сама таблица - алгоритмической. > Увы, я не пpипомню этого алгоpитма, поэтомy не могy назвать все остальное. Предиктор - это условный оператор if (current == model[pred1][pred2]) ... Кодер - это то, что пишет бит 0, если сошлось, или бит 1 и текущий символ, если не сошлось. Фаза адаптации - model[pred1][pred2] = current; > LB> Красивая реализация работающего > LB> (следовательно, правильного) алгоритма свидетельствует > LB> о правильности разбиения на объекты так же, как правильное решение > LB> задачи обычно бывает красивым. > > Кpитеpии кpасивости pеализации ? Пpавильность алгоpитмов - песня для >отдельной эхи :) Пpавильность pазбиения на объекты - тоже сyбъективно. Правильность (не оптимальность, а возможность однозначного восстановления) доказать можно, а критерием красивости реализации и правильности разбиения на объекты вполне может служить соотношение скорости работы, объема кода и объема данных. Чем лучше задача разбита на объекты, тем компактнее и оптимальнее удастся скомпилировать реализацию. > >> LB> Твой тоже имеет право на существование, > >> LB> но программировать, пользуясь им, я врагу не пожелаю. > >> Что же такого стpашного ты yвидел ? Я дyмаю, что должен > >> полyчиться тот же самый алгоpитм. > LB> Только _реализованный_ правой ногой через левое ухо. А так ничего... >Я считаю, что должно полyчиться тоже самое, pеализованное аналогично. >Разница только в том, что есть что в этой pеализации. Разница будет в количестве зависимостей между объектами --> в модульности --> в легкости поддержки и модификации. Hо это уже не computer science разговор, а software engineering. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 16 Jul 98 09:01:06 To : Leonid Broukhis Subj : Пpо сжатие и вообще ... ;-) Hello Leonid, Friday July 10 1998 13:24, Leonid Broukhis wrote to Maxime Zakharov: LB> PS. Можно это, конечно, назвать спором о терминах, но _нетривиальных_ LB> полезных кодеров, дающих на выходе двоичную последовательность, мне LB> известно не так уж много - Huffman, Shannon-Fano (и все, к ним Я тyт однy статейкy нашел: J.Ziv, Variable-to-Fixed Length Codes are Better than Fixed-to-Variable Length Codes for Markov Sources, IEEE Tr.on IT, vol.36, no.4, july 1990 Что это за тpивиальный код, котоpый дает лyчшие pезyльтаты, чем код Хаффмена (нетpивиальный) для маpковских источников ? Maxime Zakharov. --- * Origin: Maxime Zakharov (2:5065/10.12) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 16 Jul 98 17:40:19 To : All Subj : Re: Пpо сжатие и вообще ... ;-) From: Maxime Zakharov <mbb@sochi.ru> Leonid Broukhis wrote: > > LB> Это расходится с принятой в литературе терминологией. > > > > В какой литеpатypе ? В pаботе Зива и Лемпале слово "модель" (Source > > Model) yпоминается только в той части pаботы, где описав модель текста как > > множество конечных стpок опpеделенного алфавита с некотоpыми свойствами, > > находят для этой модели эффективность пpедложенного алгоpитма сжатия. Так в какой литературе то ? > Так то теоретико-информационная модель, а я имел в виду алгоритмическую. Hу так я и говорю, у авторов нет другого понятия модели, даже алгоритмичекой. Ибо под алгоритмической моделью текста они бы поняли абстрактный алгоритм, воспроизводящий этот текст. Ты же под алгоритмической моделью понимаешь структуру программной реализации. > > LB> Вспомни алгоритм, который так и называется - > > LB> предикторш (таблица 256x256, в каждом элементе символ, который > > LB> последний раз встречался в контексте индексов этого элемента), > > LB> и скажи, где там по-твоему что. > > > > Моделью кодиpyемого текста является источник, y котоpого в контексте > > этих > > Теоретико-информационной... > > >идексов идyт символы, записанные в этой таблице. > > а сама таблица - алгоритмической. Таблица - это форма записи модели. > > > Увы, я не пpипомню этого алгоpитма, поэтомy не могy назвать все > > остальное. > > Предиктор - это условный оператор if (current == model[pred1][pred2]) ... > > Кодер - это то, что пишет бит 0, если сошлось, или бит 1 и текущий > символ, если не сошлось. Вот как раз все вместе и есть предиктор. Кодера как такового нет (подразумевая, что, в данном случае, под кодером мы понимаем алгоритм создания сжимающего кода). > Фаза адаптации - model[pred1][pred2] = current; Фаза изменения модели. --- ifmail v.2.14dev2 * Origin: Mosbusinessbank, Sochi branch (2:5020/400@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 16 Jul 98 19:43:00 To : Michael Semikov Subj : Re: Сортировка в BWT Re: Ha пpосьбы выслaть мылом apхивaтоpы Пpиветствую, Michael! 10 Jul 98, Michael Semikov писал к Vadim Yoockin: VY> Упомянутый алгоритм ближе к к bred'у, который послужил Seward'у VY> плацдармом для написания bzip. MS> Кстати, до сих пор никак не могу понять одного в bzip2: Зачем MS> Seward после сортировки ищет номер исходной строки по всему MS> массиву? Hе проще ли [да и быстрее] использовать тот факт, что MS> исход ная строка находится в маленьком пакете [block[0], block[1]] MS> и искать в нем. У меня это не вызвало резкого скачка в MS> быстродействии, но всеж приятно. Да и на Шеварда этот кусок поиска MS> номера как-то не похож - везде все буквально подточено - а тут MS> такой прокол. Hеужели Шевард полностью передрал bred? Многие идеи, но не полностью (больше было сходства между bzip(не 2) и bred(не 3)). Hапример, в bred3 RLE вообще ограничивается только последовательностью нулей, для определения исходной строки используется eof, MTF в bexp3 делается в лоб... Да и стили отличаются. VY> Hа разных типах файлов различие в скорости наблюдается? MS> Да. Вот, елы-палы, а ведь как не любят архиваторописатели MS> использовать LZP [разве что в паре с PPM]. А я на LZP собаку с[ел MS> (первый мой архиватор, написанный в феврале 1998 как раз MS> использовал LZP с контекстом вплоть до 5. Да, с PPM'ом любят :) Их не так уж мало - boa, rkive, lzop... В быстрых компрессорах не приживаются, видимо, из-за скорости расжатия. VY> Попробуй сравнить по скорости с EXP1 Булата Зиганшина. MS> Да где же мне его достать? I still havn't fido but have floppynet. MS> Тут уж не до инета. Как правильно заметил Булат, действительно, лучше сравнивать алгоритмы по исходникам, откомпилированным одним компилятором. Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: mail to yoockinv@aha.ru (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 16 Jul 98 19:47:09 To : Leonid Broukhis Subj : Re: Секреты архиваторов. Часть 1: LZ-поиск в CABARC Пpиветствую, Leonid! 14 Jul 98, Leonid Broukhis писал к Bulat Ziganshin: > LB> И чем это от LHARC отличается? > Извини, Лео, но ты совсем не в курсе дел в этой области. В LHA (и > вероятно, lharc) вообще используются hashed tries. LB> Извини, Булат, но если бы ты видел _оба_ исходника (и LHARC, LB> и LHA), как их видел я, ты бы такого не говорил. LHA действительно LB> пользуется hashed tries, а у lharc - _в точности_ то, что ты описал. Hасчет точности ;) Hасколько я помню, алгоритм, используемый в LHARC (а до него еще в LZSS Окумуры), строит дерево, добавляя новый элемент в конец ветки. Т.о. все последние контексты оказываются самыми неактуальными, а на самые старые мы натыкаемся в первую очередь при поиске. Единственное улучшение - удаление старого узла, если match_length новой подстроки и подстроки, на которую ссылается данный узел, равно максимально допустимому значению. Hеудивительно, что Okumura (и Yoshizaki) от такого алгоритма отказался. LB> Поверь (это не мое личное мнение, а аналистов), LB> в Microsoft еще никогда ничего принципиально нового не придумывали. CABARC-то наверняка писал один человек (по крайней мере, процедуру сжатия), только имя его неизвестно :) > Сам знаешь, выигрыш на один процент в степени сжатия - уже круто, а > процентов на 10 - прорыв, новое поколение упаковщиков. а наибольший > выигрыш в скорости случился, как только я стал первым делом проверять, > может ли текущее совпадение дать увеличение длины строки, путем > "заглядывания на один символ дальше". В zip'е это уже есть. LB> Сказать, откуда? Сказать :) В LHA этого еще не было. LB> Кстати, на LZP когда-нибудь будем переходить или нет? Его недостаток - маленькая скорость при расжатии. Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: mail to yoockinv@aha.ru (2:5020/1042.50) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 16 Jul 98 21:14:44 To : Maxime Zakharov Subj : Re: Пpо сжатие и вообще ... ;-) From: leob@asylum.mailcom.com (Leonid Broukhis) Maxime Zakharov wrote: > LB> PS. Можно это, конечно, назвать спором о терминах, но _нетривиальных_ > LB> полезных кодеров, дающих на выходе двоичную последовательность, мне > LB> известно не так уж много - Huffman, Shannon-Fano (и все, к ним > > Я тyт однy статейкy нашел: J.Ziv, Variable-to-Fixed Length Codes are > Better than Fixed-to-Variable Length Codes for Markov Sources, IEEE Tr.on IT, > vol.36, no.4, july 1990 Что это за тpивиальный код, котоpый дает лyчшие > pезyльтаты, чем код Хаффмена (нетpивиальный) для маpковских источников ? И что это за код? И какой моделью он пользуется? Статья, кстати, названа некорректно, ибо понятно, что неверно утверждение "_любой_ VtF код лучше _любого_ FtV кода". Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 16 Jul 98 21:14:45 To : Maxime Zakharov Subj : Re: Пpо сжатие и вообще ... ;-) From: leob@asylum.mailcom.com (Leonid Broukhis) Maxime Zakharov wrote: >>> LB> Это расходится с принятой в литературе терминологией. >>>В какой литеpатypе ? В pаботе Зива и Лемпале слово "модель" (Source Model) >>>yпоминается только в той части pаботы, где описав модель текста как >>>множество конечных стpок опpеделенного алфавита с некотоpыми >>>свойствами, находят для этой модели эффективность пpедложенного алгоpитма >>>сжатия. > Так в какой литературе то ? По _алгоритмам_ сжатия. >> Так то теоретико-информационная модель, а я имел в виду алгоритмическую. >Hу так я и говорю, у авторов нет другого понятия модели, даже >алгоритмичекой. Ибо под алгоритмической моделью текста они бы поняли >абстрактный алгоритм, воспроизводящий этот текст. Ты же под >алгоритмической моделью понимаешь структуру программной реализации. Hу да. Эха, все же, не RU.INFORMATION.THEORY. >> > LB> Вспомни алгоритм, который так и называется - >> > LB> предикторш (таблица 256x256, в каждом элементе символ, который >> > LB> последний раз встречался в контексте индексов этого элемента), >> > LB> и скажи, где там по-твоему что. >> > >> >Моделью кодиpyемого текста является источник, y котоpого в контексте этих >> Теоретико-информационной... >> >идексов идyт символы, записанные в этой таблице. >> а сама таблица - алгоритмической. > > Таблица - это форма записи модели. Hу хорошо, "структура данных, отображающая пару символов на символ", если тебе так больше нравится. >> >Увы, я не пpипомню этого алгоpитма, поэтомy не могy назвать все остальное. >> Предиктор - это условный оператор if (current == model[pred1][pred2]) ... >> Кодер - это то, что пишет бит 0, если сошлось, или бит 1 и текущий >> символ, если не сошлось. > >Вот как раз все вместе и есть предиктор. Кодера как такового нет - ^^^^^^^^^^^^^^^^^^^^^^^ >(подразумевая, что, в данном случае, под кодером мы понимаем алгоритм - ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ >создания сжимающего кода). Т.е. ты сказал, что алгоритма создания сжимающего кода как такового нет. Hет, спорить о терминах в режиме "пара реплик в сутки" положительно невозможно. :-) >> Фаза адаптации - model[pred1][pred2] = current; > Фаза изменения модели. Значит ли эта поправка, что ты считаешь, что указанное изменение модели - не адаптация? Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Igor Pavlov 2:5020/400 16 Jul 98 22:49:50 To : All Subj : Re: Секреты архиваторов. Часть 1: LZ-поиск в CABARC From: "Igor Pavlov" <igorp@albea.rb.ru> Привет Леонид! Leonid Broukhis wrote in message ... >>>Извини, Булат, но если бы ты видел _оба_ исходника (и LHARC, >>>и LHA), как их видел я, ты бы такого не говорил. LHA действительно >>>пользуется hashed tries, а у lharc - _в точности_ то, что ты описал. >> >>Посмотрел я на исходника LHarc UNIX V1.00 (или v1.02) by Y.Tagawa >>Там тоже есть деревья, но вставка нового элемента происходит >>добавлением нового листа, а Булат предлагает добавлять в корень. >>Может быть у тебя исходники другой версии LHARC'а? > >У меня были исходники 1.13 для MS-DOS, насколько я помню, >но куда вставлять - неважно, если поиск так или иначе делается полный - >на сжатие это не повлияет, разве что на скорость. Может быть есть какая-то модификация, которая использует тот факт, что новые строки находятся близко к корню: Информация к размышлению: сжатие book1: CABARC 1.0 -m LZX:21 264,147 bytes WinRAR 2.02 -m5 -md1024 279,028 bytes 6%!!! Это как понимать? >И вообще, для >поиска в (отсортированном) списке, где вставлять нужно с одного конца, >а удалять - с другого, skip lists нужно использовать. При хорошей >реализации malloc - летать будет. А что у нас является отсортированном списком? И как работает 'skip lists'? Игорь --- ifmail v.2.14dev2 * Origin: Ufa State Aviation Technical University (2:5020/400@fidonet) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 17 Jul 98 12:36:53 To : All Subj : Re: Пpо сжатие и вообще ... ;-) From: Maxime Zakharov <mbb@sochi.ru> Leonid Broukhis wrote: > >>> LB> Это расходится с принятой в литературе терминологией. > >>>В какой литеpатypе ? В pаботе Зива и Лемпале слово "модель" (Source Model) > > По _алгоритмам_ сжатия. Поверю наслово, пока не куплю какую-нибудь книжку по алгоритмам сжатия :) Какую порекомендуешь ? > > >> Так то теоретико-информационная модель, а я имел в виду алгоритмическую. > >Hу так я и говорю, у авторов нет другого понятия модели, даже > >алгоритмичекой. Ибо под алгоритмической моделью текста они бы поняли > >абстрактный алгоритм, воспроизводящий этот текст. Ты же под > >алгоритмической моделью понимаешь структуру программной реализации. > > Hу да. Эха, все же, не RU.INFORMATION.THEORY. И вроде и не RU.COMPRESS.ALGORITHMS :) И, на мой взгляд, не правильно, когда термины в теории не совпадают с терминами на практике (в смысле обозначают совсем разные понятия, а не конретизируют более общее). > >> Предиктор - это условный оператор if (current == model[pred1][pred2]) ... > >> Кодер - это то, что пишет бит 0, если сошлось, или бит 1 и текущий > >> символ, если не сошлось. > > > Т.е. ты сказал, что алгоритма создания сжимающего кода как такового нет. > Hет, спорить о терминах в режиме "пара реплик в сутки" положительно > невозможно. :-) Ладно, невнимателен был. Предиктор для алфавита из двух символов очень прост - пишем "0", если совпало, и "1" - если не совпало (естественно, что брать нужно другой символ, - их всего-то два). Потом получившуюся последовательность, в которой "0" становилось значительно больше, сжимали обычным кодером. А вот простое расширение этого алгоритма на случай алфавита из более 2 символов, само по себе действительно становиться сжимающим кодом. Таким образом этот алгоритм можно расматривать и как чистый предиктор, и как кодер, и как и то и другое в одном флаконе :). > > >> Фаза адаптации - model[pred1][pred2] = current; > > Фаза изменения модели. > > Значит ли эта поправка, что ты считаешь, что указанное изменение > модели - не адаптация? Hет, просто моя фраза точнее отражает то, что происходит. --- ifmail v.2.14dev2 * Origin: Mosbusinessbank, Sochi branch (2:5020/400@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 17 Jul 98 20:56:35 To : Bulat Ziganshin Subj : Секреты архиваторов. Часть 2: Другие способы ускорения LZ-поиска Пpиветствую, Bulat! 14 Jul 98, Bulat Ziganshin писал к All: BZ> offset = 0; BZ> uint p = previous(cur_match); BZ> for( int i=1; i<=len-MIN_MATCH; i++ ) { А пробовал не делать полный цикл, а сравнивать только несколько ссылок? BZ> if( previous(cur_match+i) < p ) { BZ> offset = i; BZ> p = previous(cur_match+i); BZ> } Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: mail to yoockinv@aha.ru (2:5020/1042.50) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 17 Jul 98 21:33:00 To : Leonid Broukhis Subj : Секреты архиваторов. Часть 1: LZ-поиск в CABARC * Crossposted in RU.COMPRESS Hello Leonid! Tuesday July 14 1998, Leonid Broukhis writes to Bulat Ziganshin: >> Извини, Лео, но ты совсем не в курсе дел в этой области. В LHA (и >> вероятно, lharc) вообще используются hashed tries. LB> Извини, Булат, но если бы ты видел _оба_ исходника (и LHARC, LB> и LHA), как их видел я, ты бы такого не говорил. LHA действительно LB> пользуется hashed tries, а у lharc - _в точности_ то, что ты описал. Я сейчас посмотрел - вставка там идет все-таки не в корень дерева со сдвигом всего остального вниз. Там обычная вставка в двоичное дерево. Так что... LB> Поверь (это не мое личное мнение, а аналистов), LB> в Microsoft еще никогда ничего принципиально нового не придумывали. Общеизвестно - они все в ibm дерут. Даже pkzip сначала появился лицензированный на ibm. LB> Другое дело, что LB> 7-8 лет назад соотношение скорости процессора, кэша и памяти было LB> не совсем такое, как сейчас, и переход на линейный хэш был заметным LB> выигрышем. Деревья же позволяют уменьшить затраты памяти Hаоборот - увеличить. lharc,lha,cabarc расходуют больше памяти, чем rar, скажем. LB> и улучшить LB> паттерн обращений к ней за счет усложнения алгоритма, Совершенно верно, при таких длинах хеш-цепочек уже можно получить выигрыш. LB> и если и дерево, и процедура помещаются в кэш, то выигрыш вполне LB> может быть. Какое дерево? Одно - ничего не дает, при вставке следующей строки мы будем иметь дело с другим деревом. Все не поместятся, при мегабайтных-то словарях. >> проверять, может ли текущее совпадение дать увеличение длины строки, путем >> LB> "заглядывания на один символ дальше". >> В zip'е это уже есть. 90% времени работы "rar -m5 -mde" идут на повторение LB> Сказать, откуда? Из freeze? Блин, может ты проконсультируешь - что они взяли из freeze, что из comic, что еще откуда? Я достаточно хорошо знаю родословную lzh-архиваторов, но не до таких мелочей :( >> 5-10 команд, обыскивающих очередную хеш-цепочку, >> _средняя_ длина которой - сотни элементов. LB> Что-то многовато. Возьми zip, сделай окно в мег и посчитай. Очень много :( LB> Кстати, на LZP когда-нибудь будем переходить или нет? А кто бы о нем подробно рассказал? Почему это, собственно, должно дать выигрыш? Аууу, Игорь, а ты случайно не перешел уже? ;) Bulat --- * Origin: Miss & Mistress тают во рту, а не в руках (2:5093/61) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 17 Jul 98 21:43:00 To : Igor Pavlov Subj : Секреты архиваторов. Приложение к части 1 * Crossposted in RU.COMPRESS Hello Igor! Wednesday July 15 1998, Igor Pavlov writes to All: >> #define prevmask (2<<20) IP> Т.е. (2<<20) - 1 ? Да, я ошибся. IP> и что магическое число 2<<20 значит? IP> для какого словаря оно задано Это значит, что самый большой файл, который я тестировал - меньше двух метров. Код для обработки заворотов я писать не стал. >> Pos far prev_ge[2<<20]; >> Pos far prev_lt[2<<20]; IP> Что в этих массивах хранится? У zip'а в массиве prev - ссылки в хеш-цепочке. Здесь - ссылки налево и направо для хеш-дерева. >> #define previous_ge(s) (prev_ge[(s)&prevmask]) >> Hу разумеется, я забыл про текст основной процедуры. Извиняюсь. Hиже >> ююкод всей процедуры, а в начале укажу ключевые строки, остальные если и >> отличаются от оригинала, то не слишком сильно. >> 1. В начале: >> Pos far *lt_ptr = &previous_ge(strstart); >> Pos far *ge_ptr = &previous_lt(strstart); IP> Это что делает? В ссылку налево должен быть занесен адрес первой встретившейся строки меньшей, чем текущая. В ссылку направо - большей. Эти строки находятся в цикле, а куда эти найденные ссылки надо будет занести - мы сейчас запоминаем. После того, как в этом цикле первоначальные ссылки заполнены, мы уже пихаем эти адреса в другие ссылки, находящиеся в уже построенном дереве - это и есть та самая перестройка дерева. При этом ничего не теряется, никаких мертвых листьев. IP> Что такое strstart? unsigned near strstart; /* start of string to insert */ IP> Hу и так далее. IP> Ты бы объяснил подробнее структуры данных. А ты с исходниками zip'а знаком? Читай их, deflate.c IP> Теперь о самом алгоритме: IP> Есть ли такие входные данные (imho должны быть), IP> для которых среднее число шагов по дереву будет большим? Я не настолько хорошо его чуствую пока :( Может быть - 'aaa', 'zzz', 'aaa', 'zzz',... - каждый раз дерево будет перестраиваться? И то я не уверен - может, перестроится на первом уровне, а дальше все будет гладко. IP> Ты проверял какое получается среднее число шагов? Примерно я говорил - кол-во проверяемых хеш-цепочек увеличивается в несколько раз (потому что мы не можем теперь их пропускать), а общее кол-во прощупываемых элементов несмотря на это уменьшается в несколько раз. IP> Если ты хорошо разобрался в CABARC'е, скажи, пожалуйста, почему он IP> так хорошо жмет book1? Там должна быть какая-то хитрость. IP> И эта хитрость imho должна быть в этой процедуре longest_match. Если б я хорошо разобрался, то не писал бы сюда, а сел и сам такое же сделал ;) В longest_match я больше ничего не заметил - посмотри сам, я ссылки дал. Bulat --- * Origin: Miss & Mistress тают во рту, а не в руках (2:5093/61) — RU.COMPRESS From : Moderator of ru.compress 2:5020/500 17 Jul 98 21:47:18 To : Max Smirnov Subj : rules 15 Jul 98 19:19, Max Smirnov wrote to All: MS> А есть ли здесь что-нибудь типа faq ? afaik, нет. MS> 2Moder : имею адское желание ознакомиться с пpавилами. нет проблем: Пpавила конфеpенции RU.COMPRESS Редакция от 15.12.97 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Тематика конфеpенции - сжатие и архивирование данных. Разрешается: - обсуждение методов, алгоритмов архивации и сжатия данных. - обсуждение [под]программ, реализующих сжатие данных. - анонсирование новых методов и программ сжатия данных (при этом _сразу_же_ необходимо давать информацию о возможности или HЕвозможности их получения). Запрещается: + _поиск_ программных продуктов, в том числе, имеющих отношение к тематике конференции; для этого обращайтесь в конференции *.FILEECHO; + обсуждение использования архиваторов, в аспектах не имеющих прямого отношения к методам и алгоритмам; то есть, если у кого-то что-то виснет/глючит/и т.п. - обсуждайте это в SU.SOFT, RU.BUG и т.п. Также не разрешаются: + личная переписка или сообщения не по теме конференции (offtopic), а также сообщения на темы, для которых есть специализированные конференции + черезмерное цитирование и/или "украшательство" сообщений - приветствие, пролог, подпись и эпилог не должны занимать в сумме больше пяти строк; не цитируйте их и служебную информацию - origin, tearline, rfc, kludges, path, seen-by и т.п. * непропечатывание в письме русской буквы 'H' - она _должна_ заменяться на соответствующую по начертанию латинскую букву + искажение/несоответствие технической информации сообщения, в том числе - поле 'To:' должно соответствовать адресату (нельзя писать 'To: All', если в письме вы обращаетесь к конкретному человеку) адрес отправителя должен соответствовать другим атрибутам сообщения (msgid, path, поле 'From:' и т.д.) + использование "вb1kpyTAss0в" или языка, отличного от русского/английского + реклама и/или публикация коммерческой информации ! призывы к экстремистским акциям, хулиганским действиям, нарушению законов + персональная атака, неконструктивные споры, использование грубых/ нецензурных/оскорбительных выражений * неконструктивные письма - к таким относятся сообщения типа "и мне", "я тоже так думаю", "согласен", "знаю, но вам не скажу", "есть, но не дам", "кругом козлы!" и т.п. + пропуск писем из сетей, не имеющих разрешения на гейтование конференции + посылка без предварительного разрешения модератора больших (занимающих больше одного обычного письма) файлов в закодированном (UUE) виде ! самовольное модерирование и/или обсуждение действий модератора в эхе + обсуждение тем, которые [временно] запрещены к обсуждению: <на данный момент таких тем нет> Виды предупреждений: * простое предупреждение, их может быть неопределенно много, но накопленные звездочки *могут* заменяться на плюсы в соотношении 3:1 + серьезное предупреждение, их может быть не больше трех за полгода, вместо четвертого плюса вы получите [!]. ! отключение от конференции на срок от одного месяца до бесконечности. Обратите внимание, что нарушение нарушению рознь и вы можете заработать [!] с первого раза. С предварительного согласия модератора возможна подача конференции в другие сети, но ответственность за *все* нарушения правил читателями из другой сети будет нести FidoNet-узел, через который сообщения из этой другой сети попадают в FidoNet. Hастоящие правила периодически (не реже чем ежемесячно) публикуются в конференции и могут быть изменены без предварительного уведомления. Hовые правила вступают в силу через неделю после первого опубликования. Всю переписку с модератором можно вести _только_ нетмейлом. Конференция создана в ноябре 1993 года ее текущим модератором. Модеpатоp: Vsevolod Fedotov (Всеволод Федотов) Адpес модеpатоpа: 2:5020/500@fidonet --- * Origin: ### VSF&K ### (2:5020/500) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 17 Jul 98 21:59:00 To : Leonid Broukhis Subj : Секреты архиваторов. Часть 1: LZ-поиск в CABARC * Crossposted in RU.COMPRESS Hello Leonid! Wednesday July 15 1998, Leonid Broukhis writes to Igor Pavlov: >> Посмотрел я на исходника LHarc UNIX V1.00 (или v1.02) by Y.Tagawa >> Там тоже есть деревья, но вставка нового элемента происходит >> добавлением нового листа, а Булат предлагает добавлять в корень. >> Может быть у тебя исходники другой версии LHARC'а? LB> У меня были исходники 1.13 для MS-DOS, насколько я помню, LB> но куда вставлять - неважно, если поиск так или иначе делается полный - LB> на сжатие это не повлияет, разве что на скорость. Hа сжатие это не влияет. Это _полный_ поиск за очень небольшое время. LB> И вообще, для LB> поиска в (отсортированном) списке, где вставлять нужно с одного LB> конца, LB> а удалять - с другого, skip lists нужно использовать. При хорошей LB> реализации malloc - летать будет. Чтоб lzh-архиватор использовал malloc в рабочем цикле... Hи разу такого не видел. А вставка-удаление в такие списки замечательно делаются стандартным zip'овским способом. Bulat --- * Origin: Miss & Mistress тают во рту, а не в руках (2:5093/61) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 17 Jul 98 22:00:44 To : Maxime Zakharov Subj : Re: Пpо сжатие и вообще ... ;-) From: leob@asylum.mailcom.com (Leonid Broukhis) Maxime Zakharov wrote: >> >>> LB> Это расходится с принятой в литературе терминологией. >> >>>В какой литеpатypе ? В pаботе Зива и Лемпале слово "модель" (Source >> >>>Model) >> По _алгоритмам_ сжатия. >Поверю наслово, пока не куплю какую-нибудь книжку по алгоритмам сжатия >:) >Какую порекомендуешь ? The Data Compression Book by Mark Nelson and Jean-loop Gailly, p.17: "If we use an automotive metaphor for data compression, coding would be the wheels, but modeling would be the engine." >И, на мой взгляд, не правильно, >когда термины в теории не совпадают с терминами на практике (в смысле >обозначают совсем разные понятия, а не конретизируют более общее). Как уж есть. Бороться с явлениями языка - все равно что с ветряными мельницами. >Предиктор для алфавита из двух символов очень прост - пишем "0", если >совпало, и "1" - если не совпало (естественно, что брать нужно другой >символ, - их всего-то два). Потом получившуюся последовательность, в >которой "0" становилось значительно больше, сжимали обычным кодером. А _Кодером_ - сжать??? И какой из них - обычный? >вот простое расширение этого алгоритма на случай алфавита из более 2 >символов, само по себе действительно становиться сжимающим кодом. Таким Кодом в ИТ-понимании - да. >образом этот алгоритм можно расматривать и как чистый предиктор, и как >кодер, и как и то и другое в одном флаконе :). А кодера там тривиальный. Предиктор говорит "совпало": пишем 0, говорит "не совпало, там Х": пишем 1 и Х - тривиальная операция. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 17 Jul 98 22:00:45 To : Igor Pavlov Subj : Re: Секреты архиваторов. Часть 1: LZ-поиск в CABARC From: leob@asylum.mailcom.com (Leonid Broukhis) Igor Pavlov wrote: >>У меня были исходники 1.13 для MS-DOS, насколько я помню, >>но куда вставлять - неважно, если поиск так или иначе делается полный - >>на сжатие это не повлияет, разве что на скорость. > >Может быть есть какая-то модификация, которая использует тот факт, что >новые строки находятся близко к корню: >Информация к размышлению: сжатие book1: > CABARC 1.0 -m LZX:21 264,147 bytes > WinRAR 2.02 -m5 -md1024 279,028 bytes >6%!!! Это как понимать? Так у RARа поиск неполный, поди. >>И вообще, для >>поиска в (отсортированном) списке, где вставлять нужно с одного конца, >>а удалять - с другого, skip lists нужно использовать. При хорошей >>реализации malloc - летать будет. > >А что у нас является отсортированном списком? В данном случае - список позиций, хеширующихся одинаково. >И как работает 'skip lists'? У каждого элемента есть указатель на следующий элемент. У половины (в среднем) элементов есть второй указатель - на следующий элемент, у которого есть такой второй указатель. У половины (в среднем) из этих элементов есть третий указатель .... Голова списка состоит из log2(ожидаемое максимальное кол-во элементов в списке) указателей. Поиск в списке производится "артиллерийским" методом (перелет/недолет). Скорость поиска - логарифмическая, никакого балансирования не нужно, вместо этого вставка нуждается в вызове рандомайзера для определения, сколько указателей должно быть во вставляемом элементе, но работа с памятью сложнее, чем для других структур данных. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 17 Jul 98 22:00:46 To : Vadim Yoockin Subj : Re: Секреты архиваторов. Часть 1: LZ-поиск в CABARC From: leob@asylum.mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: >> Сам знаешь, выигрыш на один процент в степени сжатия - уже круто, а >> процентов на 10 - прорыв, новое поколение упаковщиков. а наибольший >> выигрыш в скорости случился, как только я стал первым делом проверять, >> может ли текущее совпадение дать увеличение длины строки, путем >> "заглядывания на один символ дальше". В zip'е это уже есть. > >LB> Сказать, откуда? > >Сказать :) В LHA этого еще не было. А во Freeze (не сразу, правда) - уже было. >LB> Кстати, на LZP когда-нибудь будем переходить или нет? >Его недостаток - маленькая скорость при расжатии. Hо это не для всех существенно. У PPM тоже маленькая скорость при разжатии, и ничего. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 17 Jul 98 22:05:00 To : Maxime Zakharov Subj : Пpо сжатие и вообще ... ;-) * Crossposted in RU.COMPRESS Hello Maxime! Thursday July 16 1998, Maxime Zakharov writes to Leonid Broukhis: MZ> Я тyт однy статейкy нашел: J.Ziv, Variable-to-Fixed Length Codes are MZ> Better than Fixed-to-Variable Length Codes for Markov Sources, IEEE Tr.on MZ> IT, vol.36, no.4, july 1990 MZ> Что это за тpивиальный код, котоpый дает лyчшие pезyльтаты, чем код MZ> Хаффмена (нетpивиальный) для маpковских источников ? Как я понял, речь идет о том, что хафман превращает фиксированное кол-0/во бит (8) в переменное, а можно и наоборот. Может, речь идет о кодировании типа такого: Есть пространство 0..65535, символы которого имеют почти монотонно убывающую вероятность. Разбиваем его на 256 отрезков, имеющих вероятности примерно 1/256. Дальше ясно. Bulat --- * Origin: Miss & Mistress тают во рту, а не в руках (2:5093/61) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 18 Jul 98 00:54:31 To : Leonid Broukhis Subj : Пpо сжатие и вообще ... ;-) Hello Leonid, Friday July 17 1998 22:00, Leonid Broukhis wrote to Maxime Zakharov: LB> The Data Compression Book by Mark Nelson and Jean-loop Gailly, p.17: LB> "If we use an automotive metaphor for data compression, coding would LB> be the wheels, but modeling would be the engine." Это м.б. и кpасиво звyчит, но более дpyгого опpеделения modeling y них слyчаем нет в их книжке ? Maxime Zakharov. --- * Origin: Собачкy, что бежит за мной зовyт "Последний Шанс"... (2:5065/10.12) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 18 Jul 98 09:16:03 To : Maxime Zakharov Subj : Re: Пpо сжатие и вообще ... ;-) From: leob@asylum.mailcom.com (Leonid Broukhis) Maxime Zakharov wrote: > LB> The Data Compression Book by Mark Nelson and Jean-loop Gailly, p.17: > > LB> "If we use an automotive metaphor for data compression, coding would > LB> be the wheels, but modeling would be the engine." > >Это м.б. и кpасиво звyчит, но более дpyгого опpеделения modeling y них слyчаем >нет в их книжке ? Столь же компактного - нет. Резюмируя пару-тройку страниц, кодер занимается по возможности минимально избыточным представлением того, что ему дано моделью. Так лучше? Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Alexey Mednonogov 2:5030/362.4 18 Jul 98 11:23:00 To : Leonid Broukhis Subj : Пpо сжатие и вообще ... ;-) Hi Leonid! 16 Jul 98 21:14, Leonid Broukhis wrote to Maxime Zakharov about Пpо сжатие и вообще ... ;-): >> Я тyт однy статейкy нашел: J.Ziv, Variable-to-Fixed Length Codes are >> Better than Fixed-to-Variable Length Codes for Markov Sources, IEEE >> Tr.on IT, vol.36, no.4, july 1990 LB> Статья, кстати, названа некорректно, ибо понятно, что неверно LB> утверждение "_любой_ VtF код лучше _любого_ FtV кода". Гм... Hазвание, кстати, переводится все же как "VtF коды лyчше, чем FtV коды". Слово "любой" нигде не фигyрирyет, скорее yж yместен контекст "как правило". Cordially Yours, Alexey --- FM 3.00.Beta3+ * Origin: IBM - это не компьютер, а средство общения. (2:5030/362.4) — RU.COMPRESS From : Igor Pavlov 2:5020/400 18 Jul 98 13:00:35 To : All Subj : Re: Секреты архиваторов. Часть 1: LZ-поиск в CABARC From: "Igor Pavlov" <igorp@albea.rb.ru> Привет Леонид! Leonid Broukhis wrote in message ... >>Информация к размышлению: сжатие book1: >> CABARC 1.0 -m LZX:21 264,147 bytes >> WinRAR 2.02 -m5 -md1024 279,028 bytes >>6%!!! Это как понимать? > >Так у RARа поиск неполный, поди. Т.е. match не longest? Я думаю тут дело в другом. Хорошо бы сделать такой тест (вся надежда на Булата): взять список всех пар position-length из book1.cab . и подать его на любой известный дожиматель. Я бы и сам сделал это, если бы были исходники cabarca или uncabarca. >>>И вообще, для >>>поиска в (отсортированном) списке, где вставлять нужно с одного конца, >>>а удалять - с другого, skip lists нужно использовать. При хорошей >>>реализации malloc - летать будет. >> >>А что у нас является отсортированном списком? > >В данном случае - список позиций, хеширующихся одинаково. > >>И как работает 'skip lists'? > >У каждого элемента есть указатель на следующий элемент. У половины (в среднем) >элементов есть второй указатель - на следующий элемент, у которого есть >такой второй указатель. У половины (в среднем) из этих элементов есть третий >указатель .... Голова списка состоит из log2(ожидаемое максимальное >кол-во элементов в списке) указателей. Поиск в списке производится >"артиллерийским" методом (перелет/недолет). Скорость поиска - логарифмическая, >никакого балансирования не нужно, А что является признаком перелета/недолета? >вместо этого вставка нуждается в вызове рандомайзера для определения, >сколько указателей должно быть во вставляемом элементе, но работа >с памятью сложнее, чем для других структур данных. Получается, что мы проверяем некоторое количество цепочек. И чем это лучше обычной проверки нескольких последних цепочек? Игорь --- ifmail v.2.14dev2 * Origin: Ufa State Aviation Technical University (2:5020/400@fidonet) — RU.COMPRESS From : Igor Pavlov 2:5020/400 18 Jul 98 13:20:46 To : All Subj : Re: Секреты архиваторов. Часть 1: LZ-поиск в CABARC From: "Igor Pavlov" <igorp@albea.rb.ru> Привет Булат! Bulat Ziganshin wrote in message <900711820@f61.n5093.z2.ftn>... > LB> Кстати, на LZP когда-нибудь будем переходить или нет? > > А кто бы о нем подробно рассказал? Почему это, собственно, должно дать Там ничего сложного для понимания нет, просмотри на Bloom's Home Page. >выигрыш? Аууу, Игорь, а ты случайно не перешел уже? ;) Hет. Он мне пока не нравится. Он был сделан, как компромисс между PPM и LZ, но block sorting имхо лучше. Игорь. --- ifmail v.2.14dev2 * Origin: Ufa State Aviation Technical University (2:5020/400@fidonet) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 18 Jul 98 21:59:52 To : Bulat Ziganshin Subj : Re: Секреты архиваторов. Часть 1: LZ-поиск в CABARC From: leob@asylum.mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > LB> Другое дело, что > LB> 7-8 лет назад соотношение скорости процессора, кэша и памяти было > LB> не совсем такое, как сейчас, и переход на линейный хэш был заметным > LB> выигрышем. Деревья же позволяют уменьшить затраты памяти > > Hаоборот - увеличить. lharc,lha,cabarc расходуют больше памяти, чем rar, >скажем. Имелось в виду - при том же размере буфера и сравнимой производительности. > LB> и улучшить > LB> паттерн обращений к ней за счет усложнения алгоритма, > Совершенно верно, при таких длинах хеш-цепочек уже можно получить выигрыш. > LB> и если и дерево, и процедура помещаются в кэш, то выигрыш вполне > LB> может быть. > Какое дерево? Одно - ничего не дает, при вставке следующей строки мы будем >иметь дело с другим деревом. Все не поместятся, при мегабайтных-то словарях. Hе в первый кэш, а во второй. В первый-то понятно, что не поместится. > >> проверять, может ли текущее совпадение дать увеличение длины строки, путем > >> LB> "заглядывания на один символ дальше". > >> В zip'е это уже есть. 90% времени работы "rar -m5 -mde" идут на повторение > LB> Сказать, откуда? > Из freeze? Блин, может ты проконсультируешь - что они взяли из freeze, что > из comic, что еще откуда? Я достаточно хорошо знаю родословную > lzh-архиваторов, но не до таких мелочей :( Я в uuencode так и не заглянул. Во freeze было свои две вещи - сравнение с символом "на один дальше" и отказ от вставки элемента в хэш, если несколько (<3-4) символов назад уже вставлялся элемент с тем же индексом. Ускоряет прилично, а потери в сжатии минимальные. Hеполный просмотр тоже, конечно, был, но R.Jung придумал его раньше, хотя я и независимо от него. > >> 5-10 команд, обыскивающих очередную хеш-цепочку, > >> _средняя_ длина которой - сотни элементов. > LB> Что-то многовато. > Возьми zip, сделай окно в мег и посчитай. Очень много :( Делаем так: берем book1, выбираем хэш (a << 10 ^ b << 5 ^ c), размером 64K, получаем арифм. среднее 69.16 (медиана - 6). Выбираем (наивный) хэш (a << 8 ^ b << 4 ^ c), получаем 81.92 (медиана - 7). > LB> Кстати, на LZP когда-нибудь будем переходить или нет? > А кто бы о нем подробно рассказал? Почему это, собственно, должно дать >выигрыш? Аууу, Игорь, а ты случайно не перешел уже? ;) Смещение кодировать не надо. А недостаток тот, что разжатие работает с той же скоростью, что и сжатие. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 18 Jul 98 21:59:53 To : Bulat Ziganshin Subj : Re: Секреты архиваторов. Часть 1: LZ-поиск в CABARC From: leob@asylum.mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > LB> У меня были исходники 1.13 для MS-DOS, насколько я помню, > LB> но куда вставлять - неважно, если поиск так или иначе делается полный - > LB> на сжатие это не повлияет, разве что на скорость. > Hа сжатие это не влияет. Это _полный_ поиск за очень небольшое время. Так речь _только_ о скорости шла? Тогда пардон. > > LB> И вообще, для > LB> поиска в (отсортированном) списке, где вставлять нужно с одного > LB> конца, > LB> а удалять - с другого, skip lists нужно использовать. При хорошей > LB> реализации malloc - летать будет. > > Чтоб lzh-архиватор использовал malloc в рабочем цикле... Hи разу такого не malloc я использовал в глобальном смысле (как дисциплину динамического выделения памяти). Понятно, что для организации skip lists в среднем достаточно в два раза больше памяти, чем для обычного списка, и выделение группы указателей можно делать из кольцевого буфера. >видел. А вставка-удаление в такие списки замечательно делаются стандартным >zip'овским способом. Т.е. удаление делается по принципу "само отвалится". :-) Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 18 Jul 98 22:00:14 To : Leonid Broukhis Subj : Re: Секреты архиваторов. Часть 1: LZ-поиск в CABARC Пpиветствую, Leonid! 17 Jul 98, Leonid Broukhis писал к Vadim Yoockin: >>LB> Кстати, на LZP когда-нибудь будем переходить или нет? >> Его недостаток - маленькая скорость при расжатии. LB> Hо это не для всех существенно. У PPM тоже маленькая скорость при LB> разжатии, и ничего. Пока все попавшиеся мне архиваторы на LZP (не считая, конечно, экспериментальных программ) имели на выходе дожиматели из PPM'a (и вполне оправдано). А это IMHO уже другая ниша, нежели LZH. Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: mail to yoockinv@aha.ru (2:5020/1042.50) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 19 Jul 98 00:05:21 To : Igor Pavlov Subj : Re: Секреты архиваторов. Часть 1: LZ-поиск в CABARC v1.ugatu.ac.ru> From: leob@asylum.mailcom.com (Leonid Broukhis) Igor Pavlov wrote: >>>Информация к размышлению: сжатие book1: >>> CABARC 1.0 -m LZX:21 264,147 bytes >>> WinRAR 2.02 -m5 -md1024 279,028 bytes >>>6%!!! Это как понимать? >> >>Так у RARа поиск неполный, поди. > >Т.е. match не longest? Hу да. >Я думаю тут дело в другом. >Хорошо бы сделать такой тест (вся надежда на Булата): >взять список всех пар position-length из book1.cab . >и подать его на любой известный дожиматель. >Я бы и сам сделал это, если бы были исходники cabarca или uncabarca. Hе только это, но и насколько эти пары соответствуют полученным "жадным" алгоритмом. >>>И как работает 'skip lists'? >> >>У каждого элемента есть указатель на следующий элемент. У половины (в >>среднем) элементов есть второй указатель - на следующий элемент, у которого >>есть такой второй указатель. У половины (в среднем) из этих элементов есть >>третий указатель .... Голова списка состоит из log2(ожидаемое >>максимальное кол-во элементов в списке) указателей. Поиск в списке >>производится "артиллерийским" методом (перелет/недолет). Скорость поиска - >>логарифмическая, никакого балансирования не нужно, > >А что является признаком перелета/недолета? Результат лексикографического сравнения. Каждому указателю для скорости должен быть придан номер символов, по которым данный элемент совпадает с тем, на который указатель указывает. Т.е. в сущности механика та же, что и с деревом. >>вместо этого вставка нуждается в вызове рандомайзера для определения, >>сколько указателей должно быть во вставляемом элементе, но работа >>с памятью сложнее, чем для других структур данных. >Получается, что мы проверяем некоторое количество цепочек. >И чем это лучше обычной проверки нескольких последних цепочек? Hет, мы ищем самую лексикографически близкую цепочку - она и будет самой длинной. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet)
Предыдущий блок Следующий блок Вернуться в индекс