viterbi algorithm to find the most likely path of states from the start and the expected output https en wikipedia orgwikiviterbialgorithm sdafads wikipedia example observations normal cold dizzy states healthy fever startp healthy 0 6 fever 0 4 transp healthy healthy 0 7 fever 0 3 fever healthy 0 4 fever 0 6 emitp healthy normal 0 5 cold 0 4 dizzy 0 1 fever normal 0 1 cold 0 3 dizzy 0 6 viterbiobservations states startp transp emitp healthy healthy fever viterbi states startp transp emitp traceback most recent call last valueerror there s an empty parameter viterbiobservations startp transp emitp traceback most recent call last valueerror there s an empty parameter viterbiobservations states transp emitp traceback most recent call last valueerror there s an empty parameter viterbiobservations states startp emitp traceback most recent call last valueerror there s an empty parameter viterbiobservations states startp transp traceback most recent call last valueerror there s an empty parameter viterbiinvalid states startp transp emitp traceback most recent call last valueerror observationsspace must be a list viterbivalid 123 states startp transp emitp traceback most recent call last valueerror observationsspace must be a list of strings viterbiobservations invalid startp transp emitp traceback most recent call last valueerror statesspace must be a list viterbiobservations valid 123 startp transp emitp traceback most recent call last valueerror statesspace must be a list of strings viterbiobservations states invalid transp emitp traceback most recent call last valueerror initialprobabilities must be a dict viterbiobservations states 2 2 transp emitp traceback most recent call last valueerror initialprobabilities all keys must be strings viterbiobservations states a 2 transp emitp traceback most recent call last valueerror initialprobabilities all values must be float viterbiobservations states startp invalid emitp traceback most recent call last valueerror transitionprobabilities must be a dict viterbiobservations states startp a 2 emitp traceback most recent call last valueerror transitionprobabilities all values must be dict viterbiobservations states startp 2 2 2 emitp traceback most recent call last valueerror transitionprobabilities all keys must be strings viterbiobservations states startp a 2 2 emitp traceback most recent call last valueerror transitionprobabilities all keys must be strings viterbiobservations states startp a b 2 emitp traceback most recent call last valueerror transitionprobabilities nested dictionary all values must be float viterbiobservations states startp transp invalid traceback most recent call last valueerror emissionprobabilities must be a dict viterbiobservations states startp transp none traceback most recent call last valueerror there s an empty parameter creates data structures and fill initial step fills the data structure with the probabilities of different transitions and pointers to previous states calculates the argmax for probability function update probabilities and pointers dicts the final observation argmax for given final observation process pointers backwards observations normal cold dizzy states healthy fever startp healthy 0 6 fever 0 4 transp healthy healthy 0 7 fever 0 3 fever healthy 0 4 fever 0 6 emitp healthy normal 0 5 cold 0 4 dizzy 0 1 fever normal 0 1 cold 0 3 dizzy 0 6 validationobservations states startp transp emitp validation states startp transp emitp traceback most recent call last valueerror there s an empty parameter validatenotemptya b c 0 5 d e 0 6 f g 0 7 validatenotemptya b c 0 5 f g 0 7 traceback most recent call last valueerror there s an empty parameter validatenotemptya b none d e 0 6 f g 0 7 traceback most recent call last valueerror there s an empty parameter validatelistsa b validatelists1234 b traceback most recent call last valueerror observationsspace must be a list validatelistsa 3 traceback most recent call last valueerror statesspace must be a list of strings validatelista mockname validatelista mockname traceback most recent call last valueerror mockname must be a list validatelist0 5 mockname traceback most recent call last valueerror mockname must be a list of strings validatedictsc 0 5 d e 0 6 f g 0 7 validatedictsinvalid d e 0 6 f g 0 7 traceback most recent call last valueerror initialprobabilities must be a dict validatedictsc 0 5 2 e 0 6 f g 0 7 traceback most recent call last valueerror transitionprobabilities all keys must be strings validatedictsc 0 5 d e 0 6 f 2 0 7 traceback most recent call last valueerror emissionprobabilities all keys must be strings validatedictsc 0 5 d e 0 6 f g h traceback most recent call last valueerror emissionprobabilities nested dictionary all values must be float validatenesteddicta b 0 5 mockname validatenesteddictinvalid mockname traceback most recent call last valueerror mockname must be a dict validatenesteddicta 8 mockname traceback most recent call last valueerror mockname all values must be dict validatenesteddicta 2 0 5 mockname traceback most recent call last valueerror mockname all keys must be strings validatenesteddicta b 4 mockname traceback most recent call last valueerror mockname nested dictionary all values must be float validatedictb 0 5 mockname float validatedictinvalid mockname float traceback most recent call last valueerror mockname must be a dict validatedicta 8 mockname dict traceback most recent call last valueerror mockname all values must be dict validatedict2 0 5 mockname float true traceback most recent call last valueerror mockname all keys must be strings validatedictb 4 mockname float true traceback most recent call last valueerror mockname nested dictionary all values must be float viterbi algorithm to find the most likely path of states from the start and the expected output https en wikipedia org wiki viterbi_algorithm sdafads wikipedia example observations normal cold dizzy states healthy fever start_p healthy 0 6 fever 0 4 trans_p healthy healthy 0 7 fever 0 3 fever healthy 0 4 fever 0 6 emit_p healthy normal 0 5 cold 0 4 dizzy 0 1 fever normal 0 1 cold 0 3 dizzy 0 6 viterbi observations states start_p trans_p emit_p healthy healthy fever viterbi states start_p trans_p emit_p traceback most recent call last valueerror there s an empty parameter viterbi observations start_p trans_p emit_p traceback most recent call last valueerror there s an empty parameter viterbi observations states trans_p emit_p traceback most recent call last valueerror there s an empty parameter viterbi observations states start_p emit_p traceback most recent call last valueerror there s an empty parameter viterbi observations states start_p trans_p traceback most recent call last valueerror there s an empty parameter viterbi invalid states start_p trans_p emit_p traceback most recent call last valueerror observations_space must be a list viterbi valid 123 states start_p trans_p emit_p traceback most recent call last valueerror observations_space must be a list of strings viterbi observations invalid start_p trans_p emit_p traceback most recent call last valueerror states_space must be a list viterbi observations valid 123 start_p trans_p emit_p traceback most recent call last valueerror states_space must be a list of strings viterbi observations states invalid trans_p emit_p traceback most recent call last valueerror initial_probabilities must be a dict viterbi observations states 2 2 trans_p emit_p traceback most recent call last valueerror initial_probabilities all keys must be strings viterbi observations states a 2 trans_p emit_p traceback most recent call last valueerror initial_probabilities all values must be float viterbi observations states start_p invalid emit_p traceback most recent call last valueerror transition_probabilities must be a dict viterbi observations states start_p a 2 emit_p traceback most recent call last valueerror transition_probabilities all values must be dict viterbi observations states start_p 2 2 2 emit_p traceback most recent call last valueerror transition_probabilities all keys must be strings viterbi observations states start_p a 2 2 emit_p traceback most recent call last valueerror transition_probabilities all keys must be strings viterbi observations states start_p a b 2 emit_p traceback most recent call last valueerror transition_probabilities nested dictionary all values must be float viterbi observations states start_p trans_p invalid traceback most recent call last valueerror emission_probabilities must be a dict viterbi observations states start_p trans_p none traceback most recent call last valueerror there s an empty parameter creates data structures and fill initial step fills the data structure with the probabilities of different transitions and pointers to previous states calculates the argmax for probability function update probabilities and pointers dicts the final observation argmax for given final observation process pointers backwards observations normal cold dizzy states healthy fever start_p healthy 0 6 fever 0 4 trans_p healthy healthy 0 7 fever 0 3 fever healthy 0 4 fever 0 6 emit_p healthy normal 0 5 cold 0 4 dizzy 0 1 fever normal 0 1 cold 0 3 dizzy 0 6 _validation observations states start_p trans_p emit_p _validation states start_p trans_p emit_p traceback most recent call last valueerror there s an empty parameter _validate_not_empty a b c 0 5 d e 0 6 f g 0 7 _validate_not_empty a b c 0 5 f g 0 7 traceback most recent call last valueerror there s an empty parameter _validate_not_empty a b none d e 0 6 f g 0 7 traceback most recent call last valueerror there s an empty parameter _validate_lists a b _validate_lists 1234 b traceback most recent call last valueerror observations_space must be a list _validate_lists a 3 traceback most recent call last valueerror states_space must be a list of strings _validate_list a mock_name _validate_list a mock_name traceback most recent call last valueerror mock_name must be a list _validate_list 0 5 mock_name traceback most recent call last valueerror mock_name must be a list of strings _validate_dicts c 0 5 d e 0 6 f g 0 7 _validate_dicts invalid d e 0 6 f g 0 7 traceback most recent call last valueerror initial_probabilities must be a dict _validate_dicts c 0 5 2 e 0 6 f g 0 7 traceback most recent call last valueerror transition_probabilities all keys must be strings _validate_dicts c 0 5 d e 0 6 f 2 0 7 traceback most recent call last valueerror emission_probabilities all keys must be strings _validate_dicts c 0 5 d e 0 6 f g h traceback most recent call last valueerror emission_probabilities nested dictionary all values must be float _validate_nested_dict a b 0 5 mock_name _validate_nested_dict invalid mock_name traceback most recent call last valueerror mock_name must be a dict _validate_nested_dict a 8 mock_name traceback most recent call last valueerror mock_name all values must be dict _validate_nested_dict a 2 0 5 mock_name traceback most recent call last valueerror mock_name all keys must be strings _validate_nested_dict a b 4 mock_name traceback most recent call last valueerror mock_name nested dictionary all values must be float _validate_dict b 0 5 mock_name float _validate_dict invalid mock_name float traceback most recent call last valueerror mock_name must be a dict _validate_dict a 8 mock_name dict traceback most recent call last valueerror mock_name all values must be dict _validate_dict 2 0 5 mock_name float true traceback most recent call last valueerror mock_name all keys must be strings _validate_dict b 4 mock_name float true traceback most recent call last valueerror mock_name nested dictionary all values must be float
from typing import Any


def viterbi(
    observations_space: list,
    states_space: list,
    initial_probabilities: dict,
    transition_probabilities: dict,
    emission_probabilities: dict,
) -> list:
    
    _validation(
        observations_space,
        states_space,
        initial_probabilities,
        transition_probabilities,
        emission_probabilities,
    )
    
    probabilities: dict = {}
    pointers: dict = {}
    for state in states_space:
        observation = observations_space[0]
        probabilities[(state, observation)] = (
            initial_probabilities[state] * emission_probabilities[state][observation]
        )
        pointers[(state, observation)] = None

    
    
    for o in range(1, len(observations_space)):
        observation = observations_space[o]
        prior_observation = observations_space[o - 1]
        for state in states_space:
            
            arg_max = ""
            max_probability = -1
            for k_state in states_space:
                probability = (
                    probabilities[(k_state, prior_observation)]
                    * transition_probabilities[k_state][state]
                    * emission_probabilities[state][observation]
                )
                if probability > max_probability:
                    max_probability = probability
                    arg_max = k_state

            
            probabilities[(state, observation)] = (
                probabilities[(arg_max, prior_observation)]
                * transition_probabilities[arg_max][state]
                * emission_probabilities[state][observation]
            )

            pointers[(state, observation)] = arg_max

    
    final_observation = observations_space[len(observations_space) - 1]

    
    arg_max = ""
    max_probability = -1
    for k_state in states_space:
        probability = probabilities[(k_state, final_observation)]
        if probability > max_probability:
            max_probability = probability
            arg_max = k_state
    last_state = arg_max

    
    previous = last_state
    result = []
    for o in range(len(observations_space) - 1, -1, -1):
        result.append(previous)
        previous = pointers[previous, observations_space[o]]
    result.reverse()

    return result


def _validation(
    observations_space: Any,
    states_space: Any,
    initial_probabilities: Any,
    transition_probabilities: Any,
    emission_probabilities: Any,
) -> None:
    
    _validate_not_empty(
        observations_space,
        states_space,
        initial_probabilities,
        transition_probabilities,
        emission_probabilities,
    )
    _validate_lists(observations_space, states_space)
    _validate_dicts(
        initial_probabilities, transition_probabilities, emission_probabilities
    )


def _validate_not_empty(
    observations_space: Any,
    states_space: Any,
    initial_probabilities: Any,
    transition_probabilities: Any,
    emission_probabilities: Any,
) -> None:
    
    if not all(
        [
            observations_space,
            states_space,
            initial_probabilities,
            transition_probabilities,
            emission_probabilities,
        ]
    ):
        raise ValueError("There's an empty parameter")


def _validate_lists(observations_space: Any, states_space: Any) -> None:
    
    _validate_list(observations_space, "observations_space")
    _validate_list(states_space, "states_space")


def _validate_list(_object: Any, var_name: str) -> None:
    
    if not isinstance(_object, list):
        msg = f"{var_name} must be a list"
        raise ValueError(msg)
    else:
        for x in _object:
            if not isinstance(x, str):
                msg = f"{var_name} must be a list of strings"
                raise ValueError(msg)


def _validate_dicts(
    initial_probabilities: Any,
    transition_probabilities: Any,
    emission_probabilities: Any,
) -> None:
    
    _validate_dict(initial_probabilities, "initial_probabilities", float)
    _validate_nested_dict(transition_probabilities, "transition_probabilities")
    _validate_nested_dict(emission_probabilities, "emission_probabilities")


def _validate_nested_dict(_object: Any, var_name: str) -> None:
    
    _validate_dict(_object, var_name, dict)
    for x in _object.values():
        _validate_dict(x, var_name, float, True)


def _validate_dict(
    _object: Any, var_name: str, value_type: type, nested: bool = False
) -> None:
    
    if not isinstance(_object, dict):
        msg = f"{var_name} must be a dict"
        raise ValueError(msg)
    if not all(isinstance(x, str) for x in _object):
        msg = f"{var_name} all keys must be strings"
        raise ValueError(msg)
    if not all(isinstance(x, value_type) for x in _object.values()):
        nested_text = "nested dictionary " if nested else ""
        msg = f"{var_name} {nested_text}all values must be {value_type.__name__}"
        raise ValueError(msg)


if __name__ == "__main__":
    from doctest import testmod

    testmod()