Abstract
La recherche de motifs dans une chaîne de caractères se réalise facilement avec un outil tel que grep. Dans cet article, nous considérons un flux d’événements caractérisés par une date de début et de fin. La recherche de motifs dans une telle structure devient alors plus complexe. Afin de réaliser efficacement cette opération, nous proposons une nouvelle structure, appelée DIG-DAG (Directed Interval Graph - Directed Acyclic Graph). Nous montrons comment construire de manière compacte cette structure lorsque le flux est découvert à la volée. Nous expliquons ensuite comment extraire du DIG-DAG les motifs conformes à la requête d’un utilisateur. Enfin, nous illustrons l’utilisation de ces algorithmes sur des traces réelles issues de réseaux GSM. Cet article synthétise deux articles publiés dans CNSM’2018 et MLN’2019.
