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

تبدیل باروز-ویلر یک الگوریتم است که برای فشرده‌سازی داده‌ها از آن استفاده می‌شود. این الگوریتم توسط مایکل باروز و دیوید ویلر در سال 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
AllRotations
Sorted Listof Rotations
OutputLast Column
^BANANA @
^BANANA @
@ ^BANANA
A @ ^BANAN
NA @ ^BANA
ANA @ ^BAN
NANA @ ^BA
ANANA @ ^B
BANANA @ ^
ANANA @ ^ B
ANA @ ^BA N
A @ ^BANA N
BANANA @ ^
NANA @ ^B A
NA @ ^BAN A
^BANANA @
@ ^BANAN A
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)