Для чего нужно сжимать файлы
Первые персональные компьютеры обладали небольшой дисковой памятью. Чтобы перенести файлы и программы с одного компьютера на другой, их записывали на гибкие дискеты малой емкости. Памяти катастрофически не хватало. Дефицит памяти естественно побудил компьютерщиков искать способы экономной записи файлов. Одним из таких способов стала компрессия или сжатие информации. Оказалось, что во многих случаях файл можно после преобразования специальной программой сделать гораздо меньшим по размеру. Программы сжатия стали называть архиваторами. Сегодня мы на примере одной любопытной истории подробно расскажем о такой полезной для каждого пользователя функции, как сжатие файлов.
Закономерно возникает вопрос: а зачем сейчас нужно сжимать файлы, если все основные технические характеристики персональных компьютеров каждые полтора-два года удваиваются? Оперативная память современной персоналки от 128 до 512 мегабайт, дисковая память вообще исчисляется десятками гигабайт. Казалось бы, можно особенно не заботиться о размерах файлов.
Но интерес к сжатию файлов по-прежнему высок. Можно выделить две основные причины такого интереса. Первая, на персональных компьютерах стали воспроизводить и обрабатывать звук и изображение. Звуковые, графические и особенно видео файлы по объему памяти требуют на порядки больше памяти, чем текстовые. Одна фотография 15х20 см с хорошим разрешением 600 точек на дюйм или всего одна десятиминутная музыкальная композиция по объему превышают собрание сочинений Чехова.
Вторая причина интереса к сжатию, пересылка файлов по электронной почте и скачивание с Интернет-узлов звуковой и графической информации. Пропускная способность обычных интернетовских линий не позволяет быстро пересылать файлы, превышающие несколько мегабайт, и поэтому многие серверы просто не пропускают большие файлы или искусственно ограничивают у пользователя скорость передачи информации. Поэтому сжатие файлов по-прежнему актуально.
Архиваторы уменьшают некоторые файлы в 5-10 раз. За счет чего удается так сильно сократить размер файла? Некоторые файлы построены неоптимально с точки зрения их объема. Например, распространенные архиваторы сжимают большие файлы Microsoft Word в пять-шесть раз, а маленькие почти в десять. Чтобы прочесть такой сжатый текстовый файл, его нужно разжать той же самой программой.
Многим пользователям поначалу приходила в голову блестящая мысль - попробовать сжать ещё раз уже сжатые файлы. Первая же попытка разочаровывает - сжатые файлы дальше не сжимаются, причём у всех архиваторов. Почему так происходит?
Дело в том, что файлы представлены в памяти компьютера как длинные числа. А число любой заданной длины, в общем случае, нельзя точно передать числом меньшей длины, даже если оно короче всего на одну цифру. Из-за этого единственным способом сжатия данных является поиск в них некоей избыточной информации или закономерностей. Избыточную информацию можно удалить, а закономерности использовать для кодирования похожих фрагментов меньшим количеством байт. Значительное сжатие аудио-файлов стало возможно, потому что часть записанного звука ухо среднего человека не различает, или его не раздражает потеря некоторой звуковой информации.
Когда программа обработала файлы соответствующим образом, нашла закономерности, удалила малозначимую информацию, то вторично она уже эту операцию провести не сможет. Поэтому при повторных сжатиях файл не уменьшается. Может показаться странным, но избыточной информации нет и в случайных данных, например в записях шумов радиоприемника на частоте, где нет передающих станций или в результатах работы программы - генератора случайных чисел. Дело в том, что в наборе действительно случайных чисел архиватор не может найти закономерностей. Получается, что и в сжатой энциклопедии, и в результатах тиражей Спортлото машина не может найти избыточную информацию, хотя энциклопедия - это концентрат знаний, а тиражи Спортлото - длинный набор случайных цифр.
Итак, основной принцип сжатия - это поиск закономерностей. В случайных данных закономерностей нет, и поэтому теоретически их сжать абсолютно невозможно. Несжимаемость, с точки зрения теории информации, - это фундаментальное свойство ряда случайных чисел. Однако весной прошлого года произошла история, где это утверждение подверглось серьезному испытанию. История эта тем интереснее, что её главный герой - не учёный, а находчивый дилетант, хорошо понимающий, что важны не только фундаментальные принципы, но и способы их программной реализации. Но расскажем об всём по порядку.
Как правило, речь идет о том, что сотрудники малоизвестной компании разработали революционный алгоритм или даже программу для многократного сжатия информации. Обычно утверждается, что сжатие идёт без потерь, и (самое главное) - во много раз сжимается любая информация. При внимательном рассмотрении оказывается, что это - блеф, но, тем не менее, эта idea fix регулярно возникает на страницах компьютерной прессы. Характерный пример. В апреле 92-го года компания WEB Technologies объявила о создании программы, сжимающей в 16 раз любые файлы размером больше 64-х килобайта. Были другие фирмы, которые заявляли о столь же удивительных параметрах своих программ. Некоторым из них удалось даже запатентовать собственные алгоритмы, однако, в результате, подобные проекты оказались мыльными пузырями.
Это, конечно, не значит, что компрессия данных, как направление, больше не развивается. Наоборот, едва ли не каждые полгода появляются новые алгоритмы или совершенствуются старые, сжимающие данные всё сильнее и сильнее. Особенно заметен прогресс в компрессии звука и видео. Если десять лет назад для записи обычного фильма требовались два огромных лазерных диска размером с большую грампластинку, то сейчас для достижения близкого качества достаточно одного CD-ROM-а, и судя по всему, это не предел. Такие успехи создают у неспециалистов иллюзию, что сжимать можно всё и очень сильно, надо только придумать алгоритм. Но не надо забывать, что популярные алгоритмы сжатия звука и графики сжимают данные с потерями. Это означает, что они не столько сжимают информацию, сколько удаляют из неё фрагменты, удаление которых не режет слух и не бросается в глаза. Но даже непрофессионал, если у него есть возможность сравнить, услышит разницу между действительно качественным звуком и сжатыми файлами.
Если говорить о сжатии без потерь, то в нём уже давно не было пионерских работ. Последний принципиально новый алгоритм безпотерьного сжатия был изобретён в 80-х годах и пока мало применяется из-за большой сложности. Кроме того, как уже говорилось, есть данные, которые вообще нельзя сжать без потерь. Это, во-первых - случайная информация, а во вторых - сжатая ранее. Если допустить, что компрессор сжимает без потерь любые файлы, то можно взять файл и уменьшить его один раз, затем опять пропустить через компрессор и опять уменьшить. Если операцию повторять снова и снова, то, в конце концов, файл сожмётся до одного бита, сохранив всю полезную информацию, что, конечно - абсурд.
Я готов заплатить пять тысяч долларов любому, кто выполнит следующие условия. Вы сообщаете мне, какого размера файл можете сжать, и в доказательство своей серьезности присылаете мне 100 долларов. Я генерирую файл и высылаю вам. Вы изучаете его сколько хотите, затем сжимаете и присылаете мне вместе с программой для разжатия. Я разжимаю файл и проверяю - не была ли потеряна информация. Если не была, и сжатый файл вместе с вашим декомпрессором хоть сколько-нибудь меньше исходного файла, я заплачу вам 5 тысяч, плюс ваши 100 долларов.
Патрик Крейг
Я прочитал ваше предложение. Звучит очень заманчиво, оно всё еще в силе? Если да, то хотелось бы узнать детали о декомпрессоре - он должен запускаться на любой машине или достаточно какой-то одной платформы, например Linux?
Майк Голдмен
Да, предложение в силе. Linux-а достаточно. Вы хотите рискнуть?
Патрик Крейг
Я всё еще думаю над этим. Вам нужен только сжатый файл?
Майк Голдмен
Вы говорите, какого размера файл нужен, и присылаете мне 100 долларов. Я генерирую файл и высылаю вам. Вы присылаете мне его сжатым вместе с декомпрессором. Если сжатый файл вместе с декомпрессором меньше оригинала - я высылаю вам 5 тысяч. Если у вас не получилось - можете опять прислать мне 100 долларов и попробовать ещё раз.
Патрик Крейг
А могу я прислать сжатую информацию не одним файлом, а несколькими частями, плюс декомпрессор, который восстановит оригинал?
Майк Голдмен
Патрик Крейг
Майк Голдмен
Пришлите чек или банковский перевод. Если вы закажете очень большой файл, то должны обеспечить соответствующий носитель. Вы уже решили, какой размер вам нужен?
Патрик Крейг
Я до сих пор думаю над оптимальным размером, но полагаю, он будет меньше гигабайта. У вас есть где-нибудь доступ к анонимному ftp-серверу?
Александр Костинский
Далее идёт обсуждение мелких деталей, из которых выясняется, что обладатель чудо компрессора - англичанин. Он сейчас живёт в Японии, откуда не может послать чек в США Майку, поэтому вышлет деньги наличными по почте. Видя, что вызов принят, Майк пробует выяснить - каким же способом Патрик собирается выполнить теоретически невозможные условия, но тот не сдаётся, отвечает: "подожди, увидишь" и высылает деньги. Заметим, что переговоры уместились в одиннадцать электронных писем и прошли всего за несколько часов. Наличные идут по обычной почте из Японии в США четверо суток. Майк получает деньги и Патрик сообщает ему размер файла, который он готов уменьшить. Он требует 3 мегабайта. Но что же предлагал сжать всем желающим Майк Голдмен?
Человек, рискующий пятью тысячами долларов, должен позаботиться о несжимаемости своих данных. Совершенно несжимаемая информация, как уже говорилось - набор случайных чисел. Но, оказывается, гарантированно получить такой набор - не такая простая задача. Программа всегда строго следует алгоритму и в результате ее работы могут быть сгенерированы лишь псевдослучайные числа. При этом нет уверенности, что данный ряд чисел не может быть повторен или сгенерирован подобной программой. Настоящий хаос можно найти только в событиях реальной жизни.
Что же сделал с ними Патрик Крэйг? Свою версию событий он поместил в Интернете:
Патрик Крейг
Тот, кто предлагает вам такое пари, наверняка знаком с теорией информации и, скорее всего, предложит для сжатия данные какого-нибудь генератора случайных чисел. Теоретически, такой генератор может выдать всё что угодно, даже осмысленный текст, который можно сжать обычным архиватором, но надеяться на это не стоило, поскольку Майк Голдмен несомненно проверял файл, перед тем как высылать его мне. По условиям пари было достаточно сэкономить всего один байт, при этом ничего не говорилось о сохранении имени исходного файла. Можно было использовать имя файла для сохранения в нём нескольких байт информации, соответственно уменьшив на них общий размер файла. Однако, большинство сочло бы это нечестным трюком.
Другой вариант - вводить недостающие байты из командной строки при запуске декомпрессора. Естественно, в этом случае я должен был сообщить Майку, что он должен набрать эти недостающие байты вручную. Фактически, это означало бы сохранение информации в человеческой памяти. Кстати, таким способом можно любой файл уменьшить до нуля, а затем восстановить, набирая байт за байтом на клавиатуре. Однако, это трудно назвать компрессией.
К счастью для меня, Майк разрешил использовать несколько сжатых файлов, и этот нюанс позволил легко выполнить условия пари безо всяких, по моему мнению, нечестных приёмов.
Александр Костинский
Вот что придумал Патрик. Пусть, у нас есть длинный файл случайных данных. Находим в этом файле, допустим букву "А". Теперь на букве "А" мы разрежем файл на две части, а саму букву выбросим. У нас получатся два файла, которые в сумме будут на один байт меньше исходного. Что бы восстановить оригинал, нужно просто склеить две его части, вставив между ними букву "А".
Естественно, исходный файл можно разрезать не на две части, а на три и больше, поскольку выбранная нами буква "А" встречается в нём много раз. Если мы имеем дело со случайными данными, то любой символ будет встречаться примерно каждые 255 символов. Таким образом, разрезая один длинный файл в тех местах, где у него находится буква "А" и выбрасывая её, мы превращаем один большой файл в цепочку маленьких, сберегая при этом четыре байта на каждом килобайте. Остаётся только написать простейшую программу, которая могла бы склеивать из множества нарезанных файлов один большой, первоначальный.
У Патрика эта программа, которую можно назвать декомпрессором, оказалась размером всего в 156 байт. Исходный файл в 3 мегабайта, можно было разделить приблизительно на 3 тысячи фрагментов, но Патрик решил остановиться после второй сотни, поскольку алгоритм был ясен, а результат очевиден.
В среду 4 апреля, профессионал Майк Голдмен получил от находчивого Патрика Крейга письмо, где говорилось, что исходный файл был разделён на 218 частей, суммарная их длина стала на 217 байт короче исходного файла. Программа-декомпрессор имеет размер 156 байт, кое-что ушло на сохранение имени файла. В результате, общий размер уменьшился на 44 байта. Условия, поставленные Майком Голдманом выполнены, следовательно, пора платить обещанные пять тысяч долларов.
Между тем, Майк Голдмен не заплатил обещанные пять тысяч и объяснил свои действия так:
Майк Голдмен
Разрезая файл на две части и отбрасывая один байт в месте разреза, Патрик действительно уменьшал содержимое файлов на один байт. Но, кроме основного содержания, у каждого файла есть еще имя, дата создания, координаты расположения на физическом диске и так далее. В результате два файла, длина которых на один байт меньше третьего, на реальном диске занимают больше места, хотя их видимый размер действительно кажется нам меньше.
Александр Костинский
На это Патрик Крейг заметил:
Патрик Крейг
Если операционная система для одного длинного файла требует меньше места, чем для двух коротких, то это её проблемы, а не мои.
Александр Костинский
Формально он прав и, если понимать условия пари буквально, Голдмен должен признать проигрыш, а не уточнять правила по ходу дела. Кое-кто в дискуссионной группе призывал его "быть мужчиной и заплатить деньги". Однако, Майк ограничился тем, что вернул Патрику 100 долларов залога, сказав, что проделанный трюк никак нельзя назвать компрессий информации, и он сожалеет, что условия пари были сформулированы недостаточно ясно.
К чести Патрика Крейга, он не настаивал на награде и признался позже, что вовсе не рассчитывал заработать пять тысяч долларов. Его главной целью было "обхитрить хитреца" - показать, что у самоуверенного Голдмена можно выиграть, причём на его условиях, если рассматривать проблему, как головоломку, используя нечеткую постановку задачи.
Эта история оказалось полезной для всех её участников. Патрик Крейг показал незаурядную находчивость. Майк Голдмен понял, как надо изменить условия пари, чт бы в следующий раз не проиграть его. А наблюдавшие за этой историей еще раз убедились, что чудо компрессора быть не может, так как основы теории информации и теории вероятностей стоят на очень и очень прочном фундаменте.
Все ссылки в тексте программ ведут на страницы лиц и организаций, не связанных с радио "Свобода"; редакция не несет ответственности за содержание этих страниц.
В данной статье мы узнаем, что такое сжатие файлов, для чего оно используется и как позволяет оптимизировать деятельность. Посмотрим, какие факторы влияют на сжатие файлов и какую формулу можно использовать для определения его степени. Рассмотрим, какие можно применять программы для создания архивов.От чего зависит сжатие файла?
От чего зависит сжатие файла? Это одно из самых простых действий, которое может сделать пользователь, для того чтобы уменьшить размер файла, что такое сжатие изображения и как настроить, мы уже знаем. Сжатие используется для:
- экономии пространства на носителях;
- при отправке почты;
- при использовании файлов, где есть лимитирование объемов информации.
В целом, сжатие данных это алгоритм, который позволяет избавиться от избытка исходных данных, которые содержаться в исходном файле. Есть такое понятие, как сжатый атрибут. Это один из методов сжатия файла. Такое сжатие помогает сохранить место в хранилище.
Для осуществления данного способа есть несколько способов. В персональных компьютерах есть автоматическая опция для показа сжатых файлов. При его использовании данные исходного файла не утрачиваются, и он воспроизводится как обычный файл.
Распаковка файла осуществляется за счет возможностей Windows. Но при закрытии файл сжимается снова. Это значительная экономия памяти. Лучше сжимать файлы, которые практически не используются.
Размер памяти современных ПК позволяет хранить большой объем информации, поэтому нет необходимости в компрессии, об этом подробнее можно на курсах SEO с нуля можно узнать.
Файлы, которыми нужно пользоваться часто лучше не сжимать, т.к. распаковка потребует дополнительной вычислительной мощности. Использовать сжатие можно с помощью проводника и командной строки.
От чего зависит степень сжатия файлов?
От чего зависит степень сжатия файлов? Зависит данный показатель от множества факторов. Например, программы, которая используется для уменьшения, метод, тип исходника. Самая большая степень сжатия у фотографий, текстовых файлов. Самая меньшая степень сжатия – у загрузочных модулей и программ. Архивы практически не поддаются сжатию.
Степень сжатия – это основной параметр архивации. Есть специальная формула, которая характеризует степень сжатия. Есть специальные программы, которые помогают создавать архивы. Такие программы позволяют избавиться от лишней информации исходника:
- упрощение кодов;
- исключение постоянных битов;
- исключение повторяющихся символов.
Сжать можно сразу несколько файлов одновременно. Архив – это файл, который может содержать большое количество файлов. Вся информация, которая касается файлов тоже храниться в архиве. Для формирования архивов можно обратиться за помощью к специалистам IT и продвижения SEO, они всегда смогут помочь.
Для чего используется сжатие файлов?
Для чего используется сжатие файлов? К архивации прибегают в нескольких случаях. Например, для сохранения свободного места в хранилище устройства.
Меньший объем файлов позволяет не только их проще хранить, но и без труда переносить с устройства на устройство. При ведении контекстной рекламы Яндекс тоже можно использовать сжатые файлы, например, изображения.
Время копирования заархивированных файлов кратно меньше. К тому же, такие файлы больше защищены, как от взлома, так и от компьютерных вирусов. Коэффициент сжатия можно вычислить по формуле.
Где объем сжатого файла делится на объем исходника, затем умножается на 100%. В итоге получается степень сжатия. Заархивированные файлы можно как упаковать, так и распаковать. Если файлы даже в архиве очень большие, то хранить их можно на нескольких дисках, которые называют томами.
За счет чего происходит сжатие файлов?
За счет чего происходит сжатие файлов? Посмотрим, какие программы помогают уменьшать объем исходников. Есть не менее десятка специализированных программ. У каждой есть свой набор специальных функций. Производители подобных программ есть как за рубежом, так и в России.
Чаще всего упаковка и распаковка фалов проводится одной программой, но бывает и так, что для каждой операции своя. Есть файлы, которые обладают свойством самораспаковывания. Суть в том, что исполняемый модуль способен к саморазархивации.
Чаще всего при распаковке файлов программы сохраняют его на жесткий диск. Но есть и программы, которые создают упакованный исполняемый модуль. При этом в программном файле сохраняется имя и расширение, он загружается на жесткий диск, распаковывается и после этого начинает работать. После работы можно вернуть его обратно в архив.
Программы архиваторы помогают архивировать файлы, просматривать их, создавать архивы из большого количества томов. Архивные файлы можно протестировать, они позволяют вводить комментарии. В архиве можно хранить несколько версий исходника.
Что даёт сжатие файлов?
Что дает сжатие файлов? Сейчас люди обмениваются большим количеством информации. Информация обновляется постоянно. Старая информация заменяет новую, большинство данных приходится сохранять. Для того чтобы она не занимала много места на устройствах хранения лучше запаковывать файлы в архив. Есть специальные облачные хостинги что это такое, мы уже знаем.
При сжатии нужно руководствоваться тем, что файл сохранит свои исходные показатели по качеству, информативности, цветопередаче и т.д. Сжатие используется, например, при загрузке файлов в социальных сетях, где есть лимит по тяжести загруженных файлов.
Сжатые файлы используются в деловых переписках, особенно если у получателя на корпоративном сервере есть лимит по объему полученной информации в одном письме. Архивирование используется для сохранения памяти на устройствах.
Работая за компьютером, нам постоянно приходится иметь дело с файловыми архивами, – это файл, как правило с расширением .rar, .zip, .7z или др., включающий в себе один или несколько других файлов, и дополнительно содержащий метаданные.
Пожалуй, главным преимуществом архивации (это процесс ещё носит и такие названия как: компрессия, упаковка или сжатие данных, сжимающее кодирование) является возможность упаковки сразу нескольких объектов (файлов, папок) в один контейнер – архив.
Архивы можно использовать, например, для передачи данных по электронной почте, что очень удобно, так как к электронному письму во вложении можно прикрепить набор фотографий, документов и других объектов, используя всего один файл. Архивы также используются и для хранения информации, ну и конечно для сжатия данных, хотя для цифровых фотографий или видеофайлов процент сжатия не так велик, а вот, к примеру, для документов Microsoft Word или файлов Adobe Photoshop компрессия куда более существенна (несколько десятков МБ могут быть сжаты всего до нескольких мегабайт). Если тех или иных файлов достаточно много, то для экономии места на жёстком диске вполне было бы уместно добавить их в архив, если, конечно, они вам не понадобятся в самое ближайшее время, да и в любом случае, при необходимости, у вас не составит особого труда извлечь файлы из архива, используя для этого одну из популярных программ-архиваторов, например, WinRAR или WinZip. Обратите внимание, что, например, ВинРар является условно-бесплатным программным продуктом, т.е. бесплатно скачать и использовать WinRAR вы можете всего 40 дней с момента установки на компьютер, после истечения этого срока архиватор необходимо удалить или купить лицензию.
Как альтернативный вариант, вы можете использовать один из бесплатных архиваторов для Windows (32 и 64-бит), такой как 7-Zip.
В случае же, если вам потребуется скрыть файлы на своём компьютере, то и тут архивация файлов, но уже с установкой пароля на архив, придётся как нельзя кстати. Подавляющее большинство программ-архиваторов, включая вышеназванные, обладают такой возможностью. К выбору пароля в таком случае лучше подойти как можно более серьёзно, – он не должен быть слишком простым, но в тоже время его ни в коем случае нельзя забывать, т.к. никаких дополнительных средств восстановления в программах, как правило, не предусмотрено.
Доброго времени суток.
Сегодня я хочу коснуться темы сжатия данных без потерь. Несмотря на то, что на хабре уже были статьи, посвященные некоторым алгоритмам, мне захотелось рассказать об этом чуть более подробно.
Я постараюсь давать как математическое описание, так и описание в обычном виде, для того, чтобы каждый мог найти для себя что-то интересное.
В этой статье я коснусь фундаментальных моментов сжатия и основных типов алгоритмов.
Сжатие. Нужно ли оно в наше время?
Разумеется, да. Конечно, все мы понимаем, что сейчас нам доступны и носители информации большого объема, и высокоскоростные каналы передачи данных. Однако, одновременно с этим растут и объемы передаваемой информации. Если несколько лет назад мы смотрели 700-мегабайтные фильмы, умещающиеся на одну болванку, то сегодня фильмы в HD-качестве могут занимать десятки гигабайт.
Конечно, пользы от сжатия всего и вся не так много. Но все же существуют ситуации, в которых сжатие крайне полезно, если не необходимо.
- Пересылка документов по электронной почте (особенно больших объемов документов с использованием мобильных устройств)
- При публикации документов на сайтах, потребность в экономии трафика
- Экономия дискового пространства в тех случаях, когда замена или добавление средств хранения затруднительно. Например, подобное бывает в тех случаях, когда выбить бюджет под капитальные расходы непросто, а дискового пространства не хватает
Конечно, можно придумать еще множество различных ситуаций, в которых сжатие окажется полезным, но нам достаточно и этих нескольких примеров.
Все методы сжатия можно разделить на две большие группы: сжатие с потерями и сжатие без потерь. Сжатие без потерь применяется в тех случаях, когда информацию нужно восстановить с точностью до бита. Такой подход является единственно возможным при сжатии, например, текстовых данных.
В некоторых случаях, однако, не требуется точного восстановления информации и допускается использовать алгоритмы, реализующие сжатие с потерями, которое, в отличие от сжатия без потерь, обычно проще реализуется и обеспечивает более высокую степень архивации.
| Сжатие с потерями |
| Лучшие степени сжатия, при сохранении «достаточно хорошего» качества данных. Применяются в основном для сжатия аналоговых данных — звука, изображений. В таких случаях распакованный файл может очень сильно отличаться от оригинала на уровне сравнения «бит в бит», но практически неотличим для человеческого уха или глаза в большинстве практических применений. |
| Сжатие без потерь |
| Данные восстанавливаются с точностью до бита, что не приводит к каким-либо потерям информации. Однако, сжатие без потерь показывает обычно худшие степени сжатия. |
Итак, перейдем к рассмотрению алгоритмов сжатия без потерь.
Универсальные методы сжатия без потерь
В общем случае можно выделить три базовых варианта, на которых строятся алгоритмы сжатия.
Первая группа методов – преобразование потока. Это предполагает описание новых поступающих несжатых данных через уже обработанные. При этом не вычисляется никаких вероятностей, кодирование символов осуществляется только на основе тех данных, которые уже были обработаны, как например в LZ – методах (названных по имени Абрахама Лемпеля и Якоба Зива). В этом случае, второе и дальнейшие вхождения некой подстроки, уже известной кодировщику, заменяются ссылками на ее первое вхождение.
Вторая группа методов – это статистические методы сжатия. В свою очередь, эти методы делятся на адаптивные (или поточные), и блочные.
В первом (адаптивном) варианте, вычисление вероятностей для новых данных происходит по данным, уже обработанным при кодировании. К этим методам относятся адаптивные варианты алгоритмов Хаффмана и Шеннона-Фано.
Во втором (блочном) случае, статистика каждого блока данных высчитывается отдельно, и добавляется к самому сжатому блоку. Сюда можно отнести статические варианты методов Хаффмана, Шеннона-Фано, и арифметического кодирования.
Общие принципы, на которых основано сжатие данных
Все методы сжатия данных основаны на простом логическом принципе. Если представить, что наиболее часто встречающиеся элементы закодированы более короткими кодами, а реже встречающиеся – более длинными, то для хранения всех данных потребуется меньше места, чем если бы все элементы представлялись кодами одинаковой длины.
Точная взаимосвязь между частотами появления элементов, и оптимальными длинами кодов описана в так называемой теореме Шеннона о источнике шифрования(Shannon's source coding theorem), которая определяет предел максимального сжатия без потерь и энтропию Шеннона.
Немного математики
Если вероятность появления элемента si равна p(si), то наиболее выгодно будет представить этот элемент — log2p(si) битами. Если при кодировании удается добиться того, что длина всех элементов будет приведена к log2p(si) битам, то и длина всей кодируемой последовательности будет минимальной для всех возможных методов кодирования. При этом, если распределение вероятностей всех элементов F =
Это значение называют энтропией распределения вероятностей F, или энтропией источника в заданный момент времени.
Однако обычно вероятность появления элемента не может быть независимой, напротив, она находится в зависимости от каких-то факторов. В этом случае, для каждого нового кодируемого элемента si распределение вероятностей F примет некоторое значение Fk, то есть для каждого элемента F= Fk и H= Hk.
Иными словами, можно сказать, что источник находится в состоянии k, которому соответствует некий набор вероятностей pk(si) для всех элементов si.
Поэтому, учитывая эту поправку, можно выразить среднюю длину кодов как
Где Pk — вероятность нахождения источника в состоянии k.
Итак, на данном этапе мы знаем, что сжатие основано на замене часто встречающихся элементов короткими кодами, и наоборот, а так же знаем, как определить среднюю длину кодов. Но что же такое код, кодирование, и как оно происходит?
Кодирование без памяти
Коды без памяти являются простейшими кодами, на основе которых может быть осуществлено сжатие данных. В коде без памяти каждый символ в кодируемом векторе данных заменяется кодовым словом из префиксного множества двоичных последовательностей или слов.
На мой взгляд, не самое понятное определение. Рассмотрим эту тему чуть более подробно.
Пусть задан некоторый алфавит , состоящий из некоторого (конечного) числа букв. Назовем каждую конечную последовательность символов из этого алфавита (A=a1, a2,… ,an) словом, а число n — длиной этого слова.
Пусть задан также другой алфавит. Аналогично, обозначим слово в этом алфавите как B.
Введем еще два обозначения для множества всех непустых слов в алфавите. Пусть — количество непустых слов в первом алфавите, а — во втором.
Пусть также задано отображение F, которое ставит в соответствие каждому слову A из первого алфавита некоторое слово B=F(A) из второго. Тогда слово B будет называться кодом слова A, а переход от исходного слова к его коду будет называться кодированием.
Поскольку слово может состоять и из одной буквы, то мы можем выявить соответствие букв первого алфавита и соответствующих им слов из второго:
a1 <-> B1
a2 <-> B2
…
an <-> Bn
Это соответствие называют схемой, и обозначают ∑.
В этом случае слова B1, B2,…, Bn называют элементарными кодами, а вид кодирования с их помощью — алфавитным кодированием. Конечно, большинство из нас сталкивались с таким видом кодирования, пусть даже и не зная всего того, что я описал выше.
Итак, мы определились с понятиями алфавит, слово, код, и кодирование. Теперь введем понятие префикс.
Пусть слово B имеет вид B=B'B''. Тогда B' называют началом, или префиксом слова B, а B'' — его концом. Это довольно простое определение, но нужно отметить, что для любого слова B, и некое пустое слово ʌ («пробел»), и само слово B, могут считаться и началами и концами.
Итак, мы подошли вплотную к пониманию определения кодов без памяти. Последнее определение, которое нам осталось понять — это префиксное множество. Схема ∑ обладает свойством префикса, если для любых 1≤i, j≤r, i≠j, слово Bi не является префиксом слова Bj.
Проще говоря, префиксное множество – это такое конечное множество, в котором ни один элемент не является префиксом (или началом) любого другого элемента. Простым примером такого множества является, например, обычный алфавит.
Одним из канонических алгоритмов, которые иллюстрируют данный метод, является алгоритм Хаффмана.
Алгоритм Хаффмана
Алгоритм Хаффмана использует частоту появления одинаковых байт во входном блоке данных, и ставит в соответствие часто встречающимся блокам цепочки бит меньшей длины, и наоборот. Этот код является минимально – избыточным кодом. Рассмотрим случай, когда, не зависимо от входного потока, алфавит выходного потока состоит из всего 2 символов – нуля и единицы.
Для лучшей иллюстрации, рассмотрим небольшой пример.
Пусть у нас есть алфавит, состоящий из всего четырех символов — < a1, a2, a3, a4>. Предположим также, что вероятности появления этих символов равны соответственно p1=0.5; p2=0.24; p3=0.15; p4=0.11 (сумма всех вероятностей, очевидно, равна единице).
Итак, построим схему для данного алфавита.
- Объединяем два символа с наименьшими вероятностями (0.11 и 0.15) в псевдосимвол p'.
- Удаляем объединенные символы, и вставляем получившийся псевдосимвол в алфавит.
- Объединяем два символа с наименьшей вероятностью (0.24 и 0.26) в псевдосимвол p''.
- Удаляем объединенные символы, и вставляем получившийся псевдосимвол в алфавит.
- Наконец, объединяем оставшиеся два символа, и получаем вершину дерева.
Если сделать иллюстрацию этого процесса, получится примерно следующее:
Как вы видите, при каждом объединении мы присваиваем объединяемым символам коды 0 и 1.
Таким образом, когда дерево построено, мы можем легко получить код для каждого символа. В нашем случае коды будут выглядить так:
Поскольку ни один из данных кодов не является префиксом какого-нибудь другого (то есть, мы получили пресловутое префиксное множество), мы можем однозначно определить каждый код в выходном потоке.
Итак, мы добились того, что самый частый символ кодируется самым коротким кодом, и наоборот.
Если предположить, что изначально для хранения каждого символа использовался один байт, то можно посчитать, насколько нам удалось уменьшить данные.
Пусть на входу у нас была строка из 1000 символов, в которой символ a1 встречался 500 раз, a2 — 240, a3 — 150, и a4 — 110 раз.
Изначально данная строка занимала 8000 бит. После кодирования мы получим строку длинной в ∑pili = 500 * 1 + 240 * 2 + 150 * 3 + 110 * 3 = 1760 бит. Итак, нам удалось сжать данные в 4,54 раза, потратив в среднем 1,76 бита на кодирование каждого символа потока.
Напомню, что согласно Шеннону, средняя длина кодов составляет . Подставив в это уравнение наши значения вероятностей, мы получим среднюю длину кодов равную 1.75496602732291, что весьма и весьма близко к полученному нами результату.
Тем не менее, следует учитывать, что помимо самих данных нам необходимо хранить таблицу кодировки, что слегка увеличит итоговый размер закодированных данных. Очевидно, что в разных случаях могут с использоваться разные вариации алгоритма – к примеру, иногда эффективнее использовать заранее заданную таблицу вероятностей, а иногда – необходимо составить ее динамически, путем прохода по сжимаемым данным.
Заключение
Итак, в этой статье я постарался рассказать об общих принципах, по которым происходит сжатие без потерь, а также рассмотрел один из канонических алгоритмов — кодирование по Хаффману.
Если статья придется по вкусу хабросообществу, то я с удовольствием напишу продолжение, так как есть еще множество интересных вещей, касающихся сжатия без потерь; это как классические алгоритмы, так и предварительные преобразования данных (например, преобразование Барроуза-Уилира), ну и, конечно, специфические алгоритмы для сжатия звука, видео и изображений (самая, на мой взгляд, интересная тема).
Читайте также: