# Formula for finding 'near perfect' matches [duplicate]

This question already has an answer here:

I have a list of +-8000 items which is the result after applying numerous techniques to remove duplicates (the list started at over 10000 items).

I now have the following issue -

Example 1. Jack Daniel 2. Jack Daniels 3. Jack Daniel's

Clearly all of the above relate to one item but they are still technically unique. I tried pulling the first 4 letters and checking for matches however there were +-4000 and most of them were false positives i.e.

1. Jack Dxxx
2. Jack Bxxx

Both would pull Jack but would not be a valid duplicate.

Any thoughts?

## marked as duplicate by Excellll, Tog, Ƭᴇcʜιᴇ007, Doktoro Reichard, random♦Jul 29 '14 at 4:24

• Checking the Levenshtein distance between each item and reporting the records with a small distance might be what you need to do. – Zoredache Nov 1 '13 at 19:11
• @Zoredache how would you do that in Excel? – James Jenkins Nov 1 '13 at 19:13
• No idea. I leave that to you to research. Or possibly someone else who wants to spend the time writing up a full answer. – Zoredache Nov 1 '13 at 19:18
• Excel does not have any built-in functionality to do this. You with have to install an add-in (there are a few out there but are not free). Have a look at open refine which is free: youtube.com/watch?feature=player_embedded&v=B70J_H_zAWM, I had the same problem and it solved it for me (and it is very easy to transfer data from/to excel). – Ioannis Nov 2 '13 at 1:20

Based on Zoredache's comment, here is my sample workbook using VBA and the Levenshtein Distance to find similar strings within a big list. It's based on @smirkingman and @Apostolos55 answers on stackoverflow.

The Levenshtein distance between two words is the minimum number of single-character edits (insertion, deletion, substitution) required to change one word into the other

I implemented two different versions. Please check which function is faster for your case with 8000 values. If you're curious, view the full VBA code on Github. Raise the threshold in the line `const treshold = 1` if you want results with more than 1 required edit to get a match somewhere. • Formula syntax: `=LevenshteinCompare( <cell_to_check> , <range_to_search_in> )`
Example: `=LevenshteinCompare(A2;A\$2:A\$12)` (Notice the fixed range)
• Output syntax: `<number_of_required_edits> - [<match_address>] <match_value>`

``````Private Function Levenshtein(S1 As String, S2 As String)

Dim i As Integer, j As Integer
Dim l1 As Integer, l2 As Integer
Dim d() As Integer
Dim min1 As Integer, min2 As Integer

l1 = Len(S1)
l2 = Len(S2)
ReDim d(l1, l2)
For i = 0 To l1
d(i, 0) = i
Next
For j = 0 To l2
d(0, j) = j
Next
For i = 1 To l1
For j = 1 To l2
If Mid(S1, i, 1) = Mid(S2, j, 1) Then
d(i, j) = d(i - 1, j - 1)
Else
min1 = d(i - 1, j) + 1
min2 = d(i, j - 1) + 1
If min2 < min1 Then
min1 = min2
End If
min2 = d(i - 1, j - 1) + 1
If min2 < min1 Then
min1 = min2
End If
d(i, j) = min1
End If
Next
Next
Levenshtein = d(l1, l2)
End Function

Public Function LevenshteinCompare(S1 As Range, wordrange As Range)

Const treshold = 1
For Each S2 In Application.Intersect(wordrange, wordrange.Parent.UsedRange)
oldRes = newRes
newRes = Levenshtein(S1.Value, S2.Value)
If oldRes < newRes And oldRes <> "" Or S1.Address = S2.Address Then
newRes = oldRes
newS2row = oldS2row
Else
oldS2 = S2
oldS2row = S2.Address(0, 0)
End If
newS2 = oldS2
Next

If newRes <= treshold Then
LevenshteinCompare = newRes & " - [" & newS2row & "]  " & newS2
Else
LevenshteinCompare = ""
End If
End Function
``````

That was fun ☜(ﾟヮﾟ☜)

• Nice answer! I can see myself using this one. It might be better for this case to have a function which just returns the number of cells which are N edits or less away (analogous to `COUNTIF`). That would make the duplicate-removing process easier (because you could sort/filter by the second column). – benshepherd Nov 6 '13 at 8:00
• @benshepherd `number of cells which are N edits or less away`. Can you explain what you mean by number of cells, the address, the total amount? If you change line `LevenshteinCompare = newRes & " - [" & newS2row & "] " & newS2` to `LevenshteinCompare = newRes` you will only see the minimum amount of edits needed to match any other cell – nixda Nov 6 '13 at 8:11
• What I meant was, rather than returning the min number of edits over the whole range, it would be useful to have a function which counted the number of cells in the range that were 1 edit or less away. (Also, since you're usually looking for the minimal number, can you break out of your compare function early, thus making it faster?) – benshepherd Nov 6 '13 at 14:49

Use =len and if the difference is say less then 2 mark it as possible

and something like =mid(Value,(len_Value - 7),4) mark it as possilbe dupe.

Combined with what you already have you should get a much more doable set to work with.

Edit

Formulas like this, Notice that "Jack Daniel" <> "Jack Berries" in G2. but looks like a possible match everywhere else. You would need to modify a bit to meet your specific needs but it should get to a manageable number.

C1 =IF(LEFT(A1,4)=LEFT(B1,4),"T","F")

D1 =IF(LEN(A1) - LEN(B1) <= 2, "T", "F")

E1 =LEN(A1)

F1 =LEN(B1)

G1 =IF(MID(A1,(E1 - 7),4) = MID(B1,(E1 - 7),4), "T","F") • Thanks for the reply James - Im not sure how to use the formula "=mid(Value,(len_Value - 7),4)" I assume value is cell with the list and len_value is the result of =len? – brandon Nov 1 '13 at 20:47