/>
Курсовая работа
Алгоритмы сжатия данных
Содержание
Введение
Общие сведения
Энтропия иколичество информации
Комбинаторная,вероятностная и алгоритмическая оценка количества информации
Моделированиеи кодирование
Некоторыеалгоритмы сжатия данных
Алгоритм LZ77
Алгоритм LZ78-LZW84
Алгоритм PPM
BWT — преобразование и компрессор
КодированиеХаффмана
Арифметическоекодирование
Алгоритмарифметического кодирования
Реализацияалгоритма арифметического кодирования
Реализациямодели
Доказательствоправильности декодирования
Приращаемаяпередача и получение
Отрицательноепереполнение
Переполнение изавершение
Адаптивнаямодель для арифметического кодирования
Эффективностьсжатия
Заключение
Список литературы
Приложение 1.Программный код
Приложение 2.Интерфейс программы
/>/>Введение
Основоположником науки о сжатииинформации принято считать Клода Шеннона. Его теорема об оптимальномкодировании показывает, к чему нужно стремиться при кодировании информации и насколько та или иная информация при этом сожмется. Кроме того, им были проведеныопыты по эмпирической оценке избыточности английского текста. Он предлагаллюдям угадывать следующую букву и оценивал вероятность правильного угадывания.На основе ряда опытов он пришел к выводу, что количество информации ванглийском тексте колеблется в пределах 0.6 — 1.3 бита на символ. Несмотря нато, что результаты исследований Шеннона были по-настоящему востребованы лишьдесятилетия спустя, трудно переоценить их значение.
Первые алгоритмы сжатия былипримитивными в связи с тем, что была примитивной вычислительная техника. Сразвитием мощностей компьютеров стали возможными все более мощные алгоритмы.Настоящим прорывом было изобретение Лемпелем и Зивом в 1977 г. словарных алгоритмов. До этого момента сжатие сводилось к примитивному кодированию символов.Словарные алгоритмы позволяли кодировать повторяющиеся строки символов, чтопозволило резко повысить степень сжатия. Важную роль сыграло изобретениепримерно в это же время арифметического кодирования, позволившего воплотить вжизнь идею Шеннона об оптимальном кодировании. Следующим прорывом былоизобретение в 1984 г. алгоритма РРМ. Следует отметить, что это изобретениедолго оставалось незамеченным. Дело в том, что алгоритм сложен и требуетбольших ресурсов, в первую очередь больших объемов памяти, что было серьезнойпроблемой в то время. Изобретенный в том же 1984 г. алгоритм LZW был чрезвычайно популярен благодарясвоей простоте, хорошей рекламе и нетребовательности к ресурсам, несмотря наотносительно низкую степень сжатия. На сегодняшний день алгоритм РРМ являетсянаилучшим алгоритмом для сжатия текстовой информации, a LZW давно уже не встраивается в новые приложения (однакошироко используется в старых).
Будущее алгоритмов сжатия тесносвязано с будущим компьютерных технологий. Современные алгоритмы уже вплотнуюприблизились к Шенноновской оценке 1.3 бита на символ, но ученые не видятпричин, по которым компьютер не может предсказывать лучше, чем человек. Длядостижения высоких степеней сжатия приходится использовать более сложныеалгоритмы. Однако существовавшее одно время предубеждение, что сложные алгоритмыс более высокой степенью сжатия всегда более медленны, несостоятельно. Так,существуют крайне быстрые реализации алгоритмов РРМ для текстовой информации и SPIHT для графики, имеющие очень высокуюстепень сжатия.
Таким образом, будущее за новымиалгоритмами с высокими требованиями к ресурсам и все более и более высокойстепенью сжатия.
Устареваютне только алгоритмы, но и типы информации, на которые они ориентированы. Так,на смену графике с малым числом цветов и неформатированному тексту пришливысококачественные изображения и электронные документы в различных форматах.Известные алгоритмы не всегда эффективны на новых типах данных. Это делаеткрайне актуальной проблему синтеза новых алгоритмов.
Количество нужной человеку информациинеуклонно растет. Объемы устройств для хранения данных и пропускная способностьлиний связи также растут. Однако количество информации растет быстрее. У этойпроблемы есть три решения. Первое — ограничение количества информации. Ксожалению, оно не всегда приемлемо. Например, для изображений это означаетуменьшение разрешения, что приведет к потере мелких деталей и может сделатьизображения вообще бесполезными (например, для медицинских или космическихизображений). Второе — увеличение объема носителей информации и пропускнойспособности каналов связи. Это решение связано с материальными затратами,причем иногда весьма значительными. Третье решение — использование сжатияинформации. Это решение позволяет в несколько раз сократить требования к объемуустройств хранения данных и пропускной способности каналов связи бездополнительных издержек (за исключением издержек на реализацию алгоритмовсжатия). Условиями его применимости является избыточность информации ивозможность установки специального программного обеспечения либо аппаратурыкак вблизи источника, так и вблизи приемника информации. Как правило, оба этиусловия удовлетворяются.
Именно благодаря необходимостииспользования сжатия информации методы сжатия достаточно широко распространены.Однако существуют две серьезные проблемы. Во-первых, широко используемые методысжатия, как правило, устарели и не обеспечивают достаточной степени сжатия. Вто же время они встроены в большое количество программных продуктов и библиотеки поэтому будут использоваться еще достаточно долгое время. Второй проблемойявляется частое применение методов сжатия, не соответствующих характеру данных.Например, для сжатия графики широко используется алгоритм LZW, ориентированный на сжатие одномернойинформации, например текста. Решение этих проблем позволяет резко повыситьэффективность применения алгоритмов сжатия.
Такимобразом, разработка и внедрение новых алгоритмов сжатия, а также правильноеиспользование существующих позволит значительно сократить издержки нааппаратное обеспечение вычислительных систем.
Приреализации алгоритма арифметического кодирования использовался язык C# и визуальная среда программированияMicrosoft Visual Studio 2005. Язык C# имеет следующие преимущества: простота, объектная ориентированность,типовая защищенность, “сборка мусора”, поддержка совместимости версий,упрощение отладки программ.
/>/>Общие сведения
/>/>Энтропия и количество информации
Подэнтропией в теории информации понимают меру неопределенности (например, мерунеопределенности состояния некоторого объекта). Для того чтобы снять этунеопределенность, необходимо сообщить некоторое количество информации. При этомэнтропия численно равна минимальному количеству информации, которую необходимосообщить для полного снятия неопределенности. Энтропия также может бытьиспользована в качестве оценки наилучшей возможной степени сжатия длянекоторого потока событий.
Здесьи далее понятие события используется как наиболее общее понятие сущности,которую необходимо сжать. Так, при сжатии потока символов под событием можетпониматься появление во входном потоке того или иного символа, при сжатииграфики — пикселя того или иного цвета и т.д.
/>/>Комбинаторная, вероятностная и алгоритмическая оценка />/>количества информации
Наиболеепростым способом оценки количества информации является комбинаторный подход.Согласно этому подходу, если переменная х может принадлежать к множеству из N элементов,то энтропия переменного
H(x) = log2 N.
Такимобразом, для передачи состояния объекта достаточно I=log2N бит информации. Заметим, что количество информации может бытьдробным. Разумеется, дробное количество информации невозможно сохранить наносителе или передать по каналам связи. В то же время, если необходимо передатьлибо сохранить большое количество блоков информации дробной длины, их всегдаможно сгруппировать таким образом, чтобы полностью исключить потери (например,посредством арифметического кодирования).
Основнымнедостатком комбинаторного подхода является его ориентированность на системы сравновероятными состояниями. В реальном мире события, как правило, неравновероятны. Вероятностный подход к оценке количества информации, учитывающийэтот фактор, является наиболее широко используемым на сегодняшний день. Пустьпеременная х может принимать N значений хi с вероятностью р(хi). Тогда энтропия N
/>
Обозначимчерез р(у|х) условную вероятность того, что наступит событие у если событие хуже наступило. В таком случае условная энтропия для переменной Y, которая может принимать М значений yi с условными вероятностями р(уi|х) будет
/>
Приведенныеформулы показывают, что вне зависимости от того, как были получены вероятностинаступления следующих событий, для кодирования события с вероятностью рдостаточно — log2 p бит (в полном соответствии с теоремой Шеннона об оптимальномкодировании).
Алгоритмическийподход применим в тех случаях, когда данные обладают некоторымизакономерностями. Согласно этому подходу, если данные можно описать посредствомнекоторых формул либо порождающих алгоритмов, энтропия данных будет равнаминимальному количеству информации, необходимой для передачи этих формул либоалгоритмов от источника информации к приемнику. Алгоритмический подходиспользуется самостоятельно или совместно с вероятностным, например, в некоторыхалгоритмах сжатия графической информации.
/>/>Моделирование и кодирование
Энтропиянабора данных, а значит и максимально возможная степень сжатия, зависит отмодели. Чем адекватнее модель (чем качественнее мы можем предсказатьраспределение вероятности значений следующего элемента), тем ниже энтропия итем лучше максимально достижимая степень сжатия. Таким образом, сжатие данныхразбивается на две самостоятельные задачи — моделирование и кодирование.
Моделированиеобеспечивает предсказание вероятности наступления возможных событий,кодирование обеспечивает представление события в виде -log2 p бит, где р — предсказанная вероятность наступления события. Задача моделирования, какправило, более сложная. Это обусловлено высокой сложностью современных моделейданных. В то же время кодирование не является серьезной проблемой. Существуетбольшое количество стандартных кодеров, различающихся по степени сжатия ибыстродействию. Как правило, в системах сжатия используемый кодер принеобходимости может быть легко заменен другим.
/>/>Некоторые алгоритмы сжатия данных
/>/>Алгоритм LZ77
Этотсловарный алгоритм сжатия является самым старым среди методов LZ. Описание было опубликовано в 1977 г., но сам алгоритм разработан не позднее 1975 г.
АлгоритмLZ77 является родоначальником целогосемейства словарных схем — так называемых алгоритмов со скользящим словарем, илискользящим окном. Действительно, в LZ77 в качестве словаря используется блок уже закодированнойпоследовательности. Как правило, по мере выполнения обработки положение этогоблока относительно начала последовательности постоянно меняется, словарь«скользит» по входному потоку данных.
Скользящееокно имеет длину N, т. е. в него помещается N символов, исостоит из двух частей:
■последовательности длины W=N-n уже закодированных символов, которая и является словарем;
■упреждающего буфера, или буфера предварительного просмотра, длины n; обычно и на порядки меньше W.
Пустьк текущему моменту времени мы уже закодировали t символов S1, S2, ...,St. Тогда словарембудут являться W предшествующих символов St-(W-1), St-(W-1)+1, …, St. Соответственно, в буфере находятся ожидающие кодированиясимволы St+1, St+2, …, St+n. Очевидно, что если W≥t, то словарем будет являться вся уже обработанная часть входнойпоследовательности.
Идеяалгоритма заключается в поиске самого длинного совпадения между строкой буфера,начинающейся с символа St+1, и всеми фразамисловаря. Эти фразы могут начинаться с любого символа St-(W-1), St-(W-1)+1,…, St выходить за пределы словаря, вторгаясь в область буфера, нодолжны лежать в окне. Следовательно, фразы не могут начинаться с St+1. поэтому буфер не может сравниватьсясам с собой. Длина совпадения не должна превышать размера буфера. Полученная врезультате поиска фраза St-(i-1), St-(i-1)+1, …, St-(i-1)+(j-1) кодируется с помощью двух чисел:
1)смещения (offset) от начала буфера, i;
2)длины соответствия, или совпадения (match length), j;
Смещениеи длина соответствия играют роль указателя (ссылки), однозначно определяющегофразу. Дополнительно в выходной поток записывается символ s, непосредственно следующий за совпавшей строкой буфера.
Такимобразом, на каждом шаге кодер выдает описание трех объектов: смещения и длинысоответствия, образующих код фразы, равной обработанной строке буфера, и одногосимвола s (литерала). Затем окно смещается на j+1 символов вправо и осуществляетсяпереход к новому циклу кодирования. Величина сдвига объясняется тем, что мыреально закодировали именно j+1символов: j с помощью указателя на фразу всловаре и 1(? i) с помощью тривиального копирования.Передача одного символа в явном виде позволяет разрешить проблему обработки ещени разу не виденных символов, но существенно увеличивает размер сжатого блока.
/>/>Алгоритм LZ78-LZW84
АлгоритмLZ78, предложенный в 1978 г. Лемпелом и Зивом, нашел свое практическое применение только после реализации LZW84, предложенной Велчем в 1984 г.
Словарьявляется расширяющимся (expanding). Первоначально в нем содержитсятолько 256 строк длиной в одну букву-все коды ASCII. В процессе работы словарь разрастается до своегомаксимального объема |Vmax| строк (слов). Обычно, объем словаря достигает несколькихдесятков тысяч слов. Каждая строка в словаре имеет свою известную длину и этимпохожа на привычные нам книжные словари и отличается от строк LZ77, которые допускали использованиеподстрок. Таким образом, количество слов в словаре точно равно его текущемуобъему. В процессе работы словарь пополняется по следующему закону:
1.В словаре ищется слово str, максимально совпадающее с текущимкодируемым словом в позиции pos исходноготекста. Так как словарь первоначально не пустой, такое слово всегда найдется;
2.В выходной файл помещается номер найденного слова в словаре position и следующий символ из входного текстаВ (на котором обнаружилось различие) — . Длинакода равна |position|+|B||=[logVmax]+8(бит);
3.Если словарь еще не полон, новая строка strВ добавляется в словарь по адресу last_position, размер словаря возрастает на одну позицию;
4.Указатель в исходном тексте pos смещаетсяна |strB|=|str|+l байтдальше к символу, следующему за В.
Втаком варианте алгоритм почти не нашел практического применения и былзначительно модернизирован. Изменения коснулись принципов управления словарем(его расширения и обновления) и способа формирования выходного кода:
Птаккак словарь увеличивается постепенно и одинаково для кодировщика идекодировщика, для кодирования позиции нет необходимости использовать [logVmax] бит, а можно брать лишь [logV] бит, где V-текущийобъем словаря.
Самаясерьезная проблема LZ78-переполнениесловаря: если словарь полностью заполнен, прекращается его обновление и процесссжатия может быть заметно ухудшен (метод FREEZE). Отсюда следует вывод-словарь нужно иногда обновлять. Самый простой способкак только словарь заполнился его полностью обновляют. Недостаток очевиденкодирование начинается на пустом месте, как бы с начала, и пока словарь ненакопится сжатие будет незначительным, а дальше-замкнутый цикл опять очисткасловаря!.. Поэтому предлагается словарь обновлять не сразу после егозаполнения, а только после того, как степень сжатия начала падать (метод FLUSH). Более сложные алгоритмы используют два словаря,которые заполняются синхронно, но с задержкой на |V|/2 слов один относительно другого. После заполнения одногословаря, он очищается, а работа переключается на другой (метод SWAP). Еще более сложными являются эвристические методыобновления словарей в зависимости от частоты использования тех или иных слов (LRU, TAG).
Выходнойкод также формируется несколько иначе (сравните с предыдущим описанием):
1.В словаре ищется слово str, максимально совпадающее с текущимкодируемым словом в позицииpos исходноготекста;
2.В выходной файл помещается номер найденного слова в словаре . Длина кода равна |position|=[logV] (бит);
3.Если словарь еще не полон, новая строка strВ добавляется в словарь по адресу last_position, размер словаря возрастает на одну позицию;
4.Указатель в исходном тексте pos смещаетсяна |str| байт дальше к символу В.
/>/>Алгоритм PPM
АлгоритмPPM (prediction by partial matching) — это методконтекстно-ограниченного моделирования, позволяющий оценить вероятность символав зависимости от предыдущих символов. Строку символов, непосредственнопредшествующую текущему символу, будем называть контекстом. Модели, в которыхдля оценки вероятности используются контексты длиной не более чем N, принято называть моделями порядкаN.
Вероятностьсимвола может быть оценена в контекстах разных порядков. Например, символ«о» в контексте «to be or not t» может быть оценен в контексте первого порядка «t», в контексте второго порядка «_t», в контексте третьего порядка «t_t» и т.д. Он также может быть оценен в контексте нулевогопорядка, где вероятности символов не зависят от контекста, и в контексте минуспервого порядка, где все символы равновероятны. Контекст минус первого порядкаиспользуется для того, чтобы исключить ситуацию, когда символ будет иметьнулевую вероятность и не сможет быть закодирован. Это может случиться, есливероятность символа не будет оценена ни в одном из контекстов (что возможно,если символ в них ранее не встречался).
Существуютдва основных подхода к вычислению распределения вероятностей следующего символана основе вероятностей символов в контекстах. Первый подход называется «полноеперемешивание». Он предполагает назначение весов контекстам разных порядков иполучение суммарных вероятностей сложением вероятностей символов в контекстах,умноженных на веса этих контекстов. Применение такого подхода ограничено двумяфакторами. Во-первых, не существует быстрой реализации данного алгоритма.Во-вторых, не разработан эффективный алгоритм вычисления весов контекстов.Примитивные же подходы не обеспечивают достаточно высокой точности оценки и,как следствие, степени сжатия.
Второйподход называется «методом исключений». При этом подходе сначала делаетсяпопытка оценить символ в контексте самого высокого порядка. Если символкодируется, алгоритм переходит к кодированию следующего символа. В противномслучае кодируется «уход» и предпринимается попытка закодировать символ вконтексте меньшего порядка. И так далее, пока символ не будет закодирован.
/>/>BWT — преобразование и компрессор
BWT-компрессор(Преобразование Барроуза – Уиллера) — сравнительно новая и революционная техника для сжатияинформации (в особенности-текстов), основанная на преобразовании, открытом в 1983 г. и описанная в 1994 г… BWT является удивительным алгоритмом.Во-первых, необычно само преобразование, открытое в научной области, далекой отархиваторов. Во-вторых, даже зная BWT, не совсем ясно, как его применить к сжатиюинформации. В-третьих, BWпреобразование чрезвычайно просто. И, наконец, сам BWT компрессор состоит из «магической»последовательности нескольких рассмотренных ранее алгоритмов и требует,поэтому, для своей реализации самых разнообразных программных навыков.
BWT несжимает данные, но преобразует блок данных в формат, исключительно подходящийдля компрессии. Рассмотрим его работу на упрощенном примере. Пусть имеетсясловарь V из N символов. Циклическипереставляя символы в словаре влево, можно получить N различных строк длиной Nкаждая. В нашем примере словарь-это слово V=«БАРАБАН» и N=7. Отсортируем эти строкилексикографически и запишем одну под другой:
F L
АБАНБАР
АНБАРАБ
АРАБАНБ
БАНБАРА
БАРАБАН
НБАРАБА
РАБАНБА
Далеенас будут интересовать только первый столбец F и последний столбец L. Оба они содержат все те же символы, что и исходная строка(словарь). Причем, в столбце F ониотсортированы, а каждый символ из L является префиксом для соответствующего символа из F.
Фактический«выход» преобразования состоит из строки L=«РББАНАА» и первичного индекса I, показывающего, какой символ из L является действительным первымсимволом словаря V (в нашем случае I=2). Зная L и Iможно восстановить строку V.
/>/>Кодирование Хаффмана
Этоталгоритм кодирования информации был предложен Д.А. Хаффманом в 1952 году. Идеяалгоритма состоит в следующем: зная вероятности вхождения символов в сообщение,можно описать процедуру построения кодов переменной длины, состоящих из целогоколичества битов. Символам с большей вероятностью присваиваются более короткиекоды. Коды Хаффмана имеют уникальный префикс, что и позволяет однозначно ихдекодировать, несмотря на их переменную длину.
Классическийалгоритм Хаффмана на входе получает таблицу частот встречаемости символов всообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана(Н-дерево). Алгоритм построения Н-дерева прост и элегантен.
1.Символы входного алфавита образуют список свободных узлов. Каждый лист имеетвес, который может быть равен либо вероятности, либо количеству вхожденийсимвола в сжимаемое сообщение.
2.Выбираются два свободных узла дерева с наименьшими весами.
3.Создается их родитель с весом, равным их суммарному весу.
4.Родитель добавляется в список свободных узлов, а двое его детей удаляются изэтого списка.
5.Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит0.
6.Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узловне останется только один свободный узел. Он и будет считаться корнем дерева.
Допустим,у нас есть следующая таблица частот:15 7 6 6 5 А Б В Г Д
Напервом шаге из листьев дерева выбираются два с наименьшими весами — Г и Д. Ониприсоединяются к новому узлу-родителю, вес которого устанавливается в 5+6 = 11.Затем узлы Г и Д удаляются из списка свободных. Узел Г соответствует ветви 0родителя, узел Д — ветви 1.
Наследующем шаге то же происходит с узлами Б и В, так как теперь эта пара имеетсамый меньший вес в дереве. Создается новый узел с весом 13, а узлы Б и Вудаляются из списка свободных. После всего этого дерево кодирования выглядиттак, как показано на рис. 2.
/>
Рис.2. Дерево кодирования Хаффмана после второго шага
Наследующем шаге «наилегчайшей» парой оказываются узлы Б/В и Г/Д. Для них еще разсоздается родитель, теперь уже с весом 24. Узел Б/В соответствует ветви 0родителя, Г/Д—ветви 1.
Напоследнем шаге в списке свободных осталось только два узла — это А и узел(Б/В)/(Г/Д). В очередной раз создается родитель с весом 39 и бывшие свободнымиузлы присоединяются к разным его ветвям.
Посколькусвободным остался только один узел, то алгоритм построения дерева кодирования Хаффманазавершается. Н-дерево представлено на рис. 3.
/>
Рис.3. Окончательное дерево кодирования Хаффмана
Чтобыопределить код для каждого из символов, входящих в сообщение, мы должны пройтипуть от листа дерева, соответствующего этому символу, до корня дерева,накапливая биты при перемещении по ветвям дерева. Полученная таким образомпоследовательность битов является кодом данного символа, записанным в обратномпорядке.
Дняданной таблицы символов коды Хаффмана будут выглядеть следующим образом.
А 0
Б 100
В 101
Г 110
Д 111
Посколькуни один из полученных кодов не является префиксом другого, они могут бытьоднозначно декодированы при чтений их из потока. Кроме того, наиболее частыйсимвол сообщения А закодирован наименьшим количеством битов, а наиболее редкийсимвол Д — наибольшим.
Классическийалгоритм Хаффмана имеет один существенный недостаток. Дня восстановления содержимогосжатого сообщения декодер должен знать таблицу частот, которой пользовалсякодер. Следовательно, длина сжатого сообщения увеличивается на длину таблицычастот, которая должна посылаться впереди данных, что может свести на нет всеусилия по сжатию сообщения. Кроме того, необходимость наличия полной частотнойстатистики перед началом собственно кодирования требует двух проходов посообщению: одного для построения модели сообщения (таблицы частот и Н-дерева),другого для собственно кодирования.
/>/>Арифметическое кодирование
/>/>Алгоритм арифметического кодирования
Арифметическоесжатие — достаточно изящный метод, в основе которого лежит очень простая идея.Мы представляем кодируемый текст в виде дроби, при этом строим дробь такимобразом, чтобы наш текст был представлен как можно компактнее. Для примерарассмотрим построение такой дроби на интервале [0, 1) (0 — включается, 1 — нет). Интервал [0, 1) выбран потому, что он удобен для объяснений. Мы разбиваемего на подынтервалы с длинами, равными вероятностям появления символов впотоке. В дальнейшем будем называть их диапазонами соответствующих символов.
Пустьмы сжимаем текст «КОВ.КОРОВА» (что, очевидно, означает «коварнаякорова»). Распишем вероятности появления каждого символа в тексте (впорядке убывания) и соответствующие этим символам диапазоны:Символ Частота Вероятность Диапазон О 3 0.3 [0.0; 0.3) К 2 0.2 [0.3; 0.5) В 2 0.2 [0.5; 0.7) Р 1 0.1 [0.7; 0.8) А 1 0.1 [0.8; 0.9) “.” 1 0.1 [0.9; 1.0)
Будемсчитать, что эта таблица известна в компрессоре и декомпрессоре. Кодированиезаключается в уменьшении рабочего интервала. Для первого символа в качестверабочего интервала берется [0, 1). Мы разбиваем его на диапазоны в соответствиис заданными частотами символов (см. таблицу диапазонов). В качестве следующегорабочего интервала берется диапазон, соответствующий текущему кодируемомусимволу. Его длина пропорциональна вероятности появления этого символа впотоке. Далее считываем следующий символ. В качестве исходного берем рабочийинтервал, полученный на предыдущем шаге, и опять разбиваем его в соответствии стаблицей диапазонов. Длина рабочего интервала уменьшается пропорциональновероятности текущего символа, а точка начала сдвигается вправо пропорциональноначалу диапазона для этого символа. Новый построенный диапазон берется вкачестве рабочего и т. д.
Используяисходную таблицу диапазонов, кодируем текст «КОВ.КОРОВА»:
Исходныйрабочий интервал [0,1).
Символ«К» [0.3; 0.5) получаем [0.3000; 0.5000).
Символ«О» [0.0; 0.3) получаем [0.3000; 0.3600).
Символ«В» [0.5; 0.7) получаем [0.3300; 0.3420).
Символ"." [0.9; 1.0) получаем [0,3408; 0.3420).
Графическийпроцесс кодирования первых трех символов можно представить так, как на рис. 4.
/>
Рис.4. Графический процесс кодирования первых трех символов
Такимобразом, окончательная длина интервала равна произведению вероятностей всехвстретившихся символов, а его начало зависит от порядка следования символов впотоке. Можно обозначить диапазон символа с как [а[с]; b[с]), аинтервал для i-го кодируемого символа потока как [li, hi).
Большойвертикальной чертой на рисунке выше обозначено произвольное число, лежащее вполученном при работе интервале [/i, hi). Для последовательности«КОВ.», состоящей из четырех символов, за такое число можно взять0.341. Этого числа достаточно для восстановления исходной цепочки, еслиизвестна исходная таблица диапазонов и длина цепочки.
Рассмотримработу алгоритма восстановления цепочки. Каждый следующий интервал вложен впредыдущий. Это означает, что если есть число 0.341, то первым символом вцепочке может быть только «К», поскольку только его диапазон включаетэто число. В качестве интервала берется диапазон «К» — [0.3; 0.5) и внем находится диапазон [а[с]; b[с]),включающий 0.341.Перебором всех возможных символов по приведенной выше таблице находим, чтотолько интервал [0.3; 0.36), соответствующий диапазону для «О»,включает число 0.341. Этот интервал выбирается в качестве следующего рабочего ит. д.
/>/>Реализация алгоритма арифметического кодирования
Нижепоказан фрагмент псевдокода процедур кодирования и декодирования. Символы в немнумеруются как 1,2,3… Частотный интервал для i-го символа задается отcum_freq[i] до cum_freq[i-1]. Пpи убывании i cum_freq[i] возрастает так, чтоcum_freq[0] = 1. (Причина такого «обpатного» соглашения состоит втом, что cum_freq[0] будет потом содеpжать ноpмализующий множитель, котоpыйудобно хpанить в начале массива). Текущий pабочий интеpвал задается в [low;high] и будет в самом начале pавен [0; 1) и для кодиpовщика, и дляpаскодиpовщика.
Алгоритмкодирования:
Скаждым символом текста обpащаться к пpоцедуpе encode_symbol(). Пpовеpить, что«завеpшающий» символ закодиpован последним. Вывести полученноезначение интеpвала [low; high).
encode_symbol(symbol, cum_freq)
{
…
range = high — low
high = low + range*cum_freq[symbol-1]
low = low + range*cum_freq[symbol]
…
}
Алгоритм декодирования:
Value- это поступившее на вход число. Обpащение к пpоцедуpе decode_symbol() пока онане возвpатит «завеpшающий» символ.
decode_symbol(cum_freq)
//поисктакого символа, что
cum_freq[symbol]
Этообеспечивает pазмещение value внутpи нового интеpвала [low;high), что отpаженов оставшейся части пpогpаммы:
range = high — low
high = low + range*cum_freq[symbol-1]
low = low + range*cum_freq[symbol]
returnsymbol
Реализация алгоритма на C# приведена в Приложении.
/>/>Реализация модели
Вязыке Си байт представляет собой целое число от 0 до 255 (тип char). Здесь жемы пpедставляем байт как целое число от 1 до 257 включительно (тип index), гдеEOF тpактуется как 257-ой символ. Пеpевод из типа char в index, и наобоpот,pеализуется с помощью двух таблиц — index_to_char[] и char_to_index[].
Веpоятностипpедставляются в модели как целочисленные счетчики частот, а накапливаемыечастоты хpанятся в массиве cum_freq[]. Этот массив — «обpатный», исчетчик общей частоты, пpименяемый для ноpмализации всех частот, pазмещается вcum_freq[0]. Накапливаемые частоты не должны превышать установленный в max_frequency максимум, а реализациямодели должна предотвращать переполнение соответствующим масштабированием.Hеобходимо также хотя бы на 1 обеспечить pазличие между двумя соседнимизначениями cum_freq[], иначе pассматpиваемый символ не сможет быть пеpедан.
/>/>Доказательство правильности декодирования
Пpовеpимвеpность определения пpоцедуpой decode_symbol() следующего символа. Изпсевдокода видно, что decode_symbol() должна использовать value для поискасимвола, сокpатившего пpи кодиpовании pабочий интеpвал так, что он пpодолжаетвключать в себя value. Стpоки range = (long) (high — low) + 1; иcum=(int)((((long)(value-low)+1)*cum_freq[0]-1)/ range); в decode_symbol() опpеделяюттакой символ, для котоpого
/>
где"| |" обозначает опеpацию взятия целой части — деление сотбpасыванием дpобной части.
Другимисловами:
/> (1)
гдеrange = high — low + 1, />.
Последнеенеравенство выражения (1) происходит из факта, что cum_freq[symbol-1] должнобыть целым. Затем мы хотим показать, что low'≤value≤high', где low'и high' есть обновленные значения для low и high как опpеделено ниже.
/>
Извыружения (1) имеем: ≤value+ 1 – 1/cum_freq[0], поэтому low'≤value, т.к. и value, и low',и cum_freq[0] > 0.
/>
Извыражения (1) имеем:
/>
/>/>Приращаемая передача и получение
Вотличие от псеводокода, программа представляет low и high целыми числами. Впсевдокоде текущий интеpвал пpедставлен чеpез [low; high), а в пpогpамме это[low; high] — интеpвал, включающий в себя значение high. Hа самом деле болеепpавильно, хотя и более непонятно, утвеpждать, что в пpогpамме пpедставляемыйинтеpвал есть [low; high + 0.1111...) по той пpичине, что пpи масштабитованиигpаниц для увеличения точности, нули смещаются к младшим битам low, а единицысмещаются в high.
Помеpе сужения кодового интеpвала, стаpшие биты low и high становятсяодинаковыми, и поэтому могут быть пеpеданы немедленно, т.к. на них будущиесужения интеpвала все pавно уже не будут влиять. Поскольку мы знаем, что low≤high,это воплотится в следующую пpогpамму:
for (;;)
{
if (high
{
output_bit(0);
low = 2 * low;
high = 2 * high + 1;
}
else if (low >= Half)
{
output_bit(1);
low = 2 * (low — Half);
high = 2 * (high — Half) + 1;
}
else break;
}
гаpантиpующую, что после ее завеpшения будет спpеведливонеpавенство: low
Пpиpащаемыйввод исходных данных выполняется с помощью числа, названного value. В пpогpамме,обpаботанные биты пеpемещаются в веpхнюю часть, а заново получаемые поступают внижнюю. Вначале, start_decoding() заполняет value полученными битами. Послеопpеделения следующего входного символа пpоцедуpой decode_symbol(), пpоисходитвынос ненужных, одинаковых в low и в high, битов стаpшего поpядка сдвигом valueна это количество pазpядов (выведенные биты восполняются введением новых снижнего конца).
for (;;)
{
if (high
{
value = 2 * value + input_bit();
low = 2 * low;
high = 2 * high + 1;
}
else if (low > Half)
{
value = 2 * (value — Half) + input_bit();
low = 2 * (low — Half);
high = 2 * (high — Half) + 1;
}
else break;
}
/>/>Отрицательное переполнение
Какпоказано в псевдокоде, арифметическое кодирование работает при помощи масштабированиянакопленных вероятностей, поставляемых моделью в интервале [low; high] длякаждого передаваемого символа. Пpедположим, что low и high настолько близкидpуг к дpугу, что опеpация масштабиpования пpиводит полученные от модели pазныесимволы к одному целому числу, входящему в [low; high]. В этом случаедальнейшее кодиpование пpодолжать невозможно. Следовательно, кодиpовщик долженследить за тем, чтобы интеpвал [low; high] всегда был достаточно шиpок. Пpостейшимспособом для этого является обеспечение шиpины интеpвала не меньшей max_frequency — максимального значениясуммы всех накапливаемых частот.
Какможно сделать это условие менее стpогим? Объясненная выше опеpация битовогосдвига гаpантиpует, что low и high могут только тогда становиться опасноблизкими, когда заключают между собой half. Пpедположим, они становятся настолько близки, что
first_qtr ≤low
Тогдаследующие два бита вывода будут иметь взаимообpатные значения: 01 или 10. Hапpимеp,если следующий бит будет нулем (т.е. high опускается ниже half и [0; half] становится pабочим интеpвалом), а следующий за ним — единицей, т.к. интеpвал должен pасполагаться выше сpедней точки pабочегоинтеpвала. Hаобоpот, если следующий бит оказался 1, то за ним будет следовать0. Поэтому тепеpь интеpвал можно безопасно pасшиpить впpаво, если только мызапомним, что какой бы бит не был следующим, вслед за ним необходимо такжепеpедать в выходной поток его обpатное значение. Т.о. происходит преобразование[first_qtr; third_qtr] в целый интеpвал, запоминая в bits_to_followзначение бита, за котоpым надо посылать обpатный ему. Это объясняет, почемувесь вывод совеpшается чеpез пpоцедуpу bit_plus_follow(), а не непосpедственночеpез output_bit().
Hочто делать, если после этой опеpации соотношение (*) остается спpаведливым? Представимтакой случай, когда pабочий интеpвал [low; high] pасшиpяется 3 pаза подpяд.Пусть очеpедной бит ниже сpедней точки пеpвоначального интеpвала, оказалсянулем. Тогда следующие 3 бита будут единицами, поскольку мы находимя не пpостово втоpой его четвеpти, а в веpхней четвеpти, даже в веpхней восьмой частинижней половины пеpвоначельного интеpвала — вот почему pасшиpение можнопpоизвести 3 pаза. Тоже самое для случая, когда очеpедной бит оказалсяединицей, и за ним будут следовать нули. Значит в общем случае необходимосначала сосчитать количество pасшиpений, а затем вслед за очеpедным битомпослать в выходной поток найденное количество обpатных ему битов.
Следуяэтим pекомендациям, кодиpовщик гаpантиpует, что после опеpаций сдвига будет или
low
или
low
Значит,пока целочисленный интеpвал, охватываемый накопленными частотами, помещается вее четвеpть, пpедставленную в code_value, пpоблема отpицательного пеpеполненияне возникнет. Это соответствует условию:
max_frequency≤(top_value + 1)/4 + 1,
котоpоеудовлетвоpяет пpогpамме, т.к. max_frequency= 214 — 1 и top_value= 216 — 1.
Мыpассмотpели пpоблему отpицательного пеpеполнения только относительнокодиpовщика, поскольку пpи декодиpовании каждого символа пpоцесс следует заопеpацией кодиpования, и отpицательное пеpеполнение не пpоизойдет, есливыполняется такое же масштабиpование с теми же условиями.
/>/>Переполнение и завершение
Теперьрассмотрим возможность переполнения при целочисленном умножении. Переполненияне произойдет, если произведение range*max_frequency вмещается в целое слово, т.к. накопленныечастоты не могут превышать max_frequency.range имеет наибольшее значение в top_value + 1, поэтому максимальновозможное произведение в программе есть 216*(214 — 1),которое меньше 230.
Призавершении процесса кодирования необходимо послать уникальный завершающийсимвол (EOF-символ), а затем послать вслед достаточное количество битов для гарантиитого, что закодированная строка попадет в итоговый рабочий интервал. Т.к.пpоцедуpа done_encoding() может быть увеpена, что low и high огpаничены либовыpажением (1a), либо (1b), ему нужно только пеpедать 01 или 10 соответственно,для удаления оставшейся неопpеделенности. Удобно это делать с помощью пpоцедуpыbit_plus_follow(). Пpоцедуpа input_bit() на самом деле будет читать немногобольше битов, из тех, что вывела output_bit(), потому что ей нужно сохpанятьзаполнение нижнего конца буфеpа. Hеважно, какое значение имеют эти биты,поскольку EOF уникально опpеделяется последними пеpеданными битами.
/>/>Адаптивная модель для арифметического кодирования
Программа должна работатьс моделью, которая предоставляет пару перекодировочныхтаблиц index_to_char[] и char_to_index[], и массивнакопленных частот cum_freq[]. Причем к последнему предъявляютсяследующие требования:
cum_freq[i-1] >= cum_freq[i];
никогдане делается попытка кодиpовать символ i, для котоpого
cum_freq[i-1] = cum_freq[i];
cum_freq[0]
Еслиданные условия соблюдены, значения в массиве не должны иметь связи сдействительными значениями накопленных частот символов текста. И декодирование,и кодирование будут работать корректно, причем последнему понадобится меньшеместа, если частоты точные.
Онаизменяет частоты уже найденных в тексте символов. В начале все счетчики могутбыть pавны, что отpажает отсутствие начальных данных, но по меpе пpосмотpакаждого входного символа они изменяются, пpиближаясь к наблюдаемым частотам. Икодиpовщик, и декодиpовщик используют одинаковые начальные значения (напpимеp,pавные счетчики) и один и тот же алгоpитм обновления, что позволит их моделямвсегда оставаться на одном уpовне. Кодиpовщик получает очеpедной символ,кодиpует его и изменяет модель. Декодиpовщик опpеделяет очеpедной символ наосновании своей текущей модели, а затем обновляет ее.
Приинициализации все частоты устанавливаются в 0. Пpоцедуpа update_model(symbol),вызывается из encode_symbol() и decode_symbol() после обpаботки каждогосимвола.
Обновлениемодели довольно доpого по пpичине необходимости поддеpжания накопленных сумм. Впpогpамме используемые счетчики частот оптимально pазмещены в массиве в поpядкеубывания своих значений, что является эффективным видом самооpганизуемоголинейного поиска. Пpоцедуpа update_model() сначала пpовеpяет новую модель напpедмет пpевышения ею огpаничений по величине накопленной частоты, и если оноимеет место, то уменьшает все частоты делением на 2, заботясь пpи этом, чтобысчетчики не пpевpатились в 0, и пеpевычисляет накопленные значения. Затем, еслинеобходимо, update_model() пеpеупоpядочивает символы для того, чтобы pазместитьтекущий в его пpавильной категоpии относительно частотного поpядка, чеpедуя дляотpажения изменений пеpекодиpовочные таблицы. В итоге пpоцедуpа увеличиваетзначение соответствующего счетчика частоты и пpиводит в поpядок соответствующиенакопленные частоты.
/>/>Эффективность сжатия
Вообще,при кодировании текста арифметическим методом, количество битов в закодированнойстроке равно энтропии этого текста относительно использованной для кодированиямодели. Тpи фактоpа вызывают ухудшение этой хаpактеpистики:
1. pасходы назавеpшение текста;
2. использованиеаpифметики небесконечной точности;
3. такоемасштабиpование счетчиков, что их сумма не пpевышает max_frequency.
Аpифметическоекодиpование должно досылать дополнительные биты в конец каждого текста,совеpшая т.о. дополнительные усилия на завеpшение текста. Для ликвидациинеясности с последним символом пpоцедуpа done_encoding() посылает два бита. Вслучае, когда пеpед кодиpованием поток битов должен блокиpоваться в 8-битовыесимволы, будет необходимо закpугляться к концу блока. Такое комбиниpованиеможет дополнительно потpебовать 9 битов.
Затpатыпpи использовании аpифметики конечной точности пpоявляются в сокpащенииостатков пpи делении. Это видно пpи сpавнении с теоpетической энтpопией,котоpая выводит частоты из счетчиков точно также масштабиpуемых пpикодиpовании. Здесь затpаты незначительны — поpядка 10-4 битов/символ.
Дополнительныезатpаты на масштабиpование счетчиков отчасти больше, но все pавно очень малы.Для коpотких текстов (меньших 214 байт) их нет. Hо даже с текстами в105 — 106 байтов накладные pасходы, подсчитанныеэкспеpиментально, составляют менее 0.25% от кодиpуемой стpоки.
Адаптивнаямодель, пpи угpозе пpевышения общей суммой накопленных частот значение max_frequency, уменьшает все счетчики.Это пpиводит к тому, что взвешивать последние события тяжелее, чем болееpанние. Т.о. показатели имеют тенденцию пpослеживать изменения во входнойпоследовательности, котоpые могут быть очень полезными.
/>/>Заключение
Вданной курсовой работе были рассмотрены вопросы архивации данных различнымиметодами. Подробно описаны алгоритмы сжатия данных по мере появления иразвития.
Вкурсовой работе был реализован алгоритм арифметического кодирования и созданапрограмма «Архиватор» со всеми необходимыми функциями.
Дляреализации использовался язык C# ивизуальная среда программирования Microsoft Visual Studio 2005. Врезультате программное обеспечение очень компактно, интуитивно понятно и эффективнов работе.
/>/>Список литературы
1. Ватолин Д.,Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов,сжатие изображений и видео. — М.: ДИАЛОГ-МИФИ, 2002. — 384 с.
2. Сэломон Д. Сжатиеданных, изображений и звука. Data Compression Methods. Серия: Мирпрограммирования. Издательство: Техносфера, 2004. — 368 с.
3. Артюшенко В. М.,Шелухин О. И., Афонин М. Ю. Цифровое сжатие видеоинформации и звука.Издательство: Дашков и Ко, 2004. — 426 с.
4. Седжвик Р.Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных.Сортировка. Поиск. Издательство: ДиаСофт, 2002. — 688 с.
/>/>Приложение 1. Программный код
//Количество бит для кода
const int bits_in_register = 16;
//Максимально возможное значение кода
const int top_value = (int)(((long)1
// Диапазоны
const int first_qtr = (top_value / 4 + 1);
const int half = (2 * first_qtr);
const int third_qtr = (3 * first_qtr);
//Количество символов алфавита
const int no_of_chars = 256;
//Специальный символ Конец файла
const int eof_symbol = (no_of_chars + 1);
// Всего символов в модели
const int no_of_symbols = (no_of_chars + 1);
//Порог частоты для масштабирования
const int max_frequency = 16383;
// Таблицы перекодировки
public int[] index_to_char = new int[no_of_symbols];
public int[] char_to_index = new int[no_of_chars];
// Таблицы частот
public int[] cum_freq = new int[no_of_symbols + 1];
public int[] freq = new int[no_of_symbols + 1];
// Регистры границ и кода
public static long low, high;
public static long value;
//Поддержка побитовых операций с файлами
public static long bits_to_follow;
// Буфер
public static int buffer;
// Количество бит в буфере
public static int bits_to_go;
//Количество бит после конца файла
public static int garbage_bits;
//Указатель на входной файл
FileStream datain;
//Указатель на выходной файл
FileStream dataout;
//--------------------------------------------------------------
// Инициализация адаптивной модели
public void start_model ()
{
int i;
// Установки таблицперекодировки
for ( i = 0; i
{
char_to_index [i] = i + 1;
index_to_char [i + 1] = i;
}
// Установка счетчиков накопленных частот
for ( i = 0; i
{
freq [i] = 1;
cum_freq[i] = no_of_symbols — i;
}
freq [0] = 0;
}
//------------------------------------------------------------
// Обновление моделиочередным символом
void update_model(int symbol)
{
// Новый индекс
int i;
int ch_i, ch_symbol;
int cum;
//Проверка на переполнение счетчика частоты
if (cum_freq[0] == max_frequency)
{
cum =0;
/*Масштабирование частот при переполнении (если счетчики частот достигли своегомаксимума, то делим на пополам) */
for (i = no_of_symbols; i >= 0; i--)
{
freq[i] = (freq[i] + 1) / 2;
cum_freq[i] = cum;
cum +=freq[i];
}
}
/*Обновление перекодировочных таблиц в случае перемещения символа */
for (i = symbol; freq[i] == freq[i — 1]; i--) ;
if (i
{
ch_i = index_to_char[i];
ch_symbol = index_to_char[symbol];
index_to_char[i] = ch_symbol;
index_to_char[symbol] = ch_i;
char_to_index[ch_i] = symbol;
char_to_index[ch_symbol] = i;
}
//Увеличить значение счетчика частоты для символа
freq[i] += 1;
//Обновление значений в таблицах частот
while (i > 0)
{
i -= 1;
cum_freq[i] += 1;
}
}
//------------------------------------------------------------
// Инициализация побитового ввода
void start_inputing_bits ()
{
bits_to_go = 0;
garbage_bits = 0;
}
//------------------------------------------------------------
//Ввод очередного бита сжатой информации
int input_bit ()
{
int t;
//Чтение байта если буфер пуст
if (bits_to_go == 0)
{
buffer = datain.ReadByte();
if (buffer == -1)
{
/*Помещение битов после конца файла, с проверкой небольшого их количества */
garbage_bits += 1;
if (garbage_bits > bits_in_register — 2)
{
Application.Exit();
}
eof = buffer;
}
bits_to_go = 8;
}
//Выдача очередного бита с правого конца
t = buffer & 1;
buffer >>= 1;
bits_to_go -= 1;
return t;
}
//------------------------------------------------------------
// Инициализация побитового вывода
public void start_outputing_bits ()
{
buffer= 0;
bits_to_go= 8;
}
//------------------------------------------------------------
//Вывод очередного бита сжатой информации
public void output_bit(int bit)
{
//Бит — в начало буфеpа
buffer>>= 1;
if (bit == 1)
buffer |= 0x80;
bits_to_go -= 1;
// Вывод полногобуфера
if (bits_to_go == 0)
{
dataout.WriteByte((byte)buffer);
bits_to_go = 8;
}
}
//------------------------------------------------------------
// Очистка буферапобитового вывода
public void done_outputing_bits ()
{
dataout.WriteByte((byte)(buffer >> bits_to_go));
}
//------------------------------------------------------------
//Вывод указанного бита и отложенных ранее
public void output_bit_plus_follow(int bit)
{
output_bit(bit);
while (bits_to_follow > 0)
{
output_bit(~bit + 2);
bits_to_follow--;
}
}
//------------------------------------------------------------
//Инициализация регистров границ и кода перед началом сжатия
public void start_encoding()
{
//Полный кодовый интервал
low = 0L;
high = top_value;
bits_to_follow = 0L;
}
//------------------------------------------------------------
//Очистка побитового вывода
publicvoid done_encoding ()
{
/*Вывод двух бит, определяющих четверть, лежащую в текущем интервале */
bits_to_follow++;
if (low
output_bit_plus_follow (0);
else
output_bit_plus_follow (1);
}
//------------------------------------------------------------
/*Инициализация регистров перед декодированием.
Загрузканачала сжатого сообщения*/
void start_decoding ()
{
int i;
int a;
value= 0L;
//Воод бит для заполнения значения кода
for (i = 1; i
{
a = input_bit();
value = 2 * value + a;
}
//Текущий интервал равен исходному
low= 0L;
high= top_value;
}
//------------------------------------------------------------
//Кодирование очередного символа
public void encode_symbol(int symbol)
{
//Ширина текущего кодового интервала
long range;
range= (long)(high — low) +1;
//Пересчет значений границ
high = low + (range*cum_freq[symbol — 1]) / cum_freq[0] — 1;
low = low + (range*cum_freq[symbol]) / cum_freq[0];
//Вывод битов
for (;; )
{
//Если в нижней половине
if (high
output_bit_plus_follow(0);
//Если в верхней половине
else if (low >= half)
{
output_bit_plus_follow(1);
low -= half;
high-= half;
}
/*Если текущий интервал содержит середину, то вывод еще одного обратного битапозже */
else if (low >= first_qtr && high
{
bits_to_follow += 1;
low -= first_qtr;
high -= first_qtr;
}
else
break;
//Расширить текущий рабочий кодовый интервал
low= 2 * low;
high= 2 * high + 1;
}
}
//------------------------------------------------------------
//Декодирование очередного символа
intdecode_symbol ()
{
//Ширина интервала
longrange;
//Накопленная частота
int cum;
// Декодируемый символ
int symbol;
int a;
//Определение текущего масштаба частот
range= (long) (high — low) + 1;
//Hахождение значения накопленной частоты для value
cum=(int)((((long)(value-low)+1)*cum_freq[0]-1)/ range);
//Поиск соответствующего символа в таблице частот
for (symbol = 1; cum_freq [symbol] > cum; symbol++);
// Пересчет границ
high = low + (range*cum_freq[symbol — 1]) / cum_freq[0] — 1;
low = low + (range * cum_freq [symbol]) / cum_freq [0];
//Удаление очередного символа из входного потока
for(;;)
{
//Расширение нижней половины
if(high
{
}
//Расширение верхней половины
elseif (low >= half)
{
value -= half;
low -= half;
high -= half;
}
// Расширение середины
else if (low >= first_qtr && high
{
value -= first_qtr;
low -= first_qtr;
high -= first_qtr;
}
else
break;
//Увеличение масштаба интервала
low= 2 * low;
high =2 * high + 1;
//Добавить новый бит
a = input_bit();
value = 2 * value + a;
}
return symbol;
}
//--------------------------------------------------------------
//Собственно адаптивное арифметическое кодирование
public void encode(string infile, string outfile)
{
int ch, symbol;
try
{
dataout = new FileStream(outfile, FileMode.Create);
}
catch (IOException exc)
{
return;
}
try
{
datain = new FileStream(infile, FileMode.Open);
}
catch (FileNotFoundException exc)
{
return;
}
start_model();
start_outputing_bits();
start_encoding();
//Цикл обработки символов
for(;; )
{
try
{
//Чтение исходного символа
ch= datain.ReadByte();
}
catch(Exception exc)
{
return;
}
//Выход при достижении конца файла
if(ch == -1)
break;
//Найти рабочий символ
symbol = char_to_index[ch];
// Закодировать символ
encode_symbol(symbol);
// Обновить модель
update_model(symbol);
}
//Закодировать символ конца файла
encode_symbol(eof_symbol);
// Завершение кодирования
done_encoding();
done_outputing_bits();
dataout.Close();
datain.Close();
}
//------------------------------------------------------------
//Собственно адаптивное арифметическое декодирование
void decode(string infile, string outfile)
{
int ch, symbol;
try
{
dataout = new FileStream(outfile, FileMode.Create);
}
catch (IOException exc)
{
return;
}
try
{
datain = new FileStream(infile, FileMode.Open);
}
catch (FileNotFoundException exc)
{
return;
}
start_model ();
start_inputing_bits ();
start_decoding ();
//Цикл обработки сиволов
for(;;)
{
//Получаем индекс символа
symbol = decode_symbol ();
if (symbol == eof_symbol)
break;
//Получаем декодированный символ
ch= index_to_char [symbol];
//Записываем в выходной файл
dataout.WriteByte((byte)ch);
//Обновляем модель
update_model (symbol);
}
dataout.Close();
datain.Close();
}
/>/>Приложение 2. Интерфейс программы
/>
/>
Примечание.Для работы программы необходим Microsoft .NET Framework 2.0.