оводячи періодичних перевірок, адміністратор не може бути впевнений у тому, що дійсно є резервні копії, з яких-небудь пізніше можна буде відновити дані.
4.3 Аналіз технологій стиснення даних
Основним завданням «Резервування даних користувача» є завдання вибору технології стиснення даних.
Технологія стиснення впливає на загальну продуктивність підсистеми.
У даному дипломному проекті були проаналізовані наступні технології стиснення даних:
алгоритм словникового стиснення Зива-Лемпела [27];
контекстне моделювання [27];
перетворення Барроуза - Уїлера [27].
Алгоритм словникового стиснення Зива-Лемпела (LZW). Даний алгоритм при стисканні (кодуванні) динамічно створює таблицю перетворення рядків: певних послідовностей символів (словами) ставляться у відповідність групи біт фіксованої довжини (зазвичай 12-бітові). Таблиця инициализируется усіма 1-символьними рядками (у разі 8-бітних символів - це 256 записів). У міру кодування, алгоритм переглядає текст символ за символом, і зберігає кожну нову, унікальну 2-символьний рядок в таблицю у вигляді пари код / ??символ, де код посилається на відповідний перший символ. Після того як нова 2-символьний рядок збережена в таблиці, на вихід передається код першого символу. Коли на вході читається черговий символ, для нього по таблиці знаходиться вже зустрічалася рядок максимальної довжини, після чого в таблиці зберігається код цього рядка з наступним символом на вході; на вихід видається код цього рядка, а наступний символ використовується в якості початку наступного рядка.
Алгоритму декодування на вході потрібно тільки закодований текст, оскільки він може відтворити відповідну таблицю перетворення безпосередньо по закодованого тексту.
На момент своєї появи алгоритм LZW давав кращий коефіцієнт стиснення, для більшості додатків, ніж будь-який інший добре відомий метод того часу. Він став першим широко використовуваним на комп'ютерах методом стиснення даних.
Алгоритм був реалізований у програмі compress, яка стала більш-менш стандартною утилітою Unix-систем приблизно в 1986 році. Кілька інших популярних утиліт-архіваторів також використовують цей метод або близькі до нього.
У 1987 році алгоритм став частиною стандарту на формат зображень GIF. Він також може (опціонально) використовуватися у форматі TIFF.
В даний час, алгоритм міститься в стандарті PDF.
Технологія контекстного моделювання (PPM). PPM (англ. Prediction by Partial Matching - пророкування щодо часткового збігу) - адаптивний статистичний алгоритм стиснення даних без втрат, заснований на контекстному моделюванні та прогнозі. Модель PPM використовує контекст - безліч символів в стислому потоці, що передують даному, щоб передбачати значення символу на основі статистичних даних. Сама модель PPM лише пророкує значення символу, безпосереднє стиск здійснюється алгоритмами ентропійного кодування, як наприклад, алгоритм Хаффмана, арифметичне кодування. Ось вже протягом півтора десятків років представники сімейства РРМ залишаються найбільш потужними практичними алгоритмами з точки зору ступеня стиснення. Найкращі результати алгоритми РРМ показують на текстах: відмінний ...
