Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Так, например, если число 0 повторяется двадцать раз подряд, то нет смысла ставить двадцать нулевых байтов. Вместо них ставят один ноль и коэффициент 20

Так фраза «КОЛОКОЛ_ОКОЛО_КОЛОКОЛЬНИ»[24] закодируется в последовательность «КОЛО(-4,3)_О(-6,4)_(-7,7)ЬНИ»[13]. Коэффициент сжатие - 54%.

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

Алгоритм Лемпеля-Зива (метод RLE (Run Length Encoding).

Т.е. сжатие будет в 3 раза.

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

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

Рассмотрим следующий пример:
исходный поток АБАБАБАВАБВГ = 12 байт
выходной поток Пусть символы кодируются как
А=1
Б=01
В=001
Г=000
тогда будет 101101101101001101001000 = 25 бит = 3 байт + 1 бит

 

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

 

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

Аналогично сжимается изображение. Большие области одного цвета заменяются на ссылку: (цвет, длина) Графические файлы сжимаются очень хорошо – в 100–200 раз!

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

Данные методы, как правило, достаточно эффективны для сжатия растровых графических изображений (BMP, PCX, TIF, GIF), т.к. последние содержат достаточно много длинных серий повторяющихся последовательностей байтов.

<== предыдущая лекция | следующая лекция ==>
Сжатие без потери информации | В файловой системе компьютера архивные файлы имеют строго заданный тип (расширение). Так, наиболее часто встречающиеся архивы имеют тип: ZIP, RAR, ARJ
Поделиться с друзьями:


Дата добавления: 2014-01-20; Просмотров: 295; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.011 сек.