Jérémie Bourdon (GREYC)

Le trie (forme généralisée des arbres digitaux) est une structure de données très utilisée dans de nombreux domaines: algorithmes de recherche sur les mots, compression, hachage dynamique,… Son intérêt et sa construction reposent sur le partitionnement d’un ensemble de mots.

Je présenterai une forme compacte des tries, appelée arbres Patricia, pour lesquels tous les noeuds unaires (qui de ce fait n’interviennent pas dans le partitionnement) sont supprimés. J’étudierai ensuite en moyenne l’occupation en mémoire et le coût d’insertion d’un mot pour cette structure de donnée lorsque les mots sont produits par une source probabiliste quelconque et pour laquelle les dépendances entre les symboles émis peuvent être très importantes.