рус | укр

Главная

Контакты

Навигация:
Арсенал
Болезни
Витамины
Вода
Вредители
Декор
Другое
Животные
Защита
Комнатные растения
Кулинария
Мода
Народная медицина
Огород
Полесадник
Почва
Растения
Садоводство
Строительство
Теплицы
Термины
Участок
Фото и дизайн
Хранение урожая









Арифметические методы

Основные принципы арифметического кодирования были разработаны в конце 70-х годов. Арифметическое кодирование, так же как и вероятностные методы, использует в качестве основы технологии сжатия вероятность появления символа в файле, однако сам процесс арифметического кодирования имеет принципиальные отличия. В результате арифметического кодирования символьная последовательность (строка) заменяется действительным числом больше нуля и меньше единицы.

Рассмотрим процесс арифметического кодирования слова "REDUNDANCE" (избыточность). Частота появления каждой буквы в этом слове равна 0.1 за исключением букв E, D и N, которые встречаются дважды, и, соответственно, вероятность их появления равна 0.2. Далее каждой букве присваивается интервал вероятности (range), длина которого рассчитывается исходя из вероятности их появления в слове (табл. 2).

Буква Вероятность Интервал
A 0.1 0.0-0.1
C 0.1 0.1-0.2
D 0.2 0.2-0.4
E 0.2 0.4-0.6
N 0.2 0.6-0.8
R 0.1 0.8-0.9
U 0.1 0.9-1.0

Таблица 2. Интервалы вероятности для символов в слове Redundance.

Дальнейшую процедуру арифметического сжатия поясним с помощью табл. 3. Первая буква слова - 'R' - получает интервал с нижней границей 0.8 и с верхней - 0.9. Нижняя граница интервала и становится первой значащей цифрой кода. Затем производится расчет границ подинтервалов для каждой последующей буквы по алгоритму: нижняя граница нового интервала равна предыдущей нижней границе (для буквы Е это 0.8) плюс произведение предыдущего интервала (для буквы Е это будет интервал 0.9-0.8=0.1) и нижней (для расчета верхней границы интервала - верхней) границы интервала для буквы Е (эти значения соответственно равны 0.4 и 0.6; их берем из табл. 2). В результате, последовательность символов 'REDUNDANCE' заменяется числом 0.8478570048. Таким образом, вместо 10 байт необходимых для хранения символьной строки нам потребуется всего 4 байта для записи числа.

Символ Нижняя граница Верхняя граница
R 0.8 0.9
E 0.84 0.86
D 0.844 0.848
U 0.8476 0.848
N 0.84784 0.84792
D 0.847856 0.847872
A 0.8478560 0.848
N 0.84785696 0.84785728
C 0.847856992 0.847857024
E 0.8478570048 0.8478570432

Таблица 3. Пошаговое представление строки REDUNDANCE методом арифметического кодирования.

Арифметическое кодирование позволяет обеспечить высокую степень сжатия данных, особенно в случаях, когда мы имеем дело с данными, где частота появления различных символов сильно отличается друг от друга. В то же время сама процедура арифметического кодирования требует мощных вычислительных ресурсов, и до недавнего времени этот метод мало применялся в сетевых приложениях из-за медленной работы алгоритма и, соответственно, существенного времени задержки при передаче пакета. Лишь появление мощных моделей RISC-процессоров позволило создать эффективные устройства арифметического сжатия данных.

Просмотров: 118

Вернуться в категорию: Термины

© 2013-2017 cozyhomestead.ru - При использовании материала "Удобная усадьба", должна быть "живая" ссылка на cozyhomestead.ru.