Data structures for strings in the internal and dynamic settings

Abstract

This thesis is devoted to algorithms and data structures for classical problems in stringology in the internal and dynamic settings. In the internal setting, the task is to preprocess a string S so that queries of interest for substrings of S can be answered efficiently. Note that a substring of S can be specified in constant time by the indices of an occurrence of it as a fragment of S. Efficient data structures for problems in the internal setting have proved useful as building blocks in the design of algorithms and data structures for problems on strings. Here, we consider the Internal Dictionary Matching problem, where one is given a text T of length n and a dictionary D consisting of substrings of T, each given as a fragment of T. This way, D takes space proportional to the number d=|D| of patterns rather than their total length, which could be Θ(nd). We show how to construct in (n+d)·log^{O(1)}n time a data structure that answers the following types of queries in log^{O(1)}n + O(occ) time: reporting/counting all occurrences of patterns from D in a fragment T[i..j] and reporting distinct patterns from D that occur in T[i..j]. We also present data structures for the problem of counting distinct patterns from D that occur in T[i..j]. Finally, we also address these problems for a dynamic dictionary, in which case queries are interleaved with updates to D. In the dynamic setting, the task is to maintain a collection of strings under updates, such as insertions and deletions of letters, so that information of interest can be efficiently retrieved. We consider the following problems in such a setting: Internal Pattern Matching: We show that the data structure of Gawrychowski et al. [SODA 2018] for maintaining a persistent collection X of strings, of total length at most N, under operations "split", "concatenate" and "insert a string of length 1 to X", in O(logN) time each, can be augmented to return the occurrences of any string P ∈ X in any string T ∈ X in O(|T|/|P| · log^{2}N) time. Repetition Detection: We show how to maintain the longest square substring of a dynamic string, of length at most n, in O(log^{3}n) time per update, using O(n) space. One of the main ingredients of our algorithm is our aforementioned implementation of internal pattern matching queries in the dynamic setting. Longest Common Factor: We show that a longest common factor (equiv. substring) of two dynamic strings, of total length at most n, can be maintained in amortised O(log^8 n) time per update, using Õ(n) space. An exponentially faster algorithm with polynomial space requirements is ruled out due to a lower bound in the cell-probe model of computation [Charalampopoulos et al., ICALP 2020]. We also show more efficient solutions for the case where one of the two strings is static. String Alignment: We consider the problem of dynamically maintaining an optimal alignment of two strings, each of length at most n, as they undergo edit operations. The string alignment problem generalises the longest common subsequence (LCS) problem and the edit distance problem (as long as insertions and deletions cost the same). The conditional lower bound of Backurs and Indyk [SICOMP 2018] for computing the LCS in the static case implies that strongly sublinear update time for the problem in scope is unlikely. We essentially match this lower bound when the alignment weights are constants, by showing how to process each update in Õ(n) time. When the weights are integers, bounded in absolute value by some w=n^{O(1)}, we can maintain the alignment in n·min{√n,w}·log^{O(1)}n time per update. Interestingly, we use a wide range of tools in order to obtain our results, such as: string periodicity, locally consistent parsing of strings, orthogonal range queries, efficient (min,+)-multiplication of simple unit-Monge matrices, and data structures for computing distances in planar graphs.

Η παρούσα διατριβή πραγματεύεται αλγόριθμους και δομές δεδομένων για κλασικά προβλήματα σε συμβολοσειρές στο εσωτερικό και στο δυναμικό μοντέλο. Στο εσωτερικό μοντέλο, ο στόχος είναι η επεξεργασία μίας συμβολοσειράς 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 πινάκων, και δομές δεδομένων για τον υπολογισμό αποστάσεων σε επίπεδους γράφους.