i-го обертання. Крім рядки L створюється індекс I початкового рядка S у впорядкованому списку обертань. Існує ефективний алгоритм відновлення вихідної послідовності символів S на основі рядка L та індексу I. Процедура сортування об'єднує результати обертань з ідентичними початковими символами. Передбачається, що символи в S відповідають алфавітом, який містить K символів.
Для пояснення роботи алгоритму візьмемо послідовність S=abraca (N=6), алфавіт X={a, b, c, r}.
. Формуємо матрицю з N * N елементів, чиї рядки являють собою результати циклічного зсуву (обертань) вихідної послідовності S, відсортованих лексикографічно. Принаймні один з рядків M містить вихідну послідовність S. Нехай I є індексом рядки S. У наведеному прикладі індекс I=1, а матриця M має вигляд:
Номер строкі0aabrac1abraca2acaabr3bracaa4caabra5racaab
. Нехай рядок L являє собою останню колонку матриці M з символами L [0], ..., L [N - 1] (відповідають M [0, N - 1], ..., M [N - 1, N - 1]). Формуємо рядок останніх символів обертань. Остаточний результат характеризується (L, I). У даному прикладі L=caraab, I=1.
Процедура декомпресії використовує L і I. Метою цієї процедури є отримання вихідної послідовності з N символів (S).
. Спочатку обчислюємо першу шпальту матриці M (F). Це робиться шляхом сортування символів рядка L. Кожна колонка вихідної матриці M являє собою перестановки вихідної послідовності S. Таким чином, перша колонка F і L є перестановками S. Так як рядки в M впорядковані, розміщення символів в F також упорядковано. F=aaabcr.
. Розглядаємо ряди матриці M, які починаються з заданого символу ch. Рядки матриці М впорядковані лексикографічно, тому рядки, що починаються з ch впорядковані аналогічним чином. Визначимо матрицю M, яка виходить з рядків матриці M шляхом циклічного зсуву на один символ вправо. Для кожного i=0, ..., N - 1 і кожного j=0, ..., N - 1, M [i, j]=m [i, (j - 1) mod N]
У розглянутому прикладі M і M мають вигляд
СтрокаMM 0aabraccaabra1abracaaabraс2acaabrracaab3bracaaabraca4caabraacaabr5racaabbracaa
Подібно M кожен рядок M є обертанням S, і для кожного рядка M існує відповідна рядок M. M отримана з M так, що рядки M впорядковані лексикографічно, починаючи з другого символу. Таким чином, якщо ми розглянемо тільки ті рядки M, які починаються з заданого символу ch, вони повинні слідувати впорядкованим чином з урахуванням другому символу. Отже, для будь-якого заданого символу ch, рядки M, які починаються з ch, з'являються в тому ж порядку що і в M, що починаються з ch. У нашому прикладі це видно на прикладі рядків, що починаються з a. Рядки aabrac, abraca і acaabr мають номери 0, 1 і 2 в M і 1, 3, 4 в M.
Використовуючи F і L, перші колонки M і M ми обчислимо вектор Т, який вказує на відповідність між рядками двох матриць, з урахуванням того, що для кожного j=0, ..., N - 1 рядка j M відповідають рядкам T [j] M.
Якщо L [j] є к-им появою ch в L, тоді T [j]=1, де F [i] є к-им появою ch в F. Зауважте, що Т представляє відповідність один в один між елементами F і елементами L, а F [T [j]]=L [j]. У нашому прикладі T одно: (4 0 5 1 2 3).
. Тепер для кожного i=0, ..., N - 1 символи L [i] і F [i] є відповідно останніми і першими символами рядка i матриці M. Так як кожна рядок є обертанням S, символ L [i] є циклічним попередником символу F [i] в ??S. З Т ми маємо F [T [j]]=L [j]. Підставляючи i=T [j], ми отримуємо символ L [T (j)], який циклічно передує символу L [j] в S.
Індекс I вказує на рядок М, де записаний рядок S. Таким чином, останній символ S дорівнює L [I]. Ми використовуємо вектор T для отримання попередників кожного символу: для кожного i=0, ..., N - 1 S [N - 1-i]=L [Ti [I]], де T0 [x]=x, а Ti + 1 [x]=T [Ti [x]. Ця процедура дозволяє відновити первинну послідовність символів S (abraca).
Послідовність Ti [I] для i=0, ..., N - 1 не обов'язково є перестановкою чисел 0, ..., N - 1. Якщо вихідна послідовність S є формою Zp для деякої підстановки Z і для деякого p gt; 1, тоді послідовність Ti [I] для i=0, ..., N - 1 буде також формою Z p для деякої субпоследовательності Z. Таким чином, якщо S=cancan, Z=can і p=2, послідовність Ti [I] для i=0, ..., N - 1 буде [2,4,0,2,4,0].
Описаний вище алгоритм впорядковує обертання вихідної послідовності символів S і формує рядок L, що складається з останніх символів обертань. Для того, щоб зрозуміти, чому таке впорядкування призводить до більш ефективного стиску, розглянемо вплив на окрему букву в звичайному слові англійського тексту.
Візьмемо як приклад букву t в слові the і припустимо, що початкова послідовн...
