 StringTools - Maple Programming Help

Home : Support : Online Help : Programming : Names and Strings : StringTools Package : Distances and Metrics : StringTools/EditDistance

StringTools

 EditDistance
 compute the edit distance between two strings

 Calling Sequence EditDistance( s, t )

Parameters

 s - Maple string t - Maple string

Description

 • The EditDistance(s,t) command returns an integer measure of the distance between the two strings s and t.
 • The edit distance between two strings s and t, is defined to be the difference between the sum of their lengths and twice the length of the longest common subsequence of s and t. If strings s and t have respective lengths m and n, then the edit distance is defined to be $m+n-2\mathrm{length}\left(\mathrm{LongestCommonSubSequence}\left(s,t\right)\right)$. It is related to the Levenshtein metric, which is sometimes also called the edit distance.
 • For a different notion of the distance between two strings, see StringTools[HammingDistance] and StringTools[Levenshtein].
 • 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

 > $\mathbf{use}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{StringTools}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{EditDistance}\left("Mathematics","Mathematische"\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{end use}$
 ${4}$ (1)
 > $\mathrm{with}\left(\mathrm{StringTools}\right):$
 > $\mathrm{EditDistance}\left("abc","abd"\right)$
 ${2}$ (2)
 > $\mathrm{EditDistance}\left("abc","abcd"\right)$
 ${1}$ (3)
 > $\mathrm{EditDistance}\left("Elisabeth","Elyse"\right)$
 ${6}$ (4)
 > $\mathrm{EditDistance}\left("Connor","Constance"\right)$
 ${7}$ (5)

Since it is a metric, the edit distance satisfies the triangle inequality.

 > $s≔\mathrm{Random}\left(1000,'\mathrm{lower}'\right):$
 > $t≔\mathrm{Random}\left(1000,'\mathrm{lower}'\right):$
 > $u≔\mathrm{Random}\left(1000,'\mathrm{lower}'\right):$
 > $\mathrm{EditDistance}\left(s,t\right)$
 ${1352}$ (6)
 > $\mathrm{EditDistance}\left(s,u\right)+\mathrm{EditDistance}\left(u,t\right)$
 ${2746}$ (7)