File size: 3,771 Bytes
f1ba785
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
"""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]