- L’auteur de la
regex crate de Rust a amélioré et optimisé la bibliothèque d’expressions régulières de Rust.
- Une nouvelle crate,
regex-automata, a été créée pour exposer les entrailles de la regex crate via une API distincte.
- C’est la première bibliothèque d’expressions régulières à exposer ainsi ses mécanismes internes dans une bibliothèque publiée séparément.
- Cet article présente le processus de réécriture pour l’améliorer, la manière dont les problèmes ont été résolus, ainsi qu’un guide de l’API de
regex-automata.
- Le public visé est constitué des programmeurs Rust et de toutes les personnes intéressées par la façon d’implémenter un moteur d’expressions régulières à automates finis.
- L’article fournit un bref historique de la
regex crate et de son développement.
- Parmi les problèmes rencontrés par la
regex crate, on trouve la configuration, les tests, certaines demandes d’API et la nécessité d’un DFA entièrement compilé.
- La réécriture résout ces problèmes et fournit une solution plus flexible et mieux optimisée.
- En publiant
regex-automata comme crate distincte, il devient possible d’expérimenter et de développer des API supplémentaires sans rendre la regex crate principale confuse.
- L’article met en avant les avantages de l’utilisation de
regex-automata et les améliorations potentielles possibles dans le domaine des moteurs d’expressions régulières.
- L’article décrit le programme
regex-cli, qui fournit un accès en ligne de commande à l’API de la regex crate.
- Ce programme comprend des utilitaires permettant notamment de sérialiser un DFA compilé dans un fichier et de générer du code Rust.
- L’article montre des exemples de l’impact d’Unicode sur les motifs d’expressions régulières.
- Le programme
regex-cli peut déboguer et afficher divers types de données de l’écosystème de la regex crate.
- Il existe une commande
regex-cli find qui permet d’exécuter des recherches multi-motifs à l’aide de groupes de capture.
- L’article explique le flux de données dans le moteur d’expressions régulières, depuis l’analyse du motif jusqu’à la construction du NFA.
- L’extraction de littéraux est une technique d’optimisation importante utilisée dans la
regex crate.
- L’extraction de littéraux consiste à extraire des littéraux d’un motif d’expression régulière afin d’identifier rapidement les correspondances candidates dans le texte cible.
- Le choix des littéraux à rechercher est important pour minimiser les faux positifs et réduire la latence.
- L’extraction de littéraux est un processus heuristique visant à minimiser les faux positifs et l’impact sur la latence.
- Les recommandations pour l’extraction de littéraux consistent à privilégier les littéraux plus longs et à éviter ceux qui sont extrêmement courts ou trop courants.
- L’article décrit l’optimisation des séquences de littéraux dans les expressions régulières.
- Une séquence de littéraux est une suite de chaînes traitées comme des correspondances exactes.
- Au cours du processus d’optimisation, on identifie les séquences qui peuvent être rendues infinies afin d’améliorer les performances.
- L’article explique comment différentes expressions régulières peuvent produire différentes séquences de littéraux.
- L’article discute également du processus de recherche de littéraux dans le texte cible.
- Des algorithmes différents sont utilisés pour la recherche d’une seule sous-chaîne et pour la recherche de plusieurs sous-chaînes.
- L’article introduit le concept de NFA (automates finis non déterministes) et leur rôle dans les moteurs d’expressions régulières.
- Les NFA peuvent être convertis en d’autres types, par exemple pour implémenter des DFA (automates finis déterministes).
- L’article fournit et explique des exemples détaillés des composants d’un NFA.
- L’article mentionne une optimisation dans le nouveau compilateur NFA qui réduit l’utilisation des transitions epsilon.
- Le nouveau compilateur NFA optimise la représentation du NFA en utilisant des états creux couvrant plusieurs plages d’octets.
- Cette optimisation réduit le surcoût et élimine la nécessité de transitions epsilon.
- Le NFA orienté octets utilisé dans l’ancien compilateur était lent et nécessitait une compilation séparée pour le NFA orienté Unicode et celui orienté octets.
- Le nouveau compilateur NFA gère les classes Unicode en intégrant un automate UTF-8 dans le NFA orienté octets.
- Le nouveau compilateur utilise l’algorithme de Daciuk pour calculer des DFA minimaux à partir de séquences triées d’éléments non imbriqués.
- Les transitions inverses sont gérées à l’aide d’une structure de données spéciale appelée
range trie.
- Le nouveau compilateur NFA génère, par rapport à l’ancien, des NFA avec moins d’états et sans transitions epsilon.
- L’optimisation de réduction inverse peut encore diminuer la taille du NFA, mais au prix d’un temps de construction plus long.
- Dans l’ensemble, le nouveau compilateur NFA améliore les performances et simplifie la gestion des classes Unicode dans les expressions régulières.
- L’article aborde des questions techniques liées à l’encodage des caractères.
- Le problème concerne les caractères rares et leur représentation dans différents formats d’encodage.
- L’article mentionne certains caractères spécifiques et leur fréquence dans leurs encodages respectifs.
- Il met en évidence la complexité de l’encodage des caractères et les défis potentiels qu’il pose.
- Cet article peut intéresser les ingénieurs logiciel et les développeurs qui travaillent avec l’encodage des caractères.
- L’article traite de techniques d’optimisation du NFA dans les moteurs d’expressions régulières.
- Le NFA de Thompson est connu pour mal passer à l’échelle en raison des transitions epsilon.
- L’article présente une optimisation du NFA qui réduit les transitions epsilon en limitant l’alternance de littéraux.
- Le nouveau compilateur NFA construit un trie de littéraux et le transforme en NFA avec un nombre minimal de transitions epsilon.
- Cette optimisation préserve la priorité la plus à gauche et améliore les performances de recherche.
- L’article évoque également des travaux futurs sur le NFA de Glushkov et sur le stockage d’un NFA dans une allocation contiguë unique.
- La
regex crate de Rust utilise plusieurs moteurs regex afin d’équilibrer les fonctionnalités et les performances de recherche.
- PikeVM est le moteur regex le plus puissant de la crate et prend en charge toutes les fonctionnalités regex.
- PikeVM simule le NFA
1 commentaires
Avis Hacker News
regexde Rust est légendaire et constitue un outil précieux pour la communauté.regex.regex-automataest compatible avec toutes les structures de données textuelles.