Обратный BWT, не зная последний символ

Обычно в алгоритме преобразования Берроуза-Уилера символ $ используется для обозначения конца строки, но во многих случаях этот $ опускается.

Мне было интересно, как его можно повернуть вспять, не зная позиции последнего персонажа?

Например, у меня есть этот BWT:

[[[[[1 [[11endgnad1234245ndbnbbb]]]]]]] nnnngnabbbdiaaaiaaii

Следуя алгоритму, я могу легко построить первый столбец матрицы BWT, который я выбрал для представления сжатым способом, как показано ниже:

Character : Occurrences
1         : 4
2         : 2
3         : 1
4         : 2
5         : 1
[         : 7
]         : 7
a         : 7
b         : 7
d         : 4
e         : 1
g         : 2
i         : 4
n         : 9

Не зная, какой символ является последним в исходной строке, я не могу понять, как я мог восстановить исходную строку.

Любая помощь с благодарностью.
Танг

P / S: На случай, если вам интересно, что такое оригинальная строка:

[1] запрет [2] банан [3] группа [4] повязка [12] бен [14] связывает [15] связывание

1

Решение

Вы не можете (но вы можете попробовать ;-).
Ваш первый символ bwt является последним в исходной строке ‘S’.
Теперь вам нужно развернуть исходную строку в обратном направлении через LF mapping.
На самом деле это bin [sym] + rank (sym, i) + 1, где вы начинаете с i = 0.
Вы можете легко получить массив bin [] по вхождениям.
Проблема в том, что как только ваше ‘i’ больше, чем пропущено ‘$’, вы не должны добавлять эту последнюю ‘1’, чтобы разбить строку и все пошло не так.
Вы можете обнаружить ошибку, если вы также восстановите sa [] и перезапишите уже установленный индекс. Таким образом, вы можете установить произвольную позицию $ в ‘0’ и попытаться восстановить, затем, если она не удастся, установите ее в 1 …, пока вы не восстановите правильно. не знаю, можно ли это оптимизировать.

Ура,

D.

1

Другие решения

Других решений пока нет …