Знаймо

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

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

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

LZ77



План:


Введення

LZ77 і LZ78 - алгоритми стиснення без втрат, опубліковані в статтях Абрахама Лемпеля (англ.) і Якоба Зеева (англ.) в 1977 і 1978 роках. Ці алгоритми найбільш відомі варіанти в сімействі LZ *, яке включає в себе також LZW, LZSS, LZMA та інші алгоритми.

Обидва алгоритми відносяться до словниковим методам, на відміну від інших методів зменшення надмірності, таких як RLE і арифметичне стиснення. LZ77 є алгоритмом зі "ковзним вікном", що еквівалентно неявному використанню словникового підходу, вперше запропонованого в LZ78.


1. LZ77

Можна сказати, що алгоритми сімейства LZ * являють собою більш складне узагальнення простого і інтуїтивного способу стиснення даних, використовуваного в RLE. Для розуміння даного алгоритму необхідно розібратися з двома його складовими: принципом ковзаючого вікна і механізмом кодування збігів.

1.1. Принцип ковзного вікна

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

Завдяки цьому принципу алгоритми LZ * іноді називаються методами стиснення з використанням ковзного вікна. Ковзне вікно можна представити у вигляді буфера (або більш складної динамічної структури даних), який організований так, щоб запам'ятовувати "сказану" раніше інформацію і надавати до неї доступ. Таким чином, сам процес стискає кодування згідно LZ77 нагадує написання програми, команди якої дозволяють звертатися до елементів "ковзного вікна", і замість значень стисливою послідовності вставляти посилання на ці значення в "ковзному вікні". Розмір ковзного вікна може динамічно змінюватися і складати 2, 4 або 32 кілобайти. Слід також зазначити, що розмір вікна кодувальника може бути менше або дорівнює розміру вікна декодировщик, але не навпаки.

Наведене вище порівняння процесу кодування з "програмуванням" може наштовхнути на передчасний висновок про те, що алгоритм LZ77 відноситься до методів контекстного моделювання. Тому слід зазначити, що алгоритм LZ77 прийнято класифікувати як метод словникового стиснення даних, коли замість поняття "ковзного вікна" використовується термін "динамічного словника".


1.2. Механізм кодування збігів

Перед тим, як перейти до розгляду механізму кодування, уточнимо поняття збігу (від англ. match ). Розглянемо послідовність з N елементів. Якщо всі елементи послідовності унікальні, то така послідовність не буде містити жодного повторюваного елемента, або, інакше кажучи, в послідовності не знайдеться хоча б двох рівних один одному або співпадаючих елементів.

У стандартному алгоритмі LZ77 збігу кодуються парою:

  • довжина збігу (match length)
  • зсув (offset) або дистанція (distance)

У продовження вже наведеної аналогії з програмуванням відзначимо, що в більшості статей, присвячених алгоритму LZ77, кодована пара трактується саме як команда копіювання символів з ​​ковзного вікна з певної позиції, або дослівно як: "Повернутися в буфері символів на значення зсуву і скопіювати значення довжини символів , починаючи з поточної позиції ".

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

Приклад з командою копіювання не зовсім очевидний: "Повернутися на 1 символ назад в буфері і скопіювати 7 символів, починаючи з поточної позиції". Яким чином можна скопіювати 7 символів з буфера, коли зараз в буфері знаходиться тільки 1 символ? Однак наступна інтерпретація кодує пари може прояснити ситуацію: кожні 7 наступних символів збігаються (еквівалентні) з 1 символом перед ними.

Це означає, що кожен символ можна однозначно визначити, перемістившись назад в буфері - навіть якщо даний символ ще відсутня в буфері на момент декодування поточної пари довжина-зміщення. Така кодована пара буде являти собою багаторазове (обумовлений значенням зсуву) повторення послідовності (обумовленої значенням довжини) символів, що являє собою більш загальну форму RLE.


1.3. Недоліки

  • неможливість кодування підрядків, віддалених один від одного на відстані, більшій довжини словника
  • довжина підрядка, яку можна закодувати, обмежена розміром буфера
  • мала ефективність при кодуванні незначного обсягу даних

1.4. Приклад "abracadabra"

 Поз. Довжина симв. Abracadabra 0 0 aa bracadabra 0 0 b ab racadabra 0 0 r a br acadabra 1 березня a c abr a c adabra 2 січня a d abra cad abra 4 липня abra 

Виділені символи відсутні в послідовності, що кодує.

1.5. Реалізація LZ77 на Сі

 / * ============================== Архівація Алгоритм LZ77 Дуже неоптимізованих варіант Прохання обробити напільнічком, як слід. ============================== * /  # Define DICBITS 12 / / Log (DICSIZE)  # Define DICSIZE (1 << DICBITS) / / 4-32kB Розмір словника  # Define THRESHOLD 2 / / Поріг  # Define STRBITS 6 / / Log (STRMAX-THRESHOLD)  # Define STRMAX ((1 << STRBITS) + THRESHOLD) / / Мах. довжина рядка  # Define BUFSIZE 0xff00U / / Повний розмір буфера  # Define TEXTSIZE (BUFSIZE-DICSIZE-STRMAX) / / Розмір буфера тексту  # Define YES 1  # Define NO 0  FILE  *  first_file  ,  *  second_file  ;  long  srcleng  =  0  ,  fileleng  ;  unsigned  char  *  srcbuf  ,  *  srcstart  ;  / * ====================================== Функція запису ======== =============================== * /  int  putbits  (  int  data  ,  int  nbits  )  {  static  int  bitcounter  =  0  ;  static  int  outdata  =  0  ;  int  bit  ,  error  ;  data  << =  (  16  -  nbits  )  ;  for  (  ;  nbits  >  0  ;  nbits  -  )  {  if  (  bitcounter  ==  8  )  {  bitcounter  =  0  ;  error  =  putc  (  outdata  ,  second_file  )  ;  if  (  error  ==  EOF  )  {  printf  (  "Error writing to Second file."  )  ;  return  -  5  ;  }  }  outdata  << =  1  ;  bit  =  (  data  &  0x8000  )  ?  1  :  0  ;  outdata  + =  bit  ;  bitcounter  + +;  data  << =  1  ;  }  }  / * ==================================== Функція архівування ========== ========================= * /  void  compress_stud  (  )  {  / / Struct stat buf;  unsigned  char  *  position  ,  *  pointer  ;  / / Байт у файлі, байт у буфері  int  i  ,  dist  ,  offset  =  0  ,  last  =  NO  ,  cnt  ,  maxleng  ;  printf  (  "Compress started."  )  ;  / / Записуємо розмір вихідного файлу  fstat  (  fileno  (  first_file  )  , &  buf  )  ;  fileleng  =  buf.  st_size  ;  write  (  fileno  (  second_file  )  ,  &  fileleng  ,  sizeof  (  long  )  )  ;  / / Читаємо файл в буфер вроздріб розміру TEXTSIZE  while  (  (  srcleng  =  fread  (  srcstart  +  offset  ,  1  ,  TEXTSIZE  ,  first_file  )  )  >  0  )  {  if  (  srcleng  <  TEXTSIZE  )  / / Остання частина тексту  {  last  =  YES  ;  }  position  =  srcstart  ;  pointer  =  srcbuf  ;  srcleng  + =  offset  ;  while  (  srcleng  >  0  )  {  printf  (  "  \ N  \ N  Step -% d  \ N  "  ,  srcleng  )  ;  maxleng  =  0  ;  if  (  (  last  ==  NO  )  &&  (  srcleng  <  STRMAX  )  )  / / Якщо в буфері тексту залишилося мало символів, зрушуємо словник і залишився текст в початок буфера і дочитувати наступну частину з файлу  {  memcpy  (  srcbuf  ,  pointer  ,  DICSIZE  +  (  int  )  srcleng  )  ;  offset  =  (  int  )  srcleng  ;  break  ;  }  for  (  i  =  DICSIZE  -  1  ;  i  > =  0  ;  i  -  )  / / Шукаємо найдовшу співпадаючу рядок у словнику  {  for  (  cnt  =  0  ;  cnt  <  STRMAX  ;  cnt  + +  )  if  (  *  (  position  +  cnt  )  ! =  *  (  pointer  +  i  +  cnt  )  )  break  ;  if  (  cnt  <=  THRESHOLD  )  / / Якщо довжина менше порога, відкидаємо  continue  ;  if  (  cnt  ==  STRMAX  )  / / Якщо максимальна рядок, далі не шукаємо  {  dist  =  DICSIZE  -  1  -  i  ;  / / Позиція  maxleng  =  STRMAX  ;  / / Довжина  break  ;  }  if  (  cnt  >  maxleng  )  / / Якщо черговий рядок довший вже знайдених, зберігає її довжину і позицію  {  dist  =  DICSIZE  -  1  -  i  ;  / / Позиція  maxleng  =  cnt  ;  / / Довжина  }  }  if  (  (  last  ==  YES  )  &&  (  maxleng  >  srcleng  )  )  / / Перевіряємо, щоб не було виходу за межі файлу  {  maxleng  =  (  int  )  srcleng  ;  / / Обрізаємо довжину по кордон буфера  }  if  (  maxleng  >  THRESHOLD  )  / / Якщо рядок досить довга, формуємо pointer-код  {  printf  (  "Link!  \ N  "  )  ;  putbits  (  1  ,  1  )  ;  / / Помічаємо як посилання  putbits  (  dist  ,  DICBITS  )  ;  / / Записуємо позицію  putbits  (  maxleng  -  THRESHOLD  -  1  ,  STRBITS  )  ;  / / Записуємо довжину  position  + =  maxleng  ;  srcleng  - =  maxleng  ;  pointer  + =  maxleng  ;  }  else  / / Інакше - chr-код  {  printf  (  "Char!  \ N  "  )  ;  putbits  (  0  ,  1  )  ;  / / Помічаємо як chr-код  putbits  (  *  position  ,  8  )  ;  / / Записуємо чар код  position  + +;  srcleng  -;  pointer  + +;  }  }  }  / / Записуємо залишилися біти  putbits  (  0  ,  8  )  ;  printf  (  "  \ N  Compress completed!  \ N  "  ,  fileleng  )  ;  }  / / Розархівація Алгоритм LZ77  / * ==================================== Функція зчитування ========== ============================ * /  int  getbits  (  int  nbits  )  {  static  int  bitcounter  =  8  ;  static  int  indata  =  0  ;  int  bit  ,  data  =  0  ;  for  (  ;  nbits  >  0  ;  nbits  -  )  {  if  (  bitcounter  ==  8  )  {  bitcounter  =  0  ;  indata  =  getc  (  first_file  )  ;  }  if  (  indata  ==  EOF  )  {  printf  (  "Error writing to First file."  )  ;  return  -  6  ;  }  bit  =  (  indata  &  0x80  )  ?  1  :  0  ;  data  << =  1  ;  data  + =  bit  ;  bitcounter  + +;  indata  << =  1  ;  }  return  data  ;  }  / * ===================================== Функція Витяги ========= ============================ * /  void  decompress_stud  (  )  {  struct  stat buf  ;  unsigned  char  *  pos  ;  int  i  ,  dist  ,  ch  ,  maxleng  ;  printf  (  "Decompress started.  \ N  "  )  ;  / / Отримуємо довжину вихідного файлу  read  (  fileno  (  first_file  )  , &  fileleng  ,  sizeof  (  long  )  )  ;  pos  =  srcstart  ;  while  (  fileleng  >  0  )  {  if  (  (  ch  =  getbits  (  1  )  )  ==  0  )  / / Якщо chr-код, копіюємо в буфер тексту символ  {  ch  =  getbits  (  8  )  ;  putc  (  ch  ,  second_file  )  ;  *  pos  =  ch  ;  pos  + +;  fileleng  -;  }  else  / / Інакше - копіюємо maxleng символів зі словника, починаючи з позиції dist  {  dist  =  getbits  (  DICBITS  )  +  1  ;  maxleng  =  getbits  (  STRBITS  )  +  THRESHOLD  +  1  ;  for  (  i  =  0  ;  i  <  maxleng  ;  i  + +  )  {  *  (  pos  +  i  )  = *  (  pos  +  i  -  dist  )  ;  putc  (  *  (  pos  +  i  -  dist  )  ,  second_file  )  ;  }  pos  + =  maxleng  ;  fileleng  - =  maxleng  ;  }  if  (  pos  >  srcstart  +  TEXTSIZE  )  / / Якщо буфер заповнений, записуємо його на диск і зрушуємо словник в початок буфера  {  memcpy  (  srcbuf  ,  pos  -  DICSIZE  ,  DICSIZE  )  ;  pos  =  srcstart  ;  }  }  printf  (  "  \ N  Decompress completed. "  )  ;  } 

2. LZ78

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


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

Схожі роботи | скачати
© Усі права захищені
написати до нас