Delphi. Трохи щодо методів упаковки даних
Running - Це найпростіший з методів упаковки інформації. Припустімо що Ви маєте рядок тексту, і в кінці рядка коштує 40 прогалин. Це явна надмірність наявної інформації. Проблема стиснення цього рядка вирішується дуже просто - ці 40 пробілів (40 байт) стискаються в 3 байти за допомогою упаковки їх за методом повторюваних символів (running). Перший байт, що стоїть замість 40 прогалин у стислій рядку, фактично буде явлться пропуском (послідовність була з пробілів). Другий байт - спеціальний байт "прапорця" який вказує що ми повинні розгорнути попередній у рядку байт в послідовність при відновленні рядка. Третій байт - байт рахунку (у нашому випадку це буде 40). Як Ви самі можете бачити, достатньо щоб будь раз, коли ми маємо послідовність з більше 3-х однакових символів, замінювати їх вище описаної послідовністю, щоб на виході отримати блок інформації менший за розміром, але допускає відновлення інформації в початковому вигляді.
Залишаючи все сказане вище істинним, додам лише те, що в даному методі основний проблемою є вибір того самого байта "прапорця", так як у реальних блоках інформації як правило використовуються всі 256 варіантів байта і немає можливості мати 257 варіант - "прапорець". На перший погляд ця проблема здається нерозв'язною, але до неї є ключик, який Ви знайдете прочитавши про кодування за допомогою алгоритму Гоффмана (Huffman).
LZW - Історія цього алгоритму починається з опублікування в травні 1977 Дж. Зівом ( J. Ziv) і А. Лемпелем (A. Lempel) статті в журналі "Інформаційні теорії "під назвою" IEEE Trans ". Надалі цей алгоритм був доопрацьований Террі А. Велчем (Terry A. Welch) і в остаточному варіанті відображено у статті "IEEE Compute" у червні 1984. У цій статті описувалися подробиці алгоритму і деякі загальні проблеми з якими можна
зіткнутися при його реалізації. Пізніше цей алгоритм отримав назву - LZW (Lempel - Ziv - Welch). p> Алгоритм LZW являє собою алгоритм кодування послідовностей неоднакових символів. Візьмемо для прикладу рядок "Об'єкт TSortedCollection породжений від TCollection. ". Аналізуючи цей рядок ми можемо бачити, що слово "Collection" повторюється двічі. У цьому слові 10 символів - 80 біт. І якщо ми зможемо замінити це слово у вихідному файлі, у другому його включенні, на посилання на перше включення, то отримаємо стиснення інформації. Якщо розглядати вхідний блок інформації розміром не більше 64К і обмежиться довгою кодируемой рядка в 256 символів, то враховуючи байт "прапор" отримаємо, що рядок з 80 біт замінюється 8 +16 +8 = 32 біта. Алгоритм LZW як-би "навчається" у процесі стиснення файлу. Якщо існують повторювані рядки у файлі, то вони будуть закодованість в таблицю. Очевидною перевагою алгоритму є те, що немає необхідності включати таблицю кодування в стислий файл. Іншою важливою особливістю є те, що стиснення за алгоритмом LZW є однопрохідної операцією на противагу алгоритму Гоффмана (Huffman...
