Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Кодування довжин серій



План:


Введення

Кодування довжин серій ( англ. Run-length encoding, RLE ) Або Кодування повторів - простий алгоритм стиснення даних, який оперує серіями даних, тобто послідовностями, в яких один і той же символ зустрічається кілька разів поспіль. При кодуванні рядок однакових символів, що складають серію, замінюється рядком, що містить сам повторюваний символ і кількість його повторів.


1. Приклад використання

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

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

Якщо ми застосуємо просте кодування довжин серій до цього рядка, то отримаємо наступне:

12W1B12W3B24W1B14W

Останній запис інтерпретується як "дванадцять W", "одна B", "дванадцять W", "три B" і т. д. Таким чином, код являє вихідні 67 символів у вигляді всього лише 18.

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

ABCABCABCABCDDEFFFFFFFF
1A1B1C1A1B1C1A1B1C1A1B1C2D1E8F

Проблема вирішується досить просто. Алфавіт, в якому записані довжини серій, поділяється на дві (зазвичай рівні) частини. Алфавіт цілих чисел можна, наприклад, розділити на дві частини: позитивні і негативні. Позитивні використовують для запису кількості повторюваних однакових символів, а негативні - для запису кількості неоднакових.

-12ABCABCABCABC2D1E8F

Так як чисельні типи даних на комп'ютері завжди мають певний межа, виникає ще одна проблема. Припустимо, ми використовуємо signed char для запису довжин серій. Тоді ми не можемо записати серію довше 127 символів однією парою "довжина-символ". Якщо поспіль записано 256 символів A, їх поділяють на мінімальну кількість груп:

127A127A2A

Запис на деякій мові програмування алгоритму RLE з урахуванням цих обмежень нетривіальна.

Звичайно, кодування, яке використовується для зберігання зображень, оперує з двійковими даними, а не з символами ASCII, як у розглянутому прикладі, однак принцип залишається той же.


2. Застосування

Очевидно, що таке кодування ефективно для даних, що містять велику кількість серій, наприклад, для простих графічних зображень, таких як іконки і графічні малюнки. Однак це кодування погано підходить для зображень з плавним переходом тонів, таких як фотографії.

Поширені формати для упаковки даних за допомогою RLE включають в себе PackBits, PCX і ILBM.

Методом кодування довжин серій можуть бути стиснуті довільні файли з двійковими даними, оскільки специфікації на формати файлів часто включають в себе повторюються байти в області вирівнювання даних. Тим не менш, сучасні системи стиснення (наприклад, DEFLATE) частіше використовують алгоритми на основі LZ77, які є узагальненням методу кодування довжин серій і оперують з послідовностями символів вигляду "BWWBWWBWWBWW".

Звукові дані, які мають довгі послідовні серії байт (такі як низькоякісні звукові семпли) можуть бути стиснуті з допомогою RLE після того, як до них буде застосовано Дельта-кодування.



3. Реалізація алгоритму мовою php

  $ Code  =  'Fafaaaaaaaaaaaaa'  ;  $ Encode  =  ''  ;  for  (  $ I  =  0  ;  $ I  <  strlen  (  $ Code  )  ;  $ I  + +  )  {  $ Smb  =  $ Code  [  $ I  ]  ;  $ Count  =  1  ;  for  (  $ B  =  $ I  ;  $ B  <  strlen  (  $ Code  )  ;  $ B  + +  )  {  if  (  $ Code  [  $ B  +  1  ]  ! =  $ Smb  )  break  ;  $ Count  + +  ;  $ I  + +  ;  }  $ Encode  . =  $ Count  .  $ Smb  ;  }  print  'Рядок:'  .  $ Code  .  'Вдалося стиснути до'  .  $ Encode  .  '. 
І ми заощадили'
. ( strlen ( $ Code ) - strlen ( $ Encode ) ) . 'Байт.' ?>

4. Простий приклад реалізації алгоритму на Delphi / Pascal

 function  encode  (  s  :  string  )  :  string  ;  var  i  ,  j  :  integer  ;  newS  :  string  ;  begin  i  :  =  1  ;  while  i <  =  length  (  s  )  do  begin  j  :  =  i  ;  while  (  s  [  i  ]  =  s  [  j  +  1  ]  )  do  inc  (  j  )  ;  if  (  j  -  i  =  0  )  or  (  j  -  i  =  1  )  or  (  j  -  i  =  2  )  then  begin  newS  :  =  newS  +  s  [  i  ]  ;  if  (  s  [  i  ]  =  '0 '  )  then  newS  :  =  newS  +  '0 '  ;  inc  (  i  )  ;  end  else  begin  newS  :  =  newS  +  inttostr  (  j  -  i  +  1  )  +  s  [  i  ]  ;  inc  (  i  ,  j  -  i  +  1  )  ;  end  ;  end  ;  result  :  =  newS  ;  end  ;  function  decode  (  s  :  string  )  :  string  ;  var  i  ,  j  ,  c  :  integer  ;  newS  :  string  ;  dp  :  string  ;  begin  i  :  =  1  ;  while  i <  =  length  (  s  )  do  begin  j  :  =  i  ;  while  s  [  j  ]  in  [  '0 '  ..  '9 '  ]  do  inc  (  j  )  ;  if  j  -  i>  0  then  begin  dp  :  =  copy  (  s  ,  i  ,  j  -  i  )  ;  for  c  :  =  1  to  strtoint  (  dp  )  do  newS  :  =  newS  +  s  [  j  ]  ;  delete  (  s  ,  i  ,  j  -  i  +  1  )  ;  end  else  begin  newS  :  =  newS  +  s  [  i  ]  ;  inc  (  i  )  ;  end  ;  end  ;  result  :  =  newS  ;  end  ; 
Перегляд цього шаблону Методи стиснення
Теорія
Інформація Власна Взаємна Ентропія Умовна ентропія Складність Надмірність
Одиниці виміру Біт Нат Ніббл Хартлі Формула Хартлі
Без втрат
Ентропійно стиснення Алгоритм Хаффмана Адаптивний алгоритм Хаффмана Алгоритм Шеннона - Фано Арифметичне кодування (Інтервальне) Коди Голомба Дельта Універсальний код ( Еліаса Фібоначчі)
Словникові методи RLE Deflate LZ ( LZ77/LZ78 LZSS LZW LZWL LZO LZMA LZX LZRW LZJB LZT)
Інше RLE CTW BWT MTF PPM DMC
Аудіо
Теорія Згортка PCM Аліасінг Дискретизація Теорема Котельникова
Методи LPC (LAR LSP) WLPC CELP ACELP A-закон μ-закон MDCT Перетворення Фур'є Психоакустичної моделі
Інше Компресор аудіосигналу Стиснення мови Смугове кодування
Зображення
Терміни Колірний простір Піксель Субдіскретізація насиченості Артефакти стиснення
Методи RLE DPCM Фрактальний Вейвлетного EZW SPIHT LP ДКП ПКЛ
Інше Бітрейт Test images PSNR Квантування
Відео
Терміни Характеристики відео Кадр Типи кадрів Якість відео
Методи Компенсація руху ДКП Квантування Вейвлетного
Інше Відеокодек Rate distortion theory ( CBR ABR VBR)



Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Список серій мультсеріалу Пригоди Джекі Чана
Кодування
Альтернативна кодування
Кодування (програмування)
Мережеве кодування
Шестібітная кодування
Дельта-кодування
Арифметичне кодування
Ентропійно кодування
© Усі права захищені
написати до нас
Рейтинг@Mail.ru