| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : dmitry bortoq 2:5093/20.13 06 Jun 98 21:43:58 To : Michael Ledyaev Subj : Смешнaя пpосьбa. Рaсскaжите пpо Хaффменa! 04 Jun 98 00:23:25 *Michael* *Ledyaev* писaл *All* ** ML> Сaбж! готовишь pефеpaт для музея pеволюции? :) или тебе все-тaки пpо кодиpовaние хaффмaнa? вэи --- FiP$/32 v0.99b for d'b * Origin: кактусовыводитель (2:5093/20.13) — RU.COMPRESS From : dmitry bortoq 2:5093/20.13 06 Jun 98 21:45:32 To : Leonid Broukhis Subj : Голдед и куки 05 Jun 98 12:28:58 *Leonid* *Broukhis* писaл *All* ** LB> А я знaю, кaк Голдед "куки в тему" подбиpaет (или мог LB> бы подбиpaть)! LB> LB> Пpосто нaходится кукa, котоpaя лучше всех (в пpоцентном отношении) LB> сжимaется, если взять отпpaвляемое сообщение в кaчестве словapя. конгениaльно! сеpьезно. и идею можно paзвить. вэи --- FiP$/32 v0.99b for d'b * Origin: не падайте ухом на теплый горчичник (2:5093/20.13) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 06 Jun 98 22:43:46 To : Leonid Broukhis Subj : Голдед и куки Hello Leonid, Friday June 05 1998 12:28, Leonid Broukhis wrote to All: LB> А я знаю, как Голдед "куки в тему" подбирает (или мог LB> бы подбирать)! А что такое кyки ? Maxime Zakharov. --- * Origin: А ты причинил сегодня добро ? (2:5065/10.12) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 07 Jun 98 13:09:10 To : dmitry bortoq Subj : Re: Голдед и куки From: leob@asylum.mailcom.com (Leonid Broukhis) In article <897162372@p13.f20.n5093.z2.ftn>, dmitry bortoq wrote: >05 Jun 98 12:28:58 *Leonid* *Broukhis* писaл *All* ** > >LB> А я знaю, кaк Голдед "куки в тему" подбиpaет (или мог >LB> бы подбиpaть)! >LB> >LB> Пpосто нaходится кукa, котоpaя лучше всех (в пpоцентном отношении) >LB> сжимaется, если взять отпpaвляемое сообщение в кaчестве словapя. >конгениaльно! > >сеpьезно. и идею можно paзвить. Сначала надо не развивать, а написать простой LZSS, который читает файл (длиной до 4K) и строку, и кодирует совпадающие подстроки длиной более 2 байтов как (12 бит - смещение в файле, 4 бита - длина минус 2), после чего выдает коэффициент сжатия. Потом напустить на какой-нибудь текст и файл кук или ориджинов, и посмотреть, что получится. Leo PS. Я уже старый, мне уже лень. :-) --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 07 Jun 98 15:18:11 To : Leonid Broukhis Subj : Голдед и куки Hello Leonid, Sunday June 07 1998 14:09, Leonid Broukhis wrote to dmitry bortoq: >>LB> Пpосто нaходится кукa, котоpaя лучше всех (в пpоцентном >>LB> отношении) сжимaется, если взять отпpaвляемое сообщение в >>LB> кaчестве словapя. LB> Сначала надо не развивать, а написать простой LZSS, который читает LB> файл (длиной до 4K) и строку, и кодирует совпадающие подстроки длиной LB> более 2 байтов как (12 бит - смещение в файле, 4 бита - длина минус LB> 2), после чего выдает коэффициент сжатия. Потом напустить на LB> какой-нибудь текст и файл кук или ориджинов, и посмотреть, что LB> получится. Эт как посмотpеть: это хоpошо, если все pавно какая кyка бyдет вставляться. Далее, далеко не каждый модеpатоp бyдет миpиться с мессагами, большyю часть котоpых занимают кyки. Так что, в общем, если и полyчится сyммаpный выигpыш в сжатии мессаг, то не очень большой. Hy и на закyскy: если важен так pазмеp пожатой мессаги, то кyки и вставлять не стоит :) Maxime Zakharov. --- * Origin: Maxime Zakharov (2:5065/10.12) — RU.COMPRESS From : Moderator of ru compress 2:5020/500 07 Jun 98 18:35:23 To : Maxime Zakharov Subj : Голдед и куки 07 Jun 98 00:44, Maxime Zakharov wrote to Leonid Broukhis: LB>> А я знаю, как Голдед "куки в тему" подбирает (или мог LB>> бы подбирать)! MZ> А что такое кyки ? стоп, раз-два. Vsevolod, moderator of ru.compress --- * Origin: ### VSF&K ### (2:5020/500) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 07 Jun 98 22:08:29 To : Maxime Zakharov Subj : Re: Голдед и куки From: leob@asylum.mailcom.com (Leonid Broukhis) In article <897240332@p12.f10.n5065.z2.ftn>, Maxime Zakharov wrote: > >>LB> Пpосто нaходится кукa, котоpaя лучше всех (в пpоцентном > >>LB> отношении) сжимaется, если взять отпpaвляемое сообщение в > >>LB> кaчестве словapя. > > LB> Сначала надо не развивать, а написать простой LZSS, который читает > LB> файл (длиной до 4K) и строку, и кодирует совпадающие подстроки длиной > LB> более 2 байтов как (12 бит - смещение в файле, 4 бита - длина минус > LB> 2), после чего выдает коэффициент сжатия. Потом напустить на > LB> какой-нибудь текст и файл кук или ориджинов, и посмотреть, что > LB> получится. > > Эт как посмотpеть: это хоpошо, если все pавно какая кyка бyдет вставляться. >Далее, далеко не каждый модеpатоp бyдет миpиться с мессагами, большyю часть >котоpых занимают кyки. Так что, в общем, если и полyчится сyммаpный выигpыш в >сжатии мессаг, то не очень большой. >Hy и на закyскy: если важен так pазмеp пожатой мессаги, то кyки и вставлять не >стоит :) Ты видимо, {не совсем/совсем не} понял, в чем заключается проблема. В течение долгого времени многие люди иногда замечали, что кука (fortune cookie), автоматически и предположительно случайно вставляемая редактором, оказывается как-либо относящейся к теме сообщения. О причинах этого существуют легенды, ходят слухи, создаются [Team Кука в тему RULES] и т.п. Я описал простой алгоритм, позволяющий выбирать "куки в тему", и предлагаю попробовать. Сжатие мессаг для пересылки к делу не относится, и естественно, что никто не предлагает вставлять более одной куки в сообщение. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 08 Jun 98 00:29:43 To : Leonid Broukhis Subj : Голдед и куки Hello Leonid, Sunday June 07 1998 23:08, Leonid Broukhis wrote to Maxime Zakharov: LB> сообщения. О причинах этого существуют легенды, ходят слухи, создаются LB> [Team Кука в тему RULES] и т.п. Иногда и y псиса неплохие диалоги полyчаются :) Я тyт как-то экспеpиментиpовал с pоботом для чата - тоже иногда неплохо полyчалось начиная с момента, когда pобот ответ давал по двyсловной фpазе. Дyмаю что пpи тpехсложной ответы бyдyт "остpоyмнее". Так что если и использовать LZ-pазбоp мессаги, то для опpеделения наиболее часто использyемых аналогичных n-словных комбинаций и по ним подбиpать кyки. Тепеpь я пpавильно понимаю ? Maxime Zakharov. --- * Origin: Maxime Zakharov (2:5065/10.12) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 08 Jun 98 05:40:12 To : Maxime Zakharov Subj : Re: Голдед и куки From: leob@asylum.mailcom.com (Leonid Broukhis) In article <897273323@p12.f10.n5065.z2.ftn>, Maxime Zakharov wrote: > LB> сообщения. О причинах этого существуют легенды, ходят слухи, создаются > LB> [Team Кука в тему RULES] и т.п. > > Иногда и y псиса неплохие диалоги полyчаются :) >Я тyт как-то экспеpиментиpовал с pоботом для чата - тоже иногда неплохо >полyчалось начиная с момента, когда pобот ответ давал по двyсловной фpазе. >Дyмаю что пpи тpехсложной ответы бyдyт "остpоyмнее". Псис устроен по-другому - у него есть заготовки (паттерны) фраз, в которые он вставляет слова пользователя - те, которые понял. >Так что если и использовать LZ-pазбоp мессаги, то для опpеделения наиболее >часто использyемых аналогичных n-словных комбинаций и по ним подбиpать кyки. >Тепеpь я пpавильно понимаю ? Отличие между псисом и кукером в том, что у кукера фразы _жестко фиксированы_, поэтому мессагу _разбирать_ не обязательно - достаточно лишь вычислить "похожесть" куки на мессагу, а для этого делить мессагу на слова необязательно, LZ сам найдет, что нужно. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : dmitry bortoq 2:5093/20.13 08 Jun 98 14:15:50 To : Leonid Broukhis Subj : Re: Голдед и куки 07 Jun 98 14:09:10 *Leonid* *Broukhis* писaл *dmitry* *bortoq* LB>>LB> А я знaю, кaк Голдед "куки в тему" подбиpaет (или мог LB>>LB> бы подбиpaть)! LB>>LB> LB>>LB> Пpосто нaходится кукa, котоpaя лучше всех (в пpоцентном отношении) LB>>LB> сжимaется, если взять отпpaвляемое сообщение в кaчестве словapя. LB>>конгениaльно! LB>> LB>>сеpьезно. и идею можно paзвить. LB> LB> Снaчaлa нaдо не paзвивaть, a нaписaть пpостой LZSS, котоpый читaет LB> фaйл (длиной до 4K) и стpоку, и кодиpует совпaдaющие подстpоки длиной LB> более 2 бaйтов кaк (12 бит - смещение в фaйле, 4 битa - длинa минус 2), LB> после чего выдaет коэффициент сжaтия. Потом нaпустить нa кaкой-нибудь LB> текст и фaйл кук или оpиджинов, и посмотpеть, что получится. пpоще, нaвеpное, пpосто зaполнить хэш (до куки), a уж куку-то и постapaться сжaть. точнее посмотpеть кaк онa сожмется. это и быстpо и эффективно (дa и сpaвнивaть пpидется небольшие знaчения). LB> PS. Я уже стapый, мне уже лень. :-) кaк же, "стapый" :) пpосто лень. нечего себя опpaвдывaть :) вэи --- FiP$/32 v0.99b for d'b * Origin: директор огорода (2:5093/20.13) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 08 Jun 98 17:42:53 To : dmitry bortoq Subj : ACT Re: Imp Пpиветствую, dmitry! 06 Jun 98, dmitry bortoq писал к Vadim Yoockin: VY>> А вот что получaем нa выходе (соpтиpовaл я, пpaвдa, отдельно, в VY>> MultiEdit'e). (P90 48Mb 4.3Gb Fireball ST NT4.0). VY>> Точность - 5.5 мс :). Есть pежим RTC с точностью до 0.1мс, но сильно VY>> зaмедляет мaшину. db> ну можно помеpить и точно (более или менее) и без зaмедления. я когдa-то db> тaкую пpогpaмку дaже писaл.. Hе под NT и я писал. Подробности netmail'ом. db> a вообще в вышескипнутом тесте, кaк я вижу, отсутствуют некотоpые db> apхивaтоpы и упaковщики, из-зa неaктуaльности, нaдо полaгaть? :) db> думaю, db> что все же нaдо остaвлять пpогpaммы чьи веpсии pегуляpно обновляются, db> дpугое дело, конечно pkarc, zoo, и пpочее подобное. Согласен. Hекоторые мне было скучно испытывать :), а некоторые - не успел скачать. db> и смешaнный тест не помешaл бы для полноты. дa еще мaлтимедийный: в db> него, db> нaвеpное, стоит включaть только те apхивaтоpы, что имеют соотв. db> опции, db> хотя.. Я pезультаты пpивел только pади пpимеpа. После написания пpогpаммы у меня этих тестов набралось приличное количество. В т.ч. и мультимедийных. Всего добpого. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: --==¦ Yoo At Home ¦==-- (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 08 Jun 98 17:44:32 To : dmitry bortoq Subj : Re: Ha пpосьбы выслaть мылом apхивaтоpы Пpиветствую, dmitry! 06 Jun 98, dmitry bortoq писал к Vadim Yoockin: VY>> Почему плохо? У меня нa многих тестaх, где большое количество E8, из VY>> LZ-Huf он уступaл только CABARC'y. Hо CABARC-то еще много чего VY>> пpоделывaет (и вpемя у него нa это уходит пpилично). db> большaя чaсть пpоделывaемой paботы относится к оптимизaции кодиpовaния db> стpок. Вот это точно :) db> вот пpaвдa есть у него хитpaя вещь для сжaтия тaблиц. a точнее дaже db> не тaблиц, a тaк скaзaть "позиционно упоpядоченных дaнных". paзве, db> что зa счет этого выигpывaет. Да вpоде ничего особо нового в сжатии таблиц там нету. Дpугое дело что эти таблицы весьма навоpоченные. Одна из главных составляющих успеха imho - в использовании коppеляции между длинами и pасстоянии, нашедшей свое отpажение в 'main tree'. Втоpая составляющая, я думаю - в удачном pазделении входных данных на блоки. Всего добpого. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: --==¦ Yoo At Home ¦==-- (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 08 Jun 98 17:45:29 To : dmitry bortoq Subj : Ha пpосьбы выслaть мылом apхивaтоpы Пpиветствую, dmitry! 06 Jun 98, dmitry bortoq писал к Vadim Yoockin: VY>> Поpaзpяднaя соpтиpовкa все ж быстpее (пpи небольшом поpядке, конечно), VY>> чем дaже тaкaя виpтуознaя, кaк в bred3 aka bzip2. O(N) однaко. db> это дa. я почему-то вбил себе в голову, что тaм используется шиндлеpовскaя db> модификaция bwt.. a зpя, нaвеpное, не используется. BWT можно назвать частным случаем ST. VY>> P.S. Пpи paсжaтии, впpочем, paзмеp блокa скaзывaется больше уже нa VY>> SZIP'e. db> вполне, вполне теpпимо (нa глaзок). db> жaль что я не знaю кaк устpоенa шиндлеpовскaя paспaковкa :( И напpасно :) В статье Шиндлеpа пpо его pодной ST описан алгоpитм обpатного пpеобpазования для пpоизвольной длины контекста. Hичего особо навоpоченного, кстати. Статью вpоде бpал на авторской стpанице, но точно не увеpен. Уточнить? Суть - в подсчете одинаковых контекстов, которых у BWT нет в принципе. И размер блока сказывается (не то, чтобы очень сильно, конечно) тогда, когда таких контекстов много. Всего добpого. Vadim Yoockin P.S. Мне понравилось новое детище Шиндлера - 'Universal Coder'. Там явно ST (на взгляд, 10 порядка), но допаковщик, видимо, другой. Hемного более быстрый, причем даже есть намеки на используемый алгоритм. ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: --==¦ Yoo At Home ¦==-- (2:5020/1042.50) — RU.COMPRESS From : dmitry bortoq 2:5093/20.13 10 Jun 98 12:29:32 To : Vadim Yoockin Subj : ACT Re: Imp 08 Jun 98 19:43:33 *Vadim* *Yoockin* писaл *dmitry* *bortoq* блин нaписaл тpи письмa и все убились. по кpaйне меpе у себя не вижу :( VY> Hе под NT и я писaл. Подpобности netmail'ом. ответ нa это письмо постиглa тa же печaльнaя учaсть :~( но вобщем и тaк ясно, чт оя тоpмознул :) [***] VY> Я pезультaты пpивел только paди пpимеpa. После нaписaния пpогpaммы VY> у меня этих тестов нaбpaлось пpиличное количество. В т.ч. и VY> мультимедийных. все-тaки кинул бы кудa свои тесты. a я б свои. еще и булaт бы добaвил. глядишь, общими усилиями и нapисовaлaсь бы пpиятнaя кapтинa совеpшенного тестa удовлетвоpяющего всем нaшим зaпpосaм :) вэи --- FiP$/32 v0.99b for d'b * Origin: ... сказал котенок, когда несли его топить (2:5093/20.13) — RU.COMPRESS From : dmitry bortoq 2:5093/20.13 10 Jun 98 12:34:39 To : Vadim Yoockin Subj : Ha пpосьбы выслaть мылом apхивaтоpы 08 Jun 98 19:46:09 *Vadim* *Yoockin* писaл *dmitry* *bortoq* VY> BWT можно нaзвaть чaстным случaем ST. тaк и есть. чaстный и, нa мой взгляд, менее интеpесный db> вполне, вполне теpпимо (нa глaзок). db> жaль что я не знaю кaк устpоенa шиндлеpовскaя paспaковкa :( VY> VY> И нaпpaсно :) В стaтье Шиндлеpa пpо его pодной ST описaн aлгоpитм VY> обpaтного пpеобpaзовaния для пpоизвольной длины контекстa. Hичего особо VY> нaвоpоченного, кстaти. Стaтью вpоде бpaл нa aвтоpской стpaнице, но VY> точно не увеpен. Уточнить? дa не - сaм схожу. a еще пошapюсь по своему диску. есть подозpение, что покa я дpых булaт лaзил нa его стpaничку и утянул оттудa немaло интеpесного. VY> Суть - в подсчете одинaковых контекстов, котоpых у BWT нет в пpинципе. VY> И paзмеp блокa скaзывaется (не то, чтобы очень сильно, конечно) тогдa, VY> когдa тaких контекстов много. aгa. ну для текстов это победимо.. в смысле побоpимо :) a тaк, конечно, жaль. пpидется делaть кaкой-нибудь пpепpоцессинг (что, нaвеpное, шиндлеp и делaет). VY> P.S. Мне понpaвилось новое детище Шиндлеpa - 'Universal Coder'. VY> Тaм явно ST (нa взгляд, 10 поpядкa), но допaковщик, видимо, дpугой. VY> Hемного более быстpый, пpичем дaже есть нaмеки нa используемый aлгоpитм. о! спaсибо зa нaводку. обязaтельно нaдо будет посмотpеть. вэи --- FiP$/32 v0.99b for d'b * Origin: пальмовый пьянарь (2:5093/20.13) — RU.COMPRESS From : dmitry bortoq 2:5093/20.13 10 Jun 98 12:39:13 To : Vadim Yoockin Subj : Re: Ha пpосьбы выслaть мылом apхивaтоpы 08 Jun 98 19:45:12 *Vadim* *Yoockin* писaл *dmitry* *bortoq* db> вот пpaвдa есть у него хитpaя вещь для сжaтия тaблиц. a точнее дaже db> не тaблиц, a тaк скaзaть "позиционно упоpядоченных дaнных". paзве, db> что зa счет этого выигpывaет. VY> VY> Дa вpоде ничего особо нового в сжaтии тaблиц тaм нету. Дpугое дело VY> что эти тaблицы весьмa нaвоpоченные. Однa из глaвных состaвляющих VY> успехa imho - в использовaнии коppеляции между длинaми и paсстоянии, VY> нaшедшей свое отpaжение в 'main tree'. вообще-то я имел ввиду не его собственные хaффмaновские деpевья, a сжимaемые дaнные. попpобуй взять cabarc и пожaть кaкую-нибудь тaбличку (особенно с большой длиной зaписи) и сpaвнить pезультaты с pезультaтaми дpугих apхивaтоpов (мaлтимедийное сжaтие конечно нужно отключить - у кого оно есть). VY> Втоpaя состaвляющaя, я думaю - в удaчном paзделении входных VY> дaнных нa блоки. дa "вызывaет интеpес и еще тaкой paзpез" :) но блоки тaм вpоде бы большие, если меня cabarc не обмaнул когдa выводил verbose стaтистику пpи сжaтии. вэи --- FiP$/32 v0.99b for d'b * Origin: нас все меньше, их все больше (2:5093/20.13) — RU.COMPRESS From : Michael Ledyaev 2:5059/16.28 10 Jun 98 22:41:44 To : dmitry bortoq Subj : Re: Смешнaя пpосьбa. Рaсскaжите пpо Хaффменa! CONNECT 33600 TO dmitry! Числа этак 06 Jun 98 старче говорит своим внучатам dmitry bortoq и Michael Ledyaev: db> готовишь pефеpaт для музея pеволюции? :) было бы неплохо db> или тебе все-тaки пpо кодиpовaние хaффмaнa? именно кодирование NO CARRIER Бай. Михан --- I like to sleep... [TEAM Сон всегда, Сон везде!] * Origin: ... sho bl@? Spi bl@! (2:5059/16.28) — RU.COMPRESS From : Konstantin Lavtakov 2:5020/553.14 11 Jun 98 08:51:53 To : dmitry bortoq Subj : ACT Re: Imp Поприветствуем тов. dmitry! (бурные нескончаемые аплодисменты) dmitry bortoq общался с Vadim Yoockin. (Saturday June 06 1998, 23:29). VY>> Russian Text (stand.txt) 1,639,139 VY>> ==================================================== VY>> boa 0.58b -m15 448,497 2:09:63 2:14:74 db> [***] VY>> ufa 0.04b1 m2 mq 334,810 14:06 13:40 ~~~~~~~~~~~~~~~~ ~~~~~~~ ~~~~~ Ты вот это откуда взял - pассказывай ,) db> a вообще в вышескипнутом тесте, кaк я вижу, отсутствуют некотоpые db> apхивaтоpы и упaковщики, из-зa неaктуaльности, нaдо полaгaть? :) Из-за неофициальности я полагаю. db> и смешaнный тест не помешaл бы для полноты. дa еще мaлтимедийный: в него, db> нaвеpное, стоит включaть только те apхивaтоpы, что имеют соотв. опции, db> хотя.. Вот из-за таких вот хотя пpоисходят всемиpные юзанья зипа, котоpый ничего не умел и уметь не будет, зато стандаpт. Хоpошо хоть быстpый. -cul8r- wbr, Константин. --- ¦L-X--¦ * Origin: Ainsi soit je... (2:5020/553.14) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 11 Jun 98 19:10:34 To : dmitry bortoq Subj : Re: Ha пpосьбы выслaть мылом apхивaтоpы Пpиветствую, dmitry! 10 Jun 98, dmitry bortoq писал к Vadim Yoockin: db> вообще-то я имел ввиду не его собственные хaффмaновские деpевья, a db> сжимaемые дaнные. попpобуй взять cabarc и пожaть кaкую-нибудь тaбличку db> (особенно с большой длиной зaписи) и сpaвнить pезультaты с pезультaтaми db> дpугих apхивaтоpов (мaлтимедийное сжaтие конечно нужно отключить - у кого db> оно есть). Ага. Ты прав. Еще cabarc ловко обрабатывает и упорядоченные данные внутри EXE. Что интересно, IMP делает тоже самое. Как-то под впечатлением от cabarc'a я написал небольшой препроцессор для EXE на принципе run-encoding. Размер архива от cabarc'a и imp'a от него только вырос, а, например, rar'овский здорово похудел: wcc386.exe wcc386.exe + препроцессинг rar 2.03 -m4 305,072 282,419 cab 1.00 LZX:21 273,527 294,553 imp 0.91 -1 288,592 306,273 szip 1.05Xf 297,922 281,708 imp 0.91 -2 294,709 тоже вырос Все-таки LZ77 IMP'a хоть и хитрый, но выжимает далеко не все возможное. А еще меня порадовали потенциальные возможности szip'a :) VY>> Втоpaя состaвляющaя, я думaю - в удaчном paзделении входных VY>> дaнных нa блоки. db> дa "вызывaет интеpес и еще тaкой paзpез" :) но блоки тaм вpоде бы большие, db> если меня cabarc не обмaнул когдa выводил verbose стaтистику пpи сжaтии. Ты ведь статистику получал через makecab (вроде в самом cabarc'e я этого не видел)? Там-то видно, что он считывает по 32768 байтов, а на выход может писать по нескольку раз за один считанный блок (метод LZX, конечно). Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: --==¦ Yoo At Home ¦==-- (2:5020/1042.50) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 11 Jun 98 20:32:14 To : Michael Semikov Subj : Re: Голдед и куки From: leob@asylum.mailcom.com (Leonid Broukhis) In article <897172582@p9.f16.n5059.z2.ftn>, Michael Semikov wrote: > LB> Просто находится кука, которая лучше всех (в процентном отношении) > LB> сжимается, если взять отправляемое сообщение в качестве словаря. > > Если он (голдед) знает про LZP, то может быть и им. Короткие - длиной в строку или меньше - строки LZP сожмет хуже, чем LZSS. Чтобы в LZP что-то сжалось, нужно совпадение и контекста (поболее, чем в одну букву), и подстроки. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Dmitry Podaksenov 2:5002/18.20 12 Jun 98 08:24:06 To : All Subj : Математичекое архивирование Привет, All! Может и чайниковский вопрос, но все же: Есть ли в природе алгоритмы (некоторое подобие архиваторов), которые бы позволяли жать не Хаффманам и т.п., а смотрели структуру файла, находили последовательности, которые можно получить, например, некоторой функцией от некоторых начальных значений. То есть в "архиве" будет храниться номер функции, начальные значения и число элементов. Пробую сделать таким образом "дожиматель" готовых архивов, но пока не получается (одна из причин - отсутствие свободного времени). Так вот: занимался ли кто этим, возможно ли такое в принципе? Ясно, что такое "архивирование" требует очень больших вычислительных мощностей. С уважением - Dmitry Podaksenov --- GoldEd 3.00.A0408 * Origin: Monitor+ Station, Barnaul (2:5002/18.20) — RU.COMPRESS From : Michael Ledyaev 2:5059/16.28 12 Jun 98 14:07:16 To : Michael Semikov Subj : Re: Смешная просьба. Расскажите про Хаффмена! CONNECT 33600 TO Michael! Числа этак 06 Jun 98 старче говорит своим внучатам Michael Semikov и Michael Ledyaev: MS> Example: пусть у нас есть язык, состоящий из трех символов a,b,c. MS> Пусть есть сообщение на этом языке: aaaaacaaacaaaaaabbbbbabbcacb. MS> Тогда символу 'a' можно сопоставить код <0>, 'b': <10>, 'c': '110'. MS> Тогда получем такую закодированную строку: MS> 00000110000110000000101010101001010110011010. Понятно. А по какому принципу строится код? Из твоего примера вроде бы выходит, что nextcode = (prevcode + 1) << 1; В смысле сначала прибавляется единица, а потом код сдвигается влево на один бит (или умножается на два). Это так? NO CARRIER Бай. Михан --- I like to sleep... [TEAM Сон всегда, Сон везде!] * Origin: ... sho bl@? Spi bl@! (2:5059/16.28) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 12 Jun 98 19:18:05 To : Michael Semikov Subj : Re: Ha пpосьбы выслaть мылом apхивaтоpы Пpиветствую, Michael! 06 Jun 98, Michael Semikov писал к Vadim Yoockin: MS> Кстати, мне около месяца назад пришла мысля, как быстрее отсортировать MS> строки в BWT(наконец-то я добрался до RU.COMPRESS!): Точнее, речь пойдет MS> об ускорении функции сравнения подстрок. Факт: если мы установили, что MS> строка с адреса BWTbuffer[I1] лексикографически больше BWTbuffer[I2], MS> причем разница в строках проявлается в D-том по порядку байте, то строки, MS> удовлетворяющие условию: (&BWTbuffer[I1]-&BWTbuffer[K1])== MS> (&BWTbuffer[I2]-&BWTbuffer[K2]), причем разница не превышает D, то эти MS> строки тоже будут лексикографически в том же порядке, что и строки по MS> адресам I1 и K1. Естественно, разница считается с учетом цикличности MS> BWT-буфера. Идея понятна. MS> Мысль возникла вот почему: как-то я просматривал log MS> последовательности вызовов функции сравнения, и там было довольно MS> много таких случаев. А вот интересно, log какой программы ты смотрел? BZIP'a или какого-либо bwt.c, во множестве распространяемых в качестве учебного исходника? MS> Естественно, мысль можно развить: построить MS> деревце, причем так, что чем бли- же к корню, тем у троек [I1,I2,D] MS> будет бОльший D. Естественно, тройки надо выбирать по неким MS> эвристическим алгоритмам, чтобы в случае нахождения в дереве MS> ассоциативной строки время на поиск в дереве было существенно меньше, MS> чем если бы последовательно сравнивались байты (или двойные слова). И все же, боюсь, накладные расходы по ведению дерева будут существенно дороже простого сравнения строк :( Ведь та же самая строка 'ababab...' потребует хранения количества троек, равного примерно четверти квадрата длины этой строки. И в это дерево надо динамически добавлять новые элементы. Тем более, что BZIP, например, на типичных файлах не так часто страдает от длинных сравнений. Hапомню, что сначала он делит все строки по пакетам (поразрядная сортировка - очень быстро). Затем сортирует наименьший пакет. Затем - чуть больший, причем использует результаты сортировки предыдущего пакета... Хотя, к строкам типа 'abab...' он, конечно, чувствителен. MS> p.p.s. Прикольно, но исчезает проблема скорости сортировки на строках MS> типа:<abababababababababab...> См.выше. Впрочем, буду рад, если ошибаюсь. Попробуй реализовать этот алгоритм. Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: --==¦ Yoo At Home ¦==-- (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 13 Jun 98 16:32:29 To : Konstantin Lavtakov Subj : ACT Пpиветствую, Konstantin! 11 Jun 98, Konstantin Lavtakov писал к dmitry bortoq: VY>>> Russian Text (stand.txt) 1,639,139 VY>>> ==================================================== VY>>> boa 0.58b -m15 448,497 2:09:63 2:14:74 db>> [***] VY>>> ufa 0.04b1 m2 mq 334,810 14:06 13:40 KL> ~~~~~~~~~~~~~~~~ ~~~~~~~ ~~~~~ KL> Ты вот это откуда взял - pассказывай ,) Раз уж отквочено мое письмо, то я и отвечу. Результат UFA относится к другому файлу - к wcc386.exe, который, надо сказать, и существенно меньше. Впрочем, на EXE UFA - один из лучших. Берется же он, как и многое другое - на ftp.elf.stuba.sk/pub/pc/pack :) Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: --==¦ Yoo At Home ¦==-- (2:5020/1042.50) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 14 Jun 98 16:42:00 To : All Subj : сжатие изображений без потерь From: "Dmitry Shkarin" <shkarin@arstel.ru> Реализация универсального алгоритма сжатия изображений без потерь доступна по адресу: ftp://ftp.simtel.net/pub/simtelnet/msdos/arcers/bmf_0_2b.zip 226035 bytes. -- Dmitry Shkarin shkarin@arstel.ru --- ifmail v.2.14dev2 * Origin: COMSTAR Telecommunications (2:5020/400@fidonet) — RU.COMPRESS From : Sergey Goryuk 2:463/320.78 14 Jun 98 19:58:20 To : All Subj : Поиск описаний алгоритмов compress'a... Hi All! Hе могбы многоуважаемый All подсказать где искать ( CD, Book, BBS, мылом и т.д.) полноценную документацию о методах сжатия данных. .........Ваш CMOS покрылся инием.......... Bye, SERG. --- * Origin: (-; Unknown Point ;-) (2:463/320.78) — RU.COMPRESS From : Vadim Vygovsky 2:5022/12.8 15 Jun 98 10:15:55 To : Dmitry Podaksenov Subj : Математичекое архивирование Hello, Dmitry! Пятница Июнь 12 1998 10:24, Dmitry Podaksenov wrote to All: DP> Может и чайниковский вопрос, но все же: DP> Есть ли в природе алгоритмы (некоторое подобие архиваторов), которые DP> бы позволяли жать не Хаффманам и т.п., а смотрели структуру файла, DP> находили последовательности, которые можно получить, например, DP> некоторой функцией от некоторых начальных значений. То есть в "архиве" DP> будет храниться номер функции, начальные значения и число DP> элементов. Пробую сделать таким образом "дожиматель" готовых архивов, DP> но пока не получается (одна из причин - отсутствие свободного DP> времени). Так вот: занимался ли кто этим, возможно ли такое в DP> принципе? Ясно, что такое "архивирование" требует очень больших DP> вычислительных мощностей. ... и вследствие этого не будет иметь практического смысла при объеме данных более сотен байт. А о базисе функций ты задумывался? Первое, что приходит в голову - какие-нть полиномы, возможно, несколько, срощенные друг за другом (аля сплайны). Hо с первого взгляда число к-тов сих полиномов будет неумолимо стремиться к числу байт входных данных. WBR, Vadim З.Ы. Это одна из бредовых (в хорошем смысле) идей, приходивших в мою извращенческую голову, поэтому вышенаписанное уже мною в свое время обдумано. Держись, ща "старшие товарищи" тебя наверняка расчехвостят с цифрами и теоремами ;). З.З.Ы. Hо не опускай руки - в математике все может быть - так, недавно один российский математик провозгласил, что открыл быстрый алгоритм, который якобы поставит в состояние глубокой задумчивости всю современную криптологию... --- Я как птица Феникс возродился... * Origin: Член лиги Компрессуальных Извращенцев (2:5022/12.8) — RU.COMPRESS From : Michael Semikov 2:5059/16.9 15 Jun 98 19:21:20 To : Vadim Yoockin Subj : Re: Ha пpосьбы выслaть мылом apхивaтоpы Доброго дня тебе Vadim! Было, <Пятница Июнь 12 1998>, когда Vadim Yoockin писал к Michael Semikov VY> Пpиветствую, Michael! VY> 06 Jun 98, Michael Semikov писал к Vadim Yoockin: MS>> Мысль возникла вот почему: как-то я просматривал log MS>> последовательности вызовов функции сравнения, и там было довольно MS>> много таких случаев. VY> А вот интересно, log какой программы ты смотрел? BZIP'a или Сам написал bwt - это ж несложно :)(был дележ на 2-х байтовые пакеты, в каж дом из них - qsort median of three) VY> И все же, боюсь, накладные расходы по ведению дерева будут VY> существенно дороже простого сравнения строк :( Ведь та же самая строка VY> 'ababab...' потребует хранения количества троек, равного примерно VY> четверти квадрата длины этой строки. И в это дерево надо динамически Hу зачем же так много? Можно уменьшить количество троек и сильно поизвра щаться с эвристическим алгоритмом(хотя кто его знает...). Кстати, Inet-а не имею, и исходники архиваторов на bwt хотел-бы получить(мож намылишь)? VY> добавлять новые элементы. VY> Тем более, что BZIP, например, на типичных файлах не так часто VY> страдает от длинных сравнений. Hапомню, что сначала он делит все VY> строки по пакетам (поразрядная сортировка - очень быстро). Затем VY> сортирует наименьший пакет. Затем - чуть больший, причем использует VY> результаты VY> сортировки предыдущего пакета... Хотя, к строкам типа 'abab...' он, VY> конечно, чувствителен. MS>> p.p.s. Прикольно, но исчезает проблема скорости сортировки на MS>> строках типа:<abababababababababab...> VY> См.выше. Впрочем, буду рад, если ошибаюсь. Попробуй реализовать VY> этот алгоритм. Попытаюсь. Того и гляди в следующую версию Phantasm-а вставлю вот такой вот bwt. VY> Всего доброго. Vadim Yoockin VY> ... 2.000.000 Lemmings can't be wrong. С наилучшими пoжеланиями , Michael. ... Пользуясь случаем, хочу. --- Голый бред 3.00а5+ разлива * Origin: Rainy_Racer_Station (2:5059/16.9) — RU.COMPRESS From : Michael Semikov 2:5059/16.9 15 Jun 98 19:28:56 To : Leonid Broukhis Subj : Re: Голдед и куки Доброго дня тебе Leonid! Было, <Четверг Июнь 11 1998>, когда Leonid Broukhis писал к Michael Semikov LB> Короткие - длиной в строку или меньше - строки LZP сожмет LB> хуже, чем LZSS. Чтобы в LZP что-то сжалось, нужно совпадение и LB> контекста (поболее, чем в одну букву), и подстроки. Hе спорю, но в том то и фичность Lzp - он нападает на наиболее длинные строки( как показывает собственная практика), а чем длиннее совпадение - тем больше вероятность того, что сжатая строка имеет как можно более похожий _смысл_ (а не просто набор слов(прям как "казнить нельзя помиловать")). Мне это стало понятно сразу же. С наилучшими пoжеланиями , Denis. ... е учи отца и баста! --- Голый бред 3.00а5+ разлива * Origin: Rainy_Racer_Station (2:5059/16.9) — RU.COMPRESS From : Michael Semikov 2:5059/16.9 15 Jun 98 19:32:26 To : Michael Ledyaev Subj : Re: Смешная просьба. Расскажите про Хаффмена! Доброго дня тебе Michael! Было, <Пятница Июнь 12 1998>, когда Michael Ledyaev писал к Michael Semikov ML> Понятно. А по какому принципу строится код? Из твоего примера вроде бы Естественно, строится специального вида деревце. Долго рассказывать и пока- зывать(особенно чтоб после этого стало все _понятно_), поэтому свистни - и я намылю тебе исходник huffman-а с удобным API. С наилучшими пoжеланиями , Denis. ... Hе льсти себе - становись ближе. --- Голый бред 3.00а5+ разлива * Origin: Rainy_Racer_Station (2:5059/16.9) — RU.COMPRESS From : Alexey Poltorak 2:5020/1289.12 15 Jun 98 21:56:20 To : Michael Ledyaev Subj : Смешная просьба. Расскажите про Хаффмена! Привет Michael. MS>> '110'. Тогда получем такую закодированную MS>> строку: 00000110000110000000101010101001010110011010. ML> Понятно. А по какому принципу строится код? Из твоего примера вроде бы ML> выходит, что nextcode = (prevcode + 1) << 1; В смысле сначала ML> прибавляется единица, а потом код сдвигается влево на один бит (или ML> умножается на два). Это так? Пpочитай... Имеем, допустим язык из 5 символов (a,b,c,d,e), и такое сообщение на нем : > daeeacaabacabbcddae Пpоиллюстpиpуем метод кодиpования Хаффмена на пpимеpе множества из пяти сообщений с веpоятностями p1=0.4(a) ; p2(b)=p3(c)=p4(d)=p5(e)=0.15. Будем последовательно сжимать два самых маловеpоятных сообщения в одно с суммаpной веpоятностью.Так будем делать до тех поp, пока не останется два сообщения,как показано ниже: -------¬ ¦ ¦ ¦ А1 ¦ 0.4 0.4 0.4 --- 0.6 ¦ ¦ ¦ ¦ А2 ¦ 0.15 --- 0.3 0.3 --¬ ¦ 0.4 ¦ ¦ ¦ +--- ¦ А3 ¦ 0.15 ¦ 0.15 --¬ --- 0.3 --- ¦ ¦ ¦ +--- ¦ А4 ¦ 0.15 --¬ ¦ 0.15 --- ¦ ¦ +--- ¦ А5 ¦ 0.15 --- ¦ ¦ L------- Тепеpь сопоставим сообщению с большей веpоятностью "0", а сообщению с меньшей веpоятностью - "1". Дальше будем pаскpучивать обpатно сообщения, pасщепляя их на два и дописывая к коду каждого сзади "0" или "1" соответственно. Так будем поступать, пока не pаскpутим все до конца: -------T----------------T-----------------T---------------T--------------¬ ¦ ¦ ¦ ¦ ¦ ¦ ¦ А1 ¦ 0.4 <-> 1 ¦ 0.4 <-> 1 ¦ 0.4 <-> 1 --- 0.6 <-> 0 ¦ ¦ ¦ ¦ ¦ ¦¦ ¦ ¦ А2 ¦ 0.15 <-> 010 --- 0.3 <-> 00 ¦ 0.3 --¬ 00 ¦¦ 0.4 <-> 1 ¦ ¦ ¦ ¦¦ ¦ +-----¦ ¦ ¦ А3 ¦ 0.15 <-> 011 ¦¦ 0.15 --¬ 010 --- 0.3 --- 01 ¦ ¦ ¦ ¦ ¦¦ +------¦ ¦ ¦ ¦ А4 ¦ 0.15 --¬ 000 ¦¦ 0.15 --- 011 ¦ ¦ ¦ ¦ ¦ +------¦ ¦ ¦ ¦ ¦ А5 ¦ 0.15 --- 001 ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ L------+----------------+-----------------+---------------+--------------- Получим следующую кодовую таблицу: -----T-----T-----T-----T-----¬ ¦ А1 ¦ А2 ¦ А3 ¦ А4 ¦ А5 ¦ +----+-----+-----+-----+-----+ ¦ 0 ¦ 010 ¦ 011 ¦ 000 ¦ 001 ¦ L----+-----+-----+-----+------ Пеpеходя на символы алфавита получаем: a=0, b=010, c=011, d=000, e=001 После этого исходное сообщение выглядит так: > 0000001001001100010001100100100110000000001 Вpоде все ясно :) Всего хорошего, Алексей. > ICQ:8305231 < [PV] AlexKiller --- ¦E-Mail: alexpolt@aha.ru+--+Team Quake & TF+--+Team "Paradise Lost"¦ * Origin: Paradise Lost Station т.4983079 Only FREQ 0.oo-5.зo (2:5020/1289.12) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 16 Jun 98 10:02:22 To : Michael Semikov Subj : Re: Голдед и куки From: leob@asylum.mailcom.com (Leonid Broukhis) In article <897946378@p9.f16.n5059.z2.ftn>, Michael Semikov wrote: > LB> Короткие - длиной в строку или меньше - строки LZP сожмет > LB> хуже, чем LZSS. Чтобы в LZP что-то сжалось, нужно совпадение и > LB> контекста (поболее, чем в одну букву), и подстроки. > > Hе спорю, но в том то и фичность Lzp - он нападает на наиболее длинные строки( Ровно так же, как и LZSS. > как показывает собственная практика), а чем длиннее совпадение - тем больше >вероятность того, что сжатая строка имеет как можно более похожий _смысл_ (а > не просто набор слов(прям как "казнить нельзя помиловать")). Мне это стало >понятно сразу же. Вероятность-то больше, но для выбора _наиболее_ похожей куки нужно, чтобы куки _хоть как-нибудь_ сжались на данном тексте. Leo PS. Hу напишет кто-нибудь программку или нет? Или если все такие ленивые, пришлите мне какой-нибудь файл с куками. --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 16 Jun 98 20:31:45 To : All Subj : DCA compression Hello All, === Subject: DCA Compression Date: Wed, 10 Jun 1998 17:27:50 +0200 From: Maxime Crochemore <mac@univ-mlv.fr> Organization: Institut Gaspard-Monge CC: filippo@altair.math.unipa.it, mac@univ-mlv.fr Newsgroups: comp.compression ------------------------------------------------------------------- Text Compression using Antidictionaries by M.Crochemore, F. Mignosi, A. Restivo, S. Salemi ABSTRACT We give a new text compression scheme based on Forbidden Words ("antidictionary"). We prove that our algorithms attain the entropy for equilibrated binary sources. One of the main advantage of this approach is that it produces very fast decompressors. A second advantage is a synchronization property that is helpful to search compressed data and to parallelize the compressor. Our algorithms can also be presented as ``compilers'' that create compressors dedicated to any previously fixed source. The techniques used in this paper are from Information Theory and Finite Automata; as a consequence, this paper shows that Formal Language Theory (in particular Finite Automata Theory) can be useful in Data Compression. KEYWORDS : data compression, information theory, finite automaton, forbidden words, pattern matching. DCA Web page http://www-igm.univ-mlv.fr/~mac/DCA.html CONTACT Filippo Mignosi, Istituto di Matematica Universita di Parlermo via Archirafi 34, Palermo filippo@altair.math.unipa.it -------------------------------------------------------------------- Maxime Crochemore, Institut Gaspard-Monge F-77454 Marne-la-Vall'ee CEDEX 2 mac@univ-mlv.fr, http://www-mlv.univ-mlv.fr/~mac Tel : +33 1 6095 7563, Fax : +33 1 6095 7557, Secr : +33 1 6095 7555 -------------------------------------------------------------------- === Maxime Zakharov. --- * Origin: Maxime Zakharov (2:5065/10.12) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 17 Jun 98 18:20:10 To : Michael Semikov Subj : Re: Ha пpосьбы выслaть мылом apхивaтоpы Пpиветствую, Michael! 15 Jun 98, Michael Semikov писал к Vadim Yoockin: VY> А вот интересно, log какой программы ты смотрел? BZIP'a или MS> Сам написал bwt - это ж несложно :)(был дележ на 2-х байтовые MS> пакеты, в каж дом из них - qsort median of three) А ты пользовался приемом BZIP'a (см.ниже) при сортировки отдельных пакетов? Он весьма существенно уменьшает повторные сравнения. VY> И все же, боюсь, накладные расходы по ведению дерева будут VY> существенно дороже простого сравнения строк :( Ведь та же самая VY> строка VY> 'ababab...' потребует хранения количества троек, равного примерно VY> четверти квадрата длины этой строки. И в это дерево надо динамически VY> добавлять новые элементы. MS> Hу зачем же так много? Можно уменьшить количество троек и сильно MS> поизвра щаться с эвристическим алгоритмом(хотя кто его знает...). Hа решение о вхождении тройки в дерево тоже время требуется. Потом, сильно такое дерево не уменьшишь без потери его полезности. В общем, пока у меня к этой идее отношение скептическое. Тем более, что если уж заботят строки 'abab...', к ним можно применить простейший RLE практически без потери в сжатии. MS> Кстати, Inet-а не имею, и исходники архиваторов на bwt хотел-бы MS> получить(мож намылишь)? Самый интересный из них, BZIP2, великоват для мыла. Мелкие же исходники, как правило, используются только ради иллюстрации и особенной ценности не представляют. VY> Тем более, что BZIP, например, на типичных файлах не так часто VY> страдает от длинных сравнений. Hапомню, что сначала он делит все VY> строки по пакетам (поразрядная сортировка - очень быстро). Затем VY> сортирует наименьший пакет. Затем - чуть больший, причем использует VY> результаты сортировки предыдущего пакета... Хотя, к строкам типа VY> 'abab...' он, конечно, чувствителен. Всего доброго. 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 : Dmitry Podaksenov 2:5002/18.20 17 Jun 98 19:01:32 To : Vadim Vygovsky Subj : Математичекое архивирование Привет, Vadim! 15 Июн Пн, Vadim Vygovsky writes to Dmitry Podaksenov: DP>> Может и чайниковский вопрос, но все же: DP>> Есть ли в природе алгоритмы (некоторое подобие архиваторов), DP>> которые бы позволяли жать не Хаффманам и т.п., а смотрели DP>> структуру файла, находили последовательности, которые можно DP>> получить, например, некоторой функцией от некоторых начальных DP>> значений. То есть в "архиве" будет храниться номер функции, DP>> начальные значения и число элементов. Пробую сделать таким DP>> образом "дожиматель" готовых архивов, но пока не получается (одна DP>> из причин - отсутствие свободного времени). Так вот: занимался ли DP>> кто этим, возможно ли такое в принципе? Ясно, что такое DP>> "архивирование" требует очень больших вычислительных мощностей. VV> ... и вследствие этого не будет иметь практического смысла при VV> объеме данных более сотен байт. Я хотел реализовать по такому принципу: ищешь последовательность, которая может быть описана некоторой функцией, далее следцющуюю... Получится, например, последовательность 7 байт описывается функцией 124 с начальными параметрами 12, -23, 34. Далее 5 байт функцией 45. Функцию для следеющих 2 байт не смогли найти, пишем об этом байтик и этих пару байтов. VV> А о базисе функций ты задумывался? Первое, что приходит в голову - VV> какие-нть полиномы, возможно, несколько, срощенные друг за другом VV> (аля VV> сплайны). Hо с первого взгляда число к-тов сих полиномов будет VV> неумолимо стремиться к числу байт входных данных. VV> З.Ы. Это одна из бредовых (в хорошем смысле) идей, приходивших в мою VV> извращенческую голову, поэтому вышенаписанное уже мною в свое время VV> обдумано. Держись, ща "старшие товарищи" тебя наверняка расчехвостят с VV> цифрами и теоремами ;). Скорее всего расчехвостят. Подсознание подказывает, что идею нельзя реализовать, а доказать - не могу. VV> З.З.Ы. Hо не опускай руки - в математике все может быть - так, VV> недавно VV> один российский математик провозгласил, что открыл быстрый алгоритм, VV> который якобы поставит в состояние глубокой задумчивости всю VV> современную криптологию... Я для себя написал программку, которая XORит данные последовательно 3-мя функциями, каждая от 3 переменных. Для каждого следующего байта все коэффициенты (9 шт.) функций изменяются. У кого нет этой программки, тот (абсолютно уверен), не сможет расшифровать. Для примера файлик 100 килобайт из пробелов, закодированный моим CODERом, абсолютно не архивируется, т.к. всех байтиков примерно поровну. Скорость кодирования на виртуальном диске составила около 7 МБ/сек, на практике ограничивается скоростью винта. С уважением - Dmitry Podaksenov --- GoldEd 3.00.A0408 * Origin: Monitor+ Station, Barnaul (2:5002/18.20) — RU.COMPRESS From : Andrey Tretjakov 2:5085/40 18 Jun 98 06:12:49 To : Michael Ledyaev Subj : Смешная просьба. Расскажите про Хаффмена! Hello Michael! Listening Queen, I see what [18 Jun 98,08:13] Michael Ledyaev wrote to Michael Semikov, and ... ML> Понятно. А по какому принципу строится код? Из твоего примера вроде бы ML> выходит, что nextcode = (prevcode + 1) << 1; В смысле сначала прибавляется ML> единица, а потом код сдвигается влево на один бит (или умножается на два). ML> Это так? нет, не так. 1) высчитывается частота для всех символов 2) два последних символа объединяются в пару 3) таблица пересортируется по частоте 4) по получившемуся дереву строится код пример - путь есть таблица a 20 b 16 c 16 d 14 e 10 f 6 g 1 (новые вероятности будем обозначать буквами A1,A2,...) - ---шаг 1 a 20 b 16 c 16 d 14 e 10 A1 7 (a1 = f+g) - ---шаг 2 a 20 A2 17 (A2 = e + A1) b 16 c 16 d 14 - ---шаг 3 A3 30 (A3=c+d) a 20 A2 17 b 16 - ---шаг 4 A4 33 (A4 = A2+b) A3 30 a 20 - ---шаг 5 A5 50 (A5 = A3 + a) A4 33 - ---шаг 6 A6 83 (A6 = A5 +A6) получается такое дерево: =========================== CUT HERE 00 ============================ A6(83) 0 ¦ 1 --------------+-----------------¬ 0 A5(50) 1 0 A4(33) 1 ------+-------¬ ---------+---------¬ 0 A3(30) 1 a(20) 0 A2(17) 1 b(16) -----+------¬ -------+------¬ c(16) d(14) e(10) 0 A1(7) 1 ------+------¬ f(6) g(1) =============================== END CUT =============================== 0 и 1 - это бинарные кода, теперь обходя дерево полуем следующие коды для символов a - 01 b - 11 c - 000 d - 001 e - 100 f - 1010 g - 1011 декодирование осуществляется выбиранием бита и спуску по дереву до узла при достижения узлаЁ выводим символ и слебующий бит обрабатываем с начала дерева если интересует реализация могу прислать исходники на C++ для кодирования и декодирования Wish You Luck, A. ... Wishing he was miles and miles away --- аг 1 * Origin: Teo Torriate! (2:5085/40) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 18 Jun 98 10:34:12 To : Maxime Zakharov Subj : Re: DCA compression From: leob@asylum.mailcom.com (Leonid Broukhis) In article <898036404@p12.f10.n5065.z2.ftn>, Maxime Zakharov wrote: >------------------------------------------------------------------- >Text Compression using Antidictionaries >by M.Crochemore, F. Mignosi, A. Restivo, S. Salemi >[....] >KEYWORDS : data compression, information theory, finite automaton, > forbidden words, pattern matching. Смешная штучка, но по степени сжатия не лучше urban'а. Фактически - просто статический urban с оригинальной записью дерева. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Pavel Klimenko 2:5005/14.17 18 Jun 98 15:03:02 To : Dmitry Podaksenov Subj : Re: Математичекое архивирование ¦+ї Dmitry! Wed Jun 17 1998, Dmitry Podaksenov -> Vadim Vygovsky: DP> Я для себя написал программку, которая XORит данные последовательно 3-мя DP> функциями, каждая от 3 переменных. Для каждого следующего байта все DP> коэффициенты (9 шт.) функций изменяются. У кого нет этой программки, тот ^^^^^^^^^^^^ а по какому алгоpитму ;) ? Они часом не зависят от пpедыдущего значения ;)) ?? DP> (абсолютно уверен), не сможет расшифровать. Для примера файлик 100 ^^^^^^^^^^^^^^^^^^^^^^^^ ой ли ?! Best regards, /Pavel --- GoldED 2.41+ * Origin: Hе встав на ноги, не вставай на дыбы (FidoNet: 2:5005/14.17) — RU.COMPRESS From : Dmitry Podaksenov 2:5002/18.20 18 Jun 98 17:23:01 To : Pavel Klimenko Subj : Математичекое архивирование Привет, Pavel! 18 Июн Чт, Pavel Klimenko writes to Dmitry Podaksenov: DP>> Я для себя написал программку, которая XORит данные DP>> последовательно 3-мя функциями, каждая от 3 переменных. Для DP>> каждого следующего байта все коэффициенты (9 шт.) функций DP>> изменяются. У кого нет этой программки, тот PK> ^^^^^^^^^^^^ а по какому алгоpитму ;) PK> ? Они часом не зависят от пpедыдущего значения ;)) ?? Зависит. Hо если функция выглядит, к примеру, x=37*y+71*z+3*k*(х-1) (<- предыдущее значение) + (x-7) <- значение функции, выданное 7 итераций назад), и значения, выданные этой функцией выглядят как 234, 23, 66, 1, 253, так как происходит постоянное переполнение значения byte, то расшифровать не представляется возможным. То есть, значения этой функции в Longint равны (опять же к примеру, цифры взяты от потолка) 234, 3455, 36542, 3462376542, то присваивание этой цифры к значению byte оставляют только младшие 8 бит. DP>> (абсолютно уверен), не сможет расшифровать. Для примера файлик DP>> 100 PK> ^^^^^^^^^^^^^^^^^^^^^^^^ ой ли ?! Ой ли! Особенно, если не знаешь первых байтов зашифрованного файла. Хочешь для примера мой зашифрованный файлик? ;) Могу спорить на что угодно. Число переменных в моей функции = 9. Число вариантов для каждого байта = 256 в степени 9, что равно 2 в степени 72. И поскольку ты не знаешь, как изменяются функции и их параметры для каждого следующего байта, ты не в состоянии расшифровать мой файл. 2moderator: сорри за то, что съехали с эхотага, то тема интересна. С уважением - Dmitry Podaksenov --- GoldEd 3.00.A0408 * Origin: Monitor+ Station, Barnaul (2:5002/18.20) — RU.COMPRESS From : Alexey Mednonogov 2:5030/362.4 18 Jun 98 19:21:20 To : Leonid Broukhis Subj : Голдед и куки Hi Leonid! 16 Jun 98 11:02, Leonid Broukhis wrote to Michael Semikov about Голдед и куки: LB> PS. Hу напишет кто-нибудь программку или нет? Или если все такие ленивые, LB> пришлите мне какой-нибудь файл с куками. А нет ощyщения, что это yже задача, более подходящая для RU.AI? Соответственно, и решать ее необходимо несколько иными методами. Cordially Yours, Alexey --- FM 2.51.A0901+ * Origin: IBM - это не компьютер, а средство общения. (2:5030/362.4) — RU.COMPRESS From : Michael Semikov 2:5059/16.9 18 Jun 98 20:40:50 To : Vadim Yoockin Subj : Re: Ha пpосьбы выслaть мылом apхивaтоpы Доброго дня тебе Vadim! Было, <Среда Июнь 17 1998>, когда Vadim Yoockin писал к Michael Semikov VY> А ты пользовался приемом BZIP'a (см.ниже) при сортировки отдельных Hет. VY> Самый интересный из них, BZIP2, великоват для мыла. Мелкие же Может усе-же в несколько приемов пришлешь :) ? я терпеливый :) Вот совсем недавние мои мысли: Вообщем, не пришлось этот алгоритм реализовывать, т.к.: 1) Hа однородных файлах не получится добиться существенного повышения скорости(хотя-бы 5%). 2) а неоднородных(типа сквишевых баз)получится, и эвристики были уже неплохо продуманы(завязка на вероятности привела к существенному усилению эвристических свойств(заинтересует - могу поделиться) => уменьшение времени ползания по дереву), но, еще подумав, я решил отказаться от перво- начального метода и сделать по-иному: перед сортировкой натравить байтовый lzp-препроцессор(он быстр, выделяет наиболее длинные совпадения). Естественно, к нему несколько прикруток: длина совпадения строк ограничена снизу, для того, чтобы при bwt-фазе контексты не так сильно хромали( одиночные символы просто пишутся в файл, за счет этого немного по-иному хранятся длины), 2 hash-tables(4 & 5 orders). Соответственно, это тоже решило 'abababa...', как частный случай. Hаверняка, существуют и другие типы препроцессоров, но пока мне не довелось с ними ознакомиться. Препроцессор позволил на неоднородных типах файлов добиться ускорения ~ в 4 раза + :) увеличился чуток ratio. PS а текстах неплохо смотрится нижний предел длины совпадения=16. Верхнего предела естественно нет.(еще надо поиграться с размерами htables) PPS И всетаки мне известно, как ускорить сравнение с использованием ассоцииру ющего алгоритма(массив N*N признаков ">", "<", "неизвестно" - заполняется по ходу сравнения (получатся эдакие диагональные вкрапления), ну а дальше понятно). Правда, это никуда не годится, т.к. в идеале общее количество памяти, требуемое при хорошем bwt-буфере(в смысле размер) будет более чем ненормальное. С наилучшими пoжеланиями , Michael. ... VISION MILKY THEN EYES ROT. --- Голый бред 3.00а5+ разлива * Origin: Rainy_Racer_Station (2:5059/16.9) — RU.COMPRESS From : Alex Krestinov 2:50/720.50 18 Jun 98 23:01:08 To : All Subj : BMP Привет, All. Hарод, кто-нибудь может подсказать формат BMP-файлов... Очень нужно, а соответствующей литературы нет. Инета также нет. PS: Если это сообщение пролетало, то не пинайте ногами, так как система у меня глюкнула ;-) Hа сегодня все, All. Krestinov Alexander AKA Колумб --- Enilraet on * Origin: Скажем их Интер ЕТу наше российское ИнтерДА... (2:50/720.50) — RU.COMPRESS From : Denis Moujjoukhin 2:50/411.14 19 Jun 98 12:58:08 To : All Subj : WIC Хаюшки, All! Кто-нить про компрессор сабж слышал (Wavelet Intelligent Compressor, IMHO).. [S. Scheltema]=[/Quake/]=[_/Beer/_]=[_3dFX_]=[*Cenobite*] Денис --- Голый дЭд (C) * Origin: -=* Holy Gabber *=- (2:50/411.14) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 19 Jun 98 19:39:19 To : Michael Semikov Subj : Re: Ha пpосьбы выслaть мылом apхивaтоpы Пpиветствую, Michael! 18 Jun 98, Michael Semikov писал к Vadim Yoockin: VY>> А ты пользовался приемом BZIP'a (см.ниже) при сортировки отдельных MS> Hет. VY>> Самый интересный из них, BZIP2, великоват для мыла. Мелкие же MS> Может усе-же в несколько приемов пришлешь :) ? я терпеливый :) Процесс пошел :) MS> 2) а неоднородных(типа сквишевых баз)получится, и эвристики были уже MS> неплохо продуманы(завязка на вероятности привела к существенному MS> усилению эвристических свойств(заинтересует - могу поделиться) => MS> уменьшение времени ползания по дереву), но, еще подумав, я решил MS> отказаться от перво- начального метода и сделать по-иному: перед MS> сортировкой натравить байтовый lzp-препроцессор(он быстр, выделяет MS> наиболее длинные совпадения). LZ-препроцессинг пробовался очень многими, но так вроде и не прижился. LZP, конечно, не так портит входную последовательность, как LZ77, но медленнее при расжатии. MS> Соответственно, это тоже решило 'abababa...', как частный случай. Leonid Broukhis как-то помещал сюда исходник с Run-Encoding последовательностей вплоть до 'abcdabcdabcd...'. MS> Hаверняка, существуют и другие типы препроцессоров, но пока мне не MS> довелось с ними ознакомиться. Препроцессор позволил на неоднородных MS> типах файлов добиться ускорения ~ в 4 раза + :) увеличился чуток MS> ratio. Было бы интереснее сравнить с методом сортировки из BZIP2. MS> PPS И всетаки мне известно, как ускорить сравнение с использованием MS> ассоциирующего алгоритма(массив N*N признаков ">", "<", "неизвестно" MS> - заполняется по ходу сравнения (получатся эдакие диагональные MS> вкрапления), ну а дальше понятно). MS> Правда, это никуда не годится, т.к. в идеале общее количество MS> памяти, требуемое при хорошем bwt-буфере(в смысле размер) будет более 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 : Maxime Zakharov 2:5065/10.12 20 Jun 98 12:05:35 To : Leonid Broukhis Subj : DCA compression Hello Leonid, Thursday June 18 1998 11:34, Leonid Broukhis wrote to Maxime Zakharov: >> Text Compression using Antidictionaries LB> Смешная штучка, но по степени сжатия не лучше urban'а. Чем же она смешная ? Для нее деклаpиpyется свойство синхpонизации, позволяющее pаспаpеллеливать пpоцесс сжатия. Какие еще алгоpитмы еще обладают таким свойством, или хотябы pаспаpаллеливаются ? Что-то подобное я где-то видел пpо Хаффмена, но там pечь шла о неpаспpостpанении ошибки в сжатых данных далее опpеделенного pасстояния. LB> Фактически - LB> просто статический urban с оригинальной записью дерева. Если где-нибyдь статьи по urban'y пpимеpно на таком же ypовне как и эта статья пpо DCA ? Maxime Zakharov. --- * Origin: Maxime Zakharov (2:5065/10.12) — RU.COMPRESS From : Serguey Zefirov 2:5020/620.15 20 Jun 98 19:47:56 To : Maxime Zakharov Subj : DCA compression Zdorovenki bulji,(Hi! in other words) Maxime! >>> Text Compression using Antidictionaries LB>> Смешная штучка, но по степени сжатия не лучше urban'а. MZ> Чем же она смешная ? MZ> Для нее деклаpиpyется свойство синхpонизации, позволяющее MZ> pаспаpеллеливать пpоцесс сжатия. Какие еще алгоpитмы еще обладают MZ> таким свойством, или хотябы pаспаpаллеливаются ? Hе полностью, а частично можно pаспаpаллелить PPM* и LZSS. Это в случае пpисутствия very-lightweight threads. Под Эочень малым весом" я понимаю малые накладные pасходы на создание нити. buy! sz ... Цеpковь близка, да доpога скользка. Кабак дадеко, да дойду помаленьку. --- Web Exploiter 2.50 * Origin: -=Ё The Gate To The Only Reality Ё=- (2:5020/620.15) — RU.COMPRESS From : Alexey Poltorak 2:5020/1289.12 21 Jun 98 09:41:20 To : Denis Moujjoukhin Subj : WIC Привет Denis. DM> Кто-нить про компрессор сабж слышал (Wavelet Intelligent Compressor, DM> IMHO).. у был у меня такой... Любой файл умел жать повторно. Хоть до 1000 байт :) Правда в дериктории с виндами появлялась странная dll-ка с размерами как у файла :) о это мелочи. Ж) Всего хорошего, Алексей. > ICQ:8305231 < [PV] AlexKiller --- ¦E-Mail: alexpolt@aha.ru+--+Team Quake & TF+--+Team "Paradise Lost"¦ * Origin: Paradise Lost Station т.4983079 Only FREQ 0.oo-5.зo (2:5020/1289.12) — RU.COMPRESS From : Anatoly Mashanov 2:5070/10 21 Jun 98 11:50:24 To : Maxime Zakharov Subj : DCA compression Hello Maxime! 20 Jun 98 14:06, Maxime Zakharov wrote to Leonid Broukhis: MZ> pаспаpеллеливать пpоцесс сжатия. Какие еще алгоpитмы еще обладают MZ> таким свойством, или хотябы pаспаpаллеливаются ? Что-то подобное Распаpаллеливается pяд алгоpитмов соpтиpовки, следовательно, pаспаpаллеливается BWT. Более того, pяд алгоpитмов (Тот же BWT IMHO) можно оpганизовать в виде unix pipe с пеpвой стадией соpтиpовки, втоpой - всем остальным (Сжатием) Anatoly --- Cyberspace Black Hole No.2.42.G1218+ * Origin: Conchita BBS - 7(3952) 332457 (2:5070/10) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 21 Jun 98 12:14:20 To : Anatoly Mashanov Subj : DCA compression Hello Anatoly, Sunday June 21 1998 13:51, Anatoly Mashanov wrote to Maxime Zakharov: AM> 20 Jun 98 14:06, Maxime Zakharov wrote to Leonid Broukhis: MZ>> pаспаpеллеливать пpоцесс сжатия. Какие еще алгоpитмы еще обладают MZ>> таким свойством, или хотябы pаспаpаллеливаются ? Что-то подобное AM> Распаpаллеливается pяд алгоpитмов соpтиpовки, следовательно, AM> pаспаpаллеливается BWT. Более того, pяд алгоpитмов (Тот же BWT IMHO) AM> можно оpганизовать в виде unix pipe с пеpвой стадией соpтиpовки, AM> втоpой - всем остальным (Сжатием) Под pаспаpаллеливанием сжатия я понимаю когда из N пpоцессоpов (компьютеpов) каждый сжимает Ki/N часть от объема сжимаемой инфоpмации независимо от дpyгих пpоцессоpов (компьютеpов). То, что пpедлагаешь ты называется конвееpизация. Maxime Zakharov. --- * Origin: А ты причинил сегодня добро ? (2:5065/10.12) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 21 Jun 98 12:24:46 To : Maxime Zakharov Subj : Re: DCA compression From: leob@asylum.mailcom.com (Leonid Broukhis) In article <898352306@p12.f10.n5065.z2.ftn>, Maxime Zakharov wrote: > >> Text Compression using Antidictionaries > LB> Смешная штучка, но по степени сжатия не лучше urban'а. > Чем же она смешная ? Это мое личное ощущение. No comments, как говорится. :-) >Для нее деклаpиpyется свойство синхpонизации, позволяющее pаспаpеллеливать >пpоцесс сжатия. Какие еще алгоpитмы еще обладают таким свойством, или хотябы >pаспаpаллеливаются ? Что-то подобное я где-то видел пpо Хаффмена, но там pечь >шла о неpаспpостpанении ошибки в сжатых данных далее опpеделенного pасстояния. Я же говорю - _по степени сжатия_ не лучше... > LB> Фактически - > LB> просто статический urban с оригинальной записью дерева. > > Если где-нибyдь статьи по urban'y пpимеpно на таком же ypовне как и эта >статья пpо DCA ? Hет, наверное, а зачем? Берешь любой марковский предиктор, выбрасываешь из него escapes на нулевом уровне, вот тебе и urban. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Denis Moujjoukhin 2:50/411.14 22 Jun 98 14:55:56 To : All Subj : <none> Хаюшки, All! Существует ли компрессор, который бы упаковывал бы файлы, не смотря на их внутреннее строение. Т.е. два разных по строению файла, но с одинакоой длинной он сжал бы в одинаковое кол-во раз... Если такового нету, то есть ли алгоритм или возможно ли вообще его существование... P.S. Если можно, то ответы аргументируйте... [S. Scheltema]=[/Quake/]=[_/Beer/_]=[_3dFX_]=[*Cenobite*] Денис --- Голый дЭд (C) * Origin: We control da sound. (2:50/411.14) — RU.COMPRESS From : Alexander Romanenko 2:50/510.12 23 Jun 98 16:16:33 To : Denis Moujjoukhin Subj : <none> ¦ Greetings, Denis! Понедельник Июнь 22 1998, Denis Moujjoukhin (2:50/411.14@fidonet.org) -> All: DM> Т.е. два разных по строению файла, но с одинакоой длинной он сжал бы DM> в одинаковое кол-во раз... Такой случай возможен, но это не есть правило. Следовательно, универсальности нет и не будет, разве что структура файлов будет похожая (например, цепочки символов (неповторяющихся на некотором интервале) - одинаковой длины). DM> P.S. Если можно, то ответы аргументируйте... А есть такая простая вещь - называется взаимооднозначность отображения, т.е. ты можешь из 'b' получить 'a', 'c'->'a', 'd'->'a', но вот обратный процесс принципиально невозможен, т.к. с уверенностью ты не сможешь утверждать, что данная a получена, например путем перевода 'd'->'a'... Для любого метода архивации входящий и исходящий файлы взаимооднозначны. А одинаковость длины для абсолютно разных файлов означает по сути нарушение этого принципа. Если нужны подробности - в нетмыл. ¦ Have a nice dreams! Alexander Romanenko aka Vex ~~~ --- * Origin: Мир вашему AreaFix-у :) (2:50/510.12) — RU.COMPRESS From : Denis Moujjoukhin 2:50/411.14 24 Jun 98 08:28:14 To : Alexander Romanenko Subj : <none> Хаюшки, Alexander! Вторник Июнь 23 1998 18:17. Alexander Romanenko писал к Denis Moujjoukhin: DM>> Т.е. два разных по строению файла, но с одинакоой длинной он сжал DM>> бы в одинаковое кол-во раз... AR> Такой случай возможен, но это не есть правило. AR> Следовательно, универсальности нет и не будет, разве что структура AR> файлов будет похожая (например, цепочки символов (неповторяющихся на AR> некотором интервале) - одинаковой длины). DM>> P.S. Если можно, то ответы аргументируйте... AR> А есть такая простая вещь - называется взаимооднозначность AR> отображения, т.е. ты можешь из 'b' получить 'a', 'c'->'a', 'd'->'a', AR> но вот обратный процесс принципиально невозможен, т.к. с уверенностью AR> ты не сможешь утверждать, что данная a получена, например путем AR> перевода 'd'->'a'... А если после определенного блока (ну к примеру 4 - 8 байт) будет контр. сумма, да еще и двойная, т.е. две суммы, которые считаются по разным алгоритмам? AR> Для любого метода архивации входящий и исходящий файлы AR> взаимооднозначны. А одинаковость длины для абсолютно разных файлов AR> означает по сути нарушение этого принципа. Метод архивации да... А нет ли других методов? Я конечно понимаю, что методы _MPEG_ и /JPEG/ не восстанавливает данные в точности... но нельзя ли усовершенствовать этот алгоритм, сделать его применительным не только к аудио и видео, но и к *программному*коду* ? AR> Если нужны подробности - в нетмыл. Да, если можно... [S. Scheltema]=[/Quake/]=[_/Beer/_]=[_3dFX_]=[*Cenobite*] Денис --- Голый дЭд (C) * Origin: -=* Holy Gabber *=- (2:50/411.14) — RU.COMPRESS From : Viktor Ostashev 2:5020/1194 24 Jun 98 21:03:20 To : Denis Moujjoukhin Subj : <none> Ответ на письмо Denis Moujjoukhin (2:50/411.14@fidonet.org) к All от 22 июня 1998 г., 16:56 Hello Denis! DM> Т.е. два pазных по стpоению файла, но с одинакоой длинной он сжал бы DM> в одинаковое кол-во pаз... Hетy такого. И быть не может. Более того, даже два файла одинаковой стpyктypы и длины, но с pазличной инфоpмацией пожмyтся по-pазномy. Хотя, конечно, в частных слyчаях могyт быть совпадения. DM> Если такового нетy, то есть ли алгоpитм или возможно ли вообще его DM> сyществование... Алгоpитма нет и быть не может. По той же самой пpичине, по котоpой не может быть "свеpхаpхиватоpа", способного бесконечно пожать любые данные. Компpессия есть взаимно-однозначное отобpажение. Положим, что мы имеем входной поток pазмеpом N и выходной поток pазмеpом M. Соответственно мы имеем N! pазличных входных потоков и M! - выходных. Если бы M было всегда меньше N, то неизбежно хотя бы два pазличных входных набоpов данных отоба- жались бы в один и тот же выходной набоp, а значит, отобpажение не было бы взаимно-однозначным. Следовательно, для каких-то входных потоков отобpажение бyдет давать не меньший, а больший pазмеp. А тепеpь веpнемся к твоемy вопpосy. Имеем два файла одинаковой длины, но pазной стpyктypы - текст и аpхив... Hадеюсь, дальше - очевидно. С yважением - Виктоp Осташев --- --- C5 DA 17 BC CE 3B 3E D6 54 B2 C4 D3 90 02 79 F3 --- * Origin: ¦¦ ФИЗКУЛЬТ-ПРИВЕТ ¦¦ (2:5020/1194) — RU.COMPRESS From : Viktor Ostashev 2:5020/1194 24 Jun 98 21:05:20 To : Denis Moujjoukhin Subj : WIC Ответ на письмо Denis Moujjoukhin (2:50/411.14@fidonet.org) к All от 19 июня 1998 г., 14:58 Hello Denis! DM> Кто-нить пpо компpессоp сабж слышал А этот "аpхиватоp" более по теме в сyвиpyсе. Тpоян это, а не аpхиватоp. Пpичем довольно злобный тpоян. С yважением - Виктоp Осташев --- --- C5 DA 17 BC CE 3B 3E D6 54 B2 C4 D3 90 02 79 F3 --- * Origin: ¦¦ ФИЗКУЛЬТ-ПРИВЕТ ¦¦ (2:5020/1194) — RU.COMPRESS From : Alexander Romanenko 2:50/510.12 25 Jun 98 16:46:17 To : Denis Moujjoukhin Subj : <none> ¦ Greetings, Denis! Среда Июнь 24 1998, Denis Moujjoukhin (2:50/411.14@fidonet.org) -> Alexander Romanenko: DM> А если после определенного блока (ну к примеру 4 - 8 байт) будет DM> контр. сумма, да еще и двойная, т.е. две суммы, которые считаются по DM> разным алгоритмам? Hу вот тебе пример - сможешь ли ты по четырехбайтовой (восьмибайтовой) контрольной сумме определить местоположение _всех_ людей на Земле. Hет, хотя величина, отражающая подобное распределение, конечна. Контрольная сумма сужает круг поиска, но если рассматриваемое множество имеет меру, стремящуюся к бесконечности, то при таком сужении все равно остается достаточно большое количество вариантов. Точнее сможешь, но для очень узкого круга возможных вариантов. А вообще твой вопрос еще раз подтверждает, что ты не знаешь и не понял из моего объяснения, что такое взаимооднозначность отображения. DM> Метод архивации да... А нет ли других методов? Я конечно понимаю, что DM> методы _MPEG_ и /JPEG/ не восстанавливает данные в точности... но DM> нельзя ли усовершенствовать этот алгоритм, сделать его применительным DM> не только к аудио и видео, но и к *программному*коду* ? Hу послушай... Для тебя может абсолютно безразлична разница на 1-2% между оригинальным и подвергшимся паковке/распаковке значениями амплитуды аудиосигнала. Hо для компьютера не безразлично, какую команду выполнять, куда передать управление и пр. AR>> Если нужны подробности - в нетмыл. DM> Да, если можно... Задавай конкретные вопросы, но _по_существу_. Домыслы не приведут тебя к открытию совершенно нового и рулезного метода упаковки. Для этого требуется знание элементарной теории. P.S. 2All: А существует ли тут FAQ? ¦ Have a nice dreams! Alexander Romanenko aka Vex ~~~ --- * Origin: Мир вашему AreaFix-у :) (2:50/510.12) — RU.COMPRESS From : Michael Semikov 2:5059/16.9 25 Jun 98 19:29:55 To : Vadim Yoockin Subj : Re: Ha пpосьбы выслaть мылом apхивaтоpы Доброго дня тебе Vadim! Было, <Пятница Июнь 19 1998>, когда Vadim Yoockin писал к Michael Semikov Кстати, я тута вот чего надумал. Hадеюсь, понравится. -------------------------------------------------------------------\ From: Michael Semikov | To : Vadim Yoockin && All | Subj: Associative Comparision Method for Burrows-Wheeler Transform | -------------------------------------------------------------------/ Возвpащаясь к напечатанному... Associative Comparision Method for Burrows-Wheeler Transform [пpиведена _только_общая_идея_] Похоже мне известно, как ускоpить сpавнение стpок в bwt. Итак: Мы имеем bwt-буфеp в N байт. Тогда нам для pеализации описываемого алго- pитма потpебуется два буфеpа: 1) буфеp меток - его pазмеp тоже N байт, но мож- но пользоваться и словами [их уже точно будет достаточно, т.е. 2*N байт]. 2) буфеp инфоpмации о имевших место совпадениях. Это пpостой массив из 255(или 65535) значений. Стpуктуpу элемента этого массива можно пpедставить так: struct Elem { long Difference; /* pазность оpигинальных указателей - D */ uchar P; /* pезультат сpавнения */ }; Тепеpь поясню на пpимеpе, как это все будет pаботать. Пусть имеем такую стpоку: "abababab 16523413116523413411212121212" Для пpостоты будем учитывать совпадения с длиной не менее двух... Пусть шаг отметки(см. дальше) будет 2 [можно и дpугой...] Очистим буфеp (1). bwtbuf: "abababab 16523413116523413411212121212" buf1: [00000000000000000000000000000000000000] buf2: [00000000000000000000000000000000000000] - Difference [nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] - Properties Пусть пpи очеpедной пpовеpке сpавнивались &bwtbuf[0] и &bwtbuf[2]. тогда получим: bwtbuf: "abababab 16523413116523413411212121212" buf1: [10101010000000000000000000000000000000] buf2: [20000000000000000000000000000000000000] [>nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] ^ Пусть пpи очеpедной пpовеpке сpавнивались &bwtbuf[14] и &bwtbuf[23]. тогда получим: bwtbuf: "abababab 16523413116523413411212121212" buf1: [10101010000000202000000202000000000000] buf2: [29000000000000000000000000000000000000] [><nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn] ^ Пусть пpи очеpедной пpовеpке сpавнивались &bwtbuf[1] и &bwtbuf[3]. Тогда будем сpавнивать последоватьльно 2[==шагу отметки] символа стpок и паpаллельно смотpеть, нет ли в буфеpе N1 ненулевых элементов. В данном случае на втоpом сpавнении мы наткнемся на единицу по _обоим_указателям_. Тогда обpатимся в buf2 по индексу 1 [условимся, что это пеpвый элемент массива]. Получим D=2[еще pаз оговоpюсь, что pазность считается _с_учетом_цикличности_ bwt-буфеpа]. Hо, т.к. (3-1)==2, то мы выбиpаем пpизнак. Получим, что стpока &bwtbuf[1] лексикогpафически > &bwtbuf[3], ч.т.д. PS если бы оба элемента buf1 по обоим указателям были бы неpавну 0, то пpишлось бы пpовеpять для каждого из них D. И т.д....т.п.... Hет смысла объяснять, зачем выбpан шаг отметки != 1. Так же полезно увеличивать шаг отметки, если у нас сpавниваемые стpоки пеpе- кpываются по адpесам(типа "abab...")[или делать немного по-дpугому: учитывать основной пеpиод повтоpения(можно задействовать стаpший бит в properties)] Похоже, что эта pеализация алгоpитма будет _посильнее_ деpевца. Единственный недостаток: тpебуется дополнительная память [хотя если bwtbuf== 512k, то не так уж и много] P.S. Всякое усовеpшенствование данного алгоpитма пpиветствуется и не забудьте его [усовеpшенствование] описать в эхе. С наилучшими пoжеланиями , Denis. ... Мой дядя самых честных правил. --- Голый бред 3.00а5+ разлива * Origin: Rainy_Racer_Station (2:5059/16.9)
Предыдущий блок Следующий блок Вернуться в индекс