Previous [1] [2 ] 3 [4] [5] [6] [7] [8 ]

Journal of Inforamtion Science and Engineering, Vol.8 No.4, pp.541-565 (December 1992)
Modified Earley parsing and MPM Method
for Attributed Grammar and Seismic Pattern Recognition

Kou-Yuan Huang and Dar-Ren Leu*
Department of Computer and Information Science
National Chiao Tung University
Hsinchu, Taiwan, R.O.C.
*Department of Computer Science
University of Houston
Houston, TEXAS 77004, U.S.A.

Two methods of parsing attributed string are proposed. One is the modified error-correcting Earley parsing, and the other is a parsing using the match primitive measure (MPM).

        The computation of the match primitive measure between two attributed strings using dynamic programming is proposed. The modified minimum distance errorcorrecting Earley parsing algorithm and the MPM parsing algorithm for an attributed string can handle three type of error. The MPM parsing algorithm is obtained from the computation between the input string and the string generated by the attributed grammar. The MPM parsing is more efficient than the modified Earley parsing. The recognition criterion of the modified Earley algorithm is "minimum-distance," and the recognition criterion of the MPM parsing algorithm is "maximum-matching." The parsing methods are applied to the recognition of seismic Ricker wavelets and the recognition of wavelets in real seismic data.

Keywords: inference of attributed grammar, attributed string, similarity measure, earley parsing, match primitive measure, levenshtein distance, seismic pattern recognition

Received November 14, 1991; revised January 5, 1993.
Communicated by Wen-Tsuen Chen.