Перетворення Берроуза-Вілера

Перетворення Берроуза-Вілера (англ. Burrows-Wheeler Transform, BWT) — метод перестановки символів у стрічці в іншу стрічку , таким чином, що із можна отримати початкову послідовність, але в той же час вона краще надається до стиснення.

Щоб знайти від стрічки довжиною слід згенерувати циклічних ротацій цієї стрічки, відсортувати їх у лексикографічному порядку і отримати нову стрічку з останніх символів цих ротацій. Якщо вихідна стрічка містить багато повторів (як, наприклад, природна мова або геноми живих організмів), то трансформована міститиме багато серій (послідовностей, в яких один і той же символ зустрічається кілька разів поспіль).

Перетворення Берроуза-Вілера використовують для стиснення даних без втрат, зокрема воно є частиною алгоритму bzip2[1], а також для індексування. Наприклад, у біоінформатиці воно дозволяє скоротити витрати пам'яті під час картування фрагментів, отриманих шляхом секвенування ДНК, стосовно референсних геномів. Цей метод перетворення послідовностей запропонували у 1994 році Майкл Берроуз і Девід Вілер[2].

Отримання

Перетворення Берроуза-Вілера можна отримати, використавши однойменну матрицю. Нехай вихідна стрічка буде "тамтам$", вона повинна містити символ-термінатор ($), який не трапляється ніде в інших позиціях цієї стрічки і лексикографічно передує всім іншим символам. Спершу слід згенерувати усі циклічні ротації цієї стрічки, записавши їх одна під одною, ми отримуємо квадратну матрицю. Далі відсортовуємо рядки матриці у лексикографічному порядку, тепер останній її стовпець прочитаний згори вниз утворює , у нашому випадку "мттаам$".

Ротації Відсортовані
ротації
тамтам$
амтам$т
мтам$та
там$там
ам$тамт
м$тамта
$тамтам
 
$тамтам
ам$тамт
амтам$т
м$тамта
мтам$та
там$там
тамтам$

Примітки
  1. Julian Seward. bzip2 manual. Архів оригіналу за 16 квітня 2015. Процитовано 9 квітня 2015.
  2. Burrows, Michael; Wheeler, David J. (1994). A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation.



This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.