Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Сжатие данных.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Лабораторна робота
Предмет:
Методи i засоби комп'ютерних інформаційних технологій
Частина тексту файла (без зображень, графіків і формул):
Сжатие данных
Сжатием (компрессией) данных называют преобразование их в форму, занимающую меньше места. В такой форме данные и хранить легче (устройства хранения все-таки не резиновые), и передавать по каналам с ограниченной пропускной способностью куда приятнее.
Все алгоритмы сжатия делятся на два типа: с потерями и без.
Сжатие с потерями позволяет достичь гораздо бóльшей степени сжатия (до 1/30 и менее от исходного объема).
Например, видеофильм, занимающий в неупакованном виде гигабайт 30, удается записать на 1 CD.
Однако, алгоритмы сжатия с потерями приводят к некоторым изменениям самих данных; поэтому применять такие алгоритмы можно только к тем данным, для которых небольшие искажения несущественны: видео, фото-изображения (алгоритмы JPEG), звук (алгоритм MP3).
Сжатие без потерь, конечно, не так эффективно (его степень очень зависит от конкретных данных), зато данные после распаковки полностью идентичны оригинальным. Что абсолютно необходимо, например, для текстовых данных, программного кода. В этой статье будет рассматриваться именно сжатие без потерь.
Большинство алгоритмов сжатия без потерь делятся на две группы: первыесоставляют текст из кусочков исходного файла в той или иной форме (словарные методы); вторые (статистические методы) используют тот факт, что разные символы или символьные группы появляются в файле с разными вероятностями (например, буква "а" в текстовых файлах встречается гораздо чаще, чем "б").
Словарные методы
Словарные методы отличаются высокой скоростью сжатия/распаковки, но несколько худшим сжатием. Словом называется некоторая последовательность символов. В общем - речь, конечно, идет не о символах, а о байтах; но для простоты в примерах будут использоваться ASCII-символы.
Словарь содержит некоторое количество слов (обычно 2x; например, 4096).
Сжатие достигается за счет того, что номер слова в словаре обычно гораздо короче самого слова.
Алгоритмы словарного сжатия делятся на две группы:
1) использующие словарь в явной форме(алгоритмы LZ78, LZW, LZC, LZT, LZMV, LZJ, LZFG)
Например, по словарю
1. "Большинство"
2. "сжатия"
3. "без"
4. "потерь"
5. "алгоритмов"
текст "Большинство алгоритмов сжатия без потерь" сжимается в "15234".
2) указывающие вместо номера слова - позицию относительно текущей позиции и длину повторяющегося участка (алгоритмы LZ77, LZR, LZSS, LZB, LZH)
Например, текст "абаббабаббабвгббабв"
сжимается в "05абабб5504абвг65", где:
"05абабб" – позиция 0 означает, что далее 5 символов идут без сжатия.
"55" – 5 букв с позиции , отстоящей от текущей на 5 символов назад.
"04абвг" – еще 4 символа не сжимается.
"65" –5 букв с позиции , отстоящей от текущей на 6 символов назад.
Модификации LZ-алгоритмов отличаются только способами представления словаря, поиска и добавления слов. Одни сжимают быстрее, но хуже; другие требуют больше памяти.
Рассмотрим подробнее модифицированный алгоритм LZ77.
Архив будет состоять из записей следующего вида:
(n,m) – означает, что с позиции n начинается такая же строка длиной m, что и с текущей позиции.
(0,m,"m символов") – означает, что далее следует m символов, которые не удалось сжать.
Алгоритм сжатия будет заключаться в следующем: ищем в файле место, начиная с которого идет самая длинная последовательность, совпадающая с последовательностью, начинающейся на текущем байте. Если ее длина больше 3, то в архив записываем начало и длину последовательности; иначе - записываем 0, длину последовательности и сами несжатые символы. Распаковка еще проще: пока файл архива не кончился, читаем по 2 числа(n,m). Если n=0, то m символов из архива сразу помещаем в буфер (эти символы нам еще понадобятся) и записываем в выходной файл. Если n<>0 то из буфера с позиции n копируем m элементов в буфер и выходной файл.
Однако есть две проблемы:
1) Ограниченный размер буфера: если нам нужно будет сжать файл размеров в 100МБ, мы его в буфер никак не поместим. Поэтому, когда он будет заполнен (скажем, на 75%), придется сдвинуть данные в нем к началу (напр., на 25%;конечно, самые старые символы при этом потеряются). Это ухудшит сжатие, но сделает алгоритм нетребовательным к памяти.
2) Скорость работы программы сжатия очень мала. В самом деле, если нужно будет сжать файл размеров 10КБ, то это потребует от нас проведения как минимум около 10000*10000/2 операций (10000 раз нам нужно будет искать совпадающую подпоследовательность, а каждый такой поиск займет в среднем 10000/2 операций). Для того, чтобы ускорить операцию поиска, можно хранить в отдельном массиве номера позиций последовательностей, начинающихся на символ chr(0), chr(2) … chr(255). Тогда при поиске нам нужно будет проверить только те комбинации, первая буква которых совпадает с первой буквой искомой последовательности.
Статистические методы
Статистические методы гораздо медленнее словарных, но достигают более сильного сжатия. В них каждая буква заменяется некоторым кодом. Код – это несколько бит, однозначно идентифицирующие некоторый символ. Статистические методы используют различные приемы для того, чтобы наиболее часто встречающимся символам соответствовали более короткие коды. Существуют два основных алгоритма кодирования букв в соответствии с их частотой встречаемости:
1) Коды Хаффмана: все символы кодируются целым количеством бит; причем так, что раскодирование всегда однозначно (например, если букве "а" соответствует последовательность бит "1001", а "b" – "10010", то раскодирование неоднозначно). Достоинство - высокая скорость сжатия. Недостатки - неоптимальное сжатие, сложности при реализации адаптивного варианта. Так как в последнее время скорость собственно алгоритма кодирования играет все меньшую роль (алгоритмы накопления статистической информации работают все медленнее и медленнее, и даже 2-х кратное увеличение времени работы кодировщика практически не влияет на скорость), этот алгоритм не имеет существенных преимуществ перед арифметическим кодированием.
2) Арифметическое кодирование: для каждого символа определяется промежуток на отрезке [0..1] и в зависимости от ширины этого отрезка может выделяться разное количество бит, условно говоря, даже дробное (например: пусть строке "a" соответствует0 , а строке "ab" - 1, тогда строка "aba" закодируется в 2 бита, т.е в среднем 2/3 бита на символ). Этот метод точнее использует статистическую информацию, и всегда сжимает не хуже алгоритма Хаффмана, но медленнее. Достоинства - максимальная теоретически достижимая степень сжатия, простая реализация адаптивного варианта. Недостатки - несколько меньшая скорость.
Принцип работы арифметического кодирования:
Например, мы присвоили символу "a" промежуток [0..0.3], "b" – [0.3..0.6] и "c" – [0.6..1]. Тогда, если у нас будет число 0.4, то мы можем сказать, что закодирована буква "b"(0.3<=0.4<=0.6), а если 0.9 – то c(0.6<=0.9<=1). Итак, у нас получилось закодировать 1 букву в число. Как же закодировать 2 буквы? Очень просто: например, если первая буква – "b", то интервал равен [0.3..0.6]. Разделим этот интервал на части, в отношении наших первоначальных отрезков. Тогда 2-м буквам "ba" будет соответствовать интервал [0.3..0.39], "bb" – [0.39..0.48] и "bc" – [0.48..0.6]. Для раскодирования нам достаточно знать любое число из этого интервала.
Попробуем раскодировать: пусть дано число 0.15. Это число попадает в интервал буквы "a"[0..0.3], значит первая закодированная буква – "a". Для того, чтобы узнать вторую букву, нужно преобразовать число, чтобы оно указывало букву в интервале не [0..0.3] , а [0..1]. Для этого от числа отнимем нижнюю границу исходного интервала (0) и разделим на ширину интервала (0.3-0=0.3). Получим новое число(0.15-0)/0.3 = 0.5. Повторив те же действия, мы узнаем, что вторая буква – "b". Если бы было закодировано 3 и более букв, то, многократно повторяя этот процесс, мы нашли бы все буквы.
Почему представление в виде числа позволяет сжать данные:
Более вероятным символам соответствует более широкий интервал, и после кодирования такой буквы, интервал уменьшится ненамного, следовательно, для представления любого числа из этого промежутка понадобится ненамного больше бит.
Алгоритм сжатия:
Для каждого символа мы должны присвоить соответствующий промежуток в соответствии с частотой (вероятностью встречи) в данных: пусть символ "а"имеет вероятность 0.4, "b" – 0,3 и "c" – тоже 0.3; тогда символу "а" будет соответствовать промежуток [0..0.4], "b" – [0.4..0.7], "c" – [0.7..1]. Т.е мы делим имеющийся у нас промежуток между всеми необходимыми буквами в соответствии с вероятностью их встречи (более вероятному символу соответствует больший промежуток).
В процессе сжатия у нас есть 2 границы: верхняя и нижняя, назовем их соответственно hiи lo. Пусть нам нужно закодировать символ, которому мы отвели промежуток [0.4..0.6]. Тогда в наш промежуток [lo..hi] "вставляется" промежуток символа, и lo будет равен нижней границе вставляемого промежутка, hi – верхней. В итоге по мере кодирования промежуток между loи hi становится все уже и уже. Наконец, когда мы закодировали все данные, выбираем любое число из получившегося промежутка и выводим. Оно и будет сжатыми данными.
Распаковка:
Построим промежутки для символов, как и для сжатия. Символ, в промежуток которого попадает число-архив, и есть первый символ данных. "Растягиваем" промежуток символа вместе с числом-архивом до промежутка [0..1] (т.е отнимаем нижнюю границу интервала только что раскодированного символа, и делим на ширину этого интервала), затем повторяем операцию, пока все не раскодируем.
Проблемы:
Если бы все было так просто… На самом деле, для хранения числа-архива нужна будет очень большая точность (десятки и сотни тысяч знаков), поэтому на практике приходится пользоваться обычными типами данных. Чтобы этого добиться, будем смотреть на старшие биты/цифры числа-архива. Как только у hi и lo они совпадут, мы можем сразу записать их в архив и "отсечь". При распаковке наоборот, когда увидим, что мы довольно много раз расширяли промежуток до [0..1], считаем из файла-архива несколько цифр и допишем их в конец нашего числа-архива.
Часто используется модификация арифметического кодирования - range coder. Основное отличие - начальный интервал - [0..255]. Это позволяет выводить данные сразу по байту, а не наскребать по биту, что отражается на скорости работы. В конце статьи приведена реализация именно этого варианта.
Определение вероятностей символов
Основной процесс, влияющий на скорость и степень сжатия – определение вероятностей символов. В простейшем случае будем считать вероятностью символа - количество его встреч в уже закодированной части данных, делённое на общее количество символов в данных. Для текстов это дает приблизительно 2-кратное сжатие. Чтобы его увеличить, можно учитывать такие факты, как, например, то, что вероятность встречи символа "я" после "ю" практически равна 0, а "o" после "с" – около 0.25. Поэтому для каждого предыдущего символа будем отдельно считать вероятности.
Предположения, которые мы делаем относительно сжимаемых данных (например, зависимость вероятности от предыдущих символов) называются вероятностной моделью. Модель, вероятности в которой не зависят от предыдущих символов, называется моделью 0-го порядка. Если вероятности зависят от 1 предыдущего символа, то это модель 1-го порядка, если от 2-х последних – то 2-го и т.д. Для эффективного вычисления вероятностей символов в моделях высокого порядка существуют специальная группа алгоритмов – PPM и его модификации.
Модели могут быть неадаптивными, полуадаптивными и адаптивными. В неадаптивных методах вероятности всех символов жестко зашиты в программу. В полуадаптивных по входным данным делается 2 прохода: 1-й - для определения вероятностей, 2-й – собственно для сжатия. Адаптивный – вероятности символов изменяются в процессе сжатия. Адаптивные модели самые медленные, но они обычно сжимают данные сильнее неадаптивных и полуадаптивных моделей. В общем, среди всех моделей лучше сжимают использующие наибольшее кол-во информации о сжимаемых данных - зависимость от предыдущих символов, некоторые факты, например: в текстах после точки обычно следует большая буква и т.д.
Алгоритмы, используемые в популярных архиваторах:
ZIP,ARJ,RAR - LZ+Хаффман
HA - PPM+Арифметическое кодирование
BOA - BWT+Арифметическое кодирование
UHARC - LZ+PPM+Арифметическое кодирование
(Здесь "+" означает, что результат работы алгоритма, написанного слева от знака, далее сжимается алгоритмом, записанным справа).
Как видно, в архиваторах ZIP,ARJ,RAR ,разрабатывавшихся в конце 80-х - начале 90-х, используются уже довольно устаревшие алгоритмы; поэтому они по тестам проигрывают более современным.
Пример программы адаптивного сжатия/распаковки 0-го порядка:
Данные: compr – тут хранятся сжатые данные
Data- тут хранятся исходные данные
Freq – частоты символов
Procedure compress_range; {Процедура сжатия}
Var
cum_freq: Extended;
Begin
{- Инициализация модели и кодера -}
For q := 0 To 255 Do
freq [q] := 1; {Все символы в начале имеют одинаковую вероятность}
freq [255] := freq [255] - 0.20000;
total := 256; {Сумма частот всех символов.}
{ В freq - небольшой остступ от 0 и макс.значения}
PC := 0;{Кол-во уже закодированых байт }
Lo := 0; range := 256;
{- Кодирование -}
For q := 1 To Size Do
Begin
{Нахождение интервала, соответствующего кодируемому символу}
cum_freq := 0.1; {Начинаем накапливать вероятность}
For w := 0 To data [q] - 1 Do
cum_freq := cum_freq + freq [w];
{Изменяем range&lo}
range := range / total;
Lo := Lo + range * (cum_freq);
range := range * freq [data [q] ];
{Нормализация т.е вывод байтов, одинаковых у Lo и Hi(Hi=Lo+Range)}
While Trunc (Lo) = Trunc (Lo + range) Do
Begin
Inc (PC);
compr [PC] := Trunc (Lo);
Lo := Frac (Lo) * 256;
range := range * 256;
End;
{Обновления модели}
freq [data [q] ] := freq [data [q] ] + 1;
{Присваеваем кодируемому символу на 1 большую вероятность}
total := total + 1;
End;
{Сжатие закончено, выводим остаток}
Lo := Lo + range / 2;
Inc (PC);
compr [PC] := Trunc (Lo);
Lo := Frac (Lo) * 256;
range := range * 256;
End;
Procedure decompress_range;{Процедура распаковки}
Var
temp: Extended;
ee: Extended;
Begin
{Инициализация модели и кодера}
For q := 0 To 255 Do
freq [q] := 1;
freq [255] := freq [255] - 0.20000; { В freq - небольшой остступ от 0 и макс.значения}
total := 256;
PC := 4; {PC - номер байта, которые мы считываем}
code := 0;
Lo := 0; range := 256;
{Считываем начальное, приближенное значение code.}
For q := 1 To 4 Do
Begin
code := code * 256 + compr [q] / 65536 / 256;
End;
w := 0; {W- кол-во верно распакованных байт}
{Собственно расжатие}
While True Do
Begin
{Нахождения вероятности следующего символа}
temp := (code- Lo) * total / range;
{Поиск символа, в интервал которого попадает temp}
sum := 0.1; ssum := 0.1;
For e := 0 To 255 Do
Begin
sum := sum + freq [e];
If sum > temp Then Break;
ssum := sum;
End;
Inc (w);
{Проверка правильности распаковки}
{Сейчас в e – распакованный байт, и его можно выводить в файл}
If data [w] <> e Then Break; {Если неправильно распаковали - выходим}
If w = Size Then Begin Inc (w); Break End; {Если все распаковали выходим,}
{и модель не обновляем :-)}
{Обновления Lo&Hi(Растягивание)}
range := range / total;
Lo := Lo + range * (ssum);
range := range * (freq [e] );
{Обновление модели(Делаем символ e более вероятным)}
freq [e] := freq [e] + 1;
total := total + 1;
{Нормализация, уточнение числа}
While Trunc (Lo) = Trunc (Lo + range) Do
Begin
Inc (PC);
temp:=compr[PC];
code := (code - trunc(code)) * 256 + temp / 16777216;
Lo := Frac (Lo) * 256;
range := range * 256;
End;
End;
Dec (w);
{DONE_DECOMPRESS}
End;
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора