Skip to main content

rightkit_transcript/
segment.rs

1//! Cue segmentation: phrase grouping, splitting, merging, line breaking.
2//!
3//! Donor: CutRight `cutright-captions` (itself ported from `video-media`'s
4//! caption model). Deterministic: identical words + config give identical cues.
5
6use serde::{Deserialize, Serialize};
7
8use crate::align::ALIGNMENT_TOLERANCE_MS;
9use crate::words::TimedWord;
10
11/// Named segmentation profile (replaces CutRight's timeline `Preset`).
12#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
13#[serde(rename_all = "snake_case")]
14pub enum Profile {
15    /// Landscape video (YouTube): 42 chars x 2 lines.
16    Standard,
17    /// Vertical feed (TikTok): 20 chars x 2 lines, short cues.
18    Vertical,
19    /// Reels / square feed: 24 chars x 2 lines.
20    Compact,
21}
22
23/// Per-profile segmentation limits.
24#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
25pub struct CaptionConfig {
26    pub max_chars_per_line: usize,
27    pub max_lines: usize,
28    /// Reading-speed ceiling: characters per second of cue time.
29    pub max_chars_per_second: f64,
30    /// Cues shorter than this are merged with a neighbour when possible, else
31    /// held on screen up to [`ALIGNMENT_TOLERANCE_MS`] into the following gap.
32    pub min_cue_ms: u64,
33    /// A cue never spans longer than this (it splits instead).
34    pub max_cue_ms: u64,
35    /// A gap between words larger than this always starts a new cue.
36    pub max_gap_ms: u64,
37}
38
39impl CaptionConfig {
40    pub fn for_profile(profile: Profile) -> Self {
41        match profile {
42            Profile::Standard => Self {
43                max_chars_per_line: 42,
44                max_lines: 2,
45                max_chars_per_second: 21.0,
46                min_cue_ms: 600,
47                max_cue_ms: 7000,
48                max_gap_ms: 700,
49            },
50            Profile::Vertical => Self {
51                max_chars_per_line: 20,
52                max_lines: 2,
53                max_chars_per_second: 18.0,
54                min_cue_ms: 600,
55                max_cue_ms: 4500,
56                max_gap_ms: 700,
57            },
58            Profile::Compact => Self {
59                max_chars_per_line: 24,
60                max_lines: 2,
61                max_chars_per_second: 18.0,
62                min_cue_ms: 600,
63                max_cue_ms: 4500,
64                max_gap_ms: 700,
65            },
66        }
67    }
68}
69
70impl Default for CaptionConfig {
71    fn default() -> Self {
72        Self::for_profile(Profile::Standard)
73    }
74}
75
76/// One caption cue on the output timeline. Cues never overlap.
77#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
78pub struct Cue {
79    pub start_ms: u64,
80    pub end_ms: u64,
81    /// Display lines (already broken; at most `max_lines` unless a single word
82    /// is longer than a line).
83    pub lines: Vec<String>,
84    /// Index range `[first_word, last_word]` into the normalized word list.
85    pub first_word: usize,
86    pub last_word: usize,
87}
88
89impl Cue {
90    pub fn text(&self) -> String {
91        self.lines.join("\n")
92    }
93}
94
95fn sentence_end(t: &str) -> bool {
96    t.ends_with(['.', '?', '!', '\u{2026}'])
97}
98
99fn clause_end(t: &str) -> bool {
100    t.ends_with([',', ';', ':', '\u{2014}', '\u{2013}'])
101}
102
103/// Trims, drops empty/zero-length words, collapses inner whitespace and clamps
104/// overlaps so each word ends no later than the next starts.
105pub fn normalize_words(words: &[TimedWord]) -> Vec<TimedWord> {
106    let mut out: Vec<TimedWord> = Vec::with_capacity(words.len());
107    for w in words {
108        let text = w.text.split_whitespace().collect::<Vec<_>>().join(" ");
109        if text.is_empty() || w.end_ms <= w.start_ms {
110            continue;
111        }
112        if let Some(prev) = out.last_mut() {
113            if prev.end_ms > w.start_ms {
114                prev.end_ms = w.start_ms;
115                if prev.end_ms <= prev.start_ms {
116                    out.pop();
117                }
118            }
119        }
120        out.push(TimedWord::new(text, w.start_ms, w.end_ms));
121    }
122    out
123}
124
125fn chars(s: &str) -> usize {
126    s.chars().count()
127}
128
129fn greedy_wrap(words: &[&str], max: usize) -> Vec<Vec<usize>> {
130    // Returns word-index ranges per line as index lists (start..end pairs flattened).
131    let mut lines: Vec<Vec<usize>> = Vec::new();
132    let mut cur: Vec<usize> = Vec::new();
133    let mut len = 0usize;
134    for (i, w) in words.iter().enumerate() {
135        let wl = chars(w);
136        if cur.is_empty() {
137            cur.push(i);
138            len = wl;
139        } else if len + 1 + wl <= max {
140            cur.push(i);
141            len += 1 + wl;
142        } else {
143            lines.push(std::mem::take(&mut cur));
144            cur.push(i);
145            len = wl;
146        }
147    }
148    if !cur.is_empty() {
149        lines.push(cur);
150    }
151    lines
152}
153
154fn line_count(group: &[TimedWord], max: usize) -> usize {
155    let w: Vec<&str> = group.iter().map(|w| w.text.as_str()).collect();
156    greedy_wrap(&w, max).len()
157}
158
159fn text_chars(group: &[TimedWord]) -> usize {
160    group
161        .iter()
162        .map(|w| chars(&w.text) + 1)
163        .sum::<usize>()
164        .saturating_sub(1)
165}
166
167/// Duration of a group, first start to last end, in milliseconds. A reversed span
168/// (end before start) is zero length, as in `group_words`, and an empty group is zero.
169/// Neither can underflow.
170fn span(group: &[TimedWord]) -> u64 {
171    match (group.first(), group.last()) {
172        (Some(first), Some(last)) => last.end_ms.saturating_sub(first.start_ms),
173        _ => 0,
174    }
175}
176
177fn needs_split(group: &[TimedWord], cfg: &CaptionConfig) -> bool {
178    if group.len() <= 1 {
179        return false;
180    }
181    let dur = span(group);
182    if dur > cfg.max_cue_ms {
183        return true;
184    }
185    if line_count(group, cfg.max_chars_per_line) > cfg.max_lines {
186        return true;
187    }
188    // Judge reading speed against the time the cue will actually be on screen.
189    let shown = dur.max(cfg.min_cue_ms) as f64 / 1000.0;
190    text_chars(group) as f64 > cfg.max_chars_per_second * shown
191}
192
193/// Split index (start of the right half): prefers sentence then clause ends
194/// near the middle, then the largest silence, falling back to the character
195/// midpoint.
196fn split_index(group: &[TimedWord]) -> usize {
197    let total = text_chars(group) as i64;
198    let mut best: Option<(i64, i64, usize)> = None; // (punct rank, distance, idx)
199    let mut run = 0i64;
200    for (i, w) in group.iter().enumerate().take(group.len() - 1) {
201        run += chars(&w.text) as i64 + 1;
202        let dist = (run - total / 2).abs();
203        // Punctuation only counts when it leaves a reasonable remainder.
204        let balanced = run * 4 >= total && (total - run) * 4 >= total;
205        let rank = if balanced && sentence_end(&w.text) {
206            0
207        } else if balanced && clause_end(&w.text) {
208            1
209        } else {
210            2
211        };
212        if best.is_none_or(|(r, d, _)| (rank, dist) < (r, d)) {
213            best = Some((rank, dist, i + 1));
214        }
215    }
216    best.map(|b| b.2).unwrap_or(1).clamp(1, group.len() - 1)
217}
218
219fn split_rec(group: Vec<TimedWord>, cfg: &CaptionConfig, out: &mut Vec<Vec<TimedWord>>) {
220    if group.is_empty() {
221        return;
222    }
223    if !needs_split(&group, cfg) {
224        out.push(group);
225        return;
226    }
227    let at = split_index(&group);
228    let mut left = group;
229    let right = left.split_off(at);
230    split_rec(left, cfg, out);
231    split_rec(right, cfg, out);
232}
233
234fn phrase_groups(words: &[TimedWord], cfg: &CaptionConfig) -> Vec<Vec<TimedWord>> {
235    let mut groups: Vec<Vec<TimedWord>> = Vec::new();
236    for w in words {
237        let new = match groups.last().and_then(|g| g.last()) {
238            None => true,
239            Some(last) => w.start_ms - last.end_ms > cfg.max_gap_ms || sentence_end(&last.text),
240        };
241        if new {
242            groups.push(vec![w.clone()]);
243        } else {
244            groups.last_mut().unwrap().push(w.clone());
245        }
246    }
247    groups
248}
249
250/// Merges a too-short cue into its neighbour when the pair still fits the
251/// limits, the gap is small and no sentence ends between them.
252fn merge_short(groups: Vec<Vec<TimedWord>>, cfg: &CaptionConfig) -> Vec<Vec<TimedWord>> {
253    let mut out: Vec<Vec<TimedWord>> = Vec::new();
254    let mut iter = groups.into_iter().peekable();
255    while let Some(mut cur) = iter.next() {
256        while span(&cur) < cfg.min_cue_ms {
257            let Some(next) = iter.peek() else { break };
258            let gap = next[0].start_ms - cur.last().unwrap().end_ms;
259            if gap > cfg.max_gap_ms || sentence_end(&cur.last().unwrap().text) {
260                break;
261            }
262            let mut joined = cur.clone();
263            joined.extend(next.iter().cloned());
264            if needs_split(&joined, cfg) {
265                break;
266            }
267            cur = joined;
268            iter.next();
269        }
270        // Also fold a short leftover into the previous cue when it fits.
271        if span(&cur) < cfg.min_cue_ms {
272            if let Some(prev) = out.last_mut() {
273                let gap = cur[0].start_ms - prev.last().unwrap().end_ms;
274                if gap <= cfg.max_gap_ms && !sentence_end(&prev.last().unwrap().text) {
275                    let mut joined = prev.clone();
276                    joined.extend(cur.iter().cloned());
277                    if !needs_split(&joined, cfg) {
278                        *prev = joined;
279                        continue;
280                    }
281                }
282            }
283        }
284        out.push(cur);
285    }
286    out
287}
288
289/// Breaks a cue's words into display lines: greedy wrap, then for two lines the
290/// balanced break that prefers a clause boundary.
291fn break_lines(group: &[TimedWord], cfg: &CaptionConfig) -> Vec<String> {
292    let w: Vec<&str> = group.iter().map(|w| w.text.as_str()).collect();
293    let greedy = greedy_wrap(&w, cfg.max_chars_per_line);
294    let join = |r: &[usize]| r.iter().map(|&i| w[i]).collect::<Vec<_>>().join(" ");
295    if greedy.len() != 2 || cfg.max_lines < 2 {
296        return greedy.iter().map(|l| join(l)).collect();
297    }
298    let all: Vec<usize> = (0..w.len()).collect();
299    let total: usize = all.iter().map(|&i| chars(w[i]) + 1).sum::<usize>() - 1;
300    let mut best: Option<((u8, usize), usize)> = None;
301    for k in 1..w.len() {
302        let l = join(&all[..k]);
303        let r = join(&all[k..]);
304        if chars(&l) > cfg.max_chars_per_line || chars(&r) > cfg.max_chars_per_line {
305            continue;
306        }
307        let diff = chars(&l).abs_diff(chars(&r));
308        let short = chars(&l).min(chars(&r));
309        let punct = (sentence_end(w[k - 1]) || clause_end(w[k - 1])) && short * 4 >= total;
310        let key = (u8::from(!punct), diff);
311        if best.is_none_or(|(b, _)| key < b) {
312            best = Some((key, k));
313        }
314    }
315    match best {
316        Some((_, k)) => vec![join(&all[..k]), join(&all[k..])],
317        None => greedy.iter().map(|l| join(l)).collect(),
318    }
319}
320
321/// Rules for [`group_words`], the lightweight cue grouper for engines whose
322/// words are already clean (no line breaking, no reading-speed limits). Use
323/// [`build_cues`] for caption-grade segmentation.
324#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
325pub struct GroupRules {
326    /// A cue closes once it holds this many words.
327    pub max_words: usize,
328    /// A cue closes once its span reaches this length.
329    pub max_span_ms: u64,
330    /// A gap larger than this between words starts a new cue.
331    pub max_gap_ms: u64,
332    /// Sentence-final punctuation (`.`, `?`, `!`) closes a cue holding at
333    /// least this many words.
334    pub sentence_min_words: usize,
335    /// Cues shorter than this are widened to it (zero-width cues never export).
336    pub min_cue_ms: u64,
337}
338
339impl Default for GroupRules {
340    /// The engine-side defaults `rightkit-asr` has always used: 12 words, 7 s,
341    /// 1 s gap, sentence close from 3 words, 80 ms floor (one encoder frame).
342    fn default() -> Self {
343        Self {
344            max_words: 12,
345            max_span_ms: 7_000,
346            max_gap_ms: 1_000,
347            sentence_min_words: 3,
348            min_cue_ms: 80,
349        }
350    }
351}
352
353fn single_line_cue(
354    text: &str,
355    start_ms: u64,
356    end_ms: u64,
357    first: usize,
358    last: usize,
359    min_cue_ms: u64,
360) -> Cue {
361    Cue {
362        start_ms,
363        end_ms: end_ms.max(start_ms + min_cue_ms),
364        lines: vec![text.trim().to_string()],
365        first_word: first,
366        last_word: last,
367    }
368}
369
370/// Groups words (in order, not re-normalised) into single-line cues by
371/// [`GroupRules`]. `first_word`/`last_word` index the input slice. A cue closes
372/// on sentence-final punctuation (after `sentence_min_words` words), at
373/// `max_words`, at `max_span_ms`, or on a gap over `max_gap_ms`.
374pub fn group_words(words: &[TimedWord], rules: &GroupRules) -> Vec<Cue> {
375    struct Open {
376        text: String,
377        start: u64,
378        end: u64,
379        first: usize,
380        last: usize,
381        count: usize,
382    }
383    let close =
384        |o: &Open| single_line_cue(&o.text, o.start, o.end, o.first, o.last, rules.min_cue_ms);
385    let open = |i: usize, w: &TimedWord| Open {
386        text: w.text.clone(),
387        start: w.start_ms,
388        end: w.end_ms,
389        first: i,
390        last: i,
391        count: 1,
392    };
393    let mut cues = Vec::new();
394    let mut current: Option<Open> = None;
395    for (i, word) in words.iter().enumerate() {
396        match current.as_mut() {
397            Some(c) => {
398                let gap_over = word.start_ms > c.end && word.start_ms - c.end > rules.max_gap_ms;
399                // An inverted word (end before start) is a zero-length span, not an underflow.
400                let span = c.end.saturating_sub(c.start);
401                if gap_over || c.count >= rules.max_words || span >= rules.max_span_ms {
402                    cues.push(close(c));
403                    current = Some(open(i, word));
404                } else {
405                    c.text.push(' ');
406                    c.text.push_str(&word.text);
407                    c.end = word.end_ms;
408                    c.last = i;
409                    c.count += 1;
410                }
411            }
412            None => current = Some(open(i, word)),
413        }
414        if current.as_ref().is_some_and(|c| {
415            c.text.ends_with(['.', '?', '!']) && c.count >= rules.sentence_min_words
416        }) {
417            cues.push(close(&current.take().expect("cue present")));
418        }
419    }
420    if let Some(c) = current {
421        cues.push(close(&c));
422    }
423    cues
424}
425
426/// One single-line cue per span, in order (`first_word == last_word ==` the
427/// span's index), widened to `min_cue_ms`. For callers that already hold cues
428/// as [`TimedWord`] spans (text = cue text) and only need export.
429pub fn cues_from_spans(spans: &[TimedWord], min_cue_ms: u64) -> Vec<Cue> {
430    spans
431        .iter()
432        .enumerate()
433        .map(|(i, s)| single_line_cue(&s.text, s.start_ms, s.end_ms, i, i, min_cue_ms))
434        .collect()
435}
436
437/// Builds non-overlapping cues from output-time words.
438///
439/// Every cue starts at a word start and ends at a word end, except that a cue
440/// shorter than `min_cue_ms` is held on screen up to [`ALIGNMENT_TOLERANCE_MS`]
441/// past its last word (never into the next cue).
442pub fn build_cues(words: &[TimedWord], cfg: &CaptionConfig) -> Vec<Cue> {
443    let words = normalize_words(words);
444    let mut groups = Vec::new();
445    for phrase in phrase_groups(&words, cfg) {
446        split_rec(phrase, cfg, &mut groups);
447    }
448    let groups = merge_short(groups, cfg);
449
450    // Word index of the start of each group.
451    let mut cues: Vec<Cue> = Vec::with_capacity(groups.len());
452    let mut idx = 0usize;
453    for g in &groups {
454        let first = idx;
455        idx += g.len();
456        cues.push(Cue {
457            start_ms: g[0].start_ms,
458            end_ms: g.last().unwrap().end_ms,
459            lines: break_lines(g, cfg),
460            first_word: first,
461            last_word: idx - 1,
462        });
463    }
464    for i in 0..cues.len() {
465        let next_start = cues.get(i + 1).map(|c| c.start_ms);
466        let c = &mut cues[i];
467        if c.end_ms - c.start_ms < cfg.min_cue_ms {
468            let mut end = (c.start_ms + cfg.min_cue_ms).min(c.end_ms + ALIGNMENT_TOLERANCE_MS);
469            if let Some(n) = next_start {
470                end = end.min(n);
471            }
472            c.end_ms = end.max(c.end_ms);
473        }
474    }
475    cues
476}
477
478#[cfg(test)]
479mod tests {
480    use super::*;
481
482    #[test]
483    fn group_words_treats_an_inverted_word_as_zero_length() {
484        // Not normalised input: the first word ends before it starts.
485        let words = [TimedWord::new("a", 500, 100), TimedWord::new("b", 600, 700)];
486        let cues = group_words(&words, &GroupRules::default());
487        assert_eq!(cues.len(), 1, "inverted span must not force a split");
488        assert_eq!(cues[0].start_ms, 500);
489        assert!(cues[0].end_ms >= cues[0].start_ms);
490        assert_eq!(cues[0].lines, vec!["a b".to_string()]);
491
492        let lone = group_words(&[TimedWord::new("x", 900, 10)], &GroupRules::default());
493        assert_eq!(lone.len(), 1);
494        assert_eq!(lone[0].start_ms, 900);
495        assert_eq!(lone[0].end_ms, 900 + GroupRules::default().min_cue_ms);
496    }
497
498    #[test]
499    fn span_of_a_reversed_or_empty_group_is_zero_and_never_underflows() {
500        // Last word ends before the first word starts: zero, not a u64 underflow.
501        let reversed = [TimedWord::new("a", 500, 100), TimedWord::new("b", 600, 200)];
502        assert_eq!(span(&reversed), 0);
503        // Ordinary groups still measure first start to last end.
504        let ordered = [TimedWord::new("a", 100, 300), TimedWord::new("b", 320, 900)];
505        assert_eq!(span(&ordered), 800);
506        assert_eq!(span(&[]), 0);
507    }
508}