Extraire les motifs minimaux efficacement et en profondeur
Abstract
Les représentations condensées ont fait l'objet de nombreux travaux
depuis 15 ans. Tandis que les motifs maximaux des classes d'équivalence ont
reçu beaucoup d'attention, les motifs minimaux sont restés dans l'ombre notamment
à cause de la difficulté de leur extraction. Dans ce papier, nous présentons
un cadre générique concernant l'extraction de motifs minimaux en introduisant
la notion de système minimisable d'ensembles. Il permet de considérer des langages
variés comme les motifs ensemblistes ou les chaînes de caractères, mais
aussi différentes métriques dont la fréquence. Ensuite, pour n'importe quel système
minimisable d'ensembles, nous introduisons un test de minimalité rapide
permettant d'extraire en profondeur les motifs minimaux. Nous démontrons que
l'algorithme proposé est polynomial-delay et polynomial-space. Des expérimentations
sur les benchmarks traditionnels complètent notre étude.