Data structures for strings in the internal and dynamic settings
Authors: Χαραλαμπόπουλος Παναγιώτης 
Published: October 2024

Η παρούσα διατριβή πραγματεύεται αλγόριθμους και δομές δεδομένων για κλασικά προβλήματα σε συμβολοσειρές στο εσωτερικό και στο δυναμικό μοντέλο. Στο εσωτερικό μοντέλο, ο στόχος είναι η επεξεργασία μίας συμβολοσειράς S που να επιτρέπει την γρήγορη απάντηση ερωτημάτων για υποσυμβολοσειρές του S. Σημειώνουμε ότι μία υποσυμβολοσειρά του S μπορεί προσδιοριστεί σε σταθερό χώρο με την αρχική και την τελική θέση μιας εμφάνισής της στο S. Αποδοτικές δομές δεδομένων για προβλήματα στο εσωτερικό μοντέλο έχουν αποδειχθεί χρήσιμες στον σχεδιασμό αλγορίθμων και δομών δεδομένων για προβλήματα σε συμβολοσειρές. Εδώ, εξετάζουμε το πρόβλημα Αντιστοίχισης Εσωτερικού Λεξικού, όπου μας δίνεται ένα κείμενο T μήκους n και ένα λεξικό D αποτελούμενο από υποσυμβολοσειρές του T. To λεξικό D καταλαβάνει χώρο ανάλογο με το πλήθος d=|D| των στοιχείων του και όχι με το συνολικό τους μήκος που μπορεί να είναι Θ(nd). Δείχνουμε πώς μπορεί να κατασκευαστεί σε χρόνο (n+d)·log^{O(1)}n μία δομή δεδομένων η οποία απαντάει σε χρόνο log^{O(1)}n + O(|output|) τα κάτωθι ερωτήματα: μέτρηση/αναφορά όλων των αντιστοιχίσεων στοιχείων του D σε μία υποσυμβολοσειρά T[i..j] και αναφορά όλων των διαφορετικών στοιχείων του D που εμφανίζονται στο T[i..j]. Επιπλέον, παρουσιάζουμε δομές δεδομένων για το πρόβλημα της μέτρησης των διαφορετικών στοιχείων του D που εμφανίζονται στο T[i..j]. Τελικώς, πραγματευόμαστε τα προβλήματα αυτά στην περίπτωση ενός δυναμικού λεξικού, όπου ανάμεσα στα ερωτήματα παρεμβάλλονται αλλαγές στο D. Στο δυναμικό μοντέλο, ο στόχος είναι η διατήρηση μίας συλλογής συμβολοσειρών που επιδέχεται αλλαγές, όπως την εισαγωγή ή τη διαγραφή συμβόλων, ώστε να υπάρχει η δυνατότητα εξαγωγής ενδιαφέρουσων πληροφοριών. Εξετάζουμε τα κάτωθι προβλήματα σε τέτοια μοντέλα: Αντιστοίχιση Εσωτερικού Προτύπου: Δείχνουμε ότι η δομή δεδομένων των Gawrychowski et al. [SODA 2018] για τη διατήρηση μιας συλλογής συμβολοσειρών X, συνολικού μήκους το πολύ Ν, που επιτρέπει αλλαγές τύπου "split", "concatenate" και "εισαγωγή συμβολοσειράς μήκους 1 στο Χ" σε χρόνο O(logN), μπορεί επιπλέον να υποστηρίξει την επιστροφή όλων των αντιστοιχίσεων οποιουδήποτε προτύπου P ∈ X σε οποιοδήποτε T ∈ X σε χρόνο O(|T|/|P| · log^{2}N). Ανίχνευση Επαναλήψεων: Δείχνουμε πώς μπορούμε να διατηρήσοουμε την μεγαλύτερη τετράγωνη υποσυμβολοσειρά μιας δυναμικής συμβολοσειράς μήκους το πολύ n, σε χρόνο O(log^{3}n) για κάθε αλλαγή, χρησιμοποιώντας χώρο O(n). Ένα βασικό συστατικό του αλγορίθμου μας είναι η προαναφερθείσα υλοποίηση ερωτημάτων αντιστοίχισης εσωτερικού προτύπου στο δυναμικό μοντέλο. Μέγιστη Κοινή Υποσυμβολοσειρά: Δείχνουμε πως μία μέγιστη κοινή υποσυμβολοσειρά δύο δυναμικών συμβολοσειρών, συνολικού μήκους το πολύ n, μπορεί να διατηρηθεί σε χρόνο O(log^8 n) ανά αλλαγή, χρησιμοποιώντας χώρο Õ(n). Εκθετικά γρηγορότερος αλγόριθμος με πολυωνυμική κατανάλωση χώρου δε μπορεί να υπάρξει λόγω ενός κάτω φράγματος στο cell-probe μοντέλο υπολογισμού [Charalampopoulos et al., ICALP 2020]. Επιπλέον, δείχνουμε πιο αποδοτικές λύσεις για την περίπτωση που μία από τις συμβολοσειρές είναι στατική. Ευθυγράμμιση συμβολοσειρών: Εξετάζουμε το πρόβλημα της δυναμικής διατήρησης μιας βέλτιστης ευθυγράμμισης συμβολοσειρών, μήκους το πολύ n, καθώς υφίστανται αλλαγές. Το πρόβλημα της ευθυγράμμισης συμβολοσειρών γενικεύει τα προβλήματα υπολογισμού μέγιστης υπακολουθίας και υπολογισμού μεταβολής ακολουθίας (αν οι εισαγωγές και οι διαγραφές έχουν το ίδιο κόστος). Το υπό όρους κάτω φράγμα των Backurs and Indyk [SICOMP 2018] για τον υπολογισμό της μέγιστης υπακολουθίας στη στατική περίπτωση συνεπάγεται πως ένας ισχυρά υπογραμμικός αλγόριθμος για το εξεταζόμενο πρόβλημα είναι μάλλον απίθανος. Ουσιαστικά, φτάνουμε αυτό το κάτω φράγμα όταν τα κόστη της ευθυγράμμισης είναι σταθερές, δείχνοντας πώς να επεξαργαστούμε την κάθε αλλαγή σε χρόνο Õ(n). Όταν τα κόστη είναι ακέραιοι, ανω φραγμένοι σε απόλυτη τιμή από κάποιο w=n^{O(1)}, μπορούμε να διατηρήσουμε την ευθυγράμμιση σε χρόνο n·min{√n,w}·log^{O(1)}n ανά αλλαγή. Παρουσιάζει ενδιαφέρον η χρησιμοποίηση μιας ευρείας γκάμας εργαλείων, όπως: περιοδικότητα συμβολοσειρών, τοπικά συνεπείς αναλύσεις συμβολοσειρών, αναζήτηση σημείων ως προς ορθογώνια περιοχή, αποδοτικός (min,+)-πολλαπλασιασμός simple unit-Monge πινάκων, και δομές δεδομένων για τον υπολογισμό αποστάσεων σε επίπεδους γράφους.