Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Сжатие данных — алгоритмическое преобразование данных, производимое с целью уменьшения занимаемого ими объёма. Применяется для более рационального использования устройств хранения и передачи данных.
Сжатие основано на устранении избыточности, содержащейся в исходных данных. Простейшим примером избыточности является повторение в тексте фрагментов. Подобная избыточность обычно устраняется заменой повторяющейся последовательности ссылкой на уже закодированный фрагмент с указанием его длины. Другой вид избыточности связан с тем, что некоторые значения в сжимаемых данных встречаются чаще других. Сокращение объёма данных достигается за счёт замены часто встречающихся данных короткими кодовыми словами, а редких — длинными (энтропийное кодирование).
Все методы сжатия данных делятся на два основных класса:
Сжатие без потерь используется, когда важна идентичность сжатых данных оригиналу. Обычный пример — исполняемые файлы и исходный код. Некоторые графические файловые форматы, такие как PNG, используют только сжатие без потерь; тогда как другие (TIFF, MNG) или GIF могут использовать сжатие как с потерями, так и без.
Существуют две основных схемы сжатия с потерями:
В трансформирующих кодеках фреймы изображений или звука обычно трансформируются в новое базисное пространство и производится квантование. Трансформация может осуществляться либо для всего фрейма целиком (как, например, в схемах на основе wavelet-преобразования), либо поблочно (характерный пример — JPEG). Результат затем сжимается энтропийными методами.
В предсказывающих кодеках предыдущие и/или последующие отсчеты данных используются для того, чтобы предсказать текущий отсчет изображения или звука. Ошибка между предсказанными данными и реальными вместе с добавочной информацией, необходимой для производства предсказания, затем квантуется и кодируется.
Архівування - це процес стискування інформації (файлів, груп файлів, каталогів, цілих дисків) з метою економії дискового простору та захисту його від несанкціонованого доступу.
Оскільки в стиснутому вигляді інформацією скористатись неможливо, що особливість використовують для її захисту від несанкціонованого доступу. Тобто, при архівуванні вказують пароль на файл, що архівується. В результаті цього інформацією з файла можна скористатись лише розархівувавши її, а для цього потрібно ввести правильний пароль. Отже, архівування проводить дії:
1) Економія дискового простору;
2) Захисту інформації за допомогою пароля;
3) Зберігання резервних копій найбільш важливих інформації;
4) Швидкої передачі файла по комп'ютерних мережах.
Процес архівування чи розархівування інформацій здійснюється спеціальними програмами, що називаються архіваторами.
Архіватори бувають двох типів.
1) архіватори, що працюють в режимі командного рядка. Рядка з ними полягає введенні команд, що відповідає назві виконавчого файлу програми та завданні відповідних параметрів. Такі архіватори працюють в текстовому режимі ОС наприклад в режимі асежу MS-POS.
2) Архіватори оболонки. Програми - із зручними інтерфейсом, що полегшує виконання користувачам операції над архівами. Робота з цим архіватором полягає у виборі потрібних команд в меню, використані гарячих клавіш або маніпулятори миші. Існують архіватори - оболонки, які із зручними інтерфейсом, до ОС подібних о Windows, та і у вигляді текстового вікна.
Архіватори що працюють в режимі командного рядка поділяються на дві групи.
А) парні
Б) непарні
Парні коли одна і таж програма здійснює архівування та розархівування інформації.
Непарні - коли одна програма архівує, а інші розархівовує файли.
В процесі роботи на ПК перед користувачем часто виникає проблема нестачі дискового простору. Доводиться або знищувати менш важливу інформацію, або записувати на CD-RW, стримери чи інші носії. Та існує ще один вихід із цього становища. Це процес так званого архівування інформації.
Статистические модели алгоритмов для текста (или текстовых бинарных данных, таких как исполняемые файлы) включают:
Алгоритмы кодирования через генерирование битовых последовательностей:
Многоцелевые
Сжатие аудио
Сжатие графики
Сжатие видео
Сжатие текстов
PPM — архиватор HA (автор Harry Hirvola), использующий алгоритм PPM, известен высокой степенью сжатия на текстовых файлах; по этому параметру он превосходил первые версии появившегося несколько лет спустя RAR. Поэтому популярные в конце 90-х годов компакт-диски наподобие «Библиотека в кармане» использовали именно HA.
Примеры алгоритмов
Существуют две основных схемы сжатия с потерями:
В некоторых системах эти две техники комбинируются путём использования трансформирующих кодеков для сжатия ошибочных сигналов, сгенерированных на стадии предсказания.
Музыка
Речь
В настоящее время наиболлее распространены три стандарта хранения видеоданных: MPEG-1, MPEG-2 и MPEG-4. В рамках первых двух форматов существуют также форматы хранения звуковой информации – Layer-1, Layer-2 и Layer-3. Эти три звуковых формата определены для MPEG-1 и незначительными расширениями используются в MPEG-2. Все три формата похожи друг на друга, но используют различные уровни компромисса между сжатием и сложностью. Уровень Layer-1 - наиболее простой, не требует значительных затрат на сжатие, но и дает незначительную степень сжатия. Уровень Layer-3 – наиболее трудоемкий и обеспечивает самое лучшее сжатие. В последнее время этот формат завоевал огромную популярность. Его часто называют MP3. Такое название связано с расширением звуковых файлов, хранящихся в этом формате.
Основанная идея, на которой основаны все методики сжатия аудио сигнала с потерями, – пренебрежение тонкими деталями звучания оригинала, лежащие вне пределов которые воспринимает человеческое ухо. Здесь можно выделить несколько моментов.
Уровень шума. Звуковое сжатие базируется на простом факте – если человек находиться рядом с громко воющей сиреной, то вряд ли он услышит разговор стоящих неподалеку людей. Этот эффект носит название маскирующего, он изменяется с различием в громкости и частоте звука.
Вторым моментом является деление полосы звуковых частот на подполосы, каждая из которых далее обрабатывается отдельно. Программа кодирования выделяет самые громкие звуки в каждой полосе и использует эту информацию для определения приемлемого уровня шума для этой полосы. Лучшие программы кодирования учитывают также влияние соседних полос. Очень громкий звук в одной полосе может повлиять на маскирующий эффект и на близлежащие полосы.
Еще одним моментом кодирования является использование психоакустической модели, опирающейся на особенности человеческого восприятия звука. Сжатие с использованием этой модели основано на удалении заведомо неслышимых частот с более тщательным сохранением звуков, хорошо различаемых человеческим ухом.
Еще одним приемом сжатия является использование так называемого совмещенного стерео. Например, если в правом канале какое-то время полная тишина, это "зарезервированное" место используется для повышения качества левого канала или туда "впихиваются" необходимые биты, не влезшие в поток чуть раньше. На последней стадии сжатия используется алгоритм сжатия Хаффмана. Этот процесс позволяет улучить степень сжатия для относительно однородных сигналов, которые плохо сжимаются с помощью описанных выше приемов.
Форматы сжатия семейства MPEG сокращают объем информации следующим образом:
Цифровые системы видеонаблюдения: передача информации и алгоритмы сжатия
Практически все применяемые в видеонаблюдении алгоритмы сжатия базируются на технологии сжатия с потерями (алгоритм сжатия JPEG 2000 имеет защищенное патентами приложение, которое осуществляет сжатие без потерь), когда после декомпрессии получить изображение первоначального качества практически невозможно. Однако устройство человеческого зрения таково, что при невысокой степени сжатия искажения на полученной картинке не влияют или мало влияют на восприятие. Было установлено, что любое изображение содержит в себе избыточную информацию, не воспринимаемую человеческим глазом. Кроме того, известно, что человеческий глаз более чувствителен к яркости картинки, чем к цветности. Этот эффект на начальном этапе компрессии используют практически все алгоритмы сжатия, и объем информации на этой стадии сокращается до 2 раз без потери качества картинки.
Современные алгоритмы сжатия: классификация.
Существующие на сегодняшний день алгоритмы сжатия классифицируются по следующим параметрам.
Потоковые алгоритмы сжатия работают с последовательностями кадров, кодируя разностную информацию между опорными кадрами (алгоритмы сжатия семейства MPEG, алгоритм сжатия JPEG 2000), тогда как статические алгоритмы сжатия работают с каждым изображением в отдельности (алгоритмы сжатия JPEG и MJPEG).
В зависимости от степени сжатия, различают:
Основные характеристики наиболее распространенных алгоритмов сжатия
|
Алгоритмы сжатия |
Размер файла (цветной кадр с разрешением 720х576 пкс.) |
Величина потока оцифрованного видео с параметрами 720х576 пкс. и 25 к/с. |
||||
|
Wavelet |
50 кб |
10 Мбит/с |
||||
|
MJpeg |
25 кб |
5 Мбит/с |
||||
|
JPEG |
70 кб |
14 Мбит/с |
||||
|
MPEG-2 |
10 кб |
2 Мбит/с |
||||
|
MPEG-4 |
5 кб |
1 Мбит/с |
Найпростіший із словарних методів – RLE (Run Length Encoding, кодування змінної довжини) уміє стискати дані, в яких є послідовності байтів, що повторюються. Упаковані RLE дані складаються з байтів що управляють та байтів даних.
Якщо старший біт байта, що управляє, рівний 0, то наступні байти (у кількості, записаній в семи молодших бітах байта, що управляє) при пакуванні не змінюються.
Якщо старший біт рівний 1, то наступний байт потрібно повторити стільки разів, яке число записане в решті розрядів байта, що управляє.
Наприклад, початкова послідовність 00000000 00000000 00000000 00000000 11001100 10111111 10111011 буде закодована в наступному вигляді (виділені байти, що управляють): 10000100 00000000 00000011 11001100 10111111 10111011.
А дані що складаються з сорока нульових байтів, будуть закодовані всього двома байтами: 1010 1000 00000000.
Метод сжатия с использованием словаря — разбиение данных на слова и замена их на индексы в словаре. Этот метод является наиболее распространенным подходом для сжатия данных в настоящее время. Является естественным обобщением RLE.
В наиболее распространенном варианте реализации словарь постепенно пополняется словами из исходного блока данных в процессе сжатия.
Основным параметром любого словарного метода является размер словаря. Чем больше словарь, тем больше эффективность. Однако для неоднородных данных чрезмерно большой размер может быть вреден, так как при резком изменении типа данных словарь будет заполнен неактуальными словами. Для эффективной работы данных методов при сжатии требуется дополнительная память. Приблизительно на порядок больше, чем нужно для исходных данных словаря. Существенным преимуществом словарных методов является простая и быстрая процедура распаковки. Дополнительная память при этом не требуется. Такая особенность крайне важна, если необходим оперативный доступ к данным.
К методам сжатия с использованием словаря относятся следующие алгоритмы: LZ77/78, LZW, LZO, DEFLATE, LZMA, LZX, ROLZ.
Один из первых алгоритмов эффективного кодирования информации был предложен Д. А. Хаффманом в 1952 году. Идея алгоритма состоит в следующем: зная вероятности символов в сообщении, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью ставятся в соответствие более короткие коды. Коды Хаффмана обладают свойством префиксности (т.е. ни одно кодовое слово не является префиксом другого), что позволяет однозначно их декодировать.
Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана
Классический алгоритм Хаффмана имеет ряд существенных недостатков. Во-первых, для восстановления содержимого сжатого сообщения декодер должен знать таблицу частот, которой пользовался кодер. Следовательно, длина сжатого сообщения увеличивается на длину таблицы частот, которая должна посылаться впереди данных, что может свести на нет все усилия по сжатию сообщения. Кроме того, необходимость наличия полной частотной статистики перед началом собственно кодирования требует двух проходов по сообщению: одного для построения модели сообщения (таблицы частот и Н-дерева), другого для собственно кодирования. Во-вторых, избыточность кодирования обращается в ноль лишь в тех случаях, когда вероятности кодируемых символов являются обратными степенями числа 2. В-третьих, для источника с энтропией, не превышающей 1 (например, для двоичного источника), непосредственное применение кода Хаффмана бессмысленно.
Алгоритм Хаффмана — адаптивный жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью.
Этот метод кодирования состоит из двух основных этапов:
Адаптивное сжатие позволяет не передавать модель сообщения вместе с ним самим и ограничиться одним проходом по сообщению как при кодировании, так и при декодировании.
В создании алгоритма адаптивного кодирования Хаффмана наибольшие сложности возникают при разработке процедуры обновления модели очередным символом. Теоретически можно было бы просто вставить внутрь этой процедуры полное построение дерева кодирования Хаффмана, однако, такой алгоритм сжатия имел бы неприемлемо низкое быстродействие, так как построение Н-дерева — это слишком большая работа, и производить её при обработке каждого символа неразумно. К счастью, существует способ модифицировать уже существующее Н-дерево так, чтобы отобразить обработку нового символа.
Обновление дерева при считывании очередного символа сообщения состоит из двух операций.
Первая — увеличение веса узлов дерева. Вначале увеличиваем вес листа, соответствующего считанному символу, на единицу. Затем увеличиваем вес родителя, чтобы привести его в соответствие с новыми значениями веса потомков. Этот процесс продолжается до тех пор, пока мы не доберемся до корня дерева. Среднее число операций увеличения веса равно среднему количеству битов, необходимых для того, чтобы закодировать символ.
Вторая операція — перестановка узлов дерева — требуется тогда, когда увеличение веса узла приводит к нарушению свойства упорядоченности, то есть тогда, когда увеличенный вес узла стал больше, чем вес следующего по порядку узла. Если и дальше продолжать обрабатывать увеличение веса, двигаясь к корню дерева, то дерево перестанет быть деревом Хаффмана.
Чтобы сохранить упорядоченность дерева кодирования, алгоритм работает следующим образом. Пусть новый увеличенный вес узла равен W+1. Тогда начинаем двигаться по списку в сторону увеличения веса, пока не найдем последний узел с весом W. Переставим текущий и найденный узлы между собой в списке, восстанавливая таким образом порядок в дереве (при этом родители каждого из узлов тоже изменятся). На этом операция перестановки заканчивается.
После перестановки операция увеличения веса узлов продолжается дальше. Следующий узел, вес которого будет увеличен алгоритмом, — это новый родитель узла, увеличение веса которого вызвало перестановку.