文字起こしから見どころの候補区間をPythonのスライディングウィンドウで探す方法

文字起こしに単語ごとのタイムスタンプがあれば、長い録画から短いクリップの候補を探すのにモデルはいりません。決まった長さの枠をどの単語からも始めて、中に収まる単語の数で点を付ければ、いちばん多くのことが話されている区間が見つかります。デスクトップアプリ osFoundry の動画エディターは、まさにこれを「クリップを提案」ボタンとしてRustで実装しています（canvas_transcript.rs の find_highlights）。この記事では、それをPythonで組み直して実際の5分7秒のインタビューで動かし、ルールごとの効き方、枠の長さで答えがどう変わるか、上位から貪欲に取る方法が最適でなくなるのはいつか、そして採点を線形時間にする方法を測ります。

入力

使うのは、NASAの宇宙飛行士クリスティーナ・コックさんのインタビューです。Whisperの文字起こしは306.97秒で1,007語、平均すると1秒に3.28語です。このモードのWhisperは句読点なしで単語を返しますが、アルゴリズムが使うのは時刻だけです。

{"words": [
  {"index": 0, "text": "And",   "start_ms": 0,   "end_ms": 160},
  {"index": 1, "text": "we'll", "start_ms": 160, "end_ms": 280},
  {"index": 2, "text": "get",   "start_ms": 280, "end_ms": 380},
  ...
], "duration_ms": 306970}

単語ごとに1つの枠

どの単語も、候補の枠の始まりになります。枠が終わるまでに終わった単語を数え、はみ出した最初の単語で数えるのをやめます。

def candidates(words, window_ms):
    out = []
    for i, w in enumerate(words):
        start = w["start_ms"]
        end = start + window_ms
        n = 0
        for x in words[i:]:
            if x["end_ms"] > end:
                break
            n += 1
        if n:
            out.append((start, end, n))
    return out

1秒ごとのような固定の刻みではなく単語から枠を始めるので、候補は必ず単語の頭から始まり、単語の途中から始まることはありません。点数は実際に話した時間ではなく枠の長さで割るので、クリップの最後の15秒の中から始まる44個の枠は、特別扱いしなくても自然に低い点になります。

このインタビューでは候補が1,007個できます。中央値は49語、最高は67語です。

上から順に、重ならないものだけ取る

候補を点数順に並べ（同点なら位置順にして、何度実行しても同じ結果になるようにします）、すでに選んだ枠と重ならないものを上から取っていきます。

def find_highlights(words, window_ms=15_000, count=3):
    ranked = sorted(candidates(words, window_ms), key=lambda c: (-c[2], c[0]))
    chosen = []
    for c in ranked:
        if len(chosen) >= count:
            break
        if any(c[0] < k[1] and k[0] < c[1] for k in chosen):
            continue  # overlaps a better window
        chosen.append(c)
    return sorted(chosen)

アプリと同じ15秒・3つの設定で動かすと、Python版はアプリの画面に出るのと同じ3つの区間を返します。

区間	単語数	1秒あたりの単語数
0:45.1 – 1:00.1	64	4.27
2:03.4 – 2:18.4	67	4.47
2:31.5 – 2:46.5	65	4.33

効いているのは、重なりを避けるルールです。これがないと上位3つは2:03.4、2:03.6、2:00.2で、3.4秒の範囲に収まる同じ箇所が3回出てきます。話が詰まっている場面はしばらく続くので、良い枠は固まって出ます。実際、上位19個の候補はすべて1:59.7〜2:04.4のあいだから始まっていました。2つ目と3つ目に選ばれたのはランキングの20位と21位で、そこまでに点の高い18個の枠を飛ばしています。2:03.4と2:03.6は同じ67語で並んでいて、位置で同点を決めるルールがここで効きます。

枠の長さで答えが変わる

同じ文字起こしを、ほかの枠の長さで動かした結果です。

枠	選ばれた区間（開始、1秒あたりの単語数）
10秒	0:51.2（4.5）、2:08.5（4.7）、3:15.3（4.5）
15秒	0:45.1（4.27）、2:03.4（4.47）、2:31.5（4.33）
30秒	0:25.1（3.8）、1:48.5（3.93）、2:31.5（3.93）
60秒	0:00.0（3.57）、1:23.7（3.48）、2:31.0（3.77）

短い枠は一瞬の早口に反応して、ピークが高くなります。長い枠は間や質問も平均に含むので、全体の平均の3.28に近づいていきます。2:31あたりの区間は15秒から60秒までのどの長さでも残っていて、一言だけの早口ではなく、まとまった答えであることがうかがえます。長さを2通り試して重なる区間を見るのは、候補を1つの数字以外でも順位づけする手軽な方法です。

上から取るやり方は最適か

いちばん良い枠から取っていくのは貪欲法です。確かめるために、開始時刻順に並べた候補の上で小さな動的計画法を書きます。候補ごとに「飛ばす」か「取って、その終わりより後に始まる最初の候補へ進む」かを選ぶだけです。

import bisect, functools

def best_total(words, window_ms, count):
    cands = sorted(candidates(words, window_ms))
    starts = [c[0] for c in cands]
    nxt = [bisect.bisect_left(starts, c[1]) for c in cands]

    @functools.lru_cache(None)
    def best(i, k):
        if k == 0 or i >= len(cands):
            return 0
        return max(best(i + 1, k), cands[i][2] + best(nxt[i], k - 1))

    return best(0, count)

選んだ枠に入る単語の合計を、貪欲法と厳密解で比べました。

枠 × 個数	上から順に取る	厳密解
15秒 × 3	196語、3区間	196
15秒 × 10	595語、10区間	595
30秒 × 5	563語、5区間	565
30秒 × 10	764語、8区間	989
60秒 × 5	849語、5区間	991

短い枠を少しだけ選ぶ使い方なら、ここでは貪欲法で損はありませんでした。15秒なら、3個、5個、10個のどれでも厳密解と同じ合計です。崩れるのは、枠が録画を埋めはじめたときです。307秒には30秒の枠が10個入りますが、貪欲法は最初の数個をピークの位置に置くので、そのあいだに30秒に満たない隙間が残り、厳密解なら10区間入るところで8区間しか返しません。60秒 × 5でも、同じ理由で142語の差が出ます。「候補を3つ出して」なら貪欲法で十分で、「この講演をチャプターに分けて」なら、数行増えるだけの動的計画法を使うべきです。

採点を線形時間にする

candidates の数え直しは枠ごとに中の単語をすべて読むので、かかる時間は単語数と枠の長さの掛け算で増えます。開始時刻も終了時刻も前にしか進まないので、枠の最後の単語も前にしか進みません。ポインタ1つで足ります。

def candidates_two_pointer(words, window_ms):
    out, j = [], 0
    for i, w in enumerate(words):
        j = max(j, i)
        end = w["start_ms"] + window_ms
        while j < len(words) and words[j]["end_ms"] <= end:
            j += 1
        if j > i:
            out.append((w["start_ms"], end, j - i))
    return out

この文字起こしでは、2つの版はまったく同じ候補を返しました。Apple M1上のPython 3.9で、採点だけを7回測った中央値です。1時間分は、インタビューを12回つなげて作りました。

文字起こし	単語数	数え直し	2ポインタ
5分	1,007	2.9ミリ秒	0.4ミリ秒
1時間	12,084	190.5ミリ秒	5.4ミリ秒

アプリのRustのループは数え直し版です。Pythonで長いポッドキャストを扱ったり、複数の枠の長さを一度に試したりするなら、2ポインタ版を使うほうがいいでしょう。ただし終了時刻が順番に並んでいることが前提です。今回の文字起こしでは全単語で成り立っていましたが、複数のソースを結合した文字起こしでは、assertで確かめておくと落とし穴を避けられます。

点数にわからないこと

1秒あたりの単語数は、どれだけ話したかを測るもので、聞く価値があるかどうかは測りません。アプリのソースでは find_highlights の上のコメントがこれをヒューリスティックだと明言していて、線を引いた理由も書いてあります。見どころをモデルに選ばせるのは別の機能で、お金がかかりキーも必要になる。この機能をこっそりモデル呼び出しに変えれば、無料の操作が、ユーザーが承認していない課金に変わってしまう、というものです。アプリのパネルもユーザーに「判定ではなく、出発点」と伝えています。実際の作業でも、3つの枠は聞き始める場所で、どこで切るかは耳で決めることになります。

ここで測った内容をすべて含むスクリプトは、標準ライブラリだけで約120行です。osFoundryのデスクトップアプリでは、同じ関数が動画エディターの文字起こしパネルの「クリップを提案」ボタンの裏にあり、その手前の文字起こしは自分のクラウドAPIキーで動きます。アプリはosFoundryのダウンロードページから無料で入手できます。