Security Teams



:::
  Ответ в темуСоздание новой темыСоздание опроса

> Алгоритмы сжатия данных без потерь
J-MiB
Дата 2.09.2007 - 13:46
Цитировать сообщение
Offline



Junior
*

Профиль
Группа: -users-
Сообщений: 36
Пользователь №: 4443
Регистрация: 7.09.2006



Рейтинг:
(0%) -----


Скажите, пожалуйста, какими они вообще бывают, в чем отличия, плюсы, минусы и тп. Можете ли посоветовать какой-то алгоритм в качестве универсального?


--------------------
Ты - мимолетное воспоминание, которое сразу забудется.
Ты не существуешь. Ты вобще не появлялся на свет.
Безымянность - твое имя. Молчание - твой родной язык.
Ты больше не чаcть общества. Ты выпадаешь из системы. Ты над ней, вне ее.
Узы порваны. Мы для всех "они". Мы - люди в черном.
PMПисьмо на e-mail пользователю
Top
VZoL
Дата 3.09.2007 - 09:28
Цитировать сообщение
Offline



Идущий
**

Профиль
Группа: -editors-
Сообщений: 79
Пользователь №: 2551
Регистрация: 6.01.2006



Рейтинг:
(50%) XXX--


Сжатие без потерь (англ. Lossless) — метод сжатия информации, при использовании которого закодированная информация может быть восстановлена с точностью до бита. Для каждого из типов цифровой информации, как правило, существуют свои алгоритмы сжатия без потерь.

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

Обычно файлы формата PNG имеют расширение PNG или png и используют обозначение MIME-типа image/png.



универсальные — Zip, 7-Zip, RAR, GZip, PAQ и др.
звук — FLAC (Free Lossless Audio Codec), Monkey's Audio (APE), TTA (True Audio), TTE, LA (LosslessAudio), RealAudio Lossless, WavPack и др.
изображения - BMP, GIF, PNG
видео — Huffyuv.

Вики рулит.


--------------------
#include <beer.h>
PMICQ
Top
drmist
Дата 3.09.2007 - 16:54
Цитировать сообщение
Offline



Professional
*****

Профиль
Группа: -users-
Сообщений: 1165
Пользователь №: 222
Регистрация: 14.04.2005



Рейтинг:
(0%) -----


Мне кажется вопрос был не про zip/7zip/png, а про алгоритмы типа Арифметического кодирования, сжатия методом Хаффмана, BWT преобразование и алгоритмы семейства LZ77 и LZ78.
Могу сказать что из последних наиболее легкие в реализации и эффективные LZSS и LZW соответственно.

Если все верно, то могу написать поподробнее, а также посоветовать посетить compression.ru


--------------------
Когда нельзя еще больше хочется...
PMСайт пользователя
Top
J-MiB
Дата 5.09.2007 - 08:27
Цитировать сообщение
Offline



Junior
*

Профиль
Группа: -users-
Сообщений: 36
Пользователь №: 4443
Регистрация: 7.09.2006



Рейтинг:
(0%) -----


drmist
Да, вопрос был не про 7zip/rar, а именно как ты сказал.
Меня интересует наиболее эффективный и универсальный метод/алгоритм сжатия, метод Хаффмана к таким, насколько я знаю, не относится.


--------------------
Ты - мимолетное воспоминание, которое сразу забудется.
Ты не существуешь. Ты вобще не появлялся на свет.
Безымянность - твое имя. Молчание - твой родной язык.
Ты больше не чаcть общества. Ты выпадаешь из системы. Ты над ней, вне ее.
Узы порваны. Мы для всех "они". Мы - люди в черном.
PMПисьмо на e-mail пользователю
Top
drmist
Дата 6.09.2007 - 19:47
Цитировать сообщение
Offline



Professional
*****

Профиль
Группа: -users-
Сообщений: 1165
Пользователь №: 222
Регистрация: 14.04.2005



Рейтинг:
(0%) -----


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

Для моделирования источника компрессор запоминает последние N обработанных им байт, называемые контекстом. N, если не ошибаюсь, называется степенью контекста. Наилучший коэффициент сжатия имеют компрессоры с N = 4. Копрессор хранит в памяти таблицы вида "в контесте 'abcd' символ 'e' появлялся 15 раз, а символ 'x' 1 раз", то есть последовательность abcde встречалась 15 раз, а abcdx - только один, таким образом вероятность появления символа 'e' в контесте 'abcd' больше вероятности поялвения 'x' и этому символу нужно поставить в соответствие код меньшей длины.

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

Все это конечно только на пальцах - на самом деле сжатие данных очень творчeское и увлекательное занятие, потому я бы настоятельно советовал для начала ознакомиться с книгой "Методы сжатия данных: устройство архиваторов, сжатие изображений и видео", авторы: Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин, а также почитать статьи с compression.ru.


--------------------
Когда нельзя еще больше хочется...
PMСайт пользователя
Top
Finder
Дата 6.06.2008 - 18:30
Цитировать сообщение
Offline



Junior
*

Профиль
Группа: -users-
Сообщений: 19
Пользователь №: 5420
Регистрация: 25.08.2007



Рейтинг:
(0%) -----


Интересует , нет ли в винде встроенных средств сжатия ?
api , чтобы делать cab или zip архивы .Я пока не нашел sad.gif .

И еще . Сколько примерно по времени уйдет , чтобы разобраться с упаковкой досконально ? Всмысле , если поднимать свой упаковщик на lzma с 0 ?
PMПисьмо на e-mail пользователю
Top
Ymnica
Дата 23.10.2009 - 02:42
Цитировать сообщение




Unregistered












Классический алгоритм Лемпеля-Зива – LZ77, названный так по году своего опубликования, предельно прост. Он формулируется следующим образом : "если в прошедшем ранее выходном потоке уже встречалась подобная последовательность байт, причем запись о ее длине и смещении от текущей позиции короче чем сама эта последовательность, то в выходной файл записывается ссылка (смещение, длина), а не сама последовательность". Так фраза "КОЛОКОЛ_ОКОЛО_КОЛОКОЛЬНИ" закодируется как "КОЛО(-4,3)_(-5,4)О_(-14,7)ЬНИ".
Пример- закодировать строку красная_краска с помощью алгоритма LZSS

https://www.intuit.ru/img/tex/1277330baccad...0aad930864e.png
Top

Опции темы Ответ в темуСоздание новой темыСоздание опроса