تبدیل باروز-ویلر

تبدیل باروز-ویلر (به انگلیسی: Burrows–Wheeler transform or BST)‏ یک الگوریتم است که برای فشرده‌سازی داده‌ها از آن استفاده می‌شود. این الگوریتم توسط مایکل باروز و دیوید ویلر در سال 1994 اختراع شد. این الگوریتم هیچکدام از کاراکترهای رشته ورودی را دستکاری نمی‌کند. بلکه فقط جای این حروف را عوض می‌کند، به طوری که اگر در رشته ورودی زیررشته یا زیررشته‌هایی داشته باشیم که چندبار تکرار شده باشند، در رشته خروجی مکان‌هایی خواهد بود که چندین کاراکتر یکسان پشت سر هم تکرار خواهد شد و وقتی در یک رشته دسته‌هایی از حروف تکراری داشته باشیم، به آسانی میتوان آن رشته را با استفاده از الگوریتم های فشرده‌سازی خاصی ( مانند Run-length encoding ) فشرده کرد. به عنوان مثالی از روش کار این الگوریتم:

Input	SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
Output	TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT

روش کار الگوریتم

روش کار این الگوریتم به این صورت است که تمامی گردش‌های رشته مورد نظر را در جدولی ذخیره می‌کند. سپس این گردش‌ها را به ترتیب الفبایی ( Lexicographical order) مرتب می‌کند و سپس ستون آخر جدول به دست آمده را به عنوان رشته تبدیل شده برمیدارد. به مثال زیر توجه کنید:

Transformation
Input	All Rotations	Sorted List of Rotations	Output Last Column
^BANANA@	^BANANA@ @^BANANA A@^BANAN NA@^BANA ANA@^BAN NANA@^BA ANANA@^B BANANA@^	ANANA@^B ANA@^BAN A@^BANAN BANANA@^ NANA@^BA NA@^BANA ^BANANA@ @^BANANA	BNN^AA@A

برای بازگردان یک رشته تبدیل شده نیز رویه زیر در پیش گرفته می‌شود: جدولی خالی ایجاد می‌کنیم و به اندازه تعداد عناصر رشته هربار رشته مربوط را به عنوان ستون اول جدول قبل از نتایج مراحل قبل اضافه می‌کنیم، سپس سطرهای جدول را به صورت الفبایی مرتب میکنیم. بعد از تکرار این کار به اندازه تعداد عناصر رشته، آن سطر از جدول را که با حرف ویژه پایانEnd-of-file( در اینجا @) به پایان می‌رسد را انتخاب می‌کنیم. این رشته همان رشته ورودی است. روش کار را به صورت نمادین در مثال زیر می‌توان مشاهده کرد:

Inverse Transformation
Input
BNN^AA@A
Add 1	Sort 1	Add 2	Sort 2
B N N ^ A A @ A	A A A B N N ^ @	BA NA NA ^B AN AN @^ A@	AN AN A@ BA NA NA ^B @^
Add 3	Sort 3	Add 4	Sort 4
BAN NAN NA@ ^BA ANA ANA @^B A@^	ANA ANA A@^ BAN NAN NA@ ^BA @^B	BANA NANA NA@^ ^BAN ANAN ANA@ @^BA A@^B	ANAN ANA@ A@^B BANA NANA NA@^ ^BAN @^BA
Add 5	Sort 5	Add 6	Sort 6
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@^B @^BANA A@^BAN	ANANA@ ANA@^B A@^BAN BANANA NANA@^ NA@^BA ^BANAN @^BANA
Add 7	Sort 7	Add 8	Sort 8
BANANA@ 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
Output
^BANANA@

برای درک اینکه این الگوریتم چگونه به کمتر کردن حجم کمک می‌کند، متنی را در نظر بگیرید که در آن یک لغت خاص زیاد تکرار شده باشد مثلا کلمه بیا، بعد از اجرا این تبدیل تمامی موارد تکرار شدن این کلمه در کنار هم مرتب میشوند و قرار میگیرند مثلا به صورت "اب" که در این صورت می‌دانیم "ی" مربوط به این زیر رشته در آخر جمله است . پس تعداد زیادی ی پشت سر هم در آخر رشته تکرار می شود که این امر، کار فشرده سازی را برای بعضی الگوریتم های فشرده سازی متدوال (به مانند آن مورد که در مقدمه آمده) ساده تر می‌کند. نکته اصلی در مورد این ساده سازی این است که رشته به دست آمده به راحتی قابل تبدیل و بازگشته به اصل جمله‌ای است که در ابتدا بوده و این برگشته پذیری است که این الگوریتم را مناسب استفاده در این گونه موارد کرده است. شبه‌کد مربوط به این الگوریتم را در زیر می توانید مشاهده کنید :

 function BWT (string s)
   create a table, rows are all possible rotations of s
   sort rows alphabetically
   return (last column of the table)

 function inverseBWT (string s)
   create empty table 
       
   repeat length(s) times
       insert s as a column of table before first column of the table   // first insert creates first column
       sort rows of the table alphabetically
   return (row that ends with the 'EOF' character)