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 в качестве столбца таблицы перед первым столбцом таблицы отсортировать строки таблицы по алфавиту return (строка, заканчивающаяся символом «EOF»)

Объяснение

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

Замечательная особенность 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) и ( ^ ). (НАНА... не представляет собой отдельное слово, так как это цикл АНАН....) На этом этапе эти слова сортируются в обратном порядке: ( ^ ), (B), (AN), ( АН), (А). Затем они объединяются, чтобы получить

^ БАНАН

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

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

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

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

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

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

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

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

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

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

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

def  inverse_bwt ( r :  str )  ->  str : """Применить обратное преобразование Берроуза-Уиллера.""" table = [ "" ] * len ( r ) # Создать пустую таблицу для _ в диапазоне ( len ( r )): table = sorted ( r [ i ] + table [ i ] for i в диапазоне ( len ( r ))) # Добавляем столбец r                      s  =  next (( строка  для  строки  в  таблице  , если  строка . заканчивается ( " \003 " )),  "" )  # Перебираем и проверяем, заканчивается ли последний символ на ETX или не  возвращает  s . rstrip ( " \003 " ) . Strip ( " \002 " )  # Извлекаем данные из массива и избавляемся от маркеров начала и конца

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

Приложения BWT

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

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

Появление методов секвенирования нового поколения (NGS) в конце десятилетия 2000-х годов привело к новому применению преобразования Берроуза-Уиллера. В NGS ДНК фрагментируется на небольшие фрагменты, из которых секвенируются первые несколько оснований , что дает несколько миллионов «чтений», каждое из которых имеет длину от 30 до 500 пар оснований («символов ДНК»). Во многих экспериментах, например, в ChIP-Seq , задача теперь состоит в том, чтобы привести эти чтения в соответствие с эталонным геномом , т.е. с известной, почти полной последовательностью рассматриваемого организма (длина которой может достигать нескольких миллиардов пар оснований). . Был опубликован ряд программ выравнивания, специализирующихся на этой задаче, которые первоначально полагались на хеширование (например, Eland, SOAP, [10] или Maq [11] ). В целях снижения требований к памяти для выравнивания последовательностей было разработано несколько программ выравнивания ( Bowie , [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, Cox et al. показали, что в геномной базе данных ERA015743 размером 135,5 ГБ схема сжатия BWT-SAP сжимает набор данных ERA015743 примерно на 94%, до 8,2 ГБ.

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

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

Рекомендации

  1. ^ аб Берроуз, Майкл ; Уиллер, Дэвид Дж. (10 мая 1994 г.), Алгоритм сжатия данных без потерь с сортировкой блоков , Технический отчет 124, Digital Equipment Corporation, заархивировано из оригинала 5 января 2003 г.
  2. ^ "Адриен-Могенет/скала-bwt". Гитхаб . Проверено 19 апреля 2018 г.
  3. ^ Симпсон, Джаред Т.; Дурбин, Ричард (15 июня 2010 г.). «Эффективное построение графа ассемблерной строки с использованием FM-индекса». Биоинформатика . 26 (12): i367–i373. doi : 10.1093/биоинформатика/btq217. ISSN  1367-4803. ПМЦ 2881401 . ПМИД  20529929. 
  4. ^ Аб Манзини, Джованни (18 августа 1999 г.). «Преобразование Берроуза – Уиллера: теория и практика» (PDF) . Математические основы информатики 1999: 24-й международный симпозиум, MFCS'99, Шклярска-Поремба, Польша, 6–10 сентября 1999 г., материалы . Springer Science & Business Media. ISBN 9783540664086. Архивировано (PDF) из оригинала 9 октября 2022 г.
  5. ^ Гил, Дж.; Скотт, Д.А. (2009), Преобразование сортировки биективных строк (PDF) , заархивировано из оригинала (PDF) 8 октября 2011 г. , получено 9 июля 2009 г.
  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. ^ Салсон М., Лекрок Т., Леонар М., Мушард Л. (2009). «Четырехэтапный алгоритм обновления преобразования Берроуза – Уиллера». Теоретическая информатика . 410 (43): 4350–4359. дои : 10.1016/j.tcs.2009.07.016 .
  10. ^ Ли Р; и другие. (2008). «SOAP: программа выравнивания коротких олигонуклеотидов». Биоинформатика . 24 (5): 713–714. doi : 10.1093/биоинформатика/btn025 . ПМИД  18227114.
  11. ^ Ли Х, Руан Дж, Дурбин Р (19 августа 2008 г.). «Картирование коротких прочтений секвенирования ДНК и вызов вариантов с использованием показателей качества картирования». Геномные исследования . 18 (11): 1851–1858. дои : 10.1101/гр.078212.108. ПМК 2577856 . ПМИД  18714091. 
  12. ^ Лэнгмид Б., Трапнелл С., Поп М., Зальцберг С.Л. (2009). «Сверхбыстрое и эффективное для памяти выравнивание коротких последовательностей ДНК с геномом человека». Геномная биология . 10 (3): 25 рандов. дои : 10.1186/gb-2009-10-3-r25 . ПМК 2690996 . ПМИД  19261174. 
  13. ^ Ли Х, Дурбин Р. (2009). «Быстрое и точное выравнивание короткого чтения с помощью преобразования Берроуза – Уиллера». Биоинформатика . 25 (14): 1754–1760. doi : 10.1093/биоинформатика/btp324. ПМК 2705234 . ПМИД  19451168. 
  14. ^ Ли Р; и другие. (2009). «SOAP2: улучшенный сверхбыстрый инструмент для выравнивания короткого чтения». Биоинформатика . 25 (15): 1966–1967. doi : 10.1093/биоинформатика/btp336. ПМИД  19497933.
  15. ^ Коллин П., Арнавут З., Коч Б. (2015). «Сжатие медицинских изображений без потерь с использованием преобразования Берроуза – Уиллера с инверсионным кодером». 2015 37-я ежегодная международная конференция Общества инженерии в медицине и биологии IEEE (EMBC) . Том. 2015. С. 2956–2959. дои : 10.1109/EMBC.2015.7319012. ISBN 978-1-4244-9271-8. PMID  26736912. S2CID  4460328.
  16. ^ Девадосс CP, Санкарагомати Б (2019). «Сжатие медицинских изображений практически без потерь с использованием блочных методов BWT – MTF и гибридных фрактальных методов сжатия». Кластерные вычисления . 22 : 12929–12937. дои : 10.1007/s10586-018-1801-3. S2CID  33687086.
  17. ^ Кокс А.Дж., Бауэр М.Дж., Якоби Т., Розоне Г. (2012). «Крупномасштабное сжатие баз данных геномных последовательностей с помощью преобразования Берроуза-Уиллера». Биоинформатика . 28 (11). Издательство Оксфордского университета: 1415–1419. arXiv : 1205.0192 . doi : 10.1093/биоинформатика/bts173. ПМИД  22556365.
  18. ^ Ктистакис Р., Фурнье-Вигер П., Пуглиси С.Дж., Раман Р. (2019). «Краткий прогноз последовательности на основе BWT». Приложения баз данных и экспертных систем . Конспекты лекций по информатике. Том. 11707. стр. 91–101. дои : 10.1007/978-3-030-27618-8_7. ISBN 978-3-030-27617-1. S2CID  201058996.

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