compute the edit distance between two strings - Maple Help

Online Help

All Products    Maple    MapleSim


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+n2lengthLongestCommonSubSequences,t. 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].

Examples

useStringToolsinEditDistanceMathematics,Mathematischeend use

4

(1)

withStringTools:

EditDistanceabc,abd

2

(2)

EditDistanceabc,abcd

1

(3)

EditDistanceElisabeth,Elyse

6

(4)

EditDistanceConnor,Constance

7

(5)

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

s:=Random1000,'lower':

t:=Random1000,'lower':

u:=Random1000,'lower':

EditDistances,t

1352

(6)

EditDistances,u+EditDistanceu,t

2746

(7)

See Also

string, StringTools, StringTools[Levenshtein]


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam