Компресиране на данни; es - Компресия на аритмата; отметка
Аритметично кодиране
Тази част ще въведе компресия без загуби, наречена аритметично кодиране. Първо ще определи интереса на алгоритъма, преди да представи компресията и декомпресията, извършени от това кодиране
Описание
Аритметичното кодиране е статистическо кодиране, което означава, че колкото повече е представен знак, толкова по-малко бита ще са необходими за неговото кодиране.
Това е братовчед на кодирането на Huffman, което обаче винаги е по-ефективно от последното (с изключение на специалния случай, когато всички тегла на листата/възлите/корените на дървото на Huffman са степен 2). Освен това е по-лесно за изпълнение.
Предимството на аритметичното кодиране пред кодирането на Хафман е, че последното ще кодира символ над цял брой битове (не може да кодира 1,5 бита), където аритметичното кодиране може. Например, ако даден символ е представен на 90%, оптималният размер на кода на символа ще бъде 0,15 бита, докато Huffman вероятно ще кодира този символ на 1 бит или 6 пъти повече.
Това кодиране се използва много малко на практика, но остава налично, особено във формат JPEG2000.
Компресия
За да демонстрираме компресия, ще използваме пример и ще опишем всяка стъпка на компресия. Нека кодираме думата „ESIPE“, използвайки аритметично кодиране.
Първата стъпка е да преброите всяка буква от думата. И така, имаме 2 „E“, 1 „S“, 1 „I“ и 1 „P“. След това генерираме вероятност за присъствие в думата, т.е. 40% шанс да намерим E и 20% шанс за останалите букви. Последното действие, което трябва да се извърши за тази първа част, ние присвояваме на всяка буква интервал между 0 и 1, както следва:
- Буквата "E" има вероятност от 40% (или 0,4). Следователно неговият интервал е [0,0,4 [
- Буквата "P" има вероятност от 20% (или 0,2). Следователно неговият интервал е [0,4,0,6 [
- И т.н.