RNTI

MODULAD
Extraire les motifs minimaux efficacement et en profondeur
In EGC 2014, vol. RNTI-E-26, pp.383-394
Résumé
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.