Алгоритм Лемпеля-Зіва

{{{img}}}
Імя	Володимир
Прізвище	Стодола
По-батькові	Романович
Факультет	ФІС
Група	СН-41
Залікова книжка	№ ПК 06-065

Алгоритм Лемпеля — Зіва(Lempel-ziv, LZ) — це універсальний алгоритм стискування даних без втрат, створений Абрамом Лемпелем (Abraham Lempel), Якобом Зівом (Jacob Ziv) . Він був опублікований Велчем в 1984 році, як покращувана реалізація алгоритму Lz78, опублікованого Лемпелем і Зівом в 1978 році. Алгоритм розроблений так, щоб його можна було швидко реалізувати, але він не обов'язково оптимальний, оскільки він не проводить жодного аналізу вхідних даних.

Історія винекнення

Більше тридцяти років алгоритм стиснення Хаффмана і його варіанти залишалися найбільш популярними методами. Проте в 1977 два дослідники з Ізраїлю запропонували абсолютно інший підхід до цієї проблеми. Абрам Лемпел і Якоб Зів висунули ідею формування "словника" загальних послідовностей даних.
При цьому стиснення даних здійснюється за рахунок заміни записів відповідними кодами із словника. Існують два алгоритми, LZ77 і LZ78. Вони вже не вимагають включення словника даних в архів, оскільки якщо ви формуєте ваш словник визначеним способом, програма декодування може його відновлювати безпосередньо з ваших даних. На жаль, LZ77 і LZ78 витрачають багато часу на створення ефективного словника. Лемпел був запрошений фірмою Sperry для допомоги в розробці способу найбільш ефективної упаковки даних на комп'ютерних стрічках. У цій же фірмі Тері Велч (Terry Welch) розширив алгоритм LZ78, створивши новий варіант, широко відомий, як LZW.
На роботу Велча звернула увагу група програмістів Unix, які використали його алгоритм в їх додатку LZW, що отримав назву compress. Вони додали декілька удосконалень і опублікували загальнодоступну версію цієї програми в телеконференції Internet, завдяки чому багато користувачів змогли почати з нею працювати.
Популярність алгоритму LZW в значній мірі пов'язана з успіхом програми compress. Початковий текст останньої версії програми що здійснює як стиснення, так і декомпресію, займає всього 1200 рядків. Ядро коду стиснення займає не більше сотні рядків, а коду декомпресії не набагато більше. Програмісти вважають, що це полегшує читання і розуміння алгоритму, а також дозволяє адаптувати його для самих різних цілей.

Метод стиснення

Існує багато практичних алгоритмів стиснення даних, але всі вони базуються на трьох теоретичних способах зменшення надлишковості даних. Перший спосіб полягає в зміні вмісту даних, другий - у зміні структури даних, а третій - в одночасній зміні як структури, так і вмісту даних.
Якщо при стисненні даних відбувається зміна їх вмісту, то метод стиснення є незворотнім, тобто при відновленні (розархівуванні) даних з архіву не відбувається повне відновлення інформації. Такі методи часто називаються методами стиснення з регульованими втратами інформації. Зрозуміло, що ці методи можна застосовувати тільки для таких типів даних, для яких втрата частини вмісту не приводить до суттєвого спотворення інформації. До таких типів даних відносяться відео- та аудіодані, а також графічні дані. Методи стиснення з регульованими втратами інформації забезпечують значно більший ступінь стиснення, але їх не можна застосовувати до текстових даних. Прикладами форматів стиснення з втратами інформації можуть бути: JPEG (Joint Photographic Experts Group) для графічних даних:

• MPG - для для відеоданих;
  
• MP3 - для аудіоданих
  

Якщо при стисненні даних відбувається тільки зміна структури даних, то метод стиснення є зворотнім. У цьому випадкові з архіву можна відновити інформацію повністю. Зворотні методи стиснення можна застосовувати до будь-яких типів даних, але вони дають менший ступінь стиснення у порівнянні з незворотними методами стиснення. Приклади форматів стиснення без втрати інформації: GIF (Graphics Interchange Format), TIFF (Tagged Image File Format) - для графічних даних; AVI - для відеоданих; ZIP, ARJ, RAR, CAB, LH - для довільних типів даних. Існує багато різних практичних методів стиснення без втрати інформації, які, як правило, мають різну ефективність для різних типів даних та різних обсягів.

hQxLn9 <a href="http://yyfyhvzhogvp.com/">yyfyhvzhogvp</a>, [url=http://qeoiyipqvmmg.com/]qeoiyipqvmmg[/url], [link=http://wkdgynchgtqb.com/]wkdgynchgtqb[/link], http://iaorgodhlsbk.com/

Дешифрування

Далі приводиться алгоритм дезархівації зі всіма необхідними технічними подробицями і ретельно підібраними значеннями параметрів. Річ у тому, що навіть дуже невеликі варіації параметрів різко міняють ступінь стиснення і, як правило, в гіршу сторону. А боротьба ведеться за долі відсотка. Завдання ускладнюється тим, що немає об'єктивних критеріїв, по яких можна було відразу сказати, що та або інша зміна алгоритму пішла йому на користь. Як ми знаємо, для будь-якого архіватора знайдеться сила-силенна текстів, взагалі непіддатливих стисненню.
Якщо брати тільки такі тексти, то роботу можна не починати. Оцінювати архіватор треба по ходових текстах, але ходові - це не наукове поняття .
3Читається чергова серія бітів до першого одиничного біта. Хай N - кількість лічених бітів. Наприклад, якщо на черги 001000..., то прочитуються 3 бфта і відповідно N=3.А якщо перший же біт дорівнює одиниці, то прочитується тільки він, і N=1. Вводимо число M для формування кількості символів, які пізніше будуть узяті з вже розшифрованого тексту. Спочатку M=N. Числа M і N - цілі двохбайтні.

1. Якщо N більше або рівне 17, то прочитуються чергові 8 бітів і поміщаються в молодші біти числа M.
   
2. Якщо N > 17, то прочитуються чергові 8 бітів і поміщаються в старший байт числа M. (Воно вважається за беззнакового.)
   
3. Якщо M=1, то прочитуються чергові 8 бітів і посилаються на вихід, тобто у відновлений текст, і тоді перехід на п.1.
   
4. Прочитуються чергові 2 біта, по яких формується ціле число Z від 0 до 3. Вводимо K і R.Якщо M=2, Z=0, то K=5, R=0. Якщо M=2, Z=1, то K=7, R=-32.
   

Якщо M=2, Z=2, то K=9, R=-160. Якщо M=2, Z=3, то K=11, R=-672. Якщо M>2, Z=0, то K=6, R=0. Якщо M>2, Z=1, то K=9, R=-64. Якщо M>2, Z=2, то K=12, R=-576. Якщо M>2, Z=3, то K=14, R=-4672.

1. Прочитуються чергові K бітів і поміщаються в молодші K бітів допоміжного цілого двобайтного числа S. Решта бітів цього числа заповнюються одиницями. Отже S<0, оскільки в старшому біті, що відповідає за знак, знаходиться одиниця.
   
2. Визначається адреса в тексті, що випускається, звідки буде узятий потрібний фрагмент. Адреса - це просто номер байта в послідовності їх розташуванні. Для цього до адреси, на якій поки закінчено формування розшифрованого тексту, треба додати R і S. З отриманої таким чином адреси беремо M символів і додаєм в кінець формованого тексту. Перехід на п.1 (якщо дані не вичерпані). Наступна реалізація алгоритму призначена для COM-програм, що саморозархівовуються. Тому перший десяток команд в основному служить для переміщення програми в кінець сегменту код. А вже звідти розшифровані оператори складуються в початок цього сегменту.
   

Варіанти удосконалення

Приведені вище деталі алгоритму і значення параметрів не можуть бути виведені якими-небудь раціональними строгими методами. У якійсь мірі в них відбиті особливості сучасного програмування і людської мови. Але автори кожного архіватора знаходять свій оптимум, і що краще - може підказати тільки практика (критерій загальний, але декілька розпливчатий).
Могутні архіватори зазвичай роблять попередню оцінку початкового файлу і до кожного файлу (або до великих частин одного файлу) здійснюють індивідуальний підхід. Наприклад, перед кожним великим фрагментом стислої коди вказується його об'єм і тип стискування для цього досить 3 байти, які не псують загальної якості компресії.
Якщо файл короткий, значить, взагалі дезархіватору не знадобиться заглядати далеко назад, тоді не потрібний, скажімо випадок K=14, і біти, що звільнилися, можна використовувати з більшою користю. Проте ефект порівняно невеликий. А оскільки він виявляється тільки на малих файлах, то на загальних (зазвичай гігантських) об'ємах інформації він і зовсім втрачається.
Можливі багато інших варіантів удосконалень, не пов'язаних безпосередньо з характерними для Лемпеля-зіва ідеями. Важливий випадок, коли чисельна інформація набита цифрами. Наприклад: 132, -44.8, 555. Зрозуміло, що цифри можуть бути так перетасовані, що навіть однакові пари будуть украй рідкісні. Згадані методи не дають стиснення. Проте, якщо у фрагменті тексту використовуються всього 16 різних знаків, то кожен з них представляється чотирма бітами. А це вже двократне стиснення! Додаткові резерви можуть бути розкриті якщо текст - російською мовою і використовується не більше 64 знаків.
Можна виділяти в початковому файлі нестискувані ділянки. Тоді збиток від кожного з них можна понизити до 3 байтів. А в представленому варіанті кожен перенесений без змін символ тягне за собою однобайтну ознаку, тобто збиток 12.5%!
Проте викладений вище алгоритм не враховує такі деталі тому що вони відносно рідкісні, а ефект від них скромний.

Перелік джерел

1. Abraham Lempel(Wikipedia)
2. Jacob Ziv(Wikipedia)
3. ЛЕМПЕЛЬ-ЗИВ В ПЛАНЕ МИНИМИЗАЦИИ ПРОГРАММЫ
4. Архивация данных в MS DOS