Σάββατο, 5 Δεκεμβρίου 2015

Μικρά προγραμματιστικά - Μέγιστο Κοινό Πρόθεμα (Longest Common Prefix) και η σύμπτυξη των λημμάτων ενός λεξικού με τη βοήθεια μιας δομής Ternary Tree

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

Η πλήρης ανάπτυξη όλων αυτών των τύπων, εκτός του ότι δεν θα προσέφερε κάτι ουσιαστικό, θα είχε σαν αποτέλεσμα να καταλήξετε σε ένα ογκοδέστατο ή και πολύτομο έργο με πολλαπλάσιο κόστος εκτύπωσης και διαχείρισης συνολικότερα.  Ένας τρόπος να περιορίσει κανείς τον όγκο ενός τέτοιου έργου θα ήταν να συμπεριλάβει μόνο κάποιους βασικούς τύπους λέξεων με την προϋπόθεση ότι οι υπόλοιποι μπορούν να αναπαραχθούν εύκολα με την υπαγωγή τους σε κάποιους κανόνες.  Εάν όμως δεν συντρέχει η προηγούμενη προϋπόθεση για κάποιον λόγο, επειδή λ.χ. η καταγραφή της γλώσσας μπορεί να βρίσκεται σε εξέλιξη ακόμη και οι γραμματικοί της κανόνες δεν έχουν οριστικοποιηθεί και αποκρυσταλλωθεί πλήρως, τότε το μόνο που απομένει είναι η προσπάθεια της σύμπτυξης αυτών των τύπων κατά τέτοιο τρόπο που δεν θα απέβαινε σε βάρος της αναγνωσιμότητας του λεξικού.  Κάτι τέτοιο, βέβαια, για να γίνει μεμονωμένα και με το χέρι, θα απαιτούσε ανυπολόγιστο χρόνο και κόπο από την πλευρά του συγγραφέα, για να μην πω ότι θα ισοδυναμούσε με αυτοκτονία.   Για την καλή ή κακή μας τύχη όμως έχουμε διαβεί ήδη το κατώφλι του 21ου αιώνα και η τεχνολογία μπορεί να παίξει τον δικό της καταλυτικό ρόλο σε μια τέτοια προσπάθεια.

Αν τυχαίνει να ασχολείστε με τον προγραμματισμό και την επεξεργασία κειμένου ή κάτι παραπλήσιο, ο όρος Longest Common Prefix (Μέγιστο Κοινό Πρόθεμα) θα πρέπει να σας είναι οικείος.  Η μέγιστη, δηλαδή, ριζική υποσυμβολοσειρά που μοιράζεται μια ομάδα τύπων λέξεων.  Έτσι, για παράδειγμα, οι τύποι "βιβλίο", "βιβλιοπωλείο", "βιβλιοπώλης", "βιβλιοδεσία", "βιβλικός", "βιβλιοθήκη", "βιβλιοθηκονόμος" έχουν ως μέγιστο κοινό πρόθεμα την υποσυμβολοσειρά "βιβλ".  Αν προσπαθήσουμε να συμπτύξουμε τους παραπάνω τύπους αντικαθιστώντας το πρόθεμα με μια παύλα, το αποτέλεσμα θα έμοιαζε κάπως έτσι: "βιβλ -ίο, -ιοπωλείο, -ιοπώλης, -ιοδεσία, -ικός, -ιοθήκη, -ιοθηκονόμος".  Βλέπουμε ότι αμέσως αμέσως έχουμε εξοικονομήσει ΜΗΚΟΣ ΠΡΟΘΕΜΑΤΟΣ (4) x ΑΡΙΘΜΟΣ ΛΕΞΕΩΝ (7) – ΑΡΙΘΜΟΣ ΛΕΞΕΩΝ (παύλα) – ΜΗΚΟΣ ΠΡΟΘΕΜΑΤΟΣ = 17 χαρακτήρες.  Φανταστείτε την εξοικονόμηση χώρου που επιτυγχάνεται όταν μιλάμε για εκατομμύρια λέξεων.

Κατά καιρούς, τώρα, διάφοροι ειδικοί (μαθηματικοπληροφορικοί) έχουν αναπτύξει διάφορους αλγορίθμους για τον υπολογισμό του Μέγιστου Κοινού Προθέματος ενός συνόλου συμβολοσειρών.  Μια γρήγορη αναζήτηση στο διαδίκτυο θα σας πείσει γι' αυτό.  Κάποιους απ' αυτούς τους έχω δοκιμάσει και ο ίδιος με κάποια επιτυχία.  Στην περίπτωση της Πομακικής όμως κι επειδή εγώ προσωπικά τουλάχιστον χρησιμοποιώ "γράμματα" που αποτελούνται από πολλαπλούς συνδυάσιμους χαρακτήρες (το γράμμα "ä́" π.χ. αποτελείται από τους απλούς χαρακτήρες U+0061 [Λατινικό πεζό γράμμα Α], U+0308 [Συνδυάσιμα διαλυτικά] και U+0301 [Συνδυάσιμη οξεία] ) αλλά κι επειδή τυχαίνει να έχω εξοικειωθεί αρκετά με τη δομή ternary tree, θέλησα να δοκιμάσω και κάποιες άλλες μεθόδους που βασίζονται στη δομή αυτή με την εμπλοκή και των κανονικών εκφράσεων (Regular Expressions), τη χρήση των οποίων επιβάλλει η ανάγκη της αναγωγής των πολυχαρακτήρων αυτών σε απλούς.

Το σύνολο του πηγαίου κώδικα της υλοποίησης (C++) περιλαμβάνεται στο αρχείο pdf που ακολοθεί και μπορεί οποιοσδήποτε να το χρησιμοποιήσει κατά την κρίση του.
Στο τέλος της ανάρτησης θα βρείτε τον σύνδεσμο σε μια εφαρμογή επίδειξης.





Εφαρμογή επίδειξης

Δευτέρα, 27 Ιουλίου 2015

Λέξεις ταξιδιάρες, λέξεις περιπατητικές

Λέξεις ταξιδιάρες, λέξεις περιπατητικές

Να πόσα ενδιαφέροντα και αποκαλυπτικά πράγματα μπορεί να μάθει κανείς κάνοντας μια σύντομη "τσάρκα" στη γειτονιά μας μέσω της υπηρεσίας μηχανικής μετάφρασης της Google.  Κι ενώ είναι γνωστές οι αδυναμίες της υπηρεσίας αυτής, εντούτοις το "θέαμα" είναι άκρως ελκυστικό, κυρίως από μορφολογική άποψη και πέρα από την όποια σημασιολογική εγγύτητα ή αναντιστοιχία.
Οι λέξεις επιλέχτηκαν στην τύχη κι εκτιμώ ότι πρέπει να υπάρχουν κι άλλες τέτοιες αρκετές, τις οποίες σας αφήνω να ανακαλύψετε μόνοι σας.
Μόνο οι τρεις πρώτες στήλες έχουν ελεγχθεί γραμματικά και σημασιολογικά με βάση τα έντυπα λεξικά που υπάρχουν στη διάθεση του γράφοντος.  Το περιεχόμενο των υπόλοιπων στηλών παρατίθεται αυτούσιο όπως δίδεται από τη συγκεκριμένη υπηρεσία.



Ενημέρωση: 15/8/2015

Κάπως έτσι φαντάζομαι ότι θα ξεκίνησε ο γλωσσολόγος Mark Hučko τη δημιουργία της σλαβικής "εσπεράντο", της Σλόβιο (Slovio).  Όπως υποστηρίζει ο δημιουργός της η τεχνητή αυτή γλώσσα μπορεί να κατανοηθεί πολύ εύκολα απ' όλους τους σλαβόφωνους πληθυσμούς, οι οποίοι ούτε λίγο ούτε πολύ υπολογίζεται ότι αριθμούν περί τα 400.000.000 πολιτών σε όλον τον κόσμο.

Παρασκευή, 19 Ιουνίου 2015

Όψιμο χιόνι

Όψιμο χιόνι

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

Όμως το πιο φοβερό είναι
ότι αυτά
που θα ανθίσουν μετά και θα καρπίσουν -
δεν θα ξέρουν ή θα ξεχάσουν
ποιος είναι ο υπαίτιος
και θα πουν με κατηγόρια ή περιφρόνηση
στα πιο τολμηρά:
- Γιατί είστε γυμνά;
- Γιατί είστε άκαρπα;

Αυτά σκέφτομαι, όψιμο χιόνι, και θλίβομαι.

1965

Στέφαν Τσάνεφ
Ουράνιες περιπέτειες - Στίχοι
Σόφια 1986

Μετάφραση στα Ελληνικά: Ριτβάν Καρα - Χότζα


Късен сняг

Късен сняг, защо дойде?
Сам знаеш колко напразно е това, няма
да измениш хода на нещата,
пролетта ще дойде въпреки тебе.
Жалко само
за най-дръзките растения.
Тези, които първи се разлистиха, няма да цъфнат.
Тези, които първи цъфнаха, няма да родят плод.

Но най-страшното е,
че онези,
които ще цъфнат след това и ще родят -
няма да знаят или ще забравят
кой е виновен
и ще кажат с упрек или с презрение
на най-дръзките:
- Защо сте голи?
- Защо сте ялови?

Затова си мисля, късен сняг, и ми е тъжно.

1965

Стефан Цанев
Небесни премеждия - Стихове
София 1986

Превод на Гръцки: Ритван Кара - Хотза