Recognition of Noisy Subsequences Using Constrained Edit Distances
- 1 September 1987
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. PAMI-9 (5) , 676-685
- https://doi.org/10.1109/tpami.1987.4767962
Abstract
Let X* be any unknown word from a finite dictionary H. Let U be any arbitrary subsequence of X*. We consider the problem of estimating X* by processing Y, which is a noisy version of U. We do this by defining the constrained edit distance between XH and Y subject to any arbitrary edit constraint involving the number and type of edit operations to be performed. An algorithm to compute this constrained edit distance has been presented. Although in general the algorithm has a cubic time complexity, within the framework of our solution the algorithm possesses a quadratic time complexity. Recognition using the constrained edit distance as a criterion demonstrates remarkable accuracy. Experimental results which involve strings of lengths between 40 and 80 and which contain an average of 26.547 errors per string demonstrate that the scheme has about 99.5 percent accuracy.Keywords
This publication has 24 references indexed in Scilit:
- The Noisy Substring Matching ProblemIEEE Transactions on Software Engineering, 1983
- Approximate String MatchingACM Computing Surveys, 1980
- Syntactic Decision Rules for Recognition of Spoken Words and Phrases Using a Stochastic AutomatonIEEE Transactions on Pattern Analysis and Machine Intelligence, 1979
- A Sentence-to-Sentence Clustering Procedure for Pattern AnalysisIEEE Transactions on Systems, Man, and Cybernetics, 1978
- A fast algorithm for computing longest common subsequencesCommunications of the ACM, 1977
- Bounds for the String Editing ProblemJournal of the ACM, 1976
- A linear space algorithm for computing maximal common subsequencesCommunications of the ACM, 1975
- Stochastic Syntactic Decoding for Pattern ClassificationIEEE Transactions on Computers, 1975
- The String-to-String Correction ProblemJournal of the ACM, 1974
- Error bounds for convolutional codes and an asymptotically optimum decoding algorithmIEEE Transactions on Information Theory, 1967