editDistance

Find edit distance between two strings or documents

Syntax

d = editDistance(str1,str2)

d = editDistance(document1,document2)

d = editDistance(___,Name,Value)

Description

d = editDistance(str1,str2) returns the lowest number of grapheme (Unicode term for human-perceived characters) insertions, deletions, and substitutions required to convert str1 to str2.

d = editDistance(document1,document2) returns the lowest number of token insertions, deletions, and substitutions required to convert document1 to document2.

d = editDistance(___,Name,Value) specifies additional options using one or more name-value pair arguments.

Examples

Edit Distance Between Two Strings

Find the edit distance between the strings "Text analytics" and "Text analysis". The edit distance, by default, is the total number of grapheme insertions, deletions, and substitutions required to change one string to another.

str1 = "Text analytics";
str2 = "Text analysis";

Find the edit distance.

d = editDistance(str1,str2)

d = 
2

This means changing the first string to the second requires two edits. For example:

1. Substitution – Substitute the character "t" to an "s": "Text analytics" to "Text analysics".

2. Deletion – Delete the character "c": "Text analysics" to "Text analysis".

Edit Distance Between Two Documents

Find the edit distance between two tokenized documents. For tokenized document input, the edit distance, by default, is the total number of token insertions, deletions, and substitutions required to change one document to another.

str1 = "It's time for breakfast.";
document1 = tokenizedDocument(str1);

str2 = "It's now time to sleep.";
document2 = tokenizedDocument(str2);

Find the edit distance.

d = editDistance(document1,document2)

d = 
3

This means changing the first document to the second requires three edits. For example:

1. Insertion – Insert the word "now".

2. Substitution – Substitute the word "for" with "to".

3. Substitution – Substitute the word "breakfast" with "sleep".

Specify Cost Values

The editDistance function, by default, returns the lowest number of grapheme insertions, deletions, and substitutions required to change one string to another. To also include the swap action in the calculation, use the 'SwapCost' option.

First, find the edit distance between the strings "MATALB" and "MATLAB".

str1 = "MATALB";
str2 = "MATLAB";
d = editDistance(str1,str2)

d = 
2

One possible edit is:

1. Substitute the second "A" with "L": ("MATALB" to "MATLLB").

2. Substitute the second "L" with "A": ("MATLLB" to "MATLAB").

The default value for the swap cost (the cost of swapping two adjacent graphemes) is Inf. This means that swaps do not count towards the edit distance. To include swaps, set the 'SwapCost' option to 1.

d = editDistance(str1,str2,'SwapCost',1)

d = 
1

This means there is one action. For example, swap the adjacent characters "A" and "L".

Specify Custom Cost Function

To compute the edit distance between two words and specify that the edits are case-insensitive, specify a custom substitute cost function.

First, compute the edit distance between the strings "MATLAB" and "MathWorks".

d = editDistance("MATLAB","MathWorks")

d = 
8

This means changing the first string to the second requires eight edits. For example:

1. Substitution – Substitute the character "A" with "a". ("MATLAB" to "MaTLAB")

2. Substitution – Substitute the character "T" with "t". ("MaTLAB" to "MatLAB")

3. Substitution – Substitute the character "L" with "h". ("MatLAB" to "MathAB")

4. Substitution – Substitute the character "A" with "W". ("MathAB" to "MathWB")

5. Substitution – Substitute the character "B" with "o". ("MathWB" to "MathWo")

6. Insertion – Insert the character "r". ("MathWo" to "MathWor")

7. Insertion – Insert the character "k". ("MathWor" to "MathWork")

8. Insertion – Insert the character "s". ("MathWork" to "MathWorks")

Compute the edit distance and specify the custom substitution cost function caseInsensitiveSubstituteCost, listed at the end of the example. The custom function caseInsensitiveSubstituteCost returns 0 if the two inputs are the same or differ only by case and returns 1 otherwise.

d = editDistance("MATLAB","MathWorks",'SubstituteCost',@caseInsensitiveSubstituteCost)

d = 
6

This means the total cost for changing the first string to the second is 6. For example:

1. Substitution (cost 0) – Substitute the character "A" with "a". ("MATLAB" to "MaTLAB")

2. Substitution (cost 0) – Substitute the character "T" with "t". ("MaTLAB" to "MatLAB")

3. Substitution (cost 1) – Substitute the character "L" with "h". ("MatLAB" to "MathAB")

4. Substitution (cost 1) – Substitute the character "A" with "W". ("MathAB" to "MathWB")

5. Substitution (cost 1) – Substitute the character "B" with "o". ("MathWB" to "MathWo")

6. Insert (cost 1) – Insert the character "r". ("MathWo" to "MathWor")

7. Insert (cost 1) – Insert the character "k". ("MathWor" to "MathWork")

8. Insert (cost 1) – Insert the character "s". ("MathWork" to "MathWorks")

Custom Cost Function

The custom function caseInsensitiveSubstituteCost returns 0 if the two inputs are the same or differ only by case and returns 1 otherwise.

function cost = caseInsensitiveSubstituteCost(grapheme1,grapheme2)

if lower(grapheme1) == lower(grapheme2)
    cost = 0;
else
    cost = 1;
end

end

Input Arguments

str1 — Source string

string array | character vector | cell array of character vectors

Source string, specified as a string array, character vector, or a cell array of character vectors.

If str1 contains multiple strings, then str2 must be the same size as str1 or scalar.

Data Types: char | string | cell

str2 — Target string

string array | character vector | cell array of character vectors

Target string, specified as a string array, character vector, or a cell array of character vectors.

If str2 contains multiple strings, then str1 must be the same size as str2 or scalar.

Data Types: char | string | cell

document1 — Source document

tokenizedDocument

Source document, specified as a tokenizedDocument array.

If document1 contains multiple documents, then document2 must be the same size as document1 or scalar.

document2 — Target document

tokenizedDocument

Target document, specified as a tokenizedDocument array.

If document2 contains multiple documents, then document1 must be the same size as document2 or scalar.

Name-Value Arguments

Specify optional pairs of arguments as Name1=Value1,...,NameN=ValueN, where Name is the argument name and Value is the corresponding value. Name-value arguments must appear after other arguments, but the order of the pairs does not matter.

Before R2021a, use commas to separate each name and value, and enclose Name in quotes.

Example: editDistance("MATALB","MATLAB",'SwapCost',1) returns the edit distance between the strings "MATALB" and "MATLAB" and sets the cost to swap two adjacent graphemes to 1.

InsertCost — Cost to insert grapheme or token

1 (default) | nonnegative scalar | function handle

Cost to insert a grapheme or token, specified as the comma-separated pair consisting of 'InsertCost' and a nonnegative scalar or a function handle.

If 'InsertCost' is a function handle, then the function must accept a single input and return the cost of inserting the input to the source. For example:

• For string input to editDistance, the cost function must have the form cost = func(grapheme), where the function returns the cost of inserting grapheme into str1.

• For document input to editDistance, the cost function must have the form cost = func(token), where the function returns the cost of inserting token into document1.

Example: 'InsertCost',2

Data Types: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64 | function_handle

DeleteCost — Cost to delete grapheme or token

1 (default) | nonnegative scalar | function handle

Cost to delete grapheme or token, specified as the comma-separated pair consisting of 'DeleteCost' and a nonnegative scalar or a function handle.

If 'DeleteCost' is a function handle, then the function must accept a single input and return the cost of deleting the input from the source. For example:

• For string input to editDistance, the cost function must have the form cost = func(grapheme), where the function returns the cost of deleting grapheme from str1.

• For document input to editDistance, the cost function must have the form cost = func(token), where the function returns the cost of deleting token from document1.

Example: 'DeleteCost',2

Data Types: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64 | function_handle

SubstituteCost — Cost to substitute grapheme or token

1 (default) | nonnegative scalar | function handle

Cost to substitute a grapheme or token, specified as the comma-separated pair consisting of 'SubstituteCost' and a nonnegative scalar or a function handle.

If 'SubstituteCost' is a function handle, then the function must accept exactly two inputs and return the cost of substituting the first input with the second in the source. For example:

• For string input to editDistance, the cost function must have the form cost = func(grapheme1,grapheme2), where the function returns the cost of substituting grapheme1 with grapheme2 in str1.

• For document input to editDistance, the cost function must have the form cost = func(token1,token2), where the function returns the cost of substituting token1 with token2 in document1.

Example: 'SubstituteCost',2

Data Types: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64 | function_handle

SwapCost — Cost to swap two adjacent graphemes or tokens

Inf (default) | nonnegative scalar | function handle

Cost to swap two adjacent graphemes or tokens, specified as the comma-separated pair consisting of 'SwapCost' and a nonnegative scalar or a function handle.

If 'SwapCost' is a function handle, then the function must accept exactly two inputs and return the cost of swapping the first input with the second in the source. For example:

• For string input to editDistance, the cost function must have the form cost = func(grapheme1,grapheme2), where the function returns the cost of swapping the adjacent graphemes grapheme1 and grapheme2 in str1.

• For document input to editDistance, the cost function must have the form cost = func(token1,token2), where the function returns the cost of swapping the adjacent tokens token1 and token2 in document1.

Example: 'SwapCost',2

Data Types: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64 | function_handle

Output Arguments

d — Edit distance

nonnegative scalar | vector of nonnegative values

Edit distance returned as a nonnegative scalar or a vector of nonnegative values.

If both str1 and str2 or both document1 and document2 are scalars, then the d is scalar.

If any of str1, str2, document1, or document2 contain multiple elements, then the d is vector with the same number of elements.

Algorithms

Edit Distance

The function, by default, uses the Levenshtein distance: the lowest number of insertions, deletions, and substitutions required to convert one string to another.

For other commonly used edit distances, use these options:

Distance	Description	Options
Levenshtein (default)	lowest number of insertions, deletions, and substitutions	Default
Damerau-Levenshtein	lowest number of insertions, deletions, substitutions, and swaps	'SwapCost',1
Hamming	lowest number of substitutions only	'InsertCost',Inf,'DeleteCost',Inf

Version History

Introduced in R2019a