DocumentCode :
1437448
Title :
Efficient error-correcting Viterbi parsing
Author :
Amengual, Juan C. ; Vidal, Enrique
Author_Institution :
Dept. de Inf., Univ. Jaume I de Castellon, Spain
Volume :
20
Issue :
10
fYear :
1998
fDate :
10/1/1998 12:00:00 AM
Firstpage :
1109
Lastpage :
1116
Abstract :
The problem of error-correcting parsing (ECP) using an insertion-deletion-substitution error model and a finite state machine is examined. The Viterbi algorithm can be straightforwardly extended to perform ECP, though the resulting computational complexity can become prohibitive for many applications. We propose three approaches in order to achieve an efficient implementation of Viterbi-like ECP which are compatible with beam search acceleration techniques. Language processing and shape recognition experiments which assess the performance of the proposed algorithms are presented
Keywords :
Viterbi decoding; computational complexity; error correction; finite automata; grammars; object recognition; search problems; sorting; Viterbi algorithm; beam search; bucket sort; computational complexity; depth first topological sort; error model; error-correcting parsing; finite state machine; language processing; priority queues; sequence alignment; shape recognition; syntactic pattern recognition; Acceleration; Automata; Computational complexity; Decoding; Noise shaping; Particle beams; Pattern recognition; Shape; Stochastic processes; Viterbi algorithm;
fLanguage :
English
Journal_Title :
Pattern Analysis and Machine Intelligence, IEEE Transactions on
Publisher :
ieee
ISSN :
0162-8828
Type :
jour
DOI :
10.1109/34.722628
Filename :
722628
Link To Document :
بازگشت