Зміст:
- Визначення - Що означає трансформація Burrow-Wheeler (BWT)?
- Техопедія пояснює трансформацію Берроу-Уілера (BWT)
Визначення - Що означає трансформація Burrow-Wheeler (BWT)?
Перетворення Берроуса-Уілера (BWT) - це алгоритм, який приймає блоки даних, такі як рядки, і переставляє їх у проміжки схожих символів. Після перетворення вихідний блок містить ті самі точні елементи даних до його початку, але відрізняється впорядкованістю. Характер алгоритму, як правило, ставить подібні символи поруч, що полегшує стискання отриманого порядку даних. Отже, він використовується у багатьох алгоритмах стиснення.
Техопедія пояснює трансформацію Берроу-Уілера (BWT)
Алгоритм перетворення Берроуса-Уілера - це порівняно новий алгоритм, винайдений у 1994 році Майклом Берроусом та Девідом Уілером і заснований на неопублікованій трансформації, виявленій Уїлером у 1983 році, опублікованій у їхній статті "Алгоритм стиснення даних без блоку без втрат".
В основному, BWT приймає блок даних, такий як рядок, додаючи символ EOF, а потім сортує всі обертання цієї рядки в лексикографічному порядку. Наступний псевдокод або етапи ілюструють алгоритм:
- Створіть таблицю, що містить рядки, які представляють усі можливі однократні обертання рядка.
- Сортувати всі рядки за алфавітом.
- Виведіть останній стовпець таблиці.
Наприклад: слово "банан"; додавання символу EOF перетворює його в "banana $", тоді ми застосовуємо алгоритм:
1. Створіть таблицю з рядками, що представляють усі можливі обертання:
банан $
anana $ b
нана $ ба
ana $ ban
на $ бана
$ банан
$ банан
2. Сортуйте рядки за алфавітом / лексикографічно на основі першого стовпця:
$ банан
$ банан
ana $ ban
anana $ b
банан $
нана $ ба
на $ бана
3.Поверніть останній стовпчик як вихід BWT: annb $ aa
Отриманий рядок простіше стиснути, тому що повторювані символи з’єднуються один біля одного. Але повинні бути додаткові дані, що зберігаються з перетвореними даними, щоб можна було зробити зворотне перетворення. Навіть незважаючи на те, що отримані трансформовані дані є більшими за початкову форму, проте його характеристика стисливості збільшується в багато разів, що робить її «вільним» методом підвищення ефективності методів стиснення.
