Find the minimum edit distance between two strings

Question

Explanation

The edit distance between two strings is a function of the minimum possible number of insertions, deletions, or substitutions to convert one word into another word.

Insertions and deletions cost 1, and substitutions cost 2.

For example, the distance between AB and A is 1, because deletions cost 1 and the only edit needed is the deletion of the B character.

The distance between CAR and FAR is 2, because substitutions cost 2. Another way to look at this is one deletion and one insertion.

Rules

Given two input strings (supplied however is convenient in your language), your program must find the minimum edit distance between the two strings.

You may assume that the strings only contain the characters A-Z and have fewer than 100 characters and more than 0 characters.

This is code golf, so the shortest solution wins.

Sample Test Cases

ISLANDER, SLANDER
> 1
MART, KARMA
> 5
KITTEN, SITTING
> 5
INTENTION, EXECUTION
> 8

Answer 1

brainfuck, 2680

+>>>>>>>>>>>>>>>>>>>>>>++++++>,<[->-----<]>--[+++++++++++++++++++++
+++++++++++>>[->>+<<]>>+<<,--------------------------------]>>[-<<<
+>>>]<<<<[>[-<<+>>]<<<]>[-<<<<<+>>>>>]>[>>],----------[++++++++++>>
[->>+<<]>>+<<,----------]>>[-<<<+>>>]<<<<[>[-<<+>>]<<<]>[-<<+>>]<<[
-<+>>+<]<<<[->+<]>[-<+>>>>+<<<]>>>[-<+>]<[->+>+<<]<[-<+>]<[->+>+<<]
<[-<+>>+<]<[->+<]>>>>>>[-[->>+<<]<<[->>+<<]<<[->>+<<]>>>>>>]<<[->>+
>+<<<]>>>[-<<<+>>>]<[->>+[->+>+<<]<<[->>+<<]>>]>>[-]<[<<]<<<+[->>>+
<<<]>>>[-<+<<+>>>]<<<<<[->>[->>>>[->>+<<]<<[->>+<<]<<[->>+<<]<<[->>
+<<]>>>>]>>[->>>>+<<<<]>>>>[-<<<<+<<+>>>>>>]<<+[->>+<<]>>[-<<+<+>>>
]<<<<<<<<]>>[-]>>[-]>>[-]-[+<<-]+>>>>>>>>>>>>>>>>>[-<+>]<[->+<<<<+>
>>]<<<[->>>>>>[-<+>]<[->+<<<<+>>>]<<<<<<<[-]<<+>>>>>>[-<<<<+>>>>>>>
>>>[-<+>]<[->+>+<<]<<<<<<<<<[->+<]>[->>>>>>>>+<<<<<<<<<+>]<<<[->+<]
>[->>>>>>>>+<<<<<<<<<+>]>>>>>>>>>[-<<<<<+>>>>>]<<<<<[->>+>>>+<<<<<]
>>>>>>>>[-[->>+<<]<<[->>+<<]<<[->>+<<]<<[->>+<<]>>>>>>>>]<<<<<<+>>-
[-<<[-<<<<+>>>>]<<<<[->>+>>+<<<<]>>[->>>>>>[->>+<<]<<[->>+<<]<<[->>
+<<]<<[->>+<<]>>]>>>>]>>[->>+<<]>>[-<<+>>>>+<<]->>-[-[->>+<<]>>]>[-
>+<]>[-<+>>>+<<]<<<[->+<]>[-<+>>>+<<]+[->>[-<<+>>]>>[-<<+>>]<<<<<<+
]<<<<<<[->>>>>>+<<<<<<]>>>>>>>>[-<<<<<<<<+>>>>>>>>]<<<<[->>>>+<<<<]
-<<[-]>>>>>>>>[-<<<<<<<<+>>>>>>>>]<<<<[->>[->>+<<]<<[->>+<<]>>]>>-[
-[->>+<<]>>]<[->+<]>[-<+>>>+<<]+[->>[-<<+>>]<<<<+]>>[-<<+>>]<<<<<<<
<-[+>>[-<<+>>]>>[-<<+>>]>>[-<<+>>]<<<<<<<<-]+>>>[-]<[->+<]>>>[-]<[-
>+<]>>>[-]<[->+<]>>>[->+<]>[-<+>>>>>>>>>>>>>+<<<<<<<<<<<<]>>>>>>>>>
>>>-[-[->>+<<]>>]>[->+<]>[-<+<+>>]<<<<-[+>>[-<<+>>]<<<<-]+>>[-<+>]>
>>>>>>>>[->+<]>[-<+>>>>>>>>>>>+<<<<<<<<<<]>>>>>[->+<]>[-<+>>>>>+<<<
<]>>>>-[-[->>+<<]>>]>[->+<]>[-<+<+>>]<<<<-[+>>[-<<+>>]<<<<-]+>[->-<
]>[-<[-]+>]<[->>>+<<<]>>>[-<<+<+>>>]<<-[+>[->+<]<]<[->>+<-[[-]>[->+
<]>[-<+>>>+<<]+>>[-<<[-]>>]<[->+<]>[-<+>>>+<<]+>>[-<<[-]>>]<[->+<]>
[-<+>>>+<<]+>>[-<<[-]>>]<<[-<<[-]+>>]<<[-<<[-]+>>]<<[-<<[-]+>>]<<<+
>->->>->>-<<<<<]<[->+<]]>[-<+>]>>[-<<<+>>>]<<<[->>>>>>>>>>>>>+<<<<<
<<<<<<<<]>>>>>>>>[->+<]>[-<+>>>>>>>>>+<<<<<<<<]>[->+<]>[-<+>>>>>>>>
>+<<<<<<<<]>>>>>>>>>[->>>+<<<]>>>[-<<+<+>>>]<<<<<[->>>>>+<<<<<]>>>>
>[-<<<<<+<<<+>>>>>>>>]<<<<<<<<+>>>>>>[-[->>+<<]<<[->>+<<]<<[->>+<<]
<<[->>+<<]<<[->>+<<]>>>>>>>>>>]<<<<[-<<[-<<<<<<+>>>>>>]<<<<<<[->>+>
>>>+<<<<<<]>>[->>>>>>>>[->>+<<]<<[->>+<<]<<[->>+<<]<<[->>+<<]<<[->>
+<<]>>]>>>>>>]<<[-]<<[->>>>+<<<<]>>>>>>[-[->>+<<]<<[->>+<<]>>>>]<<[
->>>>>+<<<<<]-[+<<-]+>>>>>>>>>>>>>>>]<<]>>>>>>>>[->+<]<<[->+<]<<[->
+<]>>>>>[-[->>+<<]<<[->>+<<]<<[->>+<<]>>>>>>]<<<<[->>[->>>>+<<<<]>>
>>[-<<+<<+>>>>]<<+[-[->>+<<]<<[->>+<<]<<[->>+<<]>>>>>>]<<<<]>>[-[->
>+<<]>>]>>>>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>>>[->-[>+>>]>
[+[-<+>]>+>>]<<<<<]>[-]<++++++[->++++++++[->+>+<<<<+>>]<]>>>.<.<<<.

Using dynamic programming, of course.

Input strings should be separated by a space, and followed by a new line. For example:

INTENTION EXECUTION
008

Answer 2

Brachylog (v2), 14 bytes

⟨⊇⊆⟩jg;?clᵐ-ˡṅ

Try it online!

This question has a surprising lack of golfing language solutions (there's an APL solution, which is a quasi-golfing language, but it doesn't beat the builtin-based solutions). So here's an attempt to get the ball rolling on that.

I'm not really happy with the golfiness of this; there's a lot of plumbing, as is so often the case when a Brachylog answer takes multiple inputs. In order to comprehensively beat the builtin-based solutions, ideally someone would come up with an answer that's shorter than the word "Levenshtein". Anyone feel like giving that a go?

Explanation

⟨⊇⊆⟩jg;?clᵐ-ˡṅ
⟨  ⟩             Find a value that is related to the first and second inputs:
 ⊇                 {the first input} is a non-continguous superstring of it
  ⊆                it is a non-contiguous substring of {the second input}
    j            Concatenate that value to itself
     g           Form a singleton list containing that value
      ;?c        Append the inputs to that list
         lᵐ      Take the length of each of the three elements
           -ˡ    Left fold by subtraction
             ṅ   Multiply the result by -1

The real work is done by the ⟨⊇⊆⟩ at the start, which finds the longest common subsequence of the two inputs (as specified, it just asks for any subsequence, but Brachlog's default tiebreaks will always pick the longest). Let's call the length of this q, and the lengths of the inputs a and b. The edit distance is then equal to a-q+b-q; to edit one into the other, we need to delete from one until we reach the common subsequence, then insert until we reach the other (when editing with insertions and deletions, the order doesn't matter).

After our ⟨⊇⊆⟩, the current implicit variable is a string of length q. Doubling this with j gives us a string of length 2q. After bringing the inputs back into our working value, we have three strings, of lengths [2q, a, b], and can replace these with their lengths. Reducing by subtraction then gives 2q-a-b = -(a-q+b-q), so we simply need to negate the answer to get the edit distance.

Answer 3

Python, 138 148 152 characters

Ok, I knew the principle but had never implemented edit distance before, so here goes:

x,y=raw_input().split()
d=range(99)
for a in x:
 c=d;d=[d[0]+1]
 for b,p,q in zip(y,c[1:],c):d+=[min(d[-1]+1,p+1,q+2*(a!=b))]
print d[-1]

Answer 4

R 51

This reads in two lines from the user (which are the input) and then just uses the adist function to calculate the distance. Since substitutions cost 2 for this problem we need to add a named vector for the costs parameter for adist. Since there is also a counts parameter for adist we can only shorten costs to cos so we still have a unique match for the parameter names.

x=readLines(n=2);adist(x[1],x[2],cos=c(i=1,d=1,s=2))

Example use

> x=readLines(n=2);adist(x[1],x[2],cos=c(i=1,d=1,s=2))
MART
KARMA
     [,1]
[1,]    5

Answer 5

PHP, 40

Follows the rules as stated, but not the spirit of the rules:

<?=levenshtein($argv[1],$argv[2],1,2,1);

Takes it's two parameters as arguments. Example calling: php edit_dist.php word1 word2.
Normally levenshtein() considers a substitution as one operation, but it has an overloaded form where the insert/sub/delete weights can be specified. In this case, its 1/2/1.

Answer 6

APL (90 characters)

⊃⌽({h←1+c←⊃⍵⋄d←h,1↓⍵⋄h,(⊂⍵){y←⍵+1⋄d[y]←⍺{h⌷b=⍵⌷a:⍵⌷⍺⋄1+d[⍵]⌊y⌷⍺}⍵}¨⍳x}⍣(⊃⍴b←,⍞))0,⍳x←⍴a←,⍞

I'm using Dyalog APL as my interpreter, with ⎕IO set to 1 and ⎕ML set to 0. The direct function ({ ... }) computes, given a row as input, the next row in the distance matrix. (It is started with the initial row: 0,⍳x.) The power operator (⍣) is used to nest the function once for each character in the second string (⊃⍴b). After all of that, the final row is reversed (⌽), and its first element is taken (⊃).

Example:

      ⊃⌽({h←1+c←⊃⍵⋄d←h,1↓⍵⋄h,(⊂⍵){y←⍵+1⋄d[y]←⍺{h⌷b=⍵⌷a:⍵⌷⍺⋄1+d[⍵]⌊y⌷⍺}⍵}¨⍳x}⍣(⊃⍴b←,⍞))0,⍳x←⍴a←,⍞
LOCKSMITH
BLACKSMITH
3
      ⊃⌽({h←1+c←⊃⍵⋄d←h,1↓⍵⋄h,(⊂⍵){y←⍵+1⋄d[y]←⍺{h⌷b=⍵⌷a:⍵⌷⍺⋄1+d[⍵]⌊y⌷⍺}⍵}¨⍳x}⍣(⊃⍴b←,⍞))0,⍳x←⍴a←,⍞
GATTTGTGACGCACCCTCAGAACTGCAGTAATGGTCCAGCTGCTTCACAGGCAACTGGTAACCACCTCATTTGGGGATGTTTCTGCCTTGCTAGCAGTGCCAGAGAGAACTTCATCATTGTCACCTCATCAAAGACTACTTTTTCAGACATCTCCTGTAG
AAGTACTGAACTCCTAATATCACCAATTCTTCTAAGTTCCTGGACATTGATCCGGAGGAGGATTCGCAGTTCAACATCAAGGTAAGGAAGGATACAGCATTGTTATCGTTGTTGAGATATTAGTAAGAAATACGCCTTTCCCCATGTTGTAAACGGGCTA
118

Answer 7

Husk, 10 9 bytes

Lṁ-→FnmṖ¹

Try it online!

Inspired by ais523's Brachylog solution, finds the longest common (not necessarily contiguous) subsequence and subtracts it from each string.

I don't like having to repeat Ṗ twice and having to explicitly refer to the two arguments ¹ and ³, but I couldn't find any shorter alternative. Now I'm happy :)

Explanation

Lṁ-→FnmṖ¹     Input: a list containing the two strings
       Ṗ      Get all possible subsequences
      m ¹      for each string
    Fn        Keep only the common ones
   →          Get the last one (which will be the longest)
  -           and subtract it
 ṁ            from each of the inputs, then concatenate the remaining characters
L             Find the length of this

Subtracting the longest common substring for each input results in the lists of characters that need to be deleted/inserted. We concatenate these two lists and get the length to calculate the edit distance.

Answer 8

Jelly, 10 bytes

ŒP€f/ṪLạẈS

Try it online!

A port to Jelly of my Brachylog answer, saving a few bytes through more convenient plumbing and some convenient builtins (and beating the builtin-based practical language answers by being shorter than the word "Levenshtein"). This is a function submission (although it also works as a full program), taking a list of the two strings.

The algorithm is the same: find the longest common subsequence of the two strings, then add together the differences in lengths between the common subsequence and each of the two original strings.

An odd side effect of this algorithm is that it seems to give an internally consistent definition of the edit difference between three or more strings, as well. I'm not sure if that would be useful for anything, but it's nice to know it exists.

Explanation

ŒP€f/ṪLạẈS
  €          On each of the original strings
ŒP             produce all possible subsequences of the string;
   f         take the list of common elements
    /          between the first and second sets of subsequences;
      L      take the length of
     Ṫ         the last of these common elements;
       ạ     take the absolute differences between that and
        Ẉ      the length of each {of the original strings}
         S   and sum them.

Shoutouts to Ẉ here for having an implied "each" in it, thus ensuring that Jelly implicitly finds the correct thing to take the length of (if you write L, "length", rather than Ẉ, "length of each", you get the number of strings you started with which is not helpful).

Jelly sorts the subsequences in order from shortest to longest, and f returns its output in the same order as in its left argument, so the Ṫ is guaranteed to find the longest subsequence. We can save any need to subtract from 0 (like the Brachylog submission does), because we have access to an absolute-difference builtin.

Answer 9

Smalltalk (Smalltalk/X), 34

I am lucky - the standard "String" class already contains levenshtein:

input a, b:

a levenshteinTo:b s:2 k:2 c:1 i:1 d:1

(the additional parameters allow for different weights on substitution, deletion, etc.)

Test run:

#( 'ISLANDER'  'SLANDER' 
   'MART'      'KARMA'   
   'KITTEN'    'SITTING' 
   'INTENTION' 'EXECUTION'  
) pairWiseDo:[:a :b|
    a print. ' ' print. b print. ' ' print.
    (a levenshteinTo:b
            s:2 k:2 c:1 i:1 d:1) printCR.
].

->

ISLANDER SLANDER 1
MART KARMA 5
KITTEN SITTING 5
INTENTION EXECUTION 8

Answer 10

Husk, 23 22 21 bytes

`-L+¹³*2▲mλΣz=←¹→)¤*Q

Try it online!

`-+L¹L³*2▲mλΣz=←¹→)¤*Q
`-                      # reversed minus: a-b
  +L¹L³                 # a = length of arg1 + length of arg2
       *2               # b = 2x
         ▲              # maximum value of
          m             # map function to all elements of list
           λ            # function:
            Σ           # sum of
             z=         # elements that are equal between
               ←¹       # sublist 1 and
                 →)     # sublist 2
                    *   # list: cartesian product of
                   ¤ Q  # all sublists of arg1 and arg2

Answer 11

Ruby 1.9, 124

l=->a,b{a[0]?b[0]?[(a[0]==b[0]?-1:1)+l[a[1..-1],b[1..-1]],l[a[1..-1],b],l[a,b[1..-1]]].min+1: a.size: b.size}
puts l[*ARGV]

Golfed version of the slow, recursive Ruby method here, modified to double the weight for substitutions. The fact that it takes 7 characters to remove the first character of a string really hurts, and it'd be cool to replace (a[0]==b[0]?-1:1) with something like -1**a[0]<=>b[0] but the order of operations is not my friend.