Алгоритм Лемпеля-Зіва
| {{{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 рядків. Ядро коду стиснення займає не більше сотні рядків, а коду декомпресії не набагато більше. Програмісти вважають, що це полегшує читання і розуміння алгоритму, а також дозволяє адаптувати його для самих різних цілей.
