Wavelet trees: Theory and implementation

Abstract

Το αντικείμενο της παρούσας διατριβής είναι η ενδελεχής κατανόηση και παρουσίαση των χαρα‐ κτηριστικών και της λειτουργίας του wavelet tree, μιας πολλαπλών εφαρμογών δομής δεδομένων που αρχικά προτάθηκε για την συμπίεση κειμένου, δια της μελέτης της υφιστάμενης βιβλιογρα‐ φίας. Επιπλέον, θα ανακτηθούν υφιστάμενες υλοποιήσεις της δομής, από ελεύθερες πηγές και θα ελεγ‐ χθεί η αποδοτικότητά τους με δοκιμές επί πραγματικών δεδομένων μεγάλου όγκου και διαφόρων ειδών. Τέλος, θα πραγματοποιηθεί υλοποίηση της δομής, με την αξιοποίηση των προηγουμένων, και έμ‐ φαση στην ορθή λειτουργία επί δεδομένων μεγάλου όγκου, με την μέγιστη δυνατή λειτουργικό‐ τητα και αποτελεσματικότητα, συγκριτικά με τις υφιστάμενες δομές που θα ανακτηθούν από ε‐ λεύθερες πηγές.