stringtranslate.com

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

Преобразование Барроуза -Уиллера ( BWT , также называемое сжатием сортировки блоков ) перестраивает строку символов в серии похожих символов. Это полезно для сжатия, поскольку, как правило, легко сжать строку, которая имеет серии повторяющихся символов, с помощью таких методов, как преобразование перемещения вперед и кодирование длины серии . Что еще более важно, преобразование обратимо , без необходимости хранить какие-либо дополнительные данные, кроме позиции первого исходного символа. Таким образом, BWT является «бесплатным» методом повышения эффективности алгоритмов сжатия текста, требующим лишь некоторых дополнительных вычислений. Преобразование Барроуза-Уиллера — это алгоритм, используемый для подготовки данных для использования с такими методами сжатия данных , как bzip2 . Он был изобретен Майклом Барроузом и Дэвидом Уиллером в 1994 году, когда Барроуз работал в исследовательском центре DEC Systems в Пало-Альто , Калифорния. Он основан на ранее неопубликованном преобразовании, открытом Уиллером в 1983 году. Алгоритм может быть эффективно реализован с использованием массива суффиксов, таким образом достигая линейной временной сложности. [1]

Описание

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

Например:

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

Пример

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

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

Не обязательно использовать оба $и ^, но по крайней мере один из них должен быть использован, иначе мы не сможем инвертировать преобразование, поскольку все циклические перестановки строки имеют одно и то же преобразование Барроуза–Уиллера.

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

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

Объяснение

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

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

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

Оптимизация

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

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

[3]

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

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

Биективный вариант

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

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

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

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

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

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

^ БАНАН

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

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

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

Всего в этих тиражах задействовано 18 персонажей.

Динамическое преобразование Барроуза–Уиллера

При редактировании текста его преобразование Барроуза-Уиллера изменится. Сэлсон и др. [9] предлагают алгоритм, который выводит преобразование Барроуза-Уиллера отредактированного текста из преобразования исходного текста, выполняя ограниченное количество локальных переупорядочений в исходном преобразовании Барроуза-Уиллера, что может быть быстрее, чем построение преобразования Барроуза-Уиллера отредактированного текста напрямую.

Пример реализации

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

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

из  curses.ascii  импорт  STX ,  ETXdef  bwt ( s :  str ,  start = chr ( STX ),  end = chr ( ETX ))  ->  str : r """  Применить преобразование Барроуза–Уиллера к входной строке.  >>> bwt('БАНАН')  '\x03ANNB\x02AA'  >>> bwt('БАНАН', start='^', end='$')  'ANNB^AA$'  >>> bwt('БАНАН', start='%', end='$')  'A$NNB%AA'  """  assert  (  start  not  in  s  and  end  not  in  s  ),  "Входная строка не может содержать символы STX и ETX"  s  =  f " { start }{ s }{ end } "  # Добавить маркер начала и конца текста # Таблица поворотов строки  table  =  sorted ( f " { s [ i :] }{ s [: i ] } "  for  i ,  c  in  enumerate ( s ))  last_column  =  [ row [ - 1 :]  for  row  in  table ]  # Последние символы каждой строки  return  "" . join ( last_column )  # Преобразовать список символов в строку

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

def  inverse_bwt ( r :  str ,  start = chr ( STX ),  end = chr ( ETX ))  ->  str : r """  Применить обратное преобразование Барроуза–Уиллера.  >>> inverse_bwt('\x03ANNB\x02AA')  'БАНАН'  >>> inverse_bwt('ANNB^AA$', start='^', end='$')  'БАНАН'  >>> inverse_bwt('A$NNB%AA', start='%', end='$')  'БАНАН'  """  str_len  =  len ( r )  table  =  [ "" ]  *  str_len  # Создаем пустую таблицу  for  _  in  range ( str_len ):  table  =  sorted ( rc  +  tc  for  rc ,  tc  in  zip ( r ,  table ))  # Добавляем столбец r # Итерируем и проверяем, заканчивается ли последний символ на ETX или нет  s  =  next (( row  for  row  in  table  if  row . endswith ( end )),  "" )  # Извлечь данные из массива и избавиться от начальных и конечных маркеров return  s.rstrip ( end ) .strip ( start )

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

BWT-приложения

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

BWT для выравнивания последовательности

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

BWT для сжатия изображений

Преобразование Берроуза–Уиллера оказалось основополагающим для приложений сжатия изображений . Например, [15] показал конвейер сжатия, основанный на применении преобразования Берроуза–Уиллера с последующими инверсионными, ран-длинными и арифметическими кодерами. Конвейер, разработанный в этом случае, известен как преобразование Берроуза–Уиллера с инверсионным кодером (BWIC). Показано, что результаты, показанные BWIC, превосходят производительность сжатия известных и широко используемых алгоритмов, таких как Lossless JPEG и JPEG 2000. Показано, что BWIC превосходит их с точки зрения конечного размера сжатия рентгенографических медицинских изображений на 5,1% и 4,1% соответственно. Улучшения достигаются путем объединения BWIC и сканирования изображения до BWIC в вертикальном порядке змеи. Совсем недавно дополнительные работы, такие как работа [16], показали, что реализация преобразования Барроуза-Уиллера в сочетании с известным преобразованием «переход на передний план » (MTF) позволяет добиться сжатия изображений практически без потерь.

BWT для сжатия геномных баз данных

Кокс и др. [17] представили схему геномного сжатия, которая использует BWT в качестве алгоритма, применяемого на первом этапе сжатия нескольких наборов геномных данных, включая информацию о геноме человека. Их работа предположила, что сжатие BWT может быть улучшено путем включения механизма сжатия второго этапа, называемого кодированием «то же самое, что и предыдущее» («SAP»), который использует тот факт, что суффиксы из двух или более префиксных букв могут быть равными. С помощью механизма сжатия BWT-SAP Кокс и др. показали, что в геномной базе данных ERA015743 размером 135,5 ГБ схема сжатия BWT-SAP сжимает набор данных ERA015743 примерно на 94% до 8,2 ГБ.

BWT для предсказания последовательности

BWT также доказал свою полезность в прогнозировании последовательностей, что является распространенной областью изучения в машинном обучении и обработке естественного языка . В частности, Ктистакис и др. [18] предложили схему прогнозирования последовательностей, называемую SuBSeq, которая использует сжатие данных без потерь преобразования Барроуза-Уиллера. SuBSeq использует BWT, извлекая FM-индекс , а затем выполняя ряд операций, называемых backwardSearch, forwardSearch, neighborExpansion и getConsequents, для поиска прогнозов по заданному суффиксу . Затем прогнозы классифицируются на основе веса и помещаются в массив, из которого элемент с наибольшим весом дается как прогноз из алгоритма SuBSeq. Было показано, что SuBSeq превосходит современные алгоритмы прогнозирования последовательностей как с точки зрения времени обучения, так и точности.

Ссылки

  1. ^ ab Burrows, Michael ; Wheeler, David J. (10 мая 1994 г.), Алгоритм сжатия данных без потерь с сортировкой блоков, Технический отчет 124, Digital Equipment Corporation, архивировано с оригинала 5 января 2003 г.
  2. ^ "Адриен-Могенет/скала-bwt". Гитхаб . Проверено 19 апреля 2018 г.
  3. ^ Симпсон, Джаред Т.; Дурбин, Ричард (2010-06-15). «Эффективное построение графа сборочной строки с использованием индекса FM». Биоинформатика . 26 (12): i367–i373. doi :10.1093/bioinformatics/btq217. ISSN  1367-4803. PMC 2881401. PMID 20529929  . 
  4. ^ ab Manzini, Giovanni (1999-08-18). "The Burrows–Wheeler Transform: Theory and Practice" (PDF) . Mathematical Foundations of Computer Science 1999: 24th International Symposium, MFCS'99 Szklarska Poreba, Poland, September 6-10, 1999 Proceedings . Springer Science & Business Media. ISBN 9783540664086. Архивировано (PDF) из оригинала 2022-10-09.
  5. ^ Gil, J.; Scott, DA (2009), Биективное преобразование сортировки строк (PDF) , заархивировано из оригинала (PDF) 2011-10-08 , извлечено 2009-07-09
  6. ^ Куфлейтнер, Манфред (2009), «О биективных вариантах преобразования Барроуза–Уиллера», в Голуб, Ян; Ждарек, Ян (ред.), Пражская конференция по стрингологии, стр. 65–69, arXiv : 0908.0239 , Bibcode :2009arXiv0908.0239K.
  7. ^ * Лотер, М. (1997), Комбинаторика слов , Энциклопедия математики и ее приложений, т. 17, Перрен, Д.; Ройтенауэр, К.; Берстель, Дж.; Пин, Дж. Э.; Пирилло, Г.; Фоата, Д.; Сакарович, Дж.; Саймон, И.; Шютценбергер, МП; Чоффрут, К.; Кори, Р.; Линдон, Роджер; Рота, Джан-Карло. Предисловие Роджера Линдона (2-е изд.), Cambridge University Press , стр. 67, ISBN 978-0-521-59924-5, ЗБЛ  0874.20040
  8. ^ Дюваль, Жан-Пьер (1983), «Факторизация слов по упорядоченному алфавиту», Журнал алгоритмов , 4 (4): 363–381, doi : 10.1016/0196-6774(83)90017-2, ISSN  0196-6774 , Збл  0532.68061.
  9. ^ Salson M, Lecroq T, Léonard M, Mouchard L (2009). «Четырехэтапный алгоритм обновления преобразования Барроуза–Уиллера». Теоретическая информатика . 410 (43): 4350–4359. doi : 10.1016/j.tcs.2009.07.016 .
  10. ^ Ли Р. и др. (2008). «SOAP: программа выравнивания коротких олигонуклеотидов». Биоинформатика . 24 (5): 713–714. doi : 10.1093/bioinformatics/btn025 . PMID  18227114.
  11. ^ Ли Х, Руан Дж, Дурбин Р. (2008-08-19). «Картирование коротких прочтений секвенирования ДНК и вызов вариантов с использованием оценок качества картирования». Genome Research . 18 (11): 1851–1858. doi :10.1101/gr.078212.108. PMC 2577856 . PMID  18714091. 
  12. ^ Langmead B, Trapnell C, Pop M, Salzberg SL (2009). «Сверхбыстрое и эффективное с точки зрения памяти выравнивание коротких последовательностей ДНК с человеческим геномом». Genome Biology . 10 (3): R25. doi : 10.1186/gb-2009-10-3-r25 . PMC 2690996. PMID  19261174 . 
  13. ^ Ли Х, Дурбин Р. (2009). «Быстрое и точное выравнивание коротких прочтений с помощью преобразования Берроуза–Уиллера». Биоинформатика . 25 (14): 1754–1760. doi :10.1093/bioinformatics/btp324. PMC 2705234. PMID  19451168 . 
  14. ^ Ли Р. и др. (2009). «SOAP2: улучшенный сверхбыстрый инструмент для выравнивания коротких прочтений». Биоинформатика . 25 (15): 1966–1967. doi :10.1093/bioinformatics/btp336. PMID  19497933.
  15. ^ Колин П., Арнавут З., Коч Б. (2015). «Сжатие медицинских изображений без потерь с использованием преобразования Барроуза–Уиллера с инверсионным кодером». 2015 37-я ежегодная международная конференция IEEE Engineering in Medicine and Biology Society (EMBC) . Том 2015. С. 2956–2959. doi :10.1109/EMBC.2015.7319012. ISBN 978-1-4244-9271-8. PMID  26736912. S2CID  4460328.
  16. ^ Devadoss CP, Sankaragomathi B (2019). «Почти без потерь сжатие медицинских изображений с использованием блочного BWT–MTF и гибридных фрактальных методов сжатия». Cluster Computing . 22 : 12929–12937. doi :10.1007/s10586-018-1801-3. S2CID  33687086.
  17. ^ Cox AJ, Bauer MJ, Jakobi T, Rosone G (2012). «Крупномасштабное сжатие баз данных геномных последовательностей с помощью преобразования Берроуза–Уиллера». Биоинформатика . 28 (11). Oxford University Press: 1415–1419. arXiv : 1205.0192 . doi : 10.1093/bioinformatics/bts173. PMID  22556365.
  18. ^ Ktistakis R, Fournier-Viger P, Puglisi SJ, Raman R (2019). "Succinct BWT-Based Sequence Prediction". Приложения для баз данных и экспертных систем . Lecture Notes in Computer Science. Vol. 11707. pp. 91–101. doi :10.1007/978-3-030-27618-8_7. ISBN 978-3-030-27617-1. S2CID  201058996.

Внешние ссылки