Peut-on calculer une sorte de distance entre expressions régulières?
L'idée est de mésure de quelle manière deux expressions régulières sont similaires.
6 Réponses :
Il y a quelques mesures que vous pourriez utiliser:
la longueur d'une correspondance valide. Certaines regex ont une taille fixe, une limite supérieure et une limite inférieure. Comparez à quel point leurs longueurs ou leurs longueurs sont similaires.
Les caractères correspondant. Toute regex aura un ensemble de caractères qu'une correspondance peut contenir (peut-être tous les caractères). Comparez l'ensemble des caractères inclus.
Utilisez un grand document et voyez combien de correspondances chaque regex fabrique et combien de ceux-ci sont identiques.
cherchez-vous une équivalence stricte?
+1: Je préfère cette réponse à la top-vote actuelle car vous avez fait une liste très pragmatique de suggestions concrètes facilement mises en œuvre.
Je pense d'abord que vous devez comprendre pour vous-même comment vous voyez une "différence" entre deux expressions. Fondamentalement, définissez une métrique de distance.
En général, il serait très différent de faire. Selon ce que vous devez faire, vous pouvez voir autoriser un caractère différent dans un endroit comme une grande différence. Dans l'autre cas, permettant à un nombre quelconque de caractères conséquents mais les mêmes caractères ne peut pas donner beaucoup de différence.
J'aimerais souligner aussi que normalement quand ils parlent de fonctions de distance, ils les appliquent à ..., eh bien, appelons-les, jetons. Dans notre cas, séquences de caractères. Ce que vous êtes prêt à faire, c'est d'appliquer cette méthode de non pas à ces jetons, mais aux règles, une multitude de jetons correspondra. Je ne suis pas tout à fait sûr qu'il ait un sens.
Néanmoins, je crois que nous pourrions penser à quelque chose, mais pas en général, mais pour un cas particulier et assez restreint. Avez-vous une sorte d'exemple pour nous montrer?
Vous pouvez construire Machines à stations finies déterministes pour les expressions régulières et comparer les transitions . La différence des deux transitions peut ensuite être utilisée pour mesurer la distance de ces expressions régulières.
Peut-être aller à un pas en avant, convertir la machine d'état en une représentation graphique et recherchez l'isomorphisme?
Comment compareriez-vous les deux expressions régulières raisonnablement similaires '\ W + \ D +' et '[A-ZA-Z] {1,63} [1-9] [0-9] {, 3}' Utilisation de cette méthode? Comment pouvez-vous dire si deux états dans différents FSM sont "équivalents" ou "similaires"?
@Noufal Ibrahim: Oui, je voulais dire quelque chose comme ça. Il existe également des algorithmes qui peuvent dire si deux machines à étatières finies sont équivalentes.
@Mark Byers: La question actuelle est de savoir comment mesurer la similitude. Quelle est la même chose est \ w à [a-za-z] , + à {1,63} , \ d à [1-9] et * à {, 3} ?
Oui, je comprends qu'il est difficile de mesurer la similarité, je ne vois tout simplement pas à quoi construire des machines d'État déterministes aident du tout. Quelle est la "différence des deux transitions"? Comment détermineriez-vous que deux états non identiques au milieu de deux FSM différents sont suffisamment équivalents qu'il est logique de mesurer «les distances de leurs transitions»? Comment définiriez-vous une cartographie entre les états de la FSMS? Pourriez-vous s'il vous plaît développer votre réponse? Bien que l'idée semble intéressante, je ne comprends pas comment cela pourrait jamais fonctionner dans la pratique. Connaissez-vous d'un vrai exemple de cela?
Si vous avez deux expressions régulières et que vous avez un ensemble d'entrées d'exemple, vous pouvez essayer de correspondre à chaque entrée contre chaque regex. Pour chaque entrée:
résumer ce score sur toutes les intrants, ce qui vous donnera une «distance» entre les expressions régulières. Cela vous donnera une idée de la fréquence à laquelle deux expressions régulières diffèrent pour une entrée typique. Il sera très lent à calculer si votre exemple d'entrée d'échantillon est grand. Cela ne fonctionnera pas du tout si les deux fegex ne correspondent pas à la quasi-totalité des chaînes aléatoires et que votre entrée attendue est entièrement aléatoire. Par exemple, la regex 'sgjlkwren "et la regex" ueuenwbkaalf "ne correspondent probablement jamais quoi que ce soit s'il est testé sur une entrée aléatoire, cette métrique dirait que la distance entre eux est nulle. Qui pourrait ou pourrait ne pas être ce que vous voulez (probablement pas).
Vous pourriez être en mesure d'analyser la structure de la regex et d'utiliser un échantillonnage aléatoire biaisé pour appuyer délibérément des chaînes qui correspondent plus fréquemment que dans une entrée entièrement aléatoire. Par exemple, si les deux réégalités exigent que la chaîne commence par «FOO», vous pouvez vous assurer que vos entrées de test commencent toujours avec FOO, afin d'éviter de perdre des chaînes de test de temps que vous savez échouera pour les deux.
Ainsi, en conclusion: à moins que vous n'ayez une situation très spécifique avec un ensemble d'entrée restreint et / ou une langue d'expression régulière restreinte, je dirais que ce n'est pas possible. Si vous avez des restrictions à votre contribution et sur l'expression régulière, cela pourrait être possible. Veuillez préciser quelles sont ces restrictions et peut-être que je peux trouver quelque chose de mieux.
Je suppose que vous pouvez calculer un Distance Levenshtein entre les chaînes d'experts régulières. C'est certainement une façon de mesurer une "distance" entre deux chaînes d'expression régulières différentes.
Bien sûr, je pense qu'il est possible que les expressions régulières ne soient pas nécessaires ici du tout et informer la distance de Levenshtein des chaînes "valeur" réelles que les expressions ordinaires seraient autrement appliquées, peut donner un meilleur résultat.
Notez qu'une mesure de distance pour les expressions régulières est quelque chose de totalement différent puis une mesure de distance pour les chaînes. Par exemple. Distance (regex ("A | B"), regex ("B | A") est par définition 0. Et certaines modifications sont beaucoup plus importantes que d'autres. ABCDE peut Soyez similaire à BACDE , seulement deux caractères échangés mais ^ [0-9] est tout à fait différent de [^ 0-9]
Il y a une réponse cachée dans une question antérieure ici sur: Générer des cordes de Regexes . Vous pouvez calculer une mesure de distance (asymétrique) en générant des chaînes utilisant une regex et en vérifiant le nombre de ceux qui correspondent à l'autre regex.
Ceci peut être optimisé en éliminant les préfixes / suffixes partagés. Par exemple. a [0-9] * et A [0-7] * Partagez le préfixe A , afin que vous puissiez calculer la distance entre [0-9] * et [0-7] * à la place.
Qu'est-ce que vous essayez de faire?
Et comment voudriez-vous mesurer cette distance?
@Gumbo: Je suppose que cela fait partie de la question.