Déterminer la spécificité des expressions régulières

Étant donné les expressions régulières suivantes:

- alice@[az]+\.[az]+ - [az]+@[az]+\.[az]+ - .* 

La chaîne [email protected] correspondra évidemment aux trois expressions régulières. Dans l’application que je développe, nous ne nous intéressons qu’au match le plus spécifique. Dans ce cas, c’est évidemment le premier.
Malheureusement, il semble impossible de le faire. Nous utilisons PCRE et je n’ai trouvé aucun moyen de le faire et une recherche sur Internet n’a pas non plus été fructueuse.
Une solution possible consisterait à conserver les expressions régulières sortingées selon la spécificité décroissante, puis à prendre simplement la première correspondance. Bien entendu, la question suivante serait de savoir comment sortinger le tableau d’expressions régulières. Ce n’est pas une option de donner la responsabilité à l’utilisateur final de s’assurer que le tableau est sortingé. J’espère donc que vous pourrez m’aider ici …

Merci !!

Paul

Voici la solution à ce problème que j’ai développée à partir du document de recherche de Donald Miner, implémenté en Python, pour les règles appliquées aux adresses MAC.

Fondamentalement, la correspondance la plus spécifique provient d’un motif qui n’est pas un sur-ensemble d’un autre motif correspondant. Pour un domaine de problème particulier, vous créez une série de tests (fonctions) qui comparent deux RE et renvoient le sur-ensemble, ou si elles sont orthogonales. Cela vous permet de construire un arbre d’allumettes. Pour une chaîne d’entrée particulière, vous parcourez les modèles de racine et recherchez les correspondances éventuelles. Ensuite, passez par leurs sous-modèles. Si, à un moment quelconque, les motifs orthogonaux correspondent, une erreur est générée.

Installer

 import re class RegexElement: def __init__(self, ssortingng,index): self.ssortingng=ssortingng self.supersets = [] self.subsets = [] self.disjoints = [] self.intersects = [] self.maybes = [] self.precompilation = {} self.comstackd = re.comstack(ssortingng,re.IGNORECASE) self.index = index SUPERSET = object() SUBSET = object() INTERSECT = object() DISJOINT = object() EQUAL = object() 

Les tests

Chaque test prend 2 chaînes (a et b) et tente de déterminer leur relation. Si le test ne peut pas déterminer la relation, None est renvoyé.

SUPERSET signifie a est un sur-ensemble de b . Tous les matchs de b correspondront à a .

SUBSET signifie que b est un sur-ensemble de a .

INTERSECT signifie que certains matchs de a correspondent à b , mais que certains ne correspondent pas et que certains matchs de b ne correspondent pas à a .

DISJOINT signifie qu’aucune correspondance ne sera DISJOINT b .

EQUAL signifie que tous les matches de a correspondent à b et que tous les matchs de b correspondent à a .

  def equal_test(a, b): if a == b: return EQUAL 

Le graphique

  class SubsetGraph(object): def __init__(self, tests): self.regexps = [] self.tests = tests self._dirty = True self._roots = None @property def roots(self): if self._dirty: r = self._roots = [i for i in self.regexps if not i.supersets] return r return self._roots def add_regex(self, new_regex): roots = self.roots new_re = RegexElement(new_regex) for element in roots: self.process(new_re, element) self.regexps.append(new_re) def process(self, new_re, element): relationship = self.compare(new_re, element) if relationship: getattr(self, 'add_' + relationship)(new_re, element) def add_SUPERSET(self, new_re, element): for i in element.subsets: i.supersets.add(new_re) new_re.subsets.add(i) element.supersets.add(new_re) new_re.subsets.add(element) def add_SUBSET(self, new_re, element): for i in element.subsets: self.process(new_re, i) element.subsets.add(new_re) new_re.supersets.add(element) def add_DISJOINT(self, new_re, element): for i in element.subsets: i.disjoints.add(new_re) new_re.disjoints.add(i) new_re.disjoints.add(element) element.disjoints.add(new_re) def add_INTERSECT(self, new_re, element): for i in element.subsets: self.process(new_re, i) new_re.intersects.add(element) element.intersects.add(new_re) def add_EQUAL(self, new_re, element): new_re.supersets = element.supersets.copy() new_re.subsets = element.subsets.copy() new_re.disjoints = element.disjoints.copy() new_re.intersects = element.intersects.copy() def compare(self, a, b): for test in self.tests: result = test(a.ssortingng, b.ssortingng) if result: return result def match(self, text, ssortingct=True): matches = set() self._match(text, self.roots, matches) out = [] for e in matches: for s in e.subsets: if s in matches: break else: out.append(e) if ssortingct and len(out) > 1: for i in out: print(i.ssortingng) raise Exception("Multiple equally specific matches found for " + text) return out def _match(self, text, elements, matches): new_elements = [] for element in elements: m = element.comstackd.match(text) if m: matches.add(element) new_elements.extend(element.subsets) if new_elements: self._match(text, new_elements, matches) 

Usage

 graph = SubsetGraph([equal_test, test_2, test_3, ...]) graph.add_regex("00:11:22:..:..:..") graph.add_regex("..(:..){5,5}" graph.match("00:de:ad:be:ef:00") 

Une version complète utilisable est ici .

Mon instinct me dit que non seulement c’est un problème difficile, à la fois en termes de coût de calcul et de difficulté de mise en œuvre, mais qu’il peut être insoluble de manière réaliste. Considérez les deux expressions régulières suivantes pour accepter la chaîne [email protected]

     alice @ [az] + \. [az] + 
     [az] + @ myprovider.com 

Lequel de ceux-ci est plus spécifique?

Je pense à un problème similaire pour un parsingur d’itinéraires de projets PHP. Après avoir lu les autres réponses et commentaires ici, et également réfléchi au coût que cela implique, je pourrais aller dans une autre direction.

Cependant, une solution serait de sortinger simplement la liste des expressions régulières dans l’ordre de la longueur de sa chaîne.

Ce n’est pas parfait, mais simplement en supprimant les groupes [], ce serait beaucoup plus proche. Sur le premier exemple de la question, voici la liste:

 - alice@[az]+\.[az]+ - [az]+@[az]+\.[az]+ - .* 

Pour cela, après avoir supprimé le contenu de tout groupe []:

 - alice@+\.+ - +@+\.+ - .* 

La même chose vaut pour le deuxième exemple dans une autre réponse, avec les groupes [] complètement supprimés et sortingés par longueur, ceci:

 alice@[az]+\.[az]+ [az][email protected] 

Deviendrait sortingé comme:

 [email protected] alice@+\.+ 

C’est une bonne solution au moins pour moi, si je choisis de l’utiliser. Inconvénient serait la suppression de tous les groupes de [] avant de sortinger et d’appliquer le sorting sur la liste non modifiée de regexes, mais bon – vous ne pouvez pas tout obtenir.