Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 7 Novembre 2000

Arbres Patricia dans le contexte des sources dynamiques

par 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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr