Revision as of 16:24, 10 June 2024 edit Liz (talk \| contribs) Autopatrolled, Checkusers, Oversighters, Administrators 842,097 edits Removing link(s) to "Statistical parsing": Removing links to deleted page Statistical parsing. Tag: Twinkle ← Previous edit		Revision as of 16:48, 12 June 2024 edit undo InternetArchiveBot (talk \| contribs) Bots, Pending changes reviewers 5,674,378 edits Rescuing 4 sources and tagging 0 as dead.) #IABot (v2.0.9.5) (AManWithNoPlan - 19964 Next edit →
Line 4: The '''Viterbi algorithm''' is a [[dynamic programming]] [[algorithm]] for obtaining the [[Maximum a posteriori estimation\|maximum a posteriori probability estimate]] of the most [[likelihood function\|likely]] sequence of hidden states—called the '''Viterbi path'''—that results in a sequence of observed events. This is done especially in the context of [[Markov information source]]s and [[hidden Markov model]]s (HMM). The algorithm has found universal application in decoding the [[convolutional code]]s used in both [[CDMA]] and [[GSM]] digital cellular, [[dial-up]] modems, satellite, deep-space communications, and [[802.11]] wireless LANs. It is now also commonly used in [[speech recognition]], [[speech synthesis]], [[diarization]],<ref>Xavier Anguera et al., [http://www1.icsi.berkeley.edu/~vinyals/Files/taslp2011a.pdf "Speaker Diarization: A Review of Recent Research"] {{Webarchive\|url=https://web.archive.org/web/20160512200056/http://www1.icsi.berkeley.edu/~vinyals/Files/taslp2011a.pdf \|date=2016-05-12 }}, retrieved 19. August 2010, IEEE TASLP</ref> [[keyword spotting]], [[computational linguistics]], and [[bioinformatics]]. For example, in [[speech-to-text]] (speech recognition), the acoustic signal is treated as the observed sequence of events, and a string of text is considered to be the "hidden cause" of the acoustic signal. The Viterbi algorithm finds the most likely string of text given the acoustic signal. == History == Line 146: * {{cite book \|vauthors=Feldman J, Abou-Faycal I, Frigo M \|chapter=A fast maximum-likelihood decoder for convolutional codes \|title=Proceedings IEEE 56th Vehicular Technology Conference \|volume=1 \|pages=371–375 \|year=2002 \|doi=10.1109/VETECF.2002.1040367\|isbn=978-0-7803-7467-6 \|citeseerx=10.1.1.114.1314 \|s2cid=9783963 }} * {{cite journal \|doi=10.1109/PROC.1973.9030 \|author=Forney GD \|title=The Viterbi algorithm \|journal=Proceedings of the IEEE \|volume=61 \|issue=3 \|pages=268–278 \|date=March 1973 }} Subscription required. * {{Cite book \| last1=Press \| first1=WH \| last2=Teukolsky \| first2=SA \| last3=Vetterling \| first3=WT \| last4=Flannery \| first4=BP \| year=2007 \| title=Numerical Recipes: The Art of Scientific Computing \| edition=3rd \| publisher=Cambridge University Press \| ___location=New York \| isbn=978-0-521-88068-8 \| chapter=Section 16.2. Viterbi Decoding \| chapter-url=http://apps.nrbook.com/empanel/index.html#pg=850 \| access-date=2011-08-17 \| archive-date=2011-08-11 \| archive-url=https://web.archive.org/web/20110811154417/http://apps.nrbook.com/empanel/index.html#pg=850 \| url-status=dead }} * {{cite journal \|author=Rabiner LR \|title=A tutorial on hidden Markov models and selected applications in speech recognition \|journal=Proceedings of the IEEE \|volume=77 \|issue=2 \|pages=257–286 \|date=February 1989 \|doi=10.1109/5.18626\|citeseerx=10.1.1.381.3454 \|s2cid=13618539 }} (Describes the forward algorithm and Viterbi algorithm for HMMs). * Shinghal, R. and [[Godfried Toussaint\|Godfried T. Toussaint]], "Experiments in text recognition with the modified Viterbi algorithm," ''IEEE Transactions on Pattern Analysis and Machine Intelligence'', Vol. PAMI-l, April 1979, pp. 184–193. Line 162: * [https://github.com/xukmin/viterbi C++] * [http://pcarvalho.com/forward_viterbi/ C#] * [http://www.cs.stonybrook.edu/~pfodor/viterbi/Viterbi.java Java] {{Webarchive\|url=https://web.archive.org/web/20140504055101/http://www.cs.stonybrook.edu/~pfodor/viterbi/Viterbi.java \|date=2014-05-04 }} * [https://adrianulbona.github.io/hmm/ Java 8] * [https://juliahub.com/ui/Packages/HMMBase/8HxY5/ Julia (HMMBase.jl)] * [https://metacpan.org/module/Algorithm::Viterbi Perl] * [http://www.cs.stonybrook.edu/~pfodor/viterbi/viterbi.P Prolog] {{Webarchive\|url=https://web.archive.org/web/20120502010115/http://www.cs.stonybrook.edu/~pfodor/viterbi/viterbi.P \|date=2012-05-02 }} * [https://hackage.haskell.org/package/hmm-0.2.1.1/docs/src/Data-HMM.html#viterbi Haskell] * [https://github.com/nyxtom/viterbi Go]

Viterbi algorithm: Difference between revisions