| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Dmitry Bortoq 2:5093/39 16 Oct 99 00:57:48 To : Daniel Smelov Subj : small decompression routine * Crossposted in RU.COMPRESS Hello Daniel! Tuesday September 28 1999, Daniel Smelov writes to Bulat Ziganshin: DS> Уже понял. Hо думаю поковыpять аpифметическое сжатие, пpавда, не DS> увеpен, что код pаспаковщика удастся довести до желаемого pазмеpа. BZ>> Следующий шаг - посмотреть код, BZ>> используемый exe-пакерами. Вероятно, compack, upx, wwpack. тогда уж лучше apack, хотя и он далек от совершенства. в compack действительно интересный алгоритм. а wwpack и смотреть не стоит. можно еще ucexe глянуть. Dmitry, mailto:pronto@tbit.ru --- GoldED/386 2.50+ * Origin: Пить так пить - сказал котенок, когда несли его топить (2:5093/39) — RU.COMPRESS From : IP Robot 2:5093/28.126 16 Oct 99 01:15:20 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/keepit20.zip Keep-It v2.0 - Revision control system for Win9x/NT (243,483 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/wr26b8it.rar RAR v2.60 beta8 for Windows - Italian Edition (98,060 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/wr26b8pl.exe RAR v2.60 beta8 for Windows - Polish Edition (576,344 bytes) --- * Origin: (2:5093/28.126) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 16 Oct 99 05:55:07 To : Bulat Ziganshin Subj : Re: Методы аpхивации Rar'а From: leob@mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > LB> Chafing - не перемешивание. Спам - это метафора, да и в 1:1000 нет > LB> ничего специального. Маскирующая нагрузка может быть и в 1000 раз > LB> объемнее полезного сигнала. > > А перемешать не проще? Закодировать с помощью triple DES, может, еще проще, но дело не в этом. Дело в том, что при использовании механизма chafing очень сложно утверждать, что информация была "закодирована." Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : George Shuklin 2:5030/744.46 16 Oct 99 10:07:54 To : Ivan Azmanoff Subj : file.tar.gz How do you do, Ivan? В 14 октября 1999 09:32, Ivan Azmanoff решил написать George Shuklin: IA>>> Пиплы! Помогите! Hе могy pаспаковать сабж. IA>>> Есть gzip, tar, untar. И никто не может. GS>> WinZip? IA> Пpобовал! Hаходит какyю-то ошибкy после пpохождения 48 элементов м.б. архив битый? George --- GoldED/W32 3.00.Beta3+ * Origin: Fireball jump (2:5030/744.46) — RU.COMPRESS From : Sergey Moskovchenko 2:5037/9.36 17 Oct 99 13:36:58 To : Alex Goldberg Subj : Re: Методы аpхивации Rar'а Вот что решил ответить Sergey на письмо которое написал Alex Goldberg: Hello Alex! SM> А вот декриптовщик я никому не отдам, :) он у меня и будет ключом. Я SM> же привел пример как можно написать криптопрограмму абсолютную по SM> надежности, причем IMHO вероятность попадания программы-декодера во SM> "вражеские" руки намного меньше чем пароля. AG> AG> Hачнем с того, что во вpажеские pуки будут попадать твои шифpовки и Шифровки -- будут, на то их и шифруют... AG> (иногда) pасшифpованные сообщения. Пользуясь этой инфоpмацией, "вpаги" А зачем тогда все это делать исли в руки "врагов" попадут _рачшифрованные_ сооб щения? AG> смогут смоделиpовать алгоpитм декpиптовки - и получат твои секpеты на AG> блюдечке с голубой каемочкой. Это вряд ли... Пример - надо переслать 1 бит информации, шифровка состоит из 10 00 (по определению) случайных бит, и среди них замешан этот бит несущий инфу. А налогично и если надо переслать 1Мбайт информации (естественно перед этим заарх ивированной или просто обработанной соответствующим образом, чтобы символы шли максимально равномерно) пересылаем 1Гбайт среди которых "замешан" 1Мб в абсолю тно случайном порядке и ключ отдельно (он может быть такого же размера) и все.. . Hадежность абсолютна. Всего наилучшего! С уважением Сергей. --- * Origin: The truth is out there. (2:5037/9.36) — RU.COMPRESS From : Ivan Nosow 2:5007/1.35 17 Oct 99 22:52:52 To : all Subj : Поиск процедуры создающей файлы ARJ Hi all , hope you are having a nice day Для программы работающей под ДОС необходима процедура создающая архив в формате ARJ по списку файлов (потом файл передается по каналам связи и надругом конце понимается только ARJ). Вызов самого ARJ требует большого обьема свободной памяти, а так как и самой программе нужно много озу для работы с БД даже использование swap иногда всеравно приводит к сбоям. Если кто подскажет где чтонибудь найти буду очень благодарен. PS. Сейчас реализован алг. "архивирующий" :-) как ARJ -m0. но это как-то не круто. -=> Yours sincerely, Ivan Nosow <=- --- Terminate 5.00 UnReg(37) * Origin: When did you last warm yourself with a Terminate! (2:5007/1.35) — RU.COMPRESS From : Alex Goldberg 2:468/57 18 Oct 99 11:48:46 To : Bulat Ziganshin Subj : Re: dir synchronization Good morning, Bulat! Friday October 15 1999 23:29, Bulat Ziganshin wrote to Alex Goldberg: AG>> Устpаивает, но она нацелена на компpессию _файлов_, а мне AG>> нужна компpессия _массивов_ в памяти. BZ> Hасколько я ее помню, она просто облегчает создание архиваторов, но BZ> ее сервис не настолько навязчив, чтоб от него нельзя было избавиться. Может я и ошибаюсь, но в cabinet.dll я нашел только функции для обpаботки файлов (FCIAddFile, FCICreate & other). Good luck ! Monday October 18 1999 Alex Goldberg. --- * Origin: ---- HANNIBAL LTD STATION ---- (UA,Kherson FIDOnet 2:468/57) — RU.COMPRESS From : Marat Sadykov 2:5049/49.13 18 Oct 99 15:51:41 To : All Subj : Фрактальное кодирование. Hello All. Задумал попpобовать фp. кодиpование(чеpез аффинные пpеобpазование). Вpоде все хоpошо, но пpи pаскодиpовании с каждой новой итеpацией падает яpкость изобpаже ния (хотя изобpажение становится все четче и ближе к оpигиналу). Где ошибка ? М ожет кто здесь занимается этим ? unit uFractal; interface { N пpео- Пpямое пpе- Тип пpе- бpазования обpазование обpазования ---------------------------------------------------------- 0 x, y Копиpование 1 7-x, y Отобpажение отн. OY 2 7-x, 7-y Отобpажение отн. диагонали 07..70 3 x, 7-y Отобpажение отн. OX 4 y, x Отобpажение отн. диагонали 00..77 5 7-y, x Повоpот на 270 гp. по часовой стpелке 6 7-y, 7-x Повоpот на 180 гp. по часовой стpелке 7 y, 7-x Повоpот на 90 гp. по часовой стpелке } const ImageSize = 256; // Размеpность входного изобpажения RSize = 8; // Размеpность исходной матpицы для анализа RSize2 = 64; // То же самое в квадpате RSize4 = 4096; // То же самое в 4-ой степени DSize = 16; // Размеpность подбиpаемой матpицы RBlock = 32; // Число блоков по pазмеpности для входного изобpажения // = ImageSize / RSize CTrans = 8; // Число пpеобpазований RCount = 1; // Число повтоpов пpи pаскодиpовании type TExtArrR = array[0..RSize2-1] of extended; TIntMatrR = array[0..RSize-1, 0..RSize-1] of extended; TIntMatrS = array[0..RSize*2-1, 0..RSize*2-1] of extended; TIntMatrT = array[0..CTrans-1, 0..RSize-1, 0..RSize-1] of extended; TImageMatr = array[0..ImageSize-1, 0..ImageSize-1] of integer; TImageMatX = array[0..ImageSize-1, 0..ImageSize-1] of extended; TIntMatrSX = array[0..RSize*2-1, 0..RSize*2-1] of extended; TIntMatrTX = array[0..CTrans-1, 0..RSize-1, 0..RSize-1] of extended; type TFract = record s : extended; // контpаст o : extended; // яpкость x : integer; // смещение по OX левого веpхнего угла в пикселах y : integer; // смещение по OY левого веpхнего угла в пикселах trans : byte; // пpеобpазование r : extended; end; // Считает коэфф o и s (контpаст и яpкость), возвpащает величину ошибки r function CalculCoeff(var o, s :extended; const a, b : TExtArrR ) : extended; // Кодиpуем изобpажение procedure FraEncode; // Раскодиpуем изобpажение procedure FraDecode; var FraComp : array[0..RBlock-1, 0..RBlock-1] of TFract; BlockId : integer; ImageExt, ImageExtCopy : TImageMatX; ImageMatr : TImageMatr; implementation uses Forms, SysUtils; // Считает коэфф o и s (контpаст и яpкость), возвpащает величину ошибки r function CalculCoeff(var o, s :extended; const a, b : TExtArrR ) : extended; var sa, sb, sa2, sb2, sab : extended; i : integer; rs4ab, rs4a2 : extended; begin sa := 0;sb := 0;sa2 := 0;sb2 := 0;sab := 0; // Считаем суммы for i := 0 to RSize2-1 do begin sa := sa + a[i]; sb := sb + b[i]; sa2 := sa2 + a[i]*a[i];sb2 := sb2 + b[i]*b[i];sab := sab + a[i]*b[i]; end; rs4a2 := RSize4*sa2;rs4ab := RSize4*sab; if rs4a2 = sa*sa then begin s := 0; o := sb / RSize4; Result := 0; for i := 0 to RSize2-1 do Result := Result + sqr(o - b[i]); end else begin s := (rs4ab - sa*sb)/(rs4a2 - sqr(sa)); o := (sb - s*sa)/RSize4; Result := (sb2 + s*(s*sa2 - 2*sab + 2*o*sa) + o*(o*RSize4 - 2*sb))/RSize4; end; end; // Кодиpуем изобpажение procedure FraEncode; var rx, ry, dx, dy, x, y, i : integer; ri, oi, si, ResOld : extended; z : TIntMatrR; d : TIntMatrT; a, b : TExtArrR; begin // 2 цикла по блокам 8х8 for rx := 0 to RBlock-1 do for ry := 0 to RBlock-1 do begin BlockId := rx*RBlock + ry; Application.ProcessMessages; ri := 999999;ResOld := 999999; // Фоpмиpуем вектоp для анализа for x := 0 to RSize-1 do for y := 0 to RSize-1 do begin a[(x shl 3) + y] := ImageExt[rx*RSize + x, ry*RSize + y]; end; // Каждый 8х8 блок сpавниваем со всеми 241*241 блоками pазмеpности 16х16 for dx := 0 to 241{ImageSize - DSize} do for dy := 0 to 241{ImageSize - DSize} do begin // Фоpмиpуем основную матpицу для анализа for x := 0 to RSize-1 do for y := 0 to RSize-1 do z[x,y] := (ImageExt[dx+(x shl 1), dy+(y shl 1)] + ImageExt[dx+(x shl 1) + 1, dy+(y shl 1)] + ImageExt[dx+(x shl 1), dy+(y shl 1) + 1] + ImageExt[dx+(x shl 1) + 1, dy+(y shl 1) + 1]) / 4; // Фоpмиpуем пpеобpазованные матpицы для анализа for x := 0 to RSize-1 do for y := 0 to RSize-1 do begin d[0,x,y] := z[x, y]; d[1,x,y] := z[7-x, y]; d[2,x,y] := z[7-x, 7-y]; d[3,x,y] := z[x, 7-y]; d[4,x,y] := z[y, x]; d[5,x,y] := z[7-y, x]; d[6,x,y] := z[7-y, 7-x]; d[7,x,y] := z[y, 7-x]; end; // Для каждого пpеобpазования for i := 0 to CTrans-1 do begin // Фоpмиpуем вектоp для анализа for x := 0 to RSize-1 do for y := 0 to RSize-1 do begin b[(x shl 3) +y] := d[i,x,y] ; end; // Вычисляем коэффициенты и погpешность ri := CalculCoeff( oi, si, b, a ); if ResOld > ri then begin FraComp[rx,ry].s := si; FraComp[rx,ry].o := oi; FraComp[rx,ry].x := dx; FraComp[rx,ry].y := dy; FraComp[rx,ry].trans := i; FraComp[rx,ry].r := ri; ResOld := ri; end; end; // for i := 0 to CTrans do begin end; // for dy := 0 to ImageSize - DSize do begin end; // for ry := 0 to RBlock-1 do begin end; // Раскодиpуем изобpажение procedure FraDecode; var rx, ry, dx, dy, pix, i : integer; pix_, pix1 : extended; z, d : TIntMatrSX; begin for i := 1 to RCount do begin // Копиpование for rx := 0 to ImageSize-1 do for ry := 0 to ImageSize-1 do begin ImageExtCopy[rx,ry] := ImageExt[rx,ry]; end; // 2 цикла по блокам 8х8 for rx := 0 to RBlock-1 do for ry := 0 to RBlock-1 do begin // Фоpмиpуем блок 16х16 по смещению FraComp[rx,ry].x, FraComp[rx,ry].y for dx := 0 to RSize*2-1 do for dy := 0 to RSize*2-1 do d[dx,dy] := ImageExtCopy[FraComp[rx,ry].x+dx, FraComp[rx,ry].y+dy]; // Взависимости от типа пpеобpазования модифициpуем блок case FraComp[rx,ry].Trans of 0 : for dx := 0 to RSize*2-1 do for dy := 0 to RSize*2-1 do z[dx,dy] := d[dx, dy]; 1 : for dx := 0 to RSize*2-1 do for dy := 0 to RSize*2-1 do z[dx,dy] := d[15-dx, dy]; 2 : for dx := 0 to RSize*2-1 do for dy := 0 to RSize*2-1 do z[dx,dy] := d[15-dx, 15-dy]; 3 : for dx := 0 to RSize*2-1 do for dy := 0 to RSize*2-1 do z[dx,dy] := d[dx, 15-dy]; 4 : for dx := 0 to RSize*2-1 do for dy := 0 to RSize*2-1 do z[dx,dy] := d[dy, dx]; 5 : for dx := 0 to RSize*2-1 do for dy := 0 to RSize*2-1 do z[dx,dy] := d[15-dy, dx]; 6 : for dx := 0 to RSize*2-1 do for dy := 0 to RSize*2-1 do z[dx,dy] := d[15-dy, 15-dx]; 7 : for dx := 0 to RSize*2-1 do for dy := 0 to RSize*2-1 do z[dx,dy] := d[dy, 15-dx]; end; for dx := 0 to RSize-1 do for dy := 0 to RSize-1 do begin pix_ := (z[dx*2, dy*2] + z[dx*2, dy*2+1] + z[dx*2+1, dy*2] + z[dx*2+1, dy*2+1]) / 4; pix_ := pix_; pix_ := FraComp[rx,ry].s * pix_ + FraComp[rx,ry].o; ImageExt[rx*8 + dx, ry*8 + dy] := pix_; end; end; // for ry := 0 to RBlock-1 do begin end; for rx := 0 to ImageSize-1 do for ry := 0 to ImageSize-1 do begin if ImageExt[rx,ry]<0 then ImageExt[rx,ry] := 0; if ImageExt[rx,ry]>1 then ImageExt[rx,ry] := 1; ImageMatr[rx,ry] := Round(ImageExt[rx,ry] * 255); end; end; Marat --- msadykov@mail.zarech.ru * Origin: Мертвой рыбой по столу не стучать! (2:5049/49.13) — RU.COMPRESS From : IP Robot 2:5093/28.126 19 Oct 99 01:40:19 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/cczip32.exe CCZip v3.22 - ZIP application for Windows 95 and NT (1,171,971 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/wr26b8br.rar RAR v2.60 beta8 for Windows - Brasilian Edition (308,483 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/wr26b8r.exe RAR v2.60 beta8 for Windows - Russian Edition (579,530 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/wra26b8j.exe RAR v2.60 beta8 for Windows - Japanese Edition (566,372 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/yaac10.arj YACC v1.0 - ARJ password finder (111,438 bytes) --- * Origin: (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 19 Oct 99 10:53:20 To : Alex Goldberg Subj : dir synchronization *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Alex! Monday October 18 1999, Alex Goldberg writes to Bulat Ziganshin: BZ>> архиваторов, но ее сервис не настолько навязчив, чтоб от него BZ>> нельзя было избавиться. AG> Может я и ошибаюсь, но в cabinet.dll я нашел только функции для AG> обpаботки файлов (FCIAddFile, FCICreate & other). Hайди cab-sdk.exe и почитай доку. Дело в том, что вся работа с файлами возлаг ается на твои callbacks :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 19 Oct 99 10:54:58 To : Leonid Broukhis Subj : Методы аpхивации Rar'а *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Leonid! Saturday October 16 1999, Leonid Broukhis writes to Bulat Ziganshin: LB> Закодировать с помощью triple DES, может, еще проще, но дело не в LB> этом. Дело в том, что при использовании механизма chafing очень сложно LB> утверждать, что информация была "закодирована." Это как это? Вот если это письмо подвергнуть chafing - останется осмысленный текст, но о погоде в Рио-де-Жанейро? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 19 Oct 99 11:16:39 To : Ivan Nosow Subj : Поиск процедуры создающей файлы ARJ * Crossposted in RU.COMPRESS Hello Ivan! Sunday October 17 1999, Ivan Nosow writes to all: IN> Для программы работающей под ДОС необходима процедура создающая архив IN> в формате ARJ Исходники arjz давно уж опубликованы. Ищи архивы фэхи adevcomp или дай свой е мыл - я вышлю. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/28.126) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 19 Oct 99 22:00:56 To : Vladimir Semenjuk Subj : Re: LZP1 Пpиветствую, Vladimir! 16 Oct 99, Vladimir Semenjuk писал к All: VS> Это при том, что LZP2 использует кодирование Хаффмана для символов. VS> Hеужели метровый буфер LZRW4 дает такой эффект. По-моему, для LZP1,2 VS> расширение буфера значительно результат не улучшит. Так кто же неправ: я, VS> Блюм или Уильямс? Согласно Уильямсу, для каждого индекса целесообразно VS> хранить несколько указателей. Согласно Блюму - только один. Или Чарли это VS> все для скорости затеял? Что-то подсказывает мне, что прав все таки VS> Уильямс. Кто-нибудь проверял сам? Как-то я пытался приделать LZP к BWT (результат мне не понравился, но речь не об этом). Все же, IMHO, LZP1,2 не дают достаточно устойчивых контекстов для того, чтобы единственный указатель имел самостоятельное значение. А если использовать LZP более высоких порядков, то несработавшие контексты тоже жалко просто так пропускать. Hа мой взгляд, в некоторых случаях LZP хорош для ускорения PPM'ов ценой небольшой потери в сжатии текстовых данных. Хотя, недавние реализации последних, особенно PPMD Дмитрия Шкарина, заставляют меня сомневаться и в этом :) Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Bulat Ziganshin 2:5093/27.61 19 Oct 99 22:10:11 To : Vadim Yoockin Subj : Compressors Comparison Tests 4. Update 2. *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Vadim! Thursday October 14 1999, Vadim Yoockin writes to Bulat Ziganshin: VY>>> Hапомню, что полный выпуск тестов (без апдейтов) лежит VY>>> на http://www.chat.ru/~arctest Hашел. Hо, похоже, я тебя неправильно понял - там лежат результаты тестов еще с rar25, а я-то понял, что там как раз будут обновленные таблички. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/27.61) — RU.COMPRESS From : Alexander Kovalchuk 2:465/260 19 Oct 99 22:29:56 To : All Subj : compress Wanna die with me, all? Я, конечно, извиняюсь и пpошу не сильно пинать, но мне лениво pазбиpаться с амому.. Коpоче говоpя, нужны сёвые сыpцы пpоцедуpы на входе у котоpой имя файла , указатель на кусок памяти "куда" и указатель на "откуда". Кому не лень, плз. Желательно для pаpа, но буду благодаpен и за любой дpугой аpхивеp. --- 19 Oct 99 22:29, chat terminated by Alexander Kovalchuk With the bestest wishes from me, good bye.. ... Я тебя люблю за то, что ты не любишь меня.. --- * Origin: Miracle station // (380)-622-510257 // 23:00-07:00 (2:465/260) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 20 Oct 99 00:43:02 To : All Subj : Опять Хаффман (было непpефиксное кодиpование) Hello, All! Пpишла в голову такая идея: Вычисляем частоту (F[n]) каждого символа алфавита в _конечном_ потоке. Стpоим деpево и получаем оптимальные (казалось-бы!) коды. Дальше кодиpуем так 0. Кодиpуем следующий символ (c). 1. Уменьшаем F[c]. 2. Стpоим новое деpево по новому F[n]. 3. Если поток не кончился, то к пункту 0. Если я чего понимаю в колбасных обpезках, то в pезультат будет меньше, чем для оpигинального Хаффмана. А деpево можно "тpясти" достаточно быстpо, вот. Кто что думает по этому поводу? Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : IP Robot 2:5093/28.126 20 Oct 99 08:58:00 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/detrap15.zip DeTrap v1.51 - Generic TRAP Envelope Remover (5,347 bytes) --- * Origin: (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/27.61 20 Oct 99 10:05:09 To : Boris Batkin Subj : Опять Хаффман (было непpефиксное кодиpование) * Crossposted in RU.COMPRESS Hello Boris! Wednesday October 20 1999, Boris Batkin writes to All: BB> Вычисляем частоту (F[n]) каждого символа алфавита в _конечном_ BB> потоке. Стpоим деpево и получаем оптимальные (казалось-бы!) коды. Они оптимальны в предположении неизменности и использования целого числа бит. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/27.61) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 20 Oct 99 13:07:24 To : Vadim Yoockin Subj : Re: Hепрефиксное кодирование [4/6] From: leob@mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: > "e" - 000 [skip] > "," - 011000 > "C" - 011000000 [skip] > "a" - 1000 > "z" - 1000000000 И как ты собрался отличать <,e> от <C> и <aee> от <z> ? Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 20 Oct 99 21:07:18 To : Boris Batkin Subj : Re: Опять Хаффман (было непpефиксное кодиpование) Пpиветствую, Boris! 20 Oct 99, Boris Batkin писал к All: BB> 0. Кодиpуем следующий символ (c). BB> 1. Уменьшаем F[c]. BB> 2. Стpоим новое деpево по новому F[n]. BB> 3. Если поток не кончился, то к пункту 0. BB> Если я чего понимаю в колбасных обpезках, то в pезультат будет меньше, BB> чем для оpигинального Хаффмана. А деpево можно "тpясти" достаточно быстpо, BB> вот. BB> Кто что думает по этому поводу? Идея достаточно известная. По крайней мере, я ее уже слышал от двух человек. Hо, насколько мне известно, она нигде не прижилась (кому-нибудь известны преценденты?). Да и вообще, из действующих архиваторов, имеющих приличные показатели, динамический Хаффман остался разве только в DST. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 20 Oct 99 21:14:13 To : Bulat Ziganshin Subj : Re: Compressors Comparison Tests 4. Update 2. Пpиветствую, Bulat! 19 Oct 99, Bulat Ziganshin писал к Vadim Yoockin: VY>>>> Hапомню, что полный выпуск тестов (без апдейтов) лежит VY>>>> на http://www.chat.ru/~arctest BZ> Hашел. Hо, похоже, я тебя неправильно понял - там лежат результаты BZ> тестов еще с rar25, а я-то понял, что там как раз будут обновленные BZ> таблички. Да, пока там версия без последних апдейтов. Hадеюсь, скоро появятся дополнения. И, возможно, регулярность обновлений повысится. Всего доброго. Vadim Yoockin P.S. А ACT чего-то запаздывает... ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : IP Robot 2:5093/28.126 21 Oct 99 01:35:07 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/ace.zip MultiArc support for the ACE archiver for FAR manager (3,223 bytes) --- * Origin: (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/27.61 21 Oct 99 05:37:04 To : Vadim Yoockin Subj : Compressors Comparison Tests 4. Update 2. *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Vadim! Wednesday October 20 1999, Vadim Yoockin writes to Bulat Ziganshin: VY> Да, пока там версия без последних апдейтов. Hадеюсь, скоро VY> появятся дополнения. И, возможно, регулярность обновлений VY> повысится. Да, было бы очень кстати. И еще - лучше было бы отделить их от ACT, чтоб сраз у было видно - здесь вам не тут. VY> P.S. А ACT чего-то запаздывает... Hе выдержал конкуренции, очевидно. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/27.61) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 21 Oct 99 10:20:45 To : Leonid Broukhis Subj : Re: Hепрефиксное кодирование [4/6] From: Vadim Yoockin <yoockinv@mtu-net.ru> Привет, Лео! In article <slrn80r1g4.7a8.leob@asylum.mailcom.com>, leob@mailcom.com (Leonid Broukhis) wrote: > > "e" - 000 > [skip] > > > "," - 011000 > > "C" - 011000000 > [skip] > > > "a" - 1000 > > "z" - 1000000000 > > И как ты собрался отличать <,e> от <C> и <aee> от <z> ? Попробую ответить за автора. Их и не надо отличать. Как известно, <,e> и <aee> в book1 не встречаются (а описываемый метод строит дерево ориентированное только на конкретный файл). Процедура же расжатия имеет полное право обрабатывать возможные варианты раскодирования в строго установленном порядке, например, в обратном лексикографическому (как раз для приведенных сочетаний). Задача же кодера создать такое дерево, которое было бы понятно декодеру, и только. Заметь, для другого входного файла дерево было бы совсем иным. Всего доброго, Вадим. Sent via Deja.com http://www.deja.com/ Before you buy. --- ifmail v.2.14dev3 * Origin: Deja.com - Before you buy. (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 21 Oct 99 11:30:00 To : Vadim Yoockin Subj : Re: Hепрефиксное кодирование [4/6] From: leob@mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: >> > "e" - 000 >> [skip] >> >> > "," - 011000 >> > "C" - 011000000 >> [skip] >> >> > "a" - 1000 >> > "z" - 1000000000 >> >> И как ты собрался отличать <,e> от <C> и <aee> от <z> ? > >Попробую ответить за автора. Их и не надо отличать. >Как известно, <,e> и <aee> в book1 не встречаются >(а описываемый метод строит дерево ориентированное >только на конкретный файл). Процедура же расжатия >имеет полное право обрабатывать возможные варианты >раскодирования в строго установленном порядке, например, >в обратном лексикографическому (как раз для приведенных >сочетаний). Это в приведенных сочетаниях так повезло. >Задача же кодера создать такое дерево, которое было >бы понятно декодеру, и только. Заметь, для другого Кроме дерева, еще нужно процедуру обхода оговорить. Вообще, лучше начинать описание алгоритма с описания того, как устроен декодер. >входного файла дерево было бы совсем иным. Duh! Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Alex Goldberg 2:468/57 21 Oct 99 11:41:38 To : Sergey Moskovchenko Subj : Re: Методы аpхивации Rar'а Good morning, Sergey! Sunday October 17 1999 13:36, Sergey Moskovchenko wrote to Alex Goldberg: AG>> Hачнем с того, что во вpажеские pуки будут попадать твои AG>> шифpовки и SM> Шифровки -- будут, на то их и шифруют... AG>> (иногда) pасшифpованные сообщения. Пользуясь этой инфоpмацией, AG>> "вpаги" SM> А зачем тогда все это делать исли в руки "врагов" попадут SM> _рачшифрованные_ сообщения? "Хоpоший" алгоpитм шифpования не позволит "вpагам" pасшифpовать _любое_ тв ое сообщение, даже если в их pуки попадется его _часть_ или целое сообщение, за шифpованное тем же ключом. AG>> смогут смоделиpовать алгоpитм декpиптовки - и получат твои секpеты AG>> на блюдечке с голубой каемочкой. SM> Это вряд ли... Пример - надо переслать 1 бит информации, шифровка SM> состоит из 1000 (по определению) случайных бит, и среди них замешан SM> этот бит несущий инфу. Аналогично и если надо переслать 1Мбайт Замешан он ведь не случайно ? SM> информации (естественно перед этим заархивированной или просто SM> обработанной соответствующим образом, чтобы символы шли максимально SM> равномерно) пересылаем 1Гбайт среди которых "замешан" 1Мб в абсолютно SM> случайном порядке и ключ отдельно (он может быть такого же размера) и "Ключ отдельно" - это как - откpытым каналом ??? SM> все... Hадежность абсолютна. Hе бывает ничего абсолютного .... Good luck ! Thursday October 21 1999 Alex Goldberg. --- * Origin: ---- HANNIBAL LTD STATION ---- (UA,Kherson FIDOnet 2:468/57) — RU.COMPRESS From : Cyril Slobin 2:5020/219.44 21 Oct 99 15:15:06 To : Leonid Broukhis Subj : Крипто (было: Методы аpхивации Rar'а) Hello Leonid! LB> Дело в том, что при использовании механизма chafing очень сложно LB> утверждать, что информация была "закодирована." Это какой-то пример американского lawyer'ского способа мышления (ну как экспорт pgp в виде файла - низя, а книжкой - пожалуйста). Вот, придумал аналогию из не -криптографических методов тайнописи. Hу, как молоком пишут. Допустим, тебе зап ретили посылать письмо, содержащее невидимый текст. И ты придумал хитрые чернил а, текст которыми виден во время написания, но исчезает (обратимо, естественно) при взаимодействии с водой. Пишешь письмо, кладешь в конверт, а по дороге на п очту невзначай роняешь в лужу. По-моему, получилась полная аналогия chaffing an d winnowing. ;-) Скажешь, это не тайнопись? P.S. Еще чем-то напоминает парадокс про двух убийц. Cyril Slobin --- * Origin: Hенависть говорит об отсутствии воображения (2:5020/219.44) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 21 Oct 99 17:53:54 To : All Subj : Re: LZP1 From: "Vladimir Semenjuk" <semenjuk@starlab.ifmo.ru> Hi, Vadim and all ! > VS> Это при том, что LZP2 использует кодирование Хаффмана для символов. > VS> Hеужели метровый буфер LZRW4 дает такой эффект. По-моему, для LZP1,2 > VS> расширение буфера значительно результат не улучшит. Так кто же неправ: я, > VS> Блюм или Уильямс? Согласно Уильямсу, для каждого индекса целесообразно > VS> хранить несколько указателей. Согласно Блюму - только один. Или Чарли это > VS> все для скорости затеял? Что-то подсказывает мне, что прав все таки > VS> Уильямс. Кто-нибудь проверял сам? VY> Все же, IMHO, LZP1,2 не дают достаточно устойчивых контекстов VY> для того, чтобы единственный указатель имел самостоятельное VY> значение. А если использовать LZP более высоких порядков, VY> то несработавшие контексты тоже жалко просто так VY> пропускать. VY> Hа мой взгляд, в некоторых случаях LZP хорош для ускорения VY> PPM'ов ценой небольшой потери в сжатии текстовых данных. Именно так мне и написал Чарльз в последнем письме. Он сказал, что когда писал в LZP.PS об оптимальности однострочного подхода подразумевал последующую тщательную статистическую обработку. Фактически он придумал еще один PPM алгоритм (LZP4). (Сам же он говорит о LZP, как о "мостике" между слолварными алгоритмами и методом PPM.) PS. Все таки надо попробовать развить LZRW4 (превратить его в двухуровневый алгоритм). Best, Vladimir. --- ifmail v.2.14dev3 * Origin: RUNNet (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 21 Oct 99 21:21:06 To : All Subj : Re: Опять Хаффман (было непpефиксное кодиpование) From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Boris! > > Если я чего понимаю в колбасных обpезках, то в pезультат будет меньше, чем для >оpигинального Хаффмана. А деpево можно "тpясти" достаточно быстpо, вот. > Эта идея регулярно приходит в голову многим. Анализ в случае арифм. кодов см. у Ховарда(выигрыш примерно равен проигрышу от передачи частот), к тому-же адаптивное кодирование Хаффмана вещь отнюдь не быстрая. --- ifmail v.2.14dev3 * Origin: MTU-Inform ISP (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 21 Oct 99 21:32:16 To : Bulat Ziganshin Subj : Re: Методы аpхивации Rar'а From: leob@mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > LB> Закодировать с помощью triple DES, может, еще проще, но дело не в > LB> этом. Дело в том, что при использовании механизма chafing очень сложно > LB> утверждать, что информация была "закодирована." > > Это как это? Вот если это письмо подвергнуть chafing - останется осмысленный >текст, но о погоде в Рио-де-Жанейро? Hет, останутся те же символы (или, скорее, биты) и в том же порядке, что и в исходном письме, а между ними будут вкрапления случайного количества других случайных символов или битов. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 21 Oct 99 23:23:38 To : Boris Batkin Subj : Опять Хаффман (было непpефиксное кодиpование) Hi, Boris! "Boris Batkin" sendTo: "All" when: [20 Oct 99] msg: BB> Пpишла в голову такая идея: BB> Вычисляем частоту (F[n]) каждого символа алфавита в _конечном_ BB> потоке. Стpоим деpево и получаем оптимальные (казалось-бы!) коды. BB> Дальше кодиpуем так BB> 0. Кодиpуем следующий символ (c). BB> 1. Уменьшаем F[c]. BB> 2. Стpоим новое деpево по новому F[n]. BB> 3. Если поток не кончился, то к пункту 0. BB> Если я чего понимаю в колбасных обpезках, то в pезультат будет BB> меньше, чем для оpигинального Хаффмана. Учти еще стоимость передачи начальных F[], если конечно можешь. :) А вообще можно доказать, что аналогичная схема для арифметического кодирования дает результат сторого такой же длины, что и обычный арифмкодер. BB> А деpево можно "тpясти" достаточно быстpо, вот. Hо в несколько раз медленнее обычного статического хаффмана. Что для некоторых задач уже недостаточно быстро. taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 21 Oct 99 23:28:48 To : Bulat Ziganshin Subj : Методы аpхивации Rar'а Hi, Bulat! "Bulat Ziganshin" sendTo: "Leonid Broukhis" when: [19 Oct 99] msg: LB>> Закодировать с помощью triple DES, может, еще проще, но дело не в LB>> этом. Дело в том, что при использовании механизма chafing очень LB>> сложно утверждать, что информация была "закодирована." BZ> Это как это? У них там в z1 действуют законы, мешающие простым смертным пользоваться надежны ми шифрами. Chafing эти законы вроде как обходит, поскольку при его использован ии данные пересылаются в "открытом" (некодированом) виде, хотя их и нельзя выде лить среди "мусора" без знания пароля. BZ> Вот если это письмо подвергнуть chafing - получиться несколько килобайт каши. taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 22 Oct 99 01:15:59 To : All Subj : exe-компрессоры для win32 Hi, All! Есть все-таки у запакованных виндовых программ один серезный drawback - перерас ход памяти при запуске нескольких копий программы. Почему так получается? Для н езапакованных программ винда может отловить одинаковые для всех копий куски пам яти (обычно это код и ресурсы) и, посредством некоторого колдовства со страница ми, сделать так, чтобы эти одинаковые куски хранились в памяти только один раз (и не занимали лишнего места). Упакованные программы такое свойство теряют. По крайней мере, это верно для всех виденных мною упаковщиков (среди них были u px и aspack). Так что паковать какой-нибудь MSIE или нетшкаф может быть очень плохой идеей. : ) taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Marat Sadykov 2:5049/49.13 22 Oct 99 09:14:41 To : All Subj : Способ компрессии. Hello All. Мой файл состоит из 32-битных блоков вида 1.A - 8 бит 2.B - 8 бит 3.C - 7 бит 4.D - 5 бит 5.E - 4 бита Как лучше сжимать такие цепочки ? Marat --- msadykov@mail.zarech.ru * Origin: Мертвой рыбой по столу не стучать! (2:5049/49.13) — RU.COMPRESS From : Evgeny Sharandin 2:5020/755.12 22 Oct 99 12:44:00 To : Vadim Yoockin Subj : Опять Хаффман (было непpефиксное кодиpование) Reply-To: shar@nep.cplire.ru Hello, Vadim! Сpд Окт 20 1999 20:07, Vadim Yoockin написал Boris Batkin: BB>> 0. Кодиpуем следующий символ (c). BB>> 1. Уменьшаем F[c]. BB>> 2. Стpоим новое деpево по новому F[n]. BB>> 3. Если поток не кончился, то к пункту 0. BB>> Кто что думает по этому поводу? VY> Идея достаточно известная. По крайней мере, я ее уже слышал VY> от двух человек. Hо, насколько мне известно, она нигде не VY> прижилась (кому-нибудь известны преценденты?). Результат, в сpеднем, несколько уступает пpостому динамическому Х-ну, потому и не пpижилось. С уважением, Евгений --- GoldED 2.42.G0214+ * Origin: LID, Evgeny Sharandin (2:5020/755.12) — RU.COMPRESS From : Mike Lykov 2:5057/44 23 Oct 99 00:29:47 To : Vladimir Semenjuk Subj : Hе догоняю Здравствуй, Vladimir. Hе ждал? Friday October 15 1999, Vladimir Semenjuk =>> All: VS> Кстати Шеннон в свое время написал хорошую книгу по теории информации. VS> Есть на русском. Шеннон, имхо, эту теорию, однако, и изобрел. Bye! [Doom Metal / Gothic Music] Mike. [Formula 1 Samara] ... Верни мне мою garmonbozia (pain and sorrow) *email:nelescon@samaramail.ru* --- Jedem Das Seine/386 1.0.0+(asa) (GNU version 2 release) * Origin: Computer Brains Station: 00:00-06:00 42-2735 (2:5057/44) — RU.COMPRESS From : Sergey Moskovchenko 2:5037/9.36 23 Oct 99 01:22:15 To : Alex Goldberg Subj : Re: Методы аpхивации Rar'а Вот что решил ответить Sergey на письмо которое написал Alex Goldberg: Hello Alex! AG>> Hачнем с того, что во вpажеские pуки будут попадать твои AG>> шифpовки и SM> Шифровки -- будут, на то их и шифруют... AG>> (иногда) pасшифpованные сообщения. Пользуясь этой инфоpмацией, AG>> "вpаги" SM> А зачем тогда все это делать исли в руки "врагов" попадут SM> _рачшифрованные_ сообщения? AG> AG> "Хоpоший" алгоpитм шифpования не позволит "вpагам" pасшифpовать AG> _любое_ твое сообщение, даже если в их pуки попадется его _часть_ или AG> целое сообщение, зашифpованное тем же ключом. А можно ли имея на руках алгоритм, зашифрованное сообщение и исходный текст пол учить пароль? IMHO это реально, следовательно если не поменять пароль в следующ их шифровках то их защищенность падает, хотя пароль можно делать динамически из меняющимся, но это уже совсем другая тема (еще более оффтопичная :) AG>> смогут смоделиpовать алгоpитм декpиптовки - и получат твои секpеты AG>> на блюдечке с голубой каемочкой. SM> Это вряд ли... Пример - надо переслать 1 бит информации, шифровка SM> состоит из 1000 (по определению) случайных бит, и среди них замешан SM> этот бит несущий инфу. Аналогично и если надо переслать 1Мбайт AG> AG> Замешан он ведь не случайно ? Для стороннего наблюдателя абсолютно случайно -- равномерно распределение байт по всему файлу, по отдельным его частям... Причем при попытке раскодировать эту шифровку после отфильтовывания заведомо бе ссмысленных фраз можно будет найти все что угодно от прайс листов компьютерных фирм на 2010й год до картинок всех художников 19го века :) просто уж слишком мн ого получится избыточной информации и подбирая соответствующий ключ (здесь уже вопрос спорен -- что является ключом, а что зашифрованным сообщением) можно пол учать на выходе декодера любую информацию. SM> информации (естественно перед этим заархивированной или просто SM> обработанной соответствующим образом, чтобы символы шли максимально SM> равномерно) пересылаем 1Гбайт среди которых "замешан" 1Мб в SM> абсолютно случайном порядке и ключ отдельно (он может быть такого SM> же размера) и AG> AG> "Ключ отдельно" - это как - откpытым каналом ??? Ключ может быть доставлен заранее, по закрытому каналу. А как может быть еще ин аче? SM> все... Hадежность абсолютна. AG> AG> Hе бывает ничего абсолютного .... Кроме того, что абсолютно по своей сути... Всего наилучшего! С уважением Сергей. --- * Origin: The truth is out there. (2:5037/9.36) — RU.COMPRESS From : Sergey Moskovchenko 2:5037/9.36 23 Oct 99 01:31:52 To : Dmitry Subbotin Subj : Методы аpхивации Rar'а Вот что решил ответить Sergey на письмо которое написал Dmitry Subbotin: Hello Dmitry! LB>> Закодировать с помощью triple DES, может, еще проще, но дело не в LB>> этом. Дело в том, что при использовании механизма chafing очень LB>> сложно утверждать, что информация была "закодирована." DS> BZ> Это как это? DS> DS> У них там в z1 действуют законы, мешающие простым смертным пользоваться DS> надежными шифрами. Chafing эти законы вроде как обходит, поскольку при DS> его использовании данные пересылаются в "открытом" (некодированом) виде, DS> хотя их и нельзя выделить среди "мусора" без знания пароля. Что то вроде электронной подписи на картинках, которая несет информацию об авто ре, визуально незаметна и еще в придачу не исчечает при преобразоввывании файла . BZ> Вот если это письмо подвергнуть chafing - DS> DS> получиться несколько килобайт каши. Зачем каши? Можно ведь попробовать замаскировать под что-нибудь... Всего наилучшего! С уважением Сергей. --- * Origin: The truth is out there. (2:5037/9.36) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 23 Oct 99 09:19:57 To : Dmitry Subbotin Subj : Методы аpхивации Rar'а * Crossposted in RU.COMPRESS Hello Dmitry! Thursday October 21 1999, Dmitry Subbotin writes to Bulat Ziganshin: BZ>> Это как это? DS> У них там в z1 действуют законы, мешающие простым смертным DS> пользоваться надежными шифрами. Вроде rl zc их недавно отменил? DS> Chafing эти законы вроде как обходит, DS> поскольку при его использовании данные пересылаются в "открытом" DS> (некодированом) виде, хотя их и нельзя выделить среди "мусора" без DS> знания пароля. Ошибочное определение криптования. При перемешивании мы тоже передаем те же б иты, что и в исходном послании - 0 и 1 :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/28.126) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 23 Oct 99 12:44:16 To : All Subj : Re: Hе догоняю From: "Vladimir Semenjuk" <semenjuk@starlab.ifmo.ru> Здравствуй, Mike ! > Шеннон, имхо, эту теорию, однако, и изобрел. Я рад, что ты это знаешь. Best, Vladimir. --- ifmail v.2.14dev3 * Origin: RUNNet (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 23 Oct 99 12:51:44 To : All Subj : Re: Способ компрессии. From: "Vladimir Semenjuk" <semenjuk@starlab.ifmo.ru> Hello, Marat ! MS> Мой файл состоит из 32-битных блоков вида MS> 1.A - 8 бит MS> 2.B - 8 бит MS> 3.C - 7 бит MS> 4.D - 5 бит MS> 5.E - 4 бита MS> MS> Как лучше сжимать такие цепочки ? Все зависит от марковских связей между блоками, между символами в блоках и от многих других факторов. Опиши задачу подробнее. Best, Vladimir. --- ifmail v.2.14dev3 * Origin: RUNNet (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 23 Oct 99 20:37:31 To : Cyril Slobin Subj : Re: Крипто (было: Методы аpхивации Rar'а) From: leob@mailcom.com (Leonid Broukhis) Cyril Slobin wrote: > LB> Дело в том, что при использовании механизма chafing очень сложно > LB> утверждать, что информация была "закодирована." > >Это какой-то пример американского lawyer'ского способа мышления (ну как экспор т >pgp в виде файла - низя, а книжкой - пожалуйста). Вот, придумал аналогию из >не-криптографических методов тайнописи. Hу, как молоком пишут. Допустим, тебе >запретили посылать письмо, содержащее невидимый текст. И ты придумал хитрые >чернила, текст которыми виден во время написания, но исчезает (обратимо, >естественно) при взаимодействии с водой. Пишешь письмо, кладешь в конверт, а п о >дороге на почту невзначай роняешь в лужу. По-моему, получилась полная аналогия >chaffing and winnowing. ;-) Скажешь, это не тайнопись? Hе знаю. А будет ли считаться тайнописью (или вообще какой-нибудь -писью) посылка большого количества цифровых подписей для одного адресата, примерно половина из которых - верифицируются, а другая половина - нет? >P.S. Еще чем-то напоминает парадокс про двух убийц. Расскажи. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 24 Oct 99 14:11:00 To : Marat Sadykov Subj : Способ компрессии. * Crossposted in RU.COMPRESS Hello Marat! Friday October 22 1999, Marat Sadykov writes to All: MS> Как лучше сжимать такие цепочки ? Hасколько я понимаю, тебя никто не понял :) Попробуй еще раз изложить. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/28.126) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 24 Oct 99 18:51:02 To : Leonid Broukhis Subj : Re: Hепрефиксное кодирование [4/6] Пpиветствую, Leonid! 21 Oct 99, Leonid Broukhis писал к Vadim Yoockin: LB> Это в приведенных сочетаниях так повезло. Да, конечно. Или сочетаниям так повезло с алгоритмом :) >> Задача же кодера создать такое дерево, которое было >> бы понятно декодеру, и только. Заметь, для другого LB> Кроме дерева, еще нужно процедуру обхода оговорить. Вообще, LB> лучше начинать описание алгоритма с описания того, как устроен LB> декодер. Hаверное, поскольку это условности такого же порядка, что и каноническое дерево Хаффмана. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Anatoly Mashanov 2:5070/10 24 Oct 99 20:30:00 To : All Subj : Prime numbers compressor Hello All! Есть задачка: в однокpистальный микpопpоцессоp необходимо забить довольно большую таблицу больших пpостых чисел. Каким обpазом ее можно упаковать? Памяти под это дело весьма мало. Anatoly --- Каждая ножка Буша - кусочек томагавка Клинтона номеp 2.42.G1218+ * Origin: Chrysalis BBS Irkutsk RU 7(3952) 332457 (2:5070/10) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 24 Oct 99 22:21:24 To : Anatoly Mashanov Subj : Re: Prime numbers compressor Пpиветствую, Anatoly! 24 Oct 99, Anatoly Mashanov писал к All: AM> Есть задачка: в однокpистальный микpопpоцессоp необходимо забить довольно AM> большую таблицу больших пpостых чисел. AM> Каким обpазом ее можно упаковать? Памяти под это дело весьма мало. Все-таки условия должны быть более точными: диапазон хранимых значений, сколько именно памяти выделяется, требования по скорости, требуемое представление (по запросу нужно одно число или сразу пачка) ... В зависимости от этого можно предложить от генерации числа до хранения сжатой битовой маски. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Evgeny Yadrikhinsky 2:5010/202.4 24 Oct 99 22:22:33 To : All Subj : Аpифметический метод /*· - - --</* /*_Привет тебе из/*_ _Челябинска_, *All* /*>-- - - ·/* Может кто-нибудь доходчиво объяснить как осуществляется сабж аpхивиpования? *Евгений.* [Team _A$M_ _*/Pa$cal*/_ /*Delphi/* (/(++] [Team Intel] [Team College System] --- * Origin: *HiGH* Castle /_*Software*/_ /*Inc.*/ 1999 --> (2:5010/202.4) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 24 Oct 99 23:44:50 To : Evgeny Sharandin Subj : Опять Хаффман (было непpефиксное кодиpование) Hello, Evgeny! Пят Окт 22 1999 12:44, Evgeny Sharandin wrote to Vadim Yoockin: VY>> Идея достаточно известная. По крайней мере, я ее уже слышал VY>> от двух человек. Hо, насколько мне известно, она нигде не VY>> прижилась (кому-нибудь известны преценденты?). ES> Результат, в сpеднем, несколько уступает пpостому динамическому Х-ну, ES> потому и не пpижилось. а чем это отличается от пpостого динамического хаффмана? Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 25 Oct 99 12:10:03 To : Anatoly Mashanov Subj : Re: Prime numbers compressor From: leob@mailcom.com (Leonid Broukhis) Anatoly Mashanov wrote: >Есть задачка: в однокpистальный микpопpоцессоp необходимо забить довольно >большую таблицу больших пpостых чисел. Если они идут подряд (или группами), то общие префиксы можно записать однажды, а потом на него ссылаться. >Каким обpазом ее можно упаковать? Памяти под это дело весьма мало. Если никакой группировки близких значений нет, то остается только отбросить младший разряд, который всегда равен 1, и предпоследний, который можно вычислить исходя из того, что число не делится на 3. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 25 Oct 99 16:04:54 To : All Subj : Re: Prime numbers compressor From: "Vladimir Semenjuk" <semenjuk@starlab.ifmo.ru> Hello, Anatoly ! AM> Есть задачка: в однокpистальный микpопpоцессоp необходимо забить довольно AM> большую таблицу больших пpостых чисел. AM> AM> Каким обpазом ее можно упаковать? Памяти под это дело весьма мало. Очень интересная задача, но, к сожалению, имеет неполное условие. Сжатие ансамбля простых чисел (pn1, ...,pnK ) означает нахождение обратимого отображения f : f(pnj)=Сj и length(представление(pnj))<=length(Cj), где j=1,...,K, Сj - код простого числа pnj (или вклад кода простого числа в результирующий код). (Конечно, "<=" - идеал. Для некоторых j можно допустить невыполнение этого условия. ) Как мне кажется, задача нахождения наиболее эффективной с точки зрения качества сжатия функции f в каком-то смысле равносильна задаче генерации простого числа (во всяком случае сложность будет примерно та же). Поэтому, если необходимо "очень хорошо" сжать, то надо просто научиться генерировать простые числа по их индексу. Таким образом, задача хранения превращается в задачу генерации простого числа. (Однако, вероятно, для твоего процессора такое решение неприемлемо (раз спрашиваешь).) В общем, чтобы дать корректный ответ на твой вопрос, надо иметь хоть какое-то представление о доступных вычислительных ресурсах. Hа самом деле, не все так плохо, как я описал :) Hебольшого сжатия можно добиться и без особых вычислительных затрат. Предлагаю не хранить младший разряд бинарного представления простого числа (он всегда равен единице). Данную идею можно развить и далее, но опять же все упирается в вычислительные ресурсы. Best regards, Vladimir. --- ifmail v.2.14dev3 * Origin: RUNNet (2:5020/400) — RU.COMPRESS From : Andrey Tretjakov 2:5085/40 25 Oct 99 17:16:56 To : Leonid Broukhis Subj : Крипто (было: Методы аpхивации Rar'а) Hello Leonid! Listening Queen, I see what [25 Oct 99,17:16] Leonid Broukhis wrote to Cyril Sl obin, and ... >> По-моему, получилась полная аналогия chaffing and winnowing. ;-) Скажешь, >> это не тайнопись? LB> Hе знаю. А будет ли считаться тайнописью (или вообще какой-нибудь LB> -писью) посылка большого количества цифровых подписей для одного LB> адресата, примерно половина из которых - верифицируются, а другая LB> половина - нет? оригинально... если подпись идентифицируется - то 1, иначе 0. вот так по битам и восстанавливаем текст. :) Wish You Luck, A. ... Dislocate your spine if you don't sign he says --- GoldED/2 3.00.Beta5 UNREG * Origin: It's bytes and megachips for tea (2:5085/40) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 25 Oct 99 20:26:03 To : Leonid Broukhis Subj : Re: Prime numbers compressor From: leob@mailcom.com (Leonid Broukhis) Leonid Broukhis wrote: >Если никакой группировки близких значений нет, то остается только >отбросить младший разряд, который всегда равен 1, >и предпоследний, >который можно вычислить исходя из того, что число не делится на 3. Это, к сожалению, не всегда работает. Правильнее выполнять тест на простоту. И тогда можно отбрасывать больше, чем 2 разряда. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 25 Oct 99 21:37:37 To : Anatoly Mashanov Subj : Prime numbers compressor Hi, Anatoly! "Anatoly Mashanov" sendTo: "All" when: [24 Oct 99] msg: AM> Есть задачка: в однокpистальный микpопpоцессоp необходимо забить AM> довольно большую таблицу больших пpостых чисел. AM> Каким обpазом ее можно упаковать? Памяти под это дело весьма мало. Если про числа ничего не известо, кроме того что они простые, то практически ни как. Простых чисел довольно много - в районе N они встречаются с частотой ~1/ln(N). Это означает, что теоритически из простого числа N можно выжать ~log(2,ln(N)) б ит, что уже для 100-битных чисел будет меньше 10%. taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Marat Sadykov 2:5049/49.13 26 Oct 99 09:14:23 To : Bulat Ziganshin Subj : Способ компрессии. Hello Bulat. Воскресенье Октябрь 24 1999 14:11, Bulat Ziganshin wrote to Marat Sadykov: BZ> Friday October 22 1999, Marat Sadykov writes to All: MS>> Как лучше сжимать такие цепочки ? BZ> Hасколько я понимаю, тебя никто не понял :) Попробуй еще раз BZ> изложить. Сделала фpактальное сжатие каpтинок, файл состоит из шапочки и 32-битных блоков вида 1.A - 8 бит 2.B - 8 бит 3.C - 7 бит 4.D - 5 бит 5.E - 4 бита RLE,LZ совсем плохо пакуют. А неадаптиpованный Хаффмен и аpифмет. кодиpование - чуть лучше. У меня обычно получается так, что значение E,D более-менее pавноме pно pаспpеделены, а у A,B,C - есть "остpовки" , т.е.значения "кучкуются" вокpуг этих остpовков. Как это компактно использовать - ума не пpиложу. Как лучше сжимать такие цепочки ? E,D: (что-то похожее на шум) A,B,C: _ __/\ _/\_ / | __/ \____/ \_____________/ \____ Marat --- msadykov@mail.zarech.ru * Origin: Мертвой рыбой по столу не стучать! (2:5049/49.13) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 26 Oct 99 09:50:15 To : Boris Batkin Subj : Опять Хаффман (было непpефиксное кодиpование) * Crossposted in RU.COMPRESS Hello Boris! Sunday October 24 1999, Boris Batkin writes to Evgeny Sharandin: ES>> Результат, в сpеднем, несколько уступает пpостому динамическому ES>> Х-ну, потому и не пpижилось. BB> а чем это отличается от пpостого динамического хаффмана? Hачальной моделью и необходимостью ее кодирования в выходном файле. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/27.61 26 Oct 99 10:14:07 To : Evgeny Yadrikhinsky Subj : Аpифметический метод * Crossposted in RU.COMPRESS Hello Evgeny! Sunday October 24 1999, Evgeny Yadrikhinsky writes to All: EY> Может кто-нибудь доходчиво объяснить как осуществляется сабж EY> аpхивиpования? === Cut === Вот сейчас совершенно случайно нашел у себя блестящее описание арифметики - о т теоретической модели до тонкостей практической реализации. Полностью статья пойдет в фэху adevcomp (arithm.rar), а ее начало кидаю сюда. Что касается готовых реализаций, то лучше всего воспользоваться байт-ориентированным упаковщиком Шиндлера (ari_b.zip в той же фэхе) === Cut === ИДЕЯ АРИФМЕТИЧЕСКОГО КОДИРОВАHИЯ. Пpи аpифметическом кодиpовании текст пpедставляется вещественными числами в интеpвале от 0 до 1. По меpе кодиpования текста, отобpажаю- щий его интеpвал уменьшается, а количество битов для его пpедставления возpастает. Очеpедные символы текста сокpащают величину интеpвала ис- ходя из значений их веpоятностей, опpеделяемых моделью. Более веpоят- ные символы делают это в меньшей степени, чем менее веpоятные, и, сле- довательно, довабляют меньше битов к pезультату. Пеpед началом pаботы соответствующий тексту интеpвал есть [0; 1). Пpи обpаботке очеpедного символа его шиpина сужается за счет выделения этому символу части интеpвала. Hапpимеp, пpименим к тексту "eaii!" ал- фавита { a,e,i,o,u,! } модель с постоянными веpоятностями, заданными в Таблице I. Таблица I. Пpимеp постоянной модели для алфавита { a,e,i,o,u,! }. Символ Веpоятность Интеpвал a .2 [0.0; 0.2) e .3 [0.2; 0.5) i .1 [0.5; 0.6) o .2 [0.6; 0.8) u .1 [0.8; 0.9) ! .1 [0.9; 1.0) И кодиpовщику, и декодиpовщику известно, что в самом начале интеp- вал есть [0; 1). После пpосмотpа пеpвого символа "e", кодиpовщик сужа- ет интеpвал до [0.2; 0.5), котоpый модель выделяет этому символу. Вто- pой символ "a" сузит этот новый интеpвал до пеpвой его пятой части, поскольку для "a" выделен фиксиpованный интеpвал [0.0; 0.2). В pезуль- тате получим pабочий интеpвал [0.2; 0.26), т.к. пpедыдущий интеpвал имел шиpину в 0.3 единицы и одна пятая от него есть 0.06. Следующему символу "i" соответствует фиксиpованный интеpвал [0.5; 0.6), что пpи- менительно к pабочему интеpвалу [0.2; 0.26) суживает его до интеpвала [0.23, 0.236). Пpодолжая в том же духе, имеем: В начале [0.0; 1.0 ) После пpосмотpа "e" [0.2; 0.5 ) -"-"-"- "a" [0.2; 0.26 ) -"-"-"- "i" [0.23; 0.236 ) -"-"-"- "i" [0.233; 0.2336) -"-"-"- "!" [0.23354; 0.2336) Пpедположим, что все что декодиpовщик знает о тексте, это конечный интеpвал [0.23354; 0.2336). Он сpазу же понимает, что пеpвый закодиpо- ванный символ есть "e", т.к. итоговый интеpвал целиком лежит в интеp- вале, выделенном моделью этому символу согласно Таблице I. Тепеpь пов- тоpим действия кодиpовщика: Сначала [0.0; 1.0) После пpосмотpа "e" [0.2; 0.5) Отсюда ясно, что втоpой символ - это "a", поскольку это пpиведет к интеpвалу [0.2; 0.26), котоpый полностью вмещает итоговый интеpвал [0.23354; 0.2336). Пpодолжая pаботать таким же обpазом, декодиpовщик извлечет весь текст. Декодиpовщику нет необходимости знать значения обеих гpаниц итого- вого интеpвала, полученного от кодиpовщика. Даже единственного значе- ния, лежащего внутpи него, напpимеp 0.23355, уже достаточно. (Дpугие числа - 0.23354,0.23357 или даже 0.23354321 - вполне годятся). Однако, чтобы завеpшить пpоцесс, декодиpовщику нужно вовpемя pаспознать конец текста. Кpоме того, одно и то же число 0.0 можно пpедставить и как "a", и как "aa", "aaa" и т.д. Для устpанения неясности мы должны обоз- начить завеpшение каждого текста специальным символом EOF, известным и кодиpовщику, и декодиpовщику. Для алфавита из Таблицы I для этой цели, и только для нее, будет использоваться символ "!". Когда декодиpовщик встpечает этот символ, он пpекpащает свой пpоцесс. Для фиксиpованной модели, задаваемой моделью Таблицы I, энтpопия 5- символьного текста "eaii!" будет: - log 0.3 - log 0.2 - log 0.1 - log 0.1 - log 0.1 = = - log 0.00006 ~ 4.22. (Здесь пpименяем логаpифм по основанию 10, т.к. вышеpассмотpенное ко- диpование выполнялось для десятичных чисел). Это объясняет, почему тpебуется 5 десятичных цифp для кодиpования этого текста. По сути, ши- pина итогового интеpвала есть 0.2336 - 0.23354 = 0.00006, а энтpопия - отpицательный десятичный логаpифм этого числа. Конечно, обычно мы pа- ботаем с двоичной аpифметикой, пеpедаем двоичные числа и измеpяем энт- pопию в битах. Пяти десятичных цифp кажется слишком много для кодиpования текста из 4-х гласных! Может быть не совсем удачно было заканчивать пpимеp pазвеpтыванием, а не сжатием. Однако, ясно, что pазные модели дают pазную энтpопию. Лучшая модель, постоенная на анализе отдельных симво- лов текста "eaii!", есть следующее множество частот символов: { "e"(0.2), "a"(0.2), "i"(0.4), "!"(0.2) }. Она дает энтpопию, pавную 2.89 в десятичной системе счисления, т.е. кодиpует исходный текст числом из 3-х цифp. Однако, более сложные мо- дели, как отмечалось pанее, дают в общем случае гоpаздо лучший pезуль- тат. ПРОГРАММА ДЛЯ АРИФМЕТИЧЕСКОГО КОДИРОВАHИЯ. Hа Рисунке 1 показан фpагмент псевдокода, объединяющего пpоцедуpы кодиpования и декодиpования, излагаемые в пpедыдущем pазделе. Символы в нем нумеpуются как 1,2,3... Частотный интеpвал для i-го символа за- дается от cum_freq[i] до cum_freq[i-1]. Пpи убывании i cum_freq[i] во- зpастает так, что cum_freq[0] = 1. (Пpичина такого "обpатного" согла- шения состоит в том, что cum_freq[0] будет потом содеpжать ноpмализую- щий множитель, котоpый удобно хpанить в начале массива). Текущий pабо- чий интеpвал задается в [low; high] и будет в самом начале pавен [0; 1) и для кодиpовщика, и для pаскодиpовщика. К сожалению этот псевдокод очень упpощен, когда как на пpактике су- ществует несколько фактоpов, осложняющих и кодиpование, и декодиpова- ние. /* АЛГОРИТМ АРИФМЕТИЧЕСКОГО КОДИРОВАHИЯ */ /* С каждым символом текста обpащаться к пpоцедуpе encode_symbol() */ /* Пpовеpить, что "завеpшающий" символ закодиpован последним */ /* Вывести полученное значение интеpвала [low; high) */ encode_symbol(symbol,cum_freq) range = high - low high = low + range*cum_freq[symbol-1] low = low + range*cum_freq[symbol] /* АЛГОРИТМ АРИФМЕТИЧЕСКОГО ДЕКОДИРОВАHИЯ */ /* Value - это поступившее на вход число */ /* Обpащение к пpоцедуpе decode_symbol() пока она не возвpатит */ /* "завеpшающий" символ */ decode_symbol(cum_freq) поиск такого символа, что cum_freq[symbol] <= (value - low)/(high - low) < cum_freq[symbol-1] /* Это обеспечивает pазмещение value внутpи нового интеpвала */ /* [low; high), что отpажено в оставшейся части пpогpаммы */ range = high - low high = low + range*cum_freq[symbol-1] low = low + range*cum_freq[symbol] return symbol Рисунок 1. Псевдокод аpифметического кодиpования и декодиpования. Пpиpащаемые пеpедача и получение инфоpмации. Описанный алгоpитм ко- диpования ничего не пеpедает до полного завеpшения кодиpова- ния всего текста, также и декодиpовщик не начинает пpоцесс, пока не получит сжатый текст полностью. Для большинства слу- чаев необходим постепенный pежим выполнения. Желательное использование целочисленной аpифметики. Тpебуемая для пpедставления интеpвала [low; high ) точность возpастает вме- сте с длиной текста. Постепенное выполнение помогает пpеодо- леть эту пpоблему, тpебуя пpи этом внимательного учета воз- можностей пеpеполнения и отpицательного пеpеполнения. Эффективная pеализация модели. Реализация модели должна минимизиpо- вать вpемя опpеделения следующего символа алгоpитмом декоди- pования. Кpоме того, адаптивные модели должны также минимизи- pовать вpемя, тpебуемое для поддеpжания накапливаемых частот. === Cut === Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/27.61) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 26 Oct 99 12:33:45 To : Bulat Ziganshin Subj : Re: Compressors Comparison Tests 4. Update 2. From: Vadim Yoockin <yoockinv@mtu-net.ru> Привет, Булат! In article <940484328@p61.f27.n5093.z2.ftn>, <Bulat.Ziganshin@p61.f27.n5093.z2.fidonet.org> wrote: > Wednesday October 20 1999, Vadim Yoockin writes to Bulat Ziganshin: > VY> Да, пока там версия без последних апдейтов. Hадеюсь, скоро > VY> появятся дополнения. И, возможно, регулярность обновлений > VY> повысится. > > Да, было бы очень кстати. Вот, обновление сделано. Так что, заходите все на http://www.chat.ru/~arctest > И еще - лучше было бы отделить их от ACT, > чтоб сразу было видно - здесь вам не тут. Постараюсь договориться. Кстати, ты не против, если туда же выложить твою статью про cabarc? Всего доброго, Вадим. Sent via Deja.com http://www.deja.com/ Before you buy. --- ifmail v.2.14dev3 * Origin: Deja.com - Before you buy. (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 26 Oct 99 15:05:08 To : All Subj : Вот какая есть идея From: leob@mailcom.com (Leonid Broukhis) Сначала небольшое вступление: есть такой прибор, называется Palm (ранее PalmPilot). Клавиатуры у него нет, а есть только палочка-стило, которым можно рисовать стилизованные символы или тыкать в нарисованную на экране qwerty-клавиатуру. Символы можно запомнить и рисовать в целом довольно быстро (но много так не попишешь, рука устает), и в клавиатуру можно тыкать тоже быстро, если хорошо помнить расположение не пальцами, как нужно при слепой печати, а глазами; но при этом среднее расстояние, на которое нужно переносить стило от одной буквы до другой, довольно велико. Одна компания решила это дело исправить, набрала статистику встречаемости пар символов для английского языка, а по ней построила граф, в котором длина ребра между символами была обратно пропорциональна частоте встречаемости пары. После чего граф был упакован в прямоугольник 6х5, и получилось вот что: Z V C H W K F I T A L Y N E G D O R S B Q J U M P X из-за чего раскладка получила название Fitaly (см. www.fitaly.com) Так вот, есть ли у кого-нибудь данные для построения чего-нибудь подобного для русского языка? Прямоугольник, видимо, будет 6x6 c тремя позициями для пробела (или 7х5 с двумя). Leo PS. Кстати, известно, что раскладка qwerty - далеко не оптимальная для английского языка, а что Dvorak - гораздо лучше. Интересно, как выглядела бы оптимальная клавиатура для русского, при условии, что чем чаще встречается символ, тем ближе он к указательному пальцу в первоначальной позиции, и что наиболее часто встречающиеся пары символов печатаются разными пальцами, желательно на разных руках. --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 27 Oct 99 00:40:04 To : Bulat Ziganshin Subj : Опять Хаффман (было непpефиксное кодиpование) Hello, Bulat! Втp Окт 26 1999 09:50, Bulat Ziganshin wrote to Boris Batkin: BB>> а чем это отличается от пpостого динамического хаффмана? BZ> Hачальной моделью и необходимостью ее кодирования в выходном файле. с дpугой стоpоны, в этом случае мы каждый символ кодиpуем по _оптимальному_ де pеву. т.е. для длинного потока (т.е. много больше длинны начальной модели), выи гpыш должен быть существенным. Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : Cyril Slobin 2:5020/219.44 28 Oct 99 02:32:36 To : Leonid Broukhis Subj : Крипто (было: Методы аpхивации Rar'а) Hello Leonid! >P.S. Еще чем-то напоминает парадокс про двух убийц. LB> Расскажи. Уехало нетмейлом - компрессия здесь уже ну совсем ни при чем. ;-) Cyril Slobin --- * Origin: Привилегии имеют приоритет перед правами (2:5020/219.44)
Предыдущий блок Следующий блок Вернуться в индекс