Title :
Efficient error-correcting Viterbi parsing
Author :
Amengual, Juan C. ; Vidal, Enrique
Author_Institution :
Dept. de Inf., Univ. Jaume I de Castellon, Spain
fDate :
10/1/1998 12:00:00 AM
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;
Journal_Title :
Pattern Analysis and Machine Intelligence, IEEE Transactions on