Мне нужно выполнить известное преобразование Берроуза-Уилера за линейное время. Я нашел решение с сортировкой по суффиксу и символом EOF, но добавление EOF меняет преобразование. Например: рассмотрим строку bcababa и два поворота
abababcababcabясно, что s1 ‹ s2. Теперь с символом EOF:
и теперь s2 ‹ s1. И результирующая трансформация будет другой. Как я могу выполнить BWT без EOF?
Вы можете выполнить преобразование в линейном времени и пространстве без символа EOF, вычислив массив суффиксов строки, объединенной с самой собой. Затем переберите массив суффиксов. Если текущее значение массива суффиксов меньше n, добавьте в выходной массив последний символ вращения, начиная с позиции, обозначенной текущим значением в массиве суффиксов. Однако этот подход приведет к немного другому результату преобразования BWT, поскольку повороты строк не сортируются, как если бы присутствовал символ EOF.
Более подробное описание можно найти здесь: http://www.quora.com/Algorithms/How-I-can-optimize-burrows-wheeler-transform-and-inverse-transform-to-work-в-O-n-времени-O-n-пространстве
ptr: 13, string: "CTAAAACACGAGA\0GATGCAGGTATTTTATGTTAGTGATGCATTTTATGGCTCCCCGAGCATATC" Используя метод конкатенации ввода, я получаю, ptr: 12, str: "TAAAACACGAGACGATGCGGATATTTTATGTTAGTGATGCATTTTATGGCTCCCCGAGCATATC" Даже если мы проигнорируем терминатор NUL, вывод все равно будет другим.
- person DSnet; 24.11.2015
Вам нужно иметь символ EOF в строке для работы BWT, потому что в противном случае вы не сможете выполнить обратное преобразование, чтобы вернуть исходную строку. Без EOF обе строки «ba» и «ab» имеют одинаковую преобразованную версию («ba»). С EOF преобразования отличаются
ab ba
a b | a | b
b | a b a |
| a b | b a
то есть ab преобразуется в «|ab», а ba в «b|a».
EOF необходим для BWT, потому что он отмечает точку, в которой начинается символьный цикл.
Re: делать это без символа EOF, согласно Википедии,
Поскольку любое вращение входной строки приведет к одной и той же преобразованной строке, BWT нельзя инвертировать без добавления маркера EOF к входным данным или добавления к выходным данным информации, такой как индекс, который позволяет идентифицировать входная строка из класса всех ее вращений.
Существует биективная версия преобразования, при которой преобразованная строка однозначно идентифицирует оригинал. В этой версии каждая строка имеет уникальную инверсию той же длины.
Биективное преобразование вычисляется путем разложения входных данных на невозрастающую последовательность слов Линдона; такая факторизация существует по теореме Чена – Фокса – Линдона и может быть найдена за линейное время. Затем алгоритм сортирует все повороты всех этих слов; как и в обычном преобразовании Берроуза-Уилера, это дает отсортированную последовательность из n строк. Затем преобразованная строка получается путем выбора последнего символа каждой из этих строк в этом отсортированном списке.
Я знаю, что эта тема довольно старая, но у меня была такая же проблема, и я нашел следующее решение:
