StringTools - Maple Programming Help

Home : Support : Online Help : Programming : Names and Strings : StringTools Package : String Homology Routines : StringTools/Levenshtein

StringTools

 Levenshtein
 compute the Levenshtein distance between two strings

 Calling Sequence Levenshtein( s, t )

Parameters

 s - Maple string t - Maple string

Description

 • The Levenshtein( s, t ) command returns an integer measure of the distance between the two strings s and t.
 • This distance measure is also known as the edit distance between the strings. It counts the number of edit operations of the following kinds needed to transform the first string into the second.
 • There are three kinds of edit operations: insertions, deletions, and substitutions. The Levenshtein distance formula assigns each edit operation a weight equal to $1$, and computes the length of the shortest sequence of edits needed to transform one string into the other.
 • 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{Levenshtein}\left("Mathematics","Mathematische"\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{end use}$
 ${3}$ (1)
 > $\mathrm{with}\left(\mathrm{StringTools}\right):$
 > $\mathrm{Levenshtein}\left("abc","abd"\right)$
 ${1}$ (2)
 > $\mathrm{Levenshtein}\left("abc","bca"\right)$
 ${2}$ (3)
 > $\mathrm{Levenshtein}\left("brad","angelina"\right)$
 ${8}$ (4)
 > $\mathrm{Levenshtein}\left(\mathrm{Random}\left(100,'\mathrm{alnum}'\right),\mathrm{Random}\left(100,'\mathrm{alnum}'\right)\right)$
 ${96}$ (5)