Cara mencari klip highlight dari transkrip dengan sliding window di Python

Kalau transkrip sudah punya timestamp per kata, mencari kandidat klip pendek dari rekaman panjang tidak butuh model. Cukup pakai window dengan panjang tetap, mulai satu window di setiap kata, lalu beri skor berdasarkan berapa banyak kata yang muat di dalamnya. Hasilnya adalah bagian-bagian dengan omongan paling padat. Editor video di aplikasi desktop osFoundry memakai cara persis ini untuk tombol Suggest clips, ditulis dalam Rust (find_highlights di canvas_transcript.rs). Di bawah ini algoritmanya dibuat ulang dengan Python dan dijalankan pada wawancara asli berdurasi 5:07, lengkap dengan pengukuran: apa efek tiap aturan, bagaimana panjang window mengubah hasilnya, kapan pemilihan "skor tertinggi dulu" tidak lagi optimal, dan cara membuat tahap penilaiannya linear.

Input

Rekamannya adalah wawancara NASA dengan astronaut Christina Koch. Transkrip Whisper-nya berisi 1,007 kata dalam 306.97 detik, rata-rata 3.28 kata per detik. Dalam mode ini Whisper mengembalikan kata tanpa tanda baca, dan field yang dibutuhkan algoritma hanya waktunya:

{"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}

Satu window per kata

Setiap kata menjadi awal satu window kandidat. Sebuah kata dihitung kalau kata itu selesai sebelum window berakhir, dan pemindaian berhenti di kata pertama yang tidak memenuhi syarat itu:

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

Karena window dimulai dari kata, bukan dari grid tetap (misalnya tiap detik), kandidat selalu dibuka di awal sebuah kata, tidak pernah di tengah kata. Skornya dibagi dengan panjang window, bukan dengan waktu bicara yang sebenarnya, jadi 44 window yang dimulai di 15 detik terakhir klip otomatis mendapat skor rendah tanpa perlu penanganan khusus.

Untuk wawancara ini hasilnya 1,007 kandidat. Mediannya berisi 49 kata, yang terbaik 67.

Skor tertinggi dulu, tanpa tumpang tindih

Kandidat diurutkan berdasarkan skor, dan kalau skornya sama, diurutkan berdasarkan posisi supaya daftar pendeknya selalu sama di setiap run. Lalu kandidat diambil dari atas selama tidak tumpang tindih dengan yang sudah dipilih:

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)

Dengan pengaturan aplikasi, 15 detik dan tiga klip, versi Python mengembalikan tiga rentang yang sama dengan yang ditampilkan aplikasi:

klip	kata	kata/detik
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

Sebagian besar pekerjaan dilakukan oleh aturan tumpang tindih. Tanpa aturan itu, tiga teratas adalah 2:03.4, 2:03.6, dan 2:00.2, bagian yang sama tiga kali, semuanya berjarak tidak lebih dari 3.4 detik satu sama lain. Bagian yang padat biasanya padat untuk beberapa saat, jadi window terbaik cenderung berkumpul: 19 kandidat teratas semuanya dimulai antara 1:59.7 dan 2:04.4. Pilihan kedua dan ketiga adalah kandidat peringkat 20 dan 21, dan 18 window dengan skor lebih tinggi dilewati untuk sampai ke sana. Dua window yang sama-sama bernilai 67 (2:03.4 dan 2:03.6) adalah alasan kenapa tie-break berdasarkan posisi itu penting.

Panjang window mengubah jawabannya

Transkrip yang sama dengan panjang window lain:

window	pilihan (awal, kata/detik)
10 s	0:51.2 (4.5), 2:08.5 (4.7), 3:15.3 (4.5)
15 s	0:45.1 (4.27), 2:03.4 (4.47), 2:31.5 (4.33)
30 s	0:25.1 (3.8), 1:48.5 (3.93), 2:31.5 (3.93)
60 s	0:00.0 (3.57), 1:23.7 (3.48), 2:31.0 (3.77)

Window pendek menguntungkan satu ledakan bicara yang cepat dan menghasilkan puncak yang lebih tinggi. Window panjang ikut merata-ratakan jeda dan pertanyaan, sehingga nilainya bergeser ke arah rata-rata keseluruhan 3.28. Bagian sekitar 2:31 selalu terpilih di setiap panjang dari 15 sampai 60 detik, dan itu tanda yang cukup bagus bahwa bagian tersebut adalah jawaban yang berkelanjutan, bukan sekadar satu kalimat cepat. Menjalankan dua panjang window lalu mencari bagian yang tumpang tindih adalah cara murah untuk meranking kandidat dengan lebih dari satu angka.

Apakah skor tertinggi dulu itu optimal?

Mengambil window terbaik lebih dulu adalah pilihan greedy. Untuk mengeceknya, jawaban yang tepat bisa didapat dengan dynamic programming kecil atas kandidat yang diurutkan berdasarkan waktu mulai: untuk setiap kandidat, lewati, atau ambil lalu lompat ke kandidat pertama yang dimulai setelah kandidat itu selesai.

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)

Total kata di window yang terpilih, greedy dibandingkan jawaban tepat:

window × klip	skor tertinggi dulu	tepat
15 s × 3	196 kata, 3 klip	196
15 s × 10	595 kata, 10 klip	595
30 s × 5	563 kata, 5 klip	565
30 s × 10	764 kata, 8 klip	989
60 s × 5	849 kata, 5 klip	991

Untuk daftar pendek dengan window pendek, greedy di sini tidak rugi apa-apa: di 15 detik hasilnya sama dengan total yang tepat untuk 3, 5, dan 10 klip. Masalahnya muncul ketika window mulai memenuhi seluruh rekaman. Sepuluh window 30 detik muat di 307 detik, tapi greedy menaruh pilihan pertamanya di mana pun puncaknya berada, celah yang tersisa di antaranya lebih pendek dari 30 detik, dan akhirnya hanya mengembalikan 8 klip, padahal jawaban tepat bisa memuat 10. Hal yang sama membuat hilang 142 kata di 60 s × 5. Jadi versi greedy adalah alat yang tepat untuk "kasih saya tiga kandidat", dan alat yang salah untuk "bagi talk ini jadi beberapa chapter", di mana DP hanya butuh beberapa baris tambahan.

Membuat tahap penilaian jadi linear

Pemindaian ulang di candidates membaca setiap kata di setiap window, jadi biayanya tumbuh sebesar panjang window dikali jumlah kata. Karena waktu mulai dan waktu selesai sama-sama hanya bergerak maju, kata terakhir dalam window juga hanya bergerak maju, dan satu pointer sudah cukup:

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

Kedua versi mengembalikan kandidat yang identik pada transkrip ini. Diukur dengan Python 3.9 di Apple M1, median dari 7 run, hanya tahap penilaian, dengan kasus 1 jam dibuat dengan mengulang wawancara 12 kali:

transkrip	kata	pindai ulang	two-pointer
5 min	1,007	2.9 ms	0.4 ms
1 h	12,084	190.5 ms	5.4 ms

Loop Rust di aplikasi memakai versi pindai ulang. Di Python, untuk podcast yang panjang atau beberapa panjang window sekaligus, versi two-pointer yang sebaiknya dipakai. Versi ini memang bergantung pada urutan waktu selesai yang benar. Di sini itu berlaku untuk semua kata, tapi sebaiknya di-assert untuk transkrip yang digabung dari beberapa sumber.

Hal yang tidak diketahui skor

Kata per detik mengukur seberapa banyak yang diucapkan, bukan apakah itu layak didengar. Komentar di atas find_highlights dalam source code aplikasi menyebutnya heuristik dan sengaja menarik garis: model yang memilih highlight akan menjadi fitur yang berbeda, yang memakan biaya dan butuh key, dan diam-diam meng-upgrade fitur ini akan mengubah operasi gratis menjadi tagihan yang tidak pernah disetujui pengguna. Panel di aplikasi mengatakan hal yang sama kepada pengguna, "a starting point, not a verdict" (titik awal, bukan vonis). Dalam praktiknya, tiga window itu adalah tempat untuk mulai mendengarkan, dan titik potongnya tetap ditentukan dengan telinga.

Script lengkapnya, dengan semua pengukuran di atas, sekitar 120 baris Python yang hanya memakai standard library. Di aplikasi desktop osFoundry, fungsi yang sama ada di balik tombol Suggest clips di panel transkrip editor video, di sebelah langkah transkripsi yang berjalan dengan API key cloud milik Anda sendiri. Aplikasinya gratis dari halaman download osFoundry.