Как я писал самопальный архиватор (тутор-рассказ)
 

Как я писал самопальный архиватор (тутор-рассказ).
Когда я учился в школе и не имел под рукой ни Интернета, ни друзей-программистов, меня как-то начал мучить вопрос: ну КАК работает архиватор? Информации не было никакой, и я решил написать с нуля своё детище (надо сказать, и сейчас, порой меня терзают не менее амбициозные планы, но осознание «изобретения велика» меня тормозит).
В общем-то, тутор будет полезен тем, что алгоритм довольно простой (архиватор я писал на С++, но его нетрудно написать и под b3d) т.к. я в нём смог разобраться, будучи школьником, ну и покажет ход моих размышлений, а также принцип работы (а то один мой одноклассник долго меня уверял, что благодаря хитрой математической формуле можно ВСЕГДА из двух символов получить один!).

Re: Как я писал самопальный архиватор (тутор-рассказ)
 

Думы.
Не знаю почему (вероятно, потому, что перед этим некоторое время ковырялся во внутренностях bmp-файлов, и нашёл несколько интересных вещей – но об этом в другой раз). Вывод алгоритма (а не бесполезные попытки преобразовать-перекодировать информацию в попытке сэкономить место) я начал с раздумий над картинкой.
Возьмём картинку и предположим, что один квадрат картинки мы кодируем цифрой – кодом цвета данного квадрата. Разумеется, мы укажем где-то в файле (в *.bmp – это делается в начале) размеры картинки – это удобней и экономичней.
Таким образом, наша картинка в файле будет выглядеть так (размеры пока не пишем):
Ну а точнее, вот так:
Попробуйте теперь переписать это куда-нибудь вручную. Наверняка вы не будете приговаривать местами: «один-один-один-один-один.», а скажите: «пять единиц». Это будет удобнее, но главное это будет БЫСТРЕЕ и занимает куда как меньше места.
Теперь осталось придумать, как развить зачатки данного алгоритма.

Re: Как я писал самопальный архиватор (тутор-рассказ)
 

Как, например, закодировать сочетание «11»? Две единицы. Написать «21»? Но ведь у нас может встречаться сочетание «21» в значении 2-1.
Не мудрствуя лукаво, я просматриваю весь файл, попутно отмечая в булевом векторе кодов, встреченные символы. В данном случае, не встречается цифра «3». Её и будем использовать, попутно указав её в начале файла (чтобы знать, на что ориентироваться, получить как-либо иначе эту информацию из сжатого файла не удастся).
Таким образом, сочетание «11», будет закодировано как «321». Символ «3» даёт понять, что после него записан блок данных для разархивации, символ «2» интерпретируется как число «два», обозначающее, что символ «1» (он идёт за числом) надо повторить два раза.
И что мы имеем? Было «11» стало «321»?! Хорошенький архиватор, ничего не скажешь, скорее громоздкий кодировщик. Сразу же делаем поправку – сжимать только последовательности, длиной больше (или равную)4х символов.
Всё вроде нормально, но как данный алгоритм обработает сочетание из пятнадцати единиц? «3151». Это сочетание будет воспринято как одна пятёрка, т.е. «5». Значит, нужно усложнить структуру блока.
«3-число-3-символ» - казалось бы, выход, но теперь неправильно будут обработаны сочетания, например из 30 единиц, т.к. «33031» -вероятно вообще закрешится на обработке. Поэтому вносим следующие коррективы:
1)числа кодировать только цифрами (напоминаю, можно использовать символы, т.е. все 256 вариаций байта) – это негативно скажется на сжатии, но позволит избежать более «сложного» (на тот момент для меня невозможного) анализа.
2)Соответственно спец. символ выбирать НЕ из цифр.
3)Минимальную длину последовательности увеличить до 5 символов.
Теперь, допустим, мы выбрали символом-индикатором - %. Предыдущий блок из 30 единиц будет закодирован как «%30%1».

Re: Как я писал самопальный архиватор (тутор-рассказ)
 

Вдоволь наигравшись с архиватором, я ввёл ещё одну фишку: сочетание «1111» кодировать как «%%1», т.е. если вместо числа стоит пустота (0), то это по дефолту -4. Это нововведение позволяет сжимать последовательности из 4х символов, что раньше было невозможно (см. поправку №3).
Учитывая, что в несжатой музыке «wav» или картинках «bmp» один символ может образовывать последовательности в сотни и тысячи символов – архиватор весьма неплохо работал. Моё любопытство было удовлетворено.

Re: Как я писал самопальный архиватор (тутор-рассказ)
 

Что в данном алгоритме можно улучшить (не уходя далеко от выбранной модели архивации):
-реализовать возможность выбора в качестве спец. символа сочетания
-обрабатывать не сочетания не только символов, но и групп («123123123123»)
-кодировать числа (указывающие кол-ва повторений символами – 256 вариаций), добавив соответствующую обработку в блоке вычленения числа.

Re: Как я писал самопальный архиватор (тутор-рассказ)
 

Супер!!! ты крут!!! :super: :super:

чесно сказать я сам так и не смог выдумать ниодин метод архивации... а потом мы это проходили в технаре... дак вот...

метод похожий на твой:

хз как называется, архивируются им такие файлы, как картинки, где есть длинные строки с одинаковыми значениями... там делается управляющий код, например "31", после этого идет сам символ, и сколько он должен повторяться... таким образом выбираются только данные которые повторяются три раза, и заеняются на управляющие символы... а если встречается 31 как данное, то заменятеся на код 31, 31, 1....

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

еще есть метод, мне он само больше нравится (чисто представляю извращенную логику чела который это выдумал)... называется "коды переменной длины"... проходит на битовом уровне... там делается следующим образом: байт - 8 бит - 256 значений... заметили что текст (простой) содержит (обычно) всего не более 90 различных байт (включая скобки там и т.п.)...
подбивается статистика файла какая буква встречается само часто... в русском языке это "О" или "П"... выстраивают сортированный список по частоте... самую частовстречаемую букву заменяют на "1", вторую по встречаемости букву заменяют на "01", третью на "001", четвертую на "0001"... таким образом мы получаем свободные биты в байте часто встречаемых букв, и они вполне компенсируют перебор битов маловстречаемых... и в результате архив превращается в длииинную строку из нулей и единиц...

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

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

есть еще сжатие звука... звук это всеголишь набор чисел... например от -32768 до 32768, число указывает в какое положение выставить динамик колонки... -32768 само далеко втянуть, 32768 само далеко выставить вперед... оцифровка проходит обычно 44 тысячи раз в секунду (есть разные форматы)... таким образом для сохранения одной секунды звука нам потребуется 44000*2 байта(16 бит)=88000 байт... но придумали метод сжатия... проследили по времени... значение практически не изменяется больше чем на 16... т.е. если предидущая высота динамика была 23449 то следующая не будет отличаться от нее больше чем на 16... ну и нафига хранить каждое значение?... записывают начальное значение а потом на сколько оно должно измениться... это занимает нааамного меньше бит...


но это все методы которые были изобретены еще во времена 86-87 процессоров...

Re: Как я писал самопальный архиватор (тутор-рассказ)
 

Ну в общем основная идея была:
1) показать просой вариант
2) показать, что до много можно додуматься самостоятельно - полезно.
Так как недолюбливаю "эрудитов" пред олимпиадой прочитают все вопросы с прошлых/других олимпиад и готово. А вот влоб задай ему вопрос, так он и до сортировки пузырьком не разродиться если б в кнжке не прочёл. Не прогер - а сборник алгоритмов. Если что не знает - своё придумать не сможет, будет подгонять готовое решение =/

За отзыв - спс

Re: Как я писал самопальный архиватор (тутор-рассказ)
 

Да и чтобы ты там не думал - никаих лекций по сжатию не было у меня. Тем более в школе - где мне объяснили только кусок basic( я его,правда, сам прочитал уже после С++).У нас и инфа то была год или два. У преподши спрашивал. Она сказала - "не знаю как это рабоает".

Re: Как я писал самопальный архиватор (тутор-рассказ)
 

Гы...
А я писал архиватор еще на спектрумовском асме, для своей игры.
Карты сжимал. Алгоритм тоже сам придумал (отстойный) Литературы не читал ваще никакой (тогда ее в природе не существовало на рус языке) в школе информатики тоже не было.

Re: Как я писал самопальный архиватор (тутор-рассказ)
 

Не, думать конечно надо самому, это очень полезно... хоть я и архивацией не занимался, но зато вполне рабочий аналог А* сам придумал... незадолго до того, как мы его по высшей математике прошли...

а книжных червей программистами обычно не называют... ;)

Re: Как я писал самопальный архиватор (тутор-рассказ)
 

Хороший туториал.

Re: Как я писал самопальный архиватор (тутор-рассказ)
 

С путенахом тоже игрался ;)

Re: Как я писал самопальный архиватор (тутор-рассказ)
 

Хм. мож я чёто недогнал, но нафик кодировать всё символами? Читаем байты и байты же пишем, т.е. в твоём примере 255 единиц будет записано так(коды байтов): {3}{1}{255}, в этом случае нам нужно ввести условие на макс. цепочку одинаковых символов...

Я тож писал архиваторы как-то, но первый был основан на поиск в строке подстрок... сжимал почти всё но несильно..

Re: Как я писал самопальный архиватор (тутор-рассказ)
 

Re: Как я писал самопальный архиватор (тутор-рассказ)
 

Re: Как я писал самопальный архиватор (тутор-рассказ)
 

Re: Как я писал самопальный архиватор (тутор-рассказ)
 

Re: Как я писал самопальный архиватор (тутор-рассказ)
 

Re: Как я писал самопальный архиватор (тутор-рассказ)
 

Я жил тогда в Ташкенте, богом забытом Узбекистане.
А вообще в свое время я на Спектруме разработал систему сжатия по методу Хаффмана, тогда я даже незнал, что чел ее изобрел.
Мне казалось что это самый крутейший алгоритм сжатия.

Re: Как я писал самопальный архиватор (тутор-рассказ)
 

Книга Форматы и алгоритмы сжатия изображений
3,36 МБ 8)

Re: Как я писал самопальный архиватор (тутор-рассказ)
 

там jpeg2000 есть ? нет.. ну и ладно :)
(блин ну и разговоры сам с собой)

Re: Как я писал самопальный архиватор (тутор-рассказ)
 

Re: Как я писал самопальный архиватор (тутор-рассказ)
 

Интересная книжка, как будет свободное время почитаю :)

Re: Как я писал самопальный архиватор (тутор-рассказ)
 

Re: Как я писал самопальный архиватор (тутор-рассказ)
 

здрасте!
я тож придумывал разные способы архивирования в основном работал напрямую с битами, основная цель была сделать суперархиватор, тоесть чтобы всегда ,при любом раскладе из 16 бит получалось 15.
изобретал, изобретал так ничего путного и не смог сделать, но я всеравно верю что это можно сделать (если очень захотеть, можно в космос полететь)
ща обдумываю два направления:
1) метод растущего дерева (сам придумал название:) )
"короче, изначально было семя потом оно потихоньку проросло в ствол, а потом ствол разветвился, а потом ещё и ещё и получилось много веток"
имеются исходные несколько байт (заархивированный файл), потом "какимито непонятными, ещё не придуманными способами" байты образуют новые байта, а те новые, и через некоторое время получаем разорхивированный файл
2) родилчик (тоже сам придумал)
код1 рождает код2, код2 рождает код3 и т.д и т.п
осталось придумать алгоритмы которые смоглибы такое организовать

Ответ: Как я писал самопальный архиватор (тутор-рассказ)
 

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

Ответ: Как я писал самопальный архиватор (тутор-рассказ)
 

МоКа, так врод и делают !! или не так ??
(о, сорри, еще один монолог :-))

Ответ: Как я писал самопальный архиватор (тутор-рассказ)
 

Тоже писал когда свой архиватор. Принцип был примитивен до безобразия.

{код символа}
Т.к. таблица носки состоит из 128 основных символов и 128 дополнительных, то делаем так. Юзаем символ с кодом 0 как кодировочный. Собственно символы с кодами до 128 оставляем без изменения, а от {128-255} заключаем их между {0}, вычитая из кода каждого символа 128. Т.к. {128+0} это большое русское А(у нас=)) то при раскодировке все в лучшем случае неправильно раскодируется, то 'А' будем кодировать как {0}{0} (да, смайлик, я знаю).
Тогда строка "АБВГДЕЖЗЕИ" будет представлена как {0}{0} {0}коды букв - 128{0}
В чем же архивирование? У нас была 256-ричная система, а стала 128-ричная. Т.е. уменьшилась в 2 раза! Теперь мы все это побитово записываем в файл. При этом один символ у нас занимает не 8 позиций, а семь!
Ну а разархивировать это дело совсем просто.

*Кстати русские тексты, аски-арт(и вообще все, где преимущественно символы от {128} до {256} архивирует на ура=)
**Сейчас пороюсь и выложу сырцы
***Не нашел, оказывается я эту хрень на асме писал. Ну как на асме, на ++ со вставками.

Re: Как я писал самопальный архиватор (тутор-рассказ)
 

Еще сидя за "системником" ZX и изучая асм, прочел о примитивнейшем методе сжатия - составление базы "пустых" блоков. Тогда показалось интересным и не более.
Лет семь назад захотелось попробовать прогать на С, а сделать решил свой кодировщик, но так как собирался добавлять ключ для кодировки то под него надо было освободить в файле место, обычный метод был не лишним, но не актуальным при кодировании архивов и проч. Пришлось написать свой алгоритм, родил за пару дней приблизительно такой принцип:
1) бьем файл на блоки, анализируем на соответствие блока маске из готового набора. Маска должна увеличить число пустых битов в байте.
2) если необходимо, делаем вычитания или прибавления по маске, инфу о маске сохраняем в базу(например: блок,маска№5)
3) теперь у нас есть какой-то процент блоков, имеющих по четыре свободных бита в байте, смещаем байты и смешиваем блоки так, чтобы заполнить пустоты в байтах.
4)повторяем процедуру до потери актуальности..
Проверялось все на бумаге, и работало со случайным набором символов уменьшая файл на 10 и более процентов. Был так е вариант без масок, уменьшение размера от 4% :)
после недели долботни то ли с Сишными, то ли с компиляторскими глюками забил на С вообще.. :( Блитца тогда не знал..

Ответ: Re: Как я писал самопальный архиватор (тутор-рассказ)
 

Не люблю это слово - но это невозможно.
Тому можно привести много подтверждений из различных дисциплин, все они, так или иначе поднимаются в курсе Теории Передачи Информации.

Если на пальцах:
сжатие 16 бит до 15.. положим даже так N сжимаем до T (где T<N).
Получаем, что после архивации имеем вместо N бит - T.
Обозначим частное N/T за J. J>1 (исходя из утверждения, что T<N)
Таким образом, T=N/J. Т.е. ratio архивирования составляет const J.
Далее заключим следующий факт:
Для любого количества архивируемой информации, измеряемой M, найдётся такое кол-во проходов сжатия (итераций архивирования) S, что M` (размер информации после многократного сжатия) M`->0 Принимая во внимание логику задачи: любой сколь угодно большой файл лбой энтропии всегда можно сжать до 1 байта, и даже меньше (например в одном байте хранить 8 файлов - каждый по биту). Не верите? - убедитесь сами:

Ответ: Как я писал самопальный архиватор (тутор-рассказ)
 

2FrankH
чем-то похоже на преобразование Барроуза — Уилера
2Fla
интересная идея, но архиватор узконаправленный (ориентирован на кириллический текст), для файла же с равномерным распределением значений байтов - архивация ->0 (ну собсно, этим все архиватор страдают в той или иной степени)

Ответ: Re: Как я писал самопальный архиватор (тутор-рассказ)
 

Можно проще объяснить: с помощью 16 бит можно задать 2^16 разных значений (например целое число 0...65535), с помощью 15 бит - 2^15 разных значений, т. е. в 2 раза меньше.
Значит хотя бы для двух исходных последовательностей получим одну и ту же на выходе. Но тогда как ее разархивировать? Ведь неизвестно, какой из 2 вариантов был заархивирован.

Ответ: Как я писал самопальный архиватор (тутор-рассказ)
 

легких путей не ищем, трудностей не боимся ;)

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

Ответ: Как я писал самопальный архиватор (тутор-рассказ)
 

Matt Merkulov
если возьмем функцию хеширования F(data)
только с одним словием :

y = F(data)
при одном и том же y может быть несколько значений data
но все ети data имеют разную длину

или возможно есть несколько комбинаций data одинаковой длины
но ихнее количество сведено к минимуму

для передачи информации нам нужен y,размер и комбинация етой data :)

ну вот мой мозг не может пока опровергнуть существование такой функции

RLE )

ты и описал принцип работы архиватора. Он реален.
Я лишь утверждаю - что не существует и не может существовать вообще алгоритма, кторый всегда сжимает W байт в Q байт (Q<W).
Для твоего случая: описатель комбинации data может быть эквивалентен по длине самой data, да в придачу к нему надо передать ещё и хеш.
Если уж мы начали строить всё более абстрактные модели:
вспомните золотое правило механики (именно равновесие, описанное этим правилом является ключевым для природы). Вечных двигателей не бывает - кпд не досигнет 100%

Ответ: Как я писал самопальный архиватор (тутор-рассказ)
 

У меня была идея о том, что можно сделать архиватор, в котором будут собраны всевозможные алгоритмы сжатия, каждый из которых наиболее эффективен для опр. "структуры" данных. Он будет подбирать наиболее эффективный алгоритм, архивировать данные и ставить номер алгоритма в начале. Если не удалось найти алгоритм, то ставить 0 (т. е. данные без сжатия).

Т. о. в самом неудачном случае длина выходного потока данных будет на 1 байт больше.

Ответ: Как я писал самопальный архиватор (тутор-рассказ)
 

"тоесть чтобы всегда ,при любом раскладе из 16 бит получалось 15.
изобретал, изобретал так ничего путного и не смог сделать, но я всеравно верю что это можно сделать (если очень захотеть, можно в космос полететь)". Имхо можно примерно так сделать, и указывать при распаковке, какой тип файла в архиве. Например jpeg, mp3, wav... А архиватор подбирает несколько подходящих под сжатый файл последовательностей ищет сигнатуру заданного типа. Разумеется в архиве только один файл.