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        let mut word = TimedWord::new(text, w.start_ms, w.end_ms);
121        word.source_ms = w.source_ms;
122        out.push(word);
123    }
124    out
125}
126
127fn chars(s: &str) -> usize {
128    s.chars().count()
129}
130
131/// Width callback & usable text width for deterministic measured line breaking.
132///
133/// `measure_width` receives whole candidate lines, including spaces, in rendered
134/// case. Return widths in the same units as `max_width_px` (normally pixels).
135/// Capture font face & size in the callback; this crate has no font dependency.
136/// The callback should return identical widths for identical text. Errors pass
137/// through [`wrap_lines`] & [`build_cues_with_metrics`] unchanged.
138#[derive(Clone, Copy)]
139pub struct LineMetrics<'a> {
140    pub measure_width: &'a dyn Fn(&str) -> Result<u64, String>,
141    pub max_width_px: u64,
142    /// Measure uppercase text & count its expanded characters without changing
143    /// transcript text or returned display lines.
144    pub uppercase: bool,
145}
146
147impl std::fmt::Debug for LineMetrics<'_> {
148    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
149        f.debug_struct("LineMetrics")
150            .field("max_width_px", &self.max_width_px)
151            .field("uppercase", &self.uppercase)
152            .finish_non_exhaustive()
153    }
154}
155
156impl LineMetrics<'_> {
157    fn width(&self, text: &str) -> Result<u64, String> {
158        if self.uppercase {
159            (self.measure_width)(&text.to_uppercase())
160        } else {
161            (self.measure_width)(text)
162        }
163    }
164}
165
166fn fits(text: &str, max: usize, metrics: Option<&LineMetrics<'_>>) -> Result<bool, String> {
167    let count = if metrics.is_some_and(|m| m.uppercase) {
168        chars(&text.to_uppercase())
169    } else {
170        chars(text)
171    };
172    Ok(count <= max
173        && match metrics {
174            Some(m) => m.width(text)? <= m.max_width_px,
175            None => true,
176        })
177}
178
179/// Wrap whitespace-separated text, preserving case & word order.
180///
181/// With metrics, both character count & measured width must fit. An overlong
182/// word splits at Unicode scalar boundaries; an individual glyph that cannot
183/// fit returns an error. Without metrics, overlong words stay on one line &
184/// character-count wrapping is infallible. Empty text returns no lines.
185/// Wrapping does not change cue timing or word indices.
186pub fn wrap_lines(
187    text: &str,
188    max_chars: usize,
189    metrics: Option<&LineMetrics<'_>>,
190) -> Result<Vec<String>, String> {
191    let mut lines = Vec::new();
192    let mut cur = String::new();
193    for word in text.split_whitespace() {
194        let joined = if cur.is_empty() {
195            word.to_string()
196        } else {
197            format!("{cur} {word}")
198        };
199        if fits(&joined, max_chars, metrics)? {
200            cur = joined;
201            continue;
202        }
203        if !cur.is_empty() {
204            lines.push(std::mem::take(&mut cur));
205        }
206        if metrics.is_none() || fits(word, max_chars, metrics)? {
207            cur = word.to_string();
208            continue;
209        }
210        // An overlong word keeps its timing, but occupies multiple display lines.
211        for c in word.chars() {
212            let joined = format!("{cur}{c}");
213            if !fits(&joined, max_chars, metrics)? {
214                if cur.is_empty() || !fits(&c.to_string(), max_chars, metrics)? {
215                    return Err(format!("caption glyph {c:?} exceeds the safe line width"));
216                }
217                lines.push(std::mem::take(&mut cur));
218            }
219            cur.push(c);
220        }
221    }
222    if !cur.is_empty() {
223        lines.push(cur);
224    }
225    Ok(lines)
226}
227
228fn line_count(
229    group: &[TimedWord],
230    max: usize,
231    metrics: Option<&LineMetrics<'_>>,
232) -> Result<usize, String> {
233    let text = group
234        .iter()
235        .map(|w| w.text.as_str())
236        .collect::<Vec<_>>()
237        .join(" ");
238    Ok(wrap_lines(&text, max, metrics)?.len())
239}
240
241fn text_chars(group: &[TimedWord]) -> usize {
242    group
243        .iter()
244        .map(|w| chars(&w.text) + 1)
245        .sum::<usize>()
246        .saturating_sub(1)
247}
248
249/// Duration of a group, first start to last end, in milliseconds. A reversed span
250/// (end before start) is zero length, as in `group_words`, and an empty group is zero.
251/// Neither can underflow.
252fn span(group: &[TimedWord]) -> u64 {
253    match (group.first(), group.last()) {
254        (Some(first), Some(last)) => last.end_ms.saturating_sub(first.start_ms),
255        _ => 0,
256    }
257}
258
259fn needs_split(
260    group: &[TimedWord],
261    cfg: &CaptionConfig,
262    metrics: Option<&LineMetrics<'_>>,
263) -> Result<bool, String> {
264    if group.len() <= 1 {
265        return Ok(false);
266    }
267    let dur = span(group);
268    if dur > cfg.max_cue_ms {
269        return Ok(true);
270    }
271    if line_count(group, cfg.max_chars_per_line, metrics)? > cfg.max_lines {
272        return Ok(true);
273    }
274    // Judge reading speed against the time the cue will actually be on screen.
275    let shown = dur.max(cfg.min_cue_ms) as f64 / 1000.0;
276    Ok(text_chars(group) as f64 > cfg.max_chars_per_second * shown)
277}
278
279/// Split index (start of the right half): prefers sentence then clause ends
280/// near the middle, then the largest silence, falling back to the character
281/// midpoint.
282fn split_index(group: &[TimedWord]) -> usize {
283    let total = text_chars(group) as i64;
284    let mut best: Option<(i64, i64, usize)> = None; // (punct rank, distance, idx)
285    let mut run = 0i64;
286    for (i, w) in group.iter().enumerate().take(group.len() - 1) {
287        run += chars(&w.text) as i64 + 1;
288        let dist = (run - total / 2).abs();
289        // Punctuation only counts when it leaves a reasonable remainder.
290        let balanced = run * 4 >= total && (total - run) * 4 >= total;
291        let rank = if balanced && sentence_end(&w.text) {
292            0
293        } else if balanced && clause_end(&w.text) {
294            1
295        } else {
296            2
297        };
298        if best.is_none_or(|(r, d, _)| (rank, dist) < (r, d)) {
299            best = Some((rank, dist, i + 1));
300        }
301    }
302    best.map(|b| b.2).unwrap_or(1).clamp(1, group.len() - 1)
303}
304
305fn split_rec(
306    group: Vec<TimedWord>,
307    cfg: &CaptionConfig,
308    metrics: Option<&LineMetrics<'_>>,
309    out: &mut Vec<Vec<TimedWord>>,
310) -> Result<(), String> {
311    if group.is_empty() {
312        return Ok(());
313    }
314    if !needs_split(&group, cfg, metrics)? {
315        out.push(group);
316        return Ok(());
317    }
318    let at = split_index(&group);
319    let mut left = group;
320    let right = left.split_off(at);
321    split_rec(left, cfg, metrics, out)?;
322    split_rec(right, cfg, metrics, out)
323}
324
325fn phrase_groups(words: &[TimedWord], cfg: &CaptionConfig) -> Vec<Vec<TimedWord>> {
326    let mut groups: Vec<Vec<TimedWord>> = Vec::new();
327    for w in words {
328        let new = match groups.last().and_then(|g| g.last()) {
329            None => true,
330            // Mapped words can overlap at cut points: an overlap is no gap.
331            Some(last) => {
332                w.start_ms.saturating_sub(last.end_ms) > cfg.max_gap_ms || sentence_end(&last.text)
333            }
334        };
335        if new {
336            groups.push(vec![w.clone()]);
337        } else {
338            groups.last_mut().unwrap().push(w.clone());
339        }
340    }
341    groups
342}
343
344/// Merges a too-short cue into its neighbour when the pair still fits the
345/// limits, the gap is small and no sentence ends between them.
346fn merge_short(
347    groups: Vec<Vec<TimedWord>>,
348    cfg: &CaptionConfig,
349    metrics: Option<&LineMetrics<'_>>,
350) -> Result<Vec<Vec<TimedWord>>, String> {
351    let mut out: Vec<Vec<TimedWord>> = Vec::new();
352    let mut iter = groups.into_iter().peekable();
353    while let Some(mut cur) = iter.next() {
354        while span(&cur) < cfg.min_cue_ms {
355            let Some(next) = iter.peek() else { break };
356            let gap = next[0].start_ms.saturating_sub(cur.last().unwrap().end_ms);
357            if gap > cfg.max_gap_ms || sentence_end(&cur.last().unwrap().text) {
358                break;
359            }
360            let mut joined = cur.clone();
361            joined.extend(next.iter().cloned());
362            if needs_split(&joined, cfg, metrics)? {
363                break;
364            }
365            cur = joined;
366            iter.next();
367        }
368        // Also fold a short leftover into the previous cue when it fits.
369        if span(&cur) < cfg.min_cue_ms {
370            if let Some(prev) = out.last_mut() {
371                let gap = cur[0].start_ms.saturating_sub(prev.last().unwrap().end_ms);
372                if gap <= cfg.max_gap_ms && !sentence_end(&prev.last().unwrap().text) {
373                    let mut joined = prev.clone();
374                    joined.extend(cur.iter().cloned());
375                    if !needs_split(&joined, cfg, metrics)? {
376                        *prev = joined;
377                        continue;
378                    }
379                }
380            }
381        }
382        out.push(cur);
383    }
384    Ok(out)
385}
386
387/// Breaks a cue's words into display lines: greedy wrap, then for two lines the
388/// balanced break that prefers a clause boundary.
389fn break_lines(
390    group: &[TimedWord],
391    cfg: &CaptionConfig,
392    metrics: Option<&LineMetrics<'_>>,
393) -> Result<Vec<String>, String> {
394    let w: Vec<&str> = group.iter().map(|w| w.text.as_str()).collect();
395    let greedy = wrap_lines(&w.join(" "), cfg.max_chars_per_line, metrics)?;
396    let join = |r: &[usize]| r.iter().map(|&i| w[i]).collect::<Vec<_>>().join(" ");
397    if greedy.len() != 2 || cfg.max_lines < 2 {
398        return Ok(greedy);
399    }
400    let all: Vec<usize> = (0..w.len()).collect();
401    let mut best: Option<((u8, u64), usize)> = None;
402    for k in 1..w.len() {
403        let l = join(&all[..k]);
404        let r = join(&all[k..]);
405        if !fits(&l, cfg.max_chars_per_line, metrics)?
406            || !fits(&r, cfg.max_chars_per_line, metrics)?
407        {
408            continue;
409        }
410        let size = |s: &str| match metrics {
411            Some(m) => m.width(s),
412            None => Ok(chars(s) as u64),
413        };
414        let (left, right) = (size(&l)?, size(&r)?);
415        let diff = left.abs_diff(right);
416        let short = left.min(right);
417        let total = left + right + u64::from(metrics.is_none());
418        let punct = (sentence_end(w[k - 1]) || clause_end(w[k - 1])) && short * 4 >= total;
419        let key = (u8::from(!punct), diff);
420        if best.is_none_or(|(b, _)| key < b) {
421            best = Some((key, k));
422        }
423    }
424    Ok(match best {
425        Some((_, k)) => vec![join(&all[..k]), join(&all[k..])],
426        None => greedy,
427    })
428}
429
430/// Rules for [`group_words`], the lightweight cue grouper for engines whose
431/// words are already clean (no line breaking, no reading-speed limits). Use
432/// [`build_cues`] for caption-grade segmentation.
433#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
434pub struct GroupRules {
435    /// A cue closes once it holds this many words.
436    pub max_words: usize,
437    /// A cue closes once its span reaches this length.
438    pub max_span_ms: u64,
439    /// A gap larger than this between words starts a new cue.
440    pub max_gap_ms: u64,
441    /// Sentence-final punctuation (`.`, `?`, `!`) closes a cue holding at
442    /// least this many words.
443    pub sentence_min_words: usize,
444    /// Cues shorter than this are widened to it (zero-width cues never export).
445    pub min_cue_ms: u64,
446}
447
448impl Default for GroupRules {
449    /// The engine-side defaults `rightkit-asr` has always used: 12 words, 7 s,
450    /// 1 s gap, sentence close from 3 words, 80 ms floor (one encoder frame).
451    fn default() -> Self {
452        Self {
453            max_words: 12,
454            max_span_ms: 7_000,
455            max_gap_ms: 1_000,
456            sentence_min_words: 3,
457            min_cue_ms: 80,
458        }
459    }
460}
461
462fn single_line_cue(
463    text: &str,
464    start_ms: u64,
465    end_ms: u64,
466    first: usize,
467    last: usize,
468    min_cue_ms: u64,
469) -> Cue {
470    Cue {
471        start_ms,
472        end_ms: end_ms.max(start_ms + min_cue_ms),
473        lines: vec![text.trim().to_string()],
474        first_word: first,
475        last_word: last,
476    }
477}
478
479/// Groups words (in order, not re-normalised) into single-line cues by
480/// [`GroupRules`]. `first_word`/`last_word` index the input slice. A cue closes
481/// on sentence-final punctuation (after `sentence_min_words` words), at
482/// `max_words`, at `max_span_ms`, or on a gap over `max_gap_ms`.
483pub fn group_words(words: &[TimedWord], rules: &GroupRules) -> Vec<Cue> {
484    struct Open {
485        text: String,
486        start: u64,
487        end: u64,
488        first: usize,
489        last: usize,
490        count: usize,
491    }
492    let close =
493        |o: &Open| single_line_cue(&o.text, o.start, o.end, o.first, o.last, rules.min_cue_ms);
494    let open = |i: usize, w: &TimedWord| Open {
495        text: w.text.clone(),
496        start: w.start_ms,
497        end: w.end_ms,
498        first: i,
499        last: i,
500        count: 1,
501    };
502    let mut cues = Vec::new();
503    let mut current: Option<Open> = None;
504    for (i, word) in words.iter().enumerate() {
505        match current.as_mut() {
506            Some(c) => {
507                let gap_over = word.start_ms > c.end && word.start_ms - c.end > rules.max_gap_ms;
508                // An inverted word (end before start) is a zero-length span, not an underflow.
509                let span = c.end.saturating_sub(c.start);
510                if gap_over || c.count >= rules.max_words || span >= rules.max_span_ms {
511                    cues.push(close(c));
512                    current = Some(open(i, word));
513                } else {
514                    c.text.push(' ');
515                    c.text.push_str(&word.text);
516                    c.end = word.end_ms;
517                    c.last = i;
518                    c.count += 1;
519                }
520            }
521            None => current = Some(open(i, word)),
522        }
523        if current.as_ref().is_some_and(|c| {
524            c.text.ends_with(['.', '?', '!']) && c.count >= rules.sentence_min_words
525        }) {
526            cues.push(close(&current.take().expect("cue present")));
527        }
528    }
529    if let Some(c) = current {
530        cues.push(close(&c));
531    }
532    cues
533}
534
535/// One single-line cue per span, in order (`first_word == last_word ==` the
536/// span's index), widened to `min_cue_ms`. For callers that already hold cues
537/// as [`TimedWord`] spans (text = cue text) and only need export.
538pub fn cues_from_spans(spans: &[TimedWord], min_cue_ms: u64) -> Vec<Cue> {
539    spans
540        .iter()
541        .enumerate()
542        .map(|(i, s)| single_line_cue(&s.text, s.start_ms, s.end_ms, i, i, min_cue_ms))
543        .collect()
544}
545
546/// Builds non-overlapping cues from output-time words.
547///
548/// Every cue starts at a word start and ends at a word end, except that a cue
549/// shorter than `min_cue_ms` is held on screen up to [`ALIGNMENT_TOLERANCE_MS`]
550/// past its last word (never into the next cue).
551pub fn build_cues(words: &[TimedWord], cfg: &CaptionConfig) -> Vec<Cue> {
552    build_cues_with_metrics(words, cfg, None).expect("character-count layout is infallible")
553}
554
555/// Builds cues using caller-measured widths, or character limits without metrics.
556///
557/// Measured limits apply to splitting, short-cue merging & line balancing.
558/// Character limits remain an upper bound. Returned text keeps input case;
559/// indices refer to [`normalize_words`] output & timings stay on word boundaries
560/// within [`ALIGNMENT_TOLERANCE_MS`]. A single word may occupy more than
561/// `max_lines` when it must split to fit. Measurement & overwide-glyph errors
562/// propagate without returning partial cues.
563pub fn build_cues_with_metrics(
564    words: &[TimedWord],
565    cfg: &CaptionConfig,
566    metrics: Option<&LineMetrics<'_>>,
567) -> Result<Vec<Cue>, String> {
568    let words = normalize_words(words);
569    let mut groups = Vec::new();
570    for phrase in phrase_groups(&words, cfg) {
571        split_rec(phrase, cfg, metrics, &mut groups)?;
572    }
573    let groups = merge_short(groups, cfg, metrics)?;
574
575    // Word index of the start of each group.
576    let mut cues: Vec<Cue> = Vec::with_capacity(groups.len());
577    let mut idx = 0usize;
578    for g in &groups {
579        let first = idx;
580        idx += g.len();
581        cues.push(Cue {
582            start_ms: g[0].start_ms,
583            end_ms: g.last().unwrap().end_ms,
584            lines: break_lines(g, cfg, metrics)?,
585            first_word: first,
586            last_word: idx - 1,
587        });
588    }
589    for i in 0..cues.len() {
590        let next_start = cues.get(i + 1).map(|c| c.start_ms);
591        let c = &mut cues[i];
592        if c.end_ms.saturating_sub(c.start_ms) < cfg.min_cue_ms {
593            let mut end = (c.start_ms + cfg.min_cue_ms).min(c.end_ms + ALIGNMENT_TOLERANCE_MS);
594            if let Some(n) = next_start {
595                end = end.min(n);
596            }
597            c.end_ms = end.max(c.end_ms);
598        }
599    }
600    Ok(cues)
601}