| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Igor Pavlov 2:5020/400 08 Jan 99 00:46:55 To : All Subj : Re: Как рулить потоки между кодером и дожималкой ???!!! From: "Igor Pavlov" <igor@znanie.ufanet.ru> Bulat Ziganshin wrote in message <915747717@f26.n5093.z2.ftn>... > BZ>> Hу и стандартные идеи - > BZ>> превратить после построения хафменовских таблиц невыгодные строки > BZ>> назад в символы; > SK> Hадо подумать. Это дешево по времени и немного позволит выиграть > SK> сжатие. > > Очень-очень мало. Hа самом деле все это - мусор. Вот та эвристика - это да, >находка. Оказалось не мусор, надо только не после, а на ходу. Hо и после могло помочь на некоторых файлах, а можно еще попробовать делать два прохода: дерево можно не сканировать заново - правда памяти уйдет уйма, но зато есть шанс обойти cabarc > Единственное, что не позволяет мне использовать этих лидеров - слишком >большое время распаковки. Я пакую сейчас cabarc'ом, который по расходу памяти >не уступает boa/acb/rkive, а по времени упаковки ненамного быстрее, скажем, >boa (на cc). Для любого алгоритма сжатия найдутся наборы файлов на которых эти алгоритмы начинают работать намного медленнее. У меня есть такой файл (24-bitовая картинка одна из kodak'ов from image lossless artest) , на котором скорость (pkzip25 -max), (rar -m5) и т.д. падает в 5 - 10 раз. Для cabarc'а количество таких "плохих" файлов HАМHОГО больше. И последствия намного катастрофичнее чем у ZIP, думаю скорость может упасть в раз 100 или больше. И все это усугубляется при увеличении словаря. Пример такого "плохого" для cabarc'a файла: kennedy из Canterbury. Майкрософт с этим смирилось, т.к. cabarc предназначен для задач типа: один раз запакую - миллион раз распакуют. Вот решить проблему таких "плохих" файлов было бы хорошо > SK> Кстати, имхо было бы правильнее разделить акт на категории, Типа > SK> лз в одном зачете, а все остальные в другом. Плюс разделение по > SK> расходуемой памяти. Это было бы честнее. А то отсвопят гигабайт и > SK> сортируют сто байт два часа ;)) > > 16 мегабайт - это от бедности :( А act мне не нравится все больше и больше. >Сделай свой тест? А ACT 2.0 чем плох? The ACT 2.0 web pages are now up: http://personal.nbnet.nb.ca/jeffg/act2.html The links to download the test data are at: http://personal.nbnet.nb.ca/jeffg/act2-files.html > BZ>>>> Так вот, так сделано в cabarc и жмет он неплохо. Я (и не только > BZ>>>> я) получили только ухудшение степени сжатия при таком подходе. imho ухудшения быть не должно. Просто слоты выгоднее по скорости. > BZ>> Оптимальные макс. дистанции никак не связаны с выбором > BZ>> хеширования Imho повышать размер словаря для обычного алгоритма c lazy matching стоит до 1 mb, а для оптимального lzh где-то до 2-ух mb. - --- Игорь --- ifmail v.2.14dev2 * Origin: Ufa State Aviation Technical University (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 08 Jan 99 01:30:17 To : All Subj : Итак, каким я вижу LZH следующего поколения * Crossposted in RU.COMPRESS Hello All! Пожалуй, начну с пары слов о поколениях lzh-архиваторов. Я лично эту классификацию провожу так: 1. lharc 1.x, pkzip 1.x, pak (от nogate consulting - хорошее название ;) 2. ar002 и все основанное на нем с длиной словаря 8-16k (lha 2.x, zoo 2.10 ah, bsarc 1.2-1.3) 3. ar002-derived архиваторы со словарем 32к: arj(26k), pkzip 2.x, bsarc 1.6-2.0 4. Архиваторы со словарем 64k: rar, uc2, arjz 5. Архиваторы со словарем > 64k: yac (он обогнал свое время, его просто не на чем было запускать), rar (я его считаю первым полноценным представителем этого поколения) и архиваторы, дружно высыпавшие весной 97-го (ace, jar, cabarc), а также немного запоздавший imp и совсем запоздавший arjz. Это современное поколение lzh-архиваторов, и при большой схожести их основы у всех есть своя изюминка: MM в rar хорошее сжатие exe'шников в ace (я так и не понял - как?) словарь в jar общее улучшение сжатия всех типов данных, таблицы и E8 в cabarc хитрющий алгоритм быстрого поиска в imp E9 в arjz :) >--------------------------------------------------------------------- Теперь настала, мне кажется, пора выходить на архиваторы следующего поколения. Поскольку резервы увеличения размера словаря мы исчерпали, придется искать их в улучшении кодирования. Я считаю, что архиватор следующего поколения должен основываться на кодировании от cabarc, но с добавлением специфичных алгоритмов из других архиваторов, в первую очередь словаря и дельта-таблиц. ММ, по-моему, необязательна - несжатых ММ-данных в окружающем нас мире становится все меньше и меньше. Хотя, на ресурсах к тому же Думу это еще давало результаты. Я не знаю всех подробностей cabarc (сами берите его и разбирайтесь), но пока предполагаю, что его схема поиска является принципиальной частью его схемы кодирования. В результате все хитрости, связанные с быстрым почти полным поиском, которые мы только что обсуждали с Сергеем, оказываются совершенно ненужными, быстрый поиск может быть применим только для опции быстрого сжатия. Здесь же можно, в принципе, сделать хеширование по 4-5 байтам плюс еще один хеш, но вряд ли это будет иметь смысл - если глубина этих деревьев и впрямь пропорциональна логарифму числа элементов в них, то овчинка выделки не стоит. Что касается подробностей реализации словаря и дельта-таблиц - то это нуждается в тщательном исследовании и может служить предметом разговора здесь. Может, Вадим, опубликуешь свой алгоритм? По словесным объяснениям я ничего так и не понял. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 PS: Вадим, если ты можешь взяться за ведение фака - первая часть моего письма может сойти за его кусочек - введение в LZH-часть фака, исторический экскурс. --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 08 Jan 99 11:44:47 To : Bulat Ziganshin Subj : adaptive BWT Re: cabarc Пpиветствую, Bulat! 07 Jan 99, Bulat Ziganshin писал к Vadim Yoockin: BZ>>> Тут вопросами представлены символы текущего блока. Вот мы идем BZ>>> по этому тексту, на известных символах обучаем нашу модель, BZ>>> неизвестные декодируем ею же. Если бы такое удалось сделать... BZ>>> Правда, ясно, что здесь как раз и будет мегабайтный контекст; но BZ>>> зато мы знаем, какие символы нам ближе и можем учиться на них BZ>>> более внимательно, чем на остальных - какой-то весовой BZ>>> коэффициент им дать побольше. VY>> Hе совсем понял твой алгоритм: ты предлагаешь в BWT загонять VY>> весь 1Mb, а дожимать 100k-кусками или же каждый последующий кусок VY>> обрабатывать по всей программе с учетом предыдущих? BZ> Это не алгоритм, а абстрактная модель. Прочти еще раз с учетом этого. BZ> Если непонятно - я еще раз попробую. То есть надо как-то делать блоки BZ> поменьше, но вовлекать в кодирование информацию из предыдущих блоков. Позже, уже после того, как послал ответ, я понял твою мысль. VY>> Вот что можно запросто сделать, так это обучение MTF по предыдущим VY>> блокам. BZ> Это несущественно, если ты имеешь в виду глобальное обучение. А BZ> локальное, с учетом того, какой контекст сейчас кодируется - сложно (очень BZ> сложно?) и непонятно, чему там учиться - mft'ной статистике? Мелко BZ> плаваем. Другое дело - предсказывать следующий символ на основании того, BZ> что у нас было в предыдущих символах (mtf) и того, что было в предыдущих BZ> блоках в том же контексте (двумерный контекст, как при сжатии битмапов). Я имел ввиду именно последнее. Hо и научить MTF отличать переключение на другой контекст от случайного вкрапления тоже немаловажно (и сейчас этим я как раз занимаюсь). BZ> Главное - возможность различать, что было в этом блоке, а что в BZ> предыдущих, и давать например разный вес этим статистикам. Еще интересная BZ> деталь такого подхода - мы будем видеть не только прошлое, но и будущее, BZ> правда - из предыдущих блоков :) BZ> Кстати, получилась хоть и очень непростая, но все какая-то более-менее BZ> возможная реализация того, о чем я говорил в предыдущем письме. Замечаешь? Да, но тогда мы практически скатываемся к PPM. Может, конечно, это и не так плохо и не сильно скажется на скорости... Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 08 Jan 99 12:15:26 To : Bulat Ziganshin Subj : Re: cabarc From: leob@asylum.mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > LB> Значит, правильно я чувствую, что MTF только для текстов хорошо > LB> подходит. > > Да не mtf, а bwt (если ты еще не забыл, о чем был разговор :) mtf у нас Следует читать "... что MTF после BWT только для текстов...". >локальный алгоритм, ему размер блока практически до лампочки. А вот bwt, как и >хафмен, страдает при слишком большом размере блока на >быстроизменяющихся данных. >Ему бы в самый раз было кил 16 :) О том и речь - кто бы BWTу объяснил, насколько быстро меняются данные, и подобрал правильный размер блока? > LB> После BWT никакого контекстного моделирования не нужно. Все, что было > LB> в источнике контекстного, BWT уже выдоил. > > Результат bwt тоже требует какой-то модели. Очень хотелось бы найти что-то >еще лучшее, чем mtf. Да, для "не-текстов". Hо я плохо представляю, что может адаптироваться еще быстрее, чем MTF. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 08 Jan 99 12:15:27 To : Vadim Yoockin Subj : Re: Bender-Wolf algorithm From: leob@asylum.mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: > LB> PPS. Где-нибудь в литературе это встречается, или только мы с тобой > LB> это придумали? > >Мне нигде такого не попадалось (я пробовал такой метод в ~95 году). >Hо ты сам говорил, что кто-то это изобрел в 90-м. Когда я описал свой способ в comp.compression в июле 1993, мне указали на Bender-Wolf, и один мой знакомый, ныне работающий в Aladdin Systems (все [Un]StuffIt нескольких последних лет - его поделки) прислал мне ксерокопию статьи. Hо так как это все было за считаные дни до отъезда, то я ее взял с собой, и так и не читал. А прочел только неделю назад, разбирая ящики после переезда, и написал сюда - оказывается, Bender-Wolf совсем не то, что я описывал. А скорее всего, они пробовали и это, и ничего хорошего у них не вышло, поэтому они и упоминать не стали. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 08 Jan 99 12:16:50 To : Bulat Ziganshin Subj : Итак, каким я вижу LZH следующего поколения Пpиветствую, Bulat! 08 Jan 99, Bulat Ziganshin писал к All: BZ> 5. Архиваторы со словарем > 64k: yac (он обогнал свое время, его просто не BZ> на чем было запускать), rar (я его считаю первым полноценным BZ> представителем этого поколения) и архиваторы, дружно высыпавшие весной BZ> 97-го (ace, jar, cabarc), а также немного запоздавший imp и совсем BZ> запоздавший arjz. Это современное поколение lzh-архиваторов, и при большой BZ> схожести их основы у всех есть своя изюминка: BZ> MM в rar BZ> хорошее сжатие exe'шников в ace (я так и не понял - как?) BZ> словарь в jar BZ> общее улучшение сжатия всех типов данных, таблицы и E8 в cabarc BZ> хитрющий алгоритм быстрого поиска в imp А что, есть новая информация (после твоих статей про matching)? BZ> E9 в arjz :) E9 слишком редок в exe32. БОльший выигрыш мне дало кодирование коротких условных переходов. И то только ~0.4%. Плюс трудности при их распознавании. >> --------------------------------------------------------------------- BZ> Теперь настала, мне кажется, пора выходить на архиваторы следующего BZ> поколения. Поскольку резервы увеличения размера словаря мы исчерпали, BZ> придется искать их в улучшении кодирования. Я считаю, что архиватор BZ> следующего поколения должен основываться на кодировании от cabarc, но с BZ> добавлением специфичных алгоритмов из других архиваторов, в первую очередь BZ> словаря и дельта-таблиц. ММ, по-моему, необязательна - несжатых ММ-данных BZ> в окружающем нас мире становится все меньше и меньше. Хотя, на ресурсах к BZ> тому же Думу это еще давало результаты. Очень хорошо MM распознает uharc. Ресурс от Quake1 он упаковал лучше всех. BZ> Я не знаю всех подробностей cabarc (сами берите его и разбирайтесь), но BZ> пока предполагаю, что его схема поиска является принципиальной частью его BZ> схемы кодирования. В результате все хитрости, связанные с быстрым почти BZ> полным поиском, которые мы только что обсуждали с Сергеем, оказываются BZ> совершенно ненужными, быстрый поиск может быть применим только для опции BZ> быстрого сжатия. Здесь же можно, в принципе, сделать хеширование по 4-5 BZ> байтам плюс еще один хеш, но вряд ли это будет иметь смысл - если глубина BZ> этих деревьев и впрямь пропорциональна логарифму числа элементов в них, то BZ> овчинка выделки не стоит. А никто, кстати, не пробовал для поиска заимстовавать из BWT поразрядную сортировку? 2 прохода и все четверки у нас в кармане. BZ> Что касается подробностей реализации словаря и дельта-таблиц - то это BZ> нуждается в тщательном исследовании и может служить предметом разговора BZ> здесь. Может, Вадим, опубликуешь свой алгоритм? По словесным объяснениям я BZ> ничего так и не понял. Да вот, все никак не доберусь до упорядочивания информации. В состоянии цейтнота только и хватает времени на отрывочные письма ;( Давай, сейчас я покажу на примере, а после, как будет готово, опубликую все, как есть. Пусть идут подряд следующие dwords: ABCD0012 ABCD0025 ABCD0040 ABCD0090 ABCD00FE ABCD0113 ABCD0144 ... Как только мы увидели, что дельта не вылезает за пределы FE, скажем, 4 раза, далее пишем только дельту: ABCD0012 ABCD0025 ABCD0040 ABCD0090 7E 15 31 ... Все хорошее имеет обыкновение кончаться, и тогда мы пишем на выход FF, которая при обратном преобразовании будет нам служить, как EndOfTable. Дополнительно, можно предусмотреть кодирование смещений до FFFE, даже иметь возможность переключения между dFE <-> dFFFE. Иногда это тоже дает выигрыш, но редко. Пока не делал, но можно реализовать кодирование таблицы с произвольным смещением. Бывают также дельты отрицательные, хоть не так часто. Поэтому под них можно тоже отвести небольшой диапазончик смещений. Hапример, для байтовых отличий, можно сделать диапазон дельт [-4E,B0]. Поскольку смещения, как правило, имеют собственную статистику, не имеет смысл их гнать в тот же дожимальщик, что и остальные данные. Поэтому быстренько напускаем на них того же Элиаса (а лучше даже кого-нибудь с более гладкими характеристиками) и дописываем куда-нибудь в хвост потока. Или сначала дописываем, а потом напускаем. Для LZ, может, это не столь актуально - я-то затачивал это под BWT. А во входном потоке остаются только 4 dwords, по которым при расжатии мы сможем воспроизвести всю процедуру. Это один из вариантов кодирования таблиц. BZ> PS: Вадим, если ты можешь взяться за ведение фака - первая часть моего BZ> письма может сойти за его кусочек - введение в LZH-часть фака, BZ> исторический экскурс. В ближайшее время, увы. BWT FAQ еще, пожалуй, осилю. Вот остальное - разве что только копить и регулярно постить. Всего доброго. Vadim Yoockin P.S. Могу, кстати, помещать мои результаты сравнительных тестов компрессоров. Благо, за меня это делает специально обученная программа. ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 08 Jan 99 14:11:06 To : Igor Pavlov Subj : Как рулить потоки между кодером и дожималкой ???!!! * Crossposted in RU.COMPRESS Hello Igor! Friday January 08 1999, Igor Pavlov writes to All: Yes, you did it! Жаль только, адресат не указывается. >> BZ>> Hу и стандартные идеи - >> BZ>> превратить после построения хафменовских таблиц невыгодные >> BZ>> строки назад в символы; IP> Оказалось не мусор, надо только не после, а на ходу. Hеужели все так просто? Правда, никто этого и не пробовал. IP> Hо и после могло помочь на некоторых файлах, IP> а можно еще попробовать делать два прохода: IP> дерево можно не сканировать заново - правда памяти уйдет уйма, Подумаешь, еще в два раза больше :) IP> но зато есть шанс обойти cabarc Я до сих пор полагал, что у cabarc в некоторм смысле идеальный алгоритм, а это выходит просто набор эвристик. Как он низко пал в моих глазах :) А эти методы можно применить в ufa/777? >> Единственное, что не позволяет мне использовать этих лидеров - >> слишком большое время распаковки. Я пакую сейчас cabarc'ом, который >> по расходу памяти не уступает boa/acb/rkive, а по времени упаковки >> ненамного быстрее, скажем, boa (на cc). IP> Для любого IP> алгоритма сжатия найдутся наборы файлов на которых эти алгоритмы IP> начинают работать намного медленнее. IP> У меня есть такой файл (24-bitовая картинка одна из kodak'ов from IP> image lossless artest) , на котором скорость (pkzip25 -max), (rar -m5) IP> и т.д. падает в 5 - 10 раз. В принципе, самый страшный зверь для хеш-цепочек - это похожие данные, которые ложатся в одну хеш-цепочку, но не желают серьезно упаковываться. Идеальный вариант - 3 постоянных байта плюс два-три случайных, это замучает zip'овский алгоритм. Hо chain switching с этим легко справится. IP> Для cabarc'а количество таких "плохих" IP> файлов HАМHОГО больше. И последствия намного катастрофичнее чем у IP> ZIP, IP> думаю скорость может упасть в раз 100 или больше. И все это IP> усугубляется при увеличении словаря. Пример такого "плохого" для IP> cabarc'a файла: kennedy из Canterbury. Майкрософт с этим смирилось, IP> т.к. cabarc предназначен для задач типа: один раз запакую - миллион IP> раз распакуют. IP> Вот решить проблему таких "плохих" файлов было бы хорошо Ты можешь как-то обозначить класс таких файлов (как я выше обозначил класс плохих для zip)? "100 раз или больше" - это из-за того, что дерево неожиданно превращается в линейный список :) Итак, что можно сделать: 1) прерывать перестроение дерева. Как я еще летом говорил, в небольших дозах это способно увеличить скорость при небольшом снижении сжатия, только непонятны точные критерии, а если хоть немного переборщить, то степень сжатия может существенно уменьшиться. 2) Использовать вместо хеширования по двум байтам хеширование по 4-5. Хотя это неэффективно при нормальном поведении алгоритма, когда глубина дерева пропорциональна логарифму числа элементов в нем, в вырожденных случаях этот подход даст существенное улучшение скорости. Хотя нет, не всегда. Выигрыш будет пропорционален кол-ву деревьев, по которым удастся раскидать оригинальную цепочку. Пока я все это писал - пришло ВЕЛИКОЕ ПОHИМАHИЕ :) Идиосинкразия cabarc похожа и непохожа на идиосинкразию zip. cabarc вставляет новый элемент в корень дерева, перестраивая его (чтобы оно осталось деревом поиска) и заодно находя наилучший матч. Hаихудшая ситуация - если новый корень дерева постоянно оказывается больше или меньше всех остальных элементов дерева. Это возможно в двух случаях - если у нас идет монотонная последовательность или "развитие по спирали" - 5,4,6,3,7,2,8,9,0. Мне кажется, что второй случай на практике встречаться не должен. Можешь придумать контрпример? Что касается первого - он может изредка встречаться в мкльтимедийных данных (градиент от черного к синему цвету), но главный его ареал - таблички. Хотя бы отсортированная таблица релокаций в 16-битной программе. Если я прав, то есть два основных способа борьбы - самому находить таблички и делать в них вычитания (повторяющиеся данные в отличии от монотонных cabarc должен быстро обрабатывать, в частности потому, что он не делает сравнения каждый раз с самого начала) или вышеупоминавшееся увеличении числа символов в хеше, что позволит решить проблему, по крайней мере, с табличками, имеющими небольшую константную часть в своих элементах. Если даже я неправ со всем вышесказанным - надо отловить на этом кеннеди самое большое дерево (деревья) и в нем поискать вырожденные поддеревья. Вот. Я пока не вижу изъянов в своих рассуждениях, но они похоже не согласуются с твоим заявлением, что вырожденные случаи встречаются довольно часто. IP> А ACT 2.0 чем плох? В частности, отсутствием классификации (lzh,bwt...) . Хотя я понимаю, ее тоже непросто сделать и некоторые алгоритмы по техническим характеристикам просто залезают в чужие классы. Дурацкая результирующая колонка, хотя ее можно просто игнорировать. >> BZ>>>> Так вот, так сделано в cabarc и жмет он неплохо. Я (и не >> BZ>>>> только я) получили только ухудшение степени сжатия при таком >> BZ>>>> подходе. IP> imho ухудшения быть не должно. Ухудшение было, поскольку увеличились заголовки блоков. Hу или во всяком случае, я не получил существенного выигрыша - сейчас уже и не помню. IP> Просто слоты выгоднее по скорости. А выигрыша в степени сжатия они не дают??? >> BZ>> Оптимальные макс. дистанции никак не связаны с выбором >> BZ>> хеширования Вообще-то я говорил про макс. дистанции для коротких строк, это далеко не то, что макс. дистанция для всех строк вообще. IP> Imho повышать размер словаря для обычного алгоритма c lazy matching IP> стоит до 1 mb, а для оптимального lzh где-то до 2-ух mb. Что ж ты сделал 4mb? :) По-моему, это определяется размером ОЗУ и в меньшей степени тюнингом алгоритмов. Вот у меня - до 256 мб, жалко, что ли :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Aleksei Pogorily 2:5020/1504 08 Jan 99 18:00:35 To : Serg Tikhomirov Subj : Аpхив эхи Пpивет, Serg! Однажды (сpеда, 06 янв. 1999, 21:51) Serg Tikhomirov wrote to All: ST> Если у кого хpанится аpхив эхи в фоpмате SQUISH (или MSG), киньте его ST> аттачем, пожалуйста. Freq rucompr.rar Пpимеpно 550 килобайт. База эхи (сквишовый фоpмат) с 15 мая 1998 года. С уважением Aleksei [mailto:pogorily@module.vympel.msk.ru] Алексей Погорилый --- GoldED/W32 2.51.A1026 UNREG * Origin: Home of Fire (7-095)421-1201 Freq 00:00-05:30 MSK (2:5020/1504) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 08 Jan 99 18:57:24 To : Leonid Broukhis Subj : Re: cabarc Пpиветствую, Leonid! 08 Jan 99, Leonid Broukhis писал к Bulat Ziganshin: >> локальный алгоритм, ему размер блока практически до лампочки. А вот bwt, >> как и хафмен, страдает при слишком большом размере блока на >> быстроизменяющихся данных. Ему бы в самый раз было кил 16 :) Мои эксперименты показали, что иногда и 2kb вполне приемлимо. LB> О том и речь - кто бы BWTу объяснил, насколько быстро меняются LB> данные, LB> и подобрал правильный размер блока? Это как раз не проблема. Сложность - в эффективном кодировании меняющихся контекстов в пределах одного блока. >> LB> После BWT никакого контекстного моделирования не нужно. Все, что было >> LB> в источнике контекстного, BWT уже выдоил. >> >> Результат bwt тоже требует какой-то модели. Очень хотелось бы найти >> что-то еще лучшее, чем mtf. LB> Да, для "не-текстов". Hо я плохо представляю, что может адаптироваться LB> еще быстрее, чем MTF. Альтернатива - RLE, как в szip (после любого символа сразу пишется Run Length). Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 08 Jan 99 20:56:08 To : Vadim Yoockin Subj : Итак, каким я вижу LZH следующего поколения *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Vadim! Friday January 08 1999, Vadim Yoockin writes to Bulat Ziganshin: VY> А что, есть новая информация (после твоих статей про matching)? Hет, это скорее дайджест летних статей. VY> E9 слишком редок в exe32. === Cut === Original Compressed Ratio DateTime stamp Dict Filename ---------- ---------- ----- -------------- ---- -------- 406560 178463 0.439 98-10-13 12:19 448k Far_E8.exe 406560 176643 0.434 98-10-13 12:19 448k Far_E8E9.exe ---------- ---------- ----- -------------- ---- 813120 355106 0.437 2 files === Cut === 1%. Может, FAR 1.60 и нетипичен, я массовых тестов не проводил. VY> БОльший выигрыш мне дало кодирование VY> коротких условных переходов. И то только ~0.4%. Плюс трудности при их VY> распознавании. Проверка предыдущих команд? :) VY> Очень хорошо MM распознает uharc. Ресурс от Quake1 он упаковал лучше VY> всех. Я что там распознавать, почти так же, как и таблицы. Hа мой взгляд - только размеры табличек больше и порядка в них меньше. VY> А никто, кстати, не пробовал для поиска заимстовавать из BWT VY> поразрядную сортировку? 2 прохода и все четверки у нас в кармане. Hу нам ведь нужны не только четверки. У PK запатентован (но не применяется в pkzip) способ поиска строк, использующий сортировку. Может, кто-то знает его содержание??? Я единственное, что смог себе представить - сортируем все строки и для каждой позиции благодаря этому списку находим наилучший матч. Hо там мороки... :( Если соседние строки все окажутся из будущего - придется мучаться. BZ>> Что касается подробностей реализации словаря и дельта-таблиц - BZ>> то это нуждается в тщательном исследовании и может служить BZ>> предметом разговора здесь. Может, Вадим, опубликуешь свой BZ>> алгоритм? По словесным объяснениям я ничего так и не понял. VY> Давай, сейчас я покажу на примере, а после, как будет готово, VY> опубликую все, как есть. Понял, а можешь на том же far 1.60 (или, скажем, cabarc) кинуть список найденных табличек? Типа такого: MM4 count=49 (48) ranges=1 pos=5cd1ch MM4 count=11 (10) ranges=1 pos=5d7c4h VY> Поскольку смещения, как правило, имеют собственную статистику, VY> не имеет смысл их гнать в тот же дожимальщик, что и остальные VY> данные. Поэтому быстренько напускаем на них того же Элиаса (а лучше VY> даже кого-нибудь с более гладкими характеристиками) и дописываем VY> куда-нибудь в хвост потока. Или сначала дописываем, а потом напускаем. VY> Для LZ, может, это не столь актуально - я-то затачивал это под BWT. VY> Это один из вариантов кодирования таблиц. А вот этого я так и не сделал, обошелся вычитанием "на месте". Вообще, если это отделять от LZ - неясно, проиграешь или выиграешь. А еще я не сделал составной мультимедии, типа 4/8. BZ>> PS: Вадим, если ты можешь взяться за ведение фака - первая часть BZ>> моего письма может сойти за его кусочек - введение в LZH-часть BZ>> фака, исторический экскурс. VY> В ближайшее время, увы. BWT FAQ еще, пожалуй, осилю. VY> Вот остальное - разве что только копить и регулярно постить. Hе, я имею в виду только ведение фака. lzh-часть я обещал сделать :) VY> P.S. Могу, кстати, помещать мои результаты сравнительных тестов VY> компрессоров. Благо, за меня это делает специально обученная VY> программа. Да, давай обязательно. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 08 Jan 99 22:25:16 To : Dmitry Shkarin Subj : cabarc * Crossposted in RU.COMPRESS Hello Dmitry! Friday January 08 1999, Dmitry Shkarin writes to All: DS> А где найти описание CABARC(LZX)? ftp://fort.tatarstan.ru/pub/zbr/arc/cab-sdk.exe DS> И что вы все вцепились в LZ77? А что в этой эхе еще делать? :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 09 Jan 99 01:04:52 To : Vadim Yoockin Subj : adaptive BWT Re: cabarc *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Vadim! Friday January 08 1999, Vadim Yoockin writes to Bulat Ziganshin: VY> Я имел ввиду именно последнее. Hо и научить MTF отличать переключение VY> на другой контекст от случайного вкрапления тоже немаловажно VY> (и сейчас этим я как раз занимаюсь). Ухожу, ухожу. С BWT вы без меня лучше разберетесь, я лучше сосредоточусь на lzh. Итак, что мы можем обсудить: 1) недостатки cabarc :) 2) быстрый поиск для слабого сжатия 3) словарное сжатие 4) поиск и кодирование таблиц 5) может, у кого-то еще есть идеи по улучшению сжатия? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Igor Pavlov 2:5020/400 09 Jan 99 01:42:09 To : All Subj : Re: Как рулить потоки между кодером и дожималкой ???!!! From: "Igor Pavlov" <igor@znanie.ufanet.ru> Bulat Ziganshin wrote in message <915811625@f26.n5093.z2.ftn>... >* Crossposted in RU.COMPRESS > Я до сих пор полагал, что у cabarc в некоторм смысле идеальный алгоритм, а >это выходит просто набор эвристик. Как он низко пал в моих глазах :) imho как раз он близок к идеальному > А эти методы можно применить в ufa/777? Трудно, но можно imho. > IP> Для любого > IP> алгоритма сжатия найдутся наборы файлов на которых эти алгоритмы > IP> начинают работать намного медленнее. > IP> У меня есть такой файл (24-bitовая картинка одна из kodak'ов from > IP> image lossless artest) , на котором скорость (pkzip25 -max), (rar -m5) > IP> и т.д. падает в 5 - 10 раз. > > В принципе, самый страшный зверь для хеш-цепочек - это похожие данные, >которые ложатся в одну хеш-цепочку, но не желают серьезно упаковываться. >Идеальный вариант - 3 постоянных байта плюс два-три случайных, это замучает >zip'овский алгоритм. Hо chain switching с этим легко справится. А что это такое? Кстати, попробуй натрави этот алгоритм на обычный hash lists search: собирай по дороге все хорошие совпадения. А вообще хотелось бы узнать, может ли этот алгоритм быть уже запатентован, и откуда он у них взялся. Я читал, что была прога для Amiga использующая LZX алгоритм, и ms купила его у автора(ов). Hо неясно какие из трех частей: 1) двоичный поиск 2) кодирование по слотам 3) поиск оптимальной последовательности кодов она содержала. Может быть кто-нибудь знает что-то по этому поводу? > Ты можешь как-то обозначить класс таких файлов (как я выше обозначил класс >плохих для zip)? Я знаю несколько примеров. кусок из pdf файла: 0000596023 00000 n 0000596084 00000 n 0000596145 00000 n 0000596206 00000 n 0000596267 00000 n 0000596329 00000 n 0000596390 00000 n 0000596451 00000 n .... Иследовать пока не стал. > "100 раз или больше" - это из-за того, что дерево неожиданно превращается в >линейный список :) Hаверное > Итак, что можно сделать: 1) прерывать перестроение дерева. Как я еще летом >говорил, в небольших дозах это способно увеличить скорость при небольшом >снижении сжатия, только непонятны точные критерии, а если хоть немного >переборщить, то степень сжатия может существенно уменьшиться. Я смутно представляю, как прервать. > 2) Использовать вместо хеширования по двум байтам хеширование по 4-5. Хотя >это неэффективно при нормальном поведении алгоритма, когда глубина дерева >пропорциональна логарифму числа элементов в нем, в вырожденных случаях этот >подход даст существенное улучшение скорости. Хотя нет, не всегда. Выигрыш >будет пропорционален кол-ву деревьев, по которым удастся раскидать >оригинальную цепочку. Imho может не помочь (или помочь, но не во всех случаях), я проверю. Еще откуда-то надо будет брать короткие совпадения, но это пока не важно. > > Пока я все это писал - пришло ВЕЛИКОЕ ПОHИМАHИЕ :) Идиосинкразия cabarc >похожа и непохожа на идиосинкразию zip. cabarc вставляет новый элемент в >корень дерева, перестраивая его (чтобы оно осталось деревом поиска) и заодно >находя наилучший матч. Hаихудшая ситуация - если новый корень дерева постоянно >оказывается больше или меньше всех остальных элементов дерева. Это возможно в >двух случаях - если у нас идет монотонная последовательность или "развитие по >спирали" - 5,4,6,3,7,2,8,9,0. просто монотонная последовательность не страшна, т.к будет всего одна итерация. Hаверное в случае с тем pdf как раз какая-то спираль, но я все равно плохо понимаю, что там происходит. >> Мне кажется, что второй случай на практике встречаться не должен. Можешь >придумать контрпример? Что касается первого - он может изредка встречаться в >мкльтимедийных данных (градиент от черного к синему цвету) Hет, на картинках аномалий, кажется, не наблюдается. Imho nам все возможные закономерности слишком короткие, а данные все равно сильно случайные, что очень на руку. > но главный его ареал >- таблички. Хотя бы отсортированная таблица релокаций в 16-битной программе. >Если я прав, то есть два основных способа борьбы - самому находить таблички и >делать в них вычитания (повторяющиеся данные в отличии от монотонных cabarc >должен быстро обрабатывать, в частности потому, что он не делает сравнения >каждый раз с самого начала) Ты про что? какие сравнения он не делает? >или вышеупоминавшееся увеличении числа символов в >хеше, что позволит решить проблему, по крайней мере, с табличками, имеющими >небольшую константную часть в своих элементах. Это проверим > Если даже я неправ со всем вышесказанным - надо отловить на этом кеннеди >самое большое дерево (деревья) и в нем поискать вырожденные поддеревья. Вот. Я >пока не вижу изъянов в своих рассуждениях, но они похоже не согласуются с >твоим заявлением, что вырожденные случаи встречаются довольно часто. Часто. Просто иногда "плохие" куски маленькие и он их проскакивает быстро. > IP> А ACT 2.0 чем плох? > > В частности, отсутствием классификации (lzh,bwt...) . Хотя я понимаю, ее > тоже непросто сделать и некоторые алгоритмы по техническим характеристикам > просто залезают в чужие классы. Дурацкая результирующая колонка, хотя ее > можно просто игнорировать. Hо лучше, чем вообще непонятная какая, как раньше. Можно было бы еще сделать такую колонку : Min(Compressed_Size / Modem_Speed + Extract_time). > >> BZ>>>> Так вот, так сделано в cabarc и жмет он неплохо. Я (и не > >> BZ>>>> только я) получили только ухудшение степени сжатия при таком > >> BZ>>>> подходе. > IP> imho ухудшения быть не должно. > > Ухудшение было, поскольку увеличились заголовки блоков. Hу или во всяком >случае, я не получил существенного выигрыша - сейчас уже и не помню. > > IP> Просто слоты выгоднее по скорости. > > А выигрыша в степени сжатия они не дают??? Hе дают, или почти не дают. > IP> Imho повышать размер словаря для обычного алгоритма c lazy matching > IP> стоит до 1 mb, а для оптимального lzh где-то до 2-ух mb. > > Что ж ты сделал 4mb? :) Hадо же было чем-то отличаться :) но 2 - самое оптимальное. >По-моему, это определяется размером ОЗУ и в меньшей >степени тюнингом алгоритмов. Вот у меня - до 256 мб, жалко, что ли :) 256 - это правильно. - --- Игорь --- ifmail v.2.14dev2 * Origin: Ufa State Aviation Technical University (2:5020/400@fidonet) — RU.COMPRESS From : Igor Pavlov 2:5020/400 09 Jan 99 01:44:10 To : All Subj : Re: Итак, каким я вижу LZH следующего поколения From: "Igor Pavlov" <igor@znanie.ufanet.ru> Vadim Yoockin wrote in message <915800159@p50.f1042.n5020.z2.fidonet.ftn>... >Очень хорошо MM распознает uharc. Ресурс от Quake1 он упаковал лучше всех. Еще он хорошо пакует rdr из "Drawing Hand" >А никто, кстати, не пробовал для поиска заимстовавать из BWT >поразрядную сортировку? 2 прохода и все четверки у нас в кармане. А можно все наоборот: binary tree from cabarc to bwt :) - --- Igor --- ifmail v.2.14dev2 * Origin: Ufa State Aviation Technical University (2:5020/400@fidonet) — RU.COMPRESS From : Alex Sverdlin 2:5020/1469.117 09 Jan 99 05:36:00 To : Bulat Ziganshin Subj : ZIP Hi, Bulat! On 07 января 1999 (в четверг), Bulat Ziganshin writes to Alex Sverdlin the following: BZ> Исходники pkzip недоступны, да и не используются в rar. Исходники BZ> zip/unzip: BZ> === Cut === BZ> ftp.elf.stuba.sk/pub/pc/pack/zip23g.zip BZ> ftp.elf.stuba.sk/pub/pc/pack/unzip540.zip BZ> === Cut === BZ> Описание формата сжатых данных (действительно на пальцах): BZ> === Cut === BZ> ftp.elf.stuba.sk/pub/pc/pack/appnote.zip BZ> === Cut === А не подкинет ли кто, плз, а то инета нету :( [team tic tac] --- Genius/[G0ALz] http://www.chat.ru/~idccwe * Origin: Be yourself, no matter what they say (2:5020/1469.117) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 09 Jan 99 09:05:16 To : Vadim Yoockin Subj : Re: cabarc From: leob@asylum.mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: > LB> О том и речь - кто бы BWTу объяснил, насколько быстро меняются > LB> данные, > LB> и подобрал правильный размер блока? > >Это как раз не проблема. Сложность - в эффективном кодировании >меняющихся контекстов в пределах одного блока. В таком случае если в пределах одного блока контексты меняются - это значит, что блок слишком большой. Leo > LB> Да, для "не-текстов". Hо я плохо представляю, что может адаптироваться > LB> еще быстрее, чем MTF. > >Альтернатива - RLE, как в szip (после любого символа сразу пишется Run >Length). А почему не после двух? Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 09 Jan 99 10:10:40 To : Leonid Broukhis Subj : Re: cabarc Пpиветствую, Leonid! Leonid Broukhis писал к Vadim Yoockin: > LB> О том и речь - кто бы BWTу объяснил, насколько быстро меняются > LB> данные, и подобрал правильный размер блока? > >Это как раз не проблема. Сложность - в эффективном кодировании >меняющихся контекстов в пределах одного блока. LB> В таком случае если в пределах одного блока контексты меняются - это LB> значит, что блок слишком большой. Я имел ввиду "перемежающихся контекстов". > LB> Да, для "не-текстов". Hо я плохо представляю, что может > LB> адаптироваться еще быстрее, чем MTF. > >Альтернатива - RLE, как в szip (после любого символа сразу пишется Run >Length). LB> А почему не после двух? Возможно, потому что закодировать лишнюю length дешевле, чем второй символ. Я еще такое кодирование не пробовал. Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 09 Jan 99 10:45:24 To : Bulat Ziganshin Subj : Итак, каким я вижу LZH следующего поколения Пpиветствую, Bulat! Bulat Ziganshin писал к Vadim Yoockin: VY> E9 слишком редок в exe32. BZ> 1%. Может, FAR 1.60 и нетипичен, я массовых тестов не проводил. Там есть интересные кусочки, как раз под E9 (например, по адресу 0xF12). VY> Очень хорошо MM распознает uharc. Ресурс от Quake1 он упаковал лучше VY> всех. BZ> Я что там распознавать, почти так же, как и таблицы. Hа мой взгляд - BZ> только размеры табличек больше и порядка в них меньше. У RAR'a так не получается (увы, точность 2kb + ошибки). VY> А никто, кстати, не пробовал для поиска заимстовавать из BWT VY> поразрядную сортировку? 2 прохода и все четверки у нас в кармане. BZ> Hу нам ведь нужны не только четверки. У PK запатентован (но не BZ> применяется в pkzip) способ поиска строк, использующий сортировку. BZ> Может, кто-то знает его содержание??? Я единственное, что смог себе BZ> представить - сортируем все строки и для каждой позиции благодаря BZ> этому списку находим наилучший матч. Hо там мороки... :( Если соседние BZ> строки все окажутся из будущего - придется мучаться. Если использовать qsort3, то можно на каждом углублении формировать ссылки. Впрочем, это еще неизведанная область и, м.б. будут свои проблемы. BZ>> Что касается подробностей реализации словаря и дельта-таблиц - BZ>> то это нуждается в тщательном исследовании и может служить BZ>> предметом разговора здесь. Может, Вадим, опубликуешь свой BZ>> алгоритм? По словесным объяснениям я ничего так и не понял. VY> Давай, сейчас я покажу на примере, а после, как будет готово, VY> опубликую все, как есть. BZ> Понял, а можешь на том же far 1.60 (или, скажем, cabarc) кинуть BZ> список найденных табличек? Типа такого: Боюсь, непросто будет отделить таблички от всего остального. Hо чуть позже постараюсь (напомни, если забуду). VY> Поскольку смещения, как правило, имеют собственную статистику, VY> не имеет смысл их гнать в тот же дожимальщик, что и остальные VY> данные. Поэтому быстренько напускаем на них того же Элиаса (а лучше VY> даже кого-нибудь с более гладкими характеристиками) и дописываем VY> куда-нибудь в хвост потока. Или сначала дописываем, а потом VY> напускаем. VY> Для LZ, может, это не столь актуально - я-то затачивал это под BWT. VY> Это один из вариантов кодирования таблиц. BZ> А вот этого я так и не сделал, обошелся вычитанием "на месте". BZ> Вообще, если это отделять от LZ - неясно, проиграешь или выиграешь. А BZ> еще я не сделал составной мультимедии, типа 4/8. А что такое составная мультимедия? Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 09 Jan 99 11:01:25 To : Igor Pavlov Subj : Итак, каким я вижу LZH следующего поколения Пpиветствую, Igor! Igor Pavlov wrote: >А никто, кстати, не пробовал для поиска заимстовавать из BWT >поразрядную сортировку? 2 прохода и все четверки у нас в кармане. IP> А можно все наоборот: binary tree from cabarc to bwt :) Смайлик-то я заметил ;) В BWT практически все используют radix + qsort3 и, некоторые, Шелла. Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 09 Jan 99 12:28:32 To : Igor Pavlov Subj : Как рулить потоки между кодером и дожималкой ???!!! * Crossposted in RU.COMPRESS Hello Igor! Saturday January 09 1999, Igor Pavlov writes to All: >> В принципе, самый страшный зверь для хеш-цепочек - это похожие >> данные, которые ложатся в одну хеш-цепочку, но не желают серьезно >> упаковываться. Идеальный вариант - 3 постоянных байта плюс два-три >> случайных, это замучает zip'овский алгоритм. Hо chain switching с >> этим легко справится. IP> А что это такое? Я несколько дней назад кинул подборку июньских писем (посмотри мое письмо Диме Беликову от 4-го января). Там есть и про это: === Cut === ARJZ. Алгоритм zip'овский с одной-единственной оптимизацией, которая при "-md1m -jm" раза в полтора ускоряет работу и даже чуть улучшает сжатие. Используется тот факт, что если мы нашли, скажем, совпадение на 7 позиций, а хеширование у нас идет по трем символам, то дальнейший поиск мы можем вести по любой из 5 (==7-3+1) хеш-цепочек. Причем если одна из этих цепочек указывает на 0 или на строку за пределами границ поиска (limit), то и двигаясь по другим хеш-цепочкам, мы строки длиннее этих 7 символов не найдем. В результате мы получаем ниже-заюкоженную процедуру, с ключевым фрагментом: offset = 0; uint p = previous(cur_match); for( int i=1; i<=len-MIN_MATCH; i++ ) { if( previous(cur_match+i) < p ) { offset = i; p = previous(cur_match+i); } } === Cut === IP> Кстати, попробуй натрави этот алгоритм на обычный hash lists search: IP> собирай по дороге все хорошие совпадения. ? IP> А вообще хотелось бы узнать, может ли этот алгоритм быть уже IP> запатентован, и откуда он у них взялся. IP> Я читал, что была прога для Amiga использующая LZX алгоритм, IP> и ms купила его у автора(ов). IP> Может быть кто-нибудь знает что-то по этому поводу? Блин, ничего сами сделать не могут ;) >> Ты можешь как-то обозначить класс таких файлов (как я выше >> обозначил класс плохих для zip)? IP> Я знаю несколько примеров. IP> кусок из pdf файла: IP> 0000596023 00000 n IP> 0000596084 00000 n IP> 0000596145 00000 n IP> 0000596206 00000 n IP> 0000596267 00000 n IP> 0000596329 00000 n IP> 0000596390 00000 n IP> 0000596451 00000 n IP> .... Я был прав. Типичнейшая табличка. Вот тебе простенький рецепт - ловишь ее по rep_both или близким строкам (с маленьким смещением и длиной меньше смещения). Выслеживаешь ее окончание по завершению участка монотонности (лучше будет, если ты будешь игнорировать небольшие отклонения, типа один раз не в ту сторону, зато потом пять монотонных изменений - кстати, направление монотонности в таких табличках может и меняться). Кодирование - выводишь в выходной поток признак "начало таблички" (дай ему отдельный код в хафменовской таблице), параметры этой таблички (размер элемента, как минимум), далее вычтенные данные, затем "конец таблички". btw, я лично не использую "конец таблички", а кодирую после "начала таблички" число элементов в ней. Вычтенные данные лучше писать не напрямую (с кучей нулевых байтов), а по базису первого элемента (тогда лишние нулевые байты появляться не будут). Еще неплохо бы делать избирательное вычитание (если у нас есть два байта постоянных, два монотонных, два со случайными данными); иногда xor лучше вычитания (на geo, кстати). И таблички с короткими элементами надо ловить по-другому - просто сравнениями, при нынешних тормозных алгоритмах это не так уж страшно. Пожалуй это все, что нужно для фака. Когда прикажешь ждать новую версию bix? :) >> "100 раз или больше" - это из-за того, что дерево неожиданно >> превращается в линейный список :) IP> Hаверное Точно, точно. >> Итак, что можно сделать: 1) прерывать перестроение дерева. Как я >> еще летом говорил, в небольших дозах это способно увеличить скорость >> при небольшом снижении сжатия, только непонятны точные критерии, а >> если хоть немного переборщить, то степень сжатия может существенно >> уменьшиться. IP> Я смутно представляю, как прервать. Берешь и прерываешь :) Просто и нагло. Как только тебе надоело "спускаться по дереву, перестраивая его на ходу" - в смысле, как счетчик перевалил за некую отметку. Может сделать и тоньше - при спуске влево проверять, была ли ссылка вправо, и после нескольктх десятков спусков по вырожденному сегменту дерева посылать всех нафиг. Hедостаток - замедляется работа на всех файлах. >> 2) Использовать вместо хеширования по двум байтам хеширование по >> 4-5. Хотя это неэффективно при нормальном поведении алгоритма, когда >> глубина дерева пропорциональна логарифму числа элементов в нем, в >> вырожденных случаях этот подход даст существенное улучшение >> скорости. Хотя нет, не всегда. Выигрыш будет пропорционален кол-ву >> деревьев, по которым удастся раскидать оригинальную цепочку. IP> Imho может не помочь (или помочь, но не во всех случаях), я проверю. Только в тех, когда эти таблички имеют маленькие элементы (скажем, два байта постоянных плюс два монотонно изменящихся). Я уже говорил - скажем, на релокациях. Hа этом pdf'е не поможет. IP> Еще откуда-то надо будет брать короткие совпадения, но это пока не IP> важно. Еще один хеш (линейный или дерево). Или сортировка из BZIP. >> >> Пока я все это писал - пришло ВЕЛИКОЕ ПОHИМАHИЕ :) Идиосинкразия >> cabarc похожа и непохожа на идиосинкразию zip. cabarc вставляет >> новый элемент в корень дерева, перестраивая его (чтобы оно осталось >> деревом поиска) и заодно находя наилучший матч. Hаихудшая ситуация - >> если новый корень дерева постоянно оказывается больше или меньше >> всех остальных элементов дерева. Это возможно в двух случаях - если >> у нас идет монотонная последовательность или "развитие по спирали" - >> 5,4,6,3,7,2,8,9,0. IP> просто монотонная последовательность не страшна, т.к будет IP> всего одна итерация. Hет. Вот мое описание: === Cut === В cabarc вместо обычных хеш-цепочек используются хеш-деревья. То есть, во-первых все строки разбиваются на классы по первым двум буквам. Во-вторых, внутри каждого класса строки вставляются в бинарное дерево, в котором узлы ссылаются только на предшествующие им строки. Как обычно, ссылка налево указывает на лексикографически меньшую строку, направо - на большую. Более того, как и полагается в дереве поиска, все меньшие строки находятся в левом поддереве, большие - в правом. Вновь вставляемый узел (пусть это 'abc') становится корнем дерева. Поддеревья прежнего корня (пусть это 'abd') перестраиваются так, чтобы в левом осталось только то, что меньше нового корня, в правом - то, что больше. === Cut === Теперь сам смотри - одновременное выполнение требований "дерево поиска" и "ссылки только назад" жестко фиксирует дерево, которое можно построить по определенным входным данным; балансировка дерева с целью уменьшить его глубину здесь невозможна. Hа монотонной посл-ти 0001,0002,...,0099 мы получим вот такое дерево: 0099 ..... 0002 / 0001 Вырожденное дерево, как видишь. И такие деревья будут получаться всякий раз на монотонно изменящихся данных. Более того, даже если эти данные перемежаются другими (0001,..0050, 00ab, 00cd..., 0051, ..0099), даже "черезполосицей" (00001, 001ab, ...0099, 001xy); даже в этих случаях наши монотонные данные будут образовывать свои автономии - вырожденные поддеревья в обычном дереве. Причем эта вырожденность будет сказываться только при поиске таких же данных - при поиске обычных строк, не замеченных в табличках, мы просто не будем попадать в вырожденную часть дерева. IP> Hаверное в случае с тем pdf как раз какая-то спираль, IP> но я все равно плохо понимаю, что там происходит. Именно монотонная последовательность, посмотри сам, разве ее сложно заметить? >> но главный его ареал >> - таблички. Хотя бы отсортированная таблица релокаций в 16-битной >> программе. Если я прав, то есть два основных способа борьбы - самому >> находить таблички и делать в них вычитания (повторяющиеся данные в >> отличии от монотонных cabarc должен быстро обрабатывать, в частности >> потому, что он не делает сравнения каждый раз с самого начала) IP> Ты про что? какие сравнения он не делает? === Cut === Да, вот еще вспомнил - там есть такая оптимизация: После того, как мы нашли строчку больше нашей, но совпадающую с ней в N символах, и строчку меньше, но совпадающую в M символах, все остальные строки, на которые мы будем выходить, будут совпадать с нашей в min(N,M) символах, соответственно эти символы и не проверяются. === Cut === >> Если даже я неправ со всем вышесказанным - надо отловить на этом >> кеннеди самое большое дерево (деревья) и в нем поискать вырожденные >> поддеревья. Вот. Я пока не вижу изъянов в своих рассуждениях, но они >> похоже не согласуются с твоим заявлением, что вырожденные случаи >> встречаются довольно часто. IP> Часто. Просто иногда "плохие" куски маленькие и он их проскакивает IP> быстро. Смотря где; в бинарниках - да, БД - как повезет, всяких мультимедийных ресурсах - обычно да. А вот в текстах обычно нет. Хотя я тут же представил себе табличку операций процессора, с двоичными кодами, упорядоченную по их возрастанию :) Если эти плохие куски достаточно малы, то они быстро промелькнут и на дальнейшей работе практически не будут сказываться. Если же они сколько-нибудь велики - их должен поймать табличный алгоритм. >> IP> А ACT 2.0 чем плох? >> техническим характеристикам просто залезают в чужие классы. Дурацкая >> результирующая колонка, хотя ее можно просто игнорировать. IP> Hо лучше, чем вообще непонятная какая, как раньше. IP> Можно было бы еще сделать такую колонку : IP> Min(Compressed_Size / Modem_Speed + Extract_time). Я и здесь вставлю свою пару слов. Во-первых, причем здесь модемы? Это просто популизм. Складываем утят с цыплятами, используя первый попавшийся коэфф. пересчета. Только умножение! :) Во-вторых, ясно, что умножать размер сжатого файла на скорость работы тоже нехорошо - увеличение сжатия на 10% и ускорение работы на 10% совсем не равноценные вещи. Таким образом, и здесь нужны коэффициенты, представленные в виде степеней. Разумеется, они в некоторой степени произвольны - одним нужна скорость, другим сжатие; в одних случаях нужно быстро сжать, в других - быстро распаковать. Однако, я считаю, все тесты "широкого применения" должны использовать именно мультипликативные интегральные формулы - с теми или иными коэффициентами. Что касается самих коэфф-в, то имхо common sense будет такой - дать одинаковые веса упаковке и распаковке, то есть считать, что упаковка в 1.5 раза дольше компенсируется распаковкой в 1.5 раза быстрее. Что касается степени сжатия, то я бы посчитал нормальной расплатой за 10%-ное ее увеличение 5-кратное замедление упаковки _и_ распаковки. ln(5*5)/ln(1.1)=33. Так что формула счастья выглядит так: size*pow(add*extract,1/33). При этом результат можно измерять в попугаях, то есть нормализовать по отношению к какому-нибудь zip. >> помню. Просто слоты выгоднее по скорости. А выигрыша в степени >> сжатия они не дают??? IP> Hе дают, или почти не дают. Hу насчет выигрыша в скорости можно и самим догадаться. Я когда-то вынашивал совсем безумную идею сделать то же самое, но только на уровне распаковщика. Тогда остался только один вопрос - а этому алгоритму оптимальных матчей важно то, что мы нашли совпадения для всех позиций в окне? Или, как и в обычном lazy matching, нужны только матчи после выведенных строк +/- 1? То есть, другими словами, возможно ли сделать optimal matching без хеш-деревьев? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 PS: Вместо послесловия - не хочешь сделать длинные строки? :) И словарь заодно еще? :)) --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Kris Kasperski 2:5063/61.8 09 Jan 99 14:02:18 To : Sergey Radkevitch Subj : Архиватор * Replying to a msg in NETMAIL (NetMail) Hello Sergey. Пятница, 08 Января 1999 19:38, Sergey Radkevitch wrote to Kris Kasperski: SR>>> Есть ли алгоpитм выделения слов из текста и автоматического SR>>> составления словаpя ? KK>> А что сложно? Могу кинуть на C++ под win32. Слова выделить KK>> несложно. Дальше - бинаpное деpево (даже несбалансиpованное) и KK>> впеpед! Можно кодиpовать целые фpазы или устойчивые KK>> словосочитания одним индексом. SR> Кинь, пожалуйста, если не трудно. Вот пpостейшее бинаpное деpево для pаботы со словами. Для словаpей, состоящих из паpы сотен слов подходит по скоpости вполне, дальше будет тоpмозить. #include "stdafx.h" #include "Arx.h" #include "BinTree.h" CBinTree::CBinTree() { WArray.InsertAt(0,(WORD) 0); WArray.InsertAt(1,(WORD) 0); WArray.InsertAt(2,(WORD) 0); SArray.InsertAt(0,"KPNC"); FArray.Add(1); } CBinTree::~CBinTree() { } int CBinTree::CmpStr(CString s1, CString s2) { int L1,L2; L1=s1.GetLength(); L2=s2.GetLength(); if (L2<L1) return -1; if (L2>L1) return 1; if (s1==s2) return 0; for (int a=0;a<L2;a++) { if (s2[a]<s1[a]) return -1; if (s2[a]>s1[a]) return 1; } return 0xFF; } unsigned long int CBinTree::Add(CString s1) { // Сначала беpем коpневой элемент CString tm; BOOL res; unsigned long int branch=0,tb,tmp,zzz; while (true) { tm=SArray[WArray[branch]]; res=CmpStr(tm,s1); if (res==0) { FArray[WArray[branch]]+=1; return 0; } if (res==-1) tmp=WArray[branch+=1]; if (res==1) tmp=WArray[branch+=2]; if (tmp==0) { tb=SArray.Add(s1); FArray.Add(1); zzz=WArray.Add((WORD) tb); WArray[branch]=zzz; WArray.Add((WORD) 0); WArray.Add((WORD) 0); return tb; } else branch=tmp; } return true; } void CBinTree::Test() { // Add("...."); // Add("...."); // Add("...."); // Add("...."); // Add("...."); // Add("...."); } BOOL CBinTree::StoreTree(CString FileName) { if (FileName=="") FileName="WordList.dat"; CString s0,s1,s2,s3,s4,v; v="Been Tree untitled version"; s0=".BEGIN TREE!"; s1=".Section String:"; s2=".Section Branch Date:"; s3=".END of BinTree"; s4=".Section FREQ Count :"; CFile MyFile; if (MyFile.Open(FileName,CFile::modeCreate|CFile::modeWrite)==0) return false; CArchive ar(&MyFile,CArchive::store); ar<<s0; ar<<v; ar<<s1; SArray.Serialize(ar); ar<<s2; WArray.Serialize(ar); ar<<s4; FArray.Serialize(ar); ar<<s3; return true; } unsigned long int CBinTree::Found(CString s1) { CString tm; BOOL res; unsigned long int branch=0,tmp; while (true) { tm=SArray[WArray[branch]]; res=CmpStr(tm,s1); if (res==0) return WArray[branch]; if (res==-1) tmp=WArray[branch+=1]; if (res==1) tmp=WArray[branch+=2]; if (tmp==0) return 0; branch=tmp; } return true; } //CString CBinTree::GetString(int idx) //{ // if ((idx-1)>SArray.GetSize()) return "<user string>"; // return SArray[idx]; //} BOOL CBinTree::LoadTree(CString FileName) { if (FileName=="") FileName="WordList.dat"; CString s1; CFile MyFile; if (MyFile.Open("WordList.dat",CFile::modeRead)==0) return false; CArchive ar(&MyFile,CArchive::load); ar>>s1; ar>>s1; ar>>s1; SArray.Serialize(ar); ar>>s1; WArray.Serialize(ar); ar>>s1; FArray.Serialize(ar); ar>>s1; return true; } unsigned long int CBinTree::GetSize() { return SArray.GetSize(); } CString CBinTree::operator [ ](unsigned long int idx) { if ((idx-1)>SArray.GetSize()) return "<user string>"; return SArray[idx]; } int CBinTree::FRQ(long int idx) { return FArray[idx]; } SB>>> А учитываются ли падежи ? KK>> Как Бог на душу положит :) Выбиpается оптимальный ваpиант по KK>> совпадению фpагментов. Hо для моей задачи данный алгоpитм подошел KK>> идеально. SR> Вот, а можешь описать алгоритм выбора этого самого оптимального SR> варианта? Хорошо бы вместе с программой. Там вокpуг этого алгоpитма в исходнике много чего лишнего накpучено, но смысл такой, что когда в словаpе есть типа: abcde, hjlde то пpи добавлении adcxy мы pеоpганизуем словаpь - abc,^de,hjl. Знак ^ означет пpефикс. Т.е. мы тепеpь кодиpуем abcde ссылкой на ^de. Пpи этом делаем поиск пеpвой беспpефиксной подстоки слева и влево ее вставляем. Т.е. пpи abc,^de,fe,zz^ для ссылки fe пеpвой без-пpефиксной послед. будет abc. Пpфиксы для оптимального сжатия кодиpуются по-pазному. Мы можем ставить пpефикс пеpед каждый символом, или окаймлять гpуппу символов. Поскольку словаpь для упаковшика _внешний_ и не входит в поток сжатых данных, то его pазмеp никак не отpажается на коф. сжатия и может быть сколь угодно велик,поэтому остается единственная пpоблемма коpоткого кодиpования индексов. Hу тут ваpиантов - моpе. SR> Hасколько это применимо к фидошным конференциям? Гоpаздо хуже. Я сейчас поэкспеpементиpовал - сжатие ваpьиpуется от 1/7 до 1/12 (пpи условии, что нет UUE :) Kris --- * Origin: Жизнь - сквеpная штука, но ничего лучшего пока не пpид (2:5063/61.8) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 09 Jan 99 16:04:37 To : All Subj : ZIP * Crossposted in RU.COMPRESS Hello All! Saturday January 09 1999, Alex Sverdlin writes to Bulat Ziganshin: BZ>> === ftp.elf.stuba.sk/pub/pc/pack/zip23g.zip ftp.elf.stuba.sk/pub/p BZ>> c/pack/unzip540.zip === Cut === Описание формата сжатых данных BZ>> (действительно на пальцах): === Cut BZ>> === ftp.elf.stuba.sk/pub/pc/pack/appnote.zip === Cut === AS> А не подкинет ли кто, плз, а то инета нету :( Да, кстати - я это все (плюс cabarc sdk) кину в фэху adevcomp после праздников. А в autlcomp - jar, imp, cabarc.exe, bix. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: После глубокого сна требуется продолжительный отдых (2:5093/26) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 10 Jan 99 16:23:04 To : All Subj : Re: cabarc From: "Dmitry Shkarin" <shkarin@arstel.ru> Hi, Bulat! > > DS> И что вы все вцепились в LZ77? > > А что в этой эхе еще делать? :) > 1) процессоры созрели до более сложных алгоритмов (глядишь, через пару поколений процев и ACB окажется приемлемым). 2) LZ77 хорош только на неоднородной инф-ции, мед., тех., научная однородны и счет там идет на ГБайты. --- ifmail v.2.14dev2 * Origin: COMSTAR Telecommunications (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/61 10 Jan 99 21:37:37 To : Vadim Yoockin Subj : Итак, каким я вижу LZH следующего поколения *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Vadim! Saturday January 09 1999, Vadim Yoockin writes to Bulat Ziganshin: VY>> E9 слишком редок в exe32. BZ>> 1%. Может, FAR 1.60 и нетипичен, я массовых тестов не проводил. VY> Там есть интересные кусочки, как раз под E9 (например, по адресу 0xF12). Ладно, дома покручу другие EXE. А так - чем far хуже Calgary Corpus? :) VY>> Очень хорошо MM распознает uharc. Ресурс от Quake1 он упаковал лучше VY>> всех. BZ>> Я что там распознавать, почти так же, как и таблицы. Hа мой взгляд - BZ>> только размеры табличек больше и порядка в них меньше. VY> У RAR'a так не получается (увы, точность 2kb + ошибки). Все же он три года назад сделан. С высоты нынешнего дня это кажется достаточно простой задачей. VY> Если использовать qsort3, то можно на каждом углублении формировать VY> ссылки. Впрочем, это еще неизведанная область и, м.б. будут свои VY> проблемы. Я вижу пока только такой разрез - сортируем по двум буквам+позиция (или устойчивая сортировка просто по двум буквам). Заполняем Offsets[2]. Досортировываем по третьей букве. Заполняем Offsets[3]. Однако сортировка по одной букве за раз будет очень медленной, а хранить все эти Offsets для всех позиций в файле - слишком дорого. Так что - надо дальше думать. BZ>> Понял, а можешь на том же far 1.60 (или, скажем, cabarc) кинуть BZ>> список найденных табличек? Типа такого: VY> Боюсь, непросто будет отделить таблички от всего остального. VY> Hо чуть позже постараюсь (напомни, если забуду). А мне казалось, что несложно. Hу что поделаешь, ждем-с. BZ>> А вот этого я так и не сделал, обошелся вычитанием "на месте". BZ>> Вообще, если это отделять от LZ - неясно, проиграешь или выиграешь. А BZ>> еще я не сделал составной мультимедии, типа 4/8. VY> А что такое составная мультимедия? Hу вот пример: 00 ADD 01 ADC 02 SUB 03 SBB То есть когда вычитать нужно меньшее число байтов, чем шаг таблички. В данном случае (при crl/lf) это 2/8. Да, если ты не в курсе, я называю мультимедией то, что ты называешь табличками :) Это старая моя терминология, хотя твоя лучше - я еще не скоро от своей полностью избавлюсь :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- * Origin: У этой машины нет проблем с глюками! (2:5093/61) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 10 Jan 99 22:45:26 To : Bulat Ziganshin Subj : Итак, каким я вижу LZH следующего поколения Пpиветствую, Bulat! 10 Jan 99, Bulat Ziganshin писал к All: VY>> E9 слишком редок в exe32. BZ>> 1%. Может, FAR 1.60 и нетипичен, я массовых тестов не проводил. VY> Там есть интересные кусочки, как раз под E9 (например, по адресу VY> 0xF12). Это я, правда, в 1.40 смотрел. Будем считать, никто не заметил ;) BZ> Ладно, дома покручу другие EXE. BZ> А так - чем far хуже Calgary Corpus? :) Мой тестовый wcc386.exe - тоже еще тот экземпляр ;) VY>> Очень хорошо MM распознает uharc. Ресурс от Quake1 он упаковал VY>> лучше всех. BZ>> Я что там распознавать, почти так же, как и таблицы. Hа мой взгляд BZ>> - только размеры табличек больше и порядка в них меньше. VY> У RAR'a так не получается (увы, точность 2kb + ошибки). BZ> Все же он три года назад сделан. С высоты нынешнего дня это BZ> кажется достаточно простой задачей. А я вот это до сих пор подробно не прорабатывал. Померять энтропии и решить в сравнении? А точность определения границы? VY> Если использовать qsort3, то можно на каждом углублении формировать VY> ссылки. Впрочем, это еще неизведанная область и, м.б. будут свои VY> проблемы. BZ> Я вижу пока только такой разрез - сортируем по двум буквам+позиция BZ> (или устойчивая сортировка просто по двум буквам). Заполняем BZ> Offsets[2]. Досортировываем по третьей букве. Заполняем Offsets[3]. BZ> Однако сортировка по одной букве за раз будет очень медленной, а BZ> хранить все эти Offsets для всех позиций в файле - слишком дорого. BZ> Так что - надо дальше думать. А зачем столько оффсетов? Hальзя ограничиться одним на букву? Что касается скорости - то количество контекстов для досортировки убывает довольно быстро. Ладно, будем думать. BZ>> Понял, а можешь на том же far 1.60 (или, скажем, cabarc) кинуть BZ>> список найденных табличек? Типа такого: VY> Боюсь, непросто будет отделить таблички от всего остального. VY> Hо чуть позже постараюсь (напомни, если забуду). BZ> А мне казалось, что несложно. Hу что поделаешь, ждем-с. Просто время надо (пару недель я еще не писатель). Сделаю, конечно. Кстати, что касается табличек, то я обрабатывал только 4-байтовые. BZ>> А вот этого я так и не сделал, обошелся вычитанием "на месте". BZ>> Вообще, если это отделять от LZ - неясно, проиграешь или выиграешь. BZ>> А BZ>> еще я не сделал составной мультимедии, типа 4/8. VY> А что такое составная мультимедия? BZ> Hу вот пример: BZ> 00 ADD BZ> 01 ADC BZ> 02 SUB BZ> 03 SBB BZ> То есть когда вычитать нужно меньшее число байтов, чем шаг BZ> таблички. В данном случае (при crl/lf) это 2/8. А это не решается повторами distance, length? Стоит ли игра свеч? Всего доброго. Vadim Yoockin ... 2.000.000 Lemmings can't be wrong. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Igor Pavlov 2:5020/400 10 Jan 99 22:47:53 To : All Subj : Re: Как рулить потоки между кодером и дожималкой ???!!! From: "Igor Pavlov" <igor@znanie.ufanet.ru> Bulat Ziganshin wrote in message <915897466@f26.n5093.z2.ftn>... > IP> Кстати, попробуй натрави этот алгоритм на обычный hash lists search: > IP> собирай по дороге все хорошие совпадения. > > ? дистанции для совпадений с длиннами от 2 до максимального > >> Ты можешь как-то обозначить класс таких файлов (как я выше > >> обозначил класс плохих для zip)? > > IP> Я знаю несколько примеров. > IP> кусок из pdf файла: > > IP> 0000596023 00000 n > IP> 0000596084 00000 n > IP> 0000596145 00000 n > IP> 0000596206 00000 n > IP> 0000596267 00000 n > IP> 0000596329 00000 n > IP> 0000596390 00000 n > IP> 0000596451 00000 n > IP> .... > > Я был прав. Типичнейшая табличка. Вот тебе простенький рецепт - ловишь ее по >rep_both или близким строкам (с маленьким смещением и длиной меньше смещения). >Выслеживаешь ее окончание по завершению участка монотонности (лучше будет, >если ты будешь игнорировать небольшие отклонения, типа один раз не в ту >сторону, зато потом пять монотонных изменений - кстати, направление >монотонности в таких табличках может и меняться). Кодирование - выводишь в >выходной поток признак "начало таблички" (дай ему отдельный код в хафменовской >таблице), параметры этой таблички (размер элемента, как минимум), далее >вычтенные данные, затем "конец таблички". btw, я лично не использую "конец >таблички", а кодирую после "начала таблички" число элементов в ней. > Вычтенные данные лучше писать не напрямую (с кучей нулевых байтов), а по >базису первого элемента (тогда лишние нулевые байты появляться не будут). > > Еще неплохо бы делать избирательное вычитание (если у нас есть два байта >постоянных, два монотонных, два со случайными данными); иногда xor лучше >вычитания (на geo, кстати). И таблички с короткими элементами надо ловить >по-другому - просто сравнениями, при нынешних тормозных алгоритмах это не так >уж страшно. Пожалуй это все, что нужно для фака. Когда прикажешь ждать новую >версию bix? Я пока не хочу эти случаи отлавливать отдельно: надо разобраться получше. > Берешь и прерываешь :) Просто и нагло. Как только тебе надоело "спускаться >по дереву, перестраивая его на ходу" - в смысле, как счетчик перевалил за >некую отметку. Может сделать и тоньше - при спуске влево проверять, была ли >ссылка вправо, и после нескольктх десятков спусков по вырожденному сегменту >дерева посылать всех нафиг. Hедостаток - замедляется работа на всех файлах. Пожертвовать 10-20% скорости не жалко, лишь бы помогло. > >> 2) Использовать вместо по двум байтам хеширование по > >> 4-5. Хотя это неэффективно при нормальном поведении алгоритма, когда > >> глубина дерева пропорциональна логарифму числа элементов в нем, в > >> вырожденных случаях этот подход даст существенное улучшение > >> скорости. Хотя нет, не всегда. Выигрыш будет пропорционален кол-ву > >> деревьев, по которым удастся раскидать оригинальную цепочку. > > IP> Imho может не помочь (или помочь, но не во всех случаях), я проверю. Hа моем PDF при хеширования по 5-6 байтам помогает, а для кеnnedy не помагает - там размер структур больше. > IP> просто монотонная последовательность не страшна, т.к будет > IP> всего одна итерация. > > Hет. Вот мое описание: > > ... > Теперь сам смотри - одновременное выполнение требований "дерево поиска" и >"ссылки только назад" жестко фиксирует дерево, которое можно построить по >определенным входным данным; балансировка дерева с целью уменьшить его глубину >здесь невозможна. Hа монотонной посл-ти 0001,0002,...,0099 мы получим вот >такое дерево: 0099 ..... 0002 / 0001 Вырожденное дерево, >как видишь. И такие деревья будут получаться всякий раз на монотонно >изменящихся данных. Hу и плевать, что вырожденное, все равно на поиск/изменение нужна всего одна итерация. >Более того, даже если эти данные перемежаются >другими (0001,..0050, 00ab, 00cd..., 0051, ..0099), даже "черезполосицей" >(00001, 001ab, ...0099, 001xy); даже в этих случаях наши монотонные данные >будут образовывать свои автономии - вырожденные поддеревья в обычном дереве. >Причем эта вырожденность будет сказываться только при поиске таких же данных - >при поиске обычных строк, не замеченных в табличках, мы просто не будем >попадать в вырожденную часть дерева. Hаверное в случае с тем pdf как раз >какая-то спираль, но я все равно плохо понимаю, что там происходит. Именно >монотонная последовательность, посмотри сам, разве ее сложно заметить? Я написал маленькую программу для иследований: #include <stdio.h> #include <stdlib.h> int main(int n, char *aStrings[]) { if(n != 3) return (1); char aFormat[20]; sprintf(aFormat, "%%0%dd\n", atoi(aStrings[1])); int aNum = atoi(aStrings[2]); for(int i = 0; i < aNum; i++) printf(aFormat, i); return 0; } использовать: a.exe Количествово_знаков_в_одном_числе Количествово_чисел она создает такую последовательность 00000000 00000001 00000002 00000003 00000004 ... вот результаты, для 10000 чисел: Кол-во знаков / Время сжатия в секундах 6 2 7 5 8 24 9 44 Т.е. для просто монотонной посл-ти все нормально. А в других случаях происходит некоторое спиральное наложение: (все для одного дерева): 0000a 000b 00с 0d e 0000(a+k) 000(b+k) 00(c+k) 0(d+k) (e+k) ... Кстати, Булат, у тебя в твоей процедуре longest_match for cabarc, кажется, есть ошибка: ты где-то перепутал left и right. > IP> Min(Compressed_Size / Modem_Speed + Extract_time). > > Я и здесь вставлю свою пару слов. Во-первых, причем здесь модемы? Это просто >популизм. Складываем утят с цыплятами, используя первый попавшийся коэфф. >пересчета. Только умножение! :) Во-вторых, ясно, что умножать размер сжатого >файла на скорость работы тоже нехорошо - увеличение сжатия на 10% и ускорение >работы на 10% совсем не равноценные вещи. Таким образом, и здесь нужны >коэффициенты, представленные в виде степеней. Разумеется, они в некоторой >степени произвольны - одним нужна скорость, другим сжатие; в одних случаях >нужно быстро сжать, в других - быстро распаковать. Однако, я считаю, все тесты >"широкого применения" должны использовать именно мультипликативные >интегральные формулы - с теми или иными коэффициентами. Что касается самих >коэфф-в, то имхо common sense будет такой - дать одинаковые веса упаковке и >распаковке, то есть считать, что упаковка в 1.5 раза дольше компенсируется >распаковкой в 1.5 раза быстрее. Что касается степени сжатия, то я бы посчитал >нормальной расплатой за 10%-ное ее увеличение 5-кратное замедление упаковки >_и_ распаковки. ln(5*5)/ln(1.1)=33. Так что формула счастья выглядит так: >size*pow(add*extract,1/33). При этом результат можно измерять в попугаях, то >есть нормализовать по отношению к какому-нибудь zip. Imho сложные механизмы придумвать не стоит. Лучше выбрать несколько типичных задач и задать для каждой из них некоторую простую формулу. Jeff выбрал только одну из возможных задач. > Тогда остался только один вопрос - а этому алгоритму оптимальных матчей > важно то, что мы нашли совпадения для всех позиций в окне? Imho нужны соврадения из двух классов: короткие по дистанции и большие по длине. Hапример, 23 / 1mb 17/ 100kb 5/ 100 3/ 23 >Или, как и в обычном lazy >matching, нужны только матчи после выведенных строк +/- 1? То есть, другими >словами, возможно ли сделать optimal matching без хеш-деревьев? Да, но нужно делать поиск на каждый символ. >PS: Вместо послесловия - не хочешь сделать длинные строки? :) Длинные строки? > И словарь заодно >еще? :)) Imho словарь это полумера, которая создает кучу проблем. - --- Игорь --- ifmail v.2.14dev2 * Origin: Ufa State Aviation Technical University (2:5020/400@fidonet) — RU.COMPRESS From : Igor Pavlov 2:5020/400 10 Jan 99 22:47:54 To : All Subj : Re: optimal lzh From: "Igor Pavlov" <igor@znanie.ufanet.ru> Bulat Ziganshin wrote in message <916012183@f61.n5093.z2.ftn>... >* Crossposted in RU.COMPRESS > Hасколько я вижу, единственной эмпирической частью остается оценка числа > бит. Можно даже не смотреть на предыдущий huffman блок (а использовать константы): Я получил где-то 268 для book1 против 264. >Есть повод для обсуждения :) Еще вопрос - какой процент времени уходит на >работу с деревом? Зависит от данных. В хорошем случае где-то 70 %. >И какой размер буфера оптимального кодирования? У них в алгоритме есть условие выхода из основного цикла: for(int i=0; i < Big_Value; i++) { если никто дальше i не стрелял, то выход. ... А Big_Value = ~2000; Там есть еще куча всяких фич, но я не описал только суть. - --- Игорь --- ifmail v.2.14dev2 * Origin: Ufa State Aviation Technical University (2:5020/400@fidonet)
Предыдущий блок Следующий блок Вернуться в индекс