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 dona 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).[1]
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ó,[2] 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
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.[3] 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.[4] 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.[5] El 1987 es va introduir al processament del llenguatge natural com a mètode d'etiquetatge de part de la parla.[6]