Fuzzy Matching - new version plus explanation

[al_b_cnu]

It has been a while since I originally posted my Fuzzy matching UDF’s on the board, and several variants have appeared subsequently.

I thought it time to ‘put the record straight’ & post a definitive version which contains slightly more efficient code, and better matching algorithms, so here it is.

Firstly, I must state that the Fuzzy matching algorithms are very CPU hungry, and should be used sparingly. If for instance you require to lookup a match for a string which starts with, contains or ends with a specified value, this can be performed far more efficiently using the MATCH function:

Fuzzy Examples.xls
	A	B	C	D	E
1			Starts With	Ends	Contains
2			Bill	jelen	Bill
3	Mr Bill Jelen		4	3	3
4	Bill Jelen
5	Joe Bloggs
6	Fred Smith
MATCH Example

... Continued ...

 

[al_b_cnu]

Hi Gissyjr,
The first post of this (very long) thread states that these functions are very CPU hungry, and I suspect that I'd have to give you the same answer as I gave senorlinguini.

if we 'normalised' your data could it be possible that we'd get an exact match for, say, 50% of your data? If so, we'd definitely be able to see some performance improvements.
By 'Normalised I mean, for example, convert both strings to be compared to all uppercase with all non alphanumeric characters removed, or if the strings to be compared are sentences, remove common words such as 'the', 'and' etc.
Failing that, a macro approach may be the answer, but not necessarily.
Can you send more details, possibly via PM?

Senorlinguini I haven't forgotten you, I've been a little busy over the past few days, nearly there, but so far, performance improvements haven't been too apparent
I'll do a little more work on it tonight.

Alan

 

[al_b_cnu]

Hi SenorLinguini,

First the Good news:
This macro will run faster than callin g the UDF 17,000 times:

Option Explicit
Const msDB1SheetName As String = "DB1"
Const msDB2SheetName As String = "DB2"

Const miDB1PropResultCol As Integer = 2
Const miDB1PropNameCol As Integer = 4
Const miDB1CityResultCol As Integer = 5
Const miDB1CityNameCol As Integer = 7
Const miDB2PropNameCol As Integer = 4
Const miDB2CityNameCol As Integer = 7

Const msngNAPercent As Single = 0.05

'-- Constant to define progress update intervals.
'-- If >=1, treat as a number of rows
'-- If < 1, treat as a percentage
Const msngProgressUpdateInterval As Single = 1

Sub GetMatches()
Dim datTimeStamp1 As Date
Dim datTimeStamp2 As Date
Dim iEndCol As Integer
Dim lEndRow As Long
Dim lStartDataRow As Long
Dim lDataRow As Long
Dim lLookupRow As Long
Dim lBestMatchRow As Long
Dim lNextProgressUpdateRow As Long
Dim lProgressInterval As Long
Dim sDB1Range As String
Dim sCurDataItem As String
Dim sCurLookupItem As String
Dim sngCurMatch As Single
Dim sngBestMatch As Single
Dim vaLookup As Variant
Dim vaData As Variant
Dim vaResponses As Variant
Dim wsDB1 As Worksheet
Dim wsDB2 As Worksheet

Set wsDB1 = Sheets(msDB1SheetName)
Set wsDB2 = Sheets(msDB2SheetName)

'-- Get lookup table into array
vaLookup = wsDB2.Range("A1:B" & wsDB2.UsedRange.Rows.Count).Value

iEndCol = WorksheetFunction.Max(miDB1CityNameCol, _
                                miDB1PropNameCol, _
                                miDB1PropResultCol, _
                                miDB1CityResultCol)
lEndRow = wsDB1.Cells(Rows.Count, miDB1PropNameCol).End(xlUp).Row

lStartDataRow = wsDB1.Cells(Rows.Count, miDB1PropResultCol).End(xlUp).Row + 1

'lProgressInterval = lEndRow / 100
If msngProgressUpdateInterval < 1 Then
    lProgressInterval = Int((lEndRow - 1) * msngProgressUpdateInterval)
Else
    lProgressInterval = Int(msngProgressUpdateInterval)
End If

lNextProgressUpdateRow = 2

sDB1Range = "A1:" & wsDB1.Cells(lEndRow, iEndCol).Address
vaData = wsDB1.Range(sDB1Range).Value

Application.ScreenUpdating = False
datTimeStamp1 = Now()
For lDataRow = lStartDataRow To UBound(vaData, 1)
    
    sngBestMatch = 0
    lBestMatchRow = 0
    sCurDataItem = UCase$(WorksheetFunction.Trim(CStr(vaData(lDataRow, miDB1PropNameCol)) & _
                         " " & _
                         CStr(vaData(lDataRow, miDB1CityNameCol))))
    For lLookupRow = 2 To UBound(vaLookup, 1)
        sCurLookupItem = UCase$(WorksheetFunction.Trim(CStr(vaLookup(lLookupRow, 1)) & _
                             " " & _
                             CStr(vaLookup(lLookupRow, 2))))
        sngCurMatch = FuzzyPercent(String1:=sCurDataItem, _
                                   String2:=sCurLookupItem, _
                                   Algorithm:=2, _
                                   Normalised:=True)
        If sngCurMatch > msngNAPercent Then
            If sngCurMatch > sngBestMatch Then
                sngBestMatch = sngCurMatch
                lBestMatchRow = lLookupRow
                If sngCurMatch = 1 Then Exit For
            End If
        End If
    Next lLookupRow
    
    If lBestMatchRow <> 0 Then
        wsDB1.Cells(lDataRow, miDB1PropResultCol).Value = wsDB2.Cells(lBestMatchRow, 1).Value
        wsDB1.Cells(lDataRow, miDB1CityResultCol).Value = wsDB2.Cells(lBestMatchRow, 2).Value
    Else
        wsDB1.Cells(lDataRow, miDB1PropResultCol).Value = CVErr(xlErrNA)
        wsDB1.Cells(lDataRow, miDB1CityResultCol).Value = CVErr(xlErrNA)
    End If
    
    If lDataRow >= lNextProgressUpdateRow Then
        With Application
            .ScreenUpdating = True
            datTimeStamp2 = Now()
            Application.StatusBar = "Processed row " & lDataRow & " of " & lEndRow & _
                                    " - " & Format(lDataRow / lEndRow, "0.0%") & " complete" & _
                                    ": " & Format(datTimeStamp2 - datTimeStamp1, "hh:mm:ss") & " elapsed"
            lNextProgressUpdateRow = lDataRow + lProgressInterval
        .ScreenUpdating = False
        End With
    End If
    
Next lDataRow

With Application
    .StatusBar = False
    .ScreenUpdating = True
End With
End Sub

Ok, now the bad:
I estimate that it takes 29 seconds to process each row.
So for 17535 of them it takes 508515 seconds or 141 hours or 5.9 days
This can be slightly mitigated by the fact you can break into the code at any time ( using [ctrl-Break] ), and subsequent runs will start where it left off.
Happy computing :¬/

 

[mybludrunsorange]

I came across this a few days ago and was curious if this could be easily modified to do the following:

1. Compare two lists of addresses
2. Run through each street address in column B and return all possible hits in column A where there is a match with a confidence (match percentage) higher than X.

We'd need to ignore case, if that matters.

 

[gissyjr]

That is what I am looking for as well. I have a listing of "old" addresses and want to compare to a "new" address column to see if they are a match and see what percentage of a match it is.

 

[al_b_cnu]

Hi Guys, Maybe something like this:
<b>Excel 2003</b><table cellpadding="2.5px" rules="all" style=";background-color: #FFFFFF;border: 1px solid;border-collapse: collapse; border-color: #A6AAB6"><colgroup><col width="25px" style="background-color: #E0E0F0" /><col /><col /><col /><col /></colgroup><thead><tr style=" background-color: #E0E0F0;text-align: center;color: #161120"><th></th><th>A</th><th>B</th><th>C</th><th>D</th></tr></thead><tbody><tr ><td style="color: #161120;text-align: center;">1</td><td style="text-align: right;;"></td><td style="text-align: right;;"></td><td style="text-align: center;;">Best Match</td><td style="text-align: center;;"></td></tr><tr ><td style="color: #161120;text-align: center;">2</td><td style="font-weight: bold;;">Address1</td><td style="font-weight: bold;;">Address2</td><td style="font-weight: bold;text-align: center;;">50%</td><td style="font-weight: bold;text-align: center;;">40%</td></tr><tr ><td style="color: #161120;text-align: center;">3</td><td style=";">1 Apple Avenue</td><td style=";">5 grapefruit Grotto</td><td style=";">5 grapefruit Grange</td><td style=";">5 grapefruit Grange</td></tr><tr ><td style="color: #161120;text-align: center;">4</td><td style=";">2 Orange Grove</td><td style=";">4 banana Boulevard</td><td style=";">4 banana road</td><td style=";">4 banana road</td></tr><tr ><td style="color: #161120;text-align: center;">5</td><td style=";">3 Pear Street</td><td style=";">3 Pear place</td><td style="text-align: right;;">#N/A</td><td style=";">3 Pear Street</td></tr><tr ><td style="color: #161120;text-align: center;">6</td><td style=";">4 banana road</td><td style=";">2 Orange Street</td><td style=";">2 Orange Grove</td><td style=";">2 Orange Grove</td></tr><tr ><td style="color: #161120;text-align: center;">7</td><td style=";">5 grapefruit Grange</td><td style=";">1 Aple Avenue</td><td style=";">1 Apple Avenue</td><td style=";">1 Apple Avenue</td></tr></tbody></table><p style="width:3.6em;font-weight:bold;margin:0;padding:0.2em 0.6em 0.2em 0.5em;border: 1px solid #A6AAB6;border-top:none;text-align: center;background-color: #E0E0F0;color: #161120">Sheet1</p><br /><br /><table width="85%" cellpadding="2.5px" rules="all" style=";border: 2px solid black;border-collapse:collapse;padding: 0.4em;background-color: #FFFFFF" ><tr><td style="padding:6px" ><b>Worksheet Formulas</b><table cellpadding="2.5px" width="100%" rules="all" style="border: 1px solid;text-align:center;background-color: #FFFFFF;border-collapse: collapse; border-color: #A6AAB6"><thead><tr style=" background-color: #E0E0F0;color: #161120"><th width="10px">Cell</th><th style="text-align:left;padding-left:5px;">Formula</th></tr></thead><tbody><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">C3</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B3,$A:$A,1,C$2,,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">D3</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B3,$A:$A,1,D$2,,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">C4</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B4,$A:$A,1,C$2,,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">D4</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B4,$A:$A,1,D$2,,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">C5</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B5,$A:$A,1,C$2,,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">D5</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B5,$A:$A,1,D$2,,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">C6</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B6,$A:$A,1,C$2,,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">D6</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B6,$A:$A,1,D$2,,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">C7</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B7,$A:$A,1,C$2,,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">D7</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B7,$A:$A,1,D$2,,2</font>)</td></tr></tbody></table></td></tr></table><br />

Follow the link in my signature for the latest version of the code.

 

[mybludrunsorange]

Not quite what I'm looking for... I'm looking to pull all addresses returned that are higher than, say a 50% confidence threshold.

 

[al_b_cnu]

Hi,
Isn't that what column C gives you - it returns N/A for anything which does not have a % match of at least 50%

 

[al_b_cnu]

... or did you want a macro solution?
Do you want ALL addresses in Column A above 50% match for each address in Column B?

 

[mybludrunsorange]

Do you want ALL addresses in Column A above 50% match for each address in Column B?

This. Being able to adjust that percentage/threshold would be great as well.

 

[al_b_cnu]

Something like this?
<b>Excel 2003</b><table cellpadding="2.5px" rules="all" style=";background-color: #FFFFFF;border: 1px solid;border-collapse: collapse; border-color: #A6AAB6"><colgroup><col width="25px" style="background-color: #E0E0F0" /><col /><col /><col /><col /><col /><col /><col /></colgroup><thead><tr style=" background-color: #E0E0F0;text-align: center;color: #161120"><th></th><th>A</th><th>B</th><th>C</th><th>D</th><th>E</th><th>F</th><th>G</th></tr></thead><tbody><tr ><td style="color: #161120;text-align: center;">1</td><td style="text-align: right;;"></td><td style="text-align: right;;"></td><td style="text-align: center;;">Rank</td><td style="text-align: center;;"></td><td style="text-align: center;;"></td><td style="text-align: center;;"></td><td style="text-align: center;;"></td></tr><tr ><td style="color: #161120;text-align: center;">2</td><td style="font-weight: bold;;">Address1</td><td style="font-weight: bold;;">Address2</td><td style="font-weight: bold;text-align: center;;">1</td><td style="font-weight: bold;text-align: center;;">2</td><td style="font-weight: bold;text-align: center;;">3</td><td style="font-weight: bold;text-align: center;;">4</td><td style="font-weight: bold;text-align: center;;">5</td></tr><tr ><td style="color: #161120;text-align: center;">3</td><td style=";">1 Apple Avenue</td><td style=";">5 grapefruit Grotto</td><td style="text-align: center;;">5 grapefruit Grange</td><td style="text-align: center;;">5 grape grotto</td><td style="text-align: center;;">6 grapefruit grotto</td><td style="text-align: center;;">5 grapfruit gotto</td><td style="text-align: center;;">#N/A</td></tr><tr ><td style="color: #161120;text-align: center;">4</td><td style=";">2 Orange Grove</td><td style=";">4 banana Boulevard</td><td style="text-align: center;;">4 banana road</td><td style="text-align: center;;">#N/A</td><td style="text-align: center;;">#N/A</td><td style="text-align: center;;">#N/A</td><td style="text-align: center;;">#N/A</td></tr><tr ><td style="color: #161120;text-align: center;">5</td><td style=";">3 Pear Street</td><td style=";">3 Pear place</td><td style="text-align: center;;">#N/A</td><td style="text-align: center;;">#N/A</td><td style="text-align: center;;">#N/A</td><td style="text-align: center;;">#N/A</td><td style="text-align: center;;">#N/A</td></tr><tr ><td style="color: #161120;text-align: center;">6</td><td style=";">4 banana road</td><td style=";">2 Orange Street</td><td style="text-align: center;;">2 Orange Grove</td><td style="text-align: center;;">#N/A</td><td style="text-align: center;;">#N/A</td><td style="text-align: center;;">#N/A</td><td style="text-align: center;;">#N/A</td></tr><tr ><td style="color: #161120;text-align: center;">7</td><td style=";">5 grapefruit Grange</td><td style=";">1 Aple Avenue</td><td style="text-align: center;;">1 Apple Avenue</td><td style="text-align: center;;">#N/A</td><td style="text-align: center;;">#N/A</td><td style="text-align: center;;">#N/A</td><td style="text-align: center;;">#N/A</td></tr><tr ><td style="color: #161120;text-align: center;">8</td><td style=";">5 grapfruit gotto</td><td style="text-align: right;;"></td><td style="text-align: center;;"></td><td style="text-align: center;;"></td><td style="text-align: center;;"></td><td style="text-align: center;;"></td><td style="text-align: center;;"></td></tr><tr ><td style="color: #161120;text-align: center;">9</td><td style=";">6 grapefruit grotto</td><td style="text-align: right;;"></td><td style="text-align: center;;"></td><td style="text-align: center;;"></td><td style="text-align: center;;"></td><td style="text-align: center;;"></td><td style="text-align: center;;"></td></tr><tr ><td style="color: #161120;text-align: center;">10</td><td style=";">5 grape grotto</td><td style="text-align: right;;"></td><td style="text-align: center;;"></td><td style="text-align: center;;"></td><td style="text-align: center;;"></td><td style="text-align: center;;"></td><td style="text-align: center;;"></td></tr><tr ><td style="color: #161120;text-align: center;">11</td><td style=";">77 grap grt</td><td style="text-align: right;;"></td><td style="text-align: center;;"></td><td style="text-align: center;;"></td><td style="text-align: center;;"></td><td style="text-align: center;;"></td><td style="text-align: center;;"></td></tr></tbody></table><p style="width:3.6em;font-weight:bold;margin:0;padding:0.2em 0.6em 0.2em 0.5em;border: 1px solid #A6AAB6;border-top:none;text-align: center;background-color: #E0E0F0;color: #161120">Sheet1</p><br /><br /><table width="85%" cellpadding="2.5px" rules="all" style=";border: 2px solid black;border-collapse:collapse;padding: 0.4em;background-color: #FFFFFF" ><tr><td style="padding:6px" ><b>Worksheet Formulas</b><table cellpadding="2.5px" width="100%" rules="all" style="border: 1px solid;text-align:center;background-color: #FFFFFF;border-collapse: collapse; border-color: #A6AAB6"><thead><tr style=" background-color: #E0E0F0;color: #161120"><th width="10px">Cell</th><th style="text-align:left;padding-left:5px;">Formula</th></tr></thead><tbody><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">C3</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B3,$A:$A,1,0.5,C$2,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">D3</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B3,$A:$A,1,0.5,D$2,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">E3</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B3,$A:$A,1,0.5,E$2,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">F3</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B3,$A:$A,1,0.5,F$2,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">G3</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B3,$A:$A,1,0.5,G$2,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">C4</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B4,$A:$A,1,0.5,C$2,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">D4</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B4,$A:$A,1,0.5,D$2,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">E4</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B4,$A:$A,1,0.5,E$2,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">F4</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B4,$A:$A,1,0.5,F$2,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">G4</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B4,$A:$A,1,0.5,G$2,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">C5</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B5,$A:$A,1,0.5,C$2,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">D5</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B5,$A:$A,1,0.5,D$2,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">E5</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B5,$A:$A,1,0.5,E$2,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">F5</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B5,$A:$A,1,0.5,F$2,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">G5</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B5,$A:$A,1,0.5,G$2,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">C6</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B6,$A:$A,1,0.5,C$2,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">D6</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B6,$A:$A,1,0.5,D$2,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">E6</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B6,$A:$A,1,0.5,E$2,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">F6</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B6,$A:$A,1,0.5,F$2,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">G6</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B6,$A:$A,1,0.5,G$2,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">C7</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B7,$A:$A,1,0.5,C$2,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">D7</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B7,$A:$A,1,0.5,D$2,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">E7</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B7,$A:$A,1,0.5,E$2,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">F7</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B7,$A:$A,1,0.5,F$2,2</font>)</td></tr><tr><th width="10px" style=" background-color: #E0E0F0;color: #161120">G7</th><td style="text-align:left">=fuzzyvlookup(<font color="Blue">$B7,$A:$A,1,0.5,G$2,2</font>)</td></tr></tbody></table></td></tr></table><br />