Συμπίεση Ανεστραμμένων Αρχείων


Η συμπίεση των ανεστραμμένων αρχείων πρωταρχικά στοχεύει στην ελάττωση του μεγέθους τους. Ωστόσο στα συστήματα ανάκτησης σημαντικό ρόλο παίζει και ο χρόνος αξιολόγησης των ερωτημάτων ειδικότερα όταν τα ευρετήρια είναι συμπιεσμένα. Για να είναι αποδεκτή μια μέθοδος συμπίεσης θα πρέπει ο χρόνος μεταφοράς των ανεστραμμένων λιστών στην μνήμη συν το χρόνο αποσυμπίεσής τους να είναι μικρότερος από το χρόνο μεταφοράς στη μνήμη των αντίστοιχων μη συμπιεσμένων ανεστραμμένων λιστών. Στην ενότητα αυτή θα περιγράψουμε αλγόριθμους συμπίεσης που επιτυγχάνουν και τους δύο αυτούς στόχους. Οι ανεστραμμένες λίστες στην απλούστερη μορφή τους για κάθε όρο t του λεξιλογίου περιέχουν στοιχεία όπου tf(t,d) είναι η συχνότητα του όρου t στο κείμενο d. Τα στοιχεία αυτά επαρκούν μαζί με άλλα στατιστικά στοιχεία, όπως το μέγεθος του κειμένου |d| και το πλήθος των κειμένων που περιέχουν τον όρο t, df(t), για την αξιολόγηση ερωτημάτων. Για την υποστήριξη φράσεων ή ερωτημάτων εγγύτητας (proximity) αποθηκεύονται επιπρόσθετες πληροφορίες στις ανεστραμμένες λίστες, όπως είναι τα offsets που παριστούν την απόσταση ενός όρου t από την αρχή του κειμένου d για κάθε εμφάνιση του όρου στο κείμενο. Οι ανεστραμμένες λίστες συνήθως είναι ταξινομημένες σε αύξουσα σειρά ως προς το d, καθώς και τα offsets με τον ίδιο τρόπο. Αν οι ανεστραμμένες λίστες είναι ταξινομημένες ως προς docID τότε θα μπορούσαμε να αποθηκεύσουμε στη λίστα τις διαφορές μεταξύ διαδοχικών docIDs. Ο λόγος είναι ότι για τους όρους με υψηλή συχνότητα κειμένων (df) οι διαφορές θα είναι μικρές και το αντίθετο θα συμβαίνει για κείμενα με μικρό df. Επειδή οι αλγόριθμοι συμπίεσης είναι καλύτεροι για μικρούς ακεραίους αναμένουμε με αυτό τον τρόπο μεγαλύτερο όφελος. Έστω η ανεστραμμένη λίστα που αντιστοιχεί στον όρο «information»: (<tf(t,d), d, [ofs(t)]>)
< 3, 7, [6, 51, 117] > < 1, 44, [12] > < 2, 117, [14, 1077] >
Για την αξιολόγηση ενός ερωτήματος πρώτα αναζητούνται οι όροι του ερωτήματος στο λεξιλόγιο. Μετά ανακτώνται από το δίσκο οι αντίστοιχες ανεστραμμένες λίστες για κάθε όρο και επεξεργάζονται σε αύξουσα σειρά ως προς το df. Για κάθε στοιχείο κάθε λίστας ενημερώνεται ένα αθροιστικό βάρος-ομοιότητας, Sim, για κάθε κείμενο. Η αύξηση από την ενημέρωση αυτή εξαρτάται από το μέτρο ομοιότητας που χρησιμοποιείται, από τα βάρη των όρων στο ερώτημα, w(t,q) και τα βάρη των όρων στο κείμενο, w(t,d) καθώς και άλλους παράγοντες. Στο τέλος οι ομοιότητες των κειμένων με το ερώτημα (Sim(q,d)) ταξινομούνται σε φθίνουσα σειρά και έτσι υπολογίζονται τα πλέον σχετικά κείμενα στο ερώτημα. Τα κείμενα αυτά ανά δεκάδες εμφανίζονται στον χρήστη. Τα offsets των όρων μέσα στα κείμενα δεν χρησιμοποιούνται στην αξιολόγηση των ερωτημάτων παρά μόνο σε ερωτήματα φράσεων (ή εγγύτητας). Τα ερωτήματα φράσεων απαιτούν οι αντίστοιχες λέξεις να βρίσκονται σε συνεχόμενες θέσεις μέσα στο κείμενο όχι όμως κατ’ ανάγκη και με την ίδια σειρά. Για παράδειγμα σ’ ένα ερώτημα φράσης γίνεται η αξιολόγηση του ερωτήματος όπως περιγράφτηκε παραπάνω και μετά αντί για το αθροιστικό βάρος κατασκευάζουμε μία προσωρινή ανεστραμμένη λίστα για την φράση, συνδυάζοντας τις ανεστραμμένες λίστες όλων των όρων του ερωτήματος. Για παράδειγμα αν η ανεστραμμένη λίστα που αντιστοιχεί στον όρο «retrieval» είναι η:
< 1, 7, [52]> <2, 12, [1, 4]> <1, 44, [83] >
τότε και οι δύο λέξεις υπάρχουν στο κείμενο 7 σε συνεχόμενες θέσεις [51, 52]. Επομένως η απάντηση στο ερώτημα «information retrieval» είναι το κείμενο 7. Στη συνέχεια, η διαδικασία αξιολόγησης συνεχίζεται κανονικά. Χωρίς την συμπίεση το κόστος ως προς τον χρόνο ισούται με τον χρόνο προσπέλασης (seek) και μεταφοράς των ανεστραμμένων λιστών από το δίσκο στη CPU cache πριν την επεξεργασία τους. Η ταχύτητα της ανάκτησης των συμπιεσμένων ανεστραμμένων λιστών καθορίζεται από δύο παράγοντες: Ένας αλγόριθμος συμπίεσης μπορεί να χρησιμοποιηθεί μόνο όταν ο χρόνος αξιολόγησης του ερωτήματος από συμπιεσμένα αρχεία είναι το πολύ ίσος με τον αντίστοιχο χρόνο όταν τα αρχεία δεν έχουν συμπιεστεί. Αυτό επιτυγχάνεται γιατί με τη συμπίεση των ανεστραμμένων λιστών αυξάνεται το πλήθος των λιστών που μπορεί να βρίσκονται (cached) στη μνήμη μεταξύ των ερωτημάτων και έτσι ελαττώνεται το πλήθος των προσπελάσεων στους δίσκους. Υπάρχουν δύο γενικές τεχνικές συμπίεσης που είναι κατάλληλες για ανεστραμμένα αρχεία.
  1. Κωδικοποίηση ακεραίων με μεταβλητό πλήθος από bits (bitwise). Τέτοιοι αλγόριθμοι περιλαμβάνουν τους αλγόριθμους κωδικοποίησης Elias gamma και delta.
  2. Κωδικοποίηση κατά Bytes. Bytewise τεχνικές που αποθηκεύουν ένα ακέραιο με ένα μεταβλητό πλήθος από bytes. Συνήθως σε όλες τις αρχιτεκτονικές υπολογιστών ένας ακέραιος έχει σταθερό μέγεθος τεσσάρων bytes.
Στη συνέχεια περιγράφουμε συνοπτικά τις τεχνικές αυτές.

Αλγόριθμος Elias – gamma

Ο αλγόριθμος Elias-gamma είναι απλός αλλά όχι βέλτιστος αλγόριθμος. Η κωδικοποίηση ενός ακεραίου, x, γίνεται με το ελάχιστο πλήθος bits που απαιτούνται, δηλαδή με log2and1 bits. Στη δυαδική αναπαράσταση του x, προηγούνται log2 μηδενικά ως πρόθεμα. Το πρόθεμα με τα μηδενικά δηλώνει πόσα bits χρειάζονται για την κωδικοποίηση του x δηλαδή log2and1. Σχηματικά ο αλγόριθμος περιγράφεται ως εξής:

eliasgamma



eliasgamma
Πίνακας 11. Παραδείγματα Elias-gamma κωδικοποίησης.


Έτσι έχουμε ένα απλό αλγόριθμο αποκωδικοποίησης αφού το συνολικό μήκος της κωδικολέξης είναι ίσο με το διπλάσιο του πλήθους των μηδενικών του προθέματος συν ένα. Επομένως μόλις συναντήσουμε το πρώτο 1 το μήκος της κωδικολέξης είναι γνωστό. Για ένα ακέραιο x η κωδικολέξη που προκύπτει από τον αλγόριθμο Elias-gamma έχει μήκος
lengthgamma
bits. Ο αλγόριθμος Elias-gamma δεν είναι βέλτιστος καθόσον ο λόγος του αναμενόμενου μεγέθους των κωδικολέξεων προς την εντροπία τείνει στο 2. Απόδειξη: Έστω μια τυχαία μεταβλητή Χ με ομοιόμορφη κατανομή στο σύνολο {1,2,...Ν}. Τότε η εντροπία της Χ ισούται με Η(Χ)=log2N (η απόδειξη άσκηση). Ως γνωστό μετράται σε bits και δηλώνει το πλήθος των bits ανά σύμβολο-ακέραιο). Από τον αλγόριθμο Elias-gamma προκύπτει ότι το αναμενόμενο μήκος μιας κωδικολέξης (δυαδική αναπαράσταση ενός ακεραίου) είναι:

eliasproof

Αλγόριθμος Elias – delta

Ο αλγόριθμος Elias-delta, αντιστοιχεί σε ένα ακέραιο x τη κωδικολέξη, Cδ(x), που αποτελείται από ένα πρόθεμα με Cγ(?log2x?+1) μηδενικά, ακολουθούμενο από την δυαδική τιμή του x χωρίς την πρώτη μονάδα. Σχηματικά ο αλγόριθμος περιγράφεται ως εξής: Η κωδικολέξη που προκύπτει από τον αλγόριμο Elias-delta έχει μήκος:
lengthdelta
Η διαδικασία μπορεί να εφαρμοστεί αναδρομικά ώστε να μικρύνει ακόμη το μήκος της κωδικολέξης, αλλά τα οφέλη ελαττώνονται πολύ γρήγορα. Η κωδικοποίηση Elias-delta είναι ασυμπτωτικά βέλτιστη καθόσον ο λόγος του αναμενόμενου μεγέθους των κωδικολέξεων προς την εντροπία τείνει στο 1. Η απόδειξη είναι ομοία με αυτή του αλγορίθμου Elias-gamma. Ο αλγόριθμος gamma για ακέραιους μικρότερους του 15 επιτυγχάνει καλύτερη συμπίεση ενώ ο delta είναι καλύτερος για ακεραίους μεγαλύτερους του 15.

deltaexample
Πίνακας 2. Παραδείγματα Κωδικοποίησης Elias-delta.

Συμπίεση με Μεταβλητό Πλήθος Bytes

Στους bytewise αλγόριθμους κωδικοποίησης ένας ακέραιος αποθηκεύεται σε ακέραιο αριθμό από bytes. Για κώδικες variable-byte, χρησιμοποιούνται 7 bits από κάθε block για την δυαδική αποθήκευση ενός ακεραίου k. Το όγδοο bit χρησιμοποιείται για να δηλώσει ότι το τρέχων block είναι το τελικό block για τον ακέραιο k, ή ότι ακολουθεί και άλλο block. Έστω για παράδειγμα ένας ακέραιος k στο διάστημα από 2^7 = 128 έως 214 = 16,384. Δύο blocks απαιτούνται για την παράσταση του ακεραίου αυτού: το πρώτο block περιέχει τα επτά λιγότερο σημαντικά bits του ακέραιου και το όγδοο bit χρησιμοποιείται ως σημαία (flag) ότι ακολουθεί και άλλο block. Το δεύτερο block περιέχει τα υπόλοιπα περισσότερο σημαντικά bits και το όγδοο bit δηλώνει ότι δεν υπάρχει άλλο block. Το flag bit έχει τιμή 1 στο τελικό block και 0 διαφορετικά. Όμοια για τους αριθμούς στο διάστημα 0