Сжатие информации

Размещено на http://www.allbest.ru/

Государственное бюджетное образовательное

образовательное учреждение среднего профессионального образования

«Санкт-Петербургский технический колледж управления и коммерции»

КУРСОВОЙ ПРОЕКТ

По дисциплине: Архитектура ЭВМ

Тема: «Сжатие информации»

Специальность: Техническое обслуживание средств вычислительной техники и компьютерных сетей

САНКТ-ПЕТЕРБУРГ

2013 г.



Назначение компьютера

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

Из истории науки и техники известно, что идеи многих своих изобретений человек "подглядел" в природе.

Например, еще в XV веке великий итальянский ученый и художник Леонардо да Винчи изучал строение тел птиц и использовал эти знания для конструирования летательных аппаратов.

Русский ученый Н. Е. Жуковский, основоположник аэродинамики, также исследовал механизм полета птиц. Результаты этих исследований используются при расчетах конструкций самолетов.

Можно сказать, что Леонардо да Винчи и Жуковский "списывали" свои летающие машины с птиц.

А есть ли в природе прототип у компьютера? Да! Таким прототипом является сам человек. Только изобретатели стремились передать компьютеру не физические, а интеллектуальные возможности человека.

По своему назначению компьютер - универсальное техническое средство для работы человека с информацией.

По принципам устройства компьютер - это модель человека, работающего с информацией.

Какие устройства входят в состав компьютера. Имеются четыре основные составляющие информационной функции человека:

прием (ввод) информации;

запоминание информации (сохранение в памяти);

процесс мышления (обработка информации); 

передача (вывод) информации.

Компьютер включает в себя устройства, выполняющие эти функции мыслящего человека:

устройства ввода; 

устройства запоминания - память;

устройство обработки - процессор;

устройства вывода.

В ходе работы компьютера информация через устройства ввода попадает в память; процессор извлекает из памяти обрабатываемую информацию, работает с ней и помещает в нее результаты обработки; полученные результаты через устройства вывода сообщаются человеку. Чаще всего в качестве устройства ввода используется клавиатура, а устройства вывода - экран дисплея или принтер (устройство печати).

Персональные компьютеры.

Что же понимается под понятием в современном понимании персональный компьютер? Ответить на этот вопрос можно, если четко сформулировать, все его основные признаки. 

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

Можно выделить пять формальных признаков, которые помогут нам определить, является ли данный компьютер персональным или нет.

1. Способ управления простой, наглядный, удобный, не требующий глубоких знаний в области вычислительной техники. Все технические средства (дисплей, клавиатура, манипулятор, печатающее устройство и т.д.), обеспечивающие взаимодействие человека и ЭВМ, сделаны так, чтобы на них безбоязненно мог работать даже ребенок. Общение человека и компьютера организованно в диалоговом режиме.

2. Разработано большое количество программных средств для различных областей применения. Это избавит пользователя от необходимости самому составлять программу на языке компьютера.

3. Малогабаритные устройства внешней памяти большой емкости допускают замену одного накопителя другим. К таким устройствам можно отнести: накопители на гибких магнитных дисках и винчестерских дисках, кассетные магнитофон.

4. Благодаря малым габариту и массе, сравнимым с телевизором, для установки не требуется специальных приспособлений, достаточно место на рабочем столе.

5. Конструкция персонального компьютера, его внешнее оформление привлекательны по цвету и форме, удовлетворяют эргономическим показателям. Впервые за время развития вычислительной техники этот признак включен в качестве основного при определении целого класса ЭВМ.

Применение ПК в жизни человека.

Компьютер - тоже дело рук и мозга человека. Процесс взаимодействия человека с ЭВМ насчитывает уже более 40лет. До недавнего времени в этом процессе могли участвовать только специалисты -инженеры, математики - программисты, операторы. В последние годы произошли кардинальные изменения в области вычислительной техники. Благодаря разработке и внедрению микропроцессоров в структуру ЭВМ появились малогабаритные, удобные для пользователя персональные компьютеры. Ситуация изменилась, в роли пользователя может быть не только специалист по вычислительной технике, но и любой человек, будь то школьник или домохозяйка, врач или учитель, рабочий или инженер. 

Бытовые персональные компьютеры используют в домашних условиях. Их основное назначение: обеспечение несложных расчетов, выполнение функции записной книжки, ведение личной картотеки, средство обучения различным дисциплинам, инструмент доступа по телефонным каналам к общественным информационным фондам и т.д. 

Широкое распространение получил он как средство развлечения - организатор и партнер в различных играх. Профессиональные персональные ЭВМ используют в конкретной профессиональной сфере, все программные и технические средства ориентированы на конкретную профессию. 

Однако независимо от профессиональной направленности ЭВМ их основное назначение-выполнение рутинной работы: они осуществляют поиск информации в различных справочно-нормативной документации и архивах, составляют типовые формы документации, ведут дневник или лабораторный журнал, фиксируют результаты исследований, запоминают и выдают по запросу пользователя информацию по данной профессиональной деятельности и т.д.

Компьютеры как средство общения людей

Если на одном компьютере работают хотя бы два человека, у них уже возникает желание использовать этот компьютер для обмена информацией друг с другом. На больших машинах, которыми пользуются одновременно десятки, а то и сотни человек, для этого предусмотрены специальные программы, позволяющие пользователям передавать сообщения друг другу, а администратору - оповещать пользователей о новостях в системе. Как только появилась возможность объединять несколько машин в сеть, пользователи ухватились за эту возможность, чтобы расширить круг своего общения. Создаются программы, предназначенные для обмена сообщениями пользователей, находящихся на разных машинах. Из-за разнообразия компьютеров, операционных систем, способов соединения машин в сеть и целей, преследуемых при этом людьми, этих программ оказалось достаточно много и они не всегда совместимы между собой.

Наиболее универсальное средство компьютерного общения - это электронная почта. Она позволяет пересылать сообщения практически с любой машины на любую, так как большинство известных машин, работающих в разных системах, ее поддерживают. Электронная почта во многом похожа на обычную почту. С ее помощью письмо - текст, снабженный стандартным заголовком (конвертом) - доставляется по указанному адресу, который определяет местонахождение машины и имя адресата, и помещается в файл, называемый почтовым ящиком адресата, с тем, чтобы адресат мог его достать и прочесть в удобное время. При этом между почтовыми программами на разных машинах существует соглашение о том, как писать адрес, чтобы все его понимали. Электронная почта оказалась во многом удобнее обычной, "бумажной" Надежность электронной почты сильно зависит от того, какие используются почтовые программы, насколько удалены друг от друга отправитель и адресат письма, и особенно от того, в одной они сети, или в разных. Если письмо потерялось, то об этом можно узнать достаточно скоро и послать новое. Обычно программы, предназначенные для пересылки писем от одного человека другому поддерживают и такую возможность, как почтовые списки. Если группа людей, объединенных общими интересами, хочет поддерживать дискуссию на какую-нибудь тему длительное время, они создают такой список, выделяют для него какое-либо имя, после чего все сообщения, посланные на это имя, рассылаются всем участникам группы. Предполагается, что у такой группы должен быть администратор, к которому можно обратиться, если Вы хотите, чтобы Вас включили в группу, исключили из нее, или если у Вас изменился адрес. Если группа становится очень большой, администратору прибавляется работы. Кроме того, большим группам неудобно пользоваться почтовыми списками потому что: - каждый из участников группы должен хранить у себя весь список - сообщения посылаются каждому из участников группы отдельно ;если четыре участника группы находятся в одной локальной сети, каждому все равно присылается отдельная копия каждого сообщения; если десять участников группы находятся на одной большой машине - на эту машину приходит по десять копий каждого сообщения, по одной на каждого члена группы. При больших масштабах это очень непрактично; - если Вы хотите ссылаться в ходе дискуссии на полученные ранее сообщения, Вам приходится хранить весь архив у себя, а он может занимать очень много места; - поскольку почтовые списки распространяются и принимаются теми же программами, что и обычная почта, если Вы участвуете в нескольких почтовых списках, сообщения от разных групп приходят вперемежку, и Вам приходится самому отделять сообщения одной группы от другой и от отдельных писем. Чтобы избежать этих неудобств, при общении очень больших групп людей используется система, независимая от электронной почты - компьютерная конференция. Самая большая компьютерная конференция - USENET - объединяет сотни тысяч машин по всему миру. Ее устройство напоминает доску объявлений, и, с другой стороны, газету. Никакого списка участников конференции не существует. Получать и отправлять сообщения может любой, чья машина связана с какой-нибудь другой машиной, которая получает сообщения конференции. Все рассылаемые сообщения разделены на группы по темам, и для того, чтобы получать сообщения группы, надо на эту группу подписаться, то есть включить имя этой группы в список на своей машине. Сетевое программное обеспечение, обслуживающее конференцию USENET, из всех предлагаемых сообщений выбирает сообщения, относящиеся к группам из Вашего списка. Посылая сообщение, Вы помечаете, к какой группе оно относится, и все, кто подписан на эту группу, Ваше сообщение получат. Такое устройство конференции позволяет Вам получать все сообщения по интересующим Вас темам, независимо от того, кто их написал, и рассылать сообщение, не беспокоясь об адресах получателей - его прочтут те, кого оно может заинтересовать. Компьютерная конференция может быть полезна тем, кто хочет узнать о новых товарах, книгах или фильмах, через нее очень удобно распространять информацию о замеченных ошибках в программах и о способах их исправить, она просто незаменима для любителей поболтать на любимую тему со своими единомышленниками во всех уголках Земли, и, конечно же, для научных дискуссий. При помощи конференции можно обсуждать интересующую тему в такой компании, собрать которую в одном месте для личной беседы стоило непредсказуемых затрат времени и сил. В списках групп можно найти группы для специалистов по древнегреческой культуре и для любителей рок-музыки, и для обмена кулинарными рецептами. Программы, обслуживающие конференцию, достаточно умны для того, чтобы присылать по одной копии сообщения на машину, независимо от того, сколько пользователей на этой машине будут его читать; они также предоставляют возможность обращаться к старым сообщениям.

Представление звуковой информации.

Приёмы и методы работы со звуковой информацией пришли в вычислительную технику наиболее поздно. К тому же, в отличие от числовых, текстовых и графических данных, у звукозаписей не было столь же длительной и проверенной истории кодирования. В итоге методы кодирования звуковой информации двоичным кодом далеки от стандартизации. Множество отдельных компаний разработали свои корпоративные стандарты, но среди них можно выделить два основных направления. 

Метод FM (Frequency Modulation) основан та том, что теоретически любой сложный звук можно разложить на последовательность простейших гармонических сигналов разных частот, каждый из которых представляет собой правильную синусоиду, а, следовательно, может быть описан числовыми параметрами, т.е. кодом. В природе звуковые сигналы имеют непрерывный спектр, т.е. являются аналоговыми. Их разложение в гармонические ряды и представление в виде дискретных цифровых сигналов выполняют специальный устройства - аналогово-цифровые преобразователи (АЦП). Обратное преобразование для воспроизведения звука, закодированного числовым кодом, выполняют цифро-аналоговые преобразователи (ЦАП). При таких преобразованиях неизбежны потери информации, связанные с методом кодирования, поэтому качество звукозаписи обычно получается не вполне удовлетворительным и соответствует качеству звучания простейших электромузыкальных инструментов с окрасом характерным для электронной музыки. В то же время данный метод копирования обеспечивает весьма компактный код, поэтому он нашёл применение ещё в те годы, когда ресурсы средств вычислительной техники были явно недостаточны.

Метод таблично волнового (Wave-Table) синтеза лучше соответствует современному уровню развития техники. В заранее подготовленных таблицах хранятся образцы звуков для множества различных музыкальных инструментах. В технике такие образцы называют сэмплами. Числовые коды выражают тип инструмента, номер его модели, высоту тона, продолжительность и интенсивность звука, динамику его изменения, некоторые параметры среды, в которой происходит звучание, а также прочие параметры, характеризующие особенности звучания. Поскольку в качестве образцов исполняются реальные звуки, то его качество получается очень высоким и приближается к качеству звучания реальных музыкальных инструментов.

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

цифровая запись, когда реальные звуковые волны преобразуются в цифровую информацию путем измерения звука тысячи раз в секунду;

MIDI-запись, которая, вообще говоря, является не реальным звуком, а записью определенных команд-указаний (какие клавиши надо нажимать, например, на синтезаторе). MIDI-запись является электронным эквивалентом записи игры на фортепиано.

Для того чтобы воспользоваться первым указанным способом в компьютере должна быть звуковая карта (плата). 

Реальные звуковые волны имеют весьма сложную форму и для получения их высококачественного цифрового представления требуется высокая частота квантования.

Звуковая плата преобразует звук в цифровую информацию путем измерения характеристики звука (уровень сигнала) несколько тысяч раз в секунду. То есть аналоговый (непрерывный) сигнал измеряется в тысячах точек, и получившиеся значения записываются в виде 0 и 1 в память компьютера. При воспроизведении звука специальное устройство на звуковой карте преобразует цифры в аналог звуковой волны. Хранение звука в виде цифровой записи занимает достаточно много места в памяти компьютера.

Число разрядов, используемое для создания цифрового звука, определяет качество звучания.

MIDI-запись была разработана в начале 80-х годов (MIDI - Musical Instrument Digital Interfase - интерфейс цифровых музыкальных инструментов). MIDI-информация представляет собой команды, а не звуковую волну. Эти команды - инструкции синтезатору. МIDI-команды гораздо удобнее для хранения музыкальной информации, чем цифровая запись. Однако для записи MIDI-команд вам потребуется устройство, имитирующее клавишный синтезатор, которое воспринимает МIDI-команды и при их получении может генерировать соответствующие звуки.

Таким образом, рассмотрев принципы хранения в ЭВМ различных видов информации, можно сделать важный вывод о том, что все они так или иначе преобразуются в числовую форму и кодируются набором нулей и единиц. Благодаря такой универсальности представления данных, если из памяти наудачу извлечь содержимое какой-нибудь ячейки, то принципиально невозможно определить, какая именно информация там закодирована: текст, число или картинка. 

Представление текстовых данных.

Любой текст состоит из последовательности символов. Символами могут быть буквы, цифры, знаки препинания, знаки математических действий, круглые и квадратные скобки и т.д. Особо обратим внимание на символ "пробел", который используется для разделения слов и предложений между собой. Хотя на бумаге или экране дисплея "пробел" - это пустое, свободное место, этот символ ничем не "хуже" любого другого символа. На клавиатуре компьютера или пишущей машинки символу "пробел" соответствует специальная клавиша.

Текстовая информация, как и любая другая, хранится в памяти компьютера в двоичном виде. Для этого каждому символу ставится в соответствие некоторое неотрицательное число, называемое кодом символа, и это число записывается в память ЭВМ в двоичном виде. Конкретное соответствие между символами и их кодами называется системой кодировки.

В современных ЭВМ, в зависимости от типа операционной системы и конкретных прикладных программ, используются 8-разрядные и 16-разрядные (Windows 95, 98, NT) коды символов. Использование 8-разрядных кодов позволяет закодировать 256 различных знаков, этого вполне достаточно для представления многих символов, используемых на практике. При такой кодировке для кода символа достаточно выделить в памяти один байт. Так и делают: каждый символ представляют своим кодом, который записывают в один байт памяти.

В персональных компьютерах обычно используется система кодировки ASCII (American Standard Code for Information Interchange - американский стандартный код для обмена информации). Он введен в 1963 г. и ставит в соответствие каждому символу семиразрядный двоичный код. Легко определить, что в коде ASCII можно представить 128 символов.

В системе ASCII закреплены две таблицы кодирования базовая и расширенная. Базовая таблица закрепляет значения кодов от 0 до 127, а расширенная относится к символам с номерами от 128 до 255. 

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

Кодировка символов русского языка, известная как кодировка Windows-1251, была введена "извне" - компанией Microsoft, но, учитывая широкое распространение операционных систем и других продуктов этой компании в России, она глубоко закрепилась и нашла широкое распространение. 

Другая распространённая кодировка носит название КОИ-8 (код обмена информацией, восьмизначный) - её происхождение относится к временам действия Совета Экономической Взаимопомощи государств Восточной Европы. Сегодня кодировка КОИ - 8 имеет широкое распространение в компьютерных сетях на территории России и в российском секторе Интернета. 

Международный стандарт, в котором предусмотрена кодировка символов русского языка, носит название ISO (International Standard Organization - Международный институт стандартизации). На практике данная кодировка используется редко. 

Универсальная система кодирования текстовых данных.

Если проанализировать организационные трудности, связанные с созданием единой системы кодирования текстовых данных, то можно прийти к выводу, что они вызваны ограниченным набором кодов (256). В то же время, очевидно, что если, кодировать символы не восьмиразрядными двоичными числами, а числами с большим разрядом то и диапазон возможных значений кодов станет на много больше. Такая система, основанная на 16-разрядном кодировании символов, получила название универсальной - UNICODE. Шестнадцать разрядов позволяют обеспечить уникальные коды для 65 536 различных символов - этого поля вполне достаточно для размещения в одной таблице символов большинства языков планеты. 

Несмотря на тривиальную очевидность такого подхода, простой механический переход на данную систему долгое время сдерживался из-за недостатков ресурсов средств вычислительной техники (в системе кодирования UNICODE все текстовые документы становятся автоматически вдвое длиннее). Во второй половине 90-х годов технические средства достигли необходимого уровня обеспечения ресурсами, и сегодня мы наблюдаем постепенный перевод документов и программных средств на универсальную систему кодирования.

Ниже приведены таблицы кодировки ASCII.



 

Принципы сжатия данных.

В основе любого способа сжатия лежит модель источника данных, или, точнее, модель избыточности. Иными словами, для сжатия данных используются некоторые априорные сведения о том, какого рода данные сжимаются. Не обладая такими сведениями об источнике, невозможно сделать никаких предположений о преобразовании, которое позволило бы уменьшить объём сообщения. Модель избыточности может быть статической, неизменной для всего сжимаемого сообщения, либо строиться или параметризоваться на этапе сжатия (и восстановления). Методы, позволяющие на основе входных данных изменять модель избыточности информации, называются адаптивными. Неадаптивными являются обычно узкоспециализированные алгоритмы, применяемые для работы с данными, обладающими хорошо определёнными и неизменными характеристиками. Подавляющая часть достаточно универсальных алгоритмов являются в той или иной мере адаптивными.

Все методы сжатия данных делятся на два основных класса:

Сжатие без потерь

Сжатие с потерями

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

Допустимость потерь

Основным критерием различия между алгоритмами сжатия является описанное выше наличие или отсутствие потерь. В общем случае алгоритмы сжатия без потерь универсальны в том смысле, что их применение безусловно возможно для данных любого типа, в то время как возможность применения сжатия с потерями должна быть обоснована. Для некоторых типов данных искажения не допустимы в принципе. В их числе

символические данные, изменение которых неминуемо приводит к изменению их семантики: программы и их исходные тексты, двоичные массивы и т. п.;

жизненно важные данные, изменения в которых могут привести к критическим ошибкам: например, получаемые с медицинской измерительной аппаратуры или контрольных приборов летательных, космических аппаратов и т. п.;

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

Системные требования алгоритмов

Различные алгоритмы могут требовать различного количества ресурсов вычислительной системы, на которых они реализованы:

оперативной памяти (под промежуточные данные);

постоянной памяти (под код программы и константы);

процессорного времени.

В целом, эти требования зависят от сложности и «интеллектуальности» алгоритма. Общая тенденция такова: чем эффективнее и универсальнее алгоритм, тем большие требования к вычислительным ресурсам он предъявляет. Тем не менее, в специфических случаях простые и компактные алгоритмы могут работать не хуже сложных и универсальных. Системные требования определяют их потребительские качества: чем менее требователен алгоритм, тем на более простой, а следовательно, компактной, надёжной и дешёвой системе он может быть реализован.

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

Алгоритм сжатия требует больших вычислительных ресурсов, нежели алгоритм восстановления.

Это наиболее распространённое соотношение, характерное для случаев, когда однократно сжатые данные будут использоваться многократно. В качестве примера можно привести цифровые аудио- и видеопроигрыватели.

Алгоритмы сжатия и восстановления требуют приблизительно равных вычислительных ресурсов.

Наиболее приемлемый вариант для линий связи, когда сжатие и восстановление происходит однократно на двух её концах (например, в цифровой телефонии).

Алгоритм сжатия существенно менее требователен, чем алгоритм восстановления.

Такая ситуация характерна для случаев, когда процедура сжатия реализуется простым, часто портативным устройством, для которого объём доступных ресурсов весьма критичен, например, космический аппарат или большая распределённая сеть датчиков. Это могут быть также данные, распаковка которых требуется в очень малом проценте случаев, например запись камер видеонаблюдения.

Алгоритмы сжатия данных неизвестного формата

Имеется два основных подхода к сжатию данных неизвестного формата.

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

Для каждой сжимаемой последовательности символов однократно либо в каждый момент времени собирается статистика её встречаемости в кодируемых данных. На основе этой статистики вычисляется вероятность значения очередного кодируемого символа (либо последовательности символов).

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

Сжатие текстовой информации

Специфичный способ, основанный на том, что в текстовом файле используется только ограниченный набор 8-битовых кодов ASCII. Например, для задания всех букв английского алфавита и знаков препинания может хватить всего 64 символов выходного 6-битного алфавита (как сделано в коде EBCDIC). При этом размер выходного файла составит 75% от входного. Подобный алгоритм применяется при сжатии текстовых файлов в архиваторе ARJ. Если допустить сжатие с потерями, можно сделать следующий шаг и заменить пробелы символами табуляции, заменить пары символов только на , выкинуть пустые строки, представлять текст только заглавными буквами, исключить буквы Й и первую букву в слове “елка” (на моей клавиатуре она уже исключена). Именно с использованием таких приемов работала самая первая известная автору программа-архиватор, исходные коды которой он видел. И она действительно сжимала информацию, хотя в настоящее время перечисленные приемы следует использовать как предварительный проход перед запуском более серьезной программы сжатия.

В качестве разрядки можно предложить интересный метод сжатия информации до 1/3 первоначального объема, предложенный в [7.4]. Он заключается в том, что из исходного текста выкидываются каждая вторая и третья из трех последовательных букв. Например, после сжатия сообщения ”Даже Эдди нас опередил с детским хором” мы получим строку вида “Дед спел тихо”. Как видно, фраза после такой “обработки” не утратила некоторого смысла.

Сжатие изображений и видеофильмов

Сжатие - процесс, напоминающий укладку чемодана. Если путем изменения местоположения и взаимного расположения носителей информации удается сократить ее объем, то мы и будем считать такой процесс упаковкой. Может быть, у кого-то знак равенства между упаковкой и архивацией вызовет улыбку, и, тем не менее, это-один из самых старых и по сей день популярных способов сжатия информации, о котором помнят, однако, только специалисты. Он отличается исключительной простотой и высокой скоростью работы. Вот лишь краткий перечень задач, элегантно решаемых с помощью упаковки:

- многие знают, что файлы на дисках хранятся по секторам. Размер сектора обычно равен или кратен 512 байтам, размеры же файлов самые разные. Поскольку кластер-минимальная, неделимая единица объема диска, состоит из нескольких секторов, то файлы длиной 2 и 508 байт займут один кластер, а файлы размером в 513 и 1001 байт-уже, может быть, два. В любом случае мы можем потерять до 511 неиспользованных байт. 

Еще хуже дело обстоит на современных жестких дисках объемом в сотни МБ с файловой системой FAT под управлением MS-DOS. Так как на таком диске может быть не более 64000 кластеров (округленно), то для 600МБ диска размер кластера составляет 16 кб. Такими же могут быть и потери в расчете на один файл. 

Одна из первых программ-архиваторов MatchBox объединяла несколько маленьких файлов в один непрерывный и могла при необходимости извлекать их обратно, экономя в среднем по полкластера на файл.

- Такую же процедуру выполняет архиватор RAR при создании так называемых Solid-архивов, выигрывая на зтом несколько процентов в степени сжатия.

- Различные менеджеры expanded-памяти (^ QEMM и Optimize, EMM386 и Memmaker). Эти утилиты призваны поместить в области High и Upper Memory MS-DOS как можно больше файлов и для этого они пытаются так расположить (упаковать) программы, чтобы свести к минимуму потери памяти.

Сжатие видео - (англ. Video compression) -- уменьшение количества данных, используемых для представления видеопотока. Сжатие видео позволяет эффективно уменьшать поток, необходимый для передачи видео по каналам радиовещания, уменьшать пространство, необходимое для хранения данных на носителе. Недостатки: при использования сжатия с потерями появляются характерные, иногда отчётливо видные артефакты -- например, блочность (разбиение изображения на блоки 8x8 пикселей), замыливание (потеря мелких деталей изображения) и т. д. Существуют и способы сжатия видео без потерь, но на сегодняшний день они уменьшают данные недостаточно.

Сжатие звука - совокупность технологий по уменьшению объема данных, необходимых для передачи и хранения звуковой информации. Базируясь на основных принципах сжатия информации, при сжатии звука используются особенности звуковой информации, особенности природы, механизмов проихождения звука (речь, музыкальные инструменты и т.д.) и звуковосприятия.

Звук, как и любой аналоговый сигнал может быть описан временной и спектральной диаграммами.

Оцифровка звука сводится к дискретизации последующему квантованию с шагом и кодированию .

С учетом особенностей слухового аппарата человека стандартизированы следующие уровни частот:

- 44 кГц

- 22 кГц (

- 8 кГц (

Один из классических способов сжатия - так называемая "адаптивная дифференциальная ИКМ" (АДИКМ) основан на следующем:

- вместо кода абсолютного значения очередного импульса передают код изменения его амплитуды по отношению к предыдущему (дифференциальному);

- при увеличении скорости изменения сигнала шаг его квантования возрастает, а при уменьшении - уменьшается (адаптивность).

Использование АДИКМ позволяет уменьшить объем передаваемых данных примерно на порядок без потери информации.

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

Частота дискретизации согласно теореме Найквиста-Котельникова должна быть не меньше удвоенной максимальной частоты спектра сигнала.

Погрешности квантования опре6деляются исходя из емкости кода для максимального уровня сигнала - 8 или 16 бит на отсчет.

Второй способ сжатия именуется компадированием и использует известную особенность человеческого слухового аппарата, вследствие которой ухо менее критично к погрешностям квантования при более громком звуке.

Механизм компадирования выгладит следующим образом (рис.5.7) 

звуковой сигнал перед оцифровкой подается на так называемый «компрессор» КМП - нелинейный преобразователь, «растягивающий» слабые сигналы и «сжимающий» сильные;

после передачи зашумленный погрешностями АЦП сигнал подается на вход «эспандера», который в противоположность компрессору сжимает слабые сигналы и растягивает сильные, восстанавливая первоначальный баланс, при этом погрешности , попавшие в область слабых сигналов, уменьшаются, а сильных - возрастают.

Это не только позволяет учесть особенности человеческого восприятия звука, но и приводит к уменьшению «среднестатистических» погрешностей квантования: дело в том, что слабые сигналы встречаются чаще (мы, например, как правило, говорим вполголоса, а не кричим).

Компадирование получило очень широкое распространение в системах передачи звуковых сигналов. Стоит только добавить, что в современных системах вместо комбинации - аналоговый компрессор (эспандер) + АЦП (ЦАП) реально используются АЦП с нелинейной характеристикой.

Наряду с описанными при сжатии звука используются еще некоторые дополнительные способы, например:

- урезание спектра сигналов (уменьшение частоты дискретизации при условии не критичности к качеству звучания);

- сжатие участков «тишины» (когда амплитуда сигнала меньше определенного порогового значения). 

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

Алгоритмы сжатия без потерь

RLE -- используется в форматах PCX -- в качестве основного метода и в форматах BMP, TGA, TIFF в качестве одного из доступных.

LZW-- используется в формате GIF

LZ-Huffman -- используется в формате PNG

Алгоритмы сжатия с потерями

Наиболее популярным примером формата изображения, где используется сжатие с потерями, является JPEG

На мобильных платформах применяется перевод изображения в палитровый формат.

JPEG 2000

Алгоритм фрактального сжатия

DXTC -- компрессия текстур, реализованная в графическом API DirectX и поддерживаемая на аппаратном уровне современными видеокартами.

Сжатие изображений на базе дифференциального анализа

Программы восстановления изображений.

Иногда возникают ситуации, когда надо восстановить удаленные или поврежденные системные файлы или возникают вопросы: "Как восстановить поврежденные файлы?". Системные файлы повреждаются в результате: внезапного отключения питания компьютера, замены зараженными файлами в результате действия вирусов. Вследствие всевозможных событий вы обнаруживаете, что файлы не открываются. 

Операционная система выдаёт какие-то малопонятные ошибки, работающие ранее программы, не открывают документы или фотографии. В результате этого вы приходите к выводу, что файлы испорчены. Однако не стоит их преждевременно удалять, так как имеются различные утилиты для восстановления. 

Есть популярная утилита Advanced Word Repair, которая прекрасно справится с восстановлением файлов в формате doc. Щёлкнув дважды по ярлыку программы на рабочем столе, запустится программа для восстановления поврежденных файлов Advanced Word Repair. Если ярлык программы на рабочем столе отсутствует, то его можно отыскать в папке программы. Далее укажите необходимые параметры, такие как адрес поврежденных файлов, их тип и другие. 

После завершения работы программы проверьте работоспособность восстановленных файлов. Если файлы опять не запустятся, значит, восстановление прошло неудачно. Попробуйте запустить другие программы. В результате долгого поиска вы всё же найдёте необходимую программу. Разработчики программ наверняка уже сталкивались с подобными проблемами, и нашли решение в виде утилит. Можно использовать программу Undelete Plus.

При запуске программы в появившемся окне выберете диск, с которого нужно восстанавливать файлы. После нажатия кнопки «Старт» будет выдан список файлов, восстановление которых возможно. Выберете необходимые файлы и запустите функцию «Восстановить». 

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

Запустите программу. Перед вами появится окно, в котором найдите диск, на котором надо искать файлы для восстановления. После этого нажмите кнопку «вперед». Будет произведен поиск, в ходе которого программа покажет все файлы, доступные для восстановления. Выберите нужные документы и нажмите на кнопку «Восстановить».

Методы компрессии статического изображения.

Все стандарты сжатия статического изображения направлены на обработку одного единственного образа. Самый известный и широко распространенный стандарт - JPEG.

JPEG - сокращение от Joint Photographic Experts Group (Объединенная Фотографическая Группа Экспертов) - качественный и очень популярный стандарт для статических изображений, который поддерживается практически всеми современными программами. Для просмотра JPEG файлов достаточно стандартных Web-браузеров, которые осуществляют их декомпрессию и отображение на мониторе.

При JPEG компрессии могут использоваться различные уровни сжатия, устанавливаемые пользователем, которые определяют насколько изображение должно быть сжато. Выбранный уровень непосредственно связан с качеством картинки и размером файла. 

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

Некоторые основные принципы JPEG компрессии:

-Чем больше изображение, тем больше данных оно содержит. 

-Чем выше уровень сжатия, тем меньше данных сохраняется и тем более «размытым» становится изображение.

-Чем больше деталей на изображении, тем больше требуется данных для их сохранения. Например: красочное изображение дерева содержит значительно больше данных чем изображение однотонной стены.

JPEG-2000

Еще один формат сжатия, разработанный той же Группой экспертов, JPEG-2000. Он разрабатывался специально для медицинских приложений и цифровой фотографии. При низких уровнях компрессии, обработка изображения происходит аналогично формату JPEG, а при больших степенях сжатия, благодаря новым, прогрессивным, но более сложным алгоритмам, изображение получается более качественным, чем при JPEG. Из-за того, что большинство ПО, в том числе и web-браузеры, не поддерживают этот стандарт, использование JPEG-2000 сильно ограниченно.

Перспектива сжатия информации.

Графические данные, особенно данные растровых файлов, занимают колоссальное количество дискового пространства. Например, растровое изображение формата А4 в цветовой модели CMYK при разрешении 300 точек на дюйм занимает порядка 30 мегабайт дискового пространства. Хорошо, если файл один, и ваша публикация не использует других изображений (что крайне маловероятно). Ситуация в корне изменяется тогда, когда вы создаете некий шедевр, например, галерею репродукций картин А2 формата, при этом она с трудом умещается на 100 листах, запечатанных с двух сторон. При самых скромных подсчетах (120 мегабайт х 100 листов х 2 стороны у каждого листа), растровые изображения в этом формате при таком количестве листов будут занимать порядка 24 гигабайт дискового пространства. На чем вы собираетесь хранить такую публикацию ? А теперь представьте, что у вас несколько заказчиков, и работы каждого из них хранятся в нескольких вариантах оформления, кроме того, для большинства заказов вы сохранили выполненный проект на разных стадиях его готовности, чтобы в случае желания заказчика все в корне и кардинально изменить, вы могли быстро это выполнить.... Естественно, все эти данные сохранить будет очень и очень сложно. Именно поэтому, а также потому, что дисковое пространство обычно достаточно дорого обходится (не смотря на то, что устройства для хранения цифровой информации постоянно дешевеют, их все время требуется больше и больше, что требует немалых капиталовложений), были изобретены множество методов сжатия данных самого различного типа, в том числе и графических. О наиболее распространенных и широко использующихся мы сейчас поговорим.

В самом начале разделим существующие методы сжатия изображений на две условные категории - на архивацию (сжатие), и на компрессию (конвертирование). Разница между этими способами в том, что второй не подразумевает полного восстановления исходного сохраненного изображения в полном качестве. Но каким бы не был алгоритм компрессии данных, для работы с ним файл нужно проанализировать и распаковать, т. е. вернуть данные в исходный незапакованный вид для их быстрой обработки (обычно это происходит прозрачно для пользователя). Ниже мы рассмотрим способы сжатия подробнее.

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

Компрессия (конвертирование) данных - это способ сохранения данных таким образом, при использовании которого не гарантируется (хотя иногда возможно) полное восстановление исходных графических данных. При таком способе хранения данных обычно графическая информация немного "портится" по сравнению с оригинальной, но этими искажениями можно управлять, и при их небольшом значении ими вполне можно пренебречь. Обычно файлы, сохраненные с использованием этого способа хранения, занимают значительно меньше дискового пространства, чем файлы, сохраненные с использованием простой аривации (сжатия). Сильная степень компрессии при использовании второго способа сжатия и дает этому способу хранения данных право на существование (в противном случае, все поголовно использовали бы сжатие без потерь). Как правило, при сохранении данных с использованием компрессии, имеется возможность компромисса между размером выходного файла и его качеством. Понятно, что возможна оптимизация только по одному параметру (чем меньше качество, тем меньше объем выходного файла, и наоборот).

Ниже будут рассмотрены некоторые алгоритмы сжатия данных, их достоинства и недостатки, а также оптимальная их сфера применения (т. е. те типы изображений, к которым данный метод сжатия лучше применять).

Вначале рассмотрим несколько алгоритмов сжатия данных, которые не вносят изменения в исходные файлы и гарантируют полное восстановление данных.

RLE (Run - length encoding) - метод сжатия данных, при котором одинаковые последовательности одних и тех же байт заменяются однократным упоминанием повторяющегося байта (или целой цепочки байтов), и числа его повторений в исходных данных. Например, строка типа 0100 0100 0100 0100 0100 0100 0100 0100, описывающая некую группу пикселов будет заменена на запись типа 0100 х 8, и т.д. Применяется этот тип сжатия в тех случаях, когда изображение имеет большие участки одинакового цвета, цифровое представление которых идентично. В основном, этот тип сжатия применим для монохромных изображний, сохраненных в цветовой модели Bitmap, где при сжатии данных с его использованием можно добиться наилучших результатов. Для сжатия других типов данных (в том числе, и не графических) алгоритм применим, но малоэффективен, так как сжимаемые данные должны иметь простую повторяющуюся структуру). Этот алгоритм имеет еще одно важное преимущество, заключающееся в его относительной простоте, что позволяет быстро производить распаковку из этого формата и упаковку в этот формат (как вы помните, все графические данные для их обработки должны быть предварительно распакованы, а любая компрессия или архивация применяется, в основном, для временного или постоянного хранения файла). В принципе, на основе этого несложного алгоритма, работают более совершенные и более сложные (а также менее быстрые) методы сжатия графических данных, которые мы рассмотрим ниже. Этот метод сжатия графических фанных испольуется для файлов формата PSD, BMP и других.

CCITT Group 3, CCITT Group 4 - Два похожих метода сжатия графических данных, работающие с однобитными изображениями, сохраненными в цветовой модели Bitmap. Основаны на поиске и исключении из исходного изображения дублирующихся последовательностей данных (как в предыдущем типе сжатия, RLE). Различием является лишь то, что эти алгоритмы ориентированы на упаковку именно растровой графической информации, так как работают с отдельными рядами пикселов в изображении. Изначально алгоритм был разработан для сжатия данных, передаваемых через факсимильные системы связи (CCITT Group 3), а более совершенная разновидность этого метода архивации данных (CCITT Group 4) подходит для записи монохромных изображений с более высокой степенью сжатия. Как и предыдущий алгоритм, он, в основном, подходит для сжатия изображений с большими одноцветными областями. Его достоинством является скорость выполнения, а недостатком - ограниченность применения для компрессии графических данных (не все данные удается таким образом эффективно сжать). Этот метод сжатия графических фанных испольуется в файлах формата PDF, PostScript (в инкапсулированных объектах) и других.

LZW (Lemple-Zif-Welch) - алгоритм сжатия данных, основанный на поиске и замене в исходном файле одинаковых последовательностей данных, для их исключения, и уменьшения размера "архива". В отличие от предыдущих рассмотреных методов сжатия, в данном случае производится более "интеллектуальный" просмотр сжимаемого cодержимого, для достижения большей степени сжатия данных. Данный тип сжатия не вносит искажений в исходный графический файл, и подходит для обработки растровых данных любого типа - монохромных, черно - белых, или полноцветных. Наилучшие результаты получаются при компрессии изображений с большими областями одинакового цвета или изображений с повторяющимися одинаковыми структурами. Этот метод позволяет достичь одну из самых наилучших степеней сжатия среди других существующих методов сжатия графических данных, при одновременном полном отсутствии потерь или искажений в исходных файлах. Этот метод сжатия графических фанных испольуется в файлах формата TIFF, PDF, GIF, PostScript (в инкапсулированных объектах) и других.

ZIP - метод сжатия данных, аналогичный методу, использованному в популярном алгоритме архивации PKZip. В основу метода сжатия положен метод, аналогичный LZW. Как и предыдущий метод сжатия данных, этот способ не вносит искажений в исходный файл, и лучше всего подходит для обработки графических данных с одинаковыми одноцветными или повторяющимися областями. Этот метод сжатия графических фанных испольуется в файлах формата PDF, TIFF и некоторых других.

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

JPEG (Joint Photographic Experts Group) - метод, используемый для хранения полутоновых и полноцветных изображений, позволяющий добиться наивысшей степени сжатия и минимальный размер выходного файла. Основан алгоритм на особенностях восприятия человеческим глазом различных цветов, и достаточно громоздок с вычислительной точки зрения, так как занимает много процессорного времени. Происходит кодирование файла в несколько этапов. Во-первых, изображение условно разбивается на несколько цветовых каналов, для дальнейшего анализа. Затем, изображение разбивается на группы, по 64 пиксела в каждой группе, которые представляют из себя квадратные участки изображения размером 8х8 пикселов, для последующей обработки. Затем, цвет пикселов специальным образом кодируется, исключается дублирующая и избыточная информация, причем при описании цвета большее внимание уделяется скорее яркостной, чем цветовой составляющей, так как человеческий глаз воспринимает больше изменения яркости, чем конкретного цветового тона. Полученные данные сжимаются по RLE или LZW - алгоритму, для получения еще большей компрессии. В результате, на выходе мы получаем файл, иногда в десятки раз меньший, чем его неконвертированный аналог. Однако, чем меньше размер выходного файла, тем меньше степень "аккуратности" при работе программы - конвертора, и, соответственно, ниже качество выходного изображения. Обычно, в программах, позволяющих сохранять растровые данные, возможно задание некоего компромисса между объемом выходного файла и качеством изображения. При наивысшем качестве, обхем выходного файла в 3-5 раз меньше исходного незапакованного. При наименьшем - меньше исходника в десятки раз, но, как правило, при этом качество изображения не позволяет его где-либо использовать. Как правило, для сохранения достойного уровня качества, используют наивысшую из доступных степень качества. Данный формат предназначен для хранения, в основном, фотографических изображений с большим количеством оттенков и цветовых переходов, и практически не подходит для хранения однотонных изображений типа кадров из мультфильмов, скриншотов и пр.(сжатие будет слишком низким, или качество картинки окажется просто недопустимым). Этот метод сжатия графических фанных испольуется в файлах формата PDF, PostScript (в инкапсулированных объектах), собственно, в JPEG и других.

...