Ας δούμε την τετριμμένη προσέγγιση, η οποία σε πολλές περιπτώσεις μπορεί να είναι η βέλτιστη:
Θα αποθήκευε:
- Ο αριθμός των στοιχείων στην περιοχή (με 31 bits, αφού οι λίστες στην Ιάβα περιορίζονται σε 231 - 1 στοιχεία).
- Ακολουθείται από 1 bit για κάθε δείκτη, υποδεικνύοντας αν το στοιχείο είναι παρόν στο σύνολο ή όχι.
Αυτή είναι η υλοποίηση που είχε η πρώτη έκδοση του συμπιεστή εικόνας fractal, για την αποθήκευση των δεδομένων από τις διασπάσεις και τις συγχωνεύσεις των τριγωνισμών.
Αν και δεν ήταν η βέλτιστη, δεδομένου ότι καθώς οι επαναλήψεις των διασπάσεων προχωρούσαν, ο αριθμός των στοιχείων που έπρεπε να αποθηκευτούν μειώθηκε, αποτελώντας ένα πολύ μικρό ποσοστό του συνόλου, οπότε η τετριμμένη κωδικοποίηση μπορεί να βελτιωθεί σημαντικά.
Τώρα ο στόχος είναι να βελτιωθεί αυτή η ασήμαντη κωδικοποίηση, για να δούμε αν μπορεί να αποκτηθεί μια πιο συμπιεσμένη κωδικοποίηση όσον αφορά τον αριθμό των bit που χρησιμοποιούνται.
Πρώτη προσέγγιση : Όταν ο αριθμός των στοιχείων στο σύνολο είναι πολύ μικρότερος από το μέγεθος του εύρους, μπορούμε να εξετάσουμε την αποθήκευση των παρόντων δεικτών.
Σε αυτή την περίπτωση, η χρήση θα ήταν:
- 31 bit για τον αριθμό των στοιχείων στην περιοχή.
- 31 bit για τον αριθμό των στοιχείων που υπάρχουν στο σετ.
- 31 bit * ο αριθμός των στοιχείων που υπάρχουν στο σύνολο.
Δεύτερη προσέγγιση . Βελτιώνουμε τον αριθμό των bit ανά αποθηκευμένο στοιχείο:
- 31 bit για τον αριθμό των στοιχείων στην περιοχή. Ο αριθμός των bit του μεγαλύτερου στοιχείου στην περιοχή ( numBitsΈλεμ ) θα υπολογιζόταν.
- 5 μπιτ για αποθήκευση numBitsΈλεμ .Έτσι, αν ο αριθμός των στοιχείων στην περιοχή ήταν 1023, ένα 10 θα αποθηκεύονταν σε αυτά τα 5 bit.
- numBitsΈλεμ bits, για την αποθήκευση του αριθμού των στοιχείων στο Σετ.
- numBitsΈλεμ bits * τον αριθμό των στοιχείων που υπάρχουν στο Σύνολο.
Λοιπόν, σιγά σιγά πλησιάζουμε σε μια καλύτερη κωδικοποίηση...
Τρίτη προσέγγιση . Αντιλαμβανόμαστε ότι αν ταξινομήσουμε το σύνολο σε αύξουσα σειρά, τα δέλτα (διαφορές μεταξύ διαδοχικών στοιχείων) μπορούν πιθανότατα να κωδικοποιηθούν με λιγότερα bits από ένα απόλυτο στοιχείο της περιοχής:
- 31 bit για τον αριθμό των στοιχείων στην περιοχή.
- Υπολογίζουμε το μικρότερο numBitsElem για να κωδικοποιήσουμε ένα στοιχείο.Υπολογίζουμε επίσης τη λίστα των δέλτα (λίστα διαφορών μεταξύ διαδοχικών στοιχείων της ταξινομημένης λίστας των στοιχείων στο σύνολο).Και τέλος, υπολογίζουμε επίσης numBitsΔέλτα
- 5 μπιτ για αποθήκευση numBitsΈλεμ .
- 5 μπιτ για αποθήκευση numBitsΔέλτα .
- numBitsΈλεμ bits, για την αποθήκευση του αριθμού των στοιχείων στο Σετ.
- numBitsΔέλτα bits * τον αριθμό των στοιχείων στο Σύνολο.
Λοιπόν, φαίνεται ότι ήδη φτάνουμε στη βέλτιστη κωδικοποίηση, σωστά;...
Ας συνεχίσουμε...
Τέταρτη προσέγγιση Επικεντρωνόμαστε στο γεγονός ότι μπορεί να υπάρχει ένας πολύ μεγαλύτερος αριθμός μικρότερων δέλτα, και ίσως μόνο μερικά πολύ μεγαλύτερα, που σπάνε το numBitsΔέλτα .
Κάτω από αυτές τις συνθήκες, μπορεί να βρούμε ένα numOptimumBitsΔέλτα μικρότερο από το μέγιστο numMaxBitsΔέλτα , η οποία με τη σειρά της είναι μικρότερη ή ίση με numBitsΈλεμ .
Αλλά πώς κωδικοποιούμε ένα στοιχείο δέλτα που ξεπερνάει το numOptimumBitsΔέλτα ;
Λοιπόν... αφού τα δέλτα δεν θα είναι ποτέ 0 (δεν υπάρχουν επαναλαμβανόμενα στοιχεία σε ένα Σύνολο), μπορούμε να χρησιμοποιήσουμε την τιμή 0 για να υποδείξουμε ότι είναι μια ειδική τιμή.
Και ότι το 0 θα ακολουθηθεί από την τιμή του δέλτα, αλλά κωδικοποιήθηκε αυτή τη φορά με numMaxBitsΔέλτα .Ο συνολικός αριθμός των bit θα μπορούσε να υπολογιστεί ως εξής:
- 31 bit για τον αριθμό των στοιχείων στην περιοχή. Υπολογίζουμε το μικρότερο numBitsΈλεμ για να μπορέσουμε να κωδικοποιήσουμε ένα στοιχείο. Υπολογίζουμε επίσης τη λίστα των δέλτα (λίστα διαφορών μεταξύ διαδοχικών στοιχείων της ταξινομημένης λίστας των στοιχείων στο Σύνολο).
- 31 bit, για την αποθήκευση του αριθμού των στοιχείων στο Σετ.
- 5 μπιτ για αποθήκευση numOptimumBitsΔέλτα .
- 5 μπιτ για αποθήκευση numMaxBitsΔέλτα .
- numOptimumBitsΔέλτα bits * τον αριθμό των στοιχείων στο Σύνολο.
- numMaxBitsΔέλτα bits * ο αριθμός των δέλτα που υπερβαίνουν numOptimumBitsΔέλτα .
Φτάσαμε ήδη στη βέλτιστη κωδικοποίηση;
Πέμπτη προσέγγιση Λοιπόν... αφού έχουμε ήδη προγραμματίσει όλα αυτά...Θα μπορούσαμε να σκεφτούμε τη συμπληρωματική κατάσταση...Θα ήταν δυνατόν η κωδικοποίηση του συμπληρώματος του συνόλου με τον ίδιο αλγόριθμο να παράγει πιο συμπιεσμένα αποτελέσματα;
Το συμπλήρωμα του συνόλου νοείται ως ένα άλλο σύνολο, που αποσυνδέεται από το αρχικό, του οποίου η ένωση με το αρχικό σύνολο είναι ολόκληρο το εύρος.
Δηλαδή, το συμπληρωματικό σύνολο θα είχε όλα τα στοιχεία του εύρους που απουσιάζουν στο αρχικό σύνολο, και κανένα από αυτά στο αρχικό σύνολο.
Η ομορφιά είναι ότι από ένα σύνολο, είναι πολύ εύκολο να αποκτηθεί το συμπληρωματικό σύνολο, και ως εκ τούτου θα μπορούσαμε να αποκτήσουμε το αρχικό σύνολο, έχοντας κωδικοποιήσει το συμπληρωματικό.
Η προφανής εφαρμογή είναι ένα σύνολο που έχει όλα τα στοιχεία του εύρους εκτός από ένα, ή μερικά...
Λοιπόν... αν αποθηκεύσουμε μόνο τα απόντα (το συμπληρωματικό σύνολο), θα μπορούσε να αποθηκευτεί σε πολύ μικρότερο μέγεθος, σωστά;
Η κωδικοποίηση σε αυτή την περίπτωση θα μπορούσε να είναι ως εξής:
- 31 bit για τον αριθμό των στοιχείων στην περιοχή. Υπολογίζουμε το μικρότερο numBitsΈλεμ για να κωδικοποιήσουμε ένα στοιχείο. Υπολογίζουμε επίσης τη λίστα των δέλτα (λίστα διαφορών μεταξύ διαδοχικών στοιχείων της ταξινομημένης λίστας των στοιχείων στο σύνολο).
- 1 bit, για να αποθηκεύσουμε αν αποθηκεύουμε το αρχικό Σετ, ή το συμπλήρωμα.Αυτό είναι το έξτρα κομμάτι.
- 31 bit, για την αποθήκευση του αριθμού των στοιχείων στο Σετ.
- 5 μπιτ για αποθήκευση numOptimumBitsΔέλτα .
- 5 μπιτ για αποθήκευση numMaxBitsΔέλτα .
- numOptimumBitsΔέλτα bits * τον αριθμό των στοιχείων στο Σύνολο.
- numMaxBitsΔέλτα bits * ο αριθμός των δέλτα που υπερβαίνουν numOptimumBitsΔέλτα , στις θέσεις όπου εμφανίζονται.
Λοιπόν... τώρα μιλάμε.
Έτσι εκεί κόλλησα... αλλά γνωρίζω ότι αν όλα αυτά τα θαύματα μπορούν να γίνουν, τι δεν θα μπορούσε να γίνει με την αναζήτηση άλλων μοτίβων, ή απλά με τη χρήση ενός συμπιεστή χωρίς απώλειες, όπως το φερμουάρ ή το 7z...
Αυτό θα πρέπει να περιμένει, στον πίσω καυστήρα για την επόμενη φορά...
