Съдържание:
- Определение - Какво означава трансформацията на Burrows-Wheeler (BWT)?
- Techopedia обяснява трансформацията на Burrows-Wheeler (BWT)
Определение - Какво означава трансформацията на Burrows-Wheeler (BWT)?
Трансформацията Burrows-Wheeler (BWT) е алгоритъм, който взема блокове от данни, като например низове, и ги пренарежда в групи от подобни символи. След преобразуването изходният блок съдържа същите точни елементи от данни, преди да е започнал, но се различава в подреждането. Характерът на алгоритъма има тенденция да поставя подобни символи един до друг, което улеснява компресирането на получения ред. Следователно той се използва в много алгоритми за компресия.
Techopedia обяснява трансформацията на Burrows-Wheeler (BWT)
Алгоритъмът за трансформация на Burrows-Wheeler е сравнително нов алгоритъм, изобретен през 1994 г. от Майкъл Бърроуз и Дейвид Уилър и основан на непубликувана трансформация, открита от Уилър през 1983 г., публикувана в тяхната книга „Алгоритъм за компресиране на данни без загуба на данни.“
В най-основния BWT взема блок от данни като низ, добавя EOF символ и след това сортира всички завъртания на този низ в лексикографски ред. Следните псевдокодове или стъпки илюстрират алгоритъма:
- Създайте таблица, която съдържа редове, които представляват всички възможни еднократни ротации на низа.
- Сортиране на всички редове по азбучен ред.
- Изведете последната колона на таблицата.
Например: думата „банан“; добавянето на EOF символ го превръща в „banana $“, след което прилагаме алгоритъма:
1. Създайте таблица с редове, представящи всички възможни завъртания:
банан $
Анана $ б
Нана $ ба
Ана $ забрана
Na $ Бана
от $ Banan
$ банан
2. Сортирайте редовете по азбучен / лексикографски начин въз основа на първата колона:
$ банан
от $ Banan
Ана $ забрана
Анана $ б
банан $
Нана $ ба
Na $ Бана
3.Върнете последната колона като BWT изход: обявете $ aa
Полученият низ е по-лесен за компресиране, тъй като повтарящите се знаци се събират един до друг. Но трябва да има допълнителни данни, съхранявани с трансформираните данни, за да може да се извърши обратна трансформация. Въпреки че получените трансформирани данни са по-големи от оригиналната им форма, но характеристиката му на сгъваемост се увеличава многократно, което го прави по същество „безплатен“ метод за подобряване на ефективността на методите на компресия.
