Обратное преобразование Барроуза-Уилера

Question

Я реализовал прямое преобразование преобразования Берроуза-Уилера (BWT). Теперь проблема в том, что я не могу понять обратное.

Рассмотрим р:

p = [3 2 5 3 1 4 2 6]

Форвард BWT:

fbwt = [3 3 4 5 6 1 2 2]
index = 5

Обратный путь:

Пожалуйста, кто-нибудь, помогите мне.

Answer 1

Посмотрите на все столбцы с именем a, Заметьте, как первая цифра, когда вы смотрите вниз на столбец, является преобразованной последовательностью? Взгляните на столбец a на i=1. Это оригинальная последовательность, затем она сортируется в столбце b. Тогда для i=2столбец a это столбец b от i=1, с преобразованной последовательностью в начале. Они сортируются снова и помещаются в столбец b, Это повторяется, затем вы используете индекс для поиска строки, которую нужно прочитать из таблицы. Что касается столбца cвы заметите, что это просто столбец b с добавлением оригинального преобразования.