Carleton University
Technical Report TR-16
January 1983
The Noisy Substring Matching Problem
R.L. Kashyap & B.J. Oommen
Abstract
Let T(U) be the set of words in the dictionary H which contains U as a substring. The problem considered here is the estimation of the set T(U) when U is not known, . but Y, a noisy version of U is available. The suggested set estimate S*(Y) of T(U) is a proper subset of H such that its every element contains at least one substring which resembles Y most according to the Levenshtein metric. The proposed algorithm for the computation of S*(Y) requires cubic time. The algorithm uses the recursively computÂable dissimilarity measure Dk(X,Y), termed as the k-th distance between two strings X and Y which is a dissimilarity measure between Y and a certain subset of the set of contiguous susbtrings of X. Another estimate of T(U), namely SM(Y) is also suggested. The accuracy of SM(Y) is only slightly less than that of s•(Y), but the computation time of SM(Y) is substantially less than that of S*(Y). Experimental results involving 1,900 noisy substrings and dictionaries which are subsets of 1,023 most common English words [HJ indicate that the accuracy of the estimate S*(Y) is around 99 percent and that of sM(Y) is about 98 percent.