Преобразование Барроуза – Уиллера

Преобразование Барроуза – Уиллера (BWT, также называемое сжатием с сортировкой блоков ) переупорядочивает строку символов на серии одинаковых символов. Это полезно для сжатия, так как обычно легко сжимать строку, содержащую повторяющиеся символы, с помощью таких методов, как преобразование с перемещением на передний план и кодирование длин серий. Что еще более важно, преобразование является обратимым, без необходимости хранить какие-либо дополнительные данные, кроме позиции первого исходного символа. Таким образом, BWT представляет собой «бесплатный» метод повышения эффективности алгоритмов сжатия текста, требующий лишь некоторых дополнительных вычислений.

• 1 Описание
• 2 Пример
• 3 Объяснение
• 4 Оптимизация
• 5 Биективный вариант
• 6 Динамическое преобразование Барроуза – Уиллера
• 7 Пример реализации
• 8 BWT в биоинформатике
• 9 Ссылки
• 10 Внешние ссылки

Преобразование Барроуза – Уиллера - это алгоритм, используемый для подготовки данных для использования с сжатием данных, такие как bzip2. Его изобрели Майкл Берроуз и Дэвид Уиллер в 1994 году, когда Барроуз работал в DEC Systems Research Center в Пало-Альто, Калифорния. Он основан на ранее неопубликованном преобразовании, обнаруженном Уилером в 1983 году. Алгоритм может быть эффективно реализован с использованием массива суффиксов , что позволяет достичь линейной временной сложности.

Когда строка символов преобразуется BWT, преобразование меняет порядок символов. Если в исходной строке было несколько часто встречающихся подстрок, то в преобразованной строке будет несколько мест, где один символ повторяется несколько раз подряд.

Например:

Вывод легче сжать, потому что он содержит много повторяющихся символов. В этом примере преобразованная строка содержит шесть серий одинаковых символов: XX, SS, PP, .., IIи III, которые вместе составляют 13 из 44 символов.

Преобразование выполняется путем сортировки всех циклических сдвигов текста в лексикографическом порядке и извлечения последний столбец и индекс исходной строки в наборе отсортированных перестановок S.

. Учитывая входную строку S = ^ BANANA |(шаг 1 в таблице ниже), поверните ее N раз (шаг 2), где N = 8- длина строки S, учитывая также символ ^, представляющий начало строки и красный | символ, представляющий указатель 'EOF '; эти повороты или круговые сдвиги затем сортируются лексикографически (шаг 3). Результатом фазы кодирования является последний столбец L = BNN ^ AA | Aпосле шага 3 и индекс (на основе 0) Iстроки, содержащей исходную строку S, в данном случае I = 6.

^ BANANA |

^ БАНАН | | ^ BANANA A | ^ BANAN NA | ^ BANA ANA | ^ BAN NANA | ^ BA ANANA | ^ B BANANA | ^

ANANA | ^ B A NA | ^ BAN A | ^ BANAN B ANANA | ^ N ANA | ^ BA N A | ^ BANA ^ BANANA | | ^ BANANA

ANANA | ^ B ANA | ^ BA N A | ^ BANA N BANANA | ^ NANA | ^ B A NA | ^ BAN A ^ BANANA | | ^ BANAN A

BNN ^ AA | A

Следующие псевдокод дает простой (хотя и неэффективный) способ вычисления BWT и его обратного. Предполагается, что входная строка sсодержит специальный символ «EOF», который является последним символом и больше нигде в тексте не встречается.

функция BWT (строка s) создает таблицу, в которой строки представляют собой все возможные вращения строк s сортировки по алфавиту return (последний столбец таблицы)

function inverseBWT (string s) create empty table repeat length (s) times // первая вставка создает первый столбец insert s как столбец таблицы перед первым столбцом таблицы сортировать строки таблицы по алфавиту return (строка, заканчивающаяся символом 'EOF')

.

Чтобы понять, почему это создает более легко сжимаемые данные, рассмотрите возможность преобразования длинного английского текста, часто содержащего слово "the". Сортировка поворотов этого текста будет группировать повороты, начинающиеся с «он» вместе, и последним символом этого поворота (который также является символом перед «он») обычно будет «t», поэтому результат преобразования будет содержать количество символов "t" вместе с возможно менее распространенными исключениями (например, если он содержит "Brahe") смешано. Таким образом, можно видеть, что успех этого преобразования зависит от одного значения, имеющего высокую вероятность появления раньше последовательность, так что, как правило, требуются довольно длинные выборки (как минимум несколько килобайт) соответствующих данных (например, текста).

Примечательность BWT заключается не в том, что он генерирует более легко кодируемые выходные данные - это делает обычная сортировка, - а в том, что он делает это обратимо, позволяя повторно сгенерировать исходный документ из последнего столбца данные.

Таким образом можно понять обратное. Возьмите последнюю таблицу в алгоритме BWT и сотрите все столбцы, кроме последнего. Имея только эту информацию, вы можете легко восстановить первый столбец. В последнем столбце указаны все символы в тексте, поэтому просто отсортируйте эти символы по алфавиту, чтобы получить первый столбец. Затем последний и первый столбцы (каждой строки) вместе дают вам все пары следующих друг за другом символов в документе, причем пары берутся циклически, так что последний и первый символы образуют пару. Сортировка списка пар дает первый и второй столбцы. Продолжая таким образом, вы можете восстановить весь список. Тогда строка с символом «конец файла» в конце и будет исходным текстом. Обратное преобразование приведенного выше примера выполняется следующим образом:

BNN ^ AA | A

BNN ^ AA | A

A A A B N N ^ |

BA NA NA ^ B AN AN | ^ A |

АН АН А | BA NA NA ^ B | ^

BAN NAN NA | ^ BA ANA ANA | ^ B A | ^

ANA ANA A | ^ БАН НАН НА | ^ BA | ^ B

БАНА НАНА НА | ^ ^ БАН АНАН АНА | | ^ BA A | ^ B

АНАН АНА | A | ^ B BANA NANA NA | ^ ^ BAN | ^ BA

BANAN NANA | NA | ^ B ^ BANA ANANA ANA | ^ | ^ BAN A | ^ BA

ANANA ANA | ^ A | ^ BA BANAN NANA | NA | ^ B ^ BANA | ^ BAN

BANANA NANA | ^ NA | ^ BA ^ BANAN ANANA | АНА | ^ В | ^ БАНА А | ^ БАН

АНАНА | ANA | ^ BA | ^ BAN BANANA NANA | ^ NA | ^ BA ^ BANAN | ^ BANA

БАНАН | NANA | ^ B NA | ^ BAN ^ BANANA ANANA | ^ ANA | ^ BA | ^ BANAN A | ^ BANA

ANANA | ^ ANA | ^ BA A | ^ BANA BANANA | NANA | ^ B NA | ^ BAN ^ BANANA | ^ BANAN

BANANA | ^ NANA | ^ BA NA | ^ BANA ^ BANANA | ANANA | ^ B ANA | ^ BAN | ^ BANANA A | ^ BANAN

ANANA | ^ B ANA | ^ BAN A | ^ BANAN BANANA | ^ NANA | ^ BA NA | ^ BANA ^ BANANA | | ^ BANANA

^ BANANA |

Ряд оптимизаций может повысить эффективность этих алгоритмов без изменения вывода. Нет необходимости представлять таблицу ни в кодировщике, ни в декодере. В кодировщике каждая строка таблицы может быть представлена ​​одним указателем на строки, и сортировка выполняется с использованием индексов. Необходимо проявлять некоторую осторожность, чтобы гарантировать, что сортировка не демонстрирует плохого худшего случая поведения: стандартные библиотечные функции сортировки вряд ли будут подходящими. В декодере тоже нет необходимости хранить таблицу, да и сортировка вообще не нужна. За время, пропорциональное размеру алфавита и длине строки, декодированная строка может генерироваться по одному символу справа налево. «Символ» в алгоритме может быть байтом, битом или любым другим удобным размером.

Можно также сделать наблюдение, что математически закодированная строка может быть вычислена как простая модификация массива суффиксов , а массивы суффиксов могут быть вычислены с линейным временем и памятью. BWT можно определить по отношению к массиву суффиксов SA текста T как (индексирование на основе 1):

$BWT\; [i]\; =\; \{T\; [SA\; [i]\; -\; 1],\; если\; SA\; [i]>0\; \$,\; иначе\; \{\backslash \; displaystyle\; BWT\; [i]\; =\; \{\backslash \; begin\; \{case\}\; T\; [SA\; [i]\; -1],\; \{\backslash \; text\; \{if\}\}\; SA\; [i]>0\; \backslash \backslash \backslash \; \$,\; \{\backslash \; text\; \{\; в\; противном\; случае\}\}\; \backslash \; end\; \{cases\}\}\}$

Нет необходимости иметь фактический символ 'EOF'. Вместо этого, может использоваться указатель, который запоминает, где в строке был бы EOF, если бы он существовал. В этом подходе выходные данные BWT должны включать как преобразованную строку, так и окончательное значение указателя. Затем обратное преобразование сжимает его вернуться к исходному размеру: ему дается строка и указатель, и он возвращает только строку.

Полное описание алгоритмов можно найти в статье Берроуза и Уиллера или в ряде онлайн-источников. Че Алгоритмы несколько различаются в зависимости от того, используется ли EOF и в каком направлении производилась сортировка. Фактически, в исходной формулировке маркер EOF не использовался.

Поскольку любое вращение входной строки приведет к такой же преобразованной строке, BWT не может быть инвертирован без добавления Маркер EOF до конца ввода или выполнение чего-то эквивалентного, позволяющего отличить строку ввода от всех ее поворотов. Увеличение размера алфавита (путем добавления символа EOF) затрудняет последующие шаги сжатия.

Существует биективная версия преобразования, с помощью которой преобразованная строка однозначно идентифицирует оригинал, а две имеют одинаковую длину и содержат точно такие же символы, только в другом порядке.

Биективное преобразование вычисляется путем факторизации входных данных в невозрастающую последовательность слов Линдона ; такая факторизация существует и уникальна по теореме Чена – Фокса – Линдона и может быть найдена за линейное время. Алгоритм сортирует вращение всех слов; как и в преобразовании Барроуза-Уиллера, это дает отсортированную последовательность из n строк. Затем преобразованная строка получается путем выбора последнего символа каждой строки в этом отсортированном списке. Одно важное предостережение здесь заключается в том, что строки разной длины не располагаются обычным образом; две строки повторяются бесконечно, а бесконечные повторения сортируются. Например, «ORO» предшествует «OR», потому что «OROORO...» предшествует «OROROR...».

Например, текст «^ BANANA |» преобразуется в "ANNBAA ^ |" через эти шаги (красный символ | указывает на указатель EOF ) в исходной строке. Символ EOF не нужен в биективном преобразовании, поэтому он отбрасывается во время преобразования и повторно добавляется на свое место в файле.

Строка разбита на слова Линдона, поэтому слова в последовательности уменьшаются с использованием метода сравнения, описанного выше. (Обратите внимание, что мы сортируем '^' как следующие за другими символами.) «^ BANANA» становится (^) (B) (AN) (AN) (A).

^ БАНАН |

^^^^^^^^... (^) B BBBBBBB... (B) ANAN ANAN... (AN) NANA NANA... (NA) ANAN ANAN... (AN) NANA NANA... (NA) A AAAAAAA... (A)

AAAAAAAA... (A) A NANANAN... (AN) A NANANAN... (AN) B BBBBBBB... ( B) N АНАНАНА... (NA) N ANANANA... (NA) ^ ^^^^^^^... (^)

AAAAAAAA... (A ) A N ANANAN... (A N ) A N ANANAN... (A N) BBBBBBBB... (B ) N A NANANA... (N A ) N A NANANA... (N A) ^^^^^^^^... (^)

ANNBAA ^ |

ANNBAA ^

ANNBAA ^

AAABNN ^

AA NA NA NA BB AN AN ^^

AA AN AN BB NA NA ^^

AAA NAN NAN BBB ANA ANA ^^^

AAA ANA ANA BBB NAN NAN ^^^

AAAA NANA NANA BBBB ANAN ANAN ^^^^

AAAA ANAN ANAN BBBB NANA NANA ^^^^

^ BANANA

До последнего шага процесс идентичен обратному процессу Барроуза-Уиллера, но здесь он не обязательно дает вращения одной последовательности; вместо этого он дает ротацию слов Линдона (которые начнут повторяться по мере продолжения процесса). Здесь мы можем видеть (повторения) четырех различных слов Линдона: (A), (AN) (дважды), (B) и (^). (NANA... не представляет собой отдельное слово, поскольку это цикл ANAN....) На этом этапе эти слова отсортированы в обратном порядке: (^), (B), (AN), ( АН), (А). Затем они объединяются, чтобы получить

^ BANANA

Преобразование Барроуза-Уиллера действительно можно рассматривать как частный случай этого биективного преобразования; вместо традиционного введения новой буквы из-за пределов нашего алфавита для обозначения конца строки мы можем ввести новую букву, которая сравнивается как предшествующая всем существующим буквам, помещенная в начало строки. Вся строка теперь является словом Линдона, и ее выполнение через биективный процесс, следовательно, приведет к преобразованному результату, который при инвертировании возвращает слово Линдона без необходимости повторной сборки в конце.

Соответственно, преобразованный текст будет отличаться от результата BWT только на один символ на слово Lyndon; например, если ввод разложен на шесть слов Линдона, вывод будет отличаться только шестью символами. Например, применение биективного преобразования дает:

Биективное преобразование включает восемь прогонов идентичных символов. Эти прогоны идут в следующем порядке: XX, II, XX, PP, .., EE, ..и IIII.

Всего в этих прогонах используется 18 символов.

Когда текст редактируется, его преобразование Барроуза – Уиллера изменяется. Salson et al. предложить алгоритм, который выводит преобразование Барроуза-Уиллера отредактированного текста из исходного текста, выполняя ограниченное количество локальных переупорядочений в исходном преобразовании Барроуза-Уиллера, что может быть быстрее, чем построение преобразования Барроуза-Уиллера отредактированного текста. текст напрямую.

Эта реализация Python жертвует скоростью ради простоты: программа короткая, но требует больше, чем линейное время, которое было бы желательно при практической реализации. По сути, он делает то же, что и раздел псевдокода.

Использование управляющих кодов STX / ETX для обозначения начала и конца текста и использование s [i:] + s [: i]для построения i-й поворот s, прямое преобразование принимает последний символ каждой из отсортированных строк:

def bwt (s: str) ->str: "" " Примените преобразование Барроуза – Уиллера к входной строке. "" "Assert" \ 002 "не в s и" \ 003 "не в s," Входная строка не может содержать символы STX и ETX "s =" \ 002 "+ s +" \ 003 "# Добавить начало и конец таблицы текстовых маркеров = sorted (s [i:] + s [: i] for i in range (len (s))) # Таблица поворотов строки last_column = [row [-1: ] для строки в таблице] # Последние символы каждой строки возвращают "".join (last_column) # Преобразование списка символов в строку

Обратное преобразование неоднократно вставляет rв качестве левого столбца таблицы и сортирует таблицу. После того, как вся таблица построена, она возвращает строку, которая заканчивается на ETX, за вычетом STX и ETX.

def ibwt (r: str) ->str: "" "Применить обратное преобразование Барроуза – Уиллера." "" Table = [""] * len (r) # Сделать пустую таблицу для i в диапазоне (len (r)): table = sorted (r [i] + table [i] for i in range (len (r))) # Добавить столбец rs = [строка для строки в таблице, если row.endswith ("\ 003") ] [0] # Найдите правильную строку (оканчивающуюся на ETX) return s.rstrip ("\ 003"). Strip ("\ 002") # Избавьтесь от маркеров начала и конца

В соответствии с примечаниями к реализации от Manzini, это эквивалентно использованию вместо него простого суффикса нулевого символа. Сортировка должна выполняться в колексикографическом порядке (строка читается справа налево), т.е. sorted (..., key = lambda s: s [:: - 1])в Python. (Вышеупомянутые управляющие коды фактически не удовлетворяют тому, что EOF является последним символом; два кода фактически являются первыми. Тем не менее, вращение сохраняется.)

Появление методы секвенирования следующего поколения (NGS) в конце 2000-х годов привели к другому применению преобразования Барроуза-Уиллера. В NGS ДНК фрагментируется на маленькие кусочки, из которых первые несколько оснований секвенированы, давая несколько миллионов «прочтений», каждая из которых составляет от 30 до 500 пар оснований («Символы ДНК») длинные. Во многих экспериментах, например, в ChIP-Seq, задача теперь состоит в том, чтобы выровнять эти считывания с эталонным геномом, то есть с известной, почти полной последовательностью рассматриваемого организма. (которые могут иметь длину до нескольких миллиардов пар оснований). Был опубликован ряд программ выравнивания, специализированных для этой задачи, которые изначально полагались на хеширование (например, SOAP или). В попытке уменьшить требования к памяти для выравнивания последовательностей было разработано несколько программ выравнивания (Bowtie, BWA и SOAP2), в которых используется преобразование Барроуза-Уиллера.

• Статья Марка Нельсона о BWT
• Биективное преобразование сортировки строк, Гил и Скотт
• openbwt-v1.5.zip Юты содержит исходный код для различных подпрограмм BWT, включая BWTS для биективной версии
• О биективных вариантах преобразования Барроуза-Уиллера, автор Куфлейтнер
• сообщение в блоге и страница проекта для сжатия с открытым исходным кодом программа и библиотека, основанные на алгоритме Барроуза-Уиллера
• Открытая лекция MIT по BWT (Основы вычислительной и системной биологии)
• Сортировка по таблице рейтингов (LTS) или алгоритм взвешивания для BWT Абдеррахима Хечачена (утверждает чтобы быть быстрее, но правильность не доказана)