Algorisme de Viterbi

L'algorisme de Viterbi és un mètode de programació dinàmica per obtenir la màxima estimació de probabilitat a posteriori de la seqüència més probable d'estats ocults —anomenat camí de Viterbi— que dóna lloc a una seqüència d'esdeveniments observats, especialment en el context de les fonts d'informació de Markov i model ocult de Màrkov (HMM).

Una demostració animada de l'algorisme de Viterbi, basat en el model HMM

L'algoritme ha trobat una aplicació universal en la descodificació dels codis convolucionals utilitzats tant en mòbils digitals CDMA com GSM, mòdems d'accés telefònic, satèl·lit, comunicacions d'espai profund i LAN sense fil 802.11. Actualment també s'utilitza habitualment en reconeixement de parla, síntesi de parla, diarització, localització de paraules clau, lingüística computacional i bioinformàtica. Per exemple, a la parla a text (reconeixement de la parla), el senyal acústic es tracta com la

Solució aplicant l'algorisme Viterbi HMM.

seqüència observada d'esdeveniments, i es considera que una cadena de text és la "causa oculta" del senyal acústic. L'algoritme de Viterbi troba la cadena de text més probable donada el senyal acústic. L'algorisme de Viterbi rep el nom d'Andrew Viterbi, que el va proposar el 1967 com a algorisme de descodificació per a codis convolucionals sobre enllaços de comunicació digital sorollosos. Té, però, una història d'invencions múltiples, amb almenys set descobriments independents, inclosos els de Viterbi, Needleman i Wunsch, i Wagner i Fischer. El 1987 es va introduir al processament del llenguatge natural com a mètode d'etiquetatge de part de la parla.