Générer une expression régulière à partir de diff

Question

Je cherche un moyen de générer une regex à partir des différences entre deux chaînes d'entrée. L'expression rationnelle peut ensuite être utilisée pour correspondre à la troisième chaîne qui est également similaire aux deux chaînes d'entrée.

Par exemple, avec 3 chaînes: f1, f2 et f3

f1:

111xxx222 

f2:

111yyy222 

f3:

111zzz222 

Je suis se demandant s'il y a une façon générique de générer t oici regex de f1 et f2 qui peut être utilisé pour extraire "zzz" en f3:

111(.*)222 

Answer 1

En supposant que les 2 chaînes sont de longueur égale, avec Perl, vous pouvez faire:

my @x = split//,'111xxx222'; 
my @y = split//,'111yyy222'; 
my $r; 
for my $i(0..$#x) { 
    $r .= $x[$i] eq $y[$i] ? $x[$i] : '.'; 
} 
$r =~ s/(\.+)/($1)/g; 
print $r 

sortie:

111(...)222 

Answer 2

Il y a probablement beaucoup plus agréable façon de le faire, mais, en Python:

import re 

f1 = "111xxx222" 
f2 = "111yyy222" 
f3 = "111zzz222" 

pre = [] 
post = [] 
found_diff = 0 

for i in range(len(f1)): 
    if f1[i] == f2[i]: 
     if found_diff == 0: 
      pre.append(f1[i]) 
     else: 
      post.append(f1[i]) 
    else: 
     found_diff = 1 

regex = "".join(pre) + "(.*)" + "".join(post) 

re.compile(regex) 
print re.match(regex, f3).group(1) 

imprime zzz. NB: cela ne fonctionnera pas si les deux premières chaînes n'ont pas la même longueur.

Answer 3

Now you have two problems.

Vous devez réfléchir sérieusement à l'ensemble des chaînes possibles et quelle est l'expression régulière «correcte» pour chaque paire d'entrées. Je sais que cela vous semble évident en ce moment, mais convaincre votre algorithme de faire ce que vous attendez pourrait être plus difficile que vous ne le pensez. Un petit TDD est toujours une bonne idée: essayez de penser à des cas pathologiques.

Dans votre exemple, pourquoi il ne devrait pas générer quelque chose comme l'un de ceux-ci, au lieu de votre suggestion (voir @ réponse de M42 pour la première) ?:

111(...)222 
111(...*)222 
111(...+)222 
111(..*)222 
111(...?)222 
(.*)111(.*)222(.*) 
etc. 

Que voulez-vous arriver si la troisième chaîne est l'un d'entre eux? Ou le second?

1111zzz222 
111zzz2222 
0111zzz222 
111zzz2223 
111zzzz222 
111zz222 
11zzz222 
111zzz22 
111zzz 
zzz222 
111xyz222 
1z1z1z222 
111222 
1111222 
1112222 
etc. 

Si (comme je le soupçonne) vous savez déjà que certains de ces cas vont être impossible, alors vous savez déjà plus sur la structure possible des chaînes que vous laisser sur. Et si c'est le cas, vous devriez probablement juste analyser les ficelles et l'avoir fait.

Si vous voulez vraiment vraiment essayer de toute façon, alors la première chose à savoir est si vous voulez faire correspondre "longest common subsequence" ou une variation de "longest common substring".

Si vous avez vraiment êtes courir ce contre des chaînes arbitraires, alors une fois que vous pensez que vous avez un bon algorithme, assurez-vous de le tester contre beaucoup des données d'échantillon (qui devrait être assez facile de générer ...

Answer 4

La librairie std lib Python inclut un module diff, difflib. Voici un coup de couteau à votre problème:

>>> import difflib 
>>> f1 = "111xxx222" 
>>> f2 = "111yyy222" 
>>> sm = difflib.SequenceMatcher(a=f1, b=f2) 
>>> diff_re = '' 
>>> for a,b,n in sm.get_matching_blocks(): 
... if not n: continue 
... if diff_re: diff_re += "(.*)" 
... diff_re += f1[a:a+n] 
... 
>>> print diff_re 
'111(.*)222' 

Answer 5

Je pense que cela est un problème très intéressant, surtout si elle est généralisée à quelque chose comme « cordes N données, trouver le plus simple, regex la plus restrictive R qui les correspond ». Dans les données de test fournies, cela donnerait probablement des réponses inutiles comme "111 (xxx | yyy) 222", donc la question devra peut-être être affinée.

Cela ne sonne comme le genre de question compsci pure qui aurait dû avoir un document écrit à ce sujet ...