삽입 파이썬

Question

의 서열의 일부가 누락 I는 예를 들어, 두 서열을 가지고

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

파이썬으로 두 서열을 비교하고 는 변경없이 순서 (1)의 누락 부를 삽입하는 것이 가능 나머지 시퀀스 1, 즉, 최종 시퀀스 1은 MATAT--LA-B이어야합니까?

인서트 (I는 I이 부분을 재 삽입 할 ... 서열의 일부를 폐기하는 다중 서열 정렬을 ..)

미리 감사 .. 하나 개 이상의 위치에있을 수 !! !!

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을 획득하여 솔루션 검색을 시작할 것을 제안합니다. Opcode는 difflib.SequenceMatcher.get_opcodes로 생성 할 수 있습니다. 이들은 하나의 시퀀스를 다른 시퀀스로 변환하기 위해 변경해야하는 지시 사항 (삽입, 삭제 또는 바꾸기) 및 시작/중지 인덱스가있는 튜플이됩니다. 그러나 문제는 아마도 SequenceMatcher 알고리즘의 모호함으로 인해 가장 왼쪽의 일치가 항상 자신의 권리와 잠재적 인 일치보다 우선 순위가 높기 때문에 결과가 바람직하지 않을 수 있습니다. 당신은 언제나 자신의 opcodes 핸들러 함수를 디자인 할 수 있습니다. 이 예에서 SequenceMatcher를 사용하여 opcode를 생성하기 전에 두 문자열을 단순히 뒤집어서 결과가 정상적인 opcode로 얻어 질 수 있음을 알았습니다. 그 이유는 가장 오른쪽 일치가 우선되어야하기 때문입니다. 그냥 생각.