Σελίδες

Σάββατο 11 Οκτωβρίου 2014

Εξερευνώντας τα ενδότερα της υπολογιστικής ορθογραφίας

Από μικρός θυμάμαι ότι είχα μια έφεση στην ορθογραφία της Ελληνικής (είχα την "ατυχία" να μην διδαχθώ Τουρκικά στο Δημοτικό αλλά και στο, πεντατάξιο τότε, Ιεροσπουδαστήριο του Εχίνου αργότερα). Δεν είχα φανταστεί ποτέ όμως ότι θα έφτανα στο σημείο να ασχολούμαι με την ορθογραφία της Πομακικής και μάλιστα σε επίπεδο προγραμματισμού.  Είναι, φαίνεται, το “τυχερό” μου.

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


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


Στην εποχή της πληροφορίας, τώρα, και για κάποιον που ασχολείται τόσο ενεργά με μια γλώσσα και σ’ αυτό το επίπεδο δεν θα μπορούσε να μην περάσει από το μυαλό του η ιδέα της εκμετάλλευσης των όποιων γνώσεων του στην πληροφορική και να μην μπει στον "πειρασμό" της δημιουργίας ενός τέτοιου ηλεκτρονικού ορθογραφικού εργαλείου προς όφελος της ίδιας της γλώσσας, του ιδίου και των υπολοίπων ομιλητών και χρηστών της.  Πολύ περισσότερο δε όταν πρόκειται για τη μητρική του γλώσσα, η οποία βρίσκεται στο στάδιο της καταγραφής ακόμα, και δεν υπάρχει άλλη παρόμοια προσπάθεια μέχρι τώρα.


Αρκετά "τολμηρό" το εγχείρημα, βεβαίως, και σίγουρα όχι μια απλή άσκηση προγραμματισμού, για τις επίσημες και αναγνωρισμένες σπουδές μου τουλάχιστον.  Τα προβλήματα και οι δυσκολίες αρκετές.  Οι λύσεις περιορισμένες και η προσαρμογή τους στα Πομακικά αρκετά επίπονη.  Το τελικό αποτέλεσμα;  Άκρως ενθαρρυντικό.  Δικαιώνει, πιστεύω, τους κόπους και τις προσπάθειες σε πολύ υψηλό βαθμό.


Έχοντας ως σύμμαχο τη μηχανή αναζήτησης της Google μαζί με τα "άθλια" Αγγλικά μου (στα Ελληνικά δυστυχώς λίγα πράγματα κυκλοφορούν στο διαδίκτυο πάνω στο θέμα αυτό) και ως πρώτη επιλογή, λοιπόν, ανάμεσα στα "ευρήματα" είπα να δοκιμάσω την πολύ καλή και τεκμηριωμένη λύση – πρόταση ηλεκτρονικού ορθογραφικού ελέγχου του Peter Kankowski στο, επίσης, πολύ ενδιαφέρον και αναλυτικό άρθρο του στο CodeProject, το οποίο συνοδεύεται και από μια εφαρμογή επίδειξης  (για την Αγγλική Γλώσσα στην προκειμένη περίπτωση, αλλά αυτό δεν έχει και μεγάλη σημασία).


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


Πέρα από τις όποιες μικροδιορθώσεις και τροποποιήσεις που ήταν αναγκαίες, κυρίως σε ό,τι αφορά τους τύπους δεδομένων, εκεί που "χωλαίνει" αισθητά, όπως τονίζει και ο αρθρογράφος και προσδοκά σε προτάσεις βελτίωσης, είναι ο αλγόριθμος της κατά προσέγγιση (fuzzy) αναζήτησης για την υπόδειξη ορθογραφικών προτάσεων στον έλεγχο ενός κειμένου.  Ο ίδιος στην  εφαρμογή επίδειξης χρησιμοποιεί απόσταση edit 1 και τα αποτελέσματα που αυτή δίνει για τα Αγγλικά ίσως δεν είναι και τόσο άσχημα.  Για τα Πομακικά όμως, όπως ενδεχομένως και για άλλες γλώσσες, νομίζω ότι χρειάζεται τουλάχιστον μια απόσταση edit 2 για μια πληρέστερη και εγκυρότερη λίστα υποδείξεων.


Στην εφαρμογή επίδειξης που συνοδεύει το άρθρο, για παράδειγμα, και με τις μεθόδους που χρησιμοποιεί ο δημιουργός της στον αλγόριθμό του, αν πληκτρολογήσει κανείς τη λέξη matherland (αντί της σωστής motherland που υπάρχει στο λεξικό), θα διαπιστώσει έκπληκτος ότι για κάποιον "περίεργο" λόγο δεν εμφανίζεται καμιά ορθογραφική πρόταση – υπόδειξη και αυτό, αν μη τί άλλο, είναι λίγο προβληματικό.  Ο λόγος είναι ότι προφανώς δεν χρησιμοποιείται η διαδικασία της αντικατάστασης χαρακτήρων (substitution), το “o”, δηλαδή, στη θέση του “a” στην προκειμένη περίπτωση, ή ότι η χρήση της διαδικασίας αυτής είναι κατά κάποιο τρόπο περιορισμένη. Στην πραγματικότητα αν εξετάσει κανείς τον  κώδικα της διαδικασίας “fuzzy_match” που αρχίζει στη γραμμή 218 του αρχείου “spellchecker.c”, θα δει ότι, όντως, ισχύει η δεύτερη περίπτωση και η εξήγηση είναι η χρήση της συνάρτησης “similar_letters”, η οποία, ελλείψει υποστήριξης της φωνητικής γραφής (sound-like) στην παρούσα υλοποίηση, περιορίζει τη λειτουργία της αντικατάστασης μεταξύ των "ομοίων" φωνητικά και "γειτονικών" στο πληκτρολόγιο χαρακτήρων μόνο.  Η συγκεκριμένη επιλογή σαφώς και έχει κάποια λογική, πλην όμως δεν είναι η διαδικασία της αντικατάστασης όπως αυτή περιγράφεται στον αρχικό ορισμό της.  Στα Πομακικά, φυσικά, σε αντίθεση με την Αγγλική ή την Ελληνική, εκτός από την απουσία των δίψηφων φθόγγων (καταργήθηκαν με την αναθεώρηση του αλφαβήτου), η προφορά όλων των γραμμάτων είναι μοναδική ανεξάρτητα από τη θέση ή τη σειρά τους μέσα στη λέξη και οι όποιες μεταβολές στους φθόγγους αποδίδονται με αντίστοιχους εναλλακτικούς χαρακτήρες (σε κάποιες περιπτώσεις π.χ. τα τελικά άηχα σύμφωνα αντικαθίστανται από τα αντίστοιχα ηχηρά τους όπως στις λέξεις hläp – hlä́bos, plačlı́f – plačlı́va).  Αυτό σημαίνει ότι για τα Πομακικά δεν τίθεται θέμα υποστήριξης φωνητικής γραφής, ενώ η περίπτωση της μεταβολής των φθόγγων καλύπτεται πλήρως από τη διαδικασία της γνωστής απλής αντικατάστασης.
 


Εικόνα 1: Η εφαρμογή επίδειξης του P. Kankowski όπου φαίνεται η αδυναμία του αλγορίθμου να υποδείξει ορθογραφική πρόταση στη θέση της λανθασμένης λέξης “matherland”.


 


Εικόνα 2: Η εφαρμογή επίδειξης του P. Kankowski και η εύρεση της λέξης “motherland” στο λεξικό.

Ύστερα από επίμονη και επίπονη προσπάθεια τροποποίησης και βελτίωσης του εν λόγω αλγορίθμου μετά πολλών δοκιμών κι ελέγχων, το γενικό συμπέρασμα που προκύπτει είναι ότι η εκτεταμένη σάρωση μιας δομής Ternary DAG (με δεκάδες ή εκατοντάδες χιλιάδες κόμβους) στην αναζήτηση μιας λέξης με εφαρμογή του αλγορίθμου Damerau – Levenshtein για τον έλεγχο της επιθυμητής απόστασης edit είναι ασύμφορη από άποψη υπολογιστικού κόστους και επιδόσεων.  Αντ’ αυτού, μια πολύ πιο περιορισμένη και ελεγχόμενη σάρωση με εξίσου καλά αποτελέσματα μπορεί να επιτευχθεί με τη χρήση μιας προκατασκευασμένης λίστας υποψήφιων ορθογραφικών προτάσεων – υποδείξεων προσαρμοσμένων στις επιθυμητές διαδικασίες και αποστάσεις edit.  Μια τέτοια λίστα, φυσικά, με τους συνδυασμούς όλων των γραμμάτων του όποιου αλφαβήτου, πεζών και κεφαλαίων ενδεχομένως, θα ήταν τεράστια σε μέγεθος και η κατασκευή της θα είχε αρκετά μεγάλο υπολογιστικό κόστος, ενώ μια ικανοποιητική λύση στο πρόβλημα φαίνεται ότι αποτελεί η χρήση χαρακτήρων μπαλαντέρ με τον κατάλληλο χειρισμό τους.  Ωστόσο ένα μικρό ζήτημα που φαίνεται ότι υπάρχει ακόμα με μια τέτοια λίστα είναι ότι σε ορισμένες διαδικασίες edit κάποιες υποψήφιες προτάσεις – υποδείξεις επικαλύπτονται, ευτυχώς σε πολύ μικρό ποσοστό – της τάξεως του 5% με μια πρόχειρη εκτίμηση, με αποτέλεσμα την ύπαρξη διπλών τιμών, επομένως και διπλών αποτελεσμάτων, και άρα περιττών αναζητήσεων.  Από την άλλη όμως η μοναδικοποίηση των τιμών της λίστας θα είχε αμφίβολα ή πενιχρά αποτελέσματα και εκτιμάται ότι θα επιβράδυνε μάλλον τον αλγόριθμο παρά θα τον επιτάχυνε.  Σε ό,τι αφορά δε την ταξινόμηση των υποδεικνυόμενων ορθογραφικών προτάσεων με σειρά από τις περισσότερο στις λιγότερο πιθανές ή κοντινές, αυτή μπορεί να υλοποιηθεί με τη  χρήση μιας απλής κλάσης της C++ με τις κατάλληλες οδηγίες και τη χρήση του τελεστή σύγκρισης "<" (μικρότερο).  Στη σύγκριση αυτή εξετάζεται πρώτα η προϋπολογισμένη και αποθηκευμένη απόσταση edit και ακολούθως η αλφαβητική σειρά, ενώ για την επίτευξη ακόμα μεγαλύτερης προσέγγισης θα μπορούσαν να χρησιμοποιηθούν ίσως περισσότερο σύνθετοι υπολογισμοί.

 

Εικόνα 3: Η κλάση CSug όπου φαίνεται η χρήση του τελεστή σύγκρισης "<" (μικρότερο) που χρησιμεύει στην ταξινόμηση.
 


Εικόνα 4: Εφαρμογή επίδειξης κατασκευής λίστας υποψήφιων ορθογραφικών προτάσεων – υποδείξεων (* = εισαγωγή, ? = αντικατάσταση)


Εικόνα 5: Η ρουτίνα της διαδικασίας edit για την αντικατάσταση 1 +  την εισαγωγή 1 χαρακτήρα

Στην παρούσα υλοποίηση, λοιπόν, με απόσταση edit 2 και το ίδιο ακριβώς αγγλικό λεξικό που συνοδεύει την εφαρμογή επίδειξης του Peter Kankowski (περίπου 100.000 λέξεις) ο τροποποιημένος και βελτιωμένος αλγόριθμος υποδεικνύει 5 ορθογραφικές προτάσεις στη θέση της λανθασμένης λέξης “matherland”, όσες δηλαδή θα πρότεινε και ο αλγόριθμος Damerau – Levenshtein σε περιβάλλον δυναμικού προγραμματισμού με ασύγκριτα μεγαλύτερο κόστος.
Το αποτέλεσμα που εμφανίζεται στην εικόνα 6 προκύπτει από τη χρήση των εξής διαδικασιών edit:
 
  • εισαγωγή 1 και 2 χαρακτήρων, 
  • αντικατάσταση 1 και 2 χαρακτήρων, 
  • διαγραφή 1 και 2 χαρακτήρων, 
  • αντικατάσταση 1 χαρακτήρα σε συνδυασμό με την εισαγωγή 1 χαρακτήρα και, τέλος, 
  • αντιμετάθεση 2 χαρακτήρων.
Είναι δυνατή, φυσικά, η χρήση ("κατάχρηση" πιθανόν με αποτέλεσμα να προκύπτει απόσταση edit μεγαλύτερη του 2 ίσως κάποιες φορές) και άλλων διαδικασιών edit, όπως
  • διαγραφή + αντικατάσταση,
  • διαγραφή + εισαγωγή,
  • αντιμετάθεση + αντικατάσταση και
  • αντιμετάθεση + εισαγωγή,
με το ανάλογο κόστος αναζήτησης, το οποίο, σημειωτέον, ανεβαίνει αισθητά μεν, ειδικά για τις μεγάλες λέξεις, κυμαίνεται όμως σε ανεκτά επίπεδα κατά τη γνώμη μου.


Εικόνα 6: Εφαρμογή επίδειξης του τροποποιημένου και βελτιωμένου αλγορίθμου υπόδειξης ορθογραφικών προτάσεων (ο αριθμός στην παρένθεση δείχνει την απόσταση edit).




Εικόνα 7: Η κεντρική διαδικασία του αλγορίθμου ορθογραφικών προτάσεων – υποδείξεων

Κατά τη διάρκεια των δοκιμών κι ελέγχων και για λόγους σύγκρισης κρίθηκε αναγκαία η εξέταση και άλλων μοντέλων υπολογιστικής ορθογραφίας.  Ανάμεσα στις υποψήφιες λύσεις, λοιπόν, με τα πολύ ενδιαφέροντα χαρακτηριστικά της και τους προηγμένους αλγορίθμους που χρησιμοποιεί, δε θα μπορούσε να λείπει η υψηλών επιδόσεων βιβλιοθήκη PATL (Practical Algorithm Template Library), με πεδίο χρήσης στην επεξεργασία φυσικού λόγου και όχι μόνο, η οποία και επελέγη τελικά ως μοντέλο σύγκρισης.  Τα κριτήρια για την επιλογή της ήταν η παραπλήσια δομή δεδομένων PATRICIA που χρησιμοποιεί κατά πρώτο λόγο και κατά δεύτερο τα συμβατά με την STL πρότυπά της.  Στις συγκριτικές δοκιμές που έκανα με χρήση του αλγορίθμου Αυτομάτων Levenshtein των  Schulz και Mihov μου άφησε άριστες εντυπώσεις σε ό,τι αφορά τους χρόνους και όπως φάνηκε μέσα από τη διαδικασία αυτή ορισμένες τουλάχιστον φορές έδειχνε ότι είναι κατά τι γρηγορότερη.  Εκεί που υστερεί σημαντικά όμως έναντι της λύσης του Kankowski είναι στη συμπίεση των δεδομένων με αποτέλεσμα την αυξημένη χρήση πόρων της μνήμης RAM.  Ψευτολεξικό που κατασκέυασα προγραμματιστικά για τις ανάγκες των δοκιμών 800.000 λέξεων, χρησιμοποιώντας ως βάση λίγες πραγματικές λέξεις, μεγέθους 13 Megabytes σε ασυμπίεστη μορφή (έτοιμο πραγματικό λεξικό αυτού του μεγέθους δεν μπόρεσα να βρω), για να τρέξει με τη βιβλιοθήκη PATL απαιτούνται περίπου 70 Megabytes μνήμης RAM, συμπεριλαμβανομένων των πόρων που χρησιμοποιεί η ίδια η εφαρμογή, ενώ με τη λύση που προτείνει ο Kankowski απαιτείται κάτι λιγότερο από το το 1/10 αυτής στη συμπιεσμένη του μορφή που δεν υπερβαίνει το μισό Megabyte στο σκληρό δίσκο.  Η διαφορά αυτή είναι αναμφισβήτητα μια σημαντική παράμετρος που δεν μπορεί να αγνοηθεί.  Σε περιβάλλοντα συστημάτων υψηλών επιδόσεων όμως με εξασφαλισμένη επάρκεια μνήμης RAM και υπολογιστική ισχύ θα μπορούσε να χρησιμοποιηθεί ανεπιφύλακτα και με ιδιαίτερη άνεση, εξαιρουμένης ίσως της συχνής φόρτωσης ενός υπερλεξικού αρκετών εκατομμυρίων λέξεων.




Εικόνα 8: Στιγμιότυπο από τη δοκιμή της βιβλιοθήκης PATL (Practical Algorithm Template Library) με χρήση του αλγορίθμου Αυτομάτων Levenshtein και απόσταση edit 2.

Σε ό,τι αφορά τα δικά μας, τώρα, το καλό νέο είναι ότι ο τροποποιημένος και  βελτιωμένος αλγόριθμος του Kankowski και η συνολική προτεινόμενη λύση δοκιμάστηκαν με επιτυχία και στα Πομακικά, ενώ η όλη συμπεριφορά και λειτουργία της κρίνεται παραπάνω από ικανοποιητική.  Με την ολοκλήρωση τουλάχιστον του ορθογραφικού λεξικού της Πομακικής, με περίπου 500.000 τύπους λέξεων κατ’ εκτίμηση, θα είναι δυνατός πλέον ο ηλεκτρονικός ορθογραφικός έλεγχος απλού πομακικού κειμένου με τη χρήση μιας αυτόνομης εφαρμογής (απλού επεξεργαστή κειμένου), με δυνατότητες υπόδειξης – διόρθωσης λαθών, αναζήτησης – αντικατάστασης κειμένου κλπ., η οποία βρίσκεται στο στάδιο της ανάπτυξης και ο γράφων ευελπιστεί να παρουσιάσει μια πρώτη δοκιμαστική έκδοσή της σε εύθετο χρόνο.


Μέχρι τότε να περνάτε εσείς καλά κι εμείς καλύτερα.


Τις εφαρμογές επίδειξης θα τις βρείτε εδώ (md5 checksum: 8e8fceed00a5fcbecd9314f71abbfe75).  Για τον έλεγχο της ακεραιότητας του αρχείου μπορείτε να χρησιμοποιήσετε τη δωρεάν εφαρμογή που θα βρείτε στη διεύθυνση http://www.winmd5.com/).


Υπενθυμίζεται ότι το σύνολο του πηγαίου κώδικα μπορεί να διατεθεί δωρεάν σε οποιονδήποτε ενδιαφερόμενο με ένα απλό αίτημα στη ηλεκτρονική διεύθυνση ritvank@gmail.com


Κάθε καλόπιστη κριτική, υπόδειξη λάθους ή πρόταση βελτίωσης είναι ευπρόσδεκτη.



Σημείωση σχετικά με το λεξικό που συνοδεύει τις εφαρμογές επίδειξης:

Copyright 2000-2004 by Kevin Atkinson
Permission to use, copy, modify, distribute and sell these word lists, the associated scripts, the output created from the scripts, and its documentation for any purpose is hereby granted without fee, provided that the above copyright notice appears in all copies and that both that copyright notice and this permission notice appear in supporting documentation. Kevin Atkinson makes no representations about the suitability of this array for any purpose. It is provided "as is" without express or implied warranty.


http://wordlist.sourceforge.net/