概要

正解文字列がわかっている場合において、音声認識結果から抽出した発話区間と正解文字列の対応付けを行う方法を実装しました。
以下、長めに続くので、先にコードだけおいておきます。

pip install editdistance

# 編集距離と対応のリストを返す
import editdistance as ed

# 入力: correct_textはタプル、test_segmentsはcorrect_textより１つ次元の多いタプル。correct_textはstrでも可能
# 出力は分割のindexとその分割をした場合の編集距離
def find_correspondance(correct_text, test_segments):
  memo = {}
  def inner_func(correct_text, test_segments):
    memo_key = (correct_text, tuple(test_segments))
    if memo_key in memo:
      return memo[memo_key]

    # 特殊ケースの対応
    if correct_text and not test_segments:
      return len(correct_text), []
    elif not correct_text and test_segments:
      flatten_test_segments = [x for row in test_segments for x in row]
      result = (len(flatten_test_segments), [(0,0) for i in range(len(test_segments))])
      memo[memo_key] = result
      return result
    elif not correct_text and not test_segments:
      return 0, []
    # test_segmentが最後一つのとき、全部を対応させる
    elif correct_text and len(test_segments) == 1:
      dist = ed.eval(correct_text, test_segments[0])
      memo[memo_key] = (dist, [(0, len(correct_text))])
      return dist, [(0, len(correct_text))]
    
    # 全体の編集距離がゼロなら先頭から順番に対応付けすれば良い
    flatten_test_segments = tuple([x for row in test_segments for x in row])
    if correct_text  == flatten_test_segments:
      correspondance = []
      cnt = 0
      for seg in test_segments:
        correspondance.append((cnt, cnt+len(seg)))
        cnt += len(seg)
      memo[memo_key] = (0, correspondance)
      return 0, correspondance

    # プラスマイナスwindow_sizeの幅で最適な対応をみつける
    text = test_segments[0]
      
    results = []
    #window_size = ed.eval(correct_text, "".join(test_segments))
    window_size = 5
    for i in range(2*window_size+1):
      diff = i-window_size
      if len(text) + diff < 0: continue
      head_dist = ed.eval(correct_text[0:len(text)+diff], text)
      head_correspondance = [(0, len(text)+diff)]
      tail_dist, tail_correspondance = inner_func(correct_text[len(text)+diff:], test_segments[1:])
      # indexを最初の対応の長さで補正
      tail_correspondance = [(s+len(text)+diff, e+len(text)+diff) for s,e in tail_correspondance]

      dist = head_dist+tail_dist
      correspondance = head_correspondance + tail_correspondance
      results.append((dist, correspondance))
    #print(min(results, key=lambda x: x[0]))
    min_result = min(results, key=lambda x: x[0])
    memo[memo_key] = min_result
    return min_result
  # correct_textはtupleとして扱う
  if type(correct_text) is str:
    correct_text = tuple(correct_text)
  return inner_func(correct_text, test_segments)

# correspondance(始点終点のindex）を文字列のペアになおして見やすくする
def display_correspondance(correct_text, test_segments, correspondance):
  for test_seg, (start, end) in zip(test_segments, correspondance):
    print("test:", test_seg)
    print("correct:", correct_text[start:end])
    print("")

correct_text = "静むように溶けてゆくように二人だけの空が広がる夜に「さよなら」だけだったその一言で全てが分かった沈み出した空と君の姿フェンス越しに重なっていた初めて会った日から僕の心の全てを奪ったどこか儚い空気を纏う君は寂しい目をしてたんだ"

test_segments = [
 "静むように溶けてゆくように"
, "二人だけの空が白がる夜に"
, "さよなら駆け合ったその一言で全てが分かった"
, "東姫出した空と君の姿 ケウスをしに重なってた"
, "初めてあったしから 僕の心の全てを奪った"
, "どこかはかない空気をなとう君は寂しい目をしてたんだ"
]

dist, correspondance =  find_correspondance(correct_text, test_segments)
print("correct dist:", ed.eval(correct_text, "".join(test_segments)))
print("result dist:", dist)
print("correspondance: ", correspondance)
display_correspondance(correct_text, test_segments, correspondance)

correct dist: 12
result dist: 12
correspondance:  [(0, 13), (13, 25), (25, 47), (47, 70), (70, 89), (89, 114)]
test: 静むように溶けてゆくように
correct: 静むように溶けてゆくように

test: 二人だけの空が白がる夜に
correct: 二人だけの空が広がる夜に

test: さよなら駆け合ったその一言で全てが分かった
correct: 「さよなら駆け合ったその一言で全てが分かった

test: 東姫出した空と君の姿 ケウスをしに重なってた
correct: 沈み出した空と君の姿フェンス越しに重なっていた

test: 初めてあったしから 僕の心の全てを奪った
correct: 初めて会った日から僕の心の全てを奪った

test: どこかはかない空気をなとう君は寂しい目をしてたんだ
correct: どこかはかない空気をなとう君は寂しい目をしてたんだ

背景

正解文字列はすでにわかっていて「フレーズレベルのタイムスタンプだけ知りたい」という需要をみたすために作りました。音楽動画に字幕をつけたいときとか、ままあるケースかと思います。

発話文字列とそのタイムスタンプをえるためには音声認識をすればよいのですが、音声認識結果をそのまま使うとミスも多いので、音声認識結果を正解文字列で修正する、ということをよくやりたくなります。このとき、正解文字列が全文しかない場合、音声認識結果の各フレーズと対応するのは正解文字列のどの部分が対応するかを推測する必要があります。

すぐ思いつくのは先頭から各要素の文字数だけ機械的に対応付ける方法ですが、音声認識結果にミスがあると正解文字列よりも長く認識されたり、短く認識されたりすることもあり、一箇所ずれると以降も全てずれてしまうため、うまくいきません。

そこで、編集距離を指標として、文字列のうまい分割方法を考えます。

問題設定

インプットとアウトプット

正解文字列のデータと、フレーズ単位の音声認識結果が得られているとします。

correct_text = "静むように溶けてゆくように二人だけの空が広がる夜に「さよなら駆け合ったその一言で全てが分かった沈み出した空と君の姿フェンス越しに重なっていた初めて会った日から僕の心の全てを奪ったどこかはかない空気をなとう君は寂しい目をしてたんだ"

test_segments = [
 "静むように溶けてゆくように"
, "二人だけの空が白がる夜に"
, "さよなら駆け合ったその一言で全てが分かった"
, "東姫出した空と君の姿 ケウスをしに重なってた"
, "初めてあったしから 僕の心の全てを奪った"
, "どこかはかない空気をなとう君は寂しい目をしてたんだ"
]

YOASOBI「夜に駆ける」の冒頭歌詞とOpenAIのWhisper baseモデルによる認識結果を検証に用います。ある程度認識間違いがあっても使える実装にしたいので、あえてlargeではなくbaseでやっています。
correct_text, test_segmentsがそれぞれ正解文字列、認識結果です。認識結果の各要素には始点、終点のタイムスタンプが付属していますが、今回の問題設定の範囲では必要ないので省略しています。

correct_textとtest_segmentsを対応付けるとは以下のような結果を得ることを意味します。今はわかりやすいように文字列で表示していますが、実装上はtest_segmentsの各要素に対応するcorrect_textの範囲（始点と終点のindex）が得られればよいです。

test: 静むように溶けてゆくように
correct: 沈むように溶けてゆくように

test: 二人だけの空が白がる夜に
correct: 二人だけの空が広がる夜に「

test: さよなら駆け合ったその一言で全てが分かった
correct: さよなら」だけだったその一言で全てが分かった日が

test: 東姫出した空と君の姿 ケウスをしに重なってた
correct: 沈み出した空と君の姿フェンス越しに重なっていた

test: 初めてあったしから 僕の心の全てを奪った
correct: 初めて会った日から僕の心の全てを奪った

test: どこかはかない空気をなとう君は寂しい目をしてたんだ
correct: どこか儚い空気を纏う君は寂しい目をしてたんだ

目的の定量化

「正しい対応付け」とは何かを考えます。
感覚的には、対応付けされたペアが文章的にある程度近いこと、になります。「ある程度」というのがポイントで音声認識のミスが有ることが前提なので、「完全一致」は難しく、ゆるい一致をうまく定量化する必要があります。
「完全一致ではないけれどある程度近い」をうまく定量化するための便利な概念として「編集距離」があります。
編集距離は「ある文字列を別の文字列に変換するときに必要な置換、削除、挿入の最小回数」と定義されます。編集距離が小さいほど文字列同士が似ていることを意味し、完全一致の場合編集距離はゼロになります。

そこで「編集距離がなるべく小さいとき」に「うまく対応付けている」とみなすことにします。今回は対応付けが必要なsegmentが複数あるので、各segmentのペアの編集距離の合計を最小にすることを目指します。

「もっともうまく対応付けできたとき」の合計編集距離はいくつになるのでしょうか？これはcorrect_text全体とsegmentをjoinした認識結果全体の編集距離と同じになります。
抽象的にいうと文字列A、Bとそれぞれの部分文字列配列[a1, a2] (ただしlen(a1)>0, len(a2)>0, A=a1+a2), [b1,b2]（ただしlen(b1)>0, len(b2)>0, B=b1+b2）があり、文字列x, yの編集距離をED(x,y)と表記するとすると

ED(A,B) <= ED(a1,b1) + ED(a2,b2)

がなりたち、(a1,b1), (a2,b2)がいわゆる「うまい対応付け」になっている場合に等号が成立します。分割数が２より大きい場合も同様です。また等号が成立するような分割は１パターンとは限りませんが、（おそらく）必ず存在します。

上記から問題を定式化すると以下のようになります。

正解文字列Aとそのフレーズ単位の音声認識結果[b1,b2, ..., bn]が与えられたとき

A = a1+a2+...+an
かつ
ED(A, b1+b2+...+bn)=ED(a1,b1)+ED(a2,b2)+...+ED(an,bn)

を満たすAの分割(a1,...,an）を少なくとも１つ求めること

方針

実は２つの文字列の対応付けという類似の問題を過去にといたことがあります。参照記事では２つの文字列だけが与えられるのに対し、今回は文字列と分割が与えられているという違いはあります。が、参照記事のほうが一般的な設定になっているので、参照記事で言うレベル３をそのまま使えば原理的には今回の問題もとけます。最小単位ごとに対応付けてから部分集合に復元すればよいだけです。

ただこの方法は文字数が多いときに時間がかかりすぎてしまうという問題があります。歌詞全体とか長尺のスピーチに適用しようとすると使い物になりません。

そこで「音声認識結果であること」と「間違いが多すぎないこと」という条件を想定することで、計算量を減らすことを考えます。

「間違いが多すぎないこと」という条件は次のように使います。
分割の最初の要素b1が正解文字列Aの何文字目までと対応するかを考えます。もしb1の認識結果に間違いがないのなら、b1の文字列長だけ対応するはずです。しかしもし間違いがあってb1の文字列が正解よりも少なく、あるいは多く認識されていたとしたら、その分Aから短め、あるいは長めに対応付けたほうが望ましいはずです。
b1の認識結果が正しいかどうかは全体を対応付けてみるまではわからないので、b1の文字数より少なく対応付けた場合、ぴったり対応付けた場合、長く対応付けた場合のb2以降の対応付の結果を計算して、どれが全体として最適になっているかを比較すればよいです。
これは愚直にやろうとすると、b1と（Aの）0文字目までを対応付けた場合、1文字目までを対応付けた場合、2文字目、3文字目、、、というようにAの文字列長分の計算を繰り返す必要があるのですが、それをやると計算量が膨大になりすぎます。
そこで「間違いが多すぎないこと」を前提とできるのであれば、せいぜいb1の文字列長付近の狭い範囲だけ比較してもおそらく正解に近い結果はえられるだろうと予想できます。たとえば「b1の認識結果がミスしていて文字数が変わっている影響はせいぜいプラスマイナス5文字程度」ということにしてしまって、len(b1)-5 から len(b1)+5までの範囲だけで比較を行うことにすると、b1に対応するAの範囲を決定するために必要な回数は11回に抑えられます。
これ以外にも間違いが少ないことを前提とした計算量の削減方法はいろいろありそうですが、実装の中で自然に入れられそうだったら入れてみることにします。

「音声認識結果であること」は、b1の誤認識は単語レベルで生じているだろうという過程として使います。誤認識の原因が通信エラーなどだと、1文字ランダムに欠損したりすることも多そうなので、1文字を単位として編集距離を求めたほうが正確だと思うのですが、音声認識の場合は間違うとしたら単語をまるごと間違うケースが主となりそうだと予想します。ここから、文字列を単語列になおして、単語列同士の編集距離を比較することで、計算量を削減することが考えられます。

実装

概要で示したとおりです。
動的計画法で実装しており、メモ化を使って高速化しています。

真ん中あたりでwindow_size=5と定義しているところが「間違いが多くはないこと」を前提としたコードです。5くらいだと歌詞全体でも数秒程度で最適な対応を見つけることができました。window_sizeよりも多い文字数増減をともなう音声認識ミスがあると最適な対応を必ずしも見つけられなくなります。その場合、編集距離の合計が全体一括に対するそれよりも大きくなるので、最適でないこと自体の検出は可能です。最適でない結果が得られたときは、必要に応じてwindow_sizeを大きくすると良いと思います。

なお上記コードでは「音声認識結果であること」の仮定は特に使用していません。しなくてもそれなりに早かったからです。
もし使うとしたらfind_correspondance自体は変更せずに、入力を単語列にすればよいです。
以下のようなコードになります。

import MeCab
mecab = MeCab.Tagger("-Owakati")

correct_text = "静むように溶けてゆくように二人だけの空が広がる夜に「さよなら」だけだったその一言で全てが分かった沈み出した空と君の姿フェンス越しに重なっていた初めて会った日から僕の心の全てを奪ったどこか儚い空気を纏う君は寂しい目をしてたんだ"

test_segments = [
 "静むように溶けてゆくように"
, "二人だけの空が白がる夜に"
, "さよなら駆け合ったその一言で全てが分かった"
, "東姫出した空と君の姿 ケウスをしに重なってた"
, "初めてあったしから 僕の心の全てを奪った"
, "どこかはかない空気をなとう君は寂しい目をしてたんだ"
]

correct_text_wakachi = tuple(mecab.parse(correct_text).split())
test_segments_wakachi = [tuple(mecab.parse(v).split()) for v in test_segments]

dist, correspondance =  find_correspondance(correct_text_wakachi, test_segments_wakachi)
print("correct dist:", ed.eval(correct_text_wakachi, [v for row in test_segments_wakachi for v in row]))
print("result dist:", dist)
print("correspondance: ", correspondance)
display_correspondance(correct_text_wakachi, test_segments_wakachi, correspondance)

correct dist: 17
result dist: 17
correspondance:  [(0, 8), (8, 16), (16, 29), (29, 44), (44, 57), (57, 72)]
test: ('静', 'むよう', 'に', '溶け', 'て', 'ゆく', 'よう', 'に')
correct: ('静', 'むよう', 'に', '溶け', 'て', 'ゆく', 'よう', 'に')

test: ('二人', 'だけ', 'の', '空', 'が', '白', 'がる', '夜', 'に')
correct: ('二人', 'だけ', 'の', '空', 'が', '広がる', '夜', 'に')

test: ('さよなら', '駆け', '合っ', 'た', 'その', '一言', 'で', '全て', 'が', '分かっ', 'た')
correct: ('「', 'さよなら', '」', 'だけ', 'だっ', 'た', 'その', '一言', 'で', '全て', 'が', '分かっ', 'た')

test: ('東', '姫', '出し', 'た', '空', 'と', '君', 'の', '姿', 'ケウス', 'を', 'し', 'に', '重なっ', 'て', 'た')
correct: ('沈み', '出し', 'た', '空', 'と', '君', 'の', '姿', 'フェンス', '越し', 'に', '重なっ', 'て', 'い', 'た')

test: ('初めて', 'あっ', 'た', 'し', 'から', '僕', 'の', '心', 'の', '全て', 'を', '奪っ', 'た')
correct: ('初めて', '会っ', 'た', '日', 'から', '僕', 'の', '心', 'の', '全て', 'を', '奪っ', 'た')

test: ('どこか', 'はかない', '空気', 'を', 'な', 'とう', '君', 'は', '寂しい', '目', 'を', 'し', 'て', 'た', 'ん', 'だ')
correct: ('どこか', '儚い', '空気', 'を', '纏う', '君', 'は', '寂しい', '目', 'を', 'し', 'て', 'た', 'ん', 'だ')

1文字ずつの粒度で扱うと時間がかかりすぎる場合や、最適な結果が出力されなかった場合は、単語列に変換してからwindow_sizeを増やして計算することを試みても良いかもしれません。
また、副次的な効果として、正解文字列が単語の途中で分割されることを防ぐこともできます。応用上は、この効果のほうがメリットが大きい気がしています。

試行錯誤

最初、「先頭の要素から順に最適化していけばよいだけでは？」と思って、そんな感じのコードを書いたりしていました。先頭だけとか、先頭2つの要素を最適化するとか、試していましたが、なんとなくいい感じっぽい結果はでるものの、最適解にはたどり着けませんでした。
この方向性も、window_sizeをしぼるのとは別のメリットがあるような気もするので、メモ（供養）として、のこしておきます。

def find_correspondance(correct_text, test_segments):
  ...

  # プラスマイナス編集距離の幅で最適な対応をみつける
  first_text, second_text = test_segments[0], test_segments[1]
  results = []
  window_size = total_editdistance
  #window_size = 5
  base_dist = ed.eval(correct_text[:len(first_text)], first_text) + ed.eval(correct_text[len(first_text):len(first_text)+len(second_text)], second_text)

  results = [(len(first_text), len(second_text), base_dist)]
  for i in range(1, window_size+1):
    second_end = len(first_text) + len(second_text) + i
    for j in range(1, window_size + 1):
      first_end = len(first_text) + j
      if first_end > second_end: break
      dist = ed.eval(correct_text[:first_end], first_text) + ed.eval(correct_text[first_end: second_end], second_text)
      results.append((first_end, second_end, dist))
    for j in range(1, window_size + 1):
      first_end = len(first_text) - j
      if first_end < 0: break
      dist = ed.eval(correct_text[:first_end], first_text) + ed.eval(correct_text[first_end: second_end], second_text)
      results.append((first_end, second_end, dist))
  
  for i in range(1, window_size + 1):  
    second_end = len(first_text) + len(second_text) - i
    if second_end < 0: break
    for j in range(1, window_size + 1):
      first_end = len(first_text) + j
      if first_end > second_end: break
      dist = ed.eval(correct_text[:first_end], first_text) + ed.eval(correct_text[first_end: second_end], second_text)
      results.append((first_end, second_end, dist))
    for j in range(1, window_size + 1):
      first_end = len(first_text) - j
      if first_end < 0: break
      dist = ed.eval(correct_text[:first_end], first_text) + ed.eval(correct_text[first_end: second_end], second_text)
      results.append((first_end, second_end, dist))

  first_end, _, dist = min(results, key=lambda x: x[-1])
  head_dist = ed.eval(correct_text[:first_end], first_text)
  head_correspondance = [(0, first_end)]

  tail_dist, tail_correspondance = find_correspondance(correct_text[first_end:], test_segments[1:])
  # indexを最初の対応の長さで補正
  tail_correspondance = [(s+first_end, e+first_end) for s,e in tail_correspondance]
  # 最後の対応の終点をcorrect_textの終端にする
  #if tail_correspondance:
  #  tail_correspondance[-1] = (tail_correspondance[-1][0], len(correct_text))
  dist = head_dist+tail_dist
  correspondance = head_correspondance + tail_correspondance

  memo[memo_key] =(dist, correspondance)
  return dist, correspondance

おわりに

表に出ていない試行錯誤は色々ありましたが、無事、音声認識結果と正解文字列の対応付を現実的な時間で実施することができました。
音楽字幕動画をつくるのに活用したいと思います。