#概要
ある文字列text1とtext1の一部を編集した文字列text2があるとします。このときtext1とtext2のどの文字が対応しているのかを見つける関数を作りました。

これは文字数を変えない編集をしているうちは簡単なのですが、文字数が変わる編集を行ったり、同じ文字が複数箇所に登場することを許容し始めるとだんだん難易度が上がります。

文章中の漢字をひらがなに直す、ひらがなをローマ字に直す、プログラムが想定しない不正な文字の並びを削除や修正する、など、文字列の一部または全部を編集して、別の文字列に変換することはよく行われますが、変換してしまったあとで、変換する前の文字列と後の文字列のどこがもともと対応していたのかを知りたくなる機会があったので作りました。
#設定
text1、text2の対応を見つけることが目的です。
ここではtext1とtext2の同じ文字でペアを作ったあとで、残った部分同士でペアを作る作業のことを対応付と定義します。

text1、text2の長さをそれぞれL1、L2とします。
text1, text2の分割と対応する長さNの配列Aを決定することで対応付けができたものとします。
Aのi番目の要素は[s1_i, l1_i, s2_i, l2_i]であり、これはtext1のs1_i文字目から始まる長さl1_iの分割が、text2のs2_i文字目から始まる長さl2_iの分割と対応することを意味します。
なお、text1における一部がtext2で削除されている場合など、text1の分割に対応するものがtext2にない場合があります。text1のi番目の分割に対応する分割がtext2にないとき、l2_i=0とします。逆にtext2のi番目の分割に対応する分割がtext2にないときl1_i=0とします。

変数に与えられる制約は以下のとおりです。

1 <= N <= Lx (x=1,2)
sx_1 = 1 (x=1,2)
sx_i + lx_i + 1 = sx_(i+1) (1<=i<=N-1, x=1,2）
sx_N + lx_N = Lx (x=1,2)

#実装
##レベル1
text1で同じ文字が2回以上登場せず、text1から一部の文字の削除のみでtext2が作られる場合を考えます。
text1を１文字目から順番に見ていき、text2に含まれていればその文字と対応づけて、含まれていなければ削除されたとみなすことで、実装できます。

def findCorrespondance1(text1, text2):
  result = []
  s2 = 0
  for s1,c1 in enumerate(text1):
    if text2[s2] == c1:
      result.append([s1,1,s2,1])
      s2 += 1
    else:
      result.append([s1,1,s2,0])
  return result

text1 = "abcdefg"
text2 = "acdfg"
result = findCorrespondance1(text1,text2)
print(result)
#出力
#[[0, 1, 0, 1],
# [1, 1, 1, 0],
# [2, 1, 1, 1],
# [3, 1, 2, 1],
# [4, 1, 3, 0],
# [5, 1, 3, 1],
# [6, 1, 4, 1]]

確認用に、indexのリストを文字列の対応に変換する関数を作っておきます。

def result2string(result, text1, text2):
  str_result = []
  for s1,l1,s2,l2 in result:
    str_result.append([text1[s1:s1+l1], text2[s2:s2+l2]])
  return str_result

str_result = result2string(result,text1,text2)
print(str_result)
#出力
#[['a', 'a'], ['b', ''], ['c', 'c'], ['d', 'd'], ['e', ''], ['f', 'f'], ['g', 'g']]

##レベル2
text1をtext2に変換する方法として文字の削除だけでなく追加、置換も可能とします。
ただしtext1は同じ文字が2回以上登場せず、かつ、text1にもともと含まれていた文字はtext2に追加できないものとします。

ある文字を削除して、同じ位置に別の文字を追加することは、その文字を置換することと結果的に区別できないので、それは置換とみなすこととします。

def findCorrespondance2(text1, text2):
  result = []
  s1 = 0
  s2 = 0
  cnt = 0
  while s1 < len(text1) or s2 < len(text2) or cnt > 100:
    cnt += 1
    found = False
    for l1 in range(0, len(text1)-s1):
      if text1[s1+l1] in text2[s2:]:
        found = True
        l2 = text2[s2:].index(text1[s1+l1])
        if l1 > 0 or l2 > 0:
          result.append([s1,l1, s2, l2])
          s1 += l1
          s2 += l2
        break
    if found:
      result.append([s1,1,s2,1])
      s1 += 1
      s2 += 1
    else:
      result.append([s1, len(text1)-s1, s2, len(text2)-s2])
      s1 = len(text1)
      s2 = len(text2)
  if s1 < len(text1) or s2 < len(text2):
    result.append([s1, len(text1)-s1, s2, len(text2)-s2])    
  
  return result

text1 = "abcdefghijk"
text2 = "ad123ef4klmn"
result = findCorrespondance2(text1, text2)
print(result)
#[[0, 1, 0, 1], [1, 2, 1, 0], [3, 1, 1, 1], [4, 0, 2, 3], [4, 1, 5, 1], [5, 1, 6, 1], [6, 4, 7, 1], [10, 1, 8, 1], [11, 0, 9, 3]]

str_result = result2string(result,text1,text2)
print(str_result)
#[['a', 'a'], ['bc', ''], ['d', 'd'], ['', '123'], ['e', 'e'], ['f', 'f'], ['ghij', '4'], ['k', 'k'], ['', 'lmn']]

本実装だと「text1は同じ文字が2回以上登場せず、かつ、text1にもともと含まれていた文字はtext2に追加できない」という条件が満たされないとき、(必ずしも間違いではないが）最適とは言えない、結果が出力されます。
例えば、text1に同じ文字が2回以上登場することを許容すると以下のような出力が得られます。

text1 = "abcdefga"
text2 = "bcdefga" #text1の1文字目を削除

result = findCorrespondance2(text1, text2)
str_result = result2string(result,text1,text2)
print(str_result)
#[['', 'bcdefg'], ['a', 'a'], ['bcdefga', '']]

レベル３ではこれの改善を目指します。

#レベル3
レベル2に、以下の条件を加えます

text1、text2に同じ文字が2回以上使われていても良い
text2にtext1に含まれる文字を追加してもよい

この条件を加えることで、対応のさせ方が必ずしも1通りではなくなります。
例えば以下のtext1、text2を考えます。

text1 = "abcdefga"
text2 = "bcdefga"

このとき対応のさせ方はtext2の末尾と対応させる"a"をtext1の先頭の"a"とするか末尾の"a"とするかによって、2通り考えられます。

[['', 'bcdefg'], ['a', 'a'], ['bcdefga', '']]
[['a', ''], ['bcdefga', 'bcdefga']]

感覚的には2のほうが対応付けが上手くできていますので、これを定量的に評価する方法を考えます。
1の['', 'bcdefg']や['bcdefga', '']の対応付けが、2の['a', '']に比べて「大変な変換」をしている感じがします。これは['', 'bcdefg']や['bcdefga', '']の分割同士の編集コスト（text1の分割をtext2の分割に変換するのに必要な文字の削除、追加、置換の回数）が['a', '']より大きいということによって評価できそうです。
ここから各分割同士の編集コストを文章全体に渡って足し合わせた値が最も小さくなるような対応付けを「上手い」対応付けであると定義します。
これを求めるには動的計画法を使えば良さそうです。


def findCorrespondance3(text1, text2):
  memo = {}
  #動的計画法で再帰的に呼び出す関数の定義
  def dp(s1,l1,s2,l2):
    #過去に計算したことがあればその結果を返す
    if (s1,l1,s2,l2) in memo: return memo[(s1,l1,s2,l2)]
    t1, t2 = text1[s1:s1+l1], text2[s2:s2+l2]

    if l1 == 0 and l2 == 0:
      result = [0,[]]
      memo[(s1,l1,s2,l2)] = result
      return [0, []]
    elif l1+l2==1 or (l1*l2==1 and t1!=t2): #1文字ずつ対応付けたい場合
      result = [max(l1,l2),[[s1,l1,s2,l2]]]
      memo[(s1,l1,s2,l2)] = result
      return result
    elif l1*l2==1 and t1==t2:
      result = [0,[[s1,l1,s2,l2]]]
      memo[(s1,l1,s2,l2)] = result
      return result        

    results = []
    for i1 in range(0,l1+1):
      for i2 in range(0,l2+1):
        if i1==0 and i2==0: continue
        if i1==l1 and i2==l2: continue
        #(s1,l1,s2,l2)を仮に(s1,i1,s2,i2)、(s1+i1,l1-i1,s2+i2,l2-i2)という２つの部分に分けたときのscore
        score1, part1 = dp(s1,i1,s2,i2)
        score2, part2 = dp(s1+i1,l1-i1,s2+i2,l2-i2)
        part1 = [v for v in part1] #ハードコピー
        part1.extend(part2)
        results.append((score1+score2, part1))
    #scoreの最も小さいresultを取得
    result = min(results, key=lambda x: x[0])
    memo[(s1,l1,s2,l2)] = result
    return result
  result = dp(0,len(text1),0,len(text2))
  return result[1]

text1 = "abcdefghijk"
text2 = "ad123ef4klmn"
result = findCorrespondance3(text1, text2)
str_result = result2string(result, text1, text2)
print(str_result)
#[['a', 'a'], ['', 'd'], ['b', '1'], ['c', '2'], ['d', '3'], ['e', 'e'], ['f', 'f'], ['g', '4'], ['h', 'k'], ['i', 'l'], ['j', 'm'], ['k', 'n']]

text1 = "abcdefga"
text2 = "bcdefga"
result = findCorrespondance3(text1, text2)
str_result = result2string(result, text1, text2)
print(str_result)
#[['a', ''], ['b', 'b'], ['c', 'c'], ['d', 'd'], ['e', 'e'], ['f', 'f'], ['g', 'g'], ['a', 'a']]

レベル３の条件下ではtext1とtext2の同じ文字が必ず対応するという保証がないため、text1 = "abcdefghijk"とtext2 = "ad123ef4klmn"の対応付けもレベル2と結果が変わっています。
なお、上記では1文字ずつの対応を出力していますが、なるべく長い文字列で対応付けたい場合もあります。
そのときは以下のようにします。

def findCorrespondance3(text1, text2):
  memo = {}
  #動的計画法で再帰的に呼び出す関数の定義
  def dp(s1,l1,s2,l2):
    #過去に計算したことがあればその結果を返す
    if (s1,l1,s2,l2) in memo: return memo[(s1,l1,s2,l2)]
    t1, t2 = text1[s1:s1+l1], text2[s2:s2+l2]

    if l1 == 0 and l2 == 0:
      result = [0,[]]
      memo[(s1,l1,s2,l2)] = result
      return [0, []]
    #elif l1+l2==1 or (l1*l2==1 and t1!=t2): #コメントアウト
    elif l1*l2==0 or len(set(t1)&set(t2))==0: #追加
      result = [max(l1,l2),[[s1,l1,s2,l2]]]
      memo[(s1,l1,s2,l2)] = result
      return result
    #elif l1*l2==1 and t1==t2: #コメントアウト
    elif t1==t2: #追加
      result = [0,[[s1,l1,s2,l2]]]
      memo[(s1,l1,s2,l2)] = result
      return result        

    results = []
    for i1 in range(0,l1+1):
      for i2 in range(0,l2+1):
        if i1==0 and i2==0: continue
        if i1==l1 and i2==l2: continue
        #(s1,l1,s2,l2)を仮に(s1,i1,s2,i2)、(s1+i1,l1-i1,s2+i2,l2-i2)という２つの部分に分けたときのscore
        score1, part1 = dp(s1,i1,s2,i2)
        score2, part2 = dp(s1+i1,l1-i1,s2+i2,l2-i2)
        part1 = [v for v in part1] #ハードコピー
        part1.extend(part2)
        results.append((score1+score2, part1))
    #scoreの最も小さいresultを取得
    #result = min(results, key=lambda x: x[0]) #コメントアウト
    result = min(results, key=lambda x: (x[0], len(x[1]))) #追加
    memo[(s1,l1,s2,l2)] = result
    return result
  result = dp(0,len(text1),0,len(text2))
  return result[1]

text1 = "abcdefghijk"
text2 = "ad123ef4klmn"
result = findCorrespondance3(text1, text2)
str_result = result2string(result, text1, text2)
print(str_result)
#[['a', 'a'], ['', 'd'], ['bcd', '123'], ['ef', 'ef'], ['gh', '4k'], ['ijk', 'lmn']]

text1 = "abcdefga"
text2 = "bcdefga"
result = findCorrespondance3(text1, text2)
str_result = result2string(result, text1, text2)
print(str_result)
#[['a', ''], ['bcdefga', 'bcdefga']]

#レベル4
実際にこうした対応付を考えたくなるケースでは、text1におけるある分割をtext2においてどう変換するかが事前に定義されている場合が結構あります。たとえばアルファベットを数字に規則的に置き換えたい場合や、ひらがなをカタカナに変換したい場合などです。
そこで変換の法則が定義されている場合の対応付けの関数を作ります。
レベル３の関数で、text1の分割を変換法則にしたがって変換したものとtext2の分割の異同を比較するように変更すればよいです。

#convertFuncは変換できないものにはNoneを返すようにしておく
def findCorrespondance4(text1, text2, convertFunc):
  memo = {}
  #動的計画法で再帰的に呼び出す関数の定義
  def dp(s1,l1,s2,l2):
    #過去に計算したことがあればその結果を返す
    if (s1,l1,s2,l2) in memo: return memo[(s1,l1,s2,l2)]
    t1, t2 = text1[s1:s1+l1], text2[s2:s2+l2]
    converted_t1 = convertFunc(t1)
    #変換できない場合(Noneが返った場合）はt1をそのまま使う
    if converted_t1 == None: converted_t1 = t1
    converted_l1 = len(converted_t1)

    if l1 == 0 and l2 == 0:
      result = [0,[]]
      memo[(s1,l1,s2,l2)] = result
      return [0, []]
    elif converted_t1==t2:
      result = [0,[[s1,l1,s2,l2]]]
      memo[(s1,l1,s2,l2)] = result
      return result
    elif converted_t1 != "" and converted_t1 in t2:
      pass
    elif l1*l2 == 0:
      result = [max(l1,l2),[[s1,l1,s2,l2]]]
      memo[(s1,l1,s2,l2)] = result
      return result
    #elif len(set(t1)&set(t2))==0:
    elif l1==1 or l2 == 1: #変換の最小単位で比較する必要があるので(一般的に)こう書く
      result = [max(l1,l2),[[s1,l1,s2,l2]]]
      memo[(s1,l1,s2,l2)] = result
      return result
      
    results = []
    #print(s1,l1,s2,l2)
    for i1 in range(0,l1+1):
      for i2 in range(0,l2+1):
        if i1==0 and i2==0: continue
        if i1==l1 and i2==l2: continue
        #(s1,l1,s2,l2)を仮に(s1,i1,s2,i2)、(s1+i1,l1-i1,s2+i2,l2-i2)という２つの部分に分けたときのscore
        score1, part1 = dp(s1,i1,s2,i2)
        score2, part2 = dp(s1+i1,l1-i1,s2+i2,l2-i2)
        part1 = part1[:] #ハードコピー
        part1.extend(part2)
        results.append((score1+score2, part1))
    #scoreの最も小さいresultを取得
    result = min(results, key=lambda x: (x[0], -len(x[1])))#なるべく細かく対応付け
    #result = min(results, key=lambda x: (x[0], len(x[1]))) #なるべく大きく対応付け
    memo[(s1,l1,s2,l2)] = result
    return result
  result = dp(0,len(text1),0,len(text2))
  return result[1]

#単語が変換表にあれば変換後の文字列を、なければNoneを返す
TABLE = {"ab":"cd", "a":"c", "e":"ag"}
def convertWord(word):
  table = TABLE
  return table.get(word, None)

#文章全体で変換できる単語を変換する関数
def convert(text):
  table = TABLE
  return re.sub('({})'.format('|'.join(map(re.escape, table.keys()))), lambda m: table[m.group()], text)

text1 = "abcdeab"
text2 = convert(text1) #"cdcdagcd"
result = findCorrespondance4(text1, text2, convertWord)
str_result = result2string(result, text1, text2)
print(str_result)
#[['ab', 'cd'], ['c', 'c'], ['d', 'd'], ['e', 'ag'], ['ab', 'cd']]

なおこの関数はtext1やtext2が配列形式で管理されていて、その配列の要素の対応を知りたい場合にも（適切な変換法則が関数として定義されていれば）使えます。
例えばカナ１文字ずつの配列と、一部カナをモーラの単位でまとめた配列の対応を探してみます。

カナ１文字ずつ：["シ","ャ","ー","メ","ゾ","ン"]
モーラ：["シャ","ー","メ","ゾ","ン"]

#テスト用のカナをモーラにするクラス
class KanaToMora:
  def __init__(self):
    #モウラを見つける正規表現を定義
    re1 = "[ウクスツヌフムユルグズヅブプヴ][ァヮィェォ]" #ウ段＋「ァ/ィ/ェ/ォ」
    re2 = "[イキシシニヒミリギジヂビピ][ャュェョ]" #イ段（「イ」を除く）＋「ャ/ュ/ェ/ョ」
    re3 = "[テデ][ィュ]" #「テ/デ」＋「ャ/ィ/ュ/ョ」
    re4 = "[ァ-ヴー]" #カナ１文字
    #2文字1モーラの検出パターン
    self.pattern_multi_kana_mora = "|".join([re1,re2,re3])
    #すべてのモーラの検出パターン
    self.pattern_all_mora = "|".join([re1,re2,re3,re4])  
  #リスト全体が1つのモーラに相当するときのみ変換する
  def toSingleMora(self, kanalist):
    kana = "".join(kanalist)
    if re.fullmatch(self.pattern_multi_kana_mora, kana):
      return [kana]
    else:
      return None
  #リストのうちモーラに変化できる部分を変換する
  def toMora(self, kanalist):
    kana = "".join(kanalist)
    return re.findall(self.pattern_all_mora, kana)

k2m = KanaToMora()    

list1 = ["シ","ャ","ー","メ","ゾ","ン"]
list2 = k2m.toMora(list1) #["シャ","ー","メ","ゾ","ン"]

result = findCorrespondance4(list1, list2, k2m.toSingleMora)
str_result = result2string(result, list1, list2)
print(str_result)
#[[['シ', 'ャ'], ['シャ']], [['ー'], ['ー']], [['メ'], ['メ']], [['ゾ'], ['ゾ']], [['ン'], ['ン']]]

きちんと対応を見つけることができました。

#レベル５
実行してみて気づいたのですが、レベル４はとても時間がかかります。
これは挿入、置換、削除のすべての変換パターンからなる可能性のなかで最適なものをひとつ選ぼうとしているからです。
そこで実用上、妥当な以下の制約を加えることで、高速化を試みます。

事前に規定された変換以外で文字列が変化することはない
- 文字列が変化するような対応が登場した時点でその区間を含む経路の探索を打ち切ることができるようになります。
空文字が1文字以上の文字列に変換されることはない
- 変換によって実質的に文字が追加されたように見えることはあり得ます

これらの制約を考慮したコードは以下になります。

def findCorrespondance5(text1, text2, convertFunc):
  memo = {}
  #動的計画法で再帰的に呼び出す関数の定義
  def dp(s1,l1,s2,l2):
    #過去に計算したことがあればその結果を返す
    if (s1,l1,s2,l2) in memo: return memo[(s1,l1,s2,l2)]

    t1, t2 = text1[s1:s1+l1], text2[s2:s2+l2]
    converted_t1 = convertFunc(t1)

    isZeroCost = False #コスト０で変換できるときのフラグ
    isInfinity = False #コスト無限で変換できるときのフラグ
    isDp = False #DPを再帰的に呼び出すときのフラグ（使っていない)
    
    if memo.get((0,s1,0,s2),[0])[0]==float("inf") or memo.get((s1+l1,len(text1)-s1-l1,s2+l2,len(text2)-s2-l2), [0])==float("inf"):
      isInfinity = True 
    elif l1 == 0 and l2 == 0:
      result = [0,[]]
      memo[(s1,l1,s2,l2)] = result
      return [0, []]
    elif l1 == 0: #l1=0 and l2>0
      isInfinity = True #空文字が非空文字と対応することはないので
    elif l1 == 1: 
      if converted_t1 == None: #1要素を変換できなかったら
        if t1 == t2:
          isZeroCost = True
        else:
          isInfinity = True
      else:
        if converted_t1 == t2:
          isZeroCost = True
        else:
          isInifinty = True
    else: #l1が2以上
      if converted_t1 == None:
        isDp = True #ループでDP計算をする
      else:
        if converted_t1 == t2:
          isZeroCost = True
        else:
          isDp = True
    #フラグが立っていたら値を返す
    if isZeroCost:
      result = [0,[(s1,l1,s2,l2)]]
      memo[(s1,l1,s2,l2)] = result
      return result
    elif isInfinity:
      result = [float("inf"),[(s1,l1,s2,l2)]] #コストを無限大にする
      memo[(s1,l1,s2,l2)] = result
      #もし(s1,l1,s2,l2)が端の区間だったら残りの要素もinfにする
      if s1+s2+l1+l2 == len(text1)+len(text2) and s1+s2 > 0:
        memo[(0,s1,0,s2)]=[float("inf"),[(0,s1,0,s2)]]
      elif s1+s2==0 and l1+l2 < len(text1)+len(text2):
        v = (s1+l1,len(text1)-s1-l1, s2+l2, len(text2)-s2-l2)
        memo[v] = [float("inf"), [v]]
      return result                    
    results = []
    for i1 in range(1,l1): #空文字の変換は考えないので1以上l1-1以下で回す
      for i2 in range(0,l2+1):
        #(s1,l1,s2,l2)を仮に(s1,i1,s2,i2)、(s1+i1,l1-i1,s2+i2,l2-i2)という２つの部分に分けたときのscore
        score1, part1 = dp(s1,i1,s2,i2)
        if score1 == float("inf"): continue  #scoreが無限のときはスキップ
        score2, part2 = dp(s1+i1,l1-i1,s2+i2,l2-i2)
        if score2 == float("inf"): continue  #scoreが無限のときはスキップ
        part1 = part1[:] #値コピー
        part1.extend(part2)
        results.append((score1+score2, part1))
    #resultsが空のときInfinityを返す
    if len(results) == 0:
      result = [float("inf"),[(s1,l1,s2,l2)]] #コストを無限大にする
      memo[(s1,l1,s2,l2)] = result
      if s1+s2+l1+l2 == len(text1)+len(text2) and s1+s2 > 0:
        memo[(0,s1,0,s2)]=[float("inf"),[(0,s1,0,s2)]]
      elif s1+s2==0 and l1+l2 < len(text1)+len(text2):
        v = (s1+l1,len(text1)-s1-l1, s2+l2, len(text2)-s2-l2)
        memo[v] = [float("inf"), [v]]
      return result                    
    else:
      #scoreの最も小さいresultを取得    
      result = min(results, key=lambda x: (x[0], -len(x[1])))#なるべく細かく対応付け
      memo[(s1,l1,s2,l2)] = result
      return result

  result = dp(0,len(text1),0,len(text2))
  #print(result)
  return result[1]

list1 = ["シ","ャ","ー","メ","ゾ","ン"]
list2 = k2m.toMora(list1) #["シャ","ー","メ","ゾ","ン"]

result = findCorrespondance5(list1, list2, k2m.toSingleMora)
str_result = result2string(result, list1, list2)
print(str_result)
#[[['シ', 'ャ'], ['シャ']], [['ー'], ['ー']], [['メ'], ['メ']], [['ゾ'], ['ゾ']], [['ン'], ['ン']]]

レベル４とレベル５で速度を比べてみます。

import time

loop = 1000
list1 = ["シ","ャ","ー","メ","ゾ","ン"]
list2 = k2m.toMora(list1) #["シャ","ー","メ","ゾ","ン"]

start = time.time()
for i in range(loop):
  findCorrespondance4(list1, list2, k2m.toSingleMora)
elapsed_time = time.time() - start
print(elapsed_time,"sec")

start = time.time()
for i in range(loop):
  findCorrespondance5(list1, list2, k2m.toSingleMora)
elapsed_time = time.time() - start
print(elapsed_time,"sec")

出力は以下です。
それなりに程度改善できました（検証は上記コードでしかやっていないので、入力に依存して値が変わることはありえます）

5.1120429039001465 sec #レベル4
0.4900820255279541 sec #レベル5

#おわりに
編集された文字列と、その編集前の文字列を対応付ける方法について、具体的に考えてみました。
アルゴリズム自体に目新しさはないと思いますが、具体的なコードを考えられたので良かったです。

#参考
置換前と後の単語の組合せを辞書管理し、文章の複数単語を一括置換／pythonの.translate()とre.sub() | "BOKU"のITな日常