Генерация регулярного выражения из diff

Question

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

Например, даны 3 строки: f1, f2 и f3

f1:

111xxx222

f2:

111yyy222

f3:

111zzz222

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

111(.*)222

Answer 1

Теперь у вас есть две проблемы .

Вам необходимо тщательно продумать, каков набор возможных строк и каково "правильное" регулярное выражение для каждой входной пары. Я знаю, что сейчас это кажется очевидным, но убедить ваш алгоритм сделать то, что вы ожидаете, может быть сложнее, чем вы думаете. Небольшой 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.

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

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

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

Answer 2

Предполагая, что 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 3

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

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

Answer 4

Библиотека Python std включает в себя модуль 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

Вероятно, есть более хороший способ сделать это, но в 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 это не сработает, если первые две строки имеют разную длину.