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

Перетворення Берроуза-Вілера (Шаблон:Lang-en) — метод перестановки символів у стрічці $T$ в іншу стрічку $BWT(T)$, таким чином, що із $BWT(T)$ можна отримати початкову послідовність, але в той же час вона краще придатна для стиснення.

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

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

Отримання

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

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

Примітки

Шаблон:Алгоритм-доробити

Шаблон:Методи стиснення даних