В.Д. Валединский - Краткий конспект курса лекций «Работа на ЭВМ и программирование» (1119512), страница 9
Текст из файла (страница 9)
Легко видеть, что при алфавите из 256символов мы в лучшем случае сожмем 255 байт в 3 (сжатие в 85 раз), в худшем – один байтразожмем в 2 (но в силу того, что $ - наиболее редко встречающийся символ, происходитьэто будет не чаще, чем 1 раз на 256 элементов, поэтому увеличиться последовательность вдлину может не более чем в 1.004 раза).
Однако подобный подход предусматривает 2прохода по последовательности для ее сжатия, поэтому обычно используют 2 другихреализации (собственно, их и называют RLE).Байтовый вариант предусматривает, что входная последовательность – это некотораяпоследовательность байт (т.е. алфавит из 256 элементов). Сжатие будем проводитьследующим образом: введем понятие группы символов. Перед каждой группой обязательноуказывается служебный байт формата (стартовый бит)(7 бит длины). Если первый бит идет0, то это означает, что в следующих 7 битах указана длина куска последовательности (вбайтах), который никак не сжат; располагается этот кусок сразу после служебного байта.Если первый бит – 1, то в следующих 7 битах указывается длина повторяющейсяпоследовательности из 1 байта, который приводится сразу за служебным байтом.Служебный байт и следующие за ним данные образуют группу.
Понятно, что в лучшемслучае группа «разжимается» из 2 байт в 127-128 байт (7-битное число представляет собойчисла от 0 до 127), в худшем – из 2х байт в 1, но можно проводить сжатие так, чтобыхудший случай был – из 128-129 байт в 127-128. Выигрыш при удачном сжатии, такимобразом, доходит до 64-кратного уменьшения длины исходного файла; худшие возможныепотери – увеличение длины последовательности в 1.008 раз, что несколько хужеописывавшегося выше алгоритма, зато работа происходит быстрее. Пример сжатия RLE:AAAABBBCCDABCDAAAABBBBB будет сжато в[10000100]A[10000011]B[10000010]C[00000101]DABCD[10000100]A[10000101]B- из 24 байт в 16.Другая вариация RLE – битовая. Она широко используется при сжатии черно-белыхизображений (например, графических изображений текстов), где цвет каждой точки можнопредставить 1 битом и существует много длинных последовательностей нулей и единиц вЛекции по ЭВМ.
Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год30последовательности, представляющей картинку. В этом случае будем кодироватьпоследовательность 8-битными числами вида(цвет точки)(длина последовательности)Например, 111111111111100000 такое сжатие запишет как 1000110000000101 – из 17бит сделает 16. В идеале мы сможем сжать 127 бит в 1 байт – выигрыш в длине в 16 раз. Вхудшем случае у нас 1 бит окажется закодированным 1 байтом – проигрыш в длине в 8 раз.Последовательность 1010101 в этом смысле «плохая» - поскольку после сжатия из 6-битнойстанет 48-битной.
Чтобы бороться с этим эффектом используют два оставшихсянезадействованными символа (соответствующие последовательностям из 0 нулей и 0единичек). Например, можно обозначать байтом 10000000 начало несжатойпоследовательности, а 00000000 – ее завершение. Это позволит нам при сжатии файла вхудшем случае увеличить его длину всего на 2 байта, так 1010101 окажется закодированной10000000101010100000000 – всего 22 битами вместо предполагавшихся 48.Впрочем, несмотря на свою простоту и скорость работы RLE предъявляет к сжимаемымданным слишком серьезные требования и не обеспечивает очень хорошего сжатия. Поэтомуобычно RLE используют совместно с более сложными алгоритмами сжатия.Следующий алгоритм сжатия – алгоритм Хаффмана (Huffman).
Идея его состоит втом, что если в сжимаемой последовательности есть неравномерное распределениеразличных элементов, например, элемент A встречается гораздо чаще, чем B, а C вообще невстречается, то наиболее часто встречающиеся элементы надо кодировать короткимипоследовательностями бит, реже встречающиеся – длинными. Рассмотрим случай, когда унас входная последовательность состоит из байт.Будем поступать следующим образом: пусть есть элементы A и B. Нам нужно уметькак-то различать эти элементы, поэтому запишем A как C0, B как C1 (C – некотораяпоследовательность бит). Заменив всюду A и B в последовательности на указанныефрагменты, получим, что A и B из алфавита последовательности исчезнут, а вместо нихпоявится некоторый элемент C, частота встречаемости которого равна сумме частотвстречаемости A и B. Повторяя этот процесс в конце концов придем к алфавиту из 1символа – для него можно положить C пустым, ведь один символ разделять ни от чего нетребуется.
Тогда получится, что мы рекурсивно определили каждому из элементовисходного алфавита некоторую последовательность бит, причем такую, что в сжатойпоследовательности всегда с текущего места можно выбрать единственно возможнуюпоследовательность бит, кодирующую следующий символ (просто по построению – мы ведьна каждом шаге были способны это сделать – значит, это можно сделать и после замены Скакой-то конкретной последовательностью). Однако нам еще требуется получитьопределенное сжатие.
Заметим, что чем раньше мы объединили элемент с каким-то другим,тем более длинной последовательностью бит он будет кодироваться.Поэтому построим таблицу встречаемости символов в исходной последовательности.Затем будем идти по этой таблице, на каждом шаге выбирая из нее 2 элемента, наиболеередко встречающихся в последовательности и объединяя их в один, с встречаемостьюравной сумме встречаемостей объединяемых элементов, пока мы не построим для каждогоэлемента входной последовательности цепочку битов, его кодирующую.Пример: A встречается 1 раз, B – 20 раз, C – 3 раза, D – 10.На первом шаге объединяем A с C – получаем элемент (AC), с встречаемостью 4.Кодировать A будем как (AC)0, B как (AC)1.На втором шаге объединяем (AC) с D – получаем элемент (ACD) с встречаемостью 14.Кодируем (AC) как (ACD)0, D – как (ACD)1На третьем шаге объединяем (ACD) с (B) – получаем в алфавите единственный элемент(ABCD) с встречаемостью 44.
Кодируем (ACD) как (ABCD)0 B как (ABCD)1.Остается сказать, что ABCD пусто (нам абсолютно неважно, что там будет – всеразличия – в младших битах) и получим, чтоA кодируется как A = (AC)0 = (ACD)00 = (ABCD)000 = 000B кодируется как B = (ABCD)1 = 1Лекции по ЭВМ. Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год31C кодируется как C = (AC)1 = (ACD)01 = (ABCD)000 = 001D кодируется как D = (ACD)1 = (ABCD)01= 01Легко видеть, что если в исходной последовательности было 44*8 = 352 битаинформации, то в полученной – 1 * 3 + 20*1 + 3 * 3 + 10 * 2 = 50 бит, то есть в более чем в 7раз меньше.Правда, для расшифровки нам понадобится также хранить таблицу встречаемостисимволов, чтобы по ней можно было бы восстановить таблицу кодировок (какой элемент каккодируется), а это – хотя бы 1 Кб информации.
Поэтому сжатие Хаффмана в таком видеэффективно прежде всего на больших длинах кодируемой последовательности, содержащейдостаточно неоднородное распределение символов в ней. Очевидно также, что алгоритмХаффмана не может обеспечить коэффициент сжатия больший 8 (в идеале у нас всеэлементы потока данных удается закодировать 1 битом, т.е. сделать из 8 бит входногопотока – один выходного и лучше быть не может).Несложной модификацией алгоритма Хаффмана является адаптивный алгоритмХаффмана, позволяющий избавиться от необходимости передавать таблицу встречаемостисимволов.
Идея состоит в том, что можно в самом начале кодирования считать таблицувстречаемости заполненной нулями и строить по ней дерево кодирования. Далее длякодирования применяется такой алгоритм:1.Закодируем очередной символ входного потока на основе текущей таблицывстречаемости и выдадим этот символ в выходной поток2.Пересчитаем таблицу встречаемости с учетом добавленного символа и вернемсяк шагу 1 пока у нас еще есть данныеРасжатие данных происходит аналогично – декодер начинает работу с нулевойтаблицей встречаемости, на каждом шаге расжимает очередной символ по текущей таблице,после чего пересчитывает таблицу с учетом вычисленного символа.
Легко видеть, что притаком алгоритме передавать таблицу встречаемости нет надобности, а в среднем таблица впроцессе сжатия быстро придет к виду, дающему оптимальный код для кодирования (на nм шаге из N таблица встречаемости будет похожа на сжатую в N/n раз таблицу дляраспределения в целом по файлу), поэтому в остальном эффективность сжатия примернотакая же, как и у обычного алгоритма Хаффмана.
Такое сжатие можно уже применять и длякоротких файлов с достаточно большой неравномерностью распределения символов.Еще чуть лучшее сжатие на основе «исправления» неравномерного распределенияобеспечивает арифметическое кодирование.Снова возьмем таблицу частот и отрезок [0,1]. Начальный интервал поиска – отрезокцеликом1.Разобьем отрезок поиска на 256 частей, длина которых будет соответствоватьчастоте встречаемости соответствующего символа.2.Теперь пусть во входной последовательности появился символ a. Ставимграницы поиска равными тому самому отрезку, соответствующемувстречаемости символа a.3.Обновляем таблицу встречаемости (вычитаем 1 из статистики по a) ивозвращаемся к шагу 1В конце кодирования у нас получится некоторый небольшой отрезок, который нам инеобходимо закодировать.
Для этого просто выбираем какое-то число x на этом отрезке,причем стараемся это сделать так, чтобы в двоичной записи этого числа (0,1110101….) былокак можно меньше элементов. Чем больше получившийся интервал поиска, тем лучше1можно выбрать элемент – очевидно, в отрезке длины большей, чем n заведомо найдется2элемент c двоичной записью длины n.Для раскодирования требуется все та же таблица встречаемости символов и полученноечисло x. Снова начальный отрезок – [0,1]Лекции по ЭВМ. Конспект.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
