title: How to modify Levenshteins Edit Distance to count "adjacent letter exchanges" as 1 edit
body: <p>I'm playing around with <a href="http://en.wikipedia.org/wiki/Levenshtein_distance">Levenshteins Edit Distance algorithm</a>, and I want to extend this to count transpositions -- that is, exchanges of adjacent letters -- as 1 edit. The unmodified algorithm counts insertions, deletes or substitutions needed to reach a certain string from another. For instance, the edit distance from "KITTEN" to "SITTING" is 3. Here's the explanation from Wikipedia:</p>
  
  <ol>
  <li>kitten → sitten (substitution of 'k' with 's')</li>
  <li>sitten → sittin (substitution of 'e' with 'i')</li>
  <li>sittin → sitting (insert 'g' at the end).</li>
  </ol>
  
  <p>Following the same method, the edit distance from "CHIAR" to "CHAIR" is 2:</p>
  
  <ol>
  <li>CHIAR → CHAR (delete 'I')</li>
  <li>CHAR → CHAIR (insert 'I')</li>
  </ol>
  
  <p>I would like to count this as "1 edit", since I only exchange two adjacent letters. How would I go about to do this? </p>