Алгоритм Витерби — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 70 промежуточных версий 8 участников)
Строка 1: Строка 1:
 
== История ==
 
== История ==
Алгоритм Витерби был представлен в 1967 году для декодирования сверточных кодов, поступающих через зашумленный канал связи. В 1969 году Омура (Omura) показал, что основу алгоритма Витерби составляет оценка максимума правдоподобия.
+
'''Алгоритм Витерби''' (англ. ''Viterbi algorithm'') был представлен в 1967 году для декодирования сверточных кодов, поступающих через зашумленный канал связи. В 1969 году Омура (Omura) показал, что основу алгоритма Витерби составляет оценка максимума правдоподобия, которая является популярным статистическим методом для создания статистической модели на основе данных и обеспечения оценки параметров модели (т.е. оценка неизвестного параметра максимизацией функции правдоподобия).
== Применение ==
+
{{Определение
Алгоритм используется в CDMA и GSM цифровой связи, в модемах и космических коммуникациях. Он нашел применение в распознавании речи и письма, компьютерной лингвистике и биоинформатике, а также в алгоритме свёрточного декодирования Витерби.
+
|id=def1.
 +
|definition='''Сверточный код''' (англ. ''Convolutional code '') {{---}} это корректирующий ошибки код, в котором
 +
#На каждом такте работы кодера <tex>\mathtt{k}</tex> символов входной полубесконечной последовательности преобразуются в <tex>\mathtt{n} > \mathtt{k}</tex> символов выходной
 +
#Также в преобразовании участвуют <tex>\mathtt{m}</tex> предыдущих символов
 +
#Выполняется свойство линейности (если <tex>\mathtt{x}</tex> соответствует <tex>\mathtt{X}</tex>, а <tex>\mathtt{y}</tex> соответствует <tex>\mathtt{Y}</tex>, то <tex>\mathtt{ax} + \mathtt{by}</tex> соответствует <tex>\mathtt{aX} + \mathtt{bY}</tex>).
 +
}}
 +
 
 
== Описание ==
 
== Описание ==
Алгоритм Витерби позволяет сделать наилучшее предположение о последовательности состояний скрытой модели на основе последовательности наблюдений. Эта последовательность состояний называется путем Витерби.
+
Алгоритм Витерби позволяет сделать наиболее вероятное предположение о последовательности состояний [[Скрытые Марковские модели|скрытой Марковской модели]] на основе последовательности наблюдений.
 
{{Определение
 
{{Определение
 
|id=def1.  
 
|id=def1.  
|definition=Путь Витерби наиболее правдоподобная последовательность скрытых состояний.
+
|definition='''Путь Витерби''' (англ. ''Viterbi path'') {{---}} наиболее правдоподобная (наиболее вероятная) последовательность скрытых состояний.
 
}}
 
}}
 +
'''Предположения, которые делает алгоритм:'''
 +
#Скрытые и наблюдаемые события должны быть последовательностью, которая упорядочена по времени.
 +
#Каждое скрытое событие должно соответствовать только одному наблюдаемому.
 +
#Вычисление наиболее вероятной скрытой последовательности до момента <tex>\mathtt{t}</tex> зависит только от наблюдаемого события в этот момент времени и наиболее вероятной последовательности до момента <tex>\mathtt{t} - 1</tex> (динамическое программирование).
  
Пусть задано пространство наблюдений <tex>O =\{o_1,o_2...o_N\}</tex>, пространство состояний <tex>S =\{s_1,s_2...s_K\}</tex>, последовательность наблюдений <tex>Y =\{y_1,y_2...y_T\}</tex>, матрица <tex>A</tex> переходов из <tex>i</tex>-того состояния в <tex>j</tex>-ое, размером <tex>K*K</tex>, матрица эмиссии В размера <tex>K*N</tex>, которая определяет вероятность наблюдения <tex>o_j</tex> из состояния <tex>s_i</tex>, массив начальных вероятностей <tex>\pi\,\!</tex> размером <tex>K</tex>, показывающий вероятность того, что начальное состояние <tex>s_i</tex>. Путь <tex>Х =\{x_1,x_2...x_T\}</tex> — последовательность состояний, которые привели к последовательности наблюдений <tex>Y</tex>.
+
== Алгоритм ==
 +
'''Входные данные:'''
  
'''Скрытая марковская модель.'''
+
#Пространство наблюдений <tex>\mathtt{O} =\{\mathtt{o_1},\mathtt{o_2} \ldots \mathtt{o_N}\}</tex>
 +
#Пространство состояний <tex>\mathtt{S} =\{\mathtt{s_1},\mathtt{s_2} \ldots \mathtt{s_K}\}</tex>
 +
#Последовательность наблюдений <tex>\mathtt{Y} =\{\mathtt{y_1},\mathtt{y_2} \ldots \mathtt{y_T}\}</tex>
 +
#Матрица <tex>\mathtt{A}</tex> переходов из <tex>\mathtt{i}</tex>-того состояния в <tex>\mathtt{j}</tex>-ое, размером <tex>\mathtt{K} \times \mathtt{K}</tex>
 +
#Матрица эмиссии <tex>\mathtt{B}</tex> размера <tex>\mathtt{K} \times \mathtt{N}</tex>, которая определяет вероятность наблюдения <tex>\mathtt{o_j}</tex> из состояния <tex>\mathtt{s_i}</tex>
 +
#Массив начальных вероятностей <tex>\mathtt{\pi}</tex> размером <tex>\mathtt{K}</tex>, показывающий вероятность того, что начальное состояние <tex>\mathtt{s_i}</tex>
  
Модель представляет из себя марковскую цепь, для которой нам известны начальная вероятность и матрица вероятностей переходов. Скрытой она называется потому, что мы не имеем информации о ее текущем состоянии. Мы получаем информацию на основе некоторого наблюдения, в рассмотренном ниже алгоритме мы будем использовать просто натуральное число от 1 до <tex>N</tex>, как индекс наблюдаемого события. Для каждого состояния скрытой марковской модели задан вектор вероятности эмиссии, который характеризует вероятность наблюдени каждого события, когда модель находится в этом состоянии. Совокупность таких векторов образует матрицу эмиссии.
+
'''Выходные данные''':
  
'''Пример скрытой марковской модели.'''
+
<tex>\mathtt{X} =\{\mathtt{x_1},\mathtt{x_2} \ldots \mathtt{x_T}\}</tex> {{---}} последовательность состояний, которые привели к последовательности наблюдений <tex>\mathtt{Y}</tex>.
  
Рассмотрим пример скрытой марковской модели. У Деда Мороза есть три мешка с подарками в разноцветной упаковке: красной, синей, зеленой и фиолетовой. Ночью Дед Мороз  пробирается в квартиру и тайком  выкладывает подарки под елкой в ряд, доставая по одному подарку из мешка. Наутро мы обнаруживаем упорядоченную последовательность из пяти подарков и хотим сделать наилучшее предположение о последовательности мешков, из которых он доставал эти подарки.
+
'''Алгоритм:'''
Дед Мороз с мешками — скрытая марковская модель. При этом 3 мешка — количество состояний <tex>K</tex>, 5 подарков — наши <tex>T</tex> наблюдений, каждое из которых представлено цифрой — номером цвета — от 1 до 5. Мы знаем, каковы вероятности того, что Дед Мороз начнет доставать подарки из мешка с номером <tex>i</tex> – вектор <tex>\pi[i]\,\!</tex>. Мы также знаем матрицу переходов <tex>A</tex>, какова вероятность того, что от мешка с номером <tex>i</tex> Дед Мороз переходит к мешку с номером <tex>j</tex>. Мешки Деда Мороза бесконечны, но мы точно знаем, каково соотношение цветов подарков в кажом мешке ему загрузили на заводе в Великом Устюге. Это матрица вероятностей эмиссии <tex>B</tex>.
 
  
== Алгоритм ==
+
Создадим две матрицы <tex>\mathtt{TState}</tex> и <tex>\mathtt{TIndex}</tex> размером <tex>\mathtt{K} \times \mathtt{T}</tex>. Каждый элемент <tex>\mathtt{TState}[\mathtt{i},\mathtt{j}]</tex> содержит вероятность того, что на <tex>\mathtt{j}</tex>-ом шаге мы находимся в состоянии <tex>\mathtt{s_i}</tex>. Каждый элемент <tex>\mathtt{TIndex}[\mathtt{i},\mathtt{j}]</tex> содержит индекс наиболее вероятного состояния на <tex>\mathtt{j} - 1</tex>-ом шаге.  
Создадим две матрицы <tex>T_1</tex> и <tex>T_2</tex> размером <tex>K*T</tex>. Каждый элемент <tex>T_1[i,j]</tex> содержит вероятность того, что на <tex>j</tex>-ом шаге мы находимся в состоянии <tex>s_i</tex>. Каждый элемент <tex>T_2[i,j]</tex> содержит индекс наиболее вероятного состояния на <tex>{j-1}</tex>-ом шаге.  
 
 
   
 
   
'''Шаг 1.''' Заполним первый столбец матриц <tex>T_1</tex> на основании начального распределения, и <tex>T_2</tex> нулями.
+
'''Шаг 1.''' Заполним первый столбец матриц <tex>\mathtt{TState}</tex> на основании начального распределения, и <tex>\mathtt{TIndex}</tex> нулями.
  
'''Шаг 2.''' Последовательно заполняем следующие столбцы матриц <tex>T_1</tex> и <tex>T_2</tex>, используя матрицы вероятностей эмиссий и переходов.   
+
'''Шаг 2.''' Последовательно заполняем следующие столбцы матриц <tex>\mathtt{TState}</tex> и <tex>\mathtt{TIndex}</tex>, используя матрицы вероятностей эмиссий и переходов.   
  
'''Шаг 3.''' Рассматривая максимальные значения в столбцах матрицы <tex>T_2</tex>, начиная с последнего столбца, выдаем ответ.
+
'''Шаг 3.''' Рассматривая максимальные значения в столбцах матрицы <tex>\mathtt{TIndex}</tex>, начиная с последнего столбца, выдаем ответ.
 +
 
 +
'''Доказательство корректности:'''
 +
 
 +
Наиболее вероятная последовательность скрытых состояний получается следующими реккурентными соотношениями:
 +
*<tex>\mathtt{V_{1,k}} = \mathrm{P}(\mathtt{y_1} \mid \mathtt{k}) \cdot \pi_k</tex>
 +
*<tex>\mathtt{V_{t,k}} = \max\limits_{\mathtt{x} \in \mathtt{S}}\left(\mathrm{P}(\mathtt{y_t} \mid \mathtt{k}) \cdot \mathtt{A_{x,k}} \cdot \mathtt{V_{t-1,x}}\right)</tex>
 +
Где <tex>\mathtt{V_{t,k}}</tex> это вероятность наиболее вероятной последовательности, которая ответственна за первые <tex>\mathtt{t}</tex> наблюдений, у которых <tex>\mathtt{k}</tex> является завершающим состоянием. Путь Витерби может быть получен сохранением обратных указателей, которые помнят какое состояние было использовано во втором равенстве. Пусть <tex>\mathrm{Ptr}(\mathtt{k},\mathtt{t})</tex> {{---}} функция, которая возвращает значение <tex>\mathtt{x}</tex>, использованное для подсчета <tex>\mathtt{V_{t,k}}</tex> если <tex>\mathtt{t} > 1</tex>, или <tex>\mathtt{k}</tex> если <tex>\mathtt{t}=1</tex>.  Тогда:
 +
*<tex>\mathtt{x_T} = \mathtt{x} \in \mathtt{S} : \mathtt{V_{T,x}} \leadsto \max</tex>
 +
*<tex>\mathtt{x_{t-1}} = \mathrm{Ptr}(\mathtt{x_t},\mathtt{t})</tex>
  
 
== Псевдокод ==
 
== Псевдокод ==
     function viterbi <tex>(O,S,\pi\,\!,Y,A,B)</tex> //функция возвращает вектор <tex>X</tex> - последовательность номеров наиболее вероятных состояний, которые привели к данным наблюдениям.
+
Функция возвращает вектор <tex>\mathtt{X}</tex> : последовательность номеров наиболее вероятных состояний, которые привели к данным наблюдениям.
        for each state <tex>s_i</tex> do
+
     <tex>\mathrm{Viterbi}(\mathtt {O}, \mathtt {S}, \mathtt {P} , \mathtt {Y}, \mathtt {A}, \mathtt {B})</tex>
             <tex>T_1[i,1]\longleftarrow\pi[i]\,\cdot B[i,y_i]</tex>
+
        '''for''' <tex>\mathtt{j} = 1</tex> '''to''' <tex>\mathtt {K}</tex>
             <tex>T_2[i,1]\longleftarrow0</tex>
+
             <tex>\mathtt{TState}[\mathtt{j}, 1] = \mathtt{P}[\mathtt{j}] * \mathtt{B}[\mathtt{j}, \mathtt{Y}[1]]</tex>
         for <tex>i=2 .. T</tex> do
+
             <tex>\mathtt{TIndex}[\mathtt{j}, 1] = 0</tex>
             for each state <tex>s_j</tex> do
+
         '''for''' <tex>\mathtt{i} = 2</tex> '''to''' <tex>\mathtt {T}</tex>
                 <tex>T_1[j,i]\longleftarrow\max_{k}{(T_1[k,i-1]\cdot A[k,j]\cdot B[j,y_i])}</tex>  
+
             '''for''' <tex>\mathtt{j} = 1</tex> '''to''' <tex>\mathtt {K}</tex>
                 <tex>T_2[j,i]\longleftarrow\arg\max_{k}{(T_1[k,i-1]\cdot A[k,j]\cdot B[j,y_i])}</tex>  
+
                 <tex>\mathtt{TIndex}[\mathtt{j}, \mathtt{i}] = \mathtt{k} \in \mathtt{K} : (\mathtt{TState}[\mathtt{k}, \mathtt{i} - 1] * \mathtt{A}[\mathtt{k}, \mathtt{j}] * \mathtt{B}[\mathtt{j}, \mathtt{Y}[\mathtt{i}]]) \leadsto \max</tex>
         <tex>x_T\longleftarrow\arg\max_{k}{(T_1[k,T])}</tex>  
+
                 <tex>\mathtt{TState}[\mathtt{j}, \mathtt{i}] = \mathtt{TState}[\mathtt{TIndex}[\mathtt{j}, \mathtt{i}], \mathtt{i} - 1] * \mathtt{A}[\mathtt{k}, \mathtt{j}] * \mathtt{B}[\mathtt{j}, \mathtt{Y}[\mathtt{i}]]</tex>
         for <tex>i=T...2</tex> do
+
         <tex>\mathtt{X}[\mathtt{T}] = \arg\max_{1 \leqslant \mathtt{k}\leqslant \mathtt{K}} \limits (\mathtt{TState}[\mathtt{k}, \mathtt{T}])</tex>  
             <tex>x_{i-1}\longleftarrow T_2[x_i,i]</tex>
+
         '''for''' <tex>\mathtt{i} = \mathtt{T}</tex> '''downto''' <tex>2</tex>
         return <tex>X</tex>
+
             <tex>\mathtt{X}[\mathtt{i} - 1] = \mathtt{TIndex}[\mathtt{X}[\mathtt{i}], \mathtt{i}]</tex>
 +
         '''return''' <tex>\mathtt{X}</tex>
 +
Таким образом, алгоритму требуется <tex>\mathrm{O}(\mathtt{T}\times\left|{\mathtt{K}}\right|^2)</tex> времени.
 +
 
 +
== Применение ==
 +
Алгоритм используется в <tex>\mathrm{CDMA}</tex> и <tex>\mathrm{GSM}</tex> цифровой связи, в модемах и космических коммуникациях. Он нашел применение в распознавании речи и письма, компьютерной лингвистике и биоинформатике, а также в алгоритме свёрточного декодирования Витерби.
  
 +
== См. также ==
 +
*[[Скрытые Марковские модели]]
 +
*[[Алгоритм "Вперед-Назад"]]
 +
*[[Алгоритм Баума-Велша]]
  
Таким образом, алгоритму требуется <tex> O(T\times\left|{S}\right|^2)</tex> времени.
+
== Источники информации ==
 +
* [[wikipedia:Viterbi_algorithm|Wikipedia {{---}} Viterbi algorithm]]
 +
* [http://www.cs.sfu.ca/~oschulte/teaching/726/spring11/slides/mychapter13b.pdf Презентация]
  
== Ссылки ==
+
[[Категория: Дискретная математика и алгоритмы]]
*[http://en.wikipedia.org/wiki/Viterbi_algorithm  Wikipedia-Viterbi algorithm]
+
[[Категория: Марковские цепи]]
*[http://www.cs.sfu.ca/~oschulte/teaching/726/spring11/slides/mychapter13b.pdf Презентация]
+
[[Категория: Динамическое программирование]]
[[Категория: Дискретная математика и алгоритмы]][[Категория: Марковские цепи]]
 

Текущая версия на 19:17, 4 сентября 2022

История

Алгоритм Витерби (англ. Viterbi algorithm) был представлен в 1967 году для декодирования сверточных кодов, поступающих через зашумленный канал связи. В 1969 году Омура (Omura) показал, что основу алгоритма Витерби составляет оценка максимума правдоподобия, которая является популярным статистическим методом для создания статистической модели на основе данных и обеспечения оценки параметров модели (т.е. оценка неизвестного параметра максимизацией функции правдоподобия).

Определение:
Сверточный код (англ. Convolutional code ) — это корректирующий ошибки код, в котором
  1. На каждом такте работы кодера [math]\mathtt{k}[/math] символов входной полубесконечной последовательности преобразуются в [math]\mathtt{n} \gt \mathtt{k}[/math] символов выходной
  2. Также в преобразовании участвуют [math]\mathtt{m}[/math] предыдущих символов
  3. Выполняется свойство линейности (если [math]\mathtt{x}[/math] соответствует [math]\mathtt{X}[/math], а [math]\mathtt{y}[/math] соответствует [math]\mathtt{Y}[/math], то [math]\mathtt{ax} + \mathtt{by}[/math] соответствует [math]\mathtt{aX} + \mathtt{bY}[/math]).


Описание

Алгоритм Витерби позволяет сделать наиболее вероятное предположение о последовательности состояний скрытой Марковской модели на основе последовательности наблюдений.

Определение:
Путь Витерби (англ. Viterbi path) — наиболее правдоподобная (наиболее вероятная) последовательность скрытых состояний.

Предположения, которые делает алгоритм:

  1. Скрытые и наблюдаемые события должны быть последовательностью, которая упорядочена по времени.
  2. Каждое скрытое событие должно соответствовать только одному наблюдаемому.
  3. Вычисление наиболее вероятной скрытой последовательности до момента [math]\mathtt{t}[/math] зависит только от наблюдаемого события в этот момент времени и наиболее вероятной последовательности до момента [math]\mathtt{t} - 1[/math] (динамическое программирование).

Алгоритм

Входные данные:

  1. Пространство наблюдений [math]\mathtt{O} =\{\mathtt{o_1},\mathtt{o_2} \ldots \mathtt{o_N}\}[/math]
  2. Пространство состояний [math]\mathtt{S} =\{\mathtt{s_1},\mathtt{s_2} \ldots \mathtt{s_K}\}[/math]
  3. Последовательность наблюдений [math]\mathtt{Y} =\{\mathtt{y_1},\mathtt{y_2} \ldots \mathtt{y_T}\}[/math]
  4. Матрица [math]\mathtt{A}[/math] переходов из [math]\mathtt{i}[/math]-того состояния в [math]\mathtt{j}[/math]-ое, размером [math]\mathtt{K} \times \mathtt{K}[/math]
  5. Матрица эмиссии [math]\mathtt{B}[/math] размера [math]\mathtt{K} \times \mathtt{N}[/math], которая определяет вероятность наблюдения [math]\mathtt{o_j}[/math] из состояния [math]\mathtt{s_i}[/math]
  6. Массив начальных вероятностей [math]\mathtt{\pi}[/math] размером [math]\mathtt{K}[/math], показывающий вероятность того, что начальное состояние [math]\mathtt{s_i}[/math]

Выходные данные:

[math]\mathtt{X} =\{\mathtt{x_1},\mathtt{x_2} \ldots \mathtt{x_T}\}[/math] — последовательность состояний, которые привели к последовательности наблюдений [math]\mathtt{Y}[/math].

Алгоритм:

Создадим две матрицы [math]\mathtt{TState}[/math] и [math]\mathtt{TIndex}[/math] размером [math]\mathtt{K} \times \mathtt{T}[/math]. Каждый элемент [math]\mathtt{TState}[\mathtt{i},\mathtt{j}][/math] содержит вероятность того, что на [math]\mathtt{j}[/math]-ом шаге мы находимся в состоянии [math]\mathtt{s_i}[/math]. Каждый элемент [math]\mathtt{TIndex}[\mathtt{i},\mathtt{j}][/math] содержит индекс наиболее вероятного состояния на [math]\mathtt{j} - 1[/math]-ом шаге.

Шаг 1. Заполним первый столбец матриц [math]\mathtt{TState}[/math] на основании начального распределения, и [math]\mathtt{TIndex}[/math] нулями.

Шаг 2. Последовательно заполняем следующие столбцы матриц [math]\mathtt{TState}[/math] и [math]\mathtt{TIndex}[/math], используя матрицы вероятностей эмиссий и переходов.

Шаг 3. Рассматривая максимальные значения в столбцах матрицы [math]\mathtt{TIndex}[/math], начиная с последнего столбца, выдаем ответ.

Доказательство корректности:

Наиболее вероятная последовательность скрытых состояний получается следующими реккурентными соотношениями:

  • [math]\mathtt{V_{1,k}} = \mathrm{P}(\mathtt{y_1} \mid \mathtt{k}) \cdot \pi_k[/math]
  • [math]\mathtt{V_{t,k}} = \max\limits_{\mathtt{x} \in \mathtt{S}}\left(\mathrm{P}(\mathtt{y_t} \mid \mathtt{k}) \cdot \mathtt{A_{x,k}} \cdot \mathtt{V_{t-1,x}}\right)[/math]

Где [math]\mathtt{V_{t,k}}[/math] это вероятность наиболее вероятной последовательности, которая ответственна за первые [math]\mathtt{t}[/math] наблюдений, у которых [math]\mathtt{k}[/math] является завершающим состоянием. Путь Витерби может быть получен сохранением обратных указателей, которые помнят какое состояние было использовано во втором равенстве. Пусть [math]\mathrm{Ptr}(\mathtt{k},\mathtt{t})[/math] — функция, которая возвращает значение [math]\mathtt{x}[/math], использованное для подсчета [math]\mathtt{V_{t,k}}[/math] если [math]\mathtt{t} \gt 1[/math], или [math]\mathtt{k}[/math] если [math]\mathtt{t}=1[/math]. Тогда:

  • [math]\mathtt{x_T} = \mathtt{x} \in \mathtt{S} : \mathtt{V_{T,x}} \leadsto \max[/math]
  • [math]\mathtt{x_{t-1}} = \mathrm{Ptr}(\mathtt{x_t},\mathtt{t})[/math]

Псевдокод

Функция возвращает вектор [math]\mathtt{X}[/math] : последовательность номеров наиболее вероятных состояний, которые привели к данным наблюдениям.

   [math]\mathrm{Viterbi}(\mathtt {O}, \mathtt {S},  \mathtt {P} , \mathtt {Y}, \mathtt {A}, \mathtt {B})[/math]
       for [math]\mathtt{j} = 1[/math] to [math]\mathtt {K}[/math]
           [math]\mathtt{TState}[\mathtt{j}, 1] = \mathtt{P}[\mathtt{j}] * \mathtt{B}[\mathtt{j}, \mathtt{Y}[1]][/math]
           [math]\mathtt{TIndex}[\mathtt{j}, 1] = 0[/math]
       for [math]\mathtt{i} = 2[/math] to [math]\mathtt {T}[/math]
           for [math]\mathtt{j} = 1[/math] to [math]\mathtt {K}[/math]
               [math]\mathtt{TIndex}[\mathtt{j}, \mathtt{i}] = \mathtt{k} \in \mathtt{K} : (\mathtt{TState}[\mathtt{k}, \mathtt{i} - 1] * \mathtt{A}[\mathtt{k}, \mathtt{j}] * \mathtt{B}[\mathtt{j}, \mathtt{Y}[\mathtt{i}]]) \leadsto \max[/math]
               [math]\mathtt{TState}[\mathtt{j}, \mathtt{i}] = \mathtt{TState}[\mathtt{TIndex}[\mathtt{j}, \mathtt{i}], \mathtt{i} - 1] * \mathtt{A}[\mathtt{k}, \mathtt{j}] * \mathtt{B}[\mathtt{j}, \mathtt{Y}[\mathtt{i}]][/math]  
       [math]\mathtt{X}[\mathtt{T}] = \arg\max_{1 \leqslant \mathtt{k}\leqslant \mathtt{K}} \limits (\mathtt{TState}[\mathtt{k}, \mathtt{T}])[/math] 
       for [math]\mathtt{i} = \mathtt{T}[/math] downto [math]2[/math]
           [math]\mathtt{X}[\mathtt{i} - 1] = \mathtt{TIndex}[\mathtt{X}[\mathtt{i}], \mathtt{i}][/math]
       return [math]\mathtt{X}[/math]

Таким образом, алгоритму требуется [math]\mathrm{O}(\mathtt{T}\times\left|{\mathtt{K}}\right|^2)[/math] времени.

Применение

Алгоритм используется в [math]\mathrm{CDMA}[/math] и [math]\mathrm{GSM}[/math] цифровой связи, в модемах и космических коммуникациях. Он нашел применение в распознавании речи и письма, компьютерной лингвистике и биоинформатике, а также в алгоритме свёрточного декодирования Витерби.

См. также

Источники информации