Координатные схемы сжатия

лано, придираться)) давай мылом обменяемся у меня проблемы щас с моей прогой.

 

после того, как мы пропишем более/менее вразумительные релизы схем, я займусь доводкой метод для файлов, где совсем нет повторяющихся блоков. у этих схем есть свои подводные камни, кои можно решить лишь на огранниченом множестве частных случаев (впрочем, покажите мне чела, который захочет с етим поспорить))). и попутно пропишу алгос абсолютно бинарной сортировки - он давно у меня висит. а о других направлениях позже.

 

-----

 

UbIvItS
Ты совершенно прав:

поэтому сразу после обсждённого выше вопроса "на какой тип данных алгоритм рассчитан?"
следует второй вопрос: "насколько часто этот тип данных встречается в реальных файлах?"
Чтобы ответить на него слепил простенький тестер который ничего не архивирует, а только считает количество повторов в выбранном файле (почищу его от пробного мусора - вывешу)
Потестил им ряд файлов "с малой избыточностью" и убедился, что GIF, PiNG, CCITT Group 4 практически не оставляют за собой "CSC хвостов", небольшой "CSC избыточностью" обладает JPEG, но взять эту избыточность можно только динамической формой CSC

И наконец самое интересное:
Из концепции "берём очередную "букву" и бежим с ней до конца файла" следует сумма арифметической прогресcии
m = (1+n)*n / 2
m - количество сравнений, n - количество "букв" в файле
Так что, связь времени архивации и размера файла квадратичная и если ты собираешься заархивировать Гбайт, то 1 апреля - отличная дата для "торжественного запуска процесса архивации" )

 

самая главная проблема: ресурсоемкость - она адская, но в следующей редакции мана я выложу подходы как с ентим бороться.
а за тесты большое спасибо.

P. S.

отладочная версия, кстати, реальный маньяк - она вышибает систему в аут)

 

вот вторая версия мана: http://xproject-all.narod.ru/csc_compressing_algos_ver2.pdf

 

Тестер количества повторов в выбраном файле.
Схема работы:
На первом проходе подсчитывается количество повторов нулей.
Затем каждая четырёхбайтная "буква" ищется в остатке файла.
При совпадении "буква" затирается нулём (чтобы исключить её повторное нахождение).
Остановка тестирования кнопка Esc.

Исправил баг в подсчёте нулей и убрал безбранчевый выпендрёж, от которого в моём исполнении оказался только вред

 

Релиз, не поместившийся в предыдущий аттач.

 

сэнкс.
ты сделай, плзз.зззззз, тест на сегментную модель
сегмент 63 байта
буква 8 бит

 

UbIvItS
Если разбить файл на блоки, то чем меньше размер блоков и больше размер "букв" тем меньше время архивации и выше "идеальная степень сжатия". Однако при этом ниже вероятность встречи в реальном файле подходящих данных и соответственно хуже реальная степень сжатия.
Понятно что где-то есть разумный компромис, но он будет сильно зависеть от конкретного типа данных, так что начинать реализацию имхо стоит с набора соответсвующей статистики (т.е. делать разные варианты тестеров, смотреть что и где они смогут найти, а затем проверять "удачные с точки зрения CSC" файлы на предмет сжимаемости в rar, zip и т.п.).
И всё таки сдаётся мне, что алгоритм этот из серии "Грабли детские - предназначены для развивающих игр начинающих архивариусов"

если ход дойдёт

 

хмм..мм, а кто спорит с этим(??), правда, букву в 8 бит особо большой не назовешь, вообще -то. к тому же, ты забываешь об алгосах препроцессинга файла (BWT, к примеру, хотя свет клином на нём не сошелся). и, вообще, не понимаю с чего такой оптимизм: тот же RLE в чистом виде назвать эффективным, сильная заява(!!), но связка с BWT в корне меняет ситуацию - думаю, ты не будешь спорить, что множество файлов "дружелюбных" CSC шире, чем у RLE???

 

UbIvItS
Ну RLE в чистом виде практически и не прижился BWT штука забавная, но насколько он способен улучшить RLE я не в курсе - просто не вникал Зато CCITT "промокашки" круто рулят на чёрно-белых (2 color) текстах и графиках, хотя диапазон "дружелюбных" файлов у них ооочень узкий и расширению практически не поддаётся.
Я это к тому, что наибольшую эффективность имеют как раз не алгоритмы, имеющие множество "дружелюбных" файлов, а узкозаточенные под конкретный класс задач.

дык и абсолютный размер буквы ни о чём не говорит - вопрос насколько соотношение сегмент\буква хорошо ляжет на архивируемые данные. Хотя признаться, я совсем не ожидал, что среди Jpeg встретятся экземплярчики с 46% повторяющихся DWORD, но зато такие "шедевры" и и rar жмёт в 2 раза, причём делает это быстрее чем мой тестер оценивает - здесь как раз и кроется "источник оптимизма" )

ЗЫ: и обрати внимание я в тестере выше исправил баг и поднял скорость тестирования

 

ну, не надо выводы по сегментной модели строить на базе обычной схемы: да и сегмент в 63 байта вполне широк, учитывая, что всего 256 значений.
широта множества имеет значения, так как под конкретные типы файлов легче делать препроцессинг
CCITT - плохой пример: он по-любому будет проигывать CSC, впрочем, насчет "по-любому" - погарячился

 

т.е. 8 битная буква заменяется 7 битным значением (6 бит адреса + 1 стоп бит) - я ничего не напутал?
(это в дворде мы ещё два бита экономили в байте этого нету)
игого "идеальная степень сжатия" в 8/7 = 1,14 раза или до 87,5% от исходного размера. Не густо для случая - когда данные идеально подходят к алгоритму
Ладно стоп бит выкинем, тогда в идеале сожмётся в 8/6 = 1,33 раза, т.е. до 75% от исходного.
Что то я очень сильно сомневаюсь, что такие идеальные файлы не зарарятся раза этак в 2-3

 

я строил алгосы в расчете на малую избыточность - тексты таковыми назвать трудно)
c чего ты выкинул стоп бит)???????

 

Вот и я про тоже, что начинать нужно с того, чтобы

Хотя всё больше сомневаюсь, что они хоть где нибудь найдут то, что не ищется или не пакуется более быстрыми алгоритмами

А выкинуть стоп бит - это типа прикидка на динамическую версию )

 

ну, надо заметить, сильное утверждение: одни алгосы требуют таблицу вероятностей, другии словарь формируют вот на словарях и таблицах идёт повышение мин. кол-ва вхождений буквы, чтобы поиметь на ней выигрыш.сужение кода и использования вторичных кодов сделать лучше, нежели это есть в координатках, невозможно (если все же знаешь как это сделать, ты МОНСТР, снимаю шляпу) - единственый алгос, который способен играть на этом поле: RLE, впрочем я уже о нём говорил.

 

Y_Mur
Встречалась мне как-то статья, в которой предлагается приближать заданную двоичную последовательность (например, ту же картинку) последовательностью, порождаемой неким регистром сдвига с функцией обратной связи. Там же предлагался достаточно простой алгоритм нахождения такого регистра. Так вот, идея в том, что такой регистр сдвига "пакуется" весьма просто - нужно знать его начальное состояние и функцию обратной связи. Дальше он раскручивается и с некоторой вероятностью приближает исходную последовательность.

 

crypto
Не совсем тебя понял, но постараюсь вникнуть - если вспомнишь линк на статью - кинь пожалуйста
Это типа подобрать генератор случайных чисел, который сгенерирует требуемый файл? - интересная мысль - практически фрактальный архиватор

UbIvItS

Вот пожалуйста - "Тестер вилочный":
Наилучшее сжатие в 1,14 раза можно достичь в случае файла состоящего из 63 байтных блоков из одинаковых байт
Как думаешь по схеме RLE его нельзя сжать раз этак в 35?
--=<
Наихудшее сжатие в 1 раз (предел за которым будет "разбухание") здесь достигается уже при 50% повторов ) (количество добавленных стоп бит становится равно количеству сэкономленных за счёт соотношения 7 к 8)
В то время как LZW 50-30-20% повторов в пределах 63 байтного блока легко утрамбует

Рабочая степень сжатия CCITT на дружественных к ним файлах (книга сканированная в 2 color формате) составляет ~3-5раз по отношению к 2 color BitMap (на каких файлах CSC имеет такую степень сжатия?).
LZW в модификации GIF в этом случае проигрывает CCITT, хотя в модификации PiNG почти догоняет
Для полутоновой сканированной книги с грамотно настроенной контрастностью (нет ни фона, ни рваных краёв, ни цветовой избыточности) CCITT есно резко уступает GIF и PiNG, идущим примерно на равных
Для книги сканированной с серым фоном, GIF и PiNG проигрывают даже не предназначенному для сжатия сканированных текстов JPEGу, но и здесь речь идёт о сжатии в разы, а не на 1-10%
Зато идея "дежавю" (раздельно сжимать серый фон и контрастный текст) позволяет получить размер сжатого файла близкий, к тому, что даёт CCITT на очень сильно чувствительном к качеству сканирования 2 color аналоге этого-же текста

Я это не про то, что всё уже изобретено. Напротив, убеждён что эффективные схемы архивации ещё ждут своих открывателей , но увы CSC - ветвь тупиковая.

 

Y_Mur
Мне нужно будет хорошо порыться в архивах. А вот эта ссылка тоже представляет некий интерес (покрывающие массивы)
http://www.citforum.ru/SE/testing/combinat/