forum.boolean.name

forum.boolean.name (http://forum.boolean.name/index.php)
-   Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)
-   -   Как я писал самопальный архиватор (тутор-рассказ) (http://forum.boolean.name/showthread.php?t=1231)

Maxus 16.08.2006 10:59

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

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

Да ладно, в те времена этот журнал везде выходил, ZX-Ревю назывался, там и про АСМ и про загрузчики нестандартные и про гамы писали и про то как эти гамы устроены с позиции АСМа.
Я по этим книгам и познавал АСМ на Spectrume и о фишках западных программеров.

tormoz 16.08.2006 19:33

Re: Как я писал самопальный архиватор (тутор-рассказ)
 
Везде - это в центральной части России ? :)

impersonalis 16.08.2006 19:48

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

Maxus 17.08.2006 10:59

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

Сообщение от tormoz
Везде - это в центральной части России ? :)

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

impersonalis 28.08.2006 01:55

Re: Как я писал самопальный архиватор (тутор-рассказ)
 
Вложений: 4
Книга Форматы и алгоритмы сжатия изображений
3,36 МБ 8)

jimon 28.08.2006 12:50

Re: Как я писал самопальный архиватор (тутор-рассказ)
 
там jpeg2000 есть ? нет.. ну и ладно :)
(блин ну и разговоры сам с собой)

impersonalis 30.08.2006 15:41

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

pax 30.08.2006 16:43

Re: Как я писал самопальный архиватор (тутор-рассказ)
 
Интересная книжка, как будет свободное время почитаю :)

impersonalis 30.10.2007 19:42

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

zubar 10.01.2008 16:14

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

moka 10.01.2008 16:34

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

IGR 10.01.2008 18:28

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

Хм, очень часто бывают повторения в комбинации битов, дык, почему бы просто не вылавливать длинные повторения, и маленькие, и затем их вносить в список, и использовать только индекс повторения заместо вставления его полностью, таким образом можно сэкономить, но если много повторений.
МоКа, так врод и делают !! или не так ??
(о, сорри, еще один монолог :-))

Fla 10.01.2008 21:11

Ответ: Как я писал самопальный архиватор (тутор-рассказ)
 
Тоже писал когда свой архиватор. Принцип был примитивен до безобразия.

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

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

FrankH 10.01.2008 22:01

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

impersonalis 11.01.2008 00:17

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

Сообщение от zubar (Сообщение 73669)
здрасте!
тоесть чтобы всегда ,при любом раскладе из 16 бит получалось 15.
изобретал, изобретал так ничего путного и не смог сделать, но я всеравно верю что это можно сделать (если очень захотеть, можно в космос полететь)

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

Если на пальцах:
сжатие 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 файлов - каждый по биту). Не верите? - убедитесь сами:


Часовой пояс GMT +4, время: 13:24.

vBulletin® Version 3.6.5.
Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
Перевод: zCarot