A Randomized Algorithm for Approximate String Matching

A Randomized Algorithm for Approximate String Matching

0.00 Avg rating0 Votes
Article ID: iaor20121015
Volume: 29
Issue: 3
Start Page Number: 468
End Page Number: 486
Publication Date: Mar 2001
Journal: Algorithmica
Authors: , ,
Keywords: matching, text processing, document retrieval
Abstract:

We give a randomized algorithm in deterministic time O(Nlog M) for estimating the score vector of matches between a text string of length N and a pattern string of length M , i.e., the vector obtained when the pattern is slid along the text, and the number of matches is counted for each position. A direct application is approximate string matching. The randomized algorithm uses convolution to find an estimator of the scores; the variance of the estimator is particularly small for scores that are close to M , i.e., for approximate occurrences of the pattern in the text. No assumption is made about the probabilistic characteristics of the input, or about the size of the alphabet. The solution extends to string matching with classes, class complements, ‘never match’ and ‘always match’ symbols, to the weighted case and to higher dimensions.

Reviews

Required fields are marked *. Your email address will not be published.