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

[impersonalis]

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

[impersonalis]

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

000010000000
000111000000
000010000000
000111110000
000101011111
011111112221
012222222210
001222222100
000111111000

Ну а точнее, вот так:

000010000000000111000000000010000000000111110000000101011111011111112221012222222210001222222100000111111000

Попробуйте теперь переписать это куда-нибудь вручную. Наверняка вы не будете приговаривать местами: «один-один-один-один-один.», а скажите: «пять единиц». Это будет удобнее, но главное это будет БЫСТРЕЕ и занимает куда как меньше места.
Теперь осталось придумать, как развить зачатки данного алгоритма.

[impersonalis]

Как, например, закодировать сочетание «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».

[impersonalis]

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

[impersonalis]

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

[SubZer0]

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

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

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

хз как называется, архивируются им такие файлы, как картинки, где есть длинные строки с одинаковыми значениями... там делается управляющий код, например "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 процессоров...

[impersonalis]

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

За отзыв - спс

[impersonalis]

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

[tormoz]

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

[SubZer0]

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

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

[alcoSHoLiK]

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

[impersonalis]

Сообщение от SubZer0

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

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

[SBJoker]

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

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

[Maxus]

Сообщение от tormoz

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

Ну вот это ты зря.
Литературы хоть ПОПОЙ Ешь было тогда, возьми хотябы ZX-Ревю.

[tormoz]

Ну вот это ты зря.
Литературы хоть ПОПОЙ Ешь было тогда, возьми хотябы ZX-Ревью

Я книжку по спектрумовскому асму в Киеве заказывал, и переплачивал в 250 раз от номинала, а ты про превью какие то.
У нас в городе не фига не было.
Из всей комп-литературы - "Осваиваем компьютер" с 8 уроками на 40 страницах по Бейсику неизвестной модификации