Algorithme de Viterbi en temps linéaire

Question

J'ai un problème avec un modèle de Markov caché et les états SI ont besoin de trouver un algorithme qui retourne le chemin le plus probable dans le modèle de Markov caché pour une séquence donnée X dans le temps O (| S |). Je pensais à développer un graphe où j'aurais tous les différents états à différentes positions dans X et exécuterais un algorithme de plus court chemin sur ce graphe. Cependant j'aurai n | S |^2 arêtes (où n est le nombre d'états dans X) et n | S | sommets.

Le meilleur algorithme que j'ai trouvé est le plus court chemin acyclique qui court dans le temps O (| E | + | V |) qui est O (| S |^2) dans mon cas. Existe-t-il un algorithme que je peux développer pour qu'il s'exécute dans le temps O (| S |)? Tout ce dont j'ai besoin, c'est l'idée générale.

Merci

Answer 1

Je pense que si vous voulez récupérer la séquence exacte la plus probable que vous ne pouvez pas le faire dans le temps linéaire sur toutes les instances. Cependant, si votre espace de symbole est discret, la complexité moyenne du temps de cas peut être réduite. Jetez un oeil à l'optimisation de Ukkonen pour calculer les distances d'édition et son generalizations. Jetez également un coup d'oeil à compression based techniques ceci est également basé sur le travail d'Ukkonen.