"""CTC beam over preselected per-timestep candidates.""" from dataclasses import dataclass import math @dataclass(frozen=True) class BeamDecodeResult: text: str probability: float min_character_probability: float beam_margin: float character_confidences: tuple[float, ...] character_alternatives: tuple[tuple[tuple[str, float], ...], ...] @dataclass(frozen=True) class CtcFrame: candidates: tuple[tuple[int, float], ...] alternatives: tuple[tuple[str, float], ...] margin: float def select_candidates( ranked: list[tuple[int, float]], count: int, blank: int, ) -> list[tuple[int, float]]: selected: list[tuple[int, float]] = [] for index, probability in ranked: if index == blank and len(selected) >= count: continue selected.append((index, probability)) if len(selected) >= count + 1: break return selected def search_ctc_frames( frames: list[CtcFrame], vocabulary: str, beam_width: int = 4, ) -> list[BeamDecodeResult]: blank = len(vocabulary) beams: dict[tuple[str, ...], tuple[float, list[float], list]] = {(): (0.0, [], [])} margin = 1.0 for frame in frames: margin = frame.margin next_beams: dict[tuple[str, ...], tuple[float, list[float], list]] = {} for prefix, (log_prob, confidences, alt_history) in beams.items(): _extend(next_beams, prefix, log_prob, confidences, alt_history, frame, vocabulary, blank) beams = dict(sorted(next_beams.items(), key=lambda item: item[1][0], reverse=True)[:beam_width]) return _results(beams, margin, beam_width) def _extend(next_beams, prefix, log_prob, confidences, alt_history, frame: CtcFrame, vocabulary: str, blank: int) -> None: step_alts = frame.alternatives for index, probability in frame.candidates: if probability <= 0: continue char = vocabulary[index] if index != blank else "" score = log_prob + math.log(max(probability, 1e-9)) history = alt_history + [step_alts] if index == blank: _store(next_beams, prefix, score, confidences + [probability], history) continue if prefix and prefix[-1] == char: _store(next_beams, prefix, score, confidences, history) continue _store(next_beams, prefix + (char,), score, confidences + [probability], history) def _store(next_beams, key, score, confidences, alt_history) -> None: stored = next_beams.get(key) if stored is None or score > stored[0]: next_beams[key] = (score, confidences, alt_history) def _results(beams, margin: float, beam_width: int) -> list[BeamDecodeResult]: results: list[BeamDecodeResult] = [] ranked = sorted(beams.items(), key=lambda item: item[1][0], reverse=True) for prefix, (log_prob, confidences, alt_history) in ranked: if not prefix: continue text = "".join(prefix) selected = confidences[-len(text):] if len(confidences) >= len(text) else confidences if not selected: selected = [math.exp(log_prob / max(len(text), 1))] aligned = list(alt_history[-len(text):]) if alt_history else [] while len(aligned) < len(text): aligned.append(()) results.append(BeamDecodeResult( text=text, probability=sum(selected) / len(selected), min_character_probability=min(selected), beam_margin=margin, character_confidences=tuple(selected[: len(text)]), character_alternatives=tuple(aligned[: len(text)]), )) return results[:beam_width]