Levenshtein edit distance Python
<p>This piece of code returns the Levenshtein edit distance of 2 terms.
How can i make this so that insertion and deletion only costs 0.5 instead of 1 ? substitution should still costs 1.</p>

<pre><code>def substCost(x,y):
   if x == y: 
      return 0
   else: 
      return 1

def  levenshtein(target, source):
   i = len(target); j = len(source)
   if i == 0:  
      return j
   elif j == 0: 
      return i

   return(min(levenshtein(target[:i-1],source)+1,
          levenshtein(target, source[:j-1])+1,
          levenshtein(target[:i-1], source[:j-1])+substCost(source[j-1],target[i-1])))
</code></pre>

<p>There are two places you need to account for the reduced cost of adding or removing a vowel. They are the <code>return j</code> and <code>return i</code> lines in the base cases of your function, and the <code>+1</code>s in the <code>min</code> call after the first two recursive calls.</p>

<p>We need to change each of those to use a "ternary" expression: <code>0.5 if ch in 'aeiou' else 1</code> in place of assuming a cost of <code>1</code> per character added or removed.</p>

<p>For the base cases, we can replace the return values with <code>sum</code> calls on a generator expression that includes the ternary expression:</p>

<pre><code>if i == 0:  
    return sum(0.5 if ch in 'aeiou' else 1 for ch in source)
elif j == 0: 
    return sum(0.5 if ch in 'aeiou' else 1 for ch in target)
</code></pre>

<p>For later cases, we can replace the <code>+1</code> with the ternary expression itself (with an index rather than the <code>ch</code> iteration variable):</p>

<pre><code>return min(levenshtein(target[:i-1],source) + (0.5 if target[-1] in 'aeiou' else 1),
           levenshtein(target, source[:j-1]) + (0.5 if source[-1] in 'aeiou' else 1),
           levenshtein(target[:i-1], source[:j-1])+substCost(source[j-1],target[i-1]))
</code></pre>

<p>If you wanted to generalize this, you could move the ternary expression out into its own function, named something like <code>addCost</code>, and call it from the code in the <code>levenshtein</code> function.</p>

python levenshtein-distance