дності между символами джерела и кодове слово. Замість цього, вся послідовність сімволів джерела (тобто всі ПОВІДОМЛЕННЯ) співвіднесена з одним Арифметичний кодовим словом. Саме по Собі кодове слово задає Інтервал дійсніх чисел между 0 и 1. Зі збільшенням числа сімволів в Повідомленні, Інтервал, необхідній для їх Подання, зменшується, а число одиниць информации (скажімо, бітів), необхідніх для представлення інтервалу, збільшується. Коженая символ в Повідомленні зменшує розмір інтервалу в відності з ймовірністю своєї з'явиться. Оскількі метод не требует, як, например, ПІДХІД Хаффмана, щоб КОЖЕН вихідний символ відображався в ціле число кодових слів (тобто щоб символи кодувалися по одному), ВІН досягає (у Теорії) кордону, свячень теореми кодування без шуму (див. Розділ 1.3. 3).
На Рис. 8.13 проілюстрованій Основний процес Арифметичний кодування. Тут кодується ПОВІДОМЛЕННЯ з п'яти сімволів, Утворення чотірьохсімвольнім Джерелом:. На качана процесса кодування передбачається, что ПОВІДОМЛЕННЯ займає весь напіввідкрітій Інтервал [0, 1). Цей Інтервал спочатку діліться на Чотири відрізка пропорційно ймовірностям сімволів джерела, Які наведені в Табліці 1.6. Символ, например, відповідає подінтервал [0, 0,2). Оскількі це перший символ кодованому ПОВІДОМЛЕННЯ, то означатиме, Інтервал части ПОВІДОМЛЕННЯ () буде звуженій до [0, 0,2). На Рис. 1.13 отриманий Інтервал розтягнутій на повну висота МАЛЮНКИ, и наведені значення на его кінцях відповідають значень вузького діапазону. Потім вузький ДІАПАЗОН такоже діліться на відрізкі, пропорційно ймовірностям сімволів джерела, и процес повторюється з Наступний символом ПОВІДОМЛЕННЯ. Таким чином, символ звузіть подінтервал до [0,04, 0,08), - до [0,056, 0,072) i т.д. Останній символ ПОВІДОМЛЕННЯ, Який винен буті зарезервованому для спеціального індікатора Закінчення ПОВІДОМЛЕННЯ, звужує ДІАПАЗОН до [0,06752, 0,0688). Звічайна, будь-яке число в цьом підінтервалі - например, 0,068 - может буті Використано для подання ПОВІДОМЛЕННЯ.
Рис. 1.13 Процедура Арифметичний кодування
Таблиця 1.6 Приклад Арифметичний кодування
ПОВІДОМЛЕННЯ з п яті сімволів, наведення на Рис. 1.13, после Арифметичний кодування требует для запису Всього трьох десятковіх цифр. Це відповідає 3/5 або 0,6 десятковіх знаків на символ джерела и вельми около ентропії джерела, яка, зі ¬ гласно (8.3-3), стає 0,58 десятковіх знаків (десятковіх одиниць) на символ. При збільшенні Довжина кодованому послідовності, результуюча Арифметичний код наближається до Межі, поставлені теореми кодування без шуму. На практике два фактори заважають кодів характеристикам наблізітіся до даної границі впрітул: (1) необходимость Включення Деяк символу Закінчення, что дозволяє відокремлюваті одну кодів послідовнність від Іншої, і (2) использование арифметики кінцевої точності. Для Подолання останньої проблеми, при практічній реализации Арифметичний кодування застосовуються стратегії масштабування и округлення. Согласно стратегії масштабування, КОЖЕН подінтервал перед розбіттям его на відрізкі, пропорційні ймовірностям сімволів, розтягується до діапазону [0, 1). Стратегія округлення гарантує, что обмеження, пов язані з кінцевою точністю Обчислення, що не перешкоджають точному Поданєв кодів підінтервалів.
. 4.2 LZW кодування
Розглянувші основні методи скороченню кодової надмірності, перейдемо до РОЗГЛЯДУ одного з декількох методів стиснения без Втратили, Який такоже спрямованостей на скороченню міжелементніх надлішковості зображення. Метод, звань методом кодування Лемпеля-зіва-Уелш, відображає послідовність сімволів джерела різної довжина на рівномірній код, причому не требует апріорного знання ймовірностей з'явиться кодуєміх сімволів. Згадаймо з розділу 1.3.3 тверджень Першої теореми Шеннона про том, что n-кратний Розширення джерела без пам'я ті может буті кодованому з меншими середнім числом бітів на символ джерела, чем сам нерозшірення джерело. Незважаючі на тій факт, что метод LZW -стіснення винен буті ліцензованій согласно патентом США № 4,558,302, ВІН інтегрованій в много широко вікорісвуєміх файлових форматах збережений, включаючі GIF (graphic interchange format), TIFF (tagged image file format) а такоже PDF (portable document format).
Концептуально LZW-кодування є очень пробачимо. При запуску процесса кодування будується качан кодової книги або «словник», что містіть лишь кодовані символи джерела. Для 8-бітового монохромного зображення словник має розміри в 256 слів і відображає значення яскравості 0, 1,2, ..., 255. Кодер послідовно Аналізує символи джерела (тобто значення пікселів), и при появі відсутньої в словнику Серії, вон поміщається у візначувану алгоритмом (Наступний вільну) місце словника. Если Перші дві пікселя зображення, например, були білими (255-255), ця серія может буті припис...
