Mots-Clés

Algorithmique du texte, séquences ordonnées, Arbre Cartésien, Recherche approchée

Description

On s'intéresse à la recherche de motif dans les séries temporelles (Exemple: électrocardiogrammes, fluctuations boursières, partitions de musique, sismogramme, ...) et, plus largement dans des listes de valeurs numériques.
En particulier, on s'intéressera à la notion d'arbre Cartésien, qui permet d'établir la ressemblance entre deux séries/courbes si les montées et les descentes relatives ont lieu aux mêmes moments, indépendamment des valeurs.
Des solutions algorithmiques efficaces ont déjà été proposées pour résoudre la recherche de motif utilisant les arbres Cartésiens, de façon exacte, c'est à dire en respectant strictement la définition d'arbre Cartésien.
L'objectif de cette thèse est de produire des notions de recherche approchée, c'est à dire où l'on autorisera des différences supplémentaires entre les deux séries, tout en considérant qu'elles se ressemblent tout de même. En effet, selon le contexte, on peut considérer que
- les données peuvent contenir des erreurs de saisies, que ce soit dans les valeurs ou dans l'ordre où elles apparaissent,
- les données peuvent être légèrement bruitées,
- la notion de motif fournie par les arbres Cartésien est trop stricte.
Il convient donc parfois de relâcher certaines contraintes, afin de détecter automatiquement de nouvelles similitudes entre deux séries.
Une fois ces notions proposées, on fournira des solutions algorithmiques efficaces.