Algorithmes d'approximation et randomisés pour le traitement de texte – PARSe

Notre hypothèse de recherche était que les sketches, la randomisation et l’approximation sont essentielles pour des tâches telles que le traitement de données massives et bruitées, pour lesquelles les approches classiques présentent des limites infaisables. Pour examiner cette hypothèse dans toute sa généralité et répondre à nos questions centrales, nous avons organisé notre travail en trois volets : comparaison de chaînes, indexation probabiliste et recherche de motifs en flux.

Le projet a donné lieu à plusieurs publications dans des conférences internationales majeures en informatique théorique, notamment STOC, FOCS, SODA, ICALP et ESA. De plus, deux articles produits dans le cadre du projet ont reçu le prix du Meilleur Article lors de CPM.

Les résultats principaux du projet, étroitement alignés avec les objectifs scientifiques initiaux, incluent les éléments suivants :

1) Le développement d’un algorithme en flux (streaming) pour la recherche approximative de motifs sous distance d’édition.

2) La conception d’algorithmes en flux pour la reconnaissance de langages réguliers, de langages à pile visible (VPL), ainsi que de langages de palindromes et de carrés dans le modèle en streaming.

3) Le développement d’algorithmes à fenêtre glissante pour les langages réguliers, permettant un traitement efficace de flux dynamiquement évolutifs.

4) La conception de structures de données probabilistes pour la recherche dans des dictionnaires avec erreurs (mismatches) et pour des requêtes fondamentales de recherche de motifs.

Au-delà de ses contributions scientifiques, le projet a également soutenu la formation de jeunes chercheurs. Pendant le projet, deux doctorants ont soutenu avec succès leur thèse, tandis qu’une autre thèse est actuellement en voie d’achèvement. Le financement du projet a également permis le recrutement de deux chercheurs postdoctoraux.

Le projet a contribué à l’organisation d’événements scientifiques visant à diffuser les connaissances et à favoriser la collaboration au sein de la communauté :

1) Une école d’été sur la bioinformatique et les algorithmes sur chaînes, organisée en 2023, qui a réuni environ 50 étudiants participants.

2) L’atelier international « New Horizons of Stringology », organisé au CIRM à Marseille en 2024, avec environ 50 participants.

Les résultats de ce projet ouvrent deux directions de recherche prometteuses. La première concerne les algorithmes approximatifs et randomisés pour la reconnaissance de langages formels, essentiels pour traiter efficacement de grands flux de données bruitées et identifier des motifs d’intérêt. La seconde porte sur les techniques de préservation de la vie privée pour le traitement en flux de chaînes et motifs, notamment en garantissant la confidentialité via la confidentialité différentielle tout en maintenant des garanties théoriques sur la précision des algorithmes. Ces deux axes offrent de nombreuses perspectives pour des recherches futures.

Dans ce projet, nous visons à étudier les fondements du traitement de texte à grande échelle. Notre objectif est à comprendre la limite des calculs et à fournir de nouveaux algorithmes et structures de données ultra-efficaces pour le traitement de ces données, inspirés d'approches de hachage et de géométrie à grande dimension. Nous nous concentrerons sur trois axes de recherche : la recherche de motif dans un flot de caractères, l'indexation probabiliste de texte et la comparaison de séquences à base de sketching. Les algorithmes et les structures pour le traitement de texte sont traditionnellement exploités dans des domaines tels que la bioinformatique, la recherche d'information et la sécurité numérique. Nous espérons que notre projet aura un impact significatif sur ces domaines.