WIN | KOI | LAT

08.03.2l - aridemo 1.03. Доказана корректность последней версии CL-D (спасибо А.Ратушняку), "шиндлерский" rangecoder также исправлен, наконец. Кроме того, теперь есть _две_ версии CL-D - полностью на C++ и полностью (почти) на ассемблере. По-моему, интересно, что C++'ная версия с int64 кодирует на 20% быстрее ассемблерной - которая использует FPU :).

13.03.2l - Со времени моей первой удачной реализации дистансного кодирования мне хотелось изобрести подобный, но _поточный_ алгоритм. И вот он есть - Distance Mixing. С++'ные исходники прилагаются. Увы, правда, но оказалось, что этот "прямолинейный" подход работает несколько хуже, чем даже мой DC из DC-Kit (235k против 229k на book1.bwt).
Есть у кого-нибудь идеи, как его усовершенствовать? ;)

16.03.2l - Заимел идею и написал некий алфавитный сортировщик. В основном, он ориентирован на применение вместе с BWT - для переупорядочивания алфавита перед блочной сортировкой. Берет таблицу частот пар символов, сортирует колонки по возрастанию энтропии и выдает таблицу с отсортированными колонками и - в отдельном файле - использованную перестановку.

22.03.2l - После нескольких тестов и обсуждений выяснилось, что алгоритм, использованный в cnksort1 практически бесполезен :). Его применение к данным перед BWT ухудшает сжатие... и теперь я думаю, что это можно было предвидеть - нет особого смысла в сортировке просто по энтропии распределения символов-суффиксов. Практически нет корреляции между похожестью двух блоков суффиксов и их энтропий. Так что я переделал кое-что - может, оно и не помогает при блочной сортировке, но может быть использовано иначе :). Идея (возникшая благодаря Вадиму Юкину) заключалась в том, чтобы переупорядочить блоки символов в файле так, чтобы похожие фрагменты располагались рядом и получить лучшее статистическое сжатие. Это - работает! :)
(AridemoV6 сжимает book1.bwt в 326,972 байта без перестановки блоков и в 318,160 с ней (блоки по 2k), включая информацию об их порядке!)
Мне кажется, это полезнаая идея... хотя, может быть, и не с моим нынешним алгоритмом расчета оптимальной перестановки :).

23.03.2l - Вот усовершенствованная версия переупорядочивания блоков в файле - тоже медлительная, но теперь оптимизация имеет сложность O(N^3) - что сравнительно терпимо :). Заодно, теперь оно генерирует диаграммы распределения частот в данных перед и после перестановки - номер блока по горизонтали, код символа по вертикали.

16.04.2l - Потратил массу времени, пытаясь найти весовую функцию. Похоже, что оценить реальную вероятность нулевого бита при наличие _двух_ (возможно, различных) оценок p₁ и p₂, данных двумя моделями, совсем несложно. Есть общеизвестное предположение, что в таком случае должно использоваться значение, вычисляемое по формуле p_m = w₁*p₁+w₂*p₂, где w_? - веса моделей. Если обе модели считать равноценными, то это будет просто средняя вероятность. Но вместо этого мы можем использовать p_? в качестве контекстов и собрать реальные частоты битов, соответствующих каждой паре {p₁;p₂}. Так и выяснилось, что весовая функция далека от простого среднего. Но все же она довольно гладкая, хотя я и обломался подобрать функцию, дающую подобные результаты :(. Может, вам повезет ;).
Вот комплект материалов, полезных для этого - программа для сбора статистики, кодер, показывающий, что среднее - не лучшее etc.

04.05.2l - Только что переписал на Си свою схему контекстного смешивания - PPM211. Медленная штука, но очень простая, особенно в сравнении с PPMd :). Хуже относится к бинарникам, но тексты c текстами справляется несколько лучше, чем PPMd v.F. Сжимает book1 в ~210.9k. ...И расжимает :).

14.05.2l - PPM211 - фигня, поскольку основывается на некой эвристической "магии". Так что я только что разработал новый кодировщик, гораздо более логичный по натуре, чем предыдущий. Ну, случайно он оказался и более эффективным, но я этого не ожидал :). Так что вот PPM210 - моя новая модель, в данный момент дающая 209,890 на book1.

22.05.2l - Надеюсь, это последний апдейт; модель опять полна мистики :). Хотя 207,879 на book1 это уже не так плохо... Еще соорудил кое-какой workaround для избежания генерации IntelC/VC слишком медленного кода в некоторых случаях - так что теперь оно на 20% (или даже больше) быстрее.

31.05.2l - Hopes are never true :) ...Так что вот еще кое-что. Вроде как доделанная версия, более стабильная на бинарниках. Кроме того, я добавил несколько опций для ограничения максимального порядка и объема используемой памяти. Сжимает book1 в 207,379.

02.06.2l - И еще одна версия, слегка усовершенствованная. Работает несколько быстрее и большинство файлов сжимает лучше, чем раньше, хотя не все, увы :). 206,991 на book1.

04.05.2002 - Нашел место для очередного "зеркала". Тут правда, меня заставили все на русский перевести, но, хотя бы, может никто теперь на тормозизм серверов не будет жаловаться ;).
      Со времени последней "новости" прошел почти год - неудивительно, что успело появиться кое-что еще. Просто лень заливать на сайты было - а теперь такой повод ;). Но даты я все равно не помню, так что все скопом:
1) ParCoder
"Параллельный" арифметический кодировщик. Это иногда возникает у некоторых людей идея приспособить векторные системы команд для компрессии, а "аксакалы", мылом и в эхе им разъясняют степень их ламеризма. Особенно в этом Булат Зиганшин преуспел ;). ...А я смотрел на это, смотрел... пока от В.Семенюка то же самое не услышал, и тут уж не выдержал ;).
В общем, "одновременно" работает несколько инстансов кодека, каждый из которых работает с собственным файлом, но пишут/читают они все один поток. Факт тот, что эти инстансы легко расселить в отдельные thread'ы и сделать реально параллельными. А если еще напрячься - то и посчитать арифметику сразу для пары символов при помощи MMX. Практического смысла в этом мало, но возможность есть.
И нечего со мной спорить! ;)
2) mCTW
Обчитавшись Садакане, решил попробовать и я реализовать байтовый CTW. Ничего хорошего из этого не вышло, как видно. ...Впрочем, 288k на book1 за 12 часов - может, это ничего? %)
3) Enthropy Logarithmic-Scale Coder
Ну, Ратушняк давно всех ELS'ом запугивал. Но когда у меня кто-то спросил, знаю ли я, что это такое есть... пришлось выяснять. Оказалось - достаточно логичная модификация арифметического кодирования в целях избежания умножений, предлагаемая некоторыми в качестве коммерческой замены перезапатентованному Q-Coder'у. Я от'OCR'ил их исходники из pdf'а, заставил работать, и сравнил с aridemo. Душераздирающее зрелище этот ELS, я вам скажу ;).
4) Coderz 6a
Устал я aridemo апдейтить, честно. Ну какой интерес вылизывать C++'ные классы и выкладывать узоры из кодеров и моделей, когда PPM некопан? ;) Но тут такое дело: изобрелась совершенно новая (и хорошая) разновидность carryless (в процессе переписки с Игорем Павловым, кажется). Скорость кодирования - как у обычного carryless, декодирования - как у обычного rangecoder'а, такой вот мутант. Пришлось релизить в упрощенном варианте ;).
5) PPMY 3c
Неожиданно обнаружил, что PPMY не такой, как на сайте
А, вспомнил! - я там работу с табличками параметров сделал читабельней (хотя и чуточку медленней). Заодно, видимо, еще их пооптимизировал - текущий результат, во всяком случае, 206,808 на book1.
6) FLT32
Это опять-таки в процессе обсуждения препроцессинга экзешников с Игорем Павловым у меня сотворилось вот такое, ну а у Игоря, соответственно, BCJ2. У меня, правда, декодер безнадежно отстал от кодера в процессе опробывания вариантов, так что он не прилагается. Но сделать его несложно. Зато последний ppmonstr с его помощью сжимает известный wcc386 до 231,738 байт (или 232,109 без pop reversing, которое чаще вредит ;).
А еще есть хорошая штука PEUtils, которая разбирает PE'шники на секции, а потом опять собирает. Вот ежели PE'шник разобрать на секции, а потом те из них, которые кодовые, обработать нап... то есть FLT32 ;), то получается особенно хорошо.

Не уверен, что это все, но что-то я уже устал ;). Вроде... ой, чуть самое главное не забыл ;).

7) sUnrar
Это попался мне пару месяцев назад один архивчик rar'овский, запароленный, который очень открыть хочется ;). Ну и скорость работы лидеров в области "восстановления забытых rar'овских паролей" - Crark и RPC меня как-то не устроила... Так что я взял unrarsrc и... обломался. Оказалось, без BorlandC его скомпилить не так уж просто %). Поэтому вот, получился такой рип unrarsrc - 23k исходников вместо 138k, компилится VC/IntelC (отчего существенно быстрее работает ;). Можно изготовить SFX размером 7k, если upx'ом попаковать. Имхо полезно. Последняя версия, правда, вроде как вот эта, но она принципиально не создает подкаталогов и плохо обходится с архивами - т.е. хранит все распакованные файлы в памяти ;). Ну, промежуточная такая версия перед переходом к собственно кракеру паролей. Зато исходников уже всего 18k ;) и еще кое-что полезное в текстовках написано...
8) RarPass
Ну и собственно "вспоминатель забытых паролей" для rar2. В принципе, он еще довольно сырой, я над ним еще работаю... но скорость-то уже на 50% выше, чем у конкурентов. Точнее, вообще несравнимо выше - т.к. у меня скорость от длины пароля странным образом не зависит ;). По причине "сырости" еще есть масса ограничений - правильная работа обеспечивается только для файлов, запакованных без использования "мультимедийного" алгоритма. Кроме того, фиксирован алфавит - 0123456789abcdefghijklmnopqrstuvwxyz. Но все это не проблема, т.к. прилагаются исходники и описание нужной части формата архива. Да и вообще, мне кажется, что переборщик паролей особым "интеллектом" снабжать не следует. Он будет быстрее работать, если нужные параметры подставить непосредственно в исходники и откомпилировать нормальным компилятором.

Уф! Не, на сегодня все ;)

09.05.2002 - Новая версия rarpass. Еще 10% скорости.

14.05.2002 - Перекомпилил rarpass со статической линковкой. Скорость стала на 45p/s больше. Парадоксально, но факт ;). Ну, пришлось под это дело кое-какие косметические изменения в архив внести - чтоб на XX тянуло %).

Также вот ark2 в html и незапакованный - возможно, так его будет проще читать ;). См., кстати, там, в "библиографии", теперь ссылки нормальные %).
Н-да. Раз уж пошла такая пьянка, то можно и еще что-нибудь из старенького выложить. Вот, скажем, bwt1... и shc1 (за конвертирование которого в html большое спасибо Кириллу Волошину ;).

18.01.2003 - Уже и год сменился, а я все страничку ленюсь обновить. Ну ничего, теперь вот повод возник ;). В последнее время почему-то часто стали возникать вопросы, связанные с
sh 0.02 и реализованным там методом кодирования с использованием заданного набора символов. Но ассемблера почему-то никто не понимает ;). Пришлось все-таки сделать сишный вариант (для разнообразия - с не-carryless'ным кодером ;), Итак: MarcDemo.

01.03.2003 - PiLabs, где хостилось мое самое первое зеркало (и где до сих пор лежала большая часть старых файлов), склеил ласты. Оказывается. Но теперь я это заметил и принял к сведению. Кроме того, за прошедшее время пришлось выложить несколько файлов, на которые я собрался с силами дать ссылку:
1. Работа над MarcDemo вызвала несколько новых идей по реализации rangcecoder'ов, что привело к созданию нового апдейта Aridemo. Так что теперь кроме coders6a имеется еще и coders6b.
2. Сергей Оснач зачем-то приделал к PPMY коррекцию вероятности самого вероятного символа (MPC) при помощи Secondary Symbol Estimation (SSE), что привело к некоторому повышению эффективности, особенно на бинарниках, а также появлению новой версии PPMY.
3. И еще мне захотелось поиметь возможность отображать в графическом виде разную статистику, хотя бы и при работе консольного компрессора. В результате получился класс, который поддерживает картинку в окне и позволяет легко ее модифицировать. Пример использования находится здесь ("оконный" класс содержится в paint.inc). Идеи на тему того, какую реально полезную статистику можно отображать в таком виде (два измерения, яркость, цвет) ожидаются здесь ;-)
4. Еще есть BFA, но это слишком большая тема, когда-нибудь в следующей жизни.