Обратимые методы сжатия

Обратимое сжатие всегда приводит к снижению объема выходного потока информации без потери информационной структуры

Метод упаковки

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

Метод построения дерева Хаффмана

Подсчитать количество встречаемости символов в сообщении.

Объединить 2 наименьших символа, вычислить сумму.

Производить объединение до получения одного единственного элемента.

Расставить кодировку дуг (0 или 1)

Выписать полученные кодовые комбинации.

Алгоритм RLE

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

Словарные методы сжатия

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

Алгоритм LZW

Разбор сжимаемой последовательности символов на отдельные фразы с перекрытием (цепочки фраз).

20. Коды Хаффмана и READ.Алгоритм построения дерева Хаффмана 1.Символы входного алфавита образуют список свободных

узлов. Каждый узел имеет вес, равный количеству вхождений символа в исходное сообщение (статистическая вероятность).2.В списке выбираются два свободных узла с наименьшими весами 3.Создается их узел-«родитель» с весом, равным сумме их весов, он соединяется с «детьми» дугами.4.Одной дуге, выходящей из «родителя», ставится в соответствие бит 1, другой — бит 0.5.«Родитель» добавляется в список свободных узлов, а двое его «детей» удаляются из этого списка.6.Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Код Хаффмана: В нашем случае непосредственно код текста будет занимать 39 бит, или 5 байт. Коэффициент сжатия равен 18/5 = 3, 6.

0 – 00, к – 01, л – 10, пробел – 110, а – 111

Код Хаффмана является префиксным. Это означает, что код каждого символа не является началом кода ка­кого-либо другого символа Код ReaD: представляет собой построчную схему кодирования на основе выбора относительного адреса элемента. Позиции каждого меняющегося элемента строки кодируется с учетом либо позиции соответствующего меняющегося элемента опорной строки, расположенной над кодируемой строкой, либо предыдущего меняющегося элемента текущей строки. После того как строка закодирована, ее используют в качестве опорной для следующей кодируемой строки. Такой способ может привести к размножению ошибок. В случае возникновения ошибки в одной строке декодирование следующей производится относительной искаженной, что приведет к ее неправильному декодированию не только этой но и всех последующих строк. Для предотвращения вертикального распространения искажений с помощью двумерной схемы кодируются не более К-1 последующих строк, после которых строка кодируюетя модифицированным кодом Хаффмена