挿入パイソン

Question

シーケンスの一部を欠落Iは、例えば、二つの配列を有する：

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アルゴリズムのばらつきのために、一番左のマッチが常に自分の右のマッチよりも優先され、あなたのケースで望ましくない結果をもたらす可能性があります。独自のopcodesハンドラ関数を常に設計できます。この例では、SequenceMatcherを使用してオペコードを生成する前に、両方の文字列を単に逆順にするだけで、通常のオペコードで結果を得ることができます。これは、最も右の一致が優先される必要があるためです。ちょっとした考え。