коефіцієнт стиснення при високій швидкості, чому наочним прикладом є компресори PPMd і PPMonstr. Крім того, якщо стоїть завдання максимізації ступеня стиснення певних даних, то швидше за все РРМ-подібний алгоритм буде найкращим вибором в якості основи спеціа лизировать компресора.
Якщо вийти за рамки приватної проблеми стиснення даних, то безсумнівним гідністю РРМ є можливість отримання хорошої статистичної моделі обробленої послідовності якісних даних (або згенерувати її джерела). Дійсно, модель, що дозволяє ефективно пророкувати невідомі символи повідомлення, можна застосовувати не тільки для стиснення, але і для вирішення завдань корекції тексту в системах OCR, розпізнавання мови, класифікації типу тексту, семантичного аналізу тексту, шифрування.
Перетворення Барроуза - Уїлера (BWT). Технологія стиснення даних BWT заснована на перетворенні Барроуза - Уїлера.
Найважливішим завданням, що має бути вирішена для отримання швидкого алгоритму BWT, є завдання сортування рядків. При цьому слід врахувати, що деякі алгоритми сортування рядків вкрай залежні від «вдалості» вхідних даних, працюють швидко в більшості випадків, але вкрай сильно деградують в невдалих випадках.
Наприклад, така досить вдала в загальному випадку комбінація «bucket sort + qsort Седжвіка в кожній кошику» на вхідному тексті у вигляді довгої послідовності ABABABAB - bucket sort створить 2 корзини для A і B, заповнивши кожну майже повністю однаковими рядками, після чого qsort на такому наборі затягнеться майже назавжди.
У таких випадках доводиться переривати виконання «тривалого» алгоритму і переходити на інший алгоритм (radix sort), який гірше у вдалих випадках, але не схильний обвальної деградації.
Споживання пам'яті BWT компресором головним чином зводиться до буферу під нині сортируемое порцію вхідних даних, для хорошої якості компресії (гарної глибини аналізу) це одиниці мегабайт, що перевершує споживання пам'яті усіма іншими ланками компрессора.компрессор (gzip в максимальному режимі) трохи гірше за якістю стиснення і приблизно однаковий по швидкості, але споживає значно менше памяті.декомпрессор набагато швидше (лінійна швидкість) і не споживає значних обсягів пам'яті, що відрізняє його від алгоритмів PPM.
4.4 Вибір технології стиснення даних
Вибір методу - важливе завдання, яку повинен вирішити розробник програмних засобів стиснення даних. Вибір залежить від типу даних, які потрібно буде обробляти, апаратних ресурсів, вимог до ступеня стиснення і обмежень на час роботи програми.
Перш за все, слід враховувати, що кожна з розглянутих технологій стиснення даних допускає модифікації, що дозволяють істотно змінити параметри компресора. Так, збільшення порядку моделі РРМ призводить до помітного посилення стиснення ціною уповільнення роботи і збільшення витрати пам'яті. До аналогічного результату приводить збільшення розміру словника LZ77-Meтодов, але при цьому час разжатия залишається практично незмінним. Властивості компресорів на основі BWT варіюються в меншому ступені.
Обмеження на час роботи програми виникають в залежності від умов, в яких належить працювати архіватору. При резервному збереженні даних стан речей назад, оскільки ситуація, коли потрібно виконати разжатие, досить рідкісна....
