Received: from mailsys01.intnet.net (mailhost.wwc.com [198.252.32.15]) by postgresql.org (8.11.3/8.11.1) with ESMTP id f6VH78f26871 for ; Tue, 31 Jul 2001 13:07:08 -0400 (EDT) (envelope-from joseph.conway@home.com) Received: from [206.19.64.3] (HELO jecw2k1) by mailsys01.intnet.net (CommuniGate Pro SMTP 3.4.8) with SMTP id 12338376; Tue, 31 Jul 2001 13:06:32 -0400 Message-ID: <02ee01c119e3$3a128f50$48d210ac@jecw2k1> From: "Joe Conway" To: "Josh Berkus" , References: Subject: Re: Fuzzy matching? Date: Tue, 31 Jul 2001 10:07:05 -0700 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 5.50.4522.1200 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4522.1200 X-Archive-Number: 200107/392 X-Sequence-Number: 4206 > 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? Sounds like you want something along the lines of soundex or metaphone? I don't see either function in PostgreSQL, but take a look at the PHP manual to see examples: http://www.php.net/manual/en/function.soundex.php , http://www.php.net/manual/en/function.metaphone.php I looked at the soundex function in the PHP source, and it looks like it would be fairly easy to port to a Postgres C function. The algorithm itself comes from Donald Knuth in "The Art Of Computer Programming, vol. 3: Sorting And Searching", Addison-Wesley (1973), pp. 391-392. HTH, -- Joe