Efficient error-correcting viterbi parsing

被引：20

作者：

Amengual, JC

Vidal, E

机构：

[1] Univ Jaume 1, Unidad Predepartamental Informat, Castellon de La Plana 12071, Spain

[2] Univ Politecn Valencia, Dept Sistemas Informat & Computac, E-46071 Valencia, Spain

[3] Univ Politecn Valencia, Inst Tecnol Informat, E-46071 Valencia, Spain

来源：

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE | 1998年 / 20卷 / 10期

关键词：

error-correcting parsing; sequence alignment; Viterbi algorithm; beam search; depth-first topological sort; bucketsort; priority queues; language processing; shape recognition;

D O I：

10.1109/34.722628

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

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 Viterbilike 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.

引用

页码：1109 / 1116

页数：8

共 24 条

[1]

Aho A.V., 1974, The Design and Analysis of Computer Algorithms

[2]

AHO AV, 1990, ALGORITHMS COMPLEXIT, VA, P255

[3]

Amengual JC, 1996, ICSLP 96 - FOURTH INTERNATIONAL CONFERENCE ON SPOKEN LANGUAGE PROCESSING, PROCEEDINGS, VOLS 1-4, P841, DOI 10.1109/ICSLP.1996.607732

[4]

AMENGUAL JC, 1996, LNCS, V1121, P30

[5]

AMENGUAL JC, 1996, DSIC23296 U POL VAL

[6]

AMENGUAL JC, 1995, 6 SPAN S PATT REC IM, P218

[7] DECODING FOR CHANNELS WITH INSERTIONS, DELETIONS, AND SUBSTITUTIONS WITH APPLICATIONS TO SPEECH RECOGNITION [J].