Brigitte Vallée (GREYC, Caen)

Les arbres digitaux de recherche (dst) jouent un rôle essentiel dans les algorithmes de compression, du type Lempel-Ziv. Cette structure de données peut-être vue comme un hybride entre un arbre (binaire) de recherche (bst) et un arbre digital de type trie. L’analyse probabiliste de ses principaux paramètres (par exemple sa profondeur) s’avère donc complexe, même dans le cas où les mots sont produits par une source simple (sans mémoire ou chaine de Markov). Après les travaux fondateurs de Flajolet et Sedgewick vers 1985 (source sans mémoire), l’étude a été étendue par Jacquet, Louchard, Szpankowski et Tang à une chaine de Markov). Nous effectuons une telle analyse pour une source générale, en cherchant à étendre d’une part ces travaux fondateurs, et en les intégrant dans le point de vue général qu’a développé l’équipe dans l’étude des tries et des algorithmes de tri et de recherche.

Après avoir rappelé et comparé les trois structures de recherche (dst, bst, trie), et les principaux résultats connus sur leur analyse, j’expliquerai les principaux principes qui conduisent notre analyse.

C’est un travail commun avec Kanal Hun, et débuté avec Philippe Flajolet.