StringTools - Maple Programming Help

Home : Support : Online Help : Programming : Names and Strings : StringTools Package : Pattern Matching : StringTools/ApproximateSearch

StringTools

 ApproximateSearch
 find the first approximate occurrences of a string in another string
 ApproximateSearchAll
 find all approximate occurrences of a string in another string

 Calling Sequence ApproximateSearch( pattern, text, k ) ApproximateSearchAll( pattern, text, k )

Parameters

 pattern - string; pattern text - string; text to search k - non-negative integer; maximum edit distance

Description

 • The ApproximateSearch(pattern, text, k) command locates the first occurrence of a substring of the string text that is close to the string pattern in terms of its Levenshtein distance from pattern. Specifically, it locates the first such substring whose Levenshtein distance from pattern is less than or equal to k.
 • The ApproximateSearchAll(pattern, text, k) command locates all occurrences of substrings of the string text that are within Levenshtein distance k of the string pattern. An expression sequence of offsets marking the ends of matches is returned.
 • Note that for $k=0$, approximate searching degenerates into exact searching, for which StringTools[Search] and StringTools[SearchAll] provide faster algorithms.
 • If $\mathrm{length}\left(\mathrm{pattern}\right)\le k$, then every possible substring of text with length equal to the length of pattern matches pattern.
 • For a related concept that uses the Hamming metric instead of the edit distance, see StringTools[HammingSearch].
 • All of the StringTools package commands treat strings as (null-terminated) sequences of $8$-bit (ASCII) characters.  Thus, there is no support for multibyte character encodings, such as unicode encodings.

Examples

 > $\mathrm{with}\left(\mathrm{StringTools}\right):$
 > $\mathrm{ApproximateSearch}\left("foo","defoe",0\right)$
 ${0}$ (1)
 > $\mathrm{ApproximateSearch}\left("foo","defoe",1\right)$
 ${4}$ (2)
 > $\mathrm{ApproximateSearch}\left("foo","defoe",2\right)$
 ${3}$ (3)
 > $\mathrm{ApproximateSearch}\left("foo","defoe",3\right)$
 ${1}$ (4)
 > $\mathrm{ApproximateSearch}\left("foo","defoe",4\right)$
 ${1}$ (5)
 > $\mathrm{ApproximateSearch}\left("gataa","cagataagagaa",2\right)$
 ${5}$ (6)
 > $\mathrm{ApproximateSearchAll}\left("gataa","cagataagagaa",2\right)$
 ${5}{,}{6}{,}{7}{,}{8}{,}{9}{,}{11}{,}{12}$ (7)