התמרת בורווס-וילר

התמרת בורווס-וילר (באנגלית: Burrows–Wheeler transform) היא שיטה לסידור מחרוזת תווים לרצפי תווים חוזרים. סידור זה של המחרוזת מסייע לדחיסת נתונים, שכן קל לדחוס מחרוזת שבה רצפים של תווים חוזרים למשל באמצעות קידוד אורך חזרה (Run-length encoding) או בשיטת העברה קדימה (Move-to-front transform). תכונה חשובה של התמרה זו היא היכולת לשחזר את הקלט, ללא צורך באחסון של מידע נוסף. שיטה זו מאפשרת אפוא לשפר ביצועים של אלגוריתמי דחיסת טקסט במחיר נמוך. התמרת בורווס-וילר נמצאת בשימוש ביישומי דחיסה שונים, כדוגמת אלגוריתם הדחיסה bzip2 ולה שימושים חשובים גם בתחום הביואינפורמטיקה.

האלגוריתם קרוי על שמם של שני מדענים בריטים אשר הציעו אותו לראשונה, מייקל בורווס (Michael Burrows) ודייוויד וילר (David Wheeler). האלגוריתם פורסם לראשונה ב-1994 במסגרת עבודתם במרכז מחקר בפאלו אלטו שבקליפורניה. האלגוריתם מבוסס על אלגוריתם שלא פורסם שווילר פיתח עוד ב-1983 בעבודתו במעבדות בל.

==תיאור==
התמרת בורווס-וילר נעשית באמצעות מיון לקסיקוגרפי של כל הרוטציות של מחרוזת הקלט. כאשר אלו מופיעות בטבלה שורה אחר שורה, ממיינים את השורות, ומחזירים את העמודה האחרונה בטבלה, ואת מספר השורה המתאים למחרוזת המקורית. לדוגמה עבור המילה BANANA נוסיף תו מיוחד ^ שיציין את תחילת המילה, ותו $ שיציין את סופה וההתמרה תפעל כבדוגמה:

{| class="wikitable"
|- 
! colspan="5" | התמרת BWT
|- 
! קלט
! כלהרוטציות
! מיון השורות לפי סדר לקסיקוגרפי
! בחירת העמודההאחרונה
! פלטעמודה אחרונה
|- 
| align=center style="direction:ltr;" | 
 ^BANANA<span style="color:red;">$</span>
| style="direction:ltr;" |
 ^BANANA<span style="color:red;">$</span>
 <span style="color:red;">$</span>^BANANA
 A<span style="color:red;">$</span>^BANAN
 NA<span style="color:red;">$</span>^BANA
 ANA<span style="color:red;">$</span>^BAN
 NANA<span style="color:red;">$</span>^BA
 ANANA<span style="color:red;">$</span>^B
 BANANA<span style="color:red;">$</span>^
| style="direction:ltr;" |
 ANANA<span style="color:red;">$</span>^B
 ANA<span style="color:red;">$</span>^BAN
 A<span style="color:red;">$</span>^BANAN
 BANANA<span style="color:red;">$</span>^
 NANA<span style="color:red;">$</span>^BA
 NA<span style="color:red;">$</span>^BANA
 ^BANANA<span style="color:red;">$</span>
 <span style="color:red;">$</span>^BANANA
| style="direction:ltr;" |
 ANANA<span style="color:red;">$</span>^B
 ANA<span style="color:red;">$</span>^BAN
 A<span style="color:red;">$</span>^BANAN
 BANANA<span style="color:red;">$</span>^
 NANA<span style="color:red;">$</span>^BA
 NA<span style="color:red;">$</span>^BANA
 ^BANANA<span style="color:red;">$</span>
 <span style="color:red;">$</span>^BANANA
| style="direction:ltr;" |
 BNN^AA<span style="color:red;">$</span>A
|}
בעמודת "בחירת העמודה האחרונה", השורה השביעית היא שורה עם מחרוזת הקלט המקורי, והפלט צריך להכיל את מספר השורה המתאימה או באופן שקול ניתן להסיק זאת לפי תו $ שיופיע בסוף שורה זו.

התמרת בורווס-וילר היא הפיכה: בהינתן פלט של BWT, ניתן לשחזר את העמודה הקודמת בטבלה באמצעות מיון, וכך ניתן לחזור על הפעולה עד לקבלת המחרוזת המקורית. לדוגמה:

{| class="wikitable"
! colspan=8 | התמרת שחזור (ה - הוספה, מ - מיון)
|- 
! colspan=8 | קלט
|- 
| align=center colspan=8 | 
 BNN^AA<span style="color:red;">$</span>A
|- 
! ה 1
! מ 1
! ה 2
! מ 2
! ה 3
! מ 3
! ה 4
! מ 4
|- 
| align=right style="direction:ltr;" | 
 B
 N
 N
 ^
 A
 A
 <span style="color:red;">$</span>
 A
| align=right style="direction:ltr;" | 
 A
 A
 A
 B
 N
 N
 ^
 <span style="color:red;">$</span>
| align=right style="direction:ltr;" | 
 BA
 NA
 NA
 ^B
 AN
 AN
 <span style="color:red;">$</span>^
 A<span style="color:red;">$</span>
| align=right style="direction:ltr;" | 
 AN
 AN
 A<span style="color:red;">$</span>
 BA
 NA
 NA
 ^B
 <span style="color:red;">$</span>^
| align=right style="direction:ltr;" | 
 BAN
 NAN
 NA<span style="color:red;">$</span>
 ^BA
 ANA
 ANA
 <span style="color:red;">$</span>^B
 A<span style="color:red;">$</span>^
| align=right style="direction:ltr;" | 
 ANA
 ANA
 A<span style="color:red;">$</span>^
 BAN
 NAN
 NA<span style="color:red;">$</span>
 ^BA
 <span style="color:red;">$</span>^B
| align=right style="direction:ltr;" | 
 BANA
 NANA
 NA<span style="color:red;">$</span>^
 ^BAN
 ANAN
 ANA<span style="color:red;">$</span>
 <span style="color:red;">$</span>^BA
 A<span style="color:red;">$</span>^B
| align=right style="direction:ltr;" | 
 ANAN
 ANA<span style="color:red;">$</span>
 A<span style="color:red;">$</span>^B
 BANA
 NANA
 NA<span style="color:red;">$</span>^
 ^BAN
 <span style="color:red;">$</span>^BA
|- 
! ה 5
! מ 5
! ה 6
! מ 6
! ה 7
! מ 7
! ה 8
! מ 8
|- 
| align=right style="direction:ltr;" | 
 BANAN
 NANA<span style="color:red;">$</span>
 NA<span style="color:red;">$</span>^B
 ^BANA
 ANANA
 ANA<span style="color:red;">$</span>^
 <span style="color:red;">$</span>^BAN
 A<span style="color:red;">$</span>^BA
| align=right style="direction:ltr;" | 
 ANANA
 ANA<span style="color:red;">$</span>^
 A<span style="color:red;">$</span>^BA
 BANAN
 NANA<span style="color:red;">$</span>
 NA<span style="color:red;">$</span>^B
 ^BANA
 <span style="color:red;">$</span>^BAN
| align=right style="direction:ltr;" | 
 BANANA
 NANA<span style="color:red;">$</span>^
 NA<span style="color:red;">$</span>^BA
 ^BANAN
 ANANA<span style="color:red;">$</span>
 ANA<span style="color:red;">$</span>^B
 <span style="color:red;">$</span>^BANA
 A<span style="color:red;">$</span>^BAN
| align=right style="direction:ltr;" | 
 ANANA<span style="color:red;">$</span>
 ANA<span style="color:red;">$</span>^B
 A<span style="color:red;">$</span>^BAN
 BANANA
 NANA<span style="color:red;">$</span>^
 NA<span style="color:red;">$</span>^BA
 ^BANAN
 <span style="color:red;">$</span>^BANA
| align=right style="direction:ltr;" | 
 BANANA<span style="color:red;">$</span>
 NANA<span style="color:red;">$</span>^B
 NA<span style="color:red;">$</span>^BAN
 ^BANANA
 ANANA<span style="color:red;">$</span>^
 ANA<span style="color:red;">$</span>^BA
 <span style="color:red;">$</span>^BANAN
 A<span style="color:red;">$</span>^BANA
| align=right style="direction:ltr;" | 
 ANANA<span style="color:red;">$</span>^
 ANA<span style="color:red;">$</span>^BA
 A<span style="color:red;">$</span>^BANA
 BANANA<span style="color:red;">$</span>
 NANA<span style="color:red;">$</span>^B
 NA<span style="color:red;">$</span>^BAN
 ^BANANA
 <span style="color:red;">$</span>^BANAN
| align=right style="direction:ltr;" | 
 BANANA<span style="color:red;">$</span>^
 NANA<span style="color:red;">$</span>^BA
 NA<span style="color:red;">$</span>^BANA
 ^BANANA<span style="color:red;">$</span>
 ANANA<span style="color:red;">$</span>^B
 ANA<span style="color:red;">$</span>^BAN
 <span style="color:red;">$</span>^BANANA
 A<span style="color:red;">$</span>^BANAN
| align=right style="direction:ltr;" | 
 ANANA<span style="color:red;">$</span>^B
 ANA<span style="color:red;">$</span>^BAN
 A<span style="color:red;">$</span>^BANAN
 BANANA<span style="color:red;">$</span>^
 NANA<span style="color:red;">$</span>^BA
 NA<span style="color:red;">$</span>^BANA
 ^BANANA<span style="color:red;">$</span>
 <span style="color:red;">$</span>^BANANA
|-
! colspan=4 | פלט
|- 
| align=center dir="ltr" colspan=4 | 
 ^BANANA<span style="color:red;">$</span>
|}

==הערות שוליים==

קטגוריה:אלגוריתמים