Wie man mit einem Sliding Window in Python Highlight-Clips in einem Transkript findet

Sobald ein Transkript Zeitstempel pro Wort hat, braucht man kein Modell, um in einer langen Aufnahme Kandidaten für kurze Clips zu finden. Ein Fenster fester Länge, das bei jedem Wort beginnt und danach bewertet wird, wie viele Wörter hineinpassen, findet die Abschnitte, in denen am meisten gesagt wird. Der Videoeditor in der Desktop-App von osFoundry bringt genau das als Button Suggest clips mit, geschrieben in Rust (find_highlights in canvas_transcript.rs). Unten wird er in Python nachgebaut und auf ein echtes Interview von 5:07 angewendet, mit Messungen dazu, was jede Regel bewirkt, wie die Fensterlänge das Ergebnis verändert, wann die Auswahl nach dem Prinzip „Bestes zuerst“ nicht mehr optimal ist und wie man den Bewertungsdurchlauf linear macht.

Die Eingabe

Die Aufnahme ist ein NASA-Interview mit der Astronautin Christina Koch. Das Whisper-Transkript hat 1.007 Wörter auf 306,97 Sekunden, im Schnitt 3,28 Wörter pro Sekunde. In diesem Modus liefert Whisper die Wörter ohne Satzzeichen, und der Algorithmus braucht ohnehin nur die Zeiten:

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

Ein Fenster pro Wort

Jedes Wort eröffnet ein Kandidatenfenster. Ein Wort zählt, wenn es vor dem Ende des Fensters endet, und die Suche bricht beim ersten Wort ab, auf das das nicht zutrifft:

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

Weil die Fenster an Wörtern beginnen und nicht an einem festen Raster (etwa jede Sekunde), öffnet ein Kandidat immer am Anfang eines Wortes und nie mittendrin. Der Score wird durch die Fensterlänge geteilt, nicht durch die tatsächlich gesprochene Zeit. Die 44 Fenster, die in den letzten 15 Sekunden des Clips beginnen, bekommen dadurch von selbst einen niedrigen Wert, ganz ohne Sonderfall.

Für dieses Interview ergibt das 1.007 Kandidaten. Der Median enthält 49 Wörter, der beste 67.

Bestes zuerst, ohne Überlappung

Die Kandidaten werden nach Score sortiert, Gleichstände nach Position aufgelöst, damit die Auswahl bei jedem Lauf gleich ausfällt, und dann von oben übernommen, solange sie nichts bereits Gewähltes überlappen:

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)

Mit den Einstellungen der App, 15 Sekunden und drei Clips, liefert die Python-Version dieselben drei Bereiche, die auch die App anzeigt:

Clip	Wörter	Wörter/s
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

Die meiste Arbeit leistet die Überlappungsregel. Ohne sie wären die ersten drei 2:03.4, 2:03.6 und 2:00.2, also dreimal dieselbe Passage, alle innerhalb von 3,4 Sekunden. Dichte Sprache bleibt eine Weile dicht, deshalb ballen sich die besten Fenster: Die 19 besten Kandidaten beginnen alle zwischen 1:59.7 und 2:04.4. Die zweite und dritte Auswahl sind die Kandidaten Nummer 20 und 21 im Ranking, und um sie zu erreichen, wurden 18 besser bewertete Fenster übersprungen. Die zwei Fenster mit jeweils 67 Wörtern (2:03.4 und 2:03.6) zeigen, warum der Tie-Break über die Position wichtig ist.

Die Fensterlänge verändert das Ergebnis

Dasselbe Transkript mit anderen Fensterlängen:

Fenster	Auswahl (Start, Wörter/s)
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)

Kurze Fenster belohnen einen einzelnen schnellen Ausbruch und erzeugen höhere Spitzen. Lange Fenster mitteln über Pausen und Fragen und nähern sich der Gesamtrate von 3,28. Der Abschnitt um 2:31 hält sich bei jeder Länge von 15 bis 60 Sekunden, ein ziemlich gutes Zeichen dafür, dass es sich um eine durchgehende Antwort handelt und nicht um einen einzelnen schnellen Satz. Zwei Längen laufen zu lassen und nach der Überschneidung zu suchen, ist eine günstige Methode, die Kandidaten nach mehr als einer Zahl zu ordnen.

Ist „Bestes zuerst“ optimal?

Das beste Fenster zuerst zu nehmen, ist eine Greedy-Entscheidung. Zur Kontrolle lässt sich die exakte Lösung als kleines dynamisches Programm über die nach Startzeit sortierten Kandidaten berechnen: Jeder Kandidat wird entweder übersprungen oder genommen, und dann geht es beim ersten Kandidaten weiter, der nach seinem Ende beginnt.

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)

Gesamtzahl der Wörter in den gewählten Fenstern, Greedy gegen exakt:

Fenster × Clips	Bestes zuerst	exakt
15 s × 3	196 Wörter, 3 Clips	196
15 s × 10	595 Wörter, 10 Clips	595
30 s × 5	563 Wörter, 5 Clips	565
30 s × 10	764 Wörter, 8 Clips	989
60 s × 5	849 Wörter, 5 Clips	991

Bei einer kurzen Auswahl aus kurzen Fenstern verliert Greedy hier nichts: Bei 15 Sekunden traf es für 3, 5 und 10 Clips genau die exakte Summe. Es bricht ein, sobald die Fenster die Aufnahme zu füllen beginnen. Zehn Fenster à 30 Sekunden passen in 307 Sekunden, aber „Bestes zuerst“ setzt die ersten Treffer dorthin, wo die Spitzen liegen, die Lücken dazwischen sind kürzer als 30 Sekunden, und am Ende kommen 8 Clips heraus, wo die exakte Lösung 10 unterbringt. Derselbe Effekt kostet bei 60 s × 5 142 Wörter. Die Greedy-Version ist also das richtige Werkzeug für „gib mir drei Kandidaten“ und das falsche für „teile diesen Vortrag in Kapitel“, wofür das DP nur ein paar Zeilen mehr braucht.

Den Bewertungsdurchlauf linear machen

Die erneute Suche in candidates liest jedes Wort in jedem Fenster, die Kosten wachsen also mit Fensterlänge mal Wortanzahl. Da sich Start- und Endzeiten nur vorwärts bewegen, bewegt sich auch das letzte Wort des Fensters nur vorwärts, und ein einziger Zeiger reicht:

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

Beide Versionen liefern auf diesem Transkript identische Kandidaten. Gemessen mit Python 3.9 auf einem Apple M1, Median aus 7 Läufen, nur die Bewertung; der Fall mit 1 Stunde entsteht, indem das Interview 12-mal wiederholt wird:

Transkript	Wörter	erneute Suche	zwei Zeiger
5 min	1.007	2,9 ms	0,4 ms
1 h	12.084	190,5 ms	5,4 ms

Die Rust-Schleife der App ist die Version mit erneuter Suche. In Python, bei einem langen Podcast oder mit mehreren Fensterlängen gleichzeitig, ist die Zwei-Zeiger-Version die, die man behalten sollte. Sie setzt allerdings voraus, dass die Endzeiten sortiert sind. Das galt hier für jedes Wort, bei Transkripten, die aus mehreren Quellen zusammengeführt wurden, lohnt sich aber ein Assert.

Was der Score nicht weiß

Wörter pro Sekunde messen, wie viel gesagt wird, nicht ob es sich lohnt, zuzuhören. Der Kommentar über find_highlights im Quellcode der App nennt das Verfahren eine Heuristik und zieht die Grenze bewusst: Ein Modell, das Highlights auswählt, wäre eine andere Funktion, eine, die Geld kostet und einen Key braucht, und diese hier stillschweigend aufzuwerten, würde aus einer kostenlosen Operation eine Gebühr machen, der der Nutzer nie zugestimmt hat. Das Panel in der App sagt dem Nutzer dasselbe: „a starting point, not a verdict“ (ein Ausgangspunkt, kein Urteil). In der Praxis heißt das: Die drei Fenster zeigen, wo man mit dem Anhören anfängt, und die Schnittpunkte setzt man weiterhin nach Gehör.

Das vollständige Skript mit allen Messungen oben umfasst etwa 120 Zeilen Python mit reiner Standardbibliothek. In der Desktop-App von osFoundry steckt dieselbe Funktion hinter dem Button Suggest clips im Transkript-Panel des Videoeditors, neben einem Transkriptionsschritt, der mit deinem eigenen Cloud-API-Key läuft. Die App gibt es kostenlos auf der Download-Seite von osFoundry.