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

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

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

КАМСКАЯ ГОСУДАРСТВЕННАЯ ИНЖЕНЕРНО-ЭКОНОМИЧЕСКАЯ АКАДЕМИЯ

Кафедра математического моделирования и информационных технологий в экономике

Контрольная работа

По дисциплине: «Информатика»

Тема: Приемы и методы работы со сжатыми данными

Выполнила студентка

группа № 4146-с

№ зачётной книжки: 4080207

Каюмова Айгуль Фирдависовна

г. Набережные Челны 2008

Содержание

• Введение
• 1. Простые алгоритмы
• 2. Сжатие документов
• 3. Программы для обработки документов
• 4. Кодирование цветных изображений
• 5. Сжатие цветных изображений
• 6. Инструменты разработчиков
• Заключение
• Список используемой литературы

Введение

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

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

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

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

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

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

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

кодирование архивация сжатие

1. Простые алгоритмы

Начнем с обычных текстовых файлов. Файл состоит из символов и, возможно, "невидимых" кодов управления печатью. Каждый символ в коде ASCII представлен одним байтом, или восемью битами.

Алгоритм кодирования Хаффмана. В основе алгоритма лежит простой принцип: символы заменяются кодовыми последовательностями различной длины. Чем чаще используется символ, тем короче соответствующая последовательность. Например, для английского текста символам e, t, a можно поставить в соответствие 3-битовые последовательности, а j, z, q - 8-битовые. В одних вариантах алгоритма Хаффмана используются готовые кодовые таблицы, в других - кодовая таблица строится на основе статистического анализа содержимого файла см. табл. 7.4. Кодирование Хаффмана. Применение кода Хаффмана гарантирует возможность декодирования. Это важно, так как "упакованные" кодовые последовательности имеют различную длину, в отличие от обычных, длина которых постоянна и равна 8 бит на символ.

Таблица 7.4. Кодирование Хаффмана для текста "The sample you see here is fairty standard” в переводе с английского “Этот пример достаточно типичен"

Алгоритм Лемпеля-Зива (LZ), или Лемпеля-Зива-Уэлча (LZW). Это еще одна схема сжатия, основанная на сведении к минимуму избыточности кодирования. Вместо кодирования каждого отдельного символа LZ-алгоритм кодирует часто встречающиеся символьные последовательности. Например, можно заменить краткими кодами слова "который" "так же", "там", оставляя имена собственные и другие слова, встречающиеся один раз, незакодированными. Программа, реализующая LZ-алгоритм, просматривает файл, содержащий текст, символы или байты графической информации, и выполняет статистический анализ для построения своей кодовой таблицы.

Если заменить 60-70 % текста символами, длина кода которых составляет менее половины первоначальной длины, можно достигнуть сжатия приблизительно в 50 %. При попытке применить этот алгоритм к исполняемым файлам получаются менее впечатляющие результаты (от 10 до 20 % сжатия), так как избыточность кода, создаваемого компиляторами, значительно меньше избыточности текста на естественном языке. Файлы баз данных - еще один трудный случай: записи, содержащие имена, адреса и номера телефонов, редко повторяются, а поэтому плохо поддаются сжатию. В то же время файлы монохромных изображений в формате PICT архивируются довольно хорошо, так как зачастую обладают большой избыточностью, например содержат много белого пространства. Файлы полутоновых и цветных изображений также можно архивировать с помощью алгоритма Хаффмана, хотя и с меньшим успехом.

Большинство пользователей компьютеров Мaс знакомо с утилитами архивации общего назначения. В качестве примера можно привести популярные программы Stuffit Classic и Stuffit Deluxe фирмы Aladin Systems и Compactor фирмы Goodman. Такие программы в основном используют для сжатия нескольких файлов в один архивный файл. Другая программа сжатия - DiskDoubler фирмы Salent Software - представляет собой скорее утилиту для работы с диском, чем архиватор. Двойное нажатие клавиши на манипуляторе "мышь" автоматически запускает программу разархивирования отмеченного файла, а когда вы закончили работать с файлом и сохраняете его на диске, DiskDoubier автоматически выполнит обратную операцию.

2. Сжатие документов

Работа телефакса полностью основана на сжатии информации. Если бы образ вашего листа бумаги размером 297 х 210 мм, снятый с разрешением 8 точка/мм, не был сжат, он занял бы 4 Мб памяти, и для его передачи со скоростью 9600 бит/с потребовался бы почти час. На самом деле это занимает значительно меньше времени. Какие же приемы сжатия используют в факсах.

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

Рис.7.2. Сжатие данных в телефаксах

Более содержательные строки содержат отрезки черного и белого цветов различной длины. Если взглянуть на типичный документ, мы увидим, что число перемен цвета от белого к черному и обратно примерно равно удвоенному числу символов в строке. Сжатая таким образом 80-символьная строка становится набором приблизительно из 160 переходов, а не из 1728 элементов изображения. Если принять во внимание число строк на странице, мы увидим, что это весьма компактная схема кодирования видеоинформации, снятой с разрешением 8 точка/мм см. рисунок 7.2. Рекомендации МККТТ делают эту схему сжатия еще более эффективной: можно учитывать и взаимосвязи между строками. Предусмотрены, например, короткие кодовые комбинации для "следующая строка такая же, как эта" и "этот фрагмент такой же, как предыдущий", что еще больше повышает эффективность сжатия.

3. Программы для обработки документов

Хотя алгоритмы сжатия, применяемые в телефаксах, непригодны для цветных и полутоновых изображений, они, очевидно, могут быть полезны для сжатия деловых документов, содержащих только текст и штриховые рисунки. Поэтому неудивительно, что многие фирмы использовали алгоритмы сжатия, подобные применяемым в телефаксах, для обработки деловой документации. Этот подход реализован в самых разныхпрограммныхизделиях, от простых программ для однопользовательских систем до насыщенных мощными средствами программно-аппаратных комплексов, предназначенных для архивации и индексирования документации в объединяющий ряд географически разнесенных отделений корпорации. Один из примеров - система Hurdler CER для шины NuBus фирмы Creative Solutions, выполняющая сжатие и преобразование данных. На плате через встроенное постоянное запоминающее устройство реализована схема сжатия данных группы IV, в которой слегка улучшена обработка ошибок (небольшие ошибки могут не иметь значения при приеме факсов, но перерастают в большую проблему при записи информации на диск). Быстродействующая микросхема сопроцессора позволяет комплексу CER сжимать файлы, полученные в результате обработки сканером монохромного изображения, со скоростью 16 млн. элементов изображения в минуту. Фирма Creative Solutions поставляет вместе с комплексом CER специальные драйверы, позволяющие пользователям передавать файлы непосредственно в интерфейс NuBus, при этом не требуется никакого дополнительного программного обеспечения.

Система архивации документов ArcImage фирмы First Financial Technology обладает более широкими возможностями. Эта система первоначально была предназначена для удовлетворения внутренних потребностей фирмы, связанных с обработкой банковских документов. В состав системы входят плата-акселератор с интерфейсом NuBus и программное обеспечение. В комплекте поставки имеются также простая в обращении обучающая программа и документация. Плата для шины NuBus с системой ArcImage позволяет в режиме реального времени обрабатывать информацию с выхода быстродействующего сканера Fujitsu с автоматической подачей бумаги со скоростью 12 листов в минуту. Таким образом, необработанные файлы изображения (в формате PICT) никогда не записываются на жесткий диск. Система сохраняет два разных файла - файл низкого разрешения для вывода на дисплей и файл высокого разрешения для печати. Это позволяет, с одной стороны, быстро выводить изображение на экран, а с другой - печатать его с хорошим качеством на лазерном принтере. Система ArcImage в полной конфигурации состоит из драйвера оптического диска, высокоскоростного сканера и сетевого оборудования, но вполне можно ограничиться жестким диском и сканером.

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

Например, система FastTrax фирмы Du Pont Electronic предназначена для архивации, хранения и восстановления файлов чертежей. Она работает в сети компьютеров Mac и использует устройство, которое фирма Du Pont называет "оптическим накопителем башенного типа" и которое предназначено для хранения файлов изображений, объединенных в индексированную базу данных. В системе MD Mars фирмы Micro Dynamics используются сканеры, работающие с документацией и микрофильмами, для преобразования документов в архивные файлы на переписываемых оптических дисках. Пользователи сети Appie Talk могут впоследствии вызвать и восстановить эти файлы. Предусмотрена даже возможность создания копий предыдущих версий файлов на оптических дисках с однократной записью (WORM). Как в системе FastTrax, так и в MD Mars для сжатия данных используется плата Hurdler CER.

Основное отличие программы Visualink фирмы CSX Technology от программ FastTrax или MD Mars состоит в возможности сжимать факсы уже во время их приема, а не после его окончания.

4. Кодирование цветных изображений

Если вы постоянно работаете с полутоновыми или цветными изображениями, алгоритмы сжатия информации группы IV вам не подойдут. Цветные изображения содержат большое количество информации. Каждый элемент изображения, считанного с разрешением 12 точек/мм, описывается 32 битами информации: 8 бит на интенсивность красного цвета, 8 бит на зеленый, 8 бит на синий, плюс 8 дополнительных бит (RGB-описание). Даже для передачи градаций серого цвета в полутоновом изображении требуется 8 бит. Объем информации здесь значительно больше, и ее характер непрерывно меняется вдоль линии сканирования, поэтому схемы сжатия, разработанные для текстовых файлов и штриховых рисунков, здесь неприменимы. В отличие от рассмотренных выше, алгоритмы сжатия цветных образов основаны на особенностях цветовой чувствительности человеческого глаза.

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

Алгоритмы сжатия цветных образов, преобразуя обычное описание изображения, основанное на содержании в нем красного, зеленого и синего цветов (RGB), в представление, основанное на характеристиках цветности и яркости, базируются на специфике человеческого цветовосприятия. Эти алгоритмы исключают информацию, которая не воспринимается глазом, и таким образом уменьшают сохраняемый объем данных. В течение 1990 г. схема сжатия, предложенная Объединенной группой экспертов в области фотографии (JPEG), завоевала практически всеобщее признание как стандартный метод обработки неподвижных изображений. Другой коллектив, группа экспертов в области движущихся изображений (MPED), разработал схемы сжатия для видеозаписей. Работа с цветностью и яркостью, а не с RGB-описанием, позволяет алгоритму JPEG использовать тот факт, что на большой площади изображения изменения цвета и интенсивности незначительны. Чистое голубое небо, например, на залитом солнцем пейзаже состоит из множества элементов изображения, но содержит мало информации. При обработке каждого участка размером 8х8 элементов изображения с помощью алгоритма JPEG применяются последовательно три процедуры: дискретное косинус-преобразование (ДКП), квантование и схема кодирования, подобная алгоритмам обработки текстовых файлов. При восстановлении к каждому такому участку применяется обратная процедура. Все это требует, безусловно, значительных вычислений.

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

5. Сжатие цветных изображений

Наряду с пакетами Colorsgueeze фирмы Kodak и PicturePress фирмы Storm Technology рассмотрим программу SuperSgueeze, предназначенную для сжатия неподвижных изображений, фирмы Super Mac Technology.

Программа Colorsgueeze является наиболее простой в обращении из программ, предназначенных для сжатия цветных изображений. При использовании этого изделия, реализующего алгоритм JPEG, можно задать один из трех уровней сжатия - высокое, среднее или нормальное - для исходных файлов в 24-битовом формате PICT или TIFF. В результате получаются файлы, размеры которых составляют соответственно около 1/24, 1/13 и 1/6 размера исходного файла.

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

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

Хотя пакет PicturePress был разработан для конечных пользователей, это настоящий Диснейленд в отношении возможностей сжатия данных (рис. 7.3). Этот пакет представляет все те же возможности, что и ряд других, но предназначен для пользователей, немного лучше разбирающихся в обработке изображений. Кроме выбора одного из четырех стандартных уровней сжатия, PicturePress предлагает в специальном диалоговом окне Custom подобрать весовые коэффициенты в таблицах яркости и цветности. Программа PicturePress фирмы Storm Technologies позволяет полностью управлять всеми аспектами сжатия изображения, вплоть до подбора весовых коэффициентов в таблицах цветности и яркости. Программа позволяет также осуществлять сжатие без потерь и использовать расширения стандар- та JPEG.

Фирма Storm предусмотрела в программе PicturePress несколько интересных расширений по сравнению со стандартом JPEG. Стандарт JPEG++ позволяет задавать разные уровни сжатия для различных частей изображения. Другое расширение стандарта - режим сжатия без потерь, обеспечивающий максимальную экономию места на диске с полным сохранением всей информации (при этом достигается сжатие в 2 - 3 раза). Обычный алгоритм JPEG называется "алгоритмом с потерями", так как при его применении программа намеренно исключает из файла "излишнюю" часть информации.

Фирма StormTechnology выпустила плату PicturePressAccelerator. Плата с интерфейсом NuBus, поставляемая вместе с программой PicturePress, содержит два процессора обработки сигналов, которые выполняют арифметические операции при сжатии. PicturePress автоматически "перепоручает" вычисления процессорам на плате, и таким образом время, требуемое на выполнение сжатия, уменьшается приблизительно в 20 раз. Вычисления все же происходят недостаточно быстро для восстановления видеоизображений. Тем не менее восстановление сжатых образов требует столько же времени, сколько и загрузка с жесткого диска в память исходного несжатого файла или даже меньше.

Рис. 7.3. Возможности пакета PicturePress

Фирма C-Cube в свою очередь выпустила систему Compression Master, плата для шины NuBus которой содержит специальную микросхему CL550, разработанную фирмой и предназначенную для сжатия файлов изображений. В систему входит также утилита DiskDoubler Plus фирмы Salient, используемая для сжатия файлов в форматах PICT и TIFF.

Компания Advent Computer Products также объявила о выпуске платы Neotech Image Compressor на основе микросхемы CL550.

6. Инструменты разработчиков

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

Если говорить о рынке систем общего назначения, то комплекты средств для разработчиков таких систем предлагают фирмы Aladdin Systems и Salient Software. Эти пакеты позволяют использовать алгоритмы, реализованные соответственно в программах Stuffit Deluxe и DiskDoubler, в новых прикладных программах через подсистему взаимодействия прикладных программ ICA.

У программистов, занимающихся обработкой цветных и полутоновых изображений, тоже есть выбор. Одна из лидирующих фирм в этой области, Electronic for Imaging (EFI), предлагает JPTG-совместимую библиотеку функций Ecomp. Эту библиотеку можно использовать как для создания новых программ обработки изображений, так и для модификации уже имеющихся, с целью включить в них функции сжатия образов.

Фирма C-Cube предложила интерфейс сжатия образов ICI (набор соглашений, в соответствии с которыми прикладные программы могут взаимодействовать с аппаратными и программными средствами архивации). Фирма предлагает Compression Workshop - набор исходных текстов на стандартных диалектах языков Си и ПАСКАЛЬ, который позволяет использовать ICI в прикладных программах. Интерфейс ICI обеспечивает сопряжение средств сжатия с программами Photoshop фирмы Adobe, QuarkXpress 3.0, Stuffit Deluxe, Studio-32, а также DiskDoubler Plus. C-Cube также предлагает программно-аппаратный инструментальный комплекс, позволяющий разработчикам оценить по достоинству микросхему CL550, аппаратно реализующую алгоритм JPEG.

Самый большой файл, который вы могли создать с помощью программы MacPaint для одной страницы, занимал меньше 500 Кб, даже если вы задавали для каждого элемента изображения расширенное описание. Затем появилась 32-битовая программа Color QuickDraw, которая создавала растровые файлы почти в 100 раз большего размера. Тем временем число обычных файлов, которые должен был обрабатывать компьютер, тоже стремительно росло, а появление сканеров еще больше обострило проблему нехватки места на дисках. Ни одна фирма, производящая программы для цветной графики, не осмелится выпустить свое изделие, не оснастив его встроенными средствами сжатия и восстановления данных (возможно, подключаемыми командой из меню File). Кроме того, ожидается появление новых цветных сканеров и фиксаторов видеокадров со встроенными аппаратными средствами сжатия данных. Фирма Apple, в свою очередь, активно развивает собственные алгоритмы сжатия. Уже в 1990г. на демонстрации технологий, состоявшейся во время конференции Siggraph, фирма показала собственное программное обеспечение для сжатия и восстановления видеоинформации, которое послужило дополнением системных программ и 32-битовой программы QuickDraw. Столкнувшись с проблемами быстродействия, некоторые производители обратились к специализированным микросхемам типа CL550 фирмы C-Cube для воплощения алгоритмов сжатия в аппаратуре. Фирма Next создала Nextdimension - 32-разрядный адаптер цветного дисплея. В состав адаптера входят: 64-разрядный графический RISC-сопроцессор и процессор обработки изображений CL550 фирмы C-Cube. Фирма Apple нашла место для схемы сжатия изображений на плате центрального процессора Macintosh. Схема CL550 с тактовой частотой 10 МГц была бы в этом случае неплохим вариантом: ее цена близка к цене модуля памяти SIMM емкостью 1 Мб - даже при невысоких объемах производства.

Но разработка аппаратных средств - не единственный путь к повышению быстродействия. Фирма Radius выпустила программы сжатия данных под условным названием Piculator, которая сравнима с аппаратными средствами, реализующими JPEG-алгоритмы, и поэтому может стать приемлемым вариантом для использования в приложениях, интенсивно работающих с графикой. Программа сжимает файл изображения в формате PICT размером 1 Мб менее чем за 6 с на компьютере MacIIсх, и при этом его размер уменьшается в 20 раз и более. При такой скорости работы программы время восстановления файла пренебрежимо мало по сравнению со временем, необходи мым для загрузки прикладной программы. И хотя вначале сжатие данных всерьез интересовало только специалистов по обработке медицинской информации и ученых из НАСА, теперь мы удивляемся тому, как вообще могли обходиться без подобных средств.

Заключение

Характерной особенностью большинства данных является определенная избыточность, которая зависит от:

а) типа данных;

б) принятой системы кодирования.

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

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

Существует достаточно много алгоритмов сжатия данных, однако все они теоретически основаны на трех способах уменьшения их избыточности: изменение содержания данных; изменение их структуры; изменение содержания данных и их структуры. Изменение содержания данных при их сжатии делает метод сжатия необратимым и полное восстановление информации невозможно. Такие методы называются методами сжатия с регулярной потерей информации. Они применимы для данных, где формальная утрата части содержания не приводит к значительному снижению потребительских свойств. Сюда относятся мультимедийные данные: звукозаписи, рисунки и др. (форматы сжатия: .JPG для графических данных, .MP3 для звуковых данных, .MPG для видеоданных). Эти методы, обладая более высокой степенью сжатия, чем обратимые методы, неприменимы к текстовым документам, базам данных, программному коду.

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

Теоремы:

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

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

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

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

В основе существующих обратимых методов сжатия данных лежат теоретические алгоритмы RLE, KWE и алгоритм Хаффмана.

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

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

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

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

Список используемой литературы

1. Коуров Л.В. Информационные технологии. - Мн.: Амалфея, 2000 - 192 с.

2. Киселев С.В., Куранов В.П. Оператор ЭВМ. - М.: ИРПО; Изд. центр «Академия», 1999. - 208 с.

3. Информатика. Базовый курс/Симонович С.В. и др. - СПб.: Изд-во «Питер», 1999. - 640 с.

Размещено на Allbest.ru