Detailed explanation about Damerau Levenshtein Distance algorithm? I'm a fresh year Computer Science student. Our teacher gave us damerau levenshtein distance algorithm pseudo code (which he got from Wikipedia apparently) and asked us to explain how the algorithm works step by step. I've been looking around the net to find an article about that but nothing that explain how the algorithm works step by step. I tried to understand it myself but still have no idea how that works. Below is the pseudo code that he gave us :

algorithm DL-distance is
    input: strings a[1..length(a)], b[1..length(b)]
    output: distance, integer
    da := new array of |Σ| integers
    for i := 1 to |Σ| inclusive do
        da[i] := 0
    let d[−1..length(a), −1..length(b)] be a 2-d array of integers, dimensions length(a)+2, length(b)+2
    maxdist := length(a) + length(b)
    d[−1, −1] := maxdist
    for i := 0 to length(a) inclusive do
        d[i, −1] := maxdist
        d[i, 0] := i
    for j := 0 to length(b) inclusive do
        d[−1, j] := maxdist
        d[0, j] := j
    for i := 1 to length(a) inclusive do
        db := 0
        for j := 1 to length(b) inclusive do
            k := da[b[j]]
            ℓ := db
            if a[i] = b[j] then
                cost := 0
                db := j
            else
                cost := 1
            d[i, j] := minimum(d[i−1, j−1] + cost,  //substitution
                               d[i,   j−1] + 1,     //insertion
                               d[i−1, j  ] + 1,     //deletion
                               d[k−1, ℓ−1] + (i−k−1) + 1 + (j-ℓ−1)) //transposition
        da[a[i]] := i
    return d[length(a), length(b)]


I'm still trying to get the idea how it works step by step but if someone can help me I'll be very thankful.
The algorithm is based on dynamic programming. It computes a table $d[i,j]$ which stores the edit distance between $a_1\ldots a_i$ and $b_1\ldots b_j$. Although you only really need $i$ to range from $0$ to $\mathrm{length}(a)$ and $j$ to range from $0$ to $\mathrm{length}(b)$, some corner cases are handled by allowing $i=-1$ or $j=-1$ and letting the corresponding cells in the table have infinite cost (a large enough number is used instead of infinity).

The formula used to compute $d[i,j]$ given earlier parts of the table is explicitly found in the code, so I'll let you figure it out on your own.