pg.ddx.io  pgsql-sql@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Robby Slaughter <webmaster@robbyslaughter.com>
To: Josh Berkus <josh@agliodbs.com>
To: pgsql-sql@postgresql.org
Subject: RE: Fuzzy matching?
Date: Tue, 31 Jul 2001 12:07:48 -0500
Message-ID: <EPEHLKLEHAHLONFOKNHNGEGCDDAA.webmaster@robbyslaughter.com> (raw)
In-Reply-To: <web-94360@davinci.ethosmedia.com>

Here's an off the cuff reply:

It sounds like fuzzy_match(str1,str2,num) is
really just a tokenizer-type operation. The number is exactly
one less than the potential number of string segments
that you are interested in. For example:

   fuzzy_match('Thornton','Tornton',1) = TRUE

  Because the two segements are 'T' and 'ornton'

And also:

   fuzzy_match('Thornton','Torntin',2) = TRUE

  Becuse the three segments are 'T', "ornt', and 'n'

So, it seems like you could try to build the tokens,
which would be probably more efficient than just trying
all permutations.

HTH
-Robby


-----Original Message-----
From: pgsql-sql-owner@postgresql.org
[mailto:pgsql-sql-owner@postgresql.org]On Behalf Of Josh Berkus
Sent: Tuesday, July 31, 2001 11:05 AM
To: pgsql-sql@postgresql.org
Subject: [SQL] Fuzzy matching?


Folks,

For many of my programs, it would be extremely useful to have some form
of "fuzzy matching" for VARCHAR fields.  There are two kinds of fuzzy
matching for words that I know of:

1. Phonetic matching, which would be nice but will have to wait for
someone's $100,000 project;

2. Textual mathcing, which I will outline below.

The way textual fuzzy matching should work is as follows:
The developer supplies two VARCHARs to match and a number/percent of
character mis-match that is acceptable:

Fuzzy_match('Thornton','Tornton',1)

And the fuzzy_match should return True if the two phrases are no more
than that number of characters different.  Thus, we should get:

fuzzy_match('Thornton','Tornton',1) = TRUE
fuzzy_match('Thornton','Torntin',1) = FALSE
fuzzy_match('Thornton','Torntin',2) = TRUE

Unfortunately, I cannot think of a way to make this happen in a function
without cycling through all the possible permutations of characters for
both words or doing some character-by-character comparison with
elaborate logic for placement.  Either of these approaches would be very
slow, and completely unsuitable for column comparisons on large tables.

Can anyone suggest some shortcuts here?  Perhaps using pl/perl or
something similar?

Grazie!

-Josh Berkus

______AGLIO DATABASE SOLUTIONS___________________________
                                       Josh Berkus
  Complete information technology      josh@agliodbs.com
   and data management solutions       (415) 565-7293
  for law firms, small businesses        fax 621-2533
    and non-profit organizations.      San Francisco




view thread (26+ messages)  latest in thread

Message-ID: <EPEHLKLEHAHLONFOKNHNGEGCDDAA.webmaster@robbyslaughter.com>
Permalink:  ../EPEHLKLEHAHLONFOKNHNGEGCDDAA.webmaster@robbyslaughter.com/
Also on:    postgresql.org/message-id/EPEHLKLEHAHLONFOKNHNGEGCDDAA.webmaster@robbyslaughter.com

 · 

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: pgsql-sql@postgresql.org
  Cc: webmaster@robbyslaughter.com, josh@agliodbs.com
  Subject: RE: Fuzzy matching?
  In-Reply-To: <EPEHLKLEHAHLONFOKNHNGEGCDDAA.webmaster@robbyslaughter.com>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox