Abstract:In order to accelerate generation of confusion network with high quality, a fast algorithm with linear time complexity is proposed in this paper. The proposed algorithm is guided with maximum posteriori arc and only traverses the lattice one pass. Kullback-Leibler Divergence (KLD) is used to measure the similarity between two arc’s labels, which can improve the accuracy of arc alignment in the process of generating confusion network. The experimental results show that the proposed algorithm is comparable with Xue’s fast algorithm at generation speed while the quality of confusion network is significantly improved. Further improvement of the quality can be obtained by using KLD as similarity measure of arc’s labels.