Séminaire Algorithmique : « Approximate Cartesian tree matching », Bastien Auvray (LITIS, Univ. Rouen)

Le problème du pattern matching (trouver une ou toutes les occurrences d’un motif dans un texte) est un problème classique en informatique. L’algorithmique du texte propose de nombreuses solutions efficaces lorsque le motif et le texte sont des chaînes de caractères. Procéder à la recherche de motifs dans les séries temporelles se révèle plus délicat, et nécessite d’adapter la notion de motif. Une approche possible est le Cartesian tree matching, où on cherche des séquences qui partagent le même arbre cartésien (i.e.  il existe une relation d’ordre partiel commune entre les éléments des deux séquences). On présentera une version approchée de ce problème ainsi que plusieurs solutions algorithmiques pour le résoudre.