Μονάδα:
Τομέας Υπολογιστικών Συστημάτων και ΕφαρμογώνΒιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2016-10-19
Συγγραφέας:
Πανταζή Δέσποινα Αθανασία
Στοιχεία επιβλεπόντων καθηγητών:
Γιώργος Γιαννακόπουλος, Παναγιώτης Σταματόπουλος
Πρωτότυπος Τίτλος:
N-gram graph decompression
Γλώσσες εργασίας:
Αγγλικά
Μεταφρασμένος τίτλος:
Αποσυμπίεση γράφων ν-γραμμάτων
Περίληψη:
Στα πλαίσια αυτής της εργασίας, μελετήσαμε την πληροφορία που περιέχει ένας
γράφος ν-γραμμάτων. Για να πραγματοποιήσουμε το παραπάνω, αναζητήσαμε όλες τις
συμβολοσειρές
που μπορούν να συμπιεστούν και να παράξουν τον ίδιο γράφο ν-γραμμάτων. Για να
βρούμε
αυτές τις συμβολοσειρές, ορίσαμε το πρόβλημα αποσυμπίεσης του γράφου ν-
γραμμάτων. Επιπλέον, εξετάσαμε το πρόβλημα ως πρόβλημα ικανοποίησης
περιορισμών, έτσι ώστε να το βελτιστοποιήσουμε, και εφαρμόσαμε ένα σύνολο
μεθόδων αναζήτησης για να το επιλύσουμε. Παράλληλα, σχεδιάσαμε δύο ευριστικές
συναρτήσεις για να καλυτερεύσουμε τους χρόνους των μετρήσεών μας. Τέλος,
πραγματοποιήσαμε ένα σύνολο πειραμάτων σε συγκεκριμένους αλγορίθμους
αναζήτησης, για να αποσυμπιέσουμε το κείμενο που έχει συμπιεστεί στους γράφους
ν-γραμμάτων. Συγκρίνοντας τα αποτελέσματα των πειραμάτων, συμπεράναμε πως τα
καλύτερα αποτελέσματα για την αποσυμπίεση μικρών συμβολοσειρών είναι αυτά που
προκύπτουν με την εφαρμογή της τοπικής αναζήτησης. Οι συμβολοσειρές που
περιέχουν μεγαλύτερο αριθμό
γραμμάτων αποσυμπιέστηκαν γρηγορότερα με τη χρήση της ευριστικής συνάρτησης που
βασίστηκε στο βάρος των κόμβων των γράφων ν-γραμμάτων.
Λέξεις-κλειδιά:
γράφος ν-γραμμάτων, αποσυμπίεση, τοπική αναζήτηση, πρόβλημα περιορισμών, ευριστικές συναρτήσεις
Αρ. σελίδων ευρετηρίου:
9, 10, 11
Αρ. βιβλιογραφικών αναφορών:
15
