Предыдущий блок Следующий блок Вернуться в индекс
 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)
 Предыдущий блок Следующий блок Вернуться в индекс