Изменения
Нет описания правки
==Описание==
Здесь представлен алгоритм, обратный алгоритму [[Преобразование Барроуза-Уиллера]]. На вход алгоритму подается шифр строки <tex> s </tex>, зашифрованный методом Барроуза-Уиллера, и номер исходной строки в отсортированной матрице, полученной в конце преобразования. Обратное преобразование возвращает исходную строку <tex> s </tex>.
==Наивный алгоритмНаивная реализация=====ОписаниеСуть алгоритма===Если отсортировать символы последнего столбца матрицы перестановок — а перед началом обратного преобразования нам известен только он — то мы получим первый столбец данной матрицы,так как строки матрицы были отсортированы в лексикографическом порядке.
Известно, что символы последнего столбца предшествуют символам первого, находящимся в той же строке, поскольку использовался циклический сдвиг. Таким образом, мы имеем уже список пар, состоящих из символа последнего столбца и следующего за ним символа первого столбца. После сортировки этих пар мы обретаем знание о двух первых столбцах матрицы. И так далее, пока мы не получим всю матрицу перестановок, на каждом шаге новый префикс получается в результате конкатенации последнего символа и соответствующего ему префикса. В результате получаем матрицу, содержащую все циклические сдвиги, откуда выписываем строку с заданным номером. Рассмотрим этот алгоритм на конкретном примере. Пусть дана строка "абракадабра". В результате преобразования получаем набор ("рдакраааабб", 3).
{|
===Псевдокод===
Пусть <tex> N </tex> — количество символов во входной строке, <tex> M </tex> — количество символов в алфавите, <tex> k </tex> — номер исходной строки в матрице перестановок, <tex> s </tex> — входящая строка, <tex> count </tex> — массив для сортировки подсчетом, <tex> t </tex> — вектор обратного преобразования, <tex> x - </tex> — номер данной нам строки в таблице.
// Cчитаем частоты символов
