|
Арифметические методы
Основные принципы арифметического кодирования были разработаны в конце 70-х годов. Арифметическое кодирование, так же как и вероятностные методы, использует в качестве основы технологии сжатия вероятность появления символа в файле, однако сам процесс арифметического кодирования имеет принципиальные отличия. В результате арифметического кодирования символьная последовательность (строка) заменяется действительным числом больше нуля и меньше единицы. Рассмотрим процесс арифметического кодирования слова "REDUNDANCE" (избыточность). Частота появления каждой буквы в этом слове равна 0.1 за исключением букв E, D и N, которые встречаются дважды, и, соответственно, вероятность их появления равна 0.2. Далее каждой букве присваивается интервал вероятности (range), длина которого рассчитывается исходя из вероятности их появления в слове (табл. 2).
Таблица 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 байта для записи числа.
Таблица 3. Пошаговое представление строки REDUNDANCE методом арифметического кодирования. Арифметическое кодирование позволяет обеспечить высокую степень сжатия данных, особенно в случаях, когда мы имеем дело с данными, где частота появления различных символов сильно отличается друг от друга. В то же время сама процедура арифметического кодирования требует мощных вычислительных ресурсов, и до недавнего времени этот метод мало применялся в сетевых приложениях из-за медленной работы алгоритма и, соответственно, существенного времени задержки при передаче пакета. Лишь появление мощных моделей RISC-процессоров позволило создать эффективные устройства арифметического сжатия данных. Просмотров: 658 Вернуться в категорию: Термины |
© 2013-2021 cozyhomestead.ru - При использовании материала "Удобная усадьба", должна быть "живая" ссылка на cozyhomestead.ru.
|