Πίνακας περιεχομένων:
- Ορισμός - Τι σημαίνει το μετασχηματισμό Burrows-Wheeler (BWT);
- Η Techopedia εξηγεί το μετασχηματισμό Burrows-Wheeler (BWT)
Ορισμός - Τι σημαίνει το μετασχηματισμό Burrows-Wheeler (BWT);
Ο μετασχηματισμός Burrows-Wheeler (BWT) είναι ένας αλγόριθμος που παίρνει μπλοκ δεδομένων, όπως χορδές, και τα αναδιατάσσει σε τρεξίματα παρόμοιων χαρακτήρων. Μετά το μετασχηματισμό, το μπλοκ εξόδου περιέχει τα ίδια ακριβή στοιχεία δεδομένων πριν ξεκινήσει, αλλά διαφέρει κατά την παραγγελία. Η φύση του αλγορίθμου τείνει να τοποθετήσει παρόμοιους χαρακτήρες δίπλα ο ένας στον άλλο, καθιστώντας την προκύπτουσα σειρά δεδομένων ευκολότερη στη συμπίεση. Ως εκ τούτου χρησιμοποιείται σε πολλούς αλγόριθμους συμπίεσης.
Η Techopedia εξηγεί το μετασχηματισμό Burrows-Wheeler (BWT)
Ο αλγόριθμος μετασχηματισμού Burrows-Wheeler είναι ένας σχετικά νέος αλγόριθμος που εφευρέθηκε το 1994 από τον Michael Burrows και τον David Wheeler και βασίζεται σε ένα ανέκδοτο μετασχηματισμό που ανακαλύφθηκε από τον Wheeler το 1983, που δημοσιεύθηκε στο βιβλίο του "Αλγόριθμος συμπίεσης δεδομένων με διαχωρισμό μπλοκ".
Στα πιο βασικά, το BWT παίρνει ένα μπλοκ δεδομένων, όπως μια συμβολοσειρά, προσθέτοντας έναν χαρακτήρα EOF και στη συνέχεια ταξινομώντας όλες τις περιστροφές αυτής της συμβολοσειράς σε λεξικογραφική σειρά. Ο ακόλουθος ψευδοκώδικας ή βήματα απεικονίζουν τον αλγόριθμο:
- Δημιουργήστε έναν πίνακα που περιέχει γραμμές που αντιπροσωπεύουν όλες τις πιθανές περιστροφές μίας αύξησης της συμβολοσειράς.
- Ταξινόμηση όλων των σειρών αλφαβητικά.
- Εξάγετε την τελευταία στήλη του πίνακα.
Για παράδειγμα: η λέξη "μπανάνα"; προσθέτοντας ένα χαρακτήρα EOF το μετατρέπει σε "banana $" τότε εφαρμόζουμε τον αλγόριθμο:
1. Δημιουργήστε έναν πίνακα με σειρές που αντιπροσωπεύουν όλες τις πιθανές περιστροφές:
μπανάνα $
anana $ b
nana $ ba
ana $ απαγόρευση
na $ bana
ένα $ banan
$ μπανάνα
2. Ταξινόμηση των γραμμών αλφαβητικά / λεξικογραφικά με βάση την πρώτη στήλη:
$ μπανάνα
ένα $ banan
ana $ απαγόρευση
anana $ b
μπανάνα $
nana $ ba
na $ bana
3. Επαναφέρετε την τελευταία στήλη ως έξοδο BWT: annb $ aa
Η προκύπτουσα συμβολοσειρά είναι πιο εύκολη στη συμπίεση, επειδή οι επαναλαμβανόμενοι χαρακτήρες συσσωρεύονται δίπλα ο ένας στον άλλο. Αλλά πρέπει να αποθηκεύονται επιπλέον δεδομένα με τα μετασχηματισμένα δεδομένα, έτσι ώστε να μπορεί να γίνει αντίστροφος μετασχηματισμός. Αν και τα προκύπτοντα μετασχηματισμένα δεδομένα είναι μεγαλύτερα από την αρχική τους μορφή αλλά το χαρακτηριστικό της συμπιεστότητας αυξάνεται πολλές φορές, καθιστώντας ουσιαστικά μια "ελεύθερη" μέθοδο βελτίωσης της αποτελεσματικότητας των μεθόδων συμπίεσης.
