Initial release of Notesoop-STT-Ko-v1 (Private)

36deb53 verified 4 days ago

13.7 kB

"""
src/decoder.py
Production On-Device CTC Beam Search Decoder with KenLM Language Model Rescoring.
Integrates Korean Morpheme Tokenizer, Trie N-Gram language model, and contraction rules.
"""

from __future__ import annotations

import math
import ctypes
from pathlib import Path
from typing import List, Dict, Tuple, Optional, Any

import numpy as np
import torch
import torch.nn.functional as F

try:
    import kenlm
except ImportError:
    kenlm = None

from dataset import KoreanMorphemeTokenizer, normalize_text

# CTC Beam Search Engine with KenLM Language Model
_FAST_BEAM_LIB = None


def _log_add(a: float, b: float) -> float:
    """Numerically stable log-sum-exp for two scalars: log(exp(a) + exp(b))."""
    if a <= -1e20:
        return b
    if b <= -1e20:
        return a
    diff = a - b
    if diff > 50.0:
        return a
    if diff < -50.0:
        return b
    return a + math.log1p(math.exp(-diff)) if diff >= 0 else b + math.log1p(math.exp(diff))


class KenLMBeamSearchDecoder:
    """
    On-device CTC Beam Search Decoder equipped with KenLM Language Model:
    - Maintains top-K acoustic beams across temporal frames
    - Rescores word sequences using KenLM 3-gram language model
    - Integrates pure syllable decoding and batchim/contraction rules
    - Runs in pure CPU C++ bindings in ~5-15ms per utterance
    """
    def __init__(
        self,
        tokenizer: KoreanMorphemeTokenizer,
        lm_path: Optional[str] = "data/vocab/korean_lm.bin",
        beam_size: int = 8,
        alpha: float = 0.5,      # Language model weight
        beta: float = 1.0,       # Word insertion bonus
        blank_id: int = 0
    ):
        self.tokenizer = tokenizer
        self.beam_size = max(1, beam_size)
        self.alpha = alpha
        self.beta = beta
        self.blank_id = blank_id

        self.lm = None
        if lm_path and kenlm is not None:
            p = Path(lm_path)
            if not p.is_absolute():
                p = Path(__file__).resolve().parent.parent / p
            if p.exists():
                self.lm = kenlm.LanguageModel(str(p))
                print(f"[Decoder] Loaded KenLM language model ({p.stat().st_size / (1024*1024):.1f} MB) from {p.name}")
            else:
                print(f"[Decoder Warning] KenLM file not found at {p}. Falling back to acoustic beam search.")

    def decode_greedy(self, logits: torch.Tensor) -> str:
        """Standard Argmax Greedy Decoding (baseline)."""
        preds = torch.argmax(logits, dim=-1).cpu().tolist()
        return self.tokenizer.decode(preds, remove_blank=True, collapse_repeats=True)

    def decode_beam(
        self,
        logits: torch.Tensor,
        beam_size: Optional[int] = None,
        alpha: Optional[float] = None,
        beta: Optional[float] = None
    ) -> str:
        """
        Executes Time-Synchronous CTC Beam Search with KenLM Rescoring.
        Args:
            logits: Tensor of shape (Time, Vocab) or (1, Time, Vocab)
        Returns:
            Best decoded Korean text
        """
        if logits.dim() == 3:
            logits = logits.squeeze(0)

        k_beam = beam_size or self.beam_size
        a = alpha if alpha is not None else self.alpha
        b = beta if beta is not None else self.beta

        # Convert logits to log-probabilities (Time, Vocab)
        log_probs = F.log_softmax(logits, dim=-1).cpu()
        T, V = log_probs.shape

        # Beam state: (tuple_of_non_blank_tokens, last_token) -> (p_blank, p_non_blank)
        # Empty hypothesis at t=0
        beams: Dict[Tuple[int, ...], Tuple[float, float, int]] = {
            (): (0.0, -float("inf"), self.blank_id)
        }

        # Consider top-N most likely tokens per frame to keep beam search blazing fast (<10ms)
        top_k_candidates = min(40, V)

        for t in range(T):
            frame_probs = log_probs[t]
            top_vals, top_indices = torch.topk(frame_probs, top_k_candidates)
            top_vals = top_vals.tolist()
            top_indices = top_indices.tolist()

            next_beams: Dict[Tuple[int, ...], Tuple[float, float, int]] = {}

            for prefix, (p_b, p_nb, last_tok) in beams.items():
                p_total = math.log(math.exp(p_b) + (math.exp(p_nb) if p_nb > -float("inf") else 0.0) + 1e-30)

                # 1. Transition to Blank
                prob_blank = frame_probs[self.blank_id].item()
                nb_p_b, nb_p_nb, _ = next_beams.get(prefix, (-float("inf"), -float("inf"), self.blank_id))
                new_p_b = math.log(math.exp(nb_p_b) + math.exp(p_total + prob_blank) + 1e-30)
                next_beams[prefix] = (new_p_b, nb_p_nb, self.blank_id)

                # 2. Transition to Non-Blank tokens
                for p_val, tok_id in zip(top_vals, top_indices):
                    if tok_id == self.blank_id:
                        continue

                    prob_tok = p_val
                    if tok_id == last_tok:
                        # Same token repeated immediately without blank: only extends if coming from blank
                        new_prefix = prefix
                        nb_p_b, nb_p_nb, _ = next_beams.get(new_prefix, (-float("inf"), -float("inf"), tok_id))
                        add_p = math.log(math.exp(nb_p_nb) + math.exp(p_nb + prob_tok) + 1e-30)
                        next_beams[new_prefix] = (nb_p_b, add_p, tok_id)

                        # Coming from blank creates new token
                        extended_prefix = prefix + (tok_id,)
                        enb_p_b, enb_p_nb, _ = next_beams.get(extended_prefix, (-float("inf"), -float("inf"), tok_id))
                        new_enb_p = math.log(math.exp(enb_p_nb) + math.exp(p_b + prob_tok) + 1e-30)
                        next_beams[extended_prefix] = (enb_p_b, new_enb_p, tok_id)
                    else:
                        new_prefix = prefix + (tok_id,)
                        nb_p_b, nb_p_nb, _ = next_beams.get(new_prefix, (-float("inf"), -float("inf"), tok_id))
                        new_p_nb = math.log(math.exp(nb_p_nb) + math.exp(p_total + prob_tok) + 1e-30)
                        next_beams[new_prefix] = (nb_p_b, new_p_nb, tok_id)

            # Prune beams to top-k
            def _score_beam(item):
                pref, (pb, pnb, _) = item
                acoustic_score = math.log(
                    (math.exp(pb) if pb > -float("inf") else 0.0) +
                    (math.exp(pnb) if pnb > -float("inf") else 0.0) +
                    1e-30
                )
                return acoustic_score

            sorted_items = sorted(next_beams.items(), key=_score_beam, reverse=True)[: k_beam * 3]
            beams = {pref: val for pref, val in sorted_items}

        # Final Rescoring with KenLM
        best_hypothesis = ""
        best_total_score = -float("inf")

        for prefix, (p_b, p_nb, _) in beams.items():
            acoustic_score = _log_add(p_b, p_nb)

            decoded_text = self.tokenizer.decode(list(prefix), remove_blank=True, collapse_repeats=False)
            if not decoded_text:
                continue

            lm_score = 0.0
            num_words = len(decoded_text.split())
            if self.lm is not None:
                # KenLM log10 score
                lm_score = self.lm.score(decoded_text)

            total_score = acoustic_score + (a * lm_score) + (b * num_words)
            if total_score > best_total_score:
                best_total_score = total_score
                best_hypothesis = decoded_text

        if not best_hypothesis:
            # Fallback to greedy if all beams empty
            best_hypothesis = self.decode_greedy(logits)

        return best_hypothesis

    def decode_topk(
        self,
        topk_ids: np.ndarray,
        topk_logprobs: np.ndarray,
        blank_logprobs: np.ndarray,
        beam_size: Optional[int] = None,
        alpha: Optional[float] = None,
        beta: Optional[float] = None
    ) -> str:
        """
        Ultra-fast Time-Synchronous CTC Beam Search:
        - Uses Native C++ Rolling-Hash Engine (<2ms) if available
        - Direct KenLM rescoring on candidate beams
        """
        k_beam = beam_size or self.beam_size
        a = alpha if alpha is not None else self.alpha
        b = beta if beta is not None else self.beta

        T, K = topk_ids.shape

        # -------------------------------------------------------------
        # C++ Ultra-Fast Fast-Path (< 2ms for 375 frames)
        # -------------------------------------------------------------
        if _FAST_BEAM_LIB is not None:
            max_beams = max(16, k_beam * 2)
            max_seq_len = 512
            out_tokens = np.zeros((max_beams, max_seq_len), dtype=np.int32)
            out_lens = np.zeros(max_beams, dtype=np.int32)
            out_scores = np.zeros(max_beams, dtype=np.float32)

            # Ensure contiguous memory
            t_ids_c = np.ascontiguousarray(topk_ids, dtype=np.int32)
            t_lprob_c = np.ascontiguousarray(topk_logprobs, dtype=np.float32)
            blank_lp_c = np.ascontiguousarray(blank_logprobs, dtype=np.float32)

            n_hyp = _FAST_BEAM_LIB.ctc_beam_search_fast_c(
                t_ids_c.ctypes.data_as(ctypes.POINTER(ctypes.c_int32)),
                t_lprob_c.ctypes.data_as(ctypes.POINTER(ctypes.c_float)),
                blank_lp_c.ctypes.data_as(ctypes.POINTER(ctypes.c_float)),
                T, K, k_beam, self.blank_id,
                out_tokens.ctypes.data_as(ctypes.POINTER(ctypes.c_int32)),
                out_lens.ctypes.data_as(ctypes.POINTER(ctypes.c_int32)),
                out_scores.ctypes.data_as(ctypes.POINTER(ctypes.c_float)),
                max_beams, max_seq_len
            )

            best_hypothesis = ""
            best_total_score = -float("inf")

            for i in range(n_hyp):
                seq_l = out_lens[i]
                if seq_l == 0:
                    continue
                toks = out_tokens[i, :seq_l].tolist()
                text = self.tokenizer.decode(toks, remove_blank=True, collapse_repeats=True)
                lm_score = self.lm.score(text) if self.lm else 0.0
                words = len(text.split())
                score = out_scores[i] + (a * lm_score) + (b * words)
                if score > best_total_score:
                    best_total_score = score
                    best_hypothesis = text

            if best_hypothesis:
                return best_hypothesis

        # -------------------------------------------------------------
        # Fallback Python Path
        # -------------------------------------------------------------
        beams: Dict[Tuple[int, ...], Tuple[float, float, int]] = {
            (): (0.0, -float("inf"), self.blank_id)
        }

        for t in range(T):
            p_blank = float(blank_logprobs[t])
            t_ids = topk_ids[t]
            t_lprobs = topk_logprobs[t]

            next_beams: Dict[Tuple[int, ...], Tuple[float, float, int]] = {}

            for prefix, (p_b, p_nb, last_tok) in beams.items():
                p_total = _log_add(p_b, p_nb)

                # 1. Transition to Blank
                nb_p_b, nb_p_nb, _ = next_beams.get(prefix, (-float("inf"), -float("inf"), self.blank_id))
                new_p_b = _log_add(nb_p_b, p_total + p_blank)
                next_beams[prefix] = (new_p_b, nb_p_nb, self.blank_id)

                # 2. Transition to Top-K Non-Blank tokens
                for k_idx in range(K):
                    tok_id = int(t_ids[k_idx])
                    if tok_id == self.blank_id:
                        continue
                    prob_tok = float(t_lprobs[k_idx])

                    if tok_id == last_tok:
                        new_prefix = prefix
                        nb_p_b, nb_p_nb, _ = next_beams.get(new_prefix, (-float("inf"), -float("inf"), tok_id))
                        add_p = _log_add(nb_p_nb, p_nb + prob_tok)
                        next_beams[new_prefix] = (nb_p_b, add_p, tok_id)

                        extended_prefix = prefix + (tok_id,)
                        enb_p_b, enb_p_nb, _ = next_beams.get(extended_prefix, (-float("inf"), -float("inf"), tok_id))
                        new_enb_p = _log_add(enb_p_nb, p_b + prob_tok)
                        next_beams[extended_prefix] = (enb_p_b, new_enb_p, tok_id)
                    else:
                        new_prefix = prefix + (tok_id,)
                        nb_p_b, nb_p_nb, _ = next_beams.get(new_prefix, (-float("inf"), -float("inf"), tok_id))
                        new_p_nb = _log_add(nb_p_nb, p_total + prob_tok)
                        next_beams[new_prefix] = (nb_p_b, new_p_nb, tok_id)

            def _score_beam(item):
                pref, (pb, pnb, _) = item
                return _log_add(pb, pnb)

            sorted_items = sorted(next_beams.items(), key=_score_beam, reverse=True)[: k_beam * 3]
            beams = {pref: val for pref, val in sorted_items}

        best_hypothesis = ""
        best_total_score = -float("inf")

        for prefix, (p_b, p_nb, _) in beams.items():
            acoustic_score = _log_add(p_b, p_nb)

            decoded_text = self.tokenizer.decode(list(prefix), remove_blank=True, collapse_repeats=False)
            if not decoded_text:
                continue

            lm_score = 0.0
            num_words = len(decoded_text.split())
            if self.lm is not None:
                lm_score = self.lm.score(decoded_text)

            total_score = acoustic_score + (a * lm_score) + (b * num_words)
            if total_score > best_total_score:
                best_total_score = total_score
                best_hypothesis = decoded_text

        return best_hypothesis

	"""
	src/decoder.py

	Production On-Device CTC Beam Search Decoder with KenLM Language Model Rescoring.
	Integrates Korean Morpheme Tokenizer, Trie N-Gram language model, and contraction rules.
	"""

	from __future__ import annotations

	import math
	import ctypes
	from pathlib import Path
	from typing import List, Dict, Tuple, Optional, Any

	import numpy as np
	import torch
	import torch.nn.functional as F

	try:
	import kenlm
	except ImportError:
	kenlm = None

	from dataset import KoreanMorphemeTokenizer, normalize_text

	# CTC Beam Search Engine with KenLM Language Model
	_FAST_BEAM_LIB = None


	def _log_add(a: float, b: float) -> float:
	"""Numerically stable log-sum-exp for two scalars: log(exp(a) + exp(b))."""
	if a <= -1e20:
	return b
	if b <= -1e20:
	return a
	diff = a - b
	if diff > 50.0:
	return a
	if diff < -50.0:
	return b
	return a + math.log1p(math.exp(-diff)) if diff >= 0 else b + math.log1p(math.exp(diff))


	class KenLMBeamSearchDecoder:
	"""
	On-device CTC Beam Search Decoder equipped with KenLM Language Model:
	- Maintains top-K acoustic beams across temporal frames
	- Rescores word sequences using KenLM 3-gram language model
	- Integrates pure syllable decoding and batchim/contraction rules
	- Runs in pure CPU C++ bindings in ~5-15ms per utterance
	"""
	def __init__(
	self,
	tokenizer: KoreanMorphemeTokenizer,
	lm_path: Optional[str] = "data/vocab/korean_lm.bin",
	beam_size: int = 8,
	alpha: float = 0.5, # Language model weight
	beta: float = 1.0, # Word insertion bonus
	blank_id: int = 0
	):
	self.tokenizer = tokenizer
	self.beam_size = max(1, beam_size)
	self.alpha = alpha
	self.beta = beta
	self.blank_id = blank_id

	self.lm = None
	if lm_path and kenlm is not None:
	p = Path(lm_path)
	if not p.is_absolute():
	p = Path(__file__).resolve().parent.parent / p
	if p.exists():
	self.lm = kenlm.LanguageModel(str(p))
	print(f"[Decoder] Loaded KenLM language model ({p.stat().st_size / (1024*1024):.1f} MB) from {p.name}")
	else:
	print(f"[Decoder Warning] KenLM file not found at {p}. Falling back to acoustic beam search.")

	def decode_greedy(self, logits: torch.Tensor) -> str:
	"""Standard Argmax Greedy Decoding (baseline)."""
	preds = torch.argmax(logits, dim=-1).cpu().tolist()
	return self.tokenizer.decode(preds, remove_blank=True, collapse_repeats=True)

	def decode_beam(
	self,
	logits: torch.Tensor,
	beam_size: Optional[int] = None,
	alpha: Optional[float] = None,
	beta: Optional[float] = None
	) -> str:
	"""
	Executes Time-Synchronous CTC Beam Search with KenLM Rescoring.
	Args:
	logits: Tensor of shape (Time, Vocab) or (1, Time, Vocab)
	Returns:
	Best decoded Korean text
	"""
	if logits.dim() == 3:
	logits = logits.squeeze(0)

	k_beam = beam_size or self.beam_size
	a = alpha if alpha is not None else self.alpha
	b = beta if beta is not None else self.beta

	# Convert logits to log-probabilities (Time, Vocab)
	log_probs = F.log_softmax(logits, dim=-1).cpu()
	T, V = log_probs.shape

	# Beam state: (tuple_of_non_blank_tokens, last_token) -> (p_blank, p_non_blank)
	# Empty hypothesis at t=0
	beams: Dict[Tuple[int, ...], Tuple[float, float, int]] = {
	(): (0.0, -float("inf"), self.blank_id)
	}

	# Consider top-N most likely tokens per frame to keep beam search blazing fast (<10ms)
	top_k_candidates = min(40, V)

	for t in range(T):
	frame_probs = log_probs[t]
	top_vals, top_indices = torch.topk(frame_probs, top_k_candidates)
	top_vals = top_vals.tolist()
	top_indices = top_indices.tolist()

	next_beams: Dict[Tuple[int, ...], Tuple[float, float, int]] = {}

	for prefix, (p_b, p_nb, last_tok) in beams.items():
	p_total = math.log(math.exp(p_b) + (math.exp(p_nb) if p_nb > -float("inf") else 0.0) + 1e-30)

	# 1. Transition to Blank
	prob_blank = frame_probs[self.blank_id].item()
	nb_p_b, nb_p_nb, _ = next_beams.get(prefix, (-float("inf"), -float("inf"), self.blank_id))
	new_p_b = math.log(math.exp(nb_p_b) + math.exp(p_total + prob_blank) + 1e-30)
	next_beams[prefix] = (new_p_b, nb_p_nb, self.blank_id)

	# 2. Transition to Non-Blank tokens
	for p_val, tok_id in zip(top_vals, top_indices):
	if tok_id == self.blank_id:
	continue

	prob_tok = p_val
	if tok_id == last_tok:
	# Same token repeated immediately without blank: only extends if coming from blank
	new_prefix = prefix
	nb_p_b, nb_p_nb, _ = next_beams.get(new_prefix, (-float("inf"), -float("inf"), tok_id))
	add_p = math.log(math.exp(nb_p_nb) + math.exp(p_nb + prob_tok) + 1e-30)
	next_beams[new_prefix] = (nb_p_b, add_p, tok_id)

	# Coming from blank creates new token
	extended_prefix = prefix + (tok_id,)
	enb_p_b, enb_p_nb, _ = next_beams.get(extended_prefix, (-float("inf"), -float("inf"), tok_id))
	new_enb_p = math.log(math.exp(enb_p_nb) + math.exp(p_b + prob_tok) + 1e-30)
	next_beams[extended_prefix] = (enb_p_b, new_enb_p, tok_id)
	else:
	new_prefix = prefix + (tok_id,)
	nb_p_b, nb_p_nb, _ = next_beams.get(new_prefix, (-float("inf"), -float("inf"), tok_id))
	new_p_nb = math.log(math.exp(nb_p_nb) + math.exp(p_total + prob_tok) + 1e-30)
	next_beams[new_prefix] = (nb_p_b, new_p_nb, tok_id)

	# Prune beams to top-k
	def _score_beam(item):
	pref, (pb, pnb, _) = item
	acoustic_score = math.log(
	(math.exp(pb) if pb > -float("inf") else 0.0) +
	(math.exp(pnb) if pnb > -float("inf") else 0.0) +
	1e-30
	)
	return acoustic_score

	sorted_items = sorted(next_beams.items(), key=_score_beam, reverse=True)[: k_beam * 3]
	beams = {pref: val for pref, val in sorted_items}

	# Final Rescoring with KenLM
	best_hypothesis = ""
	best_total_score = -float("inf")

	for prefix, (p_b, p_nb, _) in beams.items():
	acoustic_score = _log_add(p_b, p_nb)

	decoded_text = self.tokenizer.decode(list(prefix), remove_blank=True, collapse_repeats=False)
	if not decoded_text:
	continue

	lm_score = 0.0
	num_words = len(decoded_text.split())
	if self.lm is not None:
	# KenLM log10 score
	lm_score = self.lm.score(decoded_text)

	total_score = acoustic_score + (a * lm_score) + (b * num_words)
	if total_score > best_total_score:
	best_total_score = total_score
	best_hypothesis = decoded_text

	if not best_hypothesis:
	# Fallback to greedy if all beams empty
	best_hypothesis = self.decode_greedy(logits)

	return best_hypothesis

	def decode_topk(
	self,
	topk_ids: np.ndarray,
	topk_logprobs: np.ndarray,
	blank_logprobs: np.ndarray,
	beam_size: Optional[int] = None,
	alpha: Optional[float] = None,
	beta: Optional[float] = None
	) -> str:
	"""
	Ultra-fast Time-Synchronous CTC Beam Search:
	- Uses Native C++ Rolling-Hash Engine (<2ms) if available
	- Direct KenLM rescoring on candidate beams
	"""
	k_beam = beam_size or self.beam_size
	a = alpha if alpha is not None else self.alpha
	b = beta if beta is not None else self.beta

	T, K = topk_ids.shape

	# -------------------------------------------------------------
	# C++ Ultra-Fast Fast-Path (< 2ms for 375 frames)
	# -------------------------------------------------------------
	if _FAST_BEAM_LIB is not None:
	max_beams = max(16, k_beam * 2)
	max_seq_len = 512
	out_tokens = np.zeros((max_beams, max_seq_len), dtype=np.int32)
	out_lens = np.zeros(max_beams, dtype=np.int32)
	out_scores = np.zeros(max_beams, dtype=np.float32)

	# Ensure contiguous memory
	t_ids_c = np.ascontiguousarray(topk_ids, dtype=np.int32)
	t_lprob_c = np.ascontiguousarray(topk_logprobs, dtype=np.float32)
	blank_lp_c = np.ascontiguousarray(blank_logprobs, dtype=np.float32)

	n_hyp = _FAST_BEAM_LIB.ctc_beam_search_fast_c(
	t_ids_c.ctypes.data_as(ctypes.POINTER(ctypes.c_int32)),
	t_lprob_c.ctypes.data_as(ctypes.POINTER(ctypes.c_float)),
	blank_lp_c.ctypes.data_as(ctypes.POINTER(ctypes.c_float)),
	T, K, k_beam, self.blank_id,
	out_tokens.ctypes.data_as(ctypes.POINTER(ctypes.c_int32)),
	out_lens.ctypes.data_as(ctypes.POINTER(ctypes.c_int32)),
	out_scores.ctypes.data_as(ctypes.POINTER(ctypes.c_float)),
	max_beams, max_seq_len
	)

	best_hypothesis = ""
	best_total_score = -float("inf")

	for i in range(n_hyp):
	seq_l = out_lens[i]
	if seq_l == 0:
	continue
	toks = out_tokens[i, :seq_l].tolist()
	text = self.tokenizer.decode(toks, remove_blank=True, collapse_repeats=True)
	lm_score = self.lm.score(text) if self.lm else 0.0
	words = len(text.split())
	score = out_scores[i] + (a * lm_score) + (b * words)
	if score > best_total_score:
	best_total_score = score
	best_hypothesis = text

	if best_hypothesis:
	return best_hypothesis

	# -------------------------------------------------------------
	# Fallback Python Path
	# -------------------------------------------------------------
	beams: Dict[Tuple[int, ...], Tuple[float, float, int]] = {
	(): (0.0, -float("inf"), self.blank_id)
	}

	for t in range(T):
	p_blank = float(blank_logprobs[t])
	t_ids = topk_ids[t]
	t_lprobs = topk_logprobs[t]

	next_beams: Dict[Tuple[int, ...], Tuple[float, float, int]] = {}

	for prefix, (p_b, p_nb, last_tok) in beams.items():
	p_total = _log_add(p_b, p_nb)

	# 1. Transition to Blank
	nb_p_b, nb_p_nb, _ = next_beams.get(prefix, (-float("inf"), -float("inf"), self.blank_id))
	new_p_b = _log_add(nb_p_b, p_total + p_blank)
	next_beams[prefix] = (new_p_b, nb_p_nb, self.blank_id)

	# 2. Transition to Top-K Non-Blank tokens
	for k_idx in range(K):
	tok_id = int(t_ids[k_idx])
	if tok_id == self.blank_id:
	continue
	prob_tok = float(t_lprobs[k_idx])

	if tok_id == last_tok:
	new_prefix = prefix
	nb_p_b, nb_p_nb, _ = next_beams.get(new_prefix, (-float("inf"), -float("inf"), tok_id))
	add_p = _log_add(nb_p_nb, p_nb + prob_tok)
	next_beams[new_prefix] = (nb_p_b, add_p, tok_id)

	extended_prefix = prefix + (tok_id,)
	enb_p_b, enb_p_nb, _ = next_beams.get(extended_prefix, (-float("inf"), -float("inf"), tok_id))
	new_enb_p = _log_add(enb_p_nb, p_b + prob_tok)
	next_beams[extended_prefix] = (enb_p_b, new_enb_p, tok_id)
	else:
	new_prefix = prefix + (tok_id,)
	nb_p_b, nb_p_nb, _ = next_beams.get(new_prefix, (-float("inf"), -float("inf"), tok_id))
	new_p_nb = _log_add(nb_p_nb, p_total + prob_tok)
	next_beams[new_prefix] = (nb_p_b, new_p_nb, tok_id)

	def _score_beam(item):
	pref, (pb, pnb, _) = item
	return _log_add(pb, pnb)

	sorted_items = sorted(next_beams.items(), key=_score_beam, reverse=True)[: k_beam * 3]
	beams = {pref: val for pref, val in sorted_items}

	best_hypothesis = ""
	best_total_score = -float("inf")

	for prefix, (p_b, p_nb, _) in beams.items():
	acoustic_score = _log_add(p_b, p_nb)

	decoded_text = self.tokenizer.decode(list(prefix), remove_blank=True, collapse_repeats=False)
	if not decoded_text:
	continue

	lm_score = 0.0
	num_words = len(decoded_text.split())
	if self.lm is not None:
	lm_score = self.lm.score(decoded_text)

	total_score = acoustic_score + (a * lm_score) + (b * num_words)
	if total_score > best_total_score:
	best_total_score = total_score
	best_hypothesis = decoded_text

	return best_hypothesis