Memory and time efficient Levenshtein algorithm

1. For readers who want to orient themselves in the jungle of different implementations of the edit distance: The idea of only examining relevant regions in the inner loop was first published by Esko Ukkonen (Ukkonen E. Algorithms for approximate string matching. Inf Control. 1985;64(1-3):100-18.). This type of algorithm is therefore sometimes called the “Ukkonen algorithm”.

2. The memory consumption of the function can be reduced by limiting both arrays of dist to the length of 2 * ((limit + Math.abs(n - m)) / 2 + 1) + 1 instead of using the length m + 2. The first and last elements of both arrays are initialized with the "high value". This is the "untouched" region, which now remains unchanged and no longer needs to be redefined every time the outer loop is run.
   
   To redesign the code according to these principles, the following changes are necessary (line numbers and expressions refer to the JavaScript version):
   
   a) insert after line 21:
   
   JavaScript

   var offset = Math.floor((limit + Math.abs(n - m)) / 2);

   b) replace line 22 with:
   
   JavaScript

   var dist = new Array(new Array(2 * (offset + 1) + 1), new Array(2 * (offset + 1) + 1));

   c) replace lines 24-27 with the new initialization:
   
   JavaScript

   for (var i = 1; i < dist[1 - current].length - 1; i++) {
       if (i < offset + 2) {
           dist[1 - current][i] = 0;
       } else {
           dist[1 - current][i] = i - offset - 1;
       }
   }
   dist[current][0] = 9999999;
   dist[1 - current][0] = 9999999;
   dist[current][dist[current].length - 1] = 9999999;
   dist[1 - current][dist[1 - current].length - 1] = 9999999;

   d) delete line 31
   e) delete lines 32 and 33 and replace them with:
   
   JavaScript

   if (i <= offset) {
       dist[current][offset - i + 1] = i;
   }

   f) in line 34 limit is replaced by offset
   g) after line 35 add:
   
   JavaScript

   var pos = j - (i - offset) + 1;

   h) in lines 36 to 40:
   
   • when calling dist[current] make the following replacements:
     [j] --> [pos]
[j - 1] --> [pos - 1]
   • when calling dist[1 - current] make the following replacements:
     [j] --> [pos + 1]
[j - 1] --> [pos]
   i) delete lines 43 to 46
   j) in lines 51 and 53 m is replaced by pos

3. Another possibility that Ukkonen presents is, to calculate the exact edit distance by examining only relevant regions in all cases, not just in the case where the distance is below an externally specified limit value.
   
   To do this, limit is initially set to Math.abs(n - m) + 1 within the function. Alternatively, limit can be set to 4 and, if necessary, doubled until limit is greater than or equal to Math.abs(n - m). The code from lines 22 to 50 (with or without the changes noted above) is then repeated in a loop until dists[1 - current][pos] > limit or dists[1 - current][m] > limit. Meanwhile, limit is doubled after each run of the loop. In the end dists[1 - current][pos] or dists[1 - current][m] is the exact edit distance.
   
   I found a correct implementation of Ukkonen's algorithm (written in C by Abram Connelly) that follows this approach. This was also my source for some of the ideas outlined above. In the case of other implementations of the Ukkonen algorithm circulating on the Internet, I am not sure whether they are all really correct.

4. In my opinion one should add to the comment of wtwhite regarding Myers' bit-parallel algorithm: In fact, this is faster than all variations of Wagner and Fischer's algorithm (which include Ukkonen's algorithm). But the bit-parallel approach can only be used in the special case where the cost of insertions, deletions and replacings when calculating the edit distance are identical. In contrast, with derivatives of the Wagner-Fischer algorithm it is possible to set different costs for these actions. So both have their place.

Dim fuzz As New FuzzyLogic

lblDistanceResult.Text = fuzz.Compare(txtS1.Text, txtS2.Text, NumericUpDownThreshold.Value)

Public Class FuzzyLogic
    'Dominic Turner, 14 Jun 2012 - vb.net conversion of javascript class:
    'Memory and time efficient Levenshtein algorithm By Horatiu-Andrei Stoianovici | 1 May 2012 
    'http://www.codeproject.com/Articles/362182/Memory-and-time-efficient-Levenshtein-algorithm

    Private Function GetLowest(a As Integer, b As Integer, c As Integer) As Integer
        If a > b Then
            a = b
        End If
        If a < c Then
            Return a
        End If
        Return c
    End Function

    Public Function Compare(S1 As String, S2 As String, Optional limit As Integer = 9999999) As Integer
        If S1 Is Nothing OrElse S2 Is Nothing Then
            Return 9999999
        End If

        If Math.Abs(S1.Length - S2.Length) > limit Then
            Return 9999999
        End If
        S1 = S1.ToLower
        S2 = S2.ToLower
        If S1 = S2 Then
            Return 0
        End If
        Dim n As Integer = S1.Length
        Dim m As Integer = S2.Length

        Dim dist((m + 2), (m + 2)) As Integer
        Dim current As Integer = 0
        For i = 0 To m + 1
            dist(1, i) = i
        Next
        For i = 1 To n
            Dim ok As Boolean = False
            dist(current, 0) = i
            If i - limit >= 1 Then
                dist(current, i - limit - 1) = 9999999
            End If
            For j = Math.Max(i - limit, 1) To Math.Min(i + limit, m)
                If S1.Substring(i - 1, 1) = S2.Substring(j - 1, 1) Then
                    dist(current, j) = dist(1 - current, j - 1)
                Else
                    dist(current, j) = GetLowest(dist(1 - current, j - 1), dist(1 - current, j), dist(current, j - 1)) + 1
                End If
                If dist(current, j) <= limit Then
                    ok = True
                End If
            Next
            If i + limit <= m Then
                dist(current, i + limit + 1) = 9999999
            End If
            If Not ok Then
                Return 9999999
            End If
            current = 1 - current
        Next
        If dist(1 - current, m) > limit Then
            Return 9999999
        End If
        Return dist(1 - current, m)
    End Function
End Class