Αυτόματη δημιουργία σταυρολέξων
Η μεταπτυχιακή αυτή εργασία πραγματεύεται την αυτόματη κατασκευή σταυρολέξων στην αγγλική γλώσσα. Το πρόβλημα αυτό αποτελείται από δυο διακριτά υποπροβλήματα. Το πρώτο πρόβλημα είναι η συμπλήρωση των λευκών κελιών ενός τετράγωνου πλέγματος με γράμματα, έτσι ώστε να σχηματιστούν έγκυρες λέξεις και στ...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Thesis |
| Γλώσσα: | Greek |
| Έκδοση: |
2016
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/9584 |
| id |
nemertes-10889-9584 |
|---|---|
| record_format |
dspace |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Σταυρόλεξα Crosswords Puzzles CGNet 793.734 028 5 |
| spellingShingle |
Σταυρόλεξα Crosswords Puzzles CGNet 793.734 028 5 Χαλκιόπουλος, Χρήστος Αυτόματη δημιουργία σταυρολέξων |
| description |
Η μεταπτυχιακή αυτή εργασία πραγματεύεται την αυτόματη κατασκευή σταυρολέξων στην αγγλική γλώσσα. Το πρόβλημα αυτό αποτελείται από δυο διακριτά υποπροβλήματα. Το πρώτο πρόβλημα είναι η συμπλήρωση των λευκών κελιών ενός τετράγωνου πλέγματος με γράμματα, έτσι ώστε να σχηματιστούν έγκυρες λέξεις και στις δύο κατευθύνσεις, δηλαδή τόσο οριζοντίως όσο και καθέτως. Το δεύτερο πρόβλημα είναι η κατασκευή κατάλληλων ορισμών-ερωτήσεων για τις λέξεις του πλέγματος. Οι ορισμοί αυτοί βοηθούν τον παίκτη να μαντέψει τις απαντήσεις του σταυρολέξου.
Προσεγγίσαμε το πρώτο πρόβλημα ως ένα πρόβλημα ικανοποίησης περιορισμών (CSP) όπου μεταβλητές είναι τα μη συμπληρωμένα μπλοκ λευκών κελιών πάνω στο πλέγμα. Για την επίλυση του προβλήματος, σχεδιάστηκε ο αλγόριθμος CGNet ο οποίος συμπληρώνει το πλέγμα με λέξεις επιλέγοντας πρώτα μια στρατηγική γεμίσματος μπλοκ και μετά μια στρατηγική επιλογής λέξης. Οι λέξεις που τοποθετούνται στο πλέγμα υπάρχουν στη βάση γνώσης η οποία είναι μια βάση δεδομένων με λήμματα από το λεξικό θησαυρός WordNet. O αλγόριθμος στη συνέχεια εκτελεί έλεγχο συνέπειας και εφαρμόζει τεχνικές χαλάρωσης των λέξεων όταν φθάνει σε αδιέξοδο.
Το δεύτερο πρόβλημα, την κατασκευή ερωτήσεων για τις απαντήσεις του σταυρολέξου, το λύνουμε χρησιμοποιώντας το λεξικό WordNet. Για κάθε απάντηση του σταυρολέξου ο αλγόριθμος ψάχνει να βρει έναν ορισμό στο λεξικό και δημιουργεί την αντίστοιχη ερώτηση. Ο αλγόριθμος φροντίζει έτσι ώστε η απάντηση να μην εμφανίζεται στην ερώτηση και να μη χρησιμοποιηθεί η ίδια ερώτηση πολλές φορές. Στην περίπτωση που η απάντηση του σταυρολέξου δεν περιέχεται στο λεξικό τότε ο αλγόριθμος ψάχνει για λήμματα στο λεξικό που να ταιριάζουν με την τεχνική χαλάρωσης την οποία εφάρμοσε ο αλγόριθμος.
Για να υποστηρίξουμε την προσέγγιση μας, αναπτύχθηκε το σύστημα CGNet το οποίο υλοποιεί τον παραπάνω αλγόριθμο. Ο χρήστης του συστήματος δίνει τις παραμέτρους εισόδου και το σταυρόλεξο μαζί με τις ερωτήσεις-ορισμούς δημιουργούνται αυτόματα. Έχει γίνει συγκριτική αξιολόγηση του συστήματος για όλους τους συμβατούς συνδυασμούς των στρατηγικών γεμίσματος μπλοκ και επιλογής λέξεων. Από την συγκριτική αξιολόγηση καταλήγουμε ποιος είναι ο καλύτερος συνδυασμός στρατηγικών γεμίσματος και επιλογής. Στη πειραματική μελέτη του συστήματος χρησιμοποιήθηκαν πλέγματα διαφορετικής δομής και διαφορετικού μεγέθους 5x5, 13x13 και 15x15 και αποδεικνύεται τελικά ότι η συνολική μας προσέγγιση είναι επιτυχής. |
| author2 |
Χατζηλυγερούδης, Ιωάννης |
| author_facet |
Χατζηλυγερούδης, Ιωάννης Χαλκιόπουλος, Χρήστος |
| format |
Thesis |
| author |
Χαλκιόπουλος, Χρήστος |
| author_sort |
Χαλκιόπουλος, Χρήστος |
| title |
Αυτόματη δημιουργία σταυρολέξων |
| title_short |
Αυτόματη δημιουργία σταυρολέξων |
| title_full |
Αυτόματη δημιουργία σταυρολέξων |
| title_fullStr |
Αυτόματη δημιουργία σταυρολέξων |
| title_full_unstemmed |
Αυτόματη δημιουργία σταυρολέξων |
| title_sort |
αυτόματη δημιουργία σταυρολέξων |
| publishDate |
2016 |
| url |
http://hdl.handle.net/10889/9584 |
| work_keys_str_mv |
AT chalkiopouloschrēstos automatēdēmiourgiastaurolexōn AT chalkiopouloschrēstos automaticcrosswordpuzzlegeneration |
| _version_ |
1771297272381833216 |
| spelling |
nemertes-10889-95842022-09-05T14:00:25Z Αυτόματη δημιουργία σταυρολέξων Automatic crossword puzzle generation Χαλκιόπουλος, Χρήστος Χατζηλυγερούδης, Ιωάννης Σγάρμπας, Κυριάκος Μακρής, Χρήστος Chalkiopoulos, Christos Σταυρόλεξα Crosswords Puzzles CGNet 793.734 028 5 Η μεταπτυχιακή αυτή εργασία πραγματεύεται την αυτόματη κατασκευή σταυρολέξων στην αγγλική γλώσσα. Το πρόβλημα αυτό αποτελείται από δυο διακριτά υποπροβλήματα. Το πρώτο πρόβλημα είναι η συμπλήρωση των λευκών κελιών ενός τετράγωνου πλέγματος με γράμματα, έτσι ώστε να σχηματιστούν έγκυρες λέξεις και στις δύο κατευθύνσεις, δηλαδή τόσο οριζοντίως όσο και καθέτως. Το δεύτερο πρόβλημα είναι η κατασκευή κατάλληλων ορισμών-ερωτήσεων για τις λέξεις του πλέγματος. Οι ορισμοί αυτοί βοηθούν τον παίκτη να μαντέψει τις απαντήσεις του σταυρολέξου. Προσεγγίσαμε το πρώτο πρόβλημα ως ένα πρόβλημα ικανοποίησης περιορισμών (CSP) όπου μεταβλητές είναι τα μη συμπληρωμένα μπλοκ λευκών κελιών πάνω στο πλέγμα. Για την επίλυση του προβλήματος, σχεδιάστηκε ο αλγόριθμος CGNet ο οποίος συμπληρώνει το πλέγμα με λέξεις επιλέγοντας πρώτα μια στρατηγική γεμίσματος μπλοκ και μετά μια στρατηγική επιλογής λέξης. Οι λέξεις που τοποθετούνται στο πλέγμα υπάρχουν στη βάση γνώσης η οποία είναι μια βάση δεδομένων με λήμματα από το λεξικό θησαυρός WordNet. O αλγόριθμος στη συνέχεια εκτελεί έλεγχο συνέπειας και εφαρμόζει τεχνικές χαλάρωσης των λέξεων όταν φθάνει σε αδιέξοδο. Το δεύτερο πρόβλημα, την κατασκευή ερωτήσεων για τις απαντήσεις του σταυρολέξου, το λύνουμε χρησιμοποιώντας το λεξικό WordNet. Για κάθε απάντηση του σταυρολέξου ο αλγόριθμος ψάχνει να βρει έναν ορισμό στο λεξικό και δημιουργεί την αντίστοιχη ερώτηση. Ο αλγόριθμος φροντίζει έτσι ώστε η απάντηση να μην εμφανίζεται στην ερώτηση και να μη χρησιμοποιηθεί η ίδια ερώτηση πολλές φορές. Στην περίπτωση που η απάντηση του σταυρολέξου δεν περιέχεται στο λεξικό τότε ο αλγόριθμος ψάχνει για λήμματα στο λεξικό που να ταιριάζουν με την τεχνική χαλάρωσης την οποία εφάρμοσε ο αλγόριθμος. Για να υποστηρίξουμε την προσέγγιση μας, αναπτύχθηκε το σύστημα CGNet το οποίο υλοποιεί τον παραπάνω αλγόριθμο. Ο χρήστης του συστήματος δίνει τις παραμέτρους εισόδου και το σταυρόλεξο μαζί με τις ερωτήσεις-ορισμούς δημιουργούνται αυτόματα. Έχει γίνει συγκριτική αξιολόγηση του συστήματος για όλους τους συμβατούς συνδυασμούς των στρατηγικών γεμίσματος μπλοκ και επιλογής λέξεων. Από την συγκριτική αξιολόγηση καταλήγουμε ποιος είναι ο καλύτερος συνδυασμός στρατηγικών γεμίσματος και επιλογής. Στη πειραματική μελέτη του συστήματος χρησιμοποιήθηκαν πλέγματα διαφορετικής δομής και διαφορετικού μεγέθους 5x5, 13x13 και 15x15 και αποδεικνύεται τελικά ότι η συνολική μας προσέγγιση είναι επιτυχής. This master thesis discusses the problem of automatic construction of crossword puzzles in the English language. This problem consists of two sub-problems. The first problem is the completion of all the white cells of a blank square grid with letters, in a way that valid English words are formed in both directions of the grid, horizontal and vertical. The second problem is the construction of appropriate clues for the words in the grid. These clues help the player to guess the answers of the crossword puzzle. The approach we followed for solving the first problem was to consider the problem as a constraint satisfaction problem (CSP) wherein the variables are the incomplete white cell blocks on the grid. We designed an algorithm, named CGNet, which in every iteration of the execution chooses a block to fill in, based on the fill strategy and then chooses a word to fill in the block, based on the pick strategy. The algorithm searches inside a knowledge base for words to fill into the blocks of the grid. This knowledge base is a database of words with lemmas from the WordNet thesaurus. At the end of every execution, the algorithm performs consistency check and if needed, applies a loosening technique on the non valid English words. We used the WordNet thesaurus for solving the second problem, which is the construction of clues for the crossword answers. For every crossword answer, the algorithm tries to find a definition in the dictionary and upon success constructs the respective clue. The algorithm makes sure that the answer does not appear in the clue and that a specific clue is never used more than once in the same crossword. When there is no definition for a word, the algorithm searches for lemmas in the dictionary that can match with the loosening technique that was applied by the algorithm. The CGNet system was developed with an implementation of the aforementioned algorithm, to support our approach for solving this problem. The user feeds the system with the input parameters and the system automatically constructs the crossword puzzle and the clues. An extensive system evaluation was performed by trying all the compatible combinations of fill and pick strategy. The outcome of the evaluation was to identify which is the best combination of the various fill and pick strategies. This benchmarking was performed on different grids regarding the structure and the size (5x5, 13x13, 15x15). At the end, we prove that the overall approach of solving this problem is successful. 2016-09-20T11:04:38Z 2016-09-20T11:04:38Z 2016-06-13 Thesis http://hdl.handle.net/10889/9584 gr 0 application/pdf |
