Fuzzy string comparison

[Steve Bergman]

I'm looking for a module to do fuzzy comparison of strings. I have 2
item master files which are supposed to be identical, but they have
thousands of records where the item numbers don't match in various
ways. One might include a '-' or have leading zeros, or have a single
character missing, or a zero that is typed as a letter 'O'. That kind
of thing. These tables currently reside in a mysql database. I was
wondering if there is a good package to let me compare strings and
return a value that is a measure of their similarity. Kind of like
soundex but for strings that aren't words.

Thanks,
Steve Bergman

[Wojciech =?ISO-8859-2?Q?Mu=B3a?=]

Steve Bergman wrote:

I'm looking for a module to do fuzzy comparison of strings. [...]

Check module difflib, it returns difference between two sequences.

[John Machin]

Wojciech Mula wrote:

Steve Bergman wrote:

I'm looking for a module to do fuzzy comparison of strings. [...]

Check module difflib, it returns difference between two sequences.

and it's intended for comparing text files, and is relatively slow.

Google "python levenshtein". You'll probably find this a better fit for
typoed keys in a database.

What I would do for a quick start on this exercise (as described) is:

To compare two strings, take copies, and:
1. strip out all spaces (including \xA0 i.e.   if the data has
been anywhere near the web) from each string; also all "-" (in general
strip frequently occurring meaningless punctuation)
2. remove leading zeroes from each string
3. d = levenshtein_dis tance(string_a, string_b) # string_a etc is the
reduced string, not the original
4. error_metric = float(d) / max(len(string_ a), len(string_b))

The error_metric will be 0.0 if the strings are the same (after
removing spaces, leading zeroes, etc) and 1.0 if they are completely
different (no characters in common).

.... and you don't want anything "kind of like soundex". That's a bit
like saying you'd like to travel in an aeroplane "kind of like the
Wright brothers' " ;-)

Cheers,
John

[Carsten Haese]

On Tue, 2006-12-26 at 13:08 -0800, John Machin wrote:

Wojciech Mula wrote:

Steve Bergman wrote:

I'm looking for a module to do fuzzy comparison of strings. [...]

Check module difflib, it returns difference between two sequences.

and it's intended for comparing text files, and is relatively slow.

Google "python levenshtein". You'll probably find this a better fit for
typoed keys in a database.
[...]

Using the Levenshtein distance in combination with stripping "noise"
characters is a good start, but the OP might want to take it a step
further. One of the OP's requirements is to recognize visually similar
strings, but 241O (Letter O at the end) and 241X have the same
Levenshtein distance from 2410 (digit zero at the end) while the former
is visually much closer to 2410 than the latter.

It seems to me that this could be achieved by starting with a standard
Levenshtein implementation such as http://hetland.org/python/distance.py
and altering the line "change = change + 1" to something like "change =
change + visual_distance (a[j-1], b[i-1])". visual_distance () would be a
function that embodies the OP's idea of which character replacements are
tolerable by returning a number between 0 (the two characters are
visually identical) and 1 (the two characters are completely different).

Hope this helps,

-Carsten

[Gabriel Genellina]

At Tuesday 26/12/2006 18:08, John Machin wrote:

>Wojciech Mula wrote:

Steve Bergman wrote:

I'm looking for a module to do fuzzy comparison of strings. [...]

Check module difflib, it returns difference between two sequences.

and it's intended for comparing text files, and is relatively slow.

Google "python levenshtein". You'll probably find this a better fit for
typoed keys in a database.

Other alternatives: trigram, n-gram, Jaro's distance. There are some
Python implem. available.
--
Gabriel Genellina
Softlab SRL


_______________ _______________ _______________ _____
Preguntá. Respondé. Descubrí.
Todo lo que querías saber, y lo que ni imaginabas,
está en Yahoo! Respuestas (Beta).
¡Probalo ya!
http://www.yahoo.com.ar/respuestas

[John Machin]

Carsten Haese wrote:

On Tue, 2006-12-26 at 13:08 -0800, John Machin wrote:

Wojciech Mula wrote:

Steve Bergman wrote:
I'm looking for a module to do fuzzy comparison of strings. [...]
>
Check module difflib, it returns difference between two sequences.

and it's intended for comparing text files, and is relatively slow.

Google "python levenshtein". You'll probably find this a better fit for
typoed keys in a database.
[...]

Using the Levenshtein distance in combination with stripping "noise"
characters is a good start, but the OP might want to take it a step
further. One of the OP's requirements is to recognize visually similar
strings, but 241O (Letter O at the end) and 241X have the same
Levenshtein distance from 2410 (digit zero at the end) while the former
is visually much closer to 2410 than the latter.

It seems to me that this could be achieved by starting with a standard
Levenshtein implementation such as http://hetland.org/python/distance.py
and altering the line "change = change + 1" to something like "change =
change + visual_distance (a[j-1], b[i-1])". visual_distance () would be a
function that embodies the OP's idea of which character replacements are
tolerable by returning a number between 0 (the two characters are
visually identical) and 1 (the two characters are completely different).

Ya ya ya, I could have told him a whole lot more -- please consider
that what I did tell him was IMHO over-generous in response to an OT
question asking for assistance with performing a Google search.

.... and given his keys are described as "numbers", a better example
might be 241O or 241o false-matching with 2416.

.... and it might be a good idea if he ran the simplistic approach first
and saw what near-misses he actually came up with before complicating
it and slowing down what is already an O(N**2*L**2) exercise in the
traditional/novice implementation where N is the number of keys and L
is their average length.

The OP needs to think about 123456789 compared with 123426789; are they
the same account or not? What other information does he have?

HTH,
John

[Duncan Booth]

"John Machin" <sj******@lexic on.netwrote:

To compare two strings, take copies, and:

Taking a copy of a string seems kind of superfluous in Python.

[Jorge Godoy]

"Steve Bergman" <st***@rueb.com writes:

I'm looking for a module to do fuzzy comparison of strings. I have 2
item master files which are supposed to be identical, but they have
thousands of records where the item numbers don't match in various
ways. One might include a '-' or have leading zeros, or have a single
character missing, or a zero that is typed as a letter 'O'. That kind
of thing. These tables currently reside in a mysql database. I was
wondering if there is a good package to let me compare strings and
return a value that is a measure of their similarity. Kind of like
soundex but for strings that aren't words.

If you were using PostgreSQL there's a contrib package (pg_trgm) that could
help a lot with that. It can show you the distance between two strings based
on a trigram comparison.

You can see how it works on the README
(http://www.sai.msu.su/~megera/postgr...README.pg_trgm) and maybe
port it for your needs.

But it probably won't be a one operation only search, you'll have to
post process results to decide what to do on multiple matches.

--
Jorge Godoy <jg****@gmail.c om>

[John Machin]

Duncan Booth wrote:

"John Machin" <sj******@lexic on.netwrote:

To compare two strings, take copies, and:

Taking a copy of a string seems kind of superfluous in Python.

You are right, I really meant don't do:
original = original.strip( ).replace(....) .replace(....)
(a strange way of doing things which I see occasionally in other folks'
code)

Cheers,
John

[Steven D'Aprano]

On Wed, 27 Dec 2006 02:52:42 -0800, John Machin wrote:

>
Duncan Booth wrote:

>"John Machin" <sj******@lexic on.netwrote:

To compare two strings, take copies, and:

Taking a copy of a string seems kind of superfluous in Python.

You are right, I really meant don't do:
original = original.strip( ).replace(....) .replace(....)
(a strange way of doing things which I see occasionally in other folks'
code)

Well, sure it is strange if you call the variable "original". But if you
don't care about the original, what's so strange about writing this?

astring = astring.strip() .replace(....). replace(....)

Why keep the original value of astring around if you no longer need it?
--
Steven.