Создать регулярное выражение из diff

Question

Я ищу способ генерировать регулярное выражение на основе различий между двумя входными строками. Затем регулярное выражение можно использовать для соответствия третьей строке, которая также аналогична 2 входным строкам.

Например, если три строки: f1, f2 и f3

f1:

111xxx222 

f2:

111yyy222 

f3:

111zzz222 

Я интересно, существует ли общий способ генерации t он следующее регулярное выражение из f1 и f2, которые могут быть использованы для извлечения "ZZZ" в f3:

111(.*)222 

Answer 1

Предполагая, 2 строки имеют одинаковую длину, с Perl вы можете сделать:

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 

выход:

111(...)222 

Answer 2

Там, наверное, гораздо лучше способ сделать это, но, в 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) 

печать zzz.

NB это не сработает, если первые две строки имеют одинаковую длину.

Answer 3

Now you have two problems.

Вам нужно много думать о том, что такое набор возможных строк, и каково правильное регулярное выражение для каждой пары входных данных. Я знаю, что это кажется вам очевидным прямо сейчас, но убедить ваш алгоритм делать то, что вы ожидаете, может быть сложнее, чем вы думаете. Маленькая TDD всегда хорошая идея: попробуйте подумать о некоторых патологических случаях.

В вашем примере, почему она не должна генерировать что-то вроде одного из них, а не ваше предложение (см @ ответ M42 для первого) ?:

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

Что бы вы хотели, если третья строка является одной из них? Или второй?

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

Если (как я подозреваю), вы уже знаете, что некоторые из этих случаев будет невозможно, то вы уже знаете больше о возможной структуре строк, чем вы выпускающих на. И если это так, вы должны просто разобрать строки и сделать.

Если вы действительно действительно хотите попробовать это в любом случае, то первое, что вам нужно выяснить, - это вы хотите совместить «longest common subsequence» или какой-либо вариант «longest common substring».

Если вы действительно являются работает это против произвольных строк, то, как только вы думаете, у вас есть хороший алгоритм, убедитесь, чтобы проверить его против много выборочных данных (которые должны быть довольно легко создавать ...)

Answer 4

Python std lib включает в себя модуль diff, difflib. Вот удар по вашей проблеме:

>>> 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

Я думаю, что это действительно интересная проблема, особенно если это обобщается на что-то вроде «заданных N строк, найти простейший, наиболее ограничительный регулярное выражение R, который соответствует их». В приведенных тестовых данных это, вероятно, даст бесполезные ответы, такие как «111 (xxx | yyy) 222», поэтому вопрос, возможно, потребуется отрегулировать.

Это звучит как вид чистого compsci вопрос, который должен был бы документ, написанный об этом ...