• Javascript
  • Python
  • Go

Levenshtein Distance in VBA

The Levenshtein Distance is a commonly used algorithm in computer science, specifically in string processing and spell checking. It is used ...

The Levenshtein Distance is a commonly used algorithm in computer science, specifically in string processing and spell checking. It is used to calculate the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one string into another. In this article, we will explore how to implement the Levenshtein Distance algorithm in VBA, the programming language used in Microsoft Excel.

First, let's understand the basic concept of the Levenshtein Distance. Consider two strings, "cat" and "cut". The Levenshtein Distance between them is 1, as only one substitution (replacing "a" with "u") is required to change "cat" into "cut". Similarly, the Levenshtein Distance between "kitten" and "sitting" is 3, as three insertions (adding "s", "i", and "g" to "kitten") are needed to make it into "sitting".

Now, let's see how we can implement this algorithm in VBA. We will create a function called "LevenshteinDistance" that takes two strings as input and returns the minimum edit distance between them.

First, we need to declare variables to store the two strings and their lengths. We will also create a 2-dimensional array to store the distance values for each character comparison.


Function LevenshteinDistance(str1 As String, str2 As String) As Integer

Dim len1 As Integer

Dim len2 As Integer

Dim distArr() As Integer


Next, we need to initialize the array with the appropriate size. The number of rows will be equal to the length of the first string plus one, and the number of columns will be equal to the length of the second string plus one.


len1 = Len(str1)

len2 = Len(str2)

ReDim distArr(0 To len1, 0 To len2)


Now, we can populate the first row and column of the array with values from 0 to the length of the respective strings. This represents the base case where one of the strings is empty, and the distance between them is equal to the length of the non-empty string.


For i = 0 To len1

distArr(i, 0) = i

Next i

For j = 0 To len2

distArr(0, j) = j

Next j


After that, we can start filling the rest of the array by comparing each character of the two strings. If the characters are the same, the distance remains the same as the previous comparison. If they are different, we take the minimum of the three possible edit operations (insertion, deletion, or substitution) and add one to it.


For i = 1 To len1

For j = 1 To len2

If Mid(str1, i, 1) = Mid(str2, j, 1) Then

distArr(i, j) = distArr(i - 1, j - 1)


distArr(i, j) = WorksheetFunction.Min(distArr(i - 1, j), distArr(i, j - 1), distArr(i - 1, j - 1)) + 1

End If

Next j

Next i


Finally, we can return the value at the bottom-right corner of the array, which represents the minimum edit distance between the two strings.


LevenshteinDistance = distArr(len1, len2)

End Function


To use this function, we can call it from a VBA module or directly from a cell in Excel. For example, if we have the strings "cat" and "cut" in cells A1 and B1, respectively, we can use the function in cell C1 by typing the following formula: "=LevenshteinDistance(A1, B1)". The result will be 1, indicating that only one edit is needed to change "cat" into "cut".

In conclusion, the Levenshtein Distance algorithm is a powerful tool for comparing and measuring the similarity between two strings. By implementing it in VBA, we can easily use it in our Excel spreadsheets for various applications, such as spell checking, data cleaning, and more.

Related Articles

Top IDEs for VBA Development

VBA (Visual Basic for Applications) is a popular programming language used in the Microsoft Office Suite for creating macros and automating ...

Finding Leap Years in VBA

In Visual Basic for Applications (VBA), determining whether a given year is a leap year or not can be a useful and often necessary task. Lea...

Using a for-each loop with an array

Title: Exploring the Power of a For-Each Loop with an Array As a programmer, one of the most fundamental concepts you learn is the use of lo...