Editing Viterbi algorithm (section)

== History ==
The Viterbi algorithm is named after [[Andrew Viterbi]], who proposed it in 1967 as a decoding algorithm for [[Convolution code|convolutional codes]] over noisy digital communication links.<ref>[https://arxiv.org/abs/cs/0504020v2 29 Apr 2005, G. David Forney Jr: The Viterbi Algorithm: A Personal History]</ref> It has, however, a history of [[multiple invention]], with at least seven independent discoveries, including those by Viterbi, [[Needleman–Wunsch algorithm|Needleman and Wunsch]], and [[Wagner–Fischer algorithm|Wagner and Fischer]].<ref name="slp">{{cite book |author1=Daniel Jurafsky |author2=James H. Martin |title=Speech and Language Processing |publisher=Pearson Education International |page=246}}</ref><!-- Jurafsky and Martin specifically refer to the papers that presented the Needleman–Wunsch and Wagner–Fischer algorithms, hence the wikilinks to those--> It was introduced to [[natural language processing]] as a method of [[part-of-speech tagging]] as early as 1987.

''Viterbi path'' and ''Viterbi algorithm'' have become standard terms for the application of dynamic programming algorithms to maximization problems involving probabilities.<ref name="slp" />
For example, in statistical parsing a dynamic programming algorithm can be used to discover the single most likely context-free derivation (parse) of a string, which is commonly called the "Viterbi parse".<ref>{{Cite conference | doi = 10.3115/1220355.1220379| title = Efficient parsing of highly ambiguous context-free grammars with bit vectors| conference = Proc. 20th Int'l Conf. on Computational Linguistics (COLING)| pages = <!--162-->| year = 2004| last1 = Schmid | first1 = Helmut| url = http://www.aclweb.org/anthology/C/C04/C04-1024.pdf| doi-access = free}}</ref><ref>{{Cite conference| doi = 10.3115/1073445.1073461| title = A* parsing: fast exact Viterbi parse selection| conference = Proc. 2003 Conf. of the North American Chapter of the Association for Computational Linguistics on Human Language Technology (NAACL)| pages = 40–47| year = 2003| last1 = Klein | first1 = Dan| last2 = Manning | first2 = Christopher D.| url = http://ilpubs.stanford.edu:8090/532/1/2002-16.pdf| doi-access = free}}</ref><ref>{{Cite journal | doi = 10.1093/nar/gkl200| title = AUGUSTUS: Ab initio prediction of alternative transcripts| journal = Nucleic Acids Research| volume = 34| issue = Web Server issue| pages = W435–W439| year = 2006| last1 = Stanke | first1 = M.| last2 = Keller | first2 = O.| last3 = Gunduz | first3 = I.| last4 = Hayes | first4 = A.| last5 = Waack | first5 = S.| last6 = Morgenstern | first6 = B. | pmid=16845043 | pmc=1538822}}</ref> Another application is in [[Optical motion tracking|target tracking]], where the track is computed that assigns a maximum likelihood to a sequence of observations.<ref>{{cite conference |author=Quach, T.; Farooq, M. |chapter=Maximum Likelihood Track Formation with the Viterbi Algorithm |title=Proceedings of 33rd IEEE Conference on Decision and Control |date=1994 |volume=1 |pages=271–276|doi=10.1109/CDC.1994.410918}}</ref>