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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

تبدیل باروز-ویلر (به انگلیسی: 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)