"Institute of Educational Policy" Books

Search

Go
Show

Αλγόριθμος RLE

Ο αλγόριθμος RLE (Run Length Encoding) αποτελεί μια από τις απλούστερες τεχνικές συμπίεσης. Σύμφωνα με τη μέθοδο αυτή, διατρέχεται η ακολουθία των bytes που αποτελούν τα δεδομένα προς συμπίεση και εντοπίζονται οι διαδοχικές επαναλήψεις του ίδιου χαρακτήρα. Στη συνέχεια αντικαθίστανται οι συνεχόμενες επαναλήψεις με το πλήθος τους, ακολουθούμενο από τον χαρακτήρα.

Αν συμπιέσουμε την ακολουθία AAABBBEEEAADDD με τη μέθοδο RLE, τότε η συμπιεσμένη μορφή της ακολουθίας θα είναι 3A3B3E2A3D, που έχει μήκος 10 χαρακτήρες και όχι 14 όπως η αρχική.

Αν προσέξουμε το σχήμα της παραπάνω συμπίεσης θα παρατηρήσουμε ότι αποδίδει ικανοποιητικά για ακολουθίες δεδομένων που έχουν συχνές επαναλήψεις χαρακτήρων. Αν για παράδειγμα συμπιέσουμε την ακολουθία «ABCDE» μήκους 5 bytes με τον αλγόριθμο RLE, η συμπιεσμένη μορφή της είναι «1A1B1C1D1E», με μήκος 10. Στην περίπτωση αυτή όχι μόνο δεν έγινε συμπίεση, αλλά διπλασιάστηκε το μήκος της ακολουθίας. Για να αποφευχθούν αυτές οι περιπτώσεις, ο RLE δε συμπιέζει τις ακολουθίες μη συνεχόμενων χαρακτήρων.

Στην πράξη ο αλγόριθμος διατρέχει την ακολουθία των δεδομένων και αναζητά διαδοχικές επαναλήψεις του ίδιου χαρακτήρα. Όταν βρεθεί μεμονωμένος χαρακτήρας που δεν επαναλαμβάνεται, ή διπλή επανάληψη του, μένει ως έχει, καθώς δεν επωφελούμαστε από την κωδικοποίηση RLE που απαιτεί 2 χαρακτήρες. Όταν όμως βρεθούν διαδοχικές επαναλήψεις ενός χαρακτήρα, τις αντικαθιστά με ένα ζεύγος (αριθμός, χαρακτήρας), όπου «αριθμός» είναι το σύνολο των συνεχόμενων εμφανίσεων του χαρακτήρα.