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