# Optimizing Levenshtein Distance with nested loop

Brief illustration:

I have 2 classes - tbCustomer and tbDHN which is stored inside a list. Both contains attribute CustomerName and NPWP. I need to display the percentage of similarity between the customer in tbCustomer and tbDHN.

The algorithm that I use is Levenshtein Distance, taken from this link (the second one, which the poster claims to take ~10s for long strings). If the result of this algorithm exceeds or equal to the specified threshold, then I store the result in another list.

The only approach that I can think of is to compare them one by one, as indicated by the nested For Each. The result will be pushed to database per batch in order to save memory i.e. using BulkCopy to push the list for every 6000 matching records and then Clear the list for storing further calculation.
The whole process is placed inside Background Worker. The function UpdateProgressBar simply calls a delegate to update the UI (progress bar).

Problem description:

listCustomer contains approximately 12000 records, while the listDHN contains 50000 records. If we use the above approach, then there will be around 600 million calls of Levenshtein procedure. Current execution time is about 6 hours (includes storing the result to database which is just around 1500 records).

Is there any suggestion on how to improve its performance?

This is the main process code:

For Each tbCustomer As tbCustomer In listCustomer
If (BackgroundWorkerMatch.CancellationPending) Then
Exit Sub
End If

For Each tbDHN As tbDHN In listDHN

If tbDHN.npwp_trimmed.Length >= 5 AndAlso
tbCustomer.npwp_trimmed.Length >= 5 AndAlso
tbDHN.npwp_trimmed.Equals(tbCustomer.npwp_trimmed) Then
listResult.Add(New tbResult With {.periodedate = tbDHN.periodedate, .basenumber = tbCustomer.basenumber,
.npwpDHN = tbDHN.npwp, .npwp = tbCustomer.npwp,
.custnameDHN = tbDHN.customername, .custname = tbCustomer.customername,
.similarityPercent = 100, .similarityBy = "NPWP"})
Else
' We need to match single words with single words as well. Likewise, multiple words with multiple words as well.
' Previous implementation is rather flawed. Multiple words can be compared with single words.
If (tbCustomer.isSingleWord AndAlso tbDHN.isSingleWord) OrElse
(Not tbCustomer.isSingleWord AndAlso Not tbDHN.isSingleWord) Then
Dim result = LevenshteinDistance(tbCustomer.customername_excluded, tbDHN.customername_excluded)
If result >= possibility Then
listResult.Add(New tbResult With {.periodedate = tbDHN.periodedate, .basenumber = tbCustomer.basenumber,
.npwpDHN = tbDHN.npwp, .npwp = tbCustomer.npwp,
.custnameDHN = tbDHN.customername, .custname = tbCustomer.customername,
.similarityPercent = result, .similarityBy = "CustomerName"})
End If
End If
End If
countProgressBar += 1 : lineNo += 1
UpdateProgressBar(ProgressBarMatch, If(countProgressBar = 0, 0, (countProgressBar / countMax) * 100))
If lineNo Mod 10 = 0 Then Application.DoEvents()
If listResult.Count Mod 6000 = 0 Then PushToDatabase()
Next
Next


This is the structure of tbDHN and tbCustomer:

Private Class tbDHN
Public Property periodedate As String
Public Property npwp As String
Public Property npwp_trimmed As String
Public Property customername As String
Public Property customername_excluded As String
Public Property isSingleWord As Boolean
End Class
Private Class tbCustomer
Public Property basenumber As String
Public Property npwp As String
Public Property npwp_trimmed As String
Public Property customername As String
Public Property customername_excluded As String
Public Property isSingleWord As Boolean
End Class