Analysis of depth of digital trees built on general sources
Institution:
CaenDisciplines:
Directors:
Abstract EN:
This thesis performs probabilistic analyses of the depth of digital trees [tries and digital search trees (dst)] when they are built on words emitted by a general source. This study is related to compression algorithms of Lempel-Ziv type which are based on the use of digital trees (tries or dst). The complexity of algorithms which use these data structures are related to the shape of these trees, and we are here interested by the probabilistic behaviour of an important parameter, the typical depth, or depth. We introduce a new point of view on general sources, and we then focus on the model of dynamical sources. The source intervenes in the analysis via its tameness, and we define precise notions of tameness which are new. The thesis deals with methods in analytic combinatorics, and we introduce (Dirichlet) generating functions, which characterize the behaviour of the tree (trie or dst) when it is built on the source. As the source is a dynamical source, we perform a dynamical analysis, which mixes in an original setting method from analytic combinatorics and methods from dynamical system theory (namely transfer operators, and their spectral properties). We also use many objects and methods from classical analytic combinatorics, as Poisson, Laplace, and Mellin transforms, that we mix in a new way. We also provide an unified point of view on the analysis of the two types of digital trees (tries and dst), whereas the classical analyses are dedicated to one of the precise types of trees. Finally, we prove that, for the two types of digital trees, for a large class of sources, the typical depth follows an asymptiotic gaussian law, with an optimal speed of convergence.
Abstract FR:
Cette thèse effectue des analyses probabilistes de la profondeur des arbres digitaux [ tries et arbres digitaux de recherche(dst) ] quand ils sont construits sur des mots émis par une source générale. Cette étude est liée à des algorithmes de compression de type Lempel-Ziv qui sont basés sur l'utilisation d'arbres digitaux (tries or dst). La complexité des algorithmes qui utilisent ces structures de données sont liés à la forme de ces arbres , et nous sommes ici intéressés par le comportement probabiliste d'un paramètre important , la profondeur typique ou la profondeur. Nous introduisons un nouveau point de vue sur les sources générales et nous nous concentrons alors sur le modèle des sources dynamiques. La source intervient dans l'analyse par sa ``tameness” , et nous définissons les notions précises de ``tameness” qui sont nouveaux. La thèse traite des méthodes de combinatoire analytique et nous introduisons ( Dirichlet ) fonctions génératrices , qui caractérisent le comportement de l'arbre ( trie ou dst ) quand il est construit sur la source. Comme la source est une source dynamique , nous effectuons une analyse dynamique, qui mélange dans une des méthodes de réglage d'origine de la combinatoire et les méthodes de la théorie des systèmes dynamiques d'analyse ( i. E. Transférer les opérateurs , et leurs propriétés spectrales). Nous utilisons également de nombreux objets et méthodes de la combinatoire analytiques classiques , comme Poisson , Laplace , et Mellin transforme , que nous mélangeons à une nouvelle façon. Nous fournissons également un point de vue unifié sur l'analyse des deux types d'arbres digitaux ( tries et dst ) , alors que les analyses classiques sont dédiés à un type précis d'arbres. Enfin , nous montrons que , pour les deux types d'arbres digitaux , pour une large classe de sources , la profondeur typique suit asymptiquement une loi gaussienne , avec une vitesse de convergence optimal.