RLE - байтовый рівень

RLE - бітовий рівень

Алгоритми кодування довжини повторення (RLE)

Цей тип алгоритмів (алгоритми кодування довжини повторення ²⁾ (RLE ³⁾ ))базується на найпростішому принципі: будемо заміняти повторювані групи елементів вихідної послідовності на парі (кількість, елемент), або тільки на кількість.

Будемо розглядати вихідні дані на рівні послідовності битов; наприклад, що представляють чорно-біле зображення. Підряд звичайно йде трохи 0 або 1, і можна пам'ятати лише кількість однакових цифр, що йдуть підряд. Т.е. послідовності 0000 11111 000 11111111111 відповідає набір чисел кількостей повторень 4 5 3 11. Виникає наступний нюанс: числа, що позначають кількість повторень, також треба кодувати бітами. Можна вважати, що кожне число повторень змінюється від 0 до 7 (тобто можна закодувати рівно трьома бітами), тоді послідовності 11111111111 можна зіставити числа 7 0 4, тобто 7 одиниць, 0 нулів, 4 одиниці. Для приклада, послідовність, що складається з 21 одиниці, 21 нуля, 3 одиниць і 7 нулів закодується так: 111 000 111 000 111 111 000 111 000 111 011 111, тобто з вихідної послідовності, що має довжину 51 біт, одержали послідовність довжиною 36 біт.

Ідея цього методу використовується при передачі факсів.

Припустимо, що на вхід подається напівтонове зображення, де на значення інтенсивності пикселя приділяється 1 байт. Ясно, що в порівнянні із чорно-білим растром очікування довгого ланцюжка однакових битов істотно знижується.

Будемо розбивати вхідний потік на байти (букви) і кодувати повторювані букви парою (кількість, буква).

Т.е. AABBBCDAA кодуємо (2A) (3B) (1C) (1D) (2A). Однак можуть зустрічатися довгі відрізки даних, де нічого не повторюється, а ми кодуємо кожну букву парою (цифра, буква).

Нехай у нас є фіксоване число (буква) M (від 0 до 255). Тоді одиночну букву можна закодувати нею самою, - вихід = S, а якщо букв трохи або , те вихід = CS, де C > M, а C - M - кількість букв, що підряд ідуть, S. Для приклада приведемо тільки алгоритм декодування.

// M - фіксована границя// зчитуємо символи послідовно із вхідного потоку// in - вхід - стисла послідовність// out - вихід - розціплена послідовністьwhile(in.Read(c)){ if(c > M) { // випадок лічильника n = c - M; in.Read(c); for (i = 0; i < n; i++) out.Write(c); } else // випадок просто символу out.Write(c);}

Лістинг 13.1. Алгоритм декодування RLE - байтовый рівень

Число M звичайно дорівнює 127. Частіше використовується модифікація цього алгоритму, де ознакою лічильника служить наявність одиниць в 2 старших бітах зчитувального символу. Інші 6 битов суть значення лічильника.

Така модифікація даного алгоритму використовується у форматі PCX. Однак модифікації даного алгоритму рідко використовуються самі по собі, тому що підклас послідовностей, на яких даний алгоритм ефективний, відносно вузький. Модифікації алгоритму використовуються як одна зі стадій конвеєра стиску (наприклад у форматі JPEG, див. розділ 13.4).

13.4. Словникові алгоритми

Головна ідея, що лежить в основі алгоритмів даного типу, полягає в тім, що замість кодування тільки по одному елементі вхідної послідовності виробляється кодування ланцюжка елементів. При цьому використовується словник ланцюжків (створений по вхідній послідовності) для кодування нових.

Дата добавления: 2014-01-07