Вставка отсутствующие части последовательности в Python

Question

У меня есть две последовательности, например:

Seq 1: MAT--LA-B 
seq 2: MATATLAB 

Возможно ли в Python для сравнения двух последовательностей, а затем вставить недостающую часть в последовательности 1 без изменения остаток последовательности 1, т. е. конечная последовательность 1 должна быть MATAT--LA-B?

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

Заранее спасибо !!

Answer 1

Немного менее общий, чем предыдущий ответ; но это выглядело как интересная проблема, поэтому я решил попробовать в любом случае:

import re 

def find_start_of(needle, haystack): 
    """ 
    @param needle Search on first char of string 
    @param haystack Longer string to search in 

    Look for first char of needle in haystack; return offset 
    """ 

    if needle=='': 
     return 0 

    offs = haystack.find(needle[0]) 
    if offs==-1: 
     return len(haystack) 
    else: 
     return offs 

def find_end_of(lst, letterset): 
    """ 
    @param lst  Chars to search for 
    @param letterset String to search through 

    lst contains some chars of letterset in order; 
    Return offset in letterset of last char of lst 
    """ 

    offs = 0 
    for ch in lst: 
     t = letterset.find(ch, offs) 

     if t==-1: 
      raise ValueError('letterset (%s) is not an ordered superset of lst (%s)' % (letterset, lst)) 
     else: 
      offs = t+1 

    return offs-1 

def alignSeq(s1, s2): 
    """ 
    @param s1 A string consisting of letters and hyphens 
    @param s2 A string containing only letters 

    The letters in s1 are an in-sequence subset of s2 

    Returns s1 with the missing letters from s2 inserted 
    in-sequence and greedily preceding hyphens. 
    """ 

    # break s1 into letter-chunks and hyphen-chunks 
    r = '([^-]*)([-]*)'  # string of letters followed by string of hyphens 
    seq = re.findall(r, s1) # break string into list of tuples 
    seq = seq[:-1]   # discard final empty pair 
    # eg: "MAT--LA-B" becomes [('MAT', '--'), ('LA', '-'), ('B', '')] 

    # find start of corresponding letter-chunks in s2 
    offs = 0 
    chunkstart = [] 
    for letters,hyphens in seq: 
     offs += find_start_of(letters, s2[offs:]) 
     chunkstart.append(offs) 
     offs += find_end_of(letters, s2[offs:]) + 1 

    # get end+1 for each letter-chunk 
    chunkend = chunkstart[1:] + [len(s2)] 
    # get replacement letter-chunks 
    chunks = [s2[st:en] for st,en in zip(chunkstart,chunkend)] 

    # do replacement for each chunk 
    outp = [c+s[1] for c,s in zip(chunks, seq)] 

    return ''.join(outp) 

Тогда

alignSeq('MAT--LA-B','MATATLAB') 

возвращает

'MATAT--LA-B' 

Answer 2

Я предлагаю начать поиск решения, получив opcodes для преобразования одной последовательности в другую. Коды операций могут быть сгенерированы с помощью difflib.SequenceMatcher.get_opcodes. Это будут кортежи с инструкциями (вставка, удаление или замена), а индексы запуска/остановки должны были произойти, чтобы преобразовать одну последовательность в другую. Проблема, скорее всего, в том, что из-за капризов алгоритма SequenceMatcher, самые левые совпадения всегда имеют приоритет над возможными совпадениями по правую сторону, что может привести к нежелательному результату в вашем случае. Вы всегда можете создать собственную функцию обработчика кода. Я замечаю, что в этом примере результат можно получить с помощью обычных кодов операций, просто изменив обе строки перед использованием SequenceMatcher для создания кодов операций, так как для ответа потребуется, чтобы большинство совпадений имели приоритет. Просто мысль.