[1] .00. 01.00.01101400P [4]=P [2] .10. 01.00.011.015011P [5]=P [1] .10. 01.00. 011.01 [0] - порожній рядок. Символом «. »(Точка) позначається операція об'єднання (конкатенації).
Формуємо пари рядків, кожен з яких має вигляд (AB). Кожна пара утворює нову фразу і містить ідентифікатор попередньої фрази і біт, що приєднується до цієї фрази. Об'єднання всіх цих пар являє остаточний результат стиснення С. P [1]=P [0] .0 дає (00.0), P [2]=P [1] .0 дає (01.0) і т.д. Схема перетворення відображена в таблиці нижче.
ФормулыP[1]=P[0].0P[2]=P[1].1P[3]=P[1].0P[4]=P[2].1P[5]=P[1].1Пары00.0=00001.1=01101.0=01010.1=10101.1=011С000.011.010.101.011 =000011010101011
Всі формули, що містять P [0] зовсім не дають стиснення. Очевидно, що С длиннее U, але це виходить для короткої вихідної послідовності. У разі матеріалу більшого обсягу буде отримано реальне стиснення вихідної послідовності.
Локально адаптивний алгоритм стиснення
Цей алгоритм використовується для кодування (L, I), де L рядок довжиною N, а I - індекс. Це кодування містить у собі кілька етапів.
. Спочатку кодується кожен символ L з використанням локально адаптивного алгоритму для кожного із символів індивідуально. Визначається вектор цілих чисел R [0], ..., R [N - 1], який являє собою коди для символів L [0], ..., L [N - 1]. Ініціалізується список символів Y, який містить в собі кожен символ з алфавіту Х тільки один раз. Для кожного i=0, ..., N - 1 встановлюється R [i] дорівнює кількості символів, що передують символу L [i] зі списку Y. Взявши Y=[a, b, c, r] в якості вихідного і L=caraab, обчислюємо вектор R: (2 1 3 1 0 3).
. Застосовуємо алгоритм Хафмана або інший аналогічний алгоритм стиснення до елементів R, розглядаючи кожен елемент як об'єкт для стиснення. У результаті виходить код OUT і індекс I.
Розглянемо процедуру декодування отриманого стислого тексту (OUT, I).
Тут на основі (OUT, I) необхідно обчислити (L, I). Передбачається, що список Y відомий.
1. Спочатку обчислюється вектор R, що містить N чисел: (2 1 3 1 0 3).
2. Далі обчислюється рядок L, що містить N символів, що дає значення R [0], ..., R [N - 1]. Якщо необхідно, инициализируется список Y, що містить символи алфавіту X (як і при процедурі кодування). Для кожного i=0, ..., N - 1 послідовно встановлюється значення L [i], рівне символу в положенні R [i] зі списку Y (нумерується, починаючи з 0), потім символ зсувається до початку Y. Результуюча рядок L являє собою останню колонку матриці M. Результатом роботи алгоритму буде (L, I). Взявши Y=[a, b, c, r] обчислюємо рядок L=caraab.
Найбільш важливим фактором, що визначає швидкість стиснення, є час, необхідний для сортування обертань у вхідному блоці. Найбільш швидкий спосіб вирішення проблеми полягає в сортуванні пов'язаних рядків по суффиксам.
Для того щоб стиснути рядок S, спочатку сформуємо рядок S, яка є об'єднанням S c EOF, новим символом, який не зустрічається в S. Після цього використовується стандартний алгоритм до рядка S. Так як EOF відрізняється від інших символів в S, суфікси S сортуються в тому ж порядку, як і обертання S. Це може бути зроблено шляхом побудови дерева суфіксів, яке може бути потім обійдено в лексикографічному порядку для сортування суфіксів. Для цієї мети може бути використаний алгоритм формування дерева суфіксів Мак-Крейгта. Його швидкодія становить 40% від найбільш швидкої методики в разі роботи з текстами. Алгоритм роботи з деревом суфіксів вимагає більше чотирьох слів на кожен вихідний символ. Манбер і Майерс запропонували простий алгоритм сортування суфіксів рядка. Цей алгоритм вимагає тільки двох слів на кожен вхідний символ. Алгоритм працює спочатку з першими i символами суфікса а за тим, використовуючи положення суфіксів в сортованому масиві, робить сортування для перших 2i символів. На жаль цей алгоритм працює помітно повільніше.
Стиснення даних з використанням перетворення Барроуза-Вилера
Майкл Барроуз і Давид Вілер (Burrows-Wheeler) в 1994 році запропонували свій алгоритм перетворення (BWT). Цей алгоритм працює з блоками даних і забезпечує ефективне стиснення без втрати інформації. У результаті перетворення блок даних має ту ж довжину, але інший порядок розташування символів. Алгоритм тим ефективніше, чим більший блок даних перетвориться (наприклад, 256-512 Кбайт).
Послідовність S, що містить N символів ({S (0), ... S (N - 1)}), піддається N циклічним зрушенням (обертання), лексикографічної сортуванню, а останній символ при кожному обертанні витягується. З цих символів формується рядок L, де i-ий символ є останнім символом ...
