Здравствуй , дорогой васмовец , однако. Моя засучил рукава писать свой упаковщик . Зашел на compression.ru . Скачал "Методы сжатия данных . Устройство архиваторов , сжатие изображений и видео " , как некоторые рекомендовали . Прочел страниц 30 и выпал в тильт . Авторы - люди жестко повернутые на математике ( Понять их мне совсем тяжело , однако . Я один такой чукча , который не знает про ряды Фирбоначчи и не помнит логарифмов и операций со множествами ? в общем , если кто знает , где без лишней математики вкурить эту тему , да наставит меня на путь истинный .
Ну если в двух словах. После сжатия у тебя получается два массива данных: 1 - Словарь (например все слова русского языка) или просто набор сочитаний байт, но которые очень часто повторяются. 2 - Непосредственно массив сжатых данных. Словарь сортируется по частоте повторений в исходном файле. Если очень часто то на первое место и так ... Таким образом сжатый файлик хранит указатели на данные из словаря (порядковые номера слов из словаря).
словарь - дело вторичное а вот написать хороший алгоритм для поиска одинаковых последовательностей - вот это сложно
Пример , это неплохо конечно . Но хотелось , для начала , разобраться в общем какие сегодня есть алгосы и чем оне движимы . В двух словах про словарь я , конечно , догадываюсь . Теперь нужно понять до уровня реализации . 2wsd : Спасибо , полезная пага. Нормально усваивается организмом . 2Colibri : А разве поиск последовательностей не есть часть алгоса упаковки-распаковки ? Или все его по своему ваяют ?
Hmm О какой реализации речь, если даже такая простая книга вызывает кучу вопросов? Она написана на основе курса лекций и ОЧЕНЬ доступна для любого, кто сам закончил школу, имхо. Сначала надо почитать "про ряды Фирбоначчи и не помнит логарифмов и операций со множествами". А то из желания "Моя засучил рукава писать свой упаковщик" вырастет очередной проект на основе TZip. И еще вопрос. А почему тема в WIN32? Это или в Algo, или в Beginners.
Hmm Курить на compression.ru статьи про метод упаковки Берроуза-Уилера. Лучше всего - непосредственно авторские. Метод хорош тем, что дает офигенную степень сжатия (сравнимую с арифметиком, лучше которого еще ниче не придумали) и очень высокую скорость распаковки (сравним с алгоритмами LZ77-78). Для пакера - самое милое дело. Если с английским проблемы - напиши мне ЛС с контактом, я пришлю свой перевод (хороший перевод =)).
2Xerx : Ну . в целом я не имею цели потеснить 7zip или upx . Скорее просто создать для своих личных целей криптор-паковщик . Если книга и правда хорошая , придется ее и дальше грызть . Для бегиннерс , наверно , тема чересчур . А Algo это - "Обсуждение алгоритмов и техник оптимизации кода." . Хотя модерам виднее . 2dead_body : Спасибствую . 2IceFire : С английским нормально . Другое дело , что лениво . Так что переводы мы , вольные жители севера , всегда одобрямс .
Hmm http://compression.ru/download/articles/bwt/burrows_wheeler_1994_ps.rar Перевод не прикрепляется, давай почту.
IceFire Преобразование Барроуза-Уиллера (BWT) - это не сжатие! На то оно и преобразование. Оно лишь делает последовательность более детерминируемой для пакера => он чаще угадывает смену контекста => сжатие лучше. После BWT применяют еще некоторые преобразования (например стопка книг) и _только потом_ уже сжимают (тем же арифметическим сжатием). Да и не факт, что после преобразования входной поток улучшится. И скорость там не сказал бы что очень высокая (скорость обратного преобразования, а не распаковки). Hmm На compression.ru есть много по всем стадиям преобразования и по русски. А в книжке "Методы сжатия данных" вообще даются примеры с картинками по стадиям
Xerx Ага, справедливо. Действительно, это только преобразование. Но качество выходного потока становится лучше - об этом говорят многие тесты (см. ссылку). Есть довольно производительные алгоритмы с использованием BWT. К примеру - BWT+MTF (стопка книг)+DC. А финальной стадии сжатия вообще посвящено несколько научных работ.
IceFire Как раз про стопку книг я и говорю. У меня у самого диплом магистра основан на BWT+MTF+RC. А в основе (первый шаг) лежит DWT (целочисленное вейвлет-преобразование). И я в курсе об эффективности BWT А ТС рекомендую начать с простого: RLE, Лемпель-Зив (LZ-77 вроде), Хаффман с фиксированными таблицами. Вдруг и этого будет достаточно для его пакера.
