WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте

Алгоритм Витерби — алгоритм поиска наиболее подходящего списка состояний (называемого путём Витерби), который в контексте цепей Маркова получает наиболее вероятную последовательность произошедших событий.

Является алгоритмом динамического программирования. Применяется в алгоритме свёрточного декодирования Витерби.

Алгоритм был предложен Эндрю Витерби в 1967 году как алгоритм декодирования свёрточного кода, передаваемого по сетям с наличием шума.[1] Алгоритм получил широкое применение в декодировании свёрточных кодов мобильных телефонов стандартов GSM и CDMA, dial-up модемах и беспроводных сетях стандарта 802.11. Также он широко используется в распознавании речи, синтезе речи, компьютерной лингвистике и биоинформатике. К примеру, при распознавании речи звуковой сигнал воспринимается как последовательность событий и строка текста есть «скрытый смысл» акустического сигнала. Алгоритм Витерби находит наиболее вероятную строку текста по данному сигналу.

Алгоритм делает несколько предположений:

  • наблюдаемые и скрытые события должны быть последовательностью. Последовательность чаще всего упорядочена по времени.
  • две последовательности должны быть выровнены: каждое наблюдаемое событие должно соответствовать ровно одному скрытому событию
  • вычисление наиболее вероятной скрытой последовательности до момента t должно зависеть только от наблюдаемого события в момент времени t, и наиболее вероятной последовательности до момента t − 1.

Алгоритм

Пусть у нас есть скрытая марковская модель с пространством состояний , начальными вероятностями нахождения в состоянии и вероятностями перехода из состояния в состояние . Пусть мы наблюдаем на выходе . Тогда наиболее вероятная последовательность состояний задается рекуррентными соотношениями:[2]

Здесь  — это вероятность наиболее вероятной последовательности состояний, ответственная за появление первых наблюдаемых символов, завершающаяся в состоянии . Путь Витерби может быть найден при помощи указателей, запоминающих, какое состояние появлялось во втором уравнении. Пусть  — функция, которая возвращает значение , использованное для подсчета , если , или если . Тогда

Здесь мы используем стандартное определение arg max.
Сложность этого алгоритма равна .

См. также

Примечания

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии