Κεφάλαιο 7Ο Κατάλογος Υπογραφών

Μία από τις πρώτες μεθόδους παραγωγής υπογραφών για την επεξεργασία εγγράφων κειμένου προτάθηκε από τους Tsichritzis και Christodoulakis [72]. Σύμφωνα με τη μέθοδο αυτή, από τον κάθε όρο $t$ του εγγράφου εξάγεται μία υπογραφή $TS(t)$ μήκους $f$. Η υπογραφή του συνολικού εγγράφου $d$, που συμβολίζεται με $DS(d)$, προκύπτει με τη συνένωση (concatenation) όλων των υπογραφών των όρων που συναντούμε στο έγγραφο. Αυτή η μέθοδος εξαγωγής υπογραφών είναι γνωστή ως WS (word signatures). Έστω $t_q$ ένας όρος που βρίσκεται στο ερώτημα. Αρχικά, εξάγεται η υπογραφή $TS(t_q)$ και στη συνέχεια ελέγχονται οι υπογραφές των εγγράφων. Σε περίπτωση που βρεθεί μία υπογραφή $DS(d)$ που αντιστοιχεί στο έγγραφο $d$ και περιέχει την υπογραφή $TS(t_q)$ τότε αυτό σημαίνει ότι το έγγραφο $d$ μπορεί να περιέχει τον όρο $t_q$. Στην περίπτωση αυτή, το $d$ θεωρείται ως υποψήφιο έγγραφο.

Ένας άλλος τρόπος εξαγωγής υπογραφών προτάθηκε από τους Faloutsos και Christodoulakis [16]. Η μέθοδος εξαγωγής καλείται SC (superimposed coding) και σύμφωνα με αυτήν το έγγραφο χωρίζεται σε λογικά τμήματα (logical blocks) και το κάθε τμήμα περιέχει ένα μέρος του εγγράφου που αποτελείται από $T$ όρους. Μας ενδιαφέρουν οι μοναδικοί όροι του λογικού τμήματος και επομένως δε λαμβάνονται υπόψη οι πολλαπλές εμφανίσεις των όρων. Από κάθε όρο $t$ υπολογίζεται η υπογραφή του όρου $TS(t)$ μήκους $F_{SC}$. Στη συνέχεια, χρησιμοποιείται υπέρθεση (superposition) σύμφωνα με την οποία εφαρμόζεται ο λογικός τελεστής OR σε ένα προς ένα τα δυαδικά ψηφία των υπογραφών και προκύπτει η υπογραφή του τμήματος. Η υπογραφή του συνολικού εγγράφου προκύπτει με τη συνένωση των υπογραφών των τμημάτων. Για την αναζήτηση των εγγράφων που περιέχουν τον όρο $t_q$ ακολουθείται παρόμοια διαδικασία με την προηγούμενη μέθοδο χρησιμοποιώντας τις υπογραφές των τμημάτων. Αρχικά, εξάγεται η υπογραφή του όρου $TS(t_q)$ και στη συνέχεια προσδιορίζονται οι υπογραφές των τμημάτων των οποίων οι θέσεις που έχουν άσσους ταυτίζονται με τις αντίστοιχες θέσεις των άσσων της υπογραφής $TS(t_q)$. Στην περίπτωση αυτή, το συγκεκριμένο τμήμα μπορεί να περιέχει τον όρο $t_q$ και επομένως το αντίστοιχο έγγραφο θεωρείται υποψήφιο.

Για να είναι δυνατή η αναζήτηση μέρους (και όχι ολόκληρου) του όρου, οι Faloutsos και Christodoulakis [16] πρότειναν την ακόλουθη παραλλαγή: (i) στον όρο $t$ εισάγονται δύο κενοί χαρακτήρες στην αρχή και στο τέλος του όρου, (ii) δημιουργούνται συνεχόμενες και επικαλυπτόμενες τριάδες χαρακτήρων, (iii) η κάθε τριάδα μέσω του κατακερματισμού ενεργοποιεί ένα συγκεκριμένο δυαδικό ψηφίο της υπογραφής και (iv) εάν ο αριθμός $\psi$ των δυαδικών ψηφίων που ενεργοποιούνται είναι μεγαλύτερος από $m$, τότε μόνο $m$ δυαδικά ψηφία θα ενεργοποιηθούν, διαφορετικά (αν $\psi$ ¡ $m$) τότε τα υπόλοιπα $m$-$\psi$ δυαδικά ψηφία ενεργοποιούνται χρησιμοποιώντας μία γεννήτρια τυχαίων αριθμών με φίτρο (seed) που ισούται με μία αριθμητική αναπαράσταση του συγκεκριμένου όρου. Όπως και προηγουμένως, το έγγραφο χωρίζεται σε τμήματα και η διαδικασία εκτελείται για όλους τους όρους του κάθε τμήματος. Στη συνέχεια, δημιουργούνται οι υπογραφές των τμημάτων με χρήση υπέρθεσης και τέλος κατασκευάζεται η υπογραφή του εγγράφου με συνένωση των υπογραφών των τμημάτων.

Η τρίτη μέθοδος εξαγωγής υπογραφών, που καλείται BC (bit-block compression), βασίζεται στη συμπίεση και προτάθηκε στην εργασία [21]. Όπως και στην προηγούμενη μέθοδο, το έγγραφο χωρίζεται σε τμήματα. Στην περίπτωση αυτή χρησιμοποιείται για κάθε τμήμα μία υπογραφή μεγαλύτερου μεγέθους που αποτελείται από $B$ δυαδικά ψηφία. Ο κατακερματισμός του κάθε όρου του τμήματος θα ενεργοποιήσει ένα ή περισσότερα (έστω $n$) δυαδικά ψηφία της υπογραφής. Το διάνυσμα δυαδικών ψηφίων που προκύπτει χαρακτηρίζεται ως αραιό (περιέχει λίγους άσσους σε σχέση με τα μηδενικά) και επομένως μπορεί να συμπιεστεί κατάλληλα. Η προτεινόμενη μέθοδος συμπίεσης χρησιμοποιεί τμήματα δυαδικών ψηφίων (bit-blocks). Το αραιό διάνυσμα που έχει προκύψει χωρίζεται σε τμήματα δυαδικών ψηφίων. Το μέγεθος των τμημάτων επιλέγεται έτσι ώστε να βελτιστοποιείται η απόδοση της μεθόδου. Στη συνέχεια, για κάθε τμήμα $b{b}_i$ δημιουργείται μία νέα υπογραφή μεταβλητού μήκους που αποτελείται από τρία το πολύ μέρη:

• •

  Το πρώτο μέρος της υπογραφής αποτελείται από ένα δυαδικό ψηφίο το οποίο είναι 1 αν υπάρχει τουλάχιστον ένας άσσος στο τμήμα $b{b}_i$ ή 0 διαφορετικά. Αν ισχύει το δεύτερο, τότε η μέθοδος σταματά εδώ.

• •

  Το δεύτερο μέρος της υπογραφής που προκύπτει από το $b{b}_i$ δηλώνει τον αριθμό των άσσων που περιέχονται στο $b{b}_i$. Ο αριθμός αυτός κωδικοποιείται χρησιμοποιώντας το μοναδιαίο κώδικα, βάσει του οποίου ένας αριθμός $x$ κωδικοποιείται με $x$-1 άσσους και ένα μηδενικό στο τέλος. Αν και αυτός ο τρόπος κωδικοποίησης δεν είναι ο βέλτιστος, ωστόσο είναι απλός και δίνει ικανοποιητικά αποτελέσματα.

• •

  Το τρίτο τμήμα της υπογραφής αποθηκεύει τις θέσεις των άσσων στο τμήμα $b{b}_i$ χρησιμοποιώντας την απόσταση του ψηφίου από την αρχή του $b{b}_i$. Επομένως, εάν το μέγεθος του τμήματος $b{b}_i$ είναι $b$ δυαδικά ψηφία, για την καταχώρηση της θέσης ενός άσσου απαιτούνται $\log b$ δυαδικά ψηφία.

Για το σχηματισμό της τελικής υπογραφής του τμήματος $b{b}_i$ έχουμε δύο εναλλακτικές λύσεις: (i) γίνεται συνένωση όλων των τμηματικών υπογραφών και (ii) παραθέτουμε πρώτα τα πρώτα μέρη, μετά τα δεύτερα και τέλος τα τρίτα από κάθε τμηματική υπογραφή. Η διαδικασία αυτή θα γίνει περισσότερο κατανοητή με το παράδειγμα που ακολουθεί.

Στην εργασία [21] περιγράφεται και μία ακόμη μέθοδος εξαγωγής υπογραφών που βασίζεται στη συμπίεση, χρησιμοποιεί κωδικοποίηση μήκους (run-length encoding) και καλείται RL. Η μέθοδος είχε προταθεί αρχικά από τον McIlroy [44] για διαφορετικό περιβάλλον αλλά στην εργασία [21] προσαρμόστηκε για την εξαγωγή υπογραφών. Το αραιό διάνυσμα μπορεί να συμπιεστεί κωδικοποιώντας τον αριθμό των μηδενικών που διαχωρίζουν δύο συνεχόμενους άσσους. Για την κωδικοποίηση χρησιμοποιήθηκε η μέθοδος Golomb [29] που μελετήθηκε στο Κεφάλαιο 6 κατά την περιγραφή των μεθόδων συμπίεσης του αντεστραμμένου καταλόγου.

Στην ίδια εργασία [21] προτείνεται και μία ακόμη μέθοδος που προσπαθεί να περιορίσει την επίδραση του αριθμού των όρων ανά τμήμα στην απόδοση της μεθόδου BC. Επομένως, με τη χρήση αυτής της μεθόδου δεν απαιτείται πλέον ο διαχωρισμός του εγγράφου σε τμήματα, ενώ η επεξεργασία των πολύπλοκων ερωτημάτων γίνεται απλούστερη. Η μέθοδος καλείται VBC (variable bit-block compression) και η βασίζεται στην επιλογή διαφορετικού μήκους για τα τμήματα δυαδικών ψηφίων του κάθε εγγράφου. Το μήκος αυτό εξαρτάται από το πλήθος των μοναδικών όρων του κάθε εγγράφου.

Το κοινό χαρακτηριστικό όλων των μεθόδων εξαγωγής υπογραφών είναι το γεγονός ότι μπορεί να δώσουν λανθασμένο αποτέλεσμα ως προς το αν ένας όρος περιέχεται ή όχι σε ένα έγγραφο. Έστω ένα όρος $t$ του ερωτήματος με υπογραφή 00110. Έστω τώρα ότι χρησιμοποιώντας τη μέθοδο εξαγωγής υπογραφών με υπέρθεση (SC) έχουμε εντοπίσει ένα τμήμα του εγγράφου με υπογραφή 10110. Το γεγονός ότι η υπογραφή του τμήματος έχει άσσους στις θέσεις όπου εμφανίζονται οι άσσοι στην υπογραφή του όρου δε σημαίνει ότι ο όρος σίγουρα θα περιέχεται στο τμήμα. Πράγματι, αν υποτεθεί ότι το κάθε τμήμα του εγγράφου αποτελείται από δύο όρους, τότε η υπογραφή 10110 μπορεί να έχει προκύψει από την υπέρθεση των υπογραφών 10100 και 10010. Στην περίπτωση αυτή είναι προφανές ότι ο όρος $t$ δεν περιέχεται στο τμήμα του εγγράφου. Η παραπάνω συζήτηση οδηγεί στο συμπέρασμα ότι μετά τον προσδιορισμό των υποψήφιων εγγράφων θα πρέπει να γίνει ένα δεύτερο πέρασμα ώστε τα έγγραφα που τελικά δεν περιέχουν τον όρο (ή τους όρους) του ερωτήματος να μην επιστραφούν στο χρήστη. Ένα έγγραφο που ανήκει στο σύνολο των υποψηφίων αλλά τελικά δεν ανήκει στην απάντηση καλείται ψευδής συναγερμός (η αντίστοιχος αγγλικός όρος είναι false alarm ή false positive). Είναι προφανές ότι όσο μικρότερος είναι ο αριθμός των ψευδών συναγερμών τόσο λιγότερη προσπάθεια θα απαιτηθεί για το τελικό ξεκαθάρισμα.

Στο Σχήμα 7.2 δίνονται τα βασικά βήματα του γενικού αλγορίθμου αναζήτησης των εγγράφων που περιέχουν έναν όρο. Βασική συμμετοχή στο κόστος αναζήτησης έχει ο προσδιορισμός των ψευδών συναγερμών. Υποθέτουμε ότι το έγγραφο έχει χωριστεί σε λογικά τμήματα και για κάθε λογικό τμήμα έχει προσδιοριστεί μία ξεχωριστή υπογραφή με χρήση της μεθόδου υπερθεσης (SC). Σύμφωνα με τον αλγόριθμο αναζήτησης, αρχικά προσδιορίζεται η υπογραφή του όρου $t$. Στη συνέχεια, προσδιορίζονται όλα τα λογικά τμήματα των οποίων οι υπογραφές έχουν άσσους στις θέσεις των άσσων της υπογραφής του όρου $t$. Τα τμήματα αυτά χαρακτηρίζονται ως υποψήφια να περιέχουν τον όρο $t$. Ο προσδιορισμός των ψευδών συναγερμών πραγματοποιείται στο βήμα 4.1 του αλγορίθμου. Η αναζήτηση εγγράφων για ερωτήματα που περιέχουν περισσότερους όρους που συνδέονται με λογικούς τελεστές πραγματοποιείται με παρόμοιο τρόπο.

Στη συνέχεια θα συζητήσουμε για την επίδοση των μεθόδων εξαγωγής υπογραφών ως προς τις δυνατότητές τους να περιορίζουν τον αριθμό των ψευδών συναγερμών. Γίνεται η υπόθεση ότι το ερώτημα περιέχει μόνο έναν όρο. Έστω δύο γεγονότα ${\mathrm{\Gamma }}_1$ και ${\mathrm{\Gamma }}_2$, όπου το ${\mathrm{\Gamma }}_1$ δηλώνει το γεγονός ότι η υπογραφή ενός λογικού τμήματος εγγράφου ανήκει στους υποψηφίους και ${\mathrm{\Gamma }}_2$ δηλώνει το γεγονός ότι το τμήμα του εγγράφου δεν περιέχει τον όρο του ερωτήματος. Επομένως, η πιθανότητα να εμφανιστεί ένας ψευδής συναγερμός είναι η πιθανότητα να ισχύει το γεγονός ${\mathrm{\Gamma }}_1$ δεδομένου ότι ισχύει το γεγονός ${\mathrm{\Gamma }}_2$ ($Prob({\mathrm{\Gamma }}_1|{\mathrm{\Gamma }}_2)$). Η πιθανότητα αυτή συμβολίζεται με $FA{P}_{xx}$ (false alarm probability) για τη μέθοδο $xx$. Είναι προφανές, ότι όσο μικρότερη η τιμή της πιθανότητας αυτής τόσο καλύτερη η επίδοση της μεθόδου. Η μελέτη της πιθανότητας εμφάνισης ψευδών συναγερμών οδηγεί σε χρήσιμα συμπεράσματα σχετικά με την απόδοση των μεθόδων υπογραφών ως προς την ικανότητά τους να εντοπίζουν τους όρους μέσα στα έγγραφα.

Στην εργασία [21] υπάρχει μία εκτενής ανάλυση της πιθανότητας $FAP$. Εδώ απλά θα γίνει αναφορά των σημαντικότερων συμπερασμάτων, καθώς οι αποδείξεις είναι εκτενείς. Από τη μελέτη της συμπεριφοράς των μεθόδων προκύπτουν τα ακόλουθα αποτελέσματα σε σχέση με την πιθανότητα ψευδών συναγερμών:

• •

  Οι τεχνικές BC και RL που βασίζονται στη συμπίεση δίνουν καλύτερα αποτελέσματα από τις WS και SC όταν ο κάθε όρος θέτει έναν άσσο στην υπογραφή του λογικού τμήματος ($n$ = 1).

• •

  Για τις τεχνικές BC και RL ο βέλτιστος αριθμός των άσσων που επιτρέπεται να θέσει ένας όρος είναι $n$ = 1.

• •

  Οι γραφική παράσταση του λογάριθμου της πιθανότητας $FA{P}_{xx}$ σε σχέση με το μήκος $F_{xx}$ της υπογραφής είναι σχεδόν ευθεία γραμμή για μεγάλες τιμές της παραμέτρου $F_{xx}$.

• •

  Η κλήση των γραφικών παραστάσεων των καμπυλών της ποσότητας $\log FA{P}_{xx}$ ως προς $F_{xx}$ για τις μεθόδους WS, BC και RL είναι η ίδια. Η κλήση της καμπύλης για τη μέθοδο SC ωστόσο είναι διαφορετική, διότι η μέθοδος SC έχει την καλύτερη επίδοση όταν στην υπογραφή του λογικού τμήματος τα μισά δυαδικά ψηφία είναι άσσοι. Επομένως, δεν εκμεταλλεύεται πλήρως όλες τις δυνατές $2^{F_{SC}}$ διαφορετικές υπογραφές που μπορούν να προκύψουν από μία ακολουθία από $F_{SC}$ δυαδικών ψηφίων.

Στη συνέχεια για κάθε μία από τις μεθόδους WS, SC, BC και RL δίνεται ο μαθηματικός τύπος που συνδέει την πιθανότητα $FA{P}_{xx}$ με το μήκος $F_{xx}$ της υπογραφής. Σημειώνεται ότι οι τύποι είναι προσεγγιστικοί και έχουν προκύψει από μαθηματικούς συλλογισμούς. Ο αναγνώστης που ενδιαφέρεται για τον τρόπο παραγωγής των τύπων καλείται να ανατρέξει στην εργασία [21].

Εκτός από την επίδοση των μεθόδων σε σχέση με την πιθανότητα ψευδών συναγερμών, ιδιαίτερο ενδιαφέρον παρουσιάζουν και μερικά άλλα στοιχεία όπως η ταχύτητα κατά τον έλεγχο των υπογραφών, η απόδοση των μεθόδων σε πιο πολύπλοκα ερωτήματα, η δυνατότητα των μεθόδων να απαντούν σε ερωτήματα που αφορούν σε τμήμα ενός όρου και η δυνατότητα διατήρησης της σειράς των όρων στο έγγραφο. Το κάθε στοιχείο εξετάζεται ξεχωριστά:

• •

  Ως προς την ταχύτητα ελέγχου των υπογραφών, με βάση τον τρόπο λειτουργίας των μεθόδων και των παρατηρήσεων της εργασίας [21] η μέθοδος SC εκτελεί τις λιγότερες συγκρίσεις μεταξύ δυαδικών ψηφίων. Υπενθυμίζεται ότι για να χαρακτηριστεί ένα λογικό τμήμα ως υποψήφιο θα πρέπει οι θέσεις των άσσων στην υπογραφή του όρου να ταυτίζονται με τις θέσεις των άσσων στην υπογραφή του τμήματος. Συνήθως, ο αριθμός $m$ των δυαδικών ψηφίων που θέτει η μέθοδος SC είναι μικρός (π.χ., 10). Αντίθετα, οι μέθοδοι BC και RL απαιτούν πολύ περισσότερες συγκρίσεις. Τέλος η μέθοδος WS απαιτεί την εξέταση ολόκληρης της υπογραφής (του εγγράφου ή του τμήματος) για να διαπιστωθεί εάν περιέχει ή όχι τον όρο.

• •

  Όλες οι μέθοδοι αναμένεται να έχουν καλή επίδοση κατά την επεξεργασία συζευκτικών ερωτημάτων (τύπου AND). Αυτό ισχύει διότι το λογικό AND μεταξύ των υπογραφών των όρων έχει ως αποτέλεσμα τη μείωση των άσσων στην υπογραφή που προκύπτει μετά την υπέρθεση. Αυτό έχει ως άμεσο αποτέλεσμα τη μείωση του κόστους εξέτασης των υπογραφών.

• •

  Από τις μεθόδους που εξετάστηκαν μόνο η SC έχει τη δυνατότητα να υποστηρίξει ερωτήματα που αφορούν σε τμήμα του όρου. Αυτό επιτυγχάνεται χρησιμοποιώντας επικαλυπτόμενες τριάδες συνεχόμενων χαρακτήρων. Κάθε τριάδα ενεργοποιεί και ένα δυαδικό ψηφίο της υπογραφής του όρου.

• •

  Η μόνη μέθοδος που διατηρεί τη σειρά των όρων μέσα στο έγγραφο είναι η WS. Αυτό είναι ιδιαίτερα βολικό διότι διευκολύνει την αναζήτηση φράσεων όπου οι όροι στο ερώτημα πρέπει να εμφανίζονται συνεχόμενοι στα έγγραφα.

Η πιο απλή μορφή καταλόγου βασίζεται στη σειριακή παράθεση των υπογραφών σε ένα αρχείο που καλείται σειριακό αρχείο υπογραφών (sequential signature file - SSF). Η μορφή του SSF απεικονίζεται στο Σχήμα 7.4. Το αρχείο υπογραφών είναι στην ουσία ένας πίνακας $L\times F$ με $L$ γραμμές (πλήθος λογικών τμημάτων) και $F$ στήλες (πλήθος δυαδικών ψηφίων ανά υπογραφή). Σε κάθε υπογραφή αντιστοιχεί και ένα δείκτης (pointer) που δείχνει στην αρχή του λογικού τμήματος του εγγράφου. Σε περίπτωση που οι υπογραφές έχουν παραχθεί με την απλή μέθοδο της υπέρθεσης (SC) τότε το μήκος όλων των υπογραφών είναι κοινό. Εάν έχει χρησιμοποιηθεί μία από τς μεθόδους BC ή VBC τότε στη γενική περίπτωση τα μήκη δύο υπογραφών μπορεί να είναι διαφορετικά. Με βάση την κατηγοριοποίηση των μεθόδων του Σχήματος 7.3, διακρίνουμε τις μορφές SC-SSF, BC-SSF και VBC-SSF, ανάλογα με τη μέθοδο εξαγωγής υπογραφών που χρησιμοποιείται.

Ο κατάλογος SSF υποστηρίζει αναζητήσεις, εισαγωγές και διαγραφές. Για την αναζήτηση ενός όρου, αρχικά εξάγεται η υπογραφή του όρου και στη συνέχεια προσπελαύνεται το αρχείο υπογραφών με στόχο να βρεθούν οι σχετικές υπογραφές των λογικών τμημάτων. Στη συνέχεια, ακολουθούνται οι δείκτες που οδηγούν στα λογικά τμήματα των εγγράφων. Στην τελική φάση της αναζήτησης, ο όρος αναζητείται μέσα σε κάθε υποψήφιο λογικό τμήμα χρησιμοποιώντας μεθόδους αναζήτησης συμβολοσειράς. Οι εισαγωγές και οι διαγραφές υποστηρίζονται εύκολα. Για την εισαγωγή ενός νέου εγγράφου αρχικά το έγγραφο διαχωρίζεται σε λογικά τμήματα, στη συνέχεια εξάγονται οι υπογραφές των τμημάτων και τέλος ενημερώνεται το αρχείο υπογραφών, το αρχείο εγγράφων και η λίστα των δεικτών. Για τη διαγραφή, εντοπίζονται όλα τα λογικά τμήματα του εγγράφου τα οποία διαγράφονται από το αρχείο εγγράφων και στη συνέχεια διαγράφονται οι αντίστοιχες υπογραφές από το αρχείο υπογραφών. Η λειτουργία της ενημέρωσης ενός μέρους του εγγράφου είναι πιο πολύπλοκη, καθώς θα πρέπει ενδεχομένως να επαναπροσδιοριστούν οι υπογραφές των λογικών τμημάτων που έπονται του τμήματος που έχει μεταβληθεί.

Με βάση τον τρόπο λειτουργίας του καταλόγου SSF προκύπτει ότι για την αναζήτηση ενός και μόνο όρου θα πρέπει να εξεταστούν όλες οι υπογραφές των λογικών τμημάτων. Ένα από τα θέματα που απασχόλησαν του ερευνητές ήταν το πως θα βελτιωθεί ο χρόνος επεξεργασίας. Προς αυτήν την κατεύθυνση έχουν προταθεί εναλλακτικές μορφές οργάνωσης του αρχείου υπογραφών. Η πρώτη από τις μεθόδους που θα εξετάσουμε βασίζεται στον τεμαχισμό (slicing) του πίνακα υπογραφών [15] και καλείται BSSF (bit-sliced signature file). Πρόκειται για μία μέθοδο που στηρίζεται στον κάθετο διαμερισμό του πίνακα υπογραφών. Η αποθήκευση του πίνακα γίνεται κατά στήλες (και όχι κατά γραμμές όπως στη μέθοδο SSF). Ο πίνακας υπογραφών του Σχήματος 7.4 αντιστρέφεται, και αποκτά διαστάσεις $F\times L$ ($F$ γραμμές και $L$ στήλες). Η κάθε γραμμή του αντεστραμμένου πίνακα καλείται τεμάχιο (slice) και αποτελείται από τα δυαδικά ψηφία που βρίσκονται στην ίδια θέση σε όλες τις υπογραφές των λογικών τμημάτων. Για να μπορεί η δομή να υποστηρίξει εισαγωγές και διαγραφές αποδοτικά, η κάθε γραμμή του αντεστραμμένου πίνακα αποθηκεύεται σε ξεχωριστό αρχείο. Η δομή BSSF απεικονίζεται στο Σχήμα 7.5.

Η αναζήτηση ενός όρου στη δομή BSSF ξεκινά με τον υπολογισμό της υπογραφής του όρου. Υπενθυμίζεται, ότι η υπογραφή του όρου θα περιέχει άσσους σε ακριβώς $m$ δυαδικά ψηφία. Επομένως, σε αντίθεση με τη δομή SSF, απαιτείται η εξέταση $m$ τεμαχίων (γραμμών του αντεστραμμένου πίνακα). Τα δυαδικά ψηφία των $m$ γραμμών συνδυάζονται με τη χρήση υπέρθεσης (λογικό AND) και προκύπτει ένα διάνυσμα $L$ θέσεων. Στη συνέχεια, λαμβάνονται υπόψη οι θέσεις των άσσων στο διάνυσμα αυτό και προσπελαύονται οι αντίστοιχοι δείκτες του αρχείου δεικτών για να οδηγηθούμε τελικά στα λογικά τμήματα των εγγράφων. Για την εισαγωγή ενός νέου εγγράφου, αρχικά προσδιορίζονται τα νέα λογικά τμήματα και οι αντίστοιχες υπογραφές. Στη συνέχεια, για κάθε νέο λογικό τμήμα πραγματοποιείται τεμαχισμός της υπογραφής του και κάθε ένα από τα $F$ διαφορετικά αρχεία λαμβάνει και ένα δυαδικό ψηφίο της υπογραφής που αποθηκεύεται στο τέλος.

Η μέθοδος BSSF είναι πιο αποδοτική από την SSF ως προς τη λειτουργία της αναζήτησης. Ωστόσο, υπάρχει επιπλέον χώρος για βελτίωση που οφείλεται σε δύο κυρίως λόγους:

1. (i)

   Η αναζήτηση ενός όρου επιβάλλει την προσπέλαση $m$ τεμαχίων, όπου $m$ είναι ο αριθμός των άσσων στην υπογραφή του όρου. Αν $m$=1 τότε θα μπορούσε να αυξηθεί η απόδοση της μεθόδου.

2. (ii)

   Η εισαγωγή ενός νέου λογικού τμήματος απαιτεί ένα μεγάλο αριθμό προσπελάσεων που ρυθμίζεται από τον αριθμό των δυαδικών ψηφίων της υπογραφής του λογικού τμήματος $F$. Αν η τιμή της παραμέτρου $F$ είναι μεγάλη (π.χ. 1000) τότε αυξάνεται σημαντικά το κόστος εισαγωγής.

Εάν θέσουμε $m$ = 1, τότε θα πρέπει να αυξηθεί σημαντικά το μήκος της υπογραφής ώστε η πιθανότητα ψευδών συναγερμών ($FAP$) να μην αυξηθεί. Αυτό έχει ως αποτέλεσμα, ο πίνακας διαστάσεων $F\times L$ που θα προκύψει να χαρακτηρίζεται ως αραιός, διότι το ποσοστό των άσσων σε σχέση με αυτό των μηδενικών είναι μικρό. Άρα, μπορούν να εφαρμοστούν μέθοδοι συμπίεσης με στόχο τη μείωση του μεγέθους του κάθε τεμαχίου. Η πιο απλή μέθοδος που μπορεί να εφαρμοστεί είναι να αποθηκεύονται οι θέσεις των άσσων σε κάθε τεμάχιο. Με τον τρόπο αυτό, το μέγεθος του κάθε τεμαχίου δεν είναι σταθερό, οπότε το κάθε αρχείο αποθηκεύεται σε έναν ή περισσότερους κάδους (buckets) οι οποίοι συνδέονται με τη μορφή συνδεδεμένης λίστας. Το μέγεθος του κάθε κάδου ($K$) αποτελεί σχεδιαστική παράμετρο. Η μέθοδος αυτή προτάθηκε στην εργασία [15] και καλείται CBS (compressed bit slices). Εκτός από το ότι κάθε όρος ενεργοποιεί μόνο ένα δυαδικό ψηφίο, η δομή CBS δε χρειάζεται το αρχείο δεικτών. Αντί να αποθηκεύεται η θέση του κάθε άσσου, αποθηκεύεται απευθείας ο δείκτης στο αρχείο εγγράφων.

Η δομή CBS απεικονίζεται στο Σχήμα 7.6. Παρατηρήστε την ομοιότητα της δομής με τον αντεστραμμένο κατάλογο. Ωστόσο, σε αντίθεση με τον αντεστραμμένο κατάλογο όπου οι όροι αποθηκεύονται στο λεξικό, οι όροι δεν αποθηκεύονται πουθενά (ούτε στον πίνακα κατακερματισμού, ούτε στους κάδους). Για την αναζήτηση ενός όρου, αρχικά εφαρμόζεται η συνάρτηση κατακερματισμού και διαβάζονται οι αντίστοιχοι κάδοι. Στη συνέχεια, προσπελαύνονται τα στοιχεία του κάθε κάδου και τέλος τα αντίστοιχα τμήματα των εγγράφων. Για να μειωθεί ο αριθμός των ψευδών συναγερμών, ο πίνακας κατακερματισμού πρέπει να είναι αραιός, έτσι ώστε να μειωθεί στο ελάχιστο το πλήθος των συγκρούσεων. Σε περίπτωση που δύο ή περισσότεροι όροι κατακερματίζονται στην ίδια θέση του πίνακα, τότε κατά την αναζήτηση ενός εκ των όρων θα έχουμε ψευδείς συναγερμούς.

Μία δεύτερη προσπάθεια να συμπιεστεί ακόμη περισσότερο ο κατάλογος οδήγησε στην ανάπτυξη της δομής DCBS (doubly compressed bit slices) [15]. Η δομή αυτή μοιάζει πολύ με τη δομή CBS καθώς χρησιμοποιεί πάλι έναν πίνακα κατακερματισμού για την οργάνωση των όρων. Ο κάθε όρος κατακερματίζεται σε μία θέση του πίνακα, χρησιμοποιώντας μία συνάρτηση κατακερματισμού $h_1(t)$ που δίνει τιμές από 0 έως και $F$-1. Για τη διαχείριση των συγκρούσεων, χρησιμοποιείται μία δεύτερη συνάρτηση κατακερματισμού $h_2(t)$ που επιστρέφει ένα διάνυσμα από $h$ δυαδικά ψηφία. Η δομή DCBS χρησιμοποιεί δύο επίπεδα κάδων. Στο πρώτο επίπεδο κάδων αποθηκεύονται τα διανύσματα των $h$ δυαδικών ψηφίων με τη μορφή $⟨$h-bit-vector, bucket-ptr$\mathrm{⟩}$, όπου bucket-ptr είναι ο δείκτης στο επόμενο επίπεδο κάδων όπου αποθηκεύονται οι δείκτες προς το αρχείο εγγράφων.

Η δομή DCBS δίνεται στο Σχήμα 7.7. Η διασικασία της αναζήτησης ενός όρου $t$ αρχίζει με την εφαρμογή της πρώτης συνάρτησης κατακερματισμού $h_1(t)$ που θα οδηγήσει σε μία θέση του πίνακα κατακερματισμού. Στη συνέχεια, εφαρμόζεται η δεύτερη συνάρτηση κατακερματισμού $h_2(t)$ που παράγει ένα διάνυσμα από $h$ δυαδικά ψηφία. Εξετάζονται οι κάδοι του πρώτου επιπέδου ώστε να εντοπιστεί κάποια εγγραφή που να ισούται με $h_2(t)$. Αν ναι, τότε διαβάζονται οι κάδοι του δευτέρου επιπέδου και τέλος ακολουθώντας τους δείκτες προσπελαύνονται τα τμήματα από το αρχείο εγγράφων. Με μία προσεκτική εξέταση του τρόπου λειτουργίας της δομής DCBS εύκολα διαπιστώνεται ότι οι κάδοι του δευτέρου επιπέδου θα είναι ακριβώς οι ίδιοι με αυτούς της δομής CBS αν είχαμε χρησιμοποιήσει $F\cdot 2^h$ θέσεις στον πίνακα κατακερματισμού.

Όλες οι προηγούμενες μέθοδοι οργάνωσης χαρακτηρίζονται από την παρουσία ψευδών συναγερμών. Η μέθοδος που εξετάζεται στη συνέχεια δεν έχει αυτό το πρόβλημα και για το λόγο αυτό καλείται NFD (no false drops) [15]. Η βασική ιδέα είναι η προσθήκη επιπλέον πληροφορίας στο ενδιάμεσο επίπεδο των κάδων. Μία εγγραφή σε έναν ενδιάμεσο κάδο έχει τη μορφή $⟨$h-bit-vector, bucket-ptr, term-ptr$\mathrm{⟩}$ όπου term-ptr είναι ο δείκτης στο αρχείο εγγράφων όπου βρίσκεται ο όρος. Με τον τρόπο αυτό, αποφεύγονται εντελώς οι ψευδείς συναγερμοί, καθώς έχουμε άμεση πρόσβαση στον όρο πριν την εξέταση των κάδων του δευτέρου επιπέδου.

Η δομή FSSF (frame-sliced signature files) [39] προτάθηκε με βασικό στόχο τη μείωση του χρόνου επεξεργασίας, και στηρίζεται στον τεμαχισμό σε πλαισία. Η βασική ιδέα είναι ο κάθε όρος να κατακερματίζεται σε γειτονικά δυαδικά ψηφία της υπογραφής του εγγράφου, τα οποία αποθηκεύονται μαζί, με αποτέλεσμα να ανακτώνται με λιγότερες τυχαίες προσπελάσεις στο δίσκο. Μείωση του αριθμού των τυχαίων προσπελάσεων οδηγεί σε μείωση του χρόνου επεξεργασίας των ερωτημάτων.

Ας εξετάσουμε τη δομή FSSF με μεγαλύτερη λεπτομέρεια. Η υπογραφή του εγγράφου, που αποτελείται από $F$ δυαδικά ψηφία, χωρίζεται σε $r$ πλαίσια (frames). Το κάθε πλαίσιο αποτελείται από $\lfloor F/r\rfloor$ συνεχόμενα δυαδικά ψηφία (εκτός ίσως από το τελευταίο πλαίσιο που μπορεί να έχει λιγότερα). Για την εισαγωγή ενός όρου στην υπογραφή, αρχικά χρησιμοποιείται μία συνάρτηση κατακερματισμού ώστε να επιλεγεί ένα από τα $r$ πλαίσια. Στη συνέχεια, χρησιμοποιείται μία δεύτερη συνάρτηση κατακερματισμού η οποία ενεργοποιεί $m$ δυαδικά ψηφία μέσα στο επιλεγμένο πλαίσιο.

Ο πίνακας των υπογραφών αποθηκεύεται κατά πλαίσια, ενώ κάθε πλαίσιο καταλαμβάνει συνεχόμενες σελίδες δίσκου. Για την απάντηση ενός ερωτήματος που αποτελείται από έναν μόνο όρο, απαιτείται η εξέταση ενός μόνο πλαισίου, επομένως πραγματοποιείται μία μόνο τυχαία προσπέλαση. Για την απάντηση ενός ερωτήματος που αποτελείται από $k$ όρους, απαιτείται η εξέταση το πολύ $k$ πλαισίων.

Η δομή FSSF μπορεί να γενικευθεί, επιλέγοντας περισσότερα από ένα πλαίσια για τον κατακερματισμό ενός όρου, και ενεργοποιώντας $m$ δυαδικά ψηφία σε κάθε πλαίσιο. Η νέα δομή που προκύπτει καλείται GFSSF (generalized frame-sliced signature file) και προτάθηκε επίσης στην εργασία [39].

Οι μέθοδοι οργάνωσης υπογραφών που βασίζονται στον οριζόντιο διαμερισμό προσπαθούν να αποφύγουν τη σειριακή προσπέλαση των υπογραφών του καταλόγου χρησιμοποιώντας ομαδοποίηση των υπογραφών. Η ομαδοποίηση αυτή προκαλεί τον οριζόντιο διαμερισμό του πίνακα υπογραφών. Το κριτήριο βάσει του οποίου πραγματοποιείται η ομαδοποίηση του πίνακα υπογραφών είτε προσδιορίζεται εξ’ αρχής (για παράδειγμα χρησιμοποιώντας κάποια συνάρτηση κατακερματισμού), είτε προσδιορίζεται κατά τη διάρκεια της εισαγωγής των υπογραφών στον κατάλογο (όπως συμβαίνει στην περίπτωση των καταλόγων τύπου B-δένδρου για την οργάνωση ενός συνόλου ακεραίων). Στην πρώτη περίπτωση ο διαμερισμός είναι ανεξάρτητος δεδομένων, ενώ στη δεύτερη περίπτωση είναι εξαρτώμενος από τα δεδομένα.

Η πρώτη μέθοδος οριζόντιου διαμερισμού που είναι ανεξάρτητη δεδομένων προτάθηκε από τον Gustafson [67]. Το κάθε έγγραφο μπορεί να θεωρηθεί ως εγγραφή (record) $r$ όπου οι όροι που περιέχονται στο έγγραφο αποτελούν τις ιδιότητες (attributes) της εγγραφής. Η μέθοδος στηρίζεται στη χρήση συναρτήσεων κατακερματισμού. Έστω $t$ ένας όρος και $h(t)$ μία τιμή μεταξύ των αριθμών 0 και 15 που προκύπτει με εφαρμογή της συνάρτησης κατακερματισμού $h$. Η υπογραφή του όρου $t$ ($TS(t)$) αποτελείται από 16 δυαδικά ψηφία που όλα είναι μηδενικά εκτός από τη θέση $h(t)$ που περιέχει άσσο. Η υπογραφή της εγγραφής $r$ ($RS(r)$) προκύπτει με υπέρθεση των υπογραφών των όρων. Έστω $k$ ο αριθμός των άσσων στην υπογραφή της εγγραφής. Εάν $k$¡6 τότε τα υπόλοιπα 6-$k$ δυαδικά ψηφία ενεργοποιούνται με τυχαίο τρόπο. Το πλήθος των διαφορετικών υπογραφών που μπορούν να προκύψουν ισούται με $\left(\genfrac{}{}{0ex}{}{16}{6}\right)$ = 8008 (επιλογή 6 αντικειμένων από 16). Χρησιμοποιείται ένας πίνακας κατακερματισμού 8008 θέσεων και κάθε εγγραφή κατακερματίζεται σε μία από τις θέσεις του πίνακα αυτού, σύμφωνα με την ακόλουθη μέθοδο. Εάν $p_a$ $p_b$ $p_c$ $p_d$ $p_e$ $p_f$ οι θέσεις των άσσων στην υπογραφή της εγγραφής, τότε η εγγραφή $r$ κατακερματίζεται στη θέση $H(r)$ όπου:

Το βασικό πλεονέκτημα της μεθόδου Gustafson είναι ότι ο αριθμός των υπογραφών που πρέπει να ελεχθούν μειώνεται εκθετικά ως προς τον αριθμό των όρων του ερωτήματος (σε ένα ερώτημα σύζευξης). Ωστόσο, τα μειονεκτήματα της μεθόδου είναι αρκετά σημαντικά με αποτέλεσμα η χρήση της μεθόδου να είναι περιορισμένη: (i) η επιδόσεις της μεθόδου μειώνονται με την αύξηση του μεγέθους του αρχείου, (ii) αν ο αριθμός των όρων ανά έγγραφο είναι μεγάλος τότε το μέγεθος του πίνακα κατακερματισμού θα είναι μεγάλο ή ερωτήματα που περιέχουν τρεις ή τέσσερις όρους θα εξετάσουν ένα μεγάλο τμήμα της συλλογής εγγράφων και (iii) η επεξεργασία γενικών ερωτημάτων (όχι σύζευξης) είναι πολύπλοκη.

Μία δεύτερη μέθοδος που βασίζεται στον οριζόντιο διαμερισμό προτάθηκε από τους Lee και Leng [37]. Η προτεινόμενη μέθοδος οργάνωσης καλείται διαμοιραζόμενο αρχείο υπογραφών (partitioned SF) και χρησιμοποιεί τα πρώτα $k$ δυαδικά ψηφία των υπογραφών για να διαχωρίσει τις υπογραφές. Με τον τρόπο αυτό το αρχείο υπογραφών χωρίζεται σε τμήματα. Όλες οι υπογραφές που ανήκουν στο ίδιο τμήμα έχουν τα πρώτα $k$ δυαδικά ψηφία κοινά. Για την επεξεργασία ενός ερωτήματος πρώτα επιλέγονται τα τμήματα με βάση τα πρώτα $k$ ψηφία της υπογραφής του ερωτήματος και στη συνέχεια πραγματοποιείται έλεγχος των υπογραφών που ανήκουν στα τμήματα.

Μία από τις μεθόδους οργάνωσης που εξαρτάται από τα δεδομένα προτάθηκέ από τους Sack-Davis και Ramamohanarao [54]. Σύμφωνα με τη μέθοδο αυτή, σχηματίζονται δύο επίπεδα υπογραφών, εκ των οποίων το πρώτο αναφέρεται σε υπογραφές εγγράφων και το δεύτερο σε υπογραφές τμημάτων. Για την οργάνωση του πρώτου επιπέδου χρησιμοποιείται η τεχνική SSF ενώ για την οργάνωση του δεύτερου επιπέδου χρησιμοποιείται η τεχνική BSSF. Πειραματικές μετρήσεις έχουν δείξει ότι επιτυγχάνεται σημαντική μείωση του χρόνου επεξεργασίας σε σχέση με άλλες μορφές οργάνωσης (π.χ., SSF ή BSSF).

Τέλος, αναφέρουμε την ιεραρχική μέθοδο οργάνωσης υπογραφών, η οποία προτάθηκε από τον Deppisch [13] και πρόκειται για μία δενδρική δομή δεδομένων δευτερεύουσας μνήμης που έχει πολλά κοινά στοιχεία με τις δενδρικές μεθόδους τύπου B-δένδρου. Η μέθοδος καλείται S-δένδρο (δένδρο υπογραφών) και οι υπογραφές οργανώνονται ιεραρχικά. Υπογραφές που έχουν μεγάλη ομοιότητα (αυτό καθορίζεται για παράδειγμα με βάση την απόσταση Hamming) αποθηκεύονται στο ίδιο φύλλο του S-δένδρου. Στη συνέχεια, οι υπογραφές των ανώτερων επιπέδων δημιουργούνται με χρήση υπέρθεσης. Η μέθοδος δεν έχει μεγάλες απαιτήσεις χώρου, ωστόσο είναι δύσκολο να εκτιμηθεί ο χρόνος εκτέλεσης των ερωτημάτων. Ένα πιθανό πρόβλημα που μπορεί να εμφανιστεί είναι οι υπογραφές των ανώτερων επιπέδων (κοντά στη ρίζα του δένδρου) να περιέχουν πολλούς άσσους. Σε μία τέτοια περίπτωση ο αριθμός των μονοπατιών που πρέπει να εξεταστούν για να απαντηθεί ένα ερώτημα αυξάνει σημαντικά.