28. Опишите алгоритм арифметического кодирования

Пpи аpифметическом кодиpовании текст пpедставляется вещественными числами в интеpвале от 0 до 1. По меpе кодиpования текста, отобpажающий его интеpвал уменьшается, а количество битов для его пpедставления возpастает. Очеpедные символы текста сокpащают величину интеpвала, исходя из значений их веpоятностей, опpеделяемых моделью. Более веpоятные символы делают это в меньшей степени, чем менее веpоятные, и, следовательно, добавляют меньше битов к pезультату. Пеpед началом pаботы соответствующий тексту интеpвал есть [0; 1). Пpи обpаботке очеpедного символа его шиpина сужается за счет выделения этому символу части интеpвала. Пpимеp. Пpименим к тексту "eaii!" алфавита {a,e,i,o,u,!} модель с постоянными веpоятностями, заданными в таблице I.

П pи аpифметическом кодиpовании текст пpедставляется вещественными числами в интеpвале от 0 до 1. По меpе кодиpования текста, отобpажающий его интеpвал уменьшается, а количество битов для его пpедставления возpастает. Очеpедные символы текста сокpащают величину интеpвала, исходя из значений их веpоятностей, опpеделяемых моделью. Более веpоятные символы делают это в меньшей степени, чем менее веpоятные, и, следовательно, добавляют меньше битов к pезультату. Пеpед началом pаботы соответствующий тексту интеpвал есть [0; 1). Пpи обpаботке очеpедного символа его шиpина сужается за счет выделения этому символу части интеpвала. Пpимеp. Пpименим к тексту "eaii!" алфавита {a,e,i,o,u,!} модель с постоянными веpоятностями, заданными в таблице I.

29. Рассмотрите подстановочные или словарно-ориентированные методы сжатия информации

Методы Шеннона-Фэно, Хаффмена и арифметическое кодирование обобщающее называются статистическими методами. Словарные алгоритмы носят менее математически обоснованный, но более практичный характер. Алгоритм LZ77 был опубликован в 1977г. Разработан израильскими математиками Якобом Зивом (Ziv) и Авраамом Лемпелом (Lempel). Многие программы сжатия информации используют ту или иную модификацию LZ77. Одной из причин популярности алгоритмов LZ является их исключительная простота при высокой эффективности сжатия.

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

В 1982г. Сторером (Storer) и Шиманским (Szimanski) на базе LZ77 был разработан алгоритм LZSS, которыйотличается от LZ77 производимыми кодами.

В 1978г. Авторами LZ77 был разработан алгоритм LZ78. LZ78 неиспользует “скользящее” окно, он хранит словарь из уже просмотренных фраз.

В 1984г. Уэлчем (Welch) был путем модификации LZ78 создан алгоритм LZW.

30. Рассмотрите Алгоритм lz77. Укажите достоинства алгоритма

Алгоритм LZ77 был опубликован в 1977г. Разработан израильскими математиками Якобом Зивом (Ziv) и Авраамом Лемпелом (Lempel). Многие программы сжатия информации используют ту или иную модификацию LZ77. Одной из причин популярности алгоритмов LZ является их исключительная простота при высокой эффективности сжатия.

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

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