تبدیل باروز - ویلر ( به انگلیسی: Burrows–Wheeler transform or BWT ) یک الگوریتم است که چیدمان حروف در کلمات را تغییر می دهد. ان روش برای فشرده سازی داده ها بسیار مناسب است. اگر متنی که می خواهیم آن را فشرده کنیم شامل حروف تکراری ترجیحاً پشت سر هم باشد می توان از روش های دیگر فشرده سازی نظیر کدبندی طول اجرا ( به انگلیسی: Run - length encoding ) استفاده کرد. اما در حالات دیگر روش BWT بسیار مناسب می باشد مخصوصاً اینکه BWT الگوریتمی برگشت پذیر است. یعنی می توان متن فشرده سازی شده را به متن اولیه تبدیل کرد. در حقیقت این کار روشی است که فارغ از هر الگوریتم فشرده سازی که در آن استفاده می شود، با کمی محاسبات بیشتر میزان فشرده سازی را افزایش دهد. BWT توسط مایکل باروز و دیوید ویلر در سال ۱۹۹۴ معرفی شد، زمانی که باروز در یک شرکت به نام DEC Systems Research Center مشغول به کار بود.
روش به دست آوردن BWT برای کلمهٔ EXAMPLE در شکل زیر نشان داده شده است. در ابتدا یک علامت مانند $ در انتهای آن قرار می دهیم تا بتوانیم کلمه را شیفت دورانی دهیم. خروجی های مربوط به شیفت در ستون سمت چپ آورده شده است. سپس در ستون سمت راست کلمات به دست آمده را به ترتیب حروف الفبا ( به انگلیسی: Lexicographical order ) مرتب می کنیم. ستون آخر که در شکل زیر به رنگ قرمز نمایش داده شده است، یعنی EXL$PAME همان ( BWT ( EXAMPLE می باشد.
شبه کد مربوط به این الگوریتم به شکل زیر می باشد:
function BWT ( string s ) create a table, rows are all possible rotations of s sort rows alphabetically return ( last column of the table ) الگوریتم BWT معکوس تا قبل از این روشی که گفته شد برای فشرده سازی استفاده می شود. حال اگر BWT یک کلمه را داشته باشیم چگونه باید بفهمیم اصل آنچه بوده است؟ برای این کار ابتدا حروف را شماره گذاره می کنیم. چون ممکن است در متن حروف تکراری داشته باشیم. مثلاً در مثال خودمان خواهیم داشت: E1 - X1 - A1 - M1 - P1 - L1 - E2 و ۱$. برای بدست آوردن ماتریس مرتب شدهٔ اولیه ستوان آخر را که از نتیجهٔ فشرده سازی داریم. ستوان اول هم با مرتب کردن ستوان آخر بر اساس حروف الفبا به دست می آید. در ادامه به سطر اول نگاه می کنیم که ۱$ است. باید بفهمیم در کلمه اصلی بعد از این حرف چه حرفی قرار می گرفته است. با توجه به اینکه ما ماتریس را از طریق شیفت دورانی ساخته ایم پس اگر حرف ۱$ را در ستون آخر پیدا کرده و ببینیم در مقابل آن در سطر اول چه حرفی قرار دارد آن حرف، حرف بعدی ما در کلمه نهایی خواهد بود. همین کار را مدام انجام می دهیم تا کلمهٔ کامل به دست آید. [ ۱] برای درک بهتر به مثال زیر توجه کنید: همان طور که در بالا توضیح داده شد حرف بعد از ۱$ که X1 است را به دست آوردیم. حال به طریق مشابه می بینیم که X1 در کجای ستون آخر آمده است و حرف نظیر آن در ستون اول چیست؛ بنابراین می بینیم که مقابل آن A1 قرار دارد.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفروش به دست آوردن BWT برای کلمهٔ EXAMPLE در شکل زیر نشان داده شده است. در ابتدا یک علامت مانند $ در انتهای آن قرار می دهیم تا بتوانیم کلمه را شیفت دورانی دهیم. خروجی های مربوط به شیفت در ستون سمت چپ آورده شده است. سپس در ستون سمت راست کلمات به دست آمده را به ترتیب حروف الفبا ( به انگلیسی: Lexicographical order ) مرتب می کنیم. ستون آخر که در شکل زیر به رنگ قرمز نمایش داده شده است، یعنی EXL$PAME همان ( BWT ( EXAMPLE می باشد.
شبه کد مربوط به این الگوریتم به شکل زیر می باشد:
function BWT ( string s ) create a table, rows are all possible rotations of s sort rows alphabetically return ( last column of the table ) الگوریتم BWT معکوس تا قبل از این روشی که گفته شد برای فشرده سازی استفاده می شود. حال اگر BWT یک کلمه را داشته باشیم چگونه باید بفهمیم اصل آنچه بوده است؟ برای این کار ابتدا حروف را شماره گذاره می کنیم. چون ممکن است در متن حروف تکراری داشته باشیم. مثلاً در مثال خودمان خواهیم داشت: E1 - X1 - A1 - M1 - P1 - L1 - E2 و ۱$. برای بدست آوردن ماتریس مرتب شدهٔ اولیه ستوان آخر را که از نتیجهٔ فشرده سازی داریم. ستوان اول هم با مرتب کردن ستوان آخر بر اساس حروف الفبا به دست می آید. در ادامه به سطر اول نگاه می کنیم که ۱$ است. باید بفهمیم در کلمه اصلی بعد از این حرف چه حرفی قرار می گرفته است. با توجه به اینکه ما ماتریس را از طریق شیفت دورانی ساخته ایم پس اگر حرف ۱$ را در ستون آخر پیدا کرده و ببینیم در مقابل آن در سطر اول چه حرفی قرار دارد آن حرف، حرف بعدی ما در کلمه نهایی خواهد بود. همین کار را مدام انجام می دهیم تا کلمهٔ کامل به دست آید. [ ۱] برای درک بهتر به مثال زیر توجه کنید: همان طور که در بالا توضیح داده شد حرف بعد از ۱$ که X1 است را به دست آوردیم. حال به طریق مشابه می بینیم که X1 در کجای ستون آخر آمده است و حرف نظیر آن در ستون اول چیست؛ بنابراین می بینیم که مقابل آن A1 قرار دارد.
wiki: تبدیل باروز ویلر