Viterbi algoritmi — holatlarning eng mos ketma-ketligini (Viterbi yo‘li deb ataladi) topish algoritmi bo‘lib, Markov zanjirlari doirasida sodir bo‘lgan hodisalarning eng ehtimoliy ketma-ketligini aniqlaydi.
U dinamik dasturlash algoritmidir va Viterbining konvolyutsion dekodlash algoritmida qo‘llanadi.
Algoritmni Endryu Viterbi 1967-yilda shovqinli aloqa tarmoqlari orqali uzatiladigan konvolyutsion kodni dekodlash uchun taklif etgan. U GSM va CDMA standartlaridagi mobil telefonlarda, dial-up modemlarda hamda 802.11 standartidagi simsiz tarmoqlarda konvolyutsion kodlarni dekodlash uchun keng qo‘llanadi. Shuningdek, algoritm nutqni tanib olish, nutq sintezi, kompyuter lingvistikasi va bioinformatika sohalarida ham keng qo‘llanadi. Masalan, nutqni tanib olishda tovush signali hodisalar ketma-ketligi sifatida qaraladi, matn esa akustik signalning «yashirin ma’nosi» hisoblanadi. Viterbi algoritmi ushbu signalga mos keluvchi eng ehtimoliy matnni aniqlaydi.
Algoritm quyidagi farazlarga asoslanadi:
- Kuzatiladigan va yashirin hodisalar ketma-ketlik hosil qilishi kerak. Bu ketma-ketlik odatda vaqt bo‘yicha tartiblangan bo‘ladi.
- Ikkala ketma-ketlik o‘zaro moslashtirilgan bo‘lishi kerak: har bir kuzatiladigan hodisaga aynan bitta yashirin hodisa mos kelishi lozim.
- t vaqtigacha bo‘lgan eng ehtimoliy yashirin ketma-ketlikni hisoblash faqat t vaqtidagi kuzatiladigan hodisaga va t − 1 vaqtigacha bo‘lgan eng ehtimoliy ketma-ketlikka bog‘liq bo‘lishi kerak.
Algoritm
Faraz qilaylik, yashirin Markov modeli (YMM) mavjud bo‘lib, uning holatlar fazosi , bunda — tarmoqdagi mumkin bo‘lgan turli holatlar soni. Tarmoq holatlarini bevosita kuzatib bo‘lmaydi. — tarmoqning vaqtdagi holati. Tarmoq chiqishida vaqtda kuzatiladigan qiymat hosil bo‘ladi, bunda — tarmoq chiqishida kuzatilishi mumkin bo‘lgan turli qiymatlar soni. — tarmoqning holatda bo‘lishining boshlang‘ich ehtimolini bildiradi; esa tarmoqning holatidan maqsad holatga o‘tish ehtimoli bo‘lib, maqsad holat — .
Faraz qilaylik, tarmoq chiqishida quyidagi ketma-ketlik kuzatiladi: . U holda tarmoq holatlarining eng ehtimoliy ketma-ketligi kuzatilgan ketma-ketlik asosida quyidagi rekurrent munosabatlar orqali aniqlanadi:
Bu yerda — dastlabki ta kuzatilgan qiymatga mos keluvchi va holatida yakunlanadigan eng ehtimoliy holatlar ketma-ketligining ehtimolidir. Viterbi yo‘lini ikkinchi tenglamadagi qiymatini eslab qoluvchi ko‘rsatkichlar yordamida aniqlash mumkin. Faraz qilaylik, — qiymatini qaytaruvchi funksiya. Bu qiymat ni hisoblashda ishlatiladi, agar bo‘lsa; aks holda, qiymatini qaytaradi, agar bo‘lsa. U holda
Bu yerda quyidagi operatorning standart ta’rifidan foydalaniladi: arg max.
Ushbu algoritmning hisoblash murakkabligi .