Ανεστραμμένα Αρχεία

---

Η προσπέλαση στα δεδομένα κατά την αξιολόγηση ενός ερωτήματος γίνεται μέσω ενός ευρετηρίου. Το κόστος της αξιολόγησης του ερωτήματος είναι ανάλογο του πλήθους των όρων στο ερώτημα (Ο(|Q|)). Κατά την στιγμή του ερωτήματος δεν μπορεί κανείς να προβλέψει τις λέξεις κλειδιά που θα χρησιμοποιηθούν. Κάθε λέξη είναι δυναμικά και ένας όρος αναζήτησης. Επομένως στο ευρετήριο αποθηκεύονται όλοι οι όροι των κειμένων. Τα περιεχόμενα του ευρετηρίου μπορεί να είναι Boolean (δυαδικά) ή στατιστικά ή δεδομένα θέσης των όρων μέσα στα κείμενα. Επίσης μπορεί να αποθηκεύονται η πρόταση ή η παράγραφος στην οποία ανήκει ο όρος. Στη βιβλιογραφία υπάρχουν διάφορες μέθοδοι για την υλοποίηση ευρετηρίων για κείμενα. Για παράδειγμα έχουμε: Bitmaps, αρχεία υπογραφών (signature files), ανεστραμμένα αρχεία, κατακερματισμός, n-grams κ.ά. Στα επόμενα θα περιγράψουμε τα ανεστραμμένα αρχεία καθόσον αυτά είναι τα πλέον διαδεδομένα στα συστήματα ανάκτησης. Τα βασικά στοιχεία ενός ανεστραμμένου ευρετηρίου είναι δύο: Το λεξιλόγιο (dictionary) και οι ανεστραμμένες λίστες (inverted lists, postings) οι οποίες περιέχουν τα κείμενα στα οποία εμφανίζεται κάθε όρος του λεξιλογίου, το βάρος του, η θέση του στο κείμενο κ.ά. Κατά την διάρκεια της αξιολόγησης του ερωτήματος διασχίζονται οι ανεστραμμένες λίστες των όρων του ερωτήματος και εφαρμόζονται οι πράξεις:

• OR: ένωση δύο ανεστραμμένων λιστών
• AND: Τομή δύο ανεστραμμένων λιστών
• Proximity: Τομή δύο ανεστραμμένων λιστών
• SUM: ένωση δύο ανεστραμμένων λιστών

Έστω ότι τα κείμενα μιας συλλογής δίδονται μ’ ένα αρχείο του οποίου κάθε γραμμή αντιστοιχεί σ’ ένα κείμενο (βλέπε πίνακα 4-1). Υπάρχουν δύο βασικές δομές για την οργάνωση των δεδομένων του λεξιλογίου: Δέντρα αναζήτησης (Β, Β+ δέντρα) και κατακερματισμός. Το κόστος προσπέλασης στα Β δέντρα για τον εντοπισμό μιας ανεστραμμένης λίστας είναι Ο(logmn), όπου m είναι ο βαθμός του δέντρου και στον κατακερματισμό είναι Ο(1). Στα Β δέντρα η εισαγωγή είναι απλή ενώ στον κατακερματισμό μπορεί να είναι δαπανηρή. Συνήθως το λεξιλόγιο αποθηκεύεται σε μια δυναμική δομή δεδομένων όπως είναι τα Β δέντρα και κάθε στοιχείο συνδέεται με τη λίστα που περιέχει τα κείμενα που περιέχουν το αντίστοιχο στοιχείο. Για τα κείμενα του παραδείγματος αν θεωρήσουμε ότι το σύνολο των τετριμμένων λέξεων είναι το: {ΑΠΟ, ΔΕΝ, ΕΙΝΑΙ, ΕΝΑ, Η, ΗΤΑΝ, ΜΙΑ, ΜΙΑΣ, ΠΟΥ, ΤΑ, ΤΗΝ, ΤΗΣ, ΤΟ, ΤΟΥ, ΤΩΝ} και αφού εφαρμόσουμε τον αλγόριθμο αποκοπής καταλήξεων προκύπτει το ανεστραμμένο αρχείο που δίνεται στον πίνακα 4-2. Ο αλγόριθμος κατασκευής του ανεστραμμένου αρχείου περιγράφεται ως εξής:

1. Λεξική ανάλυση (tokenization);
2. Yπογισμός της συχνότητας εμφάνισης του όρου σε κάθε κείμενο (tf(t,d));
3. Υπολογισμός της συχνότητας κειμένων των όρων (df(t));
Αποθήκευση των ανεστραμμένων λιστών στο δίσκο

Πίνακας 1 Παράδειγμα συλλογής κειμένων

Για μεγάλα αρχεία η δομή δεν μπορεί να χωρέσει στη μνήμη. Στη περίπτωση αυτή η πλέον αποτελεσματική προσέγγιση είναι η αντιστροφή του αρχείου κατά τμήματα στη μνήμη. Δύο προσεγγίσεις υπάρχουν για τη λύση αυτού του προβλήματος. Η πρώτη περίπτωση περιλαμβάνει ένα αλγόριθμο με εύκολο χώρισμα του αρχείου σε τμήματα, την αντιστοφή των τμημάτων και τέλος την συγχώνευσή τους που ως συνήθως είναι μια δύσκολη διαδικασία. Η δεύτερη περίπτωση περιλαμβάνει τις τρεις διιαδικασίας όπως προηγούμενα αλλά η δυσκολία τους είναι αντιστραμμένη. Δηλαδή έχουμε ένα δύσκολο χώρισμα του αρχείου σε τμήματα, την αντιστροφή τους και τέλος την συγχώνευσή τους που στη περίπτωση αυτή είναι μια απλή συννένωση (append). Στη συνέχεια θα περιγράψουμε μια μέθοδο που ανήκει στη δεύτερη κατηγορία.
Αλγόριθμος κατασκευής ανεστραμμένου αρχείου
/* Αρχικοποίηση */
Δημιούργησε μια κενή δομή dictionary S;
/* Φάση 1: Υπολογισμός συχνοτήτων των όρων */
for κάθε κείμενο di της συλλογής (1≤ i ≤N)
διάβασε di;
for κάθε όρο tj ∈ di
{ υπολόγισε tf(tj,di);
Ενημέρωσε το df(tj)
/*Αναζήτησε τον όρο t στο S*/
if t ∉ S
{εισάγαγε tj στο S;
εισάγαγε τον κόμβο (di; tf(tj,di) στην αρχή της
ανεστραμμένης λίστας που αντιστοιχεί στον όρο tj;}
else εισάγαγε τον κόμβο (di; tf(tj,di) στο τέλος της
ανεστραμμένης λίστας που αντιστοιχεί στον όρο tj;
}
/* Φάση 2: Γράψιμο ανεστραμμένου αρχείου στο δίσκο */
for κάθε όρο tj, 1 ≤ j ≤ n
{ξεκίνησε μια νέα εγγραφή στο ανεστραμμένο αρχείο;
for κάθε εγγραφή di; TF(tj,di) στη λίστα του όρου tj
if απαιτείται συμπίεσε την εγγραφή;
γράψε στο τέλος του αρχείο (append)το (di; TF(t,di);
}


Πίνακας 2 Ανεστραμμένο αρχείο