Методи стискання інформації: огляд та порівняльний аналіз, Детальна інформація
Методи стискання інформації: огляд та порівняльний аналіз
Текст, який стиснено арифметичним кодером, розглядається як деякий двійковий дріб з інтервалу [0,1). Результат стискання можна подати як послідовність двійкових цифр із цього дробу.
Ідея методу полягає в наступному: початковий текст розглядається як запис цього дробу, де кожен вхідний символ є “цифрою” з вагою, що пропорційна ймовірності його появи. Пояснимо роботу кодера на прикладі.
Нехай алфавіт складається із двох символів: a та b з імовірностями відповідно 3/4 та 1/4. Як вже згадувалося вище, кодування Хаффмена не може стискати слова в даному алфавіті.
Розглянемо (відкритий справа) інтервал [0,1). Розіб’ємо його на частини, довжина яких пропорційна імовірностям символів. В нашому випадку це – [0, 3/4) i [3/4, 1). Принцип дії алгоритму полягає в наступному: кожному слову в початковому алфавіті відповідає певний підінтервал із [0,1). Порожньому слову відповідаю весь інтервал [0,1). Після отримання кожного наступного символу арифметичний кодер зменшує інтервал, обираючи ту його частину, яка відповідає символу, що надійшов. Кодом ланцюжка є інтервал, виділений після обробки всіх його символів, а точніше, двійковий запис координати будь-якої точки з цього інтервалу.
Таким чином, довжина отриманого інтервалу пропорційна ймовірності появи кодованого ланцюжка.
Виконаємо алгоритм для ланцюжка aaba (див. табл.2). В якості коду можна взяти будь-яке число з інтервалу, що отриманий на кроці 4, наприклад, 0.1.
Крок Ланцюжок, що розглядається Інтервал
0 “” [0,1)=[0,1)
1 а [0, 3/4)=[0, 0.11)
2 аa [0, 9/16)=[0, 0.1001)
3 аab [27/64, 36/64)=[0.011011, 0.100100)
4 аaba [108/256,135/256)=[0.01101100, 0.10000111)
Таб. 2. Арифметичне кодування.
Арифметичний декодер працює синхронно з кодером: почавши з інтервалу [0,1), він послідовно визначає символи вхідного ланцюжка.
Зокрема, в нашому випадку він спочатку поділить (пропорційно частотам символів) інтервал [0,1) на [0, 0.11) та [0.11,1). Оскільки число 0.1 (код ланцюжка аaba, переданий кодером) знаходиться в першому з них, можна отримати перший символ: а. Потім ділимо перший підінтервал [0, 0.11) на [0, 0.1001) та [0.1001, 0.1100) (пропорційно частотам символів). Знову обираємо перший, оскільки 0 < 0.1 < 0.1001. Продовжуючи цей процес, ми однозначно декодуємо всі чотири символи. Для того, щоб декодер зміг визначити кінець ланцюжка, можна або передавати його довжину окремо, або додати до алфавіту символ “кінець ланцюжка”.
-
D
F
z
|
~
\x20AC
‚
¬
®
a
ae
ae
e
Ідея методу полягає в наступному: початковий текст розглядається як запис цього дробу, де кожен вхідний символ є “цифрою” з вагою, що пропорційна ймовірності його появи. Пояснимо роботу кодера на прикладі.
Нехай алфавіт складається із двох символів: a та b з імовірностями відповідно 3/4 та 1/4. Як вже згадувалося вище, кодування Хаффмена не може стискати слова в даному алфавіті.
Розглянемо (відкритий справа) інтервал [0,1). Розіб’ємо його на частини, довжина яких пропорційна імовірностям символів. В нашому випадку це – [0, 3/4) i [3/4, 1). Принцип дії алгоритму полягає в наступному: кожному слову в початковому алфавіті відповідає певний підінтервал із [0,1). Порожньому слову відповідаю весь інтервал [0,1). Після отримання кожного наступного символу арифметичний кодер зменшує інтервал, обираючи ту його частину, яка відповідає символу, що надійшов. Кодом ланцюжка є інтервал, виділений після обробки всіх його символів, а точніше, двійковий запис координати будь-якої точки з цього інтервалу.
Таким чином, довжина отриманого інтервалу пропорційна ймовірності появи кодованого ланцюжка.
Виконаємо алгоритм для ланцюжка aaba (див. табл.2). В якості коду можна взяти будь-яке число з інтервалу, що отриманий на кроці 4, наприклад, 0.1.
Крок Ланцюжок, що розглядається Інтервал
0 “” [0,1)=[0,1)
1 а [0, 3/4)=[0, 0.11)
2 аa [0, 9/16)=[0, 0.1001)
3 аab [27/64, 36/64)=[0.011011, 0.100100)
4 аaba [108/256,135/256)=[0.01101100, 0.10000111)
Таб. 2. Арифметичне кодування.
Арифметичний декодер працює синхронно з кодером: почавши з інтервалу [0,1), він послідовно визначає символи вхідного ланцюжка.
Зокрема, в нашому випадку він спочатку поділить (пропорційно частотам символів) інтервал [0,1) на [0, 0.11) та [0.11,1). Оскільки число 0.1 (код ланцюжка аaba, переданий кодером) знаходиться в першому з них, можна отримати перший символ: а. Потім ділимо перший підінтервал [0, 0.11) на [0, 0.1001) та [0.1001, 0.1100) (пропорційно частотам символів). Знову обираємо перший, оскільки 0 < 0.1 < 0.1001. Продовжуючи цей процес, ми однозначно декодуємо всі чотири символи. Для того, щоб декодер зміг визначити кінець ланцюжка, можна або передавати його довжину окремо, або додати до алфавіту символ “кінець ланцюжка”.
-
D
F
z
|
~
\x20AC
‚
¬
®
a
ae
ae
e
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021