Αλγόριθμος Αντιστροφής Αρχείου


Στην ενότητα αυτή θα περιγράψουμε ένα γρήγορο αλγόριθμο για την κατασκευή του ανεστραμμένου αρχείου δοθείσης μιας συλλογής κειμένων. Έστω, για παράδειγμα, ότι μετά την προεπεξεργασία μιας συλλογής, D, έχουμε Ν (=5) διανύσματα κειμένων, d=(t1, t2, …, tn) και έστω ότι θέλουμε να κατασκευάσουμε το ανεστραμμένο αρχείο που αντιστοιχεί στα παραπάνω διανύσματα. Για παράδειγμα, έστω το σύνολο των κειμένων του πίνακα 3.

documentvectors
Πίνακας 3. Τα διανύσματα των κειμένων της συλλογής

Το ανεστραμμένο αρχείο που αντιστοιχεί στα κείμενα αυτά δίνεται στον πίνακα 4-4. Στη συνέχεια θα περιγράψουμε τον αλγόριθμο σε 6 βήματα.

documentvectors
Πίνακας 4. Ανεστραμμένο αρχείο

ΒΗΜΑ 1: Διαβάζουμε τα κείμενα της συλλογής (πίνακας 4-3) και κατασκευάζουμε ένα αρχείο (DocVec) από τριάδες (docID, termID, tf(termID)). To tf δίνει το πλήθος εμφανίσεων του όρου termID στο κείμενο docID. Ένα μέρος του αρχείου αυτού φαίνεται στο πίνακα 4-5.

docvec
Πίνακας 5. Αρχείο DocVec

BHMA 2: Από το αρχείο DocVec κατασκευάζουμε ένα διάνυσμα (df) μεγέθους ίσου με το πλήθος των μοναδικών όρων στη συλλογή. Για το παράδειγμά μας το διάνυσμα, df, στον πίνακα 4-8 έχει μέγεθος 14. for each (docID, termID) in DocVec df[termID]++;

dfvec
Πίνακας 6. Το διάνυσμα df δίνει το πλήθος των κειμένων που περιέχουν κάθε όρο

ΒΗΜΑ 3: Διασχίζουμε το διάνυσμα df και κατασκευάζουμε το παρακάτω βοηθητικό πίνακα, T, του σχήματος 7:
i=0; offset=0;
for (termID=1 to N )
{
T[i][0]=termID;
T[i][1]=offset;
T[i][2]=df[termID];
i++;
offset=offset+T[i][2];
}
Το στοιχείο Τ[i][3] καθορίζεται έτσι ώστε να σχηματίζονται ισομεγέθη τμήματα που χωρούν στη μνήμη.

tempmatrix1
Πίνακας 7. Βοηθητικός πίνακας Τ

ΒΗΜΑ 4: Με βάση τον πίνακα Τ παραπάνω κατασκευάζουμε τον πίνακα RUNS ο οποίος περιέχει πληροφορίες για κάθε ένα από τα 3 τμήματα (Loads) του αρχικού αρχείου. Το μέγεθος κάθε τμήματος υπολογίζεται έτσι ώστε να χωρά στη μνήμη. O κώδικας για το βήμα αυτό είναι το ζητούμενο της άσκησης 3, στο τέλος του κεφαλαίου αυτού.

tempmatrix
Πίνακας 8. Βοηθητικός πίνακας για κάθε τμήμα του αρχείου που θα αντιστραφεί.


ΒΗΜΑ 5: Με βάση το αρχείο DocVec των (docID, termID, TF) και τους πίνακες T και RUNS αντιστρέφουμε τα στοιχεία που αντιστοιχούν σε κάθε Load ώστε να είναι στη μορφή (termID, docID, TF) και τα γράφουμε το ένα μετά το άλλο σ’ ένα αρχείο στο δίσκο. for each pair (docID, termID) in DocVec Βρες το Run που περιέχει το TermID; if (termID in [Runs[i].start, Runs[i].end] then write (docID, termID) in a corresponding file (Load); Έτσι προκύπτουν για το παράδειγμά μας τρία Loads, όπως φαίνεται στο πίνακα 4-9.

Loadsinvert
Πίνακας 9. Τα Loads μπορούν να αντιστραφούν χωρίς να επηρεάζει το ένα το άλλο.


ΒΗΜΑ 6: Από τα παραπάνω Loads κατασκευάζεται το λεξικό με τις αντίστοιχες ανεστραμμένες λίστες όπως φαίνεται στο σχήμα 4-10. Ο κώδικας επαφίεται ως άσκηση στον αναγνώστη (Άσκηση 4 στο τέλος του κεφαλαίου).

invertedlists
Πίνακας 10. Το ευρετήριο όρων και οι ανεστραμμένες λίστες.