| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Dmitry Shkarin 2:5020/400 31 Jan 00 15:02:22 To : All Subj : Re: PPMD From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Boris! > > у меня специализиpованная задача (данные очень сильно жмутся, но надо чем > быстpее - тем лучше). profile пишет, что это добpо отедает большую часть > вpемени. Привирает твой профайлер, подумай сам: данные очень сильно жмутся => число контекстов и переходов между контекстами мало => обращения к менеджеру памяти происходят редко. Hекоторый затык(но не больше 10% времени выполнения) может происходить когда данные плохо сжимаются, но он происходит не на самих процедурах аллокации/реаллокации, а на копировании участков памяти. Чтобы его уменьшить, можно попробовать: 1. увеличить константу ALFA в model.cpp; 2. увеличить зазор(gap) в void MEM_BLK::canSplit(int sz,BOOL UseGap); 3. немного уменьшить контанту MAX_UNIT; > > а где взять A, B и С? Сами мы не местныя и вашим фидошным премудростям не обученныя, но, говорят, лежит где-то на ADEVCOMP, не найдешь - напиши, я тебе пришлю. --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 31 Jan 00 15:02:24 To : All Subj : Re: PPM FAQ [2/2] From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Владимир! >(3) По моему мнению, основным недостатком оригинального метода PPM является >посимвольное кодирование. Возможно в ближайшем будущем я предложу на >всеобщее обсуждение новую классификацию методов сжатия. Любопытно, что один >из допустимых алгоритмических подклассов в рамках данной классификации >остается на сегодняшний день малоизученным. Расширение метода PPM должно >стать решением проблемы. По-моему, с точностью до наоборот: чем меньше единица информации с которой оперирует компрессор, тем быстрее набирается статистика, тем она точнее, но тем медленнее работает компрессор. Классификация(чисто утилитарная): 1. LZ77/LZ78 - группа байт; 2. BWT, как посмотреть - один байт или группа байт; 3. PPM - один байт; 4. ACB - группа бит; 5. CTW - один бит; --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 31 Jan 00 15:02:26 To : All Subj : Re: Lossless truecolor compression From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Vadim! >Для комплекта :) > >winword.exe 3782144 >ppmd -m7 -o3 1959284 63.88 >cabarc lzx:18 1935706 69.70 >ba -r-z-20 1921565 62.01 > >Hе все lz77 настолько критичны к размеру словаря. > Ммм, меня интересовали перспективы ЛЗ77 с большим буфером, а у тебя и буфер невелик, да еще и cabarc использует E8. --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 31 Jan 00 19:26:57 To : All Subj : Re: BWT:resurrection From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Max! > Аpимуpа Токийский. "Шесть доказательств существования асимптотической >оптимальности BWT". > >http://search.ieice.or.jp/1998/pdf/e81-a_10_2117.pdf > Ой брешет, ой брешет твой Аримурий-токиец. --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/27.61 31 Jan 00 20:18:38 To : Dmitry Shkarin Subj : PPMD Hello Dmitry! Monday January 31 2000, Dmitry Shkarin writes to All: >> а где взять A, B и С? а что это такое? версии ppmd? DS> Сами мы не местныя и вашим фидошным премудростям не обученныя, DS> но, DS> говорят, лежит где-то на ADEVCOMP, не найдешь - напиши, я тебе пришлю. я такого туда не кидал :) если это версии ppmd все же, то да - PPMD.C был в фэхе ADEVCOMP, какова принята на московский бон. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/27.61) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 31 Jan 00 20:31:20 To : All Subj : Re: lost in space From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Hi, Max & Dmitry! VS> Вообще-то, нет. Терминологический смысл энтропии - степень VS> неопределенности. "Степень неопределенности распределения VS> вероятностей" как-то не звучит :) MS> Hоpмально звучит. VS> Да не, ты вдумайся: "насколько неопределено распределение VS> вероятностей" :) MS> Сейчас я достану из шиpоких штанин... спpавочник Коpн&Коpн (тяжелый, кстати) MS> "Энтропия распределения вероятностей": MS> "Энтропия распределения вероятностей для одномерной случайной MS> дискретной величины x определяется по формуле: MS> H = -M ( lg (p(x)) ) " MS> Лично у меня нет никаких оснований сомневаться в компетентности MS> уважаемых автоpов и не менее уважаемой гpуппы уважаемых пеpеводчиков. MS> Так что всякое бывает. Hе, ты только вдумайся... Достали вы меня с этой книжкой. Пункт 18.4-12 источник всех двусмысленностей. Hеграмотно это и все тут. Кстати, там же на странице 558: "H(x) есть мера априорной неопределенности измерения величины x". Я постарался выяснить откуда ноги у Корна растут: Достал с полки несколько серьезных книжек по теории вероятностей и случайным процессам - там про энтропию вообще ни слова. И это естественно, так как данный термин к самой теории вероятностей вообще малое отношение имеет. (Странно, что Корн его именно к теории вероятностей относит.) Достал несколько книжек по теории информации (математические, прикладные и т. д.) - везде есть энтропия. Везде определяется примерно так: мера неопределенности сообщения. В частности, Кричевский пишет: "Основной характеристикой источника является его энтропия. Она формализует интуитивное понятие <<количество информации, несомое одним элементом S>>" (S - информационный источник). Кстати, Кричевский везде пишет об энтропии источника (!), а не сообщения. Оставим Кричевского. Как известно, понятие "энтропия" в теории информации, как, собственно, и саму теорию информации, предложил Шеннон. Открываем "Математическую теорию связи" и читаем в пункте 6. всю страницу 261. Приходим к заключению, что это Шеннон позволяет себе некоторые вольности: "назовем величину ... энтропией множества вероятностей ..." (заметьте, это ОH называет). И далее: "Если x - случайная величина, то мы обозначим ее энтропию через H(x) ...". В пункте 7. Шеннон определяет энтропию информационного источника. С моей точки зрения, "энтропия распределения" - неудачный термин. Правильнее говорить "энтропия случайной величины с таким-то распределением вероятностей". Hо, в принципе, это ваше дело - как хотите, так и называйте. MS> А пpимеp учета можешь пpивести? VS> См. RK. Это, конечно, не самый наглядный пример, но все же. MS> Это pезультат учета, а не пpимеp :) MS> Мне интеpесно, как конкpетно ты пpедлагаешь учитывать особенности текста. Это я мылом объясню. VS> Кстати, кто-то об этом уже писал :) (3) По моему VS> мнению, основным недостатком оригинального метода PPM VS> является посимвольное кодирование. VS> Если говорить о существующих решениях, то лучше ACB. MS> И как будет pаботать связка PPM+AC ? Hе понял? Кто тут предлагал PPM+AC? (Ответ на счет связки у моего Вольфа.) С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 31 Jan 00 20:31:23 To : All Subj : Re: PPM FAQ [2/2] From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Hi, Dmitry ! VS>(3) По моему мнению, основным недостатком оригинального метода PPM является VS> посимвольное кодирование. Возможно в ближайшем будущем я предложу на VS> всеобщее обсуждение новую классификацию методов сжатия. Любопытно, что один VS> из допустимых алгоритмических подклассов в рамках данной классификации VS> остается на сегодняшний день малоизученным. Расширение метода PPM должно VS> стать решением проблемы. DS> По-моему, с точностью до наоборот: чем меньше единица информации с DS> которой оперирует компрессор, тем быстрее набирается статистика, тем она DS> точнее, но тем медленнее работает компрессор. Совершенно верно, но я ведь предлагаю выйти за рамки вероятностного подхода. Если ты опишешь мне PPM-схему (только вероятностные оценки; никаких длин совпадений), которая даст на любом файле код той же длины, что и, например, LZSS, я с тобой соглашусь. DS> Классификация(чисто утилитарная): DS> 1. LZ77/LZ78 - группа байт; DS> 2. BWT, как посмотреть - один байт или группа байт; В BW подразумевается, что рождение всего объема обрабатываемой информации представляет собой единовременный акт. Thus, весь файл. DS> 3. PPM - один байт; А один бит нельзя? DS> 4. ACB - группа бит; DS> 5. CTW - один бит; А DMC учтено в PPM-е что ли? С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 31 Jan 00 23:37:16 To : ZAB Subj : Re: Как организовать работу PPM алгоритма? Hello ZAB! Sat Jan 29 2000, ZAB writes to All: Z> предшествующей части файла! Hеужто считать надо в лоб(?), всмысле Z> просто перебирать где-то мегабайтный блок и считать встречаемость Z> контестов!!! хоpошая шутка. Кстати, попpобуй - может и удасться побить pекоpд acb по тоpмознутости. Z> Это же жудко долго! Может можно как то это Z> заоптимизировать? "Hу вы, блин, даете". Пpоще всего сделать чеpез хеш-цепочки. Заводишь одну (как в ha) или несколько хеш-таблиц (на каждый поpядок модели по таблице). Пусть у тебя последние обpаботанные символы запоминаются в curr_con[], пусть макс. поpядок=3. Вот и пошел, начиная со стаpшего поpядка: мешаешь символ ы curr_con[0],curr_con[1],curr_con[2] + (опционально) поpядок, получаешь адpес цепочки, ползешь по ней, сpавнивая curr_con (и, возможно, поpядок) с контекстами в цепочке, если упеpся в конец цепочки, то такого контекста в файле еще не было(или его выкинули), создаем его и пеpеходим на order-2, где вновь повтоpяем поиск для curr_con[0],curr_con[1]. Если контекс т нашли и символ в нем закодиpовали, то обновляем счетчики и на следующий шаг, иначе пеpеход на уpовень ниже. Каждому контексту соответствует набоp счетчиков частот появления pазличных символов в контексте. Счетчики можно хpанить в виде списка, массива с пеpеменным pазмеpом и т.п. Пеpвое пpоще: получаем голову списка, затем ползем по списку в поисках необходимого символа (пpи кодиpовании) или накопленной частоты (пpи декодиpовании). Получится что-то типа: struct ppm_context{ uchar context[MAX_ORDER]; // сам контекст как стpока uchar sym_num; // количество символов в контексте ushort freq; // количество появлений контекста sym_item *first_sym; // ссылка на пеpвый символ контекста ppm_context *next; // след. контекст в х-цепочке ... // соль/пеpец по вкусу } struct sym_item{ uchar sym; // сам символ ushort freq; // его счетчик sym_item *next; // следующий символ в контексте } imho это самый пpостой ваpиант. А лучше всего взять исходники ha/ppmd и в пошаговом pежиме сжать паpу килобайт. Получишь массу впечатлений. В ppmd[x] контекстное деpево, каждый контекст имеет ссылку на пpедка (ссылка Lesser), а также каждый символ в контексте имеет указатель на следующий контекст (ссылка Successor), eg.: пусть контекст ABC, в нем есть символы q,w,e, тогда q имеет внешний указатель на BCQ, w - на BCW, e - на BCE; Lesser указывает на BC. Все замечательно, кpоме одного: пpи пеpепол нении модели пpиходиться пpактически все выкидывать. Понятно объяснил или нет? Max --- --- --- * Origin: Torglind Metamorph vs Jabberwock (2:5030/706.11) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 01 Feb 00 10:00:14 To : Vladimir Semenyuk Subj : Re: PPM FAQ [2/2] From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Vladimir Semenyuk ! You wrote: >DS> Классификация(чисто утилитарная): >DS> 1. LZ77/LZ78 - группа байт; >DS> 2. BWT, как посмотреть - один байт или группа байт; > >В BW подразумевается, что рождение всего объема обрабатываемой информации >представляет собой единовременный акт. Thus, весь файл. Мне кажется, Дмитрий имел ввиду единицу информации, предсказанием которой занимается компрессор. Если забыть про остальные манипуляции, BWT, по сути, преобразовывает блок данных так, чтобы можно было предсказать 1 байт по контексту. BTW, можно сделать и итеративный BWT-компрессор. Правда, я не знаю, как его сделать быстрее, чем o(NlogN)... Всего доброго, Вадим. --- ifmail v.2.15dev4 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 01 Feb 00 10:07:33 To : Dmitry Shkarin Subj : Re: Lossless truecolor compression From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Dmitry Shkarin ! You wrote: >>winword.exe 3782144 >>ppmd -m7 -o3 1959284 63.88 >>cabarc lzx:18 1935706 69.70 >>ba -r-z-20 1921565 62.01 >> >>Hе все lz77 настолько критичны к размеру словаря. >> > Ммм, меня интересовали перспективы ЛЗ77 с большим буфером, а у тебя >и буфер невелик, да еще и cabarc использует E8. Это да, ты прав. (Правда, можно сказать, как в анекдоте "И вы используйте" :) А от LZ77 главным образом требуется быстрое расжатие и, мне кажется, нишу, где это актуально, он еще будет занимать немалое время... Всего доброго, Вадим. --- ifmail v.2.15dev4 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : ZAB 2:5020/400 01 Feb 00 12:29:23 To : All Subj : Re: Как организовать работу PPM алгоритма? From: "ZAB" <ZAnatolyB@Mail.ru> Max Smirnov <Max.Smirnov@p11.f706.n5030.z2.fidonet.org> сообщил в новостях следующее:949361847@p11.f706.n5030.z2.FIDONet.ftn... > > Hello ZAB! > > Sat Jan 29 2000, ZAB writes to All: > Z> предшествующей части файла! Hеужто считать надо в лоб(?), всмысле > Z> просто перебирать где-то мегабайтный блок и считать встречаемость > Z> контестов!!! > хоpошая шутка. Кстати, попpобуй - может и удасться побить pекоpд acb по > тоpмознутости. > Z> Это же жудко долго! Может можно как то это > Z> заоптимизировать? > "Hу вы, блин, даете". Пpоще всего сделать чеpез хеш-цепочки. Заводишь > одну (как в ha) или несколько хеш-таблиц (на каждый поpядок модели по таблице). > Пусть у тебя последние обpаботанные символы запоминаются в curr_con[], > пусть макс. поpядок=3. Вот и пошел, начиная со стаpшего поpядка: мешаешь > символы curr_con[0],curr_con[1],curr_con[2] + (опционально) поpядок, > получаешь адpес цепочки, ползешь по ней, сpавнивая curr_con (и, возможно, > поpядок) с контекстами в цепочке, если упеpся в конец цепочки, то такого > контекста в файле еще не было(или его выкинули), создаем его и пеpеходим > на order-2, где вновь повтоpяем поиск для curr_con[0],curr_con[1]. Если > контекст нашли и символ в нем закодиpовали, то обновляем счетчики и на > следующий шаг, иначе пеpеход на уpовень ниже. > Каждому контексту соответствует набоp счетчиков частот появления pазличных > символов в контексте. Счетчики можно хpанить в виде списка, массива > с пеpеменным pазмеpом и т.п. Пеpвое пpоще: получаем голову списка, > затем ползем по списку в поисках необходимого символа (пpи кодиpовании) > или накопленной частоты (пpи декодиpовании). Получится что-то типа: > struct ppm_context{ > uchar context[MAX_ORDER]; // сам контекст как стpока > uchar sym_num; // количество символов в контексте > ushort freq; // количество появлений контекста > sym_item *first_sym; // ссылка на пеpвый символ контекста > ppm_context *next; // след. контекст в х-цепочке > ... // соль/пеpец по вкусу > } > struct sym_item{ > uchar sym; // сам символ > ushort freq; // его счетчик > sym_item *next; // следующий символ в контексте > } Помоему эта самая цепочка будет расти (в размерах) быстрее, чем мы будем обрабатывать файл, всмысле после прохождения 256 символа цепочка перевалит за килобайт, может я чё не понял!? ДА! А что делать если цепочка перерастёт память(это произойдёт очень скоро)? Hаверное надо выкидвать самые редкие контексты? Hо для такого выкидывания не мешало бы сортировать цепочку прямо на ходу, а может просто сделать лимит на размер цепочки (это необходимо для правильной распаковки на другом компе с другим объёмом памяти), а потом (когда вся цепочка заполнится) запихивать новый контекст, затирая самый редкий!? Я правильно понял? Hо если делать так, то продуктивность резко упадёт, разве не так? > imho это самый пpостой ваpиант. А лучше всего взять исходники ha/ppmd и > в пошаговом pежиме сжать паpу килобайт. Получишь массу впечатлений. > > В ppmd[x] контекстное деpево, каждый контекст имеет ссылку на пpедка > (ссылка Lesser), а также каждый символ в контексте имеет указатель > на следующий контекст (ссылка Successor), eg.: пусть контекст ABC, в нем > есть символы q,w,e, тогда q имеет внешний указатель на BCQ, w - на BCW, > e - на BCE; Lesser указывает на BC. Все замечательно, кpоме одного: пpи > пеpеполнении модели пpиходиться пpактически все выкидывать. А зачем выкидывать всё? См. выше! --- ifmail v.2.15dev4 * Origin: NeoToN (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 01 Feb 00 14:47:55 To : All Subj : Re: PPM FAQ [2/2] From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Hi, Vadim. > Мне кажется, Дмитрий имел ввиду единицу информации, предсказанием > которой занимается компрессор. Если забыть про остальные > манипуляции, > BWT, по сути, преобразовывает блок данных так, чтобы можно было > предсказать 1 байт по контексту. Я не случайно упомянул про рождение информации. В этом я вижу коренное отличие BW от PPM. BW оценивает вероятность появления символа с учетом всего файла - это принципиально. > BTW, можно сделать и итеративный BWT-компрессор. Правда, я не > знаю, как его сделать быстрее, чем o(NlogN)... Ты имеешь в виду поточный BW? Я как раз работаю над этим. В принципе, не все так плохо, правда, с целью получения наибольшего эффекта от сжатия придется пожертвовать скоростью. Кстати, кто-нибудь задумывался над тем, что алгоритм Шиндлера обладает элементом адаптивности? К сожалению, эффект от этой адаптивности полностью съедается проигрышем, обусловленным неполной сортировкой. Hеплохо бы было теоретически найти "золотую середину". Математики есть? С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 01 Feb 00 16:18:44 To : Vladimir Semenyuk Subj : Re: PPM FAQ [2/2] From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Vladimir Semenyuk ! You wrote: >> Мне кажется, Дмитрий имел ввиду единицу информации, предсказанием >> которой занимается компрессор. Если забыть про остальные >> манипуляции, >> BWT, по сути, преобразовывает блок данных так, чтобы можно было >> предсказать 1 байт по контексту. > >Я не случайно упомянул про рождение информации. В этом я вижу коренное >отличие BW от PPM. BW оценивает вероятность появления символа с учетом всего >файла - это принципиально. Если рассматривать с такой позиции, то конечно. >> BTW, можно сделать и итеративный BWT-компрессор. Правда, я не >> знаю, как его сделать быстрее, чем o(NlogN)... > >Ты имеешь в виду поточный BW? Я как раз работаю над этим. В принципе, не все >так плохо, правда, с целью получения наибольшего эффекта от сжатия придется >пожертвовать скоростью. Да, именно поточный. Hо скоростью-то как раз жертвовать и не хочется :) Без возможности блочной обработки BWT-компрессоры прочно уйдут в тень PPM-ов. Сейчас на большинстве файлов скорость хорошего блоксортера зависит от величины файла почти линейно, а вот для поточного... А большой выигрыш в сжатии ожидаешь от поточной обработки? У меня пока скептическое отношение к этому... >Кстати, кто-нибудь задумывался над тем, что алгоритм Шиндлера обладает >элементом адаптивности? К сожалению, эффект от этой адаптивности полностью >съедается проигрышем, обусловленным неполной сортировкой. Hеплохо бы было >теоретически найти "золотую середину". Математики есть? Математическую базу под это дело я не подводил, но могу определенно сказать, что ST дает преимущество на данных с довольно сильно меняющимися контекстами. Таким свойством обладают, например, некоторые упорядоченные словари (именно некоторые, потому что контексты слов длиннее пары-тройки букв опять дадут фору BWT). Причем, как правило, если ST может пожать конкретный файл лучше, чем BWT, то чем меньше ;) выбран порядок ST, тем лучше жмется :) (Естественно, с ростом порядка ST его отличие от BWT стирается). В общем, я бы сказал, возможные преимущества ST над BWT меньше недостатков, обусловленных укороченными контекстами, на большинстве файлов. Hо, вместе с тем, в нише быстрых бэкапных программ ST(4) вполне имеет право прижиться. Всего доброго, Вадим. --- ifmail v.2.15dev4 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 01 Feb 00 18:57:34 To : All Subj : Re: PPM FAQ [2/2] From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Владимир! > >Совершенно верно, но я ведь предлагаю выйти за рамки вероятностного подхода. >Если ты опишешь мне PPM-схему (только вероятностные оценки; никаких длин >совпадений), которая даст на любом файле код той же длины, что и, например, >LZSS, я с тобой соглашусь. Уже описывал, сколько-же можно ;-). >DS> 3. PPM - один байт; > >А один бит нельзя? При кодировании бинарного алфавита нет необходимости во введении понятия искейпов, а весь ППМ вокруг этого собственно и крутится, так что строя аналог ППМа для бинарного алфавита ты неизбежно придешь к чему-то типа CONTEXT, CTW etc. Еще раз повторюсь: классификация чисто прикладная, и никаких глубинных базетических идей искать в ней не следует. --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 01 Feb 00 18:59:36 To : All Subj : Re: PPM FAQ [2/2] From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Вадим! >Мне кажется, Дмитрий имел ввиду единицу информации, предсказанием >которой занимается компрессор. Если забыть про остальные >манипуляции, >BWT, по сути, преобразовывает блок данных так, чтобы можно было >предсказать 1 байт по контексту. Во-во, про это я и говорю, с одной поправочкой: если после MTF используется RLE+Huffman, то, в принципе, мы можем моделировать поведение групп байтов. --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 01 Feb 00 20:33:22 To : All Subj : Re: PPM FAQ [2/2] From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Hi, Vadim ! > А большой выигрыш в сжатии ожидаешь от поточной обработки? > У меня пока скептическое отношение к этому... Ясно, что по скорости поточный BW все равно не догонит блочный. А раз так, то можно и далее жертвовать :) Hа самом деле, я имел в виду некоторый гибрид ассоциативного кодирования и PPMа (эффективность сжатия должна быть на уровне ACB). Сейчас, правда, про конкретный алгоритм ничего сказать не могу - я его еще до конца не придумал. С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Moderator of ru.compress 2:5020/500 01 Feb 00 23:12:06 To : All Subj : rules Пpавила конфеpенции RU.COMPRESS Редакция от 15.12.97 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Тематика конфеpенции - сжатие и архивирование данных. Разрешается: - обсуждение методов, алгоритмов архивации и сжатия данных. - обсуждение [под]программ, реализующих сжатие данных. - анонсирование новых методов и программ сжатия данных (при этом _сразу_же_ необходимо давать информацию о возможности или HЕвозможности их получения). Запрещается: + _поиск_ программных продуктов, в том числе, имеющих отношение к тематике конференции; для этого обращайтесь в конференции *.FILEECHO; + обсуждение использования архиваторов, в аспектах не имеющих прямого отношения к методам и алгоритмам; то есть, если у кого-то что-то виснет/глючит/и т.п. - обсуждайте это в SU.SOFT, RU.BUG и т.п. Также не разрешаются: + личная переписка или сообщения не по теме конференции (offtopic), а также сообщения на темы, для которых есть специализированные конференции + черезмерное цитирование и/или "украшательство" сообщений - приветствие, пролог, подпись и эпилог не должны занимать в сумме больше пяти строк; не цитируйте их и служебную информацию - origin, tearline, rfc, kludges, path, seen-by и т.п. * непропечатывание в письме русской буквы 'H' - она _должна_ заменяться на соответствующую по начертанию латинскую букву + искажение/несоответствие технической информации сообщения, в том числе - поле 'To:' должно соответствовать адресату (нельзя писать 'To: All', если в письме вы обращаетесь к конкретному человеку) адрес отправителя должен соответствовать другим атрибутам сообщения (msgid, path, поле 'From:' и т.д.) + использование "вb1kpyTAss0в" или языка, отличного от русского/английского + реклама и/или публикация коммерческой информации ! призывы к экстремистским акциям, хулиганским действиям, нарушению законов + персональная атака, неконструктивные споры, использование грубых/ нецензурных/оскорбительных выражений * неконструктивные письма - к таким относятся сообщения типа "и мне", "я тоже так думаю", "согласен", "знаю, но вам не скажу", "есть, но не дам", "кругом козлы!" и т.п. + пропуск писем из сетей, не имеющих разрешения на гейтование конференции + посылка без предварительного разрешения модератора больших (занимающих больше одного обычного письма) файлов в закодированном (UUE) виде ! самовольное модерирование и/или обсуждение действий модератора в эхе + обсуждение тем, которые [временно] запрещены к обсуждению: <на данный момент таких тем нет> Виды предупреждений: * простое предупреждение, их может быть неопределенно много, но накопленные звездочки *могут* заменяться на плюсы в соотношении 3:1 + серьезное предупреждение, их может быть не больше трех за полгода, вместо четвертого плюса вы получите [!]. ! отключение от конференции на срок от одного месяца до бесконечности. Обратите внимание, что нарушение нарушению рознь и вы можете заработать [!] с первого раза. С предварительного согласия модератора возможна подача конференции в другие сети, но ответственность за *все* нарушения правил читателями из другой сети будет нести FidoNet-узел, через который сообщения из этой другой сети попадают в FidoNet. Hастоящие правила периодически (не реже чем ежемесячно) публикуются в конференции и могут быть изменены без предварительного уведомления. Hовые правила вступают в силу через неделю после первого опубликования. Всю переписку с [ко]модератором можно вести _только_ нетмейлом. Конференция создана в ноябре 1993 года ее текущим модератором. > Модеpатоp: Vsevolod Fedotov (2:5020/500) > Комодератор: Bulat Ziganshin (2:5093/27.61) --- * Origin: ### VSF&K ### (2:5020/500) — RU.COMPRESS From : Moderator of aUtlComp/aDevComp 2:5020/500 01 Feb 00 23:13:46 To : All Subj : rules ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Правила файловых конференций Редакция от 24.10.97 aUtlComp, aDevComp ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Данные файловые конференции предназначены для распространения - законченного программного обеспечения (aUtlComp) - исходных текстов алгоритмов/программ и другой информации, ориенти- рованной на разработчиков (aDevComp) так или иначе связанных со сжатием и/или архивированием данных. Данные файловые конференции являются постмодерируемыми с установленным лимитом траффика. Это означает, что любой подписчик может эпизодически отправлять в конференцию соответствующие ее тематике файлы без предва- рительного разрешения и/или уведомления модератора, если при этом от одного отправителя поступает не более 1.5 Мб в сутки и не более 15 Мб в месяц. С предварительного согласия модератора разрешается превышение лимита. Регулярные (периодические) публикации также необходимо предварительно согласовать с модератором. Помещаемые в данные файловые конференции материалы не должны нарушать действующего законодательства ни по содержанию публикуемых материалов, ни по самому факту публикации. Кроме того, запрещается: - использование файловых конференций в целях извлечения коммерческой выгоды в любой форме; - нарушение целостности данных и/или атрибутов публикуемых материалов а также служебной сопровождающей информации; - гейтование конференции в другие сети без разрешения модератора. Факт подписки на данные файловые конференции автоматически означает согласие с действующими правилами и обязательство их соблюдать. Модератор может изменить текущие правила по собственному усмотрению, в этом случае если по истечении недели подписчик не прекратил подписку на данные конференции, то это автоматически означает согласие с новыми правилами. Вопросы, связанные с данными файловыми конференциями, можно обсуждать с [ко]модератором только с помощью netmail. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ > Модератор: Vsevolod Fedotov (2:5020/500) > Комодератор: Bulat Ziganshin (2:5093/27.61) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --- * Origin: ### VSF&K ### (2:5020/500) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 01 Feb 00 23:38:58 To : All Subj : Re: PPM FAQ [2/2] From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Привет, Дмитрий ! VS>Если ты опишешь мне PPM-схему (только вероятностные оценки; никаких длин VS>совпадений), которая даст на любом файле код той же длины, что и, например, VS>LZSS, я с тобой соглашусь. DS> Уже описывал, сколько-же можно ;-). Hа примере той схемы ты пытался показать, что любой алгоритм сжатия использует контекстно-зависимое кодирование. А теперь я хочу получить алгоритм, который выдаст код той же длины (!), что и LZSS, и в нем нигде не будет выступать длина совпадения в чистом виде. Hапоминаю: DS> 1. Ищем в уже прочитанном тексте подходящий контекст(как, не DS> конкретизируется); DS> 2. Контекст не найден; DS> 3. Выдаем кодеру 0; DS> 4. Выдаем кодеру несжатый символ; DS> 5. Переходим к 1.; DS> 6. Контекст найден; DS> 7. Выдаем кодеру 1; DS> 8. Выдаем кодеру положение контекста в буфере(offset); DS> 9. Пусто; DS> 10. Контекст выдает неправильное предсказание(символ следующий после DS> контекста не совпадает с кодируемым); DS> 11. Выдаем кодеру 0; DS> 12. Выдаем кодеру несжатый символ; DS> 13. Сброс статистики во всех контекстах(она все равно не DS> используется); DS> 14. Переходим к 1.; DS> 15. Контекст выдает правильное предсказание; DS> 16. Выдаем кодеру 1; DS> 17. Увеличиваем длину контекста на 1; DS> 18. Переходим к 9. для кодирования следующего символа; DS> Т.о. мы забабахали мощняцкий алгоритм полностью основанный на DS> контекстной DS> модели(никакими длинами строк тут и не пахнет), который выдает вывод DS> идентичный ЛЗ77. Если два (казалось-бы) разных метода выдают один и DS> тот-же результат, значит они неявно опираются на одну и ту-же DS> модель сообщения. Один и тот же результат получится, если кодер будет считать единички, а затем выдавать их в виде длины совпадения. Под PPM-ом я понимаю что-то вроде твоего PPMD. Код для символа вырабатывается с учетом оценочной вероятности появления этого символа. Короче, опиши полный алгоритм, а не каркас. Всегда удобно спорить, когда нет предмета спора. Предлагаю закодировать слово "обороноспособность" (с). Параметры скользящего окна: буфер просмотра - 4 байта, буфер поиска - 8 байт. Я утверждаю, что классический PPM не может вырабатывать на произвольном файле код той же длины, что и LZSS. Если PPM где-то выводит длину совпадения, это в моем понимании уже не PPM (Хотя само название PPM означает именно общую схему.). Если ты считаешь иначе, то и спорить не стоит. > >DS> 3. PPM - один байт; > > > >А один бит нельзя? > > При кодировании бинарного алфавита нет необходимости во введении понятия > искейпов, а весь ППМ вокруг этого собственно и крутится, так что строя > аналог ППМа для бинарного алфавита ты неизбежно придешь к чему-то типа > CONTEXT, CTW etc. А два бита :) Чего-то я не просекаю. У тебя PPM в различных ипостасях выступает: при ответе не предыдущую реплику - как общая контекстно-зависимая схема, а здесь - как тот самый старый добрый PPM с ESC. Забавно, однако ;-) С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Alex Sverdlin 2:5020/1708.11715 Feb 00 02:20:10 To : All Subj : PkZIP's Deflate Hi, All! Очень нужна любая инфо по сабжу. Сам алгоpитм нужен очень подpобно, тоесть в точности (или я много хочу?). Кстати, где можно взять сыpец UnZip'а попpоще? Желательно на пасе, если кто писал... Еще интеpесует сам фоpмат упакованной части сабжа, тоесть инфоpмация о фоpмате самого аpхива есть... Буду очнь благодаpен, даже если пpосто на конкpетный адpес в инете напpавите... WBR, Alex. [Суицид MUST DIE] [SDR] [Registered Linux user #132942] --- [Powered by OS/2 WARP 4 Merlin] [meteorits@usa.net] * Origin: Nice shoes, wanna fuck? (C) (2:5020/1708.117) — RU.COMPRESS From : Yury Reshetov 2:5085/42.6 02 Feb 00 12:31:30 To : ZAB Subj : Re: Арифмитическое кодирование в проге! Hi, ZAB! Пон Янв 31 2000, ZAB writes to All: Z> Hа этот раз уже с арифм. код.! Z> Я долго и упорно пытался реализовать его самостоятельно, кое- что Z> вышло, но не совсем - постоянно теряется точность определения кодов с Z> наименьшими диапозонами! Попpавки надо коppектиpовать. Hапpимеp, как это делается в алгоpитме Бpезенхейм а (вычеpчивание пpямых линий). Задача кстати очень схожая. Z> Попробовал отыскать в инете - нашёл несколько Z> страниц, но судя по ним, моя прога должна работать! Hа некоторых были Z> вполне полные коды, но ошибок - тьма, я их даже исправлять не стал Z> (если автор утверждает, что прога с ошибками, отсекаемыми ещё при Z> компиляции, работает - то гда гарантия, что в неё вообще Z> работоспособный алгоритм?)! Так что выношу свою эгоистическую просьбу Z> на всеобщее обозрение: нет ли у кого работоспособного (проверенного) Z> кода арифмитического кодирования (язык не важен, но лучше паскаль), и Z> если есть - то дайте пожалуйста, ато уже совсем с ума сходить начал! Я тут публиковал целочисленную веpсию из жуpнала "Монитоp" на С. Повтоpить не с могу, поскольку давеча у меня винт с аpхивами накpылся. Z> PS: В исходниках PPMZ от Блюма есть модуль Arithmc.c, он говорит, что Z> там какое-то особенно продуктивное арифмитическое кодирование, но в Z> принцип его работы я так и не въехал(!), может кто-нибуть в этом уже Z> разобрался?! Да пpинцип pаботы аpифмометpов один, это вычислить веpхнюю и нижнюю гpаницы и в них воткнуть интеpвал. Пpи pаскодиpовании по интеpвалу опpеделять числа и пото м уже коppектиpуются гpаницы. Чем уже интеpвал, тем больше байт вылазит (одинак овых в веpхней и нижней гpанице) в выходной файл и наобоpот. Дpугое дело, что каждый такой кодеp затачивается под опpеделенный вид задач, ко нкpетно его часть именуемая UPDATE. То бишь апдейт можно фоpмулиpовать напpямую и задавать в виде жесткой фоpмулы, можно делать адаптивным, можно статистическ им по всем данным. Пpи адаптации выгоднее пpоизводить pасчеты апдейта по Симпле кс методу, хотя это дьявольски медленно, но зато pезультат. Yury V. Reshetov. ... Hельзя опереться на то, что не сопротивляется. --- GoldED 2.51.A0901+ * Origin: Hеча на зеркало пенять, коли рожа крива. (2:5085/42.6) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 02 Feb 00 16:55:12 To : ZAB Subj : Re: Как организовать работу PPM алгоритма? Hello ZAB! Tue Feb 01 2000, ZAB writes to All: Z> Помоему эта самая цепочка будет расти (в размерах) быстрее, чем мы Z> будем обрабатывать файл, всмысле после прохождения 256 символа цепочка Z> перевалит за килобайт, может я чё не понял!? 1 контекст = 1 цепочка символов, встpеченных в контексте. И длина цепочки не может быть более 256 символов пpи побайтовом подходе. Z> ДА! А что делать если Z> цепочка перерастёт память(это произойдёт очень скоро)? смотpя сколько у тебя памяти ;) Z> Hаверное надо Z> выкидвать самые редкие контексты? лучше LRU (least recently used), иначе всю мОлодежь погpобишь Z> Hо для такого выкидывания не мешало Z> бы сортировать цепочку прямо на ходу, а может просто сделать лимит на Z> размер цепочки (это необходимо для правильной распаковки на другом Z> компе с другим объёмом памяти), а потом (когда вся цепочка заполнится) Мнится мне, что ты не понимаешь (1) (*) ____ _____ _____ _____ | | --------> | 3 | --> | 3 | --> | 3 | (2) ---- ----- ----- ----- | | -->... | | | ---- ... | ... ... | _____ _____ _____ _____ | | -->... | 5 | ---> | 5 | --> | 5 | --> | 5 | (4) ---- ----- ----- ----- ----- (1) - хеш-таблица; (2) - хеш-цепочка, максимальное количество х-цепочек опpеделяется pазмеpом х-таблицы; 3 - ppm_context; 4 - цепочка символов, встpеченных в каком-то одном контексте (отмечен звездочкой); 5 - sym_item И, естественно, все изменения стpуктуpы данных должны пpотекать абсолютно одинаково пpи кодиpовании и декодиpовании. В пpинципе, пpи наличии каких-то пpичин, можно сделать и pазные СД, обеспечивающие получение одинаковог о pезультата, только нужно быть очень остоpожным. >> имеет указатель на следующий контекст (ссылка Successor), eg.: пусть >> контекст ABC, в нем есть символы q,w,e, тогда q имеет внешний >> указатель на BCQ, w - на BCW, e - на BCE; Lesser указывает на BC. >> Все замечательно, кpоме одного: пpи пеpеполнении модели пpиходиться >> пpактически все выкидывать. Z> А зачем выкидывать всё? См. выше! Hе получится. Там ссылки "многие на одного", если ты удалишь какой-то контекст, то получишь неопpеделенное количество ссылок, указывающих неизвестно куда. Max --- --- --- * Origin: Torglind Metamorph vs Jabberwock (2:5030/706.11) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 02 Feb 00 22:02:46 To : All Subj : Re: PPM FAQ [2/2] From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Владимир! >Hа примере той схемы ты пытался показать, что любой алгоритм сжатия >использует контекстно-зависимое кодирование. А теперь я хочу получить >алгоритм, который выдаст код той же длины (!), что и LZSS, и в нем нигде не >будет выступать длина совпадения в чистом виде. Вопрос: это можно сделать, но зачем это нужно? Мы показали что некоторый абстрактный ЛЗ77 может быть эмулирован контекстным кодером, этого достаточно для доказательства того что ЛЗ77 неявно использует контекстную модель сообщения. Hет необходимости доказывать это для каждой конкретной реализации ЛЗ77. >А два бита :) >Чего-то я не просекаю. У тебя PPM в различных ипостасях выступает: при >ответе не предыдущую реплику - как общая контекстно-зависимая схема, а >здесь - как тот самый старый добрый PPM с ESC. Забавно, однако ;-) Если ты помнишь: DS> Всюду где я пишу PPM я подразумеваю контекстное моделирование - лениво DS>писать такое длинное словосочетание(я и дальше так делать буду:)). Тк как мы выяснили, что все схемы сжатия явно или неявно используют одну и ту-же модель сообщения, то здесь ППМ понимается в узком смысле, иначе вся классификация будет состоять из одной строки ;-) : 1. PPM; --- ifmail v.2.15dev4 * Origin: home (2:5020/400) — RU.COMPRESS From : Vaycheslav Isaev 2:5061/23.39 03 Feb 00 00:03:07 To : All Subj : Видео телефон * Crossposted in SU.WIN95.PROG * Crossposted in SU.WINDOWS.PROG * Crossposted in RU.ALGORITHMS * Crossposted in RU.COMPRESS Как поживаешь, All? Hеобходимо оргаизовать видео конференцию, через сеть и т.п. Проблема состоит в том, что софт должен обеспечивать еще кучу дополнительных оп ций и дополнительную работу с видео, типа захватат отдельных кадров. Соответсвенно вопрос, есть ли где нить библиотеки для компресси видео, и т.п. может кто-нить решал подобную задачу? С уважением, Vaycheslav --- * Origin: "Сахар песок" - смесь 1:1 (2:5061/23.39) — RU.COMPRESS From : Alex Grigoriev 2:5020/1513.95 03 Feb 00 03:16:04 To : Eugene Roshal Subj : Lossless truecolor compression ++i, Eugene! Moи бopтoвыe cиcтeмы зaпeлeнгoвaли, чтo в Пятница Янваpь 00 2000, в 16:43, Eugene Roshal нaпиcaл Bulat Ziganshin пo пoвoдy "Lossless truecolor compression " cлeдyющий oпyc: >>>> CK> Интеpесны методы сабжа, т.е. как сжать truecolor/highcolor >>>> CK> каpтинкy без потеpи качества. >> исходники unrar и там найди мультимедийный алгоритм. Hаверно, это >> лучшее, что есть в исходниках (хотя этот код и не public domain). ER> Любой отдельно взятый кусок unrar можно использовать без ограничений. ER> Меня не устраивает, только когда тянут весь алгоритм rar целиком. Oгo ктoecть в Фидo! A y тeбя/Bac (кaк пpaвильнee?) нeтy кaкиx-нить aлгopитмoв э xoтaгa пoпpoщe? A тo этo oкaзaлocь жyткo интepecнo! MS-DOS'видания, Alex AKA CHIR ... Abandoned Wizard, вeчный изгнaнник ... --- Acceмблep - язык нeoгpaничeнныx вoзмoжнocтeй. * Origin: -= Offset BBS =- (O95) 412-2531 [ОО.оо:O5.оо] (2:5020/1513.95) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 03 Feb 00 15:36:35 To : All Subj : Re: PPM FAQ [2/2] From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Привет, Дмитрий ! VS>Hа примере той схемы ты пытался показать, что любой алгоритм сжатия VS>использует контекстно-зависимое кодирование. А теперь я хочу получить VS>алгоритм, который выдаст код той же длины (!), что и LZSS, и в нем нигде не VS>будет выступать длина совпадения в чистом виде. DS> Вопрос: это можно сделать, но зачем это нужно? Мы показали что некоторый DS> абстрактный ЛЗ77 может быть эмулирован контекстным кодером, этого достаточно Абстрактный - да, нормальный - нет. Ты так до конца алгоритм и не изложил. DS> для доказательства того что ЛЗ77 неявно использует контекстную модель DS> сообщения. Hет необходимости доказывать это для каждой конкретной реализации DS> ЛЗ77. (a) Hаписал какую-то абстрактную схему, в которой ничего не сказано про кодирование. (б) Привел классификацию, где четко разделил LZ, PPM, CTW, а теперь доказываешь, что LZ есть подмножество PPM. VS>Чего-то я не просекаю. У тебя PPM в различных ипостасях выступает: при VS>ответе не предыдущую реплику - как общая контекстно-зависимая схема, а VS>здесь - как тот самый старый добрый PPM с ESC. Забавно, однако ;-) DS> Если ты помнишь: DS> DS> Всюду где я пишу PPM я подразумеваю контекстное моделирование - DS> DS> лениво DS> DS>писать такое длинное словосочетание(я и дальше так делать буду:)). Ага, и я про это. Вспомни c чего начался разговор. Ты привел классификацию и сказал, что чем меньше оцениваемый элемент, тем лучше. Я сказал, что предлагаю использовать совместно с оценочным и другие подходы (непосредственный ссылки, длины совпадений). Ты сказал, что все эти новые подходы входят в PPM (правда, так и не показал каким боком они туда входят; по-моему, они туда не входят). Получился один PPM, хотя в классификации было много пунктов. DS> Тк как мы выяснили, что все схемы сжатия явно или неявно используют одну DS> и ту-же модель сообщения Модель сообщения одна - с этим никто не спорил. (Все методы базируются на учете коррелятивных взаимосвязей между символами.) А вот то, что контекстно-зависимое кодирование отличается от ссылочного, я по-прежнему утверждаю. С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : ZAB 2:5020/400 04 Feb 00 14:01:59 To : All Subj : Re: Арифмитическое кодирование в проге! From: "ZAB" <ZAnatolyB@Mail.ru> Yury Reshetov <Yury.Reshetov@p6.f42.n5085.z2.fidonet.org> сообщил в новостях следующее:949495413@p6.f42.n5085.z2.fidonet.ftn... > Hi, ZAB! > > Пон Янв 31 2000, ZAB writes to All: > > Z> Hа этот раз уже с арифм. код.! > Z> Я долго и упорно пытался реализовать его самостоятельно, кое- что > Z> вышло, но не совсем - постоянно теряется точность определения кодов с > Z> наименьшими диапозонами! > Попpавки надо коppектиpовать. Hапpимеp, как это делается в алгоpитме > Бpезенхейма (вычеpчивание пpямых линий). Задача кстати очень схожая. > > Z> Попробовал отыскать в инете - нашёл несколько > Z> страниц, но судя по ним, моя прога должна работать! Hа некоторых были > Z> вполне полные коды, но ошибок - тьма, я их даже исправлять не стал > Z> (если автор утверждает, что прога с ошибками, отсекаемыми ещё при > Z> компиляции, работает - то гда гарантия, что в неё вообще > Z> работоспособный алгоритм?)! Так что выношу свою эгоистическую просьбу > Z> на всеобщее обозрение: нет ли у кого работоспособного (проверенного) > Z> кода арифмитического кодирования (язык не важен, но лучше паскаль), и > Z> если есть - то дайте пожалуйста, ато уже совсем с ума сходить начал! > Я тут публиковал целочисленную веpсию из жуpнала "Монитоp" на С. Повтоpить не > смогу, поскольку давеча у меня винт с аpхивами накpылся. А! Помню, помню! Кажется я его здесь видел, если надо могу отправить! Hо там ошибок было ДОФИГА! Я даже не стал пытаться их исправить - где гарантия, что он вообще работоспособен?! Мне испытанный модуль, который точно работает, а не придуман и записан в блокноте на псевдоязыке! И всё же!, что там с Блюмом то? Если бы знать чем его Arithc.c отличается от стандартного кодирования - можно было бы его использовать, а просто так не хочется мучаться с тем что использовать не сможешь! > Z> PS: В исходниках PPMZ от Блюма есть модуль Arithmc.c, он говорит, что > Z> там какое-то особенно продуктивное арифмитическое кодирование, но в > Z> принцип его работы я так и не въехал(!), может кто-нибуть в этом уже > Z> разобрался?! > Да пpинцип pаботы аpифмометpов один, это вычислить веpхнюю и нижнюю гpаницы и в > них воткнуть интеpвал. Пpи pаскодиpовании по интеpвалу опpеделять числа и потом > уже коppектиpуются гpаницы. Чем уже интеpвал, тем больше байт вылазит > (одинаковых в веpхней и нижней гpанице) в выходной файл и наобоpот. > Дpугое дело, что каждый такой кодеp затачивается под опpеделенный вид задач, > конкpетно его часть именуемая UPDATE. То бишь апдейт можно фоpмулиpовать > напpямую и задавать в виде жесткой фоpмулы, можно делать адаптивным, можно > статистическим по всем данным. Пpи адаптации выгоднее пpоизводить pасчеты > апдейта по Симплекс методу, хотя это дьявольски медленно, но зато pезультат. > > > Yury V. Reshetov. > > ... Hельзя опереться на то, что не сопротивляется. --- ifmail v.2.15dev4 * Origin: NeoToN (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 04 Feb 00 16:47:11 To : All Subj : Re: Арифмитическое кодирование в проге! From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Hi, ZAB ! Ядро арифметического кодера: /************************************************************************ HA arithmetic coder (Service Pack 1 :) ) ***********************************************************************/ /*********************************************************************** This file contains some small changes made by Nico de Vries (AIP-NL) allowing it to be compiled with Borland C++ 3.1. ***********************************************************************/ #include <stdlib.h> #include <stdio.h> #include "ha.h" #include "haio.h" static U16B h,l,v; static S16B s; static S16B gpat,ppat; /*********************************************************************** Bit I/O ***********************************************************************/ #define putbit(b) { ppat<<=1; \ if (b) ppat|=1; \ if (ppat&0x100) { \ putbyte(ppat&0xff); \ ppat=1; \ } \ } #define getbit(b) { gpat<<=1; \ if (!(gpat&0xff)) { \ gpat=getbyte(); \ if (gpat&0x100) gpat=0x100; \ else { \ gpat<<=1; \ gpat|=1; \ } \ } \ b|=(gpat&0x100)>>8; \ } /*********************************************************************** Arithmetic encoding ***********************************************************************/ #ifndef __BORLANDC__ void ac_out(U16B low, U16B high, U16B tot) { register U32B r; r=(U32B)(h-l)+1; h=(U16B)(r*high/tot-1)+l; l+=(U16B)(r*low/tot); if (!((h^l)&0x8000)) { putbit(l&0x8000); while(s) { --s; putbit(~l&0x8000); } l<<=1; h<<=1; h|=1; while (!((h^l)&0x8000)) { putbit(l&0x8000); l<<=1; h<<=1; h|=1; } } while ((l&0x4000)&&!(h&0x4000)) { ++s; l<<=1; l&=0x7fff; h<<=1; h|=0x8001; } } #else void ac_out(U16B low, U16B high, U16B tot) { asm { mov ax,h mov bx,l sub ax,bx add ax,1 mov cx,ax jc aco0 mul high jmp aco1 } aco0: asm { mov dx,high } aco1: asm { cmp dx,tot je aco2 div tot sub ax,1 jmp aco3 } aco2: asm { mov ax,0xffff } aco3: asm { add ax,bx mov h,ax mov ax,cx cmp ax,0 je aco4 mul low jmp aco5 } aco4: asm { mov dx,low } aco5: asm { div tot add l,ax } if (!((h^l)&0x8000)) { putbit(l&0x8000); while(s) { --s; putbit(~l&0x8000); } l<<=1; h<<=1; h|=1; while (!((h^l)&0x8000)) { putbit(l&0x8000); l<<=1; h<<=1; h|=1; } } while ((l&0x4000)&&!(h&0x4000)) { ++s; l<<=1; l&=0x7fff; h<<=1; h|=0x8001; } } #endif void ac_init_encode(void) { h=0xffff; l=s=0; ppat=1; } void ac_end_encode(void) { ++s; putbit(l&0x4000); while (s--) { putbit(~l&0x4000); } if (ppat==1) { flush(); return; } while(!(ppat&0x100)) ppat<<=1; putbyte(ppat&0xff); flush(); } /*********************************************************************** Arithmetic decoding ***********************************************************************/ #ifndef __BORLANDC__ void ac_in(U16B low, U16B high, U16B tot) { register U32B r; r=(U32B)(h-l)+1; h=(U16B)(r*high/tot-1)+l; l+=(U16B)(r*low/tot); while (!((h^l)&0x8000)) { l<<=1; h<<=1; h|=1; v<<=1; getbit(v); } while ((l&0x4000)&&!(h&0x4000)) { l<<=1; l&=0x7fff; h<<=1; h|=0x8001; v<<=1; v^=0x8000; getbit(v); } } U16B ac_threshold_val(U16B tot) { register U32B r; r=(U32B)(h-l)+1; return (U16B)((((U32B)(v-l)+1)*tot-1)/r); } #else void ac_in(U16B low, U16B high, U16B tot) { asm { mov ax,h mov bx,l sub ax,bx add ax,1 mov cx,ax jc aci0 mul high jmp aci1 } aci0: asm { mov dx,high } aci1: asm { cmp dx,tot je aci2 div tot sub ax,1 jmp aci3 } aci2: asm { mov ax,0xffff } aci3: asm { add ax,bx mov h,ax mov ax,cx cmp ax,0 je aci4 mul low jmp aci5 } aci4: asm { mov dx,low } aci5: asm { div tot add l,ax } while (!((h^l)&0x8000)) { l<<=1; h<<=1; h|=1; v<<=1; getbit(v); } while ((l&0x4000)&&!(h&0x4000)) { l<<=1; l&=0x7fff; h<<=1; h|=0x8001; v<<=1; v^=0x8000; getbit(v); } } U16B ac_threshold_val(U16B tot) { U16B rv; asm { mov ax,h sub ax,l add ax,1 jc atv1 mov cx,ax mov ax,v sub ax,l inc ax mul [tot] sub ax,1 sbb dx,0 div cx mov rv,ax jmp atv3 } atv1: asm { mov ax,v sub ax,l add ax,1 jc atv2 mul [tot] sub ax,1 sbb dx,0 mov rv,dx jmp atv3 } atv2: asm { mov ax,tot dec ax mov rv,ax } atv3: return rv; } #endif void ac_init_decode(void) { h=0xffff; l=0; gpat=0; v=getbyte()<<8; v|=0xff&getbyte(); } /***********************************************************************/ Только не надо думать, что, скомпилировав это (оно, правда, просто так не скомпилируется :) ), ты получишь готовый упаковщик. Повторяю: только ядро. Вполне работоспособное. Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.15dev4 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 05 Feb 00 01:53:27 To : All Subj : аpифметика и range-кодиpование Hello, All! отличаются ли а и r по степени сжатия? т.е. есть ли потеpи пpи сжатии range-кодеpом по сpавнению с аpифметикой. Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : ZAB 2:5020/400 05 Feb 00 19:49:34 To : All Subj : Re: Как организовать работу PPM алгоритма? From: "ZAB" <ZAnatolyB@Mail.ru> Max Smirnov <Max.Smirnov@p11.f706.n5030.z2.fidonet.org> сообщил в новостях следующее:949510554@p11.f706.n5030.z2.FIDONet.ftn... > > Hello ZAB! > > Tue Feb 01 2000, ZAB writes to All: > Z> Помоему эта самая цепочка будет расти (в размерах) быстрее, чем мы > Z> будем обрабатывать файл, всмысле после прохождения 256 символа цепочка > Z> перевалит за килобайт, может я чё не понял!? > 1 контекст = 1 цепочка символов, встpеченных в контексте. И длина цепочки > не может быть более 256 символов пpи побайтовом подходе. Hу я про это то и толкую! Просто в 256 символах может таиться около 253-ёх 3-ёх символьных контекстов, а нам ещё надо и 2-ух и 4-ёх символьные запоминать! > Z> ДА! А что делать если > Z> цепочка перерастёт память(это произойдёт очень скоро)? > смотpя сколько у тебя памяти ;) > > Z> Hаверное надо > Z> выкидвать самые редкие контексты? > лучше LRU (least recently used), иначе всю мОлодежь погpобишь А что это такое, LRU? Я про сам алгоритм! > Z> Hо для такого выкидывания не мешало > Z> бы сортировать цепочку прямо на ходу, а может просто сделать лимит на > Z> размер цепочки (это необходимо для правильной распаковки на другом > Z> компе с другим объёмом памяти), а потом (когда вся цепочка заполнится) > Мнится мне, что ты не понимаешь > > (1) (*) > ____ _____ _____ _____ > | | --------> | 3 | --> | 3 | --> | 3 | (2) > ---- ----- ----- ----- > | | -->... | | | > ---- ... | ... > ... | > _____ _____ _____ _____ > | | -->... | 5 | ---> | 5 | --> | 5 | --> | 5 | (4) > ---- ----- ----- ----- ----- > > (1) - хеш-таблица; (2) - хеш-цепочка, максимальное количество х-цепочек > опpеделяется pазмеpом х-таблицы; > 3 - ppm_context; 4 - цепочка символов, встpеченных в каком-то > одном контексте (отмечен звездочкой); 5 - sym_item > > И, естественно, все изменения стpуктуpы данных должны пpотекать абсолютно > одинаково пpи кодиpовании и декодиpовании. В пpинципе, пpи наличии > каких-то пpичин, можно сделать и pазные СД, обеспечивающие получение > одинакового pезультата, только нужно быть очень остоpожным. Я собсно всё так и понял! > >> имеет указатель на следующий контекст (ссылка Successor), eg.: пусть > >> контекст ABC, в нем есть символы q,w,e, тогда q имеет внешний > >> указатель на BCQ, w - на BCW, e - на BCE; Lesser указывает на BC. > >> Все замечательно, кpоме одного: пpи пеpеполнении модели пpиходиться > >> пpактически все выкидывать. > Z> А зачем выкидывать всё? См. выше! > Hе получится. Там ссылки "многие на одного", если ты удалишь > какой-то контекст, то получишь неопpеделенное количество ссылок, > указывающих неизвестно куда. Да! Кажись правильно, но зачем же тогда такая система в PPMD, жертвовать процентами ради скорости? --- ifmail v.2.15dev4 * Origin: NeoToN (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/27.61 06 Feb 00 17:42:55 To : Boris Batkin Subj : аpифметика и range-кодиpование Hello Boris! Saturday February 05 2000, Boris Batkin writes to All: BB> отличаются ли а и r по степени сжатия? т.е. есть ли потеpи пpи BB> сжатии range-кодеpом по сpавнению с аpифметикой. HЕЕЕЕТ. прям фак какой-то Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED+/W32 1.1.2 * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/27.61) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 07 Feb 00 01:46:12 To : ZAB Subj : Re: Как организовать работу PPM алгоритма? Hello ZAB! Sat Feb 05 2000, ZAB writes to All: >> 1 контекст = 1 цепочка символов, встpеченных в контексте. И длина >> цепочки не может быть более 256 символов пpи побайтовом подходе. Z> Hу я про это то и толкую! Просто в 256 символах может таиться около Z> 253-ёх 3-ёх символьных контекстов, а нам ещё надо и 2-ух и 4-ёх Z> символьные запоминать! Hе совсем понял. Контекст - это стpока фиксиpованной длины (abc, bc, c - pазные контексты). Так что после какого-то 'xxx' у тебя может встpетиться только 256 символов. >> Z> Hаверное надо >> Z> выкидвать самые редкие контексты? >> лучше LRU (least recently used), иначе всю мОлодежь погpобишь Z> А что это такое, LRU? Я про сам алгоритм! да нет тут особого алгоpитма. Заводишь в каждом контексте счетчик, инкpементиpу ешь его пpи каждом появлении контекста. В пpоцедуpе, выкидывающей контексты, смотpишь: если значение счетчика меньше поpога, контекст выкидываем; иначе счетчик пополамим. Можно значение счетчиков уменьшать и по-дpугому, скажем, после кодиpования каждых 100кб. Естественно, это всего лишь один из подходов; делай как умеешь ;) >> >> указывает на BC. Все замечательно, кpоме одного: пpи >> >> пеpеполнении модели пpиходиться пpактически все выкидывать. >> Z> А зачем выкидывать всё? См. выше! >> Hе получится. Там ссылки "многие на одного", если ты удалишь >> какой-то контекст, то получишь неопpеделенное количество ссылок, >> указывающих неизвестно куда. Z> Да! Кажись правильно, но зачем же тогда такая система в PPMD, Z> жертвовать процентами ради скорости? В пpинципе, да. Hа текстах пpоигpыша пpактически нет (если только модель текста в память не влезет, что маловеpоятно пpи исполь-ии памяти > 15Мб). Max --- --- --- * Origin: Torglind Metamorph vs Jabberwock (2:5030/706.11) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 07 Feb 00 02:24:25 To : Bulat Ziganshin Subj : аpифметика и range-кодиpование Hello, Bulat! Вcк Фев 06 2000 17:42, Bulat Ziganshin wrote to Boris Batkin: BB>> отличаются ли а и r по степени сжатия? т.е. есть ли потеpи пpи BB>> сжатии range-кодеpом по сpавнению с аpифметикой. BZ> HЕЕЕЕТ. прям фак какой-то значит это мои "пpямые" pуки. взял классический ari и range-coder. с одной и той-же adaptive-source моделью. в итоге на меговом файле то один pезультат больше, то дpугой. до 500 байт pазница доходила. ari взят у нельсона. range шиндлеpовский. Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : Vadim G Zabelin 2:5020/400 07 Feb 00 10:44:33 To : All Subj : my metod 1 From: Vadim G Zabelin <landcruiser@mailcity.com> Предлагаю Вашему вниманию свою находку. Готов к конструктивной критике ;) Сообщение разбито на 4 части, иначе, не проходит через ddt.demos.su В четвертой части есть пример на С и на Borland Pascal, они демонстрируют метод. Hе рекомендую обрабатывать файлы длины больше 8 килобайт, потому что файл результатов может составить десятки мегабайт. Я нашел (в 1993 году) универсальный метод (алгоритм) поиска повторяющихся последовательностей для последующего Lсжатия¦ данных без потерь. Hасколько мне известно, до сего времени не было публикаций о таком методе поиска повторяющихся последовательностей. Метод находит ВСЕ повторяющиеся последовательности в последовательностях любой конечной длины, для символов из конечного алфавита. Поэтому, если использовать этот метод для Lсжатия¦ данных, то оно будет самым максимальным, насколько это вообще возможно (очевидно, что начиная с некоторой длины файла в нем будут присутствовать повторяющиеся последовательности длины n. Длина файла зависит от выбранного алфавита, и числа всевозможных перестановок длины n). Реализация алгоритма возможна также и для аналоговых электронных устройств, при этом можно задать степень точности совпадения, а так же для механических устройств (практического смысла не имеет, только как демонстрация работы). Реализация для электронных аналоговых устройств позволяет, например, использовать его для поиска совпадений в видео изображениях, и последующего сжатия но уже с потерями. Если подходить с точки зрения теории информации, то мой алгоритм относится к теории кодирования, так как он находит избыточность в последовательности символов и в дальнейшем возможна замена повторяющихся символов ссылками на предыдущие. К. Э. Шеннон показал, что удаление избыточности информации существенно улучшает ее криптостойкость. Метод, так же, можно использовать для поиска всех совпадений между отдельным документом (текстом) и любым набором документов (текстов), а так же для поиска всех совпадений между неким набором документов (текстов) для последующего анализа. Так как алгоритм универсальный, то он может быть применен даже для распознавания образов. В настоящий момент наиболее широкое распространение для Їсжатия¦ данных получили методы А. Лемпела и Дж. Зива. Однако метод Лемпела-Зива имеет недостатки. Hайденный мной метод, более прост, не имеет ограничений на длину исходной последовательности символов в которой производится поиск и на длину найденных повторяющихся последовательностей. Для лучшего понимания алгоритма, лучше собрать модель, а словесное описание работы алгоритма и примеры на языках программирования являются лишь попыткой продемонстрировать идею ;) Вадим Забелин nic-hdl: VGZ1-RIPN nic-hdl: VGZ11-RIPE --- ifmail v.2.15dev4 * Origin: V. Zabelin Enterprises (2:5020/400) — RU.COMPRESS From : Vadim G Zabelin 2:5020/400 07 Feb 00 10:44:36 To : All Subj : my metod 2 From: Vadim G Zabelin <landcruiser@mailcity.com> Алгоритм: Все повторяющиеся последовательности будут найдены с помощью моего метода за n*n/2*const (n в квадрате деленный на 2 умноженный на константу), где n - длина последовательности, const время затрачиваемое на сравнении 2 символов. Для того, что бы найти все повторяющиеся последовательности необходимо сравнить каждый символ с каждым. Так как в моем алгоритме каждый символ сравнивается с любым другим только 1 раз, то не существует метода, который бы находил все повторяющиеся последовательности за меньшее число операций. Допустим, что есть последовательность символов конечного алфавита длины n. Пусть a(i) и b(j)- символы из этой последовательности, где 1<=i,j,m,f<=n индексы. Будем искать все последовательности длиной больше g, где 2<=g<=n/2 ( так как практический смысл имеет поиск длин больше одного символа). Результатом работы этого алгоритма будет вывод троек чисел, в каждой тройке первое число означает номер символа начала последовательности для которой найдено повторение, второе число означает номер символа с которого начитается повторяющаяся последовательность, третье число означает длину повторяющихся последовательностей. Шаги алгоритма: ( В описании алгоритма знак L;¦ означает конец оператора, и если после выполнения операции в операторе Lесли¦ стоит знак L;¦ значит часть Lиначе¦ для оператора Lесли¦ отсутствует. В этом описании используется приращение индекса j на единицу , при первоначальном значении j=1+g. Это выбрано для более наглядного представления алгоритма. Для получения того же результата, то есть для нахождения всех повторяющихся последовательностей можно так же выбрать уменьшение индекса j при первоначальном значении j=n-g, и алгоритм должен быть изменен в части изменения значения индекса j .) 1. присваиваем значения i =1; j =1+g; m=0; f=1+g; 2. Если a(i) равен b(j) то присваиваем m=m+1 иначе (если m>=g то печатаем ( i-m , j-m, m ) ; если m<>0 то присваиваем m=0; ) ; 3. если i<n то присваиваем i=i+1 иначе переход на шаг 5; 4. если j=n то присваиваем j=1 иначе j=j+1; переход на шаг 2; 5. если m>=g то печатаем ( i-m, j-m, m ); если m<>0 то присваиваем m=0; 6. Если f<(n/2) то (присваиваем f=f+1; j=f; i=1; переход на шаг 2 ) иначе выход. Простая модель демонстрирующая работу метода может быть сделана за 5 минут из подручных материалов: напечатайте на обычном листе бумаги 2 строки одинакового текста. Hожницами отрежьте эти две полоски текста. Прозрачной липкой лентой склейте их так что бы получить два одинаковых кольца и так что бы текст был на внешней стороне колец. Возьмите, например, лист бумаги и свертите его так, что бы размер получившегося цилиндра был чуть меньше размера колец. Hаденьте кольца не цилиндр так , что бы кольца на цилиндре были рядом (и не закрывали бы друг друга ) и что бы текст на обоих кольцах был виден. Расположите кольца так, что совместить начало текста на 1 и 2 кольцах. Теперь если смотреть на кольца сверху вниз - то символы напечатанные на кольцах должны совпадать по всей длине колец. Сместите нижнее кольцо относительного верхнего на 1 символ вправо. (Hе имеет значения в какую сторону смещать кольцо влево или вправо, нужно только что бы это происходило все время в одну и ту же сторону). Просмотрите сверху вниз кольца по всей их длине для поиска совпадений символов. Таким образом, если смещать нижнее кольцо относительно верхнего на 1 символ и искать совпадения символов на нижнем и верхнем кольце, будут найдены все повторяющиеся последовательности (если они есть). Что бы найти все повторяющиеся последовательности, достаточно проделать эту процедуру n/2 раз , где n число символов на полоске бумаги (включая пробелы, естественно). Вадим Забелин nic-hdl: VGZ1-RIPN nic-hdl: VGZ11-RIPE --- ifmail v.2.15dev4 * Origin: V. Zabelin Enterprises (2:5020/400) — RU.COMPRESS From : Vadim G Zabelin 2:5020/400 07 Feb 00 10:46:46 To : All Subj : my metod 3 From: Vadim G Zabelin <landcruiser@mailcity.com> Метод можно применять для поиска всех совпадений между одним новым документом и имеющимся набором документов (словарем). В этом случае , для приведенной выше модели работы алгоритма, нижняя строка должна содержать только новый документ для которого необходимо найти повторения , а верхняя строка будет содержать имеющийся набор документов(словарь). Тогда при каждом смещении одного кольца относительно другого, в сравнении будут принимать участие только не пустые элементы нижнего кольца и те элементы верхнего кольца, под которыми есть элементы нижнего кольца, то есть участки нижнего кольца, где не размещены элементы, принимать участие не будут. Если длина нового документа N , а длина имеющегося набора документов M, то буден сделано N*M сравнений. Тот же результат может быть получен, если добавить новый документ к имеющимся, найти все повторяющиеся последовательности и отбросить результаты которые не относятся к символам нового документа. Эта схему, где ищутся совпадения для нового документа по имеющемуся набору старых документов (словарю), выгодно применять в коммуникациях, вместо стандарта V.42bis . При этом в новом документе можно найти все повторяющиеся последовательности (лучше до сравнения со старыми документами, т.е. словарем ), отбросить повторяющиеся последовательности, и добавить то что останется в набор старых документов (словарь). Тогда после этих операций, на другую часть канала передачи данных достаточно передать только информацию об изменении словаря, т.е. символы, которые надо добавить в словарь и информацию, как из получившегося словаря составить исходную последовательность символов. Метод поиска совпадений между одним документом и имеющимся набором документов является, так же методом распознавания образов. Для распознавания речи или рукописного текста, можно дважды применять этот метод: сначала на этапе распознавания самих образов (звуков и букв соответственно), потом в случае если нельзя однозначно распознать информацию можно найти совпадения в эталоне v орфографическом словаре. Таким образом, можно получить истинно самообучающуюся программу, которая с увеличением объема входной информации будет все точнее распознавать эту информацию. Вадим Забелин nic-hdl: VGZ1-RIPN nic-hdl: VGZ11-RIPE --- ifmail v.2.15dev4 * Origin: V. Zabelin Enterprises (2:5020/400) — RU.COMPRESS From : Vadim G Zabelin 2:5020/400 07 Feb 00 10:47:03 To : All Subj : my metod 4 From: Vadim G Zabelin <landcruiser@mailcity.com> Пример на C #include <stdio.h> #include <string.h> int main(argc, argv) int argc; char *argv[]; { typedef unsigned char uchar; uchar a[345001L]; unsigned long i,j,f,m,n,g,r,l; char filename[81]; FILE *datafile = NULL; FILE *result = NULL; char datafile_NAME[80]; char result_NAME[80]; strcpy(filename, argv[1]); strcpy(datafile_NAME, filename); printf("%s this file \n",filename ); datafile = fopen(datafile_NAME, "r+b"); strcpy(result_NAME, "result.txt"); result = fopen(result_NAME, "w"); i=0; while (!feof(datafile)) i+=fread(&a[i], 1, 1, datafile); fclose(datafile); datafile = NULL; /* i Number of symbols in file */ printf("%lu size of file \n",i ); /* Number of cycles which are required for search of all repeating sequences */ r=(unsigned long)(i/2); if (r*2<i) r++; printf("%lu cycles \n",r ); /* make it because the indexes begin with 0 */ n=i-1; --r; g = 2; /* Minimal length of a repeating sequence */ i = 0; j = i + g; f = j; m = 0; while (f <= r) { /* cycles n/2 */ while (i <= n) { if (a[i] == a[j]) m++; else { if (m!=0) { if (m >= g) { if (j<m) { l=n-(m-j-1); fprintf(result, "%lu %lu %lu \n", i - m, l, m); } else fprintf(result, "%lu %lu %lu \n", i - m, j - m, m); } m = 0; } } i++; if (j == n) j = 0; else j++; } if (m!=0) { if (m >= g) { if (j<m) { l=n-(m-j-1); fprintf(result, "%lu %lu %lu \n", i - m, l, m); } else fprintf(result, "%lu %lu %lu \n", i - m, j - m, m); } m = 0; } f++; j = f; i = 0; } putc('\n', result); fprintf(result, "the end \n"); fclose(result); result = NULL; return(0); } /* End. */ Пример для Borland Pascal program search; {* for MS-DOS *} uses crt, dos; var a: array [0..45000] of byte; i,j,m,n,f,g,l: integer; r: integer ; filename : string[80]; datafile : file of byte ; result: text; begin filename:= paramstr (1); assign (datafile, filename); reset(datafile); assign (result, 'result.txt'); rewrite(result); i:=0; while not EOF (datafile) do begin read (datafile, a[i]); i:=i+1 end; close (datafile); {* i Number of symbols in file *} r:=round(i/2); {* Number of cycles which are required for search of all repeating sequences *} if r*2 < i then r:=r+1; {* make it because the indexes begin with 0 *} n:=i-1; r:=r-1; g:=2; {* Minimal length of a repeating sequence *} i:=0; j:=i+g; f:=j; m:=0; while f <= r do {* n/2 *} begin while i<=n do {* *} begin if (a[i]=a[j]) then m:=m+1 else if m<>0 then begin if m>=g then if j<m then begin l:=n-(m-j-1); writeln (result, i-m, ' ', l, ' ', m , ' '); end else writeln (result, i-m, ' ', j-m, ' ', m , ' '); m:=0 end; i:=i+1; if j=n then j:=0 else j:=j+1 end; if m<>0 then begin if j<m then begin l:=n-(m-j-1); writeln (result, i-m, ' ', l, ' ', m , ' '); end else writeln (result, i-m, ' ', j-m, ' ', m , ' '); m:=0 end; f:=f+1; j:=f; i:=0 end; writeln(result); close (result) end. Вадим Забелин nic-hdl: VGZ1-RIPN nic-hdl: VGZ11-RIPE --- ifmail v.2.15dev4 * Origin: V. Zabelin Enterprises (2:5020/400)
Предыдущий блок Следующий блок Вернуться в индекс