Ας υποθέσουμε ότι γράφετε ένα μορφολογικό (ορθογραφικό) λεξικό μιας γλώσσας με αρκετά πλούσια μορφολογία που περιλαμβάνει μερικά εκατομμύρια τύπους λέξεων και θέλετε να το εκδώσετε σε έντυπη μορφή.
Η πλήρης ανάπτυξη όλων αυτών των τύπων, εκτός του ότι δεν θα προσέφερε κάτι ουσιαστικό, θα είχε σαν αποτέλεσμα να καταλήξετε σε ένα ογκοδέστατο ή και πολύτομο έργο με πολλαπλάσιο κόστος εκτύπωσης και διαχείρισης συνολικότερα. Ένας τρόπος να περιορίσει κανείς τον όγκο ενός τέτοιου έργου θα ήταν να συμπεριλάβει μόνο κάποιους βασικούς τύπους λέξεων με την προϋπόθεση ότι οι υπόλοιποι μπορούν να αναπαραχθούν εύκολα με την υπαγωγή τους σε κάποιους κανόνες. Εάν όμως δεν συντρέχει η προηγούμενη προϋπόθεση για κάποιον λόγο, επειδή λ.χ. η καταγραφή της γλώσσας μπορεί να βρίσκεται σε εξέλιξη ακόμη και οι γραμματικοί της κανόνες δεν έχουν οριστικοποιηθεί και αποκρυσταλλωθεί πλήρως, τότε το μόνο που απομένει είναι η προσπάθεια της σύμπτυξης αυτών των τύπων κατά τέτοιο τρόπο που δεν θα απέβαινε σε βάρος της αναγνωσιμότητας του λεξικού. Κάτι τέτοιο, βέβαια, για να γίνει μεμονωμένα και με το χέρι, θα απαιτούσε ανυπολόγιστο χρόνο και κόπο από την πλευρά του συγγραφέα, για να μην πω ότι θα ισοδυναμούσε με αυτοκτονία. Για την καλή ή κακή μας τύχη όμως έχουμε διαβεί ήδη το κατώφλι του 21ου αιώνα και η τεχνολογία μπορεί να παίξει τον δικό της καταλυτικό ρόλο σε μια τέτοια προσπάθεια.
Αν τυχαίνει να ασχολείστε με τον προγραμματισμό και την επεξεργασία κειμένου ή κάτι παραπλήσιο, ο όρος Longest Common Prefix (Μέγιστο Κοινό Πρόθεμα) θα πρέπει να σας είναι οικείος. Η μέγιστη, δηλαδή, ριζική υποσυμβολοσειρά που μοιράζεται μια ομάδα τύπων λέξεων. Έτσι, για παράδειγμα, οι τύποι "βιβλίο", "βιβλιοπωλείο", "βιβλιοπώλης", "βιβλιοδεσία", "βιβλικός", "βιβλιοθήκη", "βιβλιοθηκονόμος" έχουν ως μέγιστο κοινό πρόθεμα την υποσυμβολοσειρά "βιβλ". Αν προσπαθήσουμε να συμπτύξουμε τους παραπάνω τύπους αντικαθιστώντας το πρόθεμα με μια παύλα, το αποτέλεσμα θα έμοιαζε κάπως έτσι: "βιβλ -ίο, -ιοπωλείο, -ιοπώλης, -ιοδεσία, -ικός, -ιοθήκη, -ιοθηκονόμος". Βλέπουμε ότι αμέσως αμέσως έχουμε εξοικονομήσει ΜΗΚΟΣ ΠΡΟΘΕΜΑΤΟΣ (4) x ΑΡΙΘΜΟΣ ΛΕΞΕΩΝ (7) – ΑΡΙΘΜΟΣ ΛΕΞΕΩΝ (παύλα) – ΜΗΚΟΣ ΠΡΟΘΕΜΑΤΟΣ = 17 χαρακτήρες. Φανταστείτε την εξοικονόμηση χώρου που επιτυγχάνεται όταν μιλάμε για εκατομμύρια λέξεων.
Κατά καιρούς, τώρα, διάφοροι ειδικοί (μαθηματικοπληροφορικοί) έχουν αναπτύξει διάφορους αλγορίθμους για τον υπολογισμό του Μέγιστου Κοινού Προθέματος ενός συνόλου συμβολοσειρών. Μια γρήγορη αναζήτηση στο διαδίκτυο θα σας πείσει γι' αυτό. Κάποιους απ' αυτούς τους έχω δοκιμάσει και ο ίδιος με κάποια επιτυχία. Στην περίπτωση της Πομακικής όμως κι επειδή εγώ προσωπικά τουλάχιστον χρησιμοποιώ "γράμματα" που αποτελούνται από πολλαπλούς συνδυάσιμους χαρακτήρες (το γράμμα "ä́" π.χ. αποτελείται από τους απλούς χαρακτήρες U+0061 [Λατινικό πεζό γράμμα Α], U+0308 [Συνδυάσιμα διαλυτικά] και U+0301 [Συνδυάσιμη οξεία] ) αλλά κι επειδή τυχαίνει να έχω εξοικειωθεί αρκετά με τη δομή ternary tree, θέλησα να δοκιμάσω και κάποιες άλλες μεθόδους που βασίζονται στη δομή αυτή με την εμπλοκή και των κανονικών εκφράσεων (Regular Expressions), τη χρήση των οποίων επιβάλλει η ανάγκη της αναγωγής των πολυχαρακτήρων αυτών σε απλούς.
Το σύνολο του πηγαίου κώδικα της υλοποίησης (C++) περιλαμβάνεται στο αρχείο pdf που ακολοθεί και μπορεί οποιοσδήποτε να το χρησιμοποιήσει κατά την κρίση του.
Στο τέλος της ανάρτησης θα βρείτε τον σύνδεσμο σε μια εφαρμογή επίδειξης.
Η πλήρης ανάπτυξη όλων αυτών των τύπων, εκτός του ότι δεν θα προσέφερε κάτι ουσιαστικό, θα είχε σαν αποτέλεσμα να καταλήξετε σε ένα ογκοδέστατο ή και πολύτομο έργο με πολλαπλάσιο κόστος εκτύπωσης και διαχείρισης συνολικότερα. Ένας τρόπος να περιορίσει κανείς τον όγκο ενός τέτοιου έργου θα ήταν να συμπεριλάβει μόνο κάποιους βασικούς τύπους λέξεων με την προϋπόθεση ότι οι υπόλοιποι μπορούν να αναπαραχθούν εύκολα με την υπαγωγή τους σε κάποιους κανόνες. Εάν όμως δεν συντρέχει η προηγούμενη προϋπόθεση για κάποιον λόγο, επειδή λ.χ. η καταγραφή της γλώσσας μπορεί να βρίσκεται σε εξέλιξη ακόμη και οι γραμματικοί της κανόνες δεν έχουν οριστικοποιηθεί και αποκρυσταλλωθεί πλήρως, τότε το μόνο που απομένει είναι η προσπάθεια της σύμπτυξης αυτών των τύπων κατά τέτοιο τρόπο που δεν θα απέβαινε σε βάρος της αναγνωσιμότητας του λεξικού. Κάτι τέτοιο, βέβαια, για να γίνει μεμονωμένα και με το χέρι, θα απαιτούσε ανυπολόγιστο χρόνο και κόπο από την πλευρά του συγγραφέα, για να μην πω ότι θα ισοδυναμούσε με αυτοκτονία. Για την καλή ή κακή μας τύχη όμως έχουμε διαβεί ήδη το κατώφλι του 21ου αιώνα και η τεχνολογία μπορεί να παίξει τον δικό της καταλυτικό ρόλο σε μια τέτοια προσπάθεια.
Αν τυχαίνει να ασχολείστε με τον προγραμματισμό και την επεξεργασία κειμένου ή κάτι παραπλήσιο, ο όρος Longest Common Prefix (Μέγιστο Κοινό Πρόθεμα) θα πρέπει να σας είναι οικείος. Η μέγιστη, δηλαδή, ριζική υποσυμβολοσειρά που μοιράζεται μια ομάδα τύπων λέξεων. Έτσι, για παράδειγμα, οι τύποι "βιβλίο", "βιβλιοπωλείο", "βιβλιοπώλης", "βιβλιοδεσία", "βιβλικός", "βιβλιοθήκη", "βιβλιοθηκονόμος" έχουν ως μέγιστο κοινό πρόθεμα την υποσυμβολοσειρά "βιβλ". Αν προσπαθήσουμε να συμπτύξουμε τους παραπάνω τύπους αντικαθιστώντας το πρόθεμα με μια παύλα, το αποτέλεσμα θα έμοιαζε κάπως έτσι: "βιβλ -ίο, -ιοπωλείο, -ιοπώλης, -ιοδεσία, -ικός, -ιοθήκη, -ιοθηκονόμος". Βλέπουμε ότι αμέσως αμέσως έχουμε εξοικονομήσει ΜΗΚΟΣ ΠΡΟΘΕΜΑΤΟΣ (4) x ΑΡΙΘΜΟΣ ΛΕΞΕΩΝ (7) – ΑΡΙΘΜΟΣ ΛΕΞΕΩΝ (παύλα) – ΜΗΚΟΣ ΠΡΟΘΕΜΑΤΟΣ = 17 χαρακτήρες. Φανταστείτε την εξοικονόμηση χώρου που επιτυγχάνεται όταν μιλάμε για εκατομμύρια λέξεων.
Κατά καιρούς, τώρα, διάφοροι ειδικοί (μαθηματικοπληροφορικοί) έχουν αναπτύξει διάφορους αλγορίθμους για τον υπολογισμό του Μέγιστου Κοινού Προθέματος ενός συνόλου συμβολοσειρών. Μια γρήγορη αναζήτηση στο διαδίκτυο θα σας πείσει γι' αυτό. Κάποιους απ' αυτούς τους έχω δοκιμάσει και ο ίδιος με κάποια επιτυχία. Στην περίπτωση της Πομακικής όμως κι επειδή εγώ προσωπικά τουλάχιστον χρησιμοποιώ "γράμματα" που αποτελούνται από πολλαπλούς συνδυάσιμους χαρακτήρες (το γράμμα "ä́" π.χ. αποτελείται από τους απλούς χαρακτήρες U+0061 [Λατινικό πεζό γράμμα Α], U+0308 [Συνδυάσιμα διαλυτικά] και U+0301 [Συνδυάσιμη οξεία] ) αλλά κι επειδή τυχαίνει να έχω εξοικειωθεί αρκετά με τη δομή ternary tree, θέλησα να δοκιμάσω και κάποιες άλλες μεθόδους που βασίζονται στη δομή αυτή με την εμπλοκή και των κανονικών εκφράσεων (Regular Expressions), τη χρήση των οποίων επιβάλλει η ανάγκη της αναγωγής των πολυχαρακτήρων αυτών σε απλούς.
Το σύνολο του πηγαίου κώδικα της υλοποίησης (C++) περιλαμβάνεται στο αρχείο pdf που ακολοθεί και μπορεί οποιοσδήποτε να το χρησιμοποιήσει κατά την κρίση του.
Στο τέλος της ανάρτησης θα βρείτε τον σύνδεσμο σε μια εφαρμογή επίδειξης.
Εφαρμογή επίδειξης