הצגת המקור של הדף "אלגוריתם ויטרבי"

{{אלגוריתם}}
'''אלגוריתם ויטרבי''' (ב[[אנגלית]]: '''Viterbi Algorithm'''), [[אלגוריתם]] [[תכנון דינמי]] למציאת רצף המצבים החבויים ה[[סבירות|סביר]] ביותר, שתוצאתו היא רצף תצפיות נתון. בין שימושיו הנפוצים - מציאת רצף המצבים בהנחת [[מודל מרקוב חבוי]], פיענוח [[קוד קונבולוציה|קודי קונבולוציה]] ועוד רבים. תחת זאת, משמש באופן תדיר ב[[מערכת תקשורת|מערכות תקשורת]], כגון [[IEEE 802.11]].

יתרונו הבולט של האלגוריתם הוא הורדת [[סיבוכיות]] המציאה של הרצף הסביר ביותר - מהמימוש הנאיבי (בעל סיבוכיות מעריכית בגודל הרצף) למימוש היעיל של האלגוריתם (בעל סיבוכיות ליניארית בגודל הרצף).

== היסטוריה ==
האלגוריתם פותח לראשונה על ידי [[אנדרו ויטרבי]] בשנת [[1967]] לטובת פיענוח [[קוד קונבולוציה]] מעל [[ערוץ תקשורת]] [[רעש|רועש]]. הוא פותח באופן בלתי-תלוי על ידי מספר גורמים אחרים.

== פסאודו-קוד ==
אלגוריתם ויטרבי מקבל כקלט רצף תצפיות <math> Y=(y_1,y_2,\ldots, y_T) \in \{1,2,\dots,N\}^T</math>, ומטרתו להוציא את רצף המצבים <math> X=(x_1,x_2,\ldots,x_T)\in S=\{s_1,s_2,\dots,s_K\}^T </math> הסביר ביותר בהינתן התצפיות <math> Y</math>. בהקשר זה, <math> T</math> הוא אורך הרצף (תצפיות ומצבים), <math> N</math> הוא גודל מרחב התצפיות ו-<math> K</math> הוא גודל מרחב המצבים.

במהלך פעולתו, האלגוריתם משתמש בשתי טבלאות בגודל <math> K \times T</math>:
* טבלה <math> T_1</math>, שבה האיבר <math> T_1[i,j]</math> מכיל את ההסתברות של הנתיב (רצף) הכי סביר עד כה: <math> \hat{X}=(\hat{x}_1,\hat{x}_2,\ldots,\hat{x}_j) </math>.
* טבלה <math> T_2</math> שבה האיבר <math> T_2[i,j]</math> מכיל את <math>\hat{x}_{j-1} </math> של המסלול הסביר ביותר עד כה.

האלגוריתם ממלא את הטבלאות לפי סדר עולה של <math>K\cdot j+i </math>, ולפי הנוסחאות הרקורסיביות:
:<math>T_1[i,j]=\max_{k}{(T_1[k,j-1]\cdot A_{ki})\cdot B_{iy_j}} </math>
:<math> T_2[i,j]=\operatorname{argmax}_{k}{(T_1[k,j-1]\cdot A_{ki})} </math>

כאשר <math>A_{ki}</math> ו-<math>B_{iy_j}</math> מוגדרים מטה.

;קלט:
*            מרחב התצפיות <math> O=\{o_1,o_2,\dots,o_N\}</math>
*            מרחב המצבים <math> S=\{s_1,s_2,\dots,s_K\} </math>
*            ההסתברויות ההתחלתיות <math> \Pi = (\pi_1,\pi_2,\dots,\pi_K)</math>, כך ש-<math> \pi_i </math> היא ההסתברות ש-<math> x_1 ==  s_i </math>
*            רצף תצפיות <math> Y=(y_1,y_2,\ldots, y_T) </math> כך ש-<math> y_t==i </math> אם התצפית בזמן <math> t </math> היא <math> o_i </math>
*            מטריצת המעברים <math> A </math> ממימד <math> K\cdot K </math> כך ש-<math> A_{ij} </math> היא הסתברות המעבר ממצב <math> s_i </math> למצב <math> s_j </math>
*            מטריצת הפלטים <math> B </math> ממימד <math> K\cdot N </math> כך ש-<math> B_{ij} </math> הוא ההסתברות לתצפית <math> o_j </math> בהינתן שהמצב הוא <math> s_i </math> 

;פלט: 
*רצף המצבים הסביר ביותר <math> X=(x_1,x_2,\ldots,x_N) </math>

<div class="mw-content-ltr">
  '''function''' ''VITERBI''<math>(O,S,\Pi,Y,A,B):X</math>
      '''for''' each state <math>i \in \{1,2,\ldots,K\}</math> '''do'''
          <math> T_1[i,1] \leftarrow \pi_i \cdot B_{iy_1}</math>
          <math> T_2[i,1] \leftarrow 0</math>
      '''end for'''
      '''for''' each observation <math>i = 2,3,\ldots,T</math> '''do'''
          '''for''' each state <math>j \in \{1,2,\ldots,K\}</math> '''do'''
              <math> T_1[j,i] \leftarrow B_{jy_1} \cdot \max_{k}{(T_1[k,i-1]\cdot A_{kj})} </math>
              <math> T_2[j,i] \leftarrow \arg\max_{k}{(T_1[k,i-1]\cdot A_{kj}}) </math>
          '''end for'''
      '''end for'''
      <math> z_T \leftarrow \arg\max_{k}{(T_1[k,T])} </math>
      <math> x_T \leftarrow s_{z_T}</math>
      '''for''' <math>i \leftarrow T,T-1,\dots,2</math>  '''do'''
          <math> z_{i-1} \leftarrow T_2[z_i,i]</math>
          <math> x_{i-1} \leftarrow s_{z_{i-1}}</math>
      '''end for'''
      '''return''' <math> X</math>
  '''end function'''
</div>

סיבוכיות האלגוריתם היא <math>O(T\times\left|{S}\right|^2)</math>.



== קישורים חיצוניים ==
{{ויקישיתוף בשורה}}
* [https://en.wikibooks.org/wiki/Algorithm_Implementation/Viterbi_algorithm מימושים ב-Java, C#, ועוד] באתר wikibooks.
* [http://home.netcom.com/~chip.f/viterbi/tutorial.html הסבר מפורט]{{קישור שבור|date=ינואר 2020 |bot=InternetArchiveBot |fix-attempted=yes }} על האלגוריתם בהקשרי קודי קונבולוציה
* [https://arxiv.org/abs/cs/0504020v2 ההיסטוריה של האלגוריתם] - מאת David Forney



[[קטגוריה:קודים לאיתור שגיאות ולתיקונן]]
[[קטגוריה:אלגוריתמים]]
[[קטגוריה:מודלים מרקוביים]]