StringTools - Maple Programming Help

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

StringTools

 HammingSearch
 find the first approximate occurrences of a string in another string
 HammingSearchAll
 find all approximate occurrences of a string in another string

 Calling Sequence HammingSearch( pattern, text, hd ) HammingSearchAll( pattern, text, hd )

Parameters

 pattern - string text - string hd - Hamming distance

Description

 • The HammingSearch(pattern, text, hd) command locates the first occurrence of a substring of the string text that is close to the string pattern in terms of its Hamming distance from pattern. Specifically, it locates the first such substring whose Hamming distance from pattern is less than or equal to hd. It returns the offset of the occurrence found, or the value $0$ if there is no substring of text that is within Hamming distance hd of pattern.
 • The HammingSearchAll(pattern, text, hd) command locates all occurrences of substrings of the string text that are within Hamming distance hd of the string pattern. An expression sequence of pairs of the form $\left[\mathrm{offset},\mathrm{dist}\right]$ is returned, where offset is the offset of the match, and dist is the Hamming distance of that match to the string pattern.
 • Note that for $\mathrm{hd}=0$, proximity searching degenerates into exact searching, for which StringTools[Search] and StringTools[SearchAll] provide faster algorithms.
 • Since small Hamming distance bounds hd are most useful in practice, the algorithm is optimized for this case. Furthermore, if $\mathrm{length}\left(\mathrm{pattern}\right)\le \mathrm{hd}$, then every possible substring of text with length equal to the length of pattern matches pattern.
 • For approximate searching using the Levenshtein metric (instead of the Hamming metric), see the StringTools[ApproximateSearch] help page.

Examples

 > $\mathrm{with}\left(\mathrm{StringTools}\right):$
 > $\mathrm{HammingSearch}\left("foo","defoe",0\right)$
 ${0}$ (1)
 > $\mathrm{HammingSearch}\left("foo","defoe",1\right)$
 ${3}$ (2)
 > $\mathrm{HammingSearch}\left("foo","defoe",2\right)$
 ${2}$ (3)
 > $\mathrm{HammingSearch}\left("foo","defoe",3\right)$
 ${1}$ (4)
 > $\mathrm{HammingSearch}\left("foo","defoe",4\right)$
 ${1}$ (5)
 > $\mathrm{HammingSearch}\left("gataa","cagataagagaa",2\right)$
 ${3}$ (6)
 > $\mathrm{HammingSearchAll}\left("gataa","cagataagagaa",2\right)$
 $\left[{3}{,}{0}\right]{,}\left[{8}{,}{1}\right]$ (7)