Стиснення даних; es - стиснення арифмуту; галочка

Арифметичне кодування

Ця частина введе стиснення без втрат, яке називається арифметичним кодуванням. Спочатку він визначить інтерес алгоритму перед поданням стиснення та декомпресії, виконуваних цим кодуванням

арифмуту

Опис

Арифметичне кодування - це статистичне кодування, тобто, чим більше представлено символ, тим менше бітів буде потрібно для його кодування.

Це двоюрідний брат кодування Хаффмана, який, однак, завжди є більш ефективним, ніж останній (за винятком особливого випадку, коли всі ваги листя/вузлів/коренів дерева Хаффмана є степенями 2). Це також простіше у реалізації.

Перевага арифметичного кодування над кодуванням Хаффмана полягає в тому, що останнє буде кодувати символ над цілим числом бітів (він не може кодувати 1,5 біта) там, де арифметичне кодування може. Наприклад, якщо символ представлений на рівні 90%, оптимальним розміром коду символу буде 0,15 біта, тоді як Хаффман, мабуть, кодував би цей символ на 1 біт, або в 6 разів більше.

На практиці це кодування використовується дуже мало, але воно залишається наявним, особливо у форматі JPEG2000.

Стиснення

Для демонстрації стиснення ми використаємо приклад і опишемо кожен етап стиснення. Давайте кодуємо слово "ESIPE", використовуючи арифметичне кодування.

Першим кроком є ​​підрахунок кожної літери слова. Отже, у нас є 2 «E», 1 «S», 1 «I» і 1 «P». Потім ми генеруємо ймовірність присутності у слові, тобто 40% шансів знайти E та 20% шансів для інших букв. Останню дію, яку слід виконати для цієї першої частини, ми призначаємо кожній букві інтервал від 0 до 1 наступним чином:

  • Буква "Е" має ймовірність 40% (або 0,4). Тому його інтервал становить [0,0,4 [
  • Буква "Р" має ймовірність 20% (або 0,2). Тому його інтервал становить [0,4,0,6 [
  • І т. Д.

Потім ми отримуємо таку таблицю:

Інтервал вірогідності букв
Е 4/10 [0,0,4 [
S 2/10 [0,4,0,6 [
Я 2/10 [0,6,0,8 [
P 2/10 [0,8,1,0 [

Тепер кодування буде полягати в заміні слова ESIPE на плаваюче число, що відповідає йому. Для цього слову буде присвоєно інтервал між 0 і 1 або кожне число між двома інтервалами дозволить знайти слово ESIPE.

Застосований алгоритм такий: слово починається з інтервалом [0,1 [. Тоді для кожної перекресленої букви ми застосовуємо таку формулу:

  • Нижня межа (BI) слова модифікується в результаті розрахунку "BI + (BS - BI) * Borne_Inferieure_Lettre"
  • Верхня межа (BS) слова модифікується в результаті розрахунку "BI + (BS - BI) * Borne_Superieure_Lettre"

Наступна таблиця показує кроки розрахунку:

Літера Нижній термінал Верхній термінал
0,0 1.0
Е 0,0 0,4
S 0,16 0,24
Я 0,208 0,224
P 0,2208 0,224
Е 0,2208 0,22208

Отже, будь-яке число, яке плаває між 0,2208 і 0,22208, є стислим форматом слова "ESIPE"

Декомпресія

Таким же чином ми подамо декомпресію на прикладі, розпакувавши наш стислий формат.

Розглянемо число 0,2208, яке кодує слово "ESIPE". Принцип декомпресії дуже простий. Це слідує за наступними двома кроками, які повторюються до отримання слова:

  • Наступна буква слова - це та, інтервал якої містить номер поточного слова (Приклад: 0,2208 знаходиться в інтервалі E, тому перша буква - E).
  • Ми модифікуємо число, що представляє слово, використовуючи розрахунок "(номер слова - нижня межа букви)/ймовірність букви (Наприклад: номер слова = (0,2208 - 0,0)/0,4 = 0,552)

Наступна таблиця показує різні стадії декомпресії:

Слово лист новий код
Е 0,552
Е S 0,76
ES Я 0,8
ESI P 0,0
ESIP Е

Отже, ми отримали своє перше слово: ESIPE