[an error occurred while processing this directive][an error occurred while processing this directive][an error occurred while processing this directive]
— 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)
[an error occurred while processing this directive][an error occurred while processing this directive]