| Περίληψη: | Η μεταπτυχιακή αυτή εργασία πραγματεύεται την αυτόματη κατασκευή σταυρολέξων στην αγγλική γλώσσα. Το πρόβλημα αυτό αποτελείται από δυο διακριτά υποπροβλήματα. Το πρώτο πρόβλημα είναι η συμπλήρωση των λευκών κελιών ενός τετράγωνου πλέγματος με γράμματα, έτσι ώστε να σχηματιστούν έγκυρες λέξεις και στις δύο κατευθύνσεις, δηλαδή τόσο οριζοντίως όσο και καθέτως. Το δεύτερο πρόβλημα είναι η κατασκευή κατάλληλων ορισμών-ερωτήσεων για τις λέξεις του πλέγματος. Οι ορισμοί αυτοί βοηθούν τον παίκτη να μαντέψει τις απαντήσεις του σταυρολέξου.
Προσεγγίσαμε το πρώτο πρόβλημα ως ένα πρόβλημα ικανοποίησης περιορισμών (CSP) όπου μεταβλητές είναι τα μη συμπληρωμένα μπλοκ λευκών κελιών πάνω στο πλέγμα. Για την επίλυση του προβλήματος, σχεδιάστηκε ο αλγόριθμος CGNet ο οποίος συμπληρώνει το πλέγμα με λέξεις επιλέγοντας πρώτα μια στρατηγική γεμίσματος μπλοκ και μετά μια στρατηγική επιλογής λέξης. Οι λέξεις που τοποθετούνται στο πλέγμα υπάρχουν στη βάση γνώσης η οποία είναι μια βάση δεδομένων με λήμματα από το λεξικό θησαυρός WordNet. O αλγόριθμος στη συνέχεια εκτελεί έλεγχο συνέπειας και εφαρμόζει τεχνικές χαλάρωσης των λέξεων όταν φθάνει σε αδιέξοδο.
Το δεύτερο πρόβλημα, την κατασκευή ερωτήσεων για τις απαντήσεις του σταυρολέξου, το λύνουμε χρησιμοποιώντας το λεξικό WordNet. Για κάθε απάντηση του σταυρολέξου ο αλγόριθμος ψάχνει να βρει έναν ορισμό στο λεξικό και δημιουργεί την αντίστοιχη ερώτηση. Ο αλγόριθμος φροντίζει έτσι ώστε η απάντηση να μην εμφανίζεται στην ερώτηση και να μη χρησιμοποιηθεί η ίδια ερώτηση πολλές φορές. Στην περίπτωση που η απάντηση του σταυρολέξου δεν περιέχεται στο λεξικό τότε ο αλγόριθμος ψάχνει για λήμματα στο λεξικό που να ταιριάζουν με την τεχνική χαλάρωσης την οποία εφάρμοσε ο αλγόριθμος.
Για να υποστηρίξουμε την προσέγγιση μας, αναπτύχθηκε το σύστημα CGNet το οποίο υλοποιεί τον παραπάνω αλγόριθμο. Ο χρήστης του συστήματος δίνει τις παραμέτρους εισόδου και το σταυρόλεξο μαζί με τις ερωτήσεις-ορισμούς δημιουργούνται αυτόματα. Έχει γίνει συγκριτική αξιολόγηση του συστήματος για όλους τους συμβατούς συνδυασμούς των στρατηγικών γεμίσματος μπλοκ και επιλογής λέξεων. Από την συγκριτική αξιολόγηση καταλήγουμε ποιος είναι ο καλύτερος συνδυασμός στρατηγικών γεμίσματος και επιλογής. Στη πειραματική μελέτη του συστήματος χρησιμοποιήθηκαν πλέγματα διαφορετικής δομής και διαφορετικού μεγέθους 5x5, 13x13 και 15x15 και αποδεικνύεται τελικά ότι η συνολική μας προσέγγιση είναι επιτυχής.
|
|---|
