מהו טרנספורמציית גלגלים-גלגלים (bwt)? - הגדרה מטכנולוגיה

הגדרה - מה המשמעות של טרנספורמציית Burrows-Wheeler (BWT)?

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

Techopedia מסביר טרנספורמציה של Burrows-Wheeler (BWT)

אלגוריתם הטרנספורמציה Burrows-Wheeler הוא אלגוריתם חדש יחסית שהומצא בשנת 1994 על ידי מייקל בורוס ודייוויד וילר, ומבוסס על טרנספורמציה שלא פורסמה שגילה ווילר בשנת 1983, שפורסמה במאמרם "אלגוריתם דחיסת נתונים ללא אבדן נתונים".

באופן הבסיסי ביותר, BWT לוקח גוש נתונים כגון מחרוזת, מוסיף תו EOF ואז ממיין את כל הסיבובים של אותו מחרוזת לפי סדר לקסיקוגרפי. הפסאודוקוד או השלבים הבאים מדגימים את האלגוריתם:

1. צור טבלה המכילה שורות המייצגות את כל הסיבובים האפשריים בתוספת מחרוזת.
2. מיין את כל השורות באופן אלפביתי.
3. פלט את העמודה האחרונה בטבלה.

לדוגמא: המילה "בננה"; הוספת תו EOF הופכת אותו ל"בננה $ "ואז אנו מיישמים את האלגוריתם:

1. צור טבלה עם שורות המייצגות את כל הסיבובים האפשריים:

בננה $

אנאנה $ ב

nana $ ba

איסור על $ $

na $ בנה

בנן $

בננה $

2. מיין את השורות בצורה אלפביתית / לקסיקוגרפית לפי העמודה הראשונה:

בננה $

בנן $

איסור על $ $

אנאנה $ ב

בננה $

nana $ ba

na $ בנה

3. החזר את העמודה האחרונה כפלט BWT: annb $ aa

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