Problem 2309. Calculate the Damerau-Levenshtein distance between two strings.

Created by Jan Orwat

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:hyperlink w:docLocation=\"http://www.mathworks.co.uk/matlabcentral/cody/problems/2303-compute-hamming-distances-between-each-pair-of-rows-from-two-input-matrices\"><w:r><w:t>Problem 2303</w:t></w:r></w:hyperlink><w:r><w:t> reminded me a few older ones dealing with metrics between strings, problems</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.co.uk/matlabcentral/cody/problems/93-calculate-the-levenshtein-distance-between-two-strings\"><w:r><w:t>93</w:t></w:r></w:hyperlink><w:r><w:t>,</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.co.uk/matlabcentral/cody/problems/846-calculate-the-hamming-distance-between-two-strings\"><w:r><w:t>846</w:t></w:r></w:hyperlink><w:r><w:t> or</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.co.uk/matlabcentral/cody/problems/848-calculate-a-modified-levenshtein-distance-between-two-strings\"><w:r><w:t>848</w:t></w:r></w:hyperlink><w:r><w:t> about Hamming and Levenshtein distances.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance\"><w:r><w:t>Damerau-Levenshtein distance</w:t></w:r></w:hyperlink><w:r><w:t> is an extension to Levenshtein distance. It is also defined as minimum number of simple edit operations on string to change it into another, but the list of allowed operations is extended.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>As it is written on Wikipedia there are 4 allowed edits: deletion, insertion and substitution of an single character and an transposition of two adjacent characters.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Example. Such defined distance between words</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>gifts</w:t></w:r><w:r><w:t> and</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>profit</w:t></w:r><w:r><w:t> is 5:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[gifts => pgifts (insertion of 'p')\npgifts => prgifts (insertion of 'r')\nprgifts => proifts (substitution of 'g' to 'o')\nproifts => profits (transposition of 'if' to 'fi')\nprofits => profit (deletion of 's')]]></w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

<a href = "http://www.mathworks.co.uk/matlabcentral/cody/problems/2303-compute-hamming-distances-between-each-pair-of-rows-from-two-input-matrices">Problem 2303</a> reminded me a few older ones dealing with metrics between strings, problems <a href = "http://www.mathworks.co.uk/matlabcentral/cody/problems/93-calculate-the-levenshtein-distance-between-two-strings">93</a>, <a href = "http://www.mathworks.co.uk/matlabcentral/cody/problems/846-calculate-the-hamming-distance-between-two-strings">846</a> or <a href = "http://www.mathworks.co.uk/matlabcentral/cody/problems/848-calculate-a-modified-levenshtein-distance-between-two-strings">848</a>
 about Hamming and Levenshtein distances.<a href = "http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance">Damerau-Levenshtein distance</a> is an extension to Levenshtein distance. It is also defined as minimum number of simple edit operations on string to change it into another, but the list of allowed operations is extended.As it is written on Wikipedia there are 4 allowed edits: deletion, insertion and substitution of an single character and an transposition of two adjacent characters.Example. Such defined distance between words gifts and profit is 5:<pre class="language-matlab">gifts =&gt; pgifts (insertion of 'p')
pgifts =&gt; prgifts (insertion of 'r')
prgifts =&gt; proifts (substitution of 'g' to 'o')
proifts =&gt; profits (transposition of 'if' to 'fi')
profits =&gt; profit (deletion of 's')
</pre>

<http://www.mathworks.co.uk/matlabcentral/cody/problems/2303-compute-hamming-distances-between-each-pair-of-rows-from-two-input-matrices Problem 2303> reminded me a few older ones dealing with metrics between strings, problems <http://www.mathworks.co.uk/matlabcentral/cody/problems/93-calculate-the-levenshtein-distance-between-two-strings 93>,
<http://www.mathworks.co.uk/matlabcentral/cody/problems/846-calculate-the-hamming-distance-between-two-strings 846> or
<http://www.mathworks.co.uk/matlabcentral/cody/problems/848-calculate-a-modified-levenshtein-distance-between-two-strings 848>
 about Hamming and Levenshtein distances.

<http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance Damerau-Levenshtein distance> is an extension to Levenshtein distance. It is also defined as minimum number of simple edit operations on string to change it into another, but the list of allowed operations is extended.

As it is written on Wikipedia there are 4 allowed edits: deletion, insertion and substitution of an single character and an transposition of two adjacent characters.

Example. Such defined distance between words _gifts_ and _profit_ is 5:

gifts   => pgifts    (insertion of 'p')
  pgifts  => prgifts   (insertion of 'r')
  prgifts => proifts   (substitution of 'g' to 'o')
  proifts => profits   (transposition of 'if' to 'fi')
  profits => profit    (deletion of 's')

Solve

Solution Stats

83 Solutions
24 Solvers

Last Solution submitted on Jul 19, 2023

Last 200 Solutions

Problem Comments

4 Comments

4 Comments

Show 1 older comment

Asif Newaz on 25 Jan 2020

i am facing a problem with ur test suite 5. is it correct?
even the built-in matlab function 'edit distance' is giving the result 3.
which i believe is the correct one.
if i am not wrong, according to demarau algorithm - here transposition will not occur.

Rafael S.T. Vieira on 3 Sep 2020

Test case #5 is correct, Asif. If you want, you can try it on wolfram alpha using DamerauLevenshteinDistance['abc','ca']. Be careful, because the algorithm from wikipedia has errors.

Rafael S.T. Vieira on 3 Sep 2020

Another example that should return 2 via Damerou-Levenshtein and 3 via Levenshtein alone: 'jellyfish' and 'jellyifhs'.

Christian Schröder on 2 Dec 2022

The algorithm given by Wikipedia is correct, I think, but take note that the first algorithm Wikipedia gives does not actually compute the Damerau-Levenshtein distance, but rather a related metric. Confusing, but the entry says as much if you read it closely.

Solution Comments

Show comments

Problem Recent Solvers24

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 2309. Calculate the Damerau-Levenshtein distance between two strings.

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers24

Suggested Problems

More from this Author40

Problem Tags

Community Treasure Hunt

Problem 2309. Calculate the Damerau-Levenshtein distance between two strings.

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers24

Suggested Problems

More from this Author40

Problem Tags

Community Treasure Hunt

Players