Αποκοπή Καταλήξεων (Stemming, Suffix Stripping)


Ένας αλγόριθμος αποκοπής καταλήξεων αποκόπτει τις κλητικές και παραγωγικές καταλήξεις της λέξης. Για παράδειγμα οι λέξεις: thinking, thinker, thinks αντικαθιστούνται από την think. Η ομαδοποίηση λέξεων σε μια κοινή ρίζα αυξάνει την απόκριση ενός συστήματος ανάκτησης. Οι ρίζες των λέξεων στην ανάκτηση πληροφοριών δεν αποτελούν γλωσσολογικό στοιχείο, αλλά ο σκοπός είναι να φέρουμε όσο πιο πολλές λέξεις μπορούμε με το ίδιο περιεχόμενο κάτω από την ίδια ρίζα. Απ' εναντίας οι γλωσσολόγοι ενδιαφέρονται περισσότερο για την εύρεση της ορθής ρίζας. Ένας απλός αλγόριθμος για κείμενα στην αγγλική θα ήταν για παράδειγμα, ν' αφαιρέσουμε τις καταλήξεις -s, -ed, -ing. Γενικά οι αλγόριθμοι αποκοπής καταλήξεων κατατάσσονται σε δύο κατηγορίες: 1) Λίστες καταλήξεων (αφαιρούμε την μεγαλύτερη κατάληξη) και 2) Επαναληπτική αφαίρεση καταλήξεων Η κατάληξη περιέχει πληροφορίες για την γραμματική λειτουργία της λέξης και μπορεί να βοηθήσει στη συντακτική ανάλυση της γλώσσας. Για να έχουμε καλύτερες ρίζες θα πρέπει να συμπεριλάβουμε διάφορους περιορισμούς σε ένα αλγόριθμο αποκοπής καταλήξεων. Για παράδειγμα:
  1. Ποσοτικοί περιορισμοί π.χ. μήκος_ρίζας ≥3
  2. Ποιοτικοί περιορισμοί π.χ. όταν αφαιρούμε την κατάληξη -ize η κατάληξη δεν πρέπει να τελειώνει σε e. Όταν αφαιρούμε -ing αν τα δύο τελευταία γράμματα της ρίζας είναι b, d, g, m, n, p, r, s, t τότε αφαίρεσε το ένα π.χ. admitance  admitt  admit. Αν το τελευταίο γράμμα της ρίζας είναι d, r, t, z, μετάτρεψέ το σε s π.χ.
    admitance --> admitt --> admit --> admis
    admission --> admiss --> admis
Η χρήση ενός αλγόριθμου αποκοπής καταλήξεων ελαττώνει δραματικά το μέγεθος των ανεστραμμένων αρχείων. Η αξιολόγηση των αλγόριθμων αποκοπής καταλήξεων γίνεται υπολογίζοντας το ποσοστό των ορθών ριζών σε μια συλλογή λέξεων. Από το πλήθος των εσφαλμένων ριζών μπορούμε να υπολογίσουμε το ποσοστό των λέξεων στις οποίες αφαιρέθηκε μεγαλύτερο τμήμα της λέξης από όσο θα έπρεπε (overstemming), ή μικρότερο (understemming) και τυχόν άλλα λάθη. Επίσης ένα αλγόριθμο αποκοπής καταλήξεων μπορούμε να τον αξιολογήσουμε έμμεσα από την επίδοση ενός συστήματος ανάκτησης με και χωρίς αποκοπή καταλήξεων. Στην αγγλική ο πλέον διαδεδομένος αλγόριθμος αποκοπής καταλήξεων που χρησιμοποιείται από όλα σχεδόν τα συστήματα είναι ο αλγόριθμος του Porter . Στα ελληνικά τα πράγματα είναι πιο πολύπλοκα, λόγω του μεγάλου αριθμού ανωμαλιών τόσο στη μορφολογία όσο και την ορθογραφία. Στα ελληνικά έχουμε δέκα μέρη του λόγου: άρθρο, ουσιαστικό, επίθετο, αντωνυμία, ρήμα, επίρρημα, μετοχή, πρόθεση, συνδετικά και επιφώνημα. Τα άρθρο, ουσιαστικό, αντωνυμία και επίθετο κλίνονται ανάλογα με το γένος (αρσενικό, θηλυκό ουδέτερο) και τον αριθμό (ενικό και πληθυντικό). Για τα ρήματα έχουμε χρόνο και πρόσωπο. Τα άρθρο, ουσιαστικό, επίθετο, αντωνυμία και η μετοχή έχουν πτώσεις, ονομαστική, γενική, αιτιατική και κλητική. Η δοτική δεν υπάρχει πλέον στη δημοτική παρά μόνο σε στερεότυπες φράσεις. Επίσης έχουμε προβλήματα ταξινόμησης που προκύπτουν από τους διάφορους τύπους γραμμάτων, τονούμενα, και άλλα σημεία στίξεως τα οποία επηρεάζουν το νόημα μιας λέξης και την ορθογραφία της. Για παράδειγμα ο τόνος, που χρησιμοποιείται στη προφορά της λέξης, μπαίνει μόνο σε φωνήεντα πεζά γράμματα. Τα κεφαλαία δεν τονίζονται εκτός και αν είναι στην αρχή της λέξης. Μια λέξη με κεφαλαία γράμματα μπορεί να την προφέρει κανείς με διαφορετικούς τρόπους, αφού δεν έχει τόνο π.χ. ΚΑ΄ΛΟΣ και ΚΑΛΟ΄Σ. Βέβαια τέτοιες λέξεις είναι πολύ λίγες και δεν μπορούν να επηρεάσουν σοβαρά την επίδοση της ανάκτησης. Τα ουσιαστικά στη δημοτική κλίνονται ανάλογα με την κατηγορία τους. Συνολικά υπάρχουν 41 κλητικές καταλήξεις (14 για τα αρσενικά, 14 για τα θηλυκά και 13 για τα ουδέτερα). Στη γενική μπορεί να έχουμε περισσότερες από μια καταλήξεις, μια από την δημοτική και μια λόγια που έχει παραμείνει από την καθαρεύουσα. Συνεπώς αν για την αποκοπή της κατάληξης χρησιμοποιήσουμε ένα πίνακα με όλες τις κλητικές και παραγωγικές καταλήξεις τότε θα έχουμε ένα μεγάλο πλήθος καταλήξεων κάτι που επιβαρύνει πολύ το κόστος του αλγόριθμου. Επιπλέον στη περίπτωση του πίνακα είναι δύσκολο να διακρίνουμε μεταξύ καταλήξεων που επικαλύπτονται, για παράδειγμα οι λέξεις ΓΟΝΕΙΣ και ΓΟΝΑΤΟ μπορεί να θεωρηθεί ότι έχουν την ίδια ρίζα (ΓΟΝ-) αντί του ορθού ΓΟΝ- και ΓΟΝΑΤ-. Επιπλέον τα προθέματα στην ελληνική μπορεί να αλλάξουν το νόημα μιας λέξης. Τέλος υπάρχει η περίπτωση των ανωμάλων ρημάτων π.χ. ΒΛΕΠΩ, ΕΙΔΑ η οποία για να αντιμετωπιστεί χρειάζεται αρνητικό λεξικό. Ένας αλγόριθμος για την ελληνική μπορεί να αφαιρεί πρώτα τις κλητικές καταλήξεις π.χ. έτσι οι λέξεις ΧΑΡΑΚΤΗΡΑΣ ΧΑΡΑΚΤΗΡΙΣΑ ΧΑΡΑΚΤΗΡΙΖΩ ΧΑΡΑΚΤΗΡΙΖΟΝΤΑΣ ΧΑΡΑΚΤΗΡΙΣΑΜΕ κ.ά ανάγονται στην ρίζα ΧΑΡΑΚΤΗΡ-. Στη συνέχεια κατ’ ανάλογο τρόπο αντιμετωπίζονται και η παραγωγικές καταλήξεις και τέλος ελέγχονται διάφοροι ποσοτικοί περιορισμοί στη ρίζα που προκύπτει. Συνήθως οι παραγωγικές καταλήξεις προηγούνται των κλητικών και υπάρχουν περιπτώσεις όπου έχουμε δύο παραγωγικές καταλήξεις πριν την κλητική. Για την αναγωγή τέτοιων λέξεων στη σωστή ρίζα οι παραγωγικές καταλήξεις μπορεί να ελέγχονται δύο φορές. Στον πίνακα 2-2 δίδονται οι καταλήξεις των ουσιαστικά. Με *(κατάληξη) συμβολίζουμε ότι ο αντίστοιχος κανόνας εφαρμόζεται μόνο όταν προηγείται σύμφωνο.

stemming1
Πίνακας 2. Καταλήξεις ουσιαστικών

Παραδείγματα με ουσιαστικά δίδονται στον πίνακα 2-3.

stemming2
Πίνακας 3. Παραδείγματα καταλήξεων ουσιαστικών

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

Απλοί και Σύνθετοι Όροι

Η εξαγωγή απλών όρων από ένα κείμενο δεν έχει πάντα θετικό αποτέλεσμα διότι ορισμένοι όροι μπορεί να έχουν περισσότερες από μία ερμηνείες ανάλογα του περιεχομένου του κειμένου στο οποίο ευρίσκονται. Απλοί όροι μπορεί να είναι πολύ γενικοί ή ειδικοί. Συνήθως ένας ειδικός (expert) επιλέγει επιθετικές φράσεις (επίθετο-ουσιαστικό) ως περιγραφητές (λέξεις κλειδιά) για το ευρετήριο. Στη διαδικασία αυτή μπορεί να χρησιμοποιηθούν διάφορα βοηθητικά εργαλεία, όπως για παράδειγμα θησαυρός ή κάποιο σημασιολογικό δίκτυο (οντολογία) το οποίο περιέχει σχέσεις ιεραρχίας μεταξύ των όρων σε γενικότερους ή ειδικότερους όρους, όπως είναι το Wordnet . Όπως είδαμε στη προηγούμενη ενότητα η εξαγωγή σύνθετων όρων-περιγραφητών από ένα κείμενο είναι πολύ δύσκολο πρόβλημα. Συνήθως χρησιμοποιούνται τεχνικές υπολογιστικής γλωσσολογίας για την εξαγωγή όρων που συνδέονται γλωσσολογικά αλλά και στατιστικές μέθοδοι που βασίζονται σε παρατηρήσεις όπως είναι η συχνότητα συνεμφάνισης δύο λέξεων στα κείμενα. Μια αυτόματη μέθοδος εξαγωγής σύνθετων όρων μπορεί να γίνει για μια συγκεκριμένη συλλογή. Αν οι ίδιοι όροι υπάρχουν σε πολλά κείμενα τότε μπορούμε να πούμε ότι μπορεί να υπάρχει κάποια συσχέτιση μεταξύ τους. Ωστόσο ακόμη και αν υπάρχει τέτοια συσχέτιση αυτή εξαρτάται από την συλλογή. Απλά στατιστικά κριτήρια δεν βοηθούν στη δημιουργία περιγραφητών υψηλής ποιότητας για να συμπεριληφθούν στο ευρετήριο. Αυτό σημαίνει την ανάγκη ύπαρξης μη ποσοτικών κριτηρίων για την εξαγωγή των καλύτερων φράσεων. Διάφορες γλωσσολογικές μεθοδολογίες έχουν προταθεί για την εξαγωγή φράσεων που περιέχουν (επίθετο+ουσιαστικό). Επομένως χρειάζεται λεξικό για την εκχώρηση της συντακτικής κατηγορίας σ’ ένα όρο. Ωστόσο και αυτές οι μέθοδοι δεν εξασφαλίζουν σημασιολογική σχέση μεταξύ των όρων όπως φαίνεται στο επόμενο παράδειγμα. Τεράστιες ποσότητες πληροφοριών έντυπων και ψηφιακών Επίθετο ουσιαστικό ουσιαστικό ουσιαστικό ουσιαστικό Εδώ είναι δύσκολο να καθορίσει κανείς συσχετίσεις μεταξύ των όρων. Χρησιμοποιώντας το κριτήριο της γειτνίασης των όρων για το παράδειγμα έχουμε τις φράσεις όπως: τεράστιες ποσότητες έντυπων ψηφιακών εκ των οποίων η δεύτερη δεν είναι ορθή γιατί το «έντυπων» αναφέρεται στο «πληροφοριών» και όχι στο γειτονικό του ουσιαστικό «ψηφιακών». Η δημιουργία φράσεων σημαίνει "στένεμα" των όρων και βελτιώνει την ακρίβεια της ανάκτησης. Η χρήση θησαυρού σημαίνει ακριβώς το αντίθετο. Έτσι για παράδειγμα, οι φράσεις computer architecture, computer program είναι πολύ πιο συγκεκριμένες από μόνο την λέξη computer. Στατιστικά θα μπορούσαμε να πούμε ότι μια φράση συνδέει μια λέξη με υψηλή συχνότητα (όπως η λέξη computer) σε μια άλλη πιο δεξιά στον άξονα των συχνοτήτων (architecture). Με άλλα λόγια για την δημιουργία μιας φράσης η βασική λέξη (phrase head) θα πρέπει να έχει υψηλή συχνότητα στα κείμενα μιας συλλογής. Το δεύτερο στοιχείο της φράσης θα πρέπει να είναι μέσης ή χαμηλής συχνότητας. Ένας άλλος περιορισμός για τα στοιχεία της φράσης είναι ότι θα πρέπει να βρίσκονται στην ίδια πρόταση και σε σχετικά μικρή απόσταση μεταξύ τους. Οι τετριμμένες λέξεις (stop words) δηλαδή οι λέξεις με πολύ υψηλή συχνότητα εμφάνισης δεν χρησιμοποιούνται για την δημιουργία φράσεων. Έστω ότι έχουμε την πρόταση: “Οι καθημερινές δραστηριότητες των επιχειρήσεων παράγουν τεράστιες ποσότητες πληροφοριών, έντυπων και ψηφιακών.” και ας θεωρήσουμε ότι οι λέξεις “καθημερινές”, “ποσότητες”, και “πληροφοριών” έχουν υψηλή συχνότητα. Μετά την αφαίρεση των τετριμμένων λέξεων απομένουν οι όροι: { καθημερινές, δραστηριότητες, επιχειρήσεων, παράγουν, τεράστιες, ποσότητες, πληροφοριών, έντυπων, ψηφιακών }. Όταν θέλουμε οι λέξεις της φράσης να είναι γειτονικές (δηλαδή η απόστασή τους να είναι 1) τότε έχουμε 8 υποψήφιες φράσεις εκ των οποίων οι ορθές εμφανίζονται στη πρώτη στήλη του πίνακα 2-4. Όταν επεκτείνουμε την απόσταση μεταξύ λέξεων στη φράση σε ολόκληρη την πρόταση τότε το πλήθος των υποψήφιων φράσεων αυξάνει δραματικά, γίνεται 36. Στη περίπτωση αυτή οι ορθές φράσεις εμφανίζονται στη δεύτερη στήλη του πίνακα 2-4.

stemming3
Πίνακας 4. Εξαγωγή φράσεων από συλλογές κειμένων

Από το παράδειγμα βλέπουμε ότι στη δεύτερη περίπτωση έχουμε περισσότερες δόκιμες προτάσεις από την συγκεκριμένη πρόταση αλλά έχει αυξηθεί δυσανάλογα και το πλήθος των μη ορθών φράσεων. Γλωσσολογικά κριτήρια ίσως βελτιώσουν τη ποιότητα των φράσεων. Για παράδειγμα θα μπορούσε να λάβουμε υπόψη μόνο τους συντακτικούς τύπους επίθετο και ουσιαστικό οι οποίοι εκχωρούνται στις λέξεις με τη βοήθεια λεξικού και να θεωρήσουμε ως υποψήφιες φράσεις μόνο συνδυασμούς από επίθετο – ουσιαστικό και ουσιαστικό – ουσιαστικό. Θα μπορούσε επίσης, η εξαγωγή των υποψήφιων φράσεων να περιοριστεί σε μικρότερες μονάδες εντός μιας πρότασης. Έτσι μετά από μια ρηχή συντακτική ανάλυση στη πρόταση μπορούμε να απομονώσουμε τις συντακτικές μονάδες της πρότασης, δηλαδή την υποκειμενική φράση (Οι καθημερινές δραστηριότητες των επιχειρήσεων), την αντικειμενική φράση (τεράστιες, ποσότητες, πληροφοριών, έντυπων, ψηφιακών) και την ρηματική φράση (παράγουν) και να περιορίσουμε την εξαγωγή υποψήφιων φράσεων στις μονάδες αυτές. Στη περίπτωση αυτή θα έχουμε ως υποψήφιες τις φράσεις: καθημερινές δραστηριότητες δραστηριότητες επιχειρήσεων τεράστιες ποσότητες πληροφοριών έντυπων πληροφοριών ψηφιακών Το πρόβλημα της εξαγωγής φράσεων μέχρι σήμερα παραμένει ανοιχτό. Ίσως η συντακτική ανάλυση με σημασιολογικά στοιχεία μπορεί να δώσει καλύτερα αποτελέσματα στο μέλλον. Οι φράσεις βελτιώνουν το specificity των απλών όρων ειδικά για αυτούς που έχουν υψηλή συχνότητα εμφάνισης. Tο αντίθετο κάνει ο θησαυρός. Ο θησαυρός ομαδοποιεί συσχετιζόμενους ειδικούς όρους κάτω από πιο γενικούς. Αυτό βελτιώνει την απόκριση (recall) καθόσον τώρα η ομάδα του θησαυρού έχει μεγαλύτερες πιθανότητες ταιριάσματος (matching) από τον αρχικό όρο αφού μπορεί να ληφθούν υπόψη και όροι που δεν υπήρχαν στο ερώτημα του χρήστη. Με την αποκοπή των καταλήξεων επιτυγχάνεται ακόμη μεγαλύτερη βελτίωση της απόκρισης. Προφανώς μπορούμε να χρησιμοποιήσουμε θησαυρό εφόσον υπάρχει πρακτική μέθοδος για να τον κατασκευάσουμε. Αυτόματος τρόπος για την κατασκευή θησαυρού μπορεί να χρησιμοποιηθεί απλώς για βοήθεια, όπως για παράδειγμα είναι η κατασκευή του corcondance των όρων, δηλαδή ένας αλφαβητικός κατάλογος, των όρων της συλλογής με το περιεχόμενό τους (context). Διάφορες προσεγγίσεις για την αυτόματη ή ημιαυτόματη κατασκευή θησαυρού που έχουν προταθεί υπολογίζουν την ομοιότητα (similarity) μεταξύ των όρων με διάφορα στατιστικά μέτρα, όπως για παράδειγμα από τη σχέση:

sim1

όπου με wij συμβολίζεται το βάρος του όρου i σε ένα κείμενο (ενότητα) j. Ένας όρος εντάσσεται σε μια ομάδα του θησαυρού όταν ισχύει για όλους τους όρους ti και tj της κλάσης. Οι κλάσεις που θα κατασκευαστούν από αυτή την διαδικασία προφανώς θα πρέπει να δοκιμαστούν σε διάφορες συλλογές για να έχουν κάποια αξιοπιστία. Η χρήση του θησαυρού σε ένα σύστημα ανάκτησης έχει σκοπό να διευρύνει το ερώτημα του χρήστη με όρους που ανήκουν στην ίδια κλάση βελτιώνοντας έτσι την επίδοση της απόκρισης του συστήματος.

Αναφορές

  1. D. Harman, How effective is suffixing?, Journal of the American Society of Information Science, vol. 42, 1991, 7-15.
  2. M.F. Porter, An algorithm for suffix stripping, Program, vol 14, 1980, 130-137.
  3. T.Z. Kalamboukis, "Suffix stripping with modern Greek", Program: electronic library and information systems, Vol. 29 Iss: 3, pp.313 - 321, 1995
  4. M. Triantafilidi, Modern Greek Grammar, Salonica: Aristotelion University, 1991.
  5. E. Philippaki-Warburton, Introduction to theoretic linguistics, Athens: Nefeli editions, 1992.