code: def viterbi(
      prob: np.ndarray,
      transition: np.ndarray,
      *,
      p_init: Optional[np.ndarray] = None,
      return_logp: bool = False,
  ) -> Union[np.ndarray, Tuple[np.ndarray, np.ndarray]]:
      """Viterbi decoding from observation likelihoods.
  
      Given a sequence of observation likelihoods ``prob[s, t]``,
      indicating the conditional likelihood of seeing the observation
      at time ``t`` from state ``s``, and a transition matrix
      ``transition[i, j]`` which encodes the conditional probability of
      moving from state ``i`` to state ``j``, the Viterbi algorithm [#]_ computes
      the most likely sequence of states from the observations.
  
      .. [#] Viterbi, Andrew. "Error bounds for convolutional codes and an
          asymptotically optimum decoding algorithm."
          IEEE transactions on Information Theory 13.2 (1967): 260-269.
  
      Parameters
      ----------
      prob : np.ndarray [shape=(..., n_states, n_steps), non-negative]
          ``prob[..., s, t]`` is the probability of observation at time ``t``
          being generated by state ``s``.
      transition : np.ndarray [shape=(n_states, n_states), non-negative]
          ``transition[i, j]`` is the probability of a transition from i->j.
          Each row must sum to 1.
      p_init : np.ndarray [shape=(n_states,)]
          Optional: initial state distribution.
          If not provided, a uniform distribution is assumed.
      return_logp : bool
          If ``True``, return the log-likelihood of the state sequence.
  
      Returns
      -------
      Either ``states`` or ``(states, logp)``:
      states : np.ndarray [shape=(..., n_steps,)]
          The most likely state sequence.
          If ``prob`` contains multiple channels of input, then each channel is
          decoded independently.
      logp : scalar [float] or np.ndarray
          If ``return_logp=True``, the log probability of ``states`` given
          the observations.
  
      See Also
      --------
      viterbi_discriminative : Viterbi decoding from state likelihoods
  
      Examples
      --------
      Example from https://en.wikipedia.org/wiki/Viterbi_algorithm#Example
  
      In this example, we have two states ``healthy`` and ``fever``, with
      initial probabilities 60% and 40%.
  
      We have three observation possibilities: ``normal``, ``cold``, and
      ``dizzy``, whose probabilities given each state are:
  
      ``healthy => {normal: 50%, cold: 40%, dizzy: 10%}`` and
      ``fever => {normal: 10%, cold: 30%, dizzy: 60%}``
  
      Finally, we have transition probabilities:
  
      ``healthy => healthy (70%)`` and
      ``fever => fever (60%)``.
  
      Over three days, we observe the sequence ``[normal, cold, dizzy]``,
      and wish to know the maximum likelihood assignment of states for the
      corresponding days, which we compute with the Viterbi algorithm below.
  
      >>> p_init = np.array([0.6, 0.4])
      >>> p_emit = np.array([[0.5, 0.4, 0.1],
      ...                    [0.1, 0.3, 0.6]])
      >>> p_trans = np.array([[0.7, 0.3], [0.4, 0.6]])
      >>> path, logp = librosa.sequence.viterbi(p_emit, p_trans, p_init=p_init,
      ...                                       return_logp=True)
      >>> print(logp, path)
      -4.19173690823075 [0 0 1]
      """
      n_states, n_steps = prob.shape[-2:]
  
      if transition.shape != (n_states, n_states):
          raise ParameterError(
              f"transition.shape={transition.shape}, must be "
              f"(n_states, n_states)={n_states, n_states}"
          )
  
      if np.any(transition < 0) or not np.allclose(
          transition.sum(axis=1), 1
      ):
          raise ParameterError(
              "Invalid transition matrix: must be non-negative "
              "and sum to 1 on each row."
          )
  
      if np.any(prob < 0) or np.any(prob > 1):
          raise ParameterError(
              "Invalid probability values: must be between 0 and 1."
          )
  
      # Compute log-likelihoods while avoiding log-underflow
      epsilon = tiny(prob)
  
      if p_init is None:
          p_init = np.empty(n_states)
          p_init.fill(1.0 / n_states)
      elif (
          np.any(p_init < 0)
          or not np.allclose(p_init.sum(), 1)
          or p_init.shape != (n_states,)
      ):
          raise ParameterError(
              f"Invalid initial state distribution: p_init={p_init}"
          )
  
      log_trans = np.log(transition + epsilon)
      log_prob = np.log(prob + epsilon)
      log_p_init = np.log(p_init + epsilon)
  
      def _helper(lp):
          # Transpose input
          _state, logp = _viterbi(lp.T, log_trans, log_p_init)
          # Transpose outputs for return
          return _state.T, logp
  
      states: np.ndarray
      logp: np.ndarray
  
      if log_prob.ndim == 2:
          states, logp = _helper(log_prob)
      else:
          # Vectorize the helper
          __viterbi = np.vectorize(
              _helper,
              otypes=[np.uint16, np.float64],
              signature="(s,t)->(t),(1)",
          )
  
          states, logp = __viterbi(log_prob)
  
          # Flatten out the trailing dimension introduced by vectorization
          logp = logp[..., 0]
  
      if return_logp:
          return states, logp
  
      return states
  
imports: from __future__ import annotations
  import numpy
  from scipy.spatial.distance import cdist
  from numba import jit
  from .util import pad_center, fill_off_diagonal, is_positive_int, tiny, expand_to
  from .util.exceptions import ParameterError
  from .filters import get_window
  from typing import Any, Iterable, List, Optional, Tuple, Union, overload
  from typing_extensions import Literal
  from ._typing import _WindowSpec, _IntLike_co
label_desc: Use image node_id 22 for calling a global function with example usage: viterbi(prob, transition) and returns: states, _state,  logp, states,  logp