Received: from mail.utexas.edu (wb2-a.mail.utexas.edu [128.83.126.136]) by postgresql.org (8.11.3/8.11.1) with SMTP id f6VH61f25828 for ; Tue, 31 Jul 2001 13:06:01 -0400 (EDT) (envelope-from webmaster@robbyslaughter.com) Received: (qmail 25047 invoked by uid 0); 31 Jul 2001 17:05:59 -0000 Received: from adsl-64-218-163-9.dsl.austtx.swbell.net (HELO robmanbox) (64.218.163.9) by umbs-smtp-2 with SMTP; 31 Jul 2001 17:05:59 -0000 Reply-To: From: "Robby Slaughter" To: "Josh Berkus" , Subject: RE: Fuzzy matching? Date: Tue, 31 Jul 2001 12:07:48 -0500 Message-ID: MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2911.0) X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400 In-Reply-To: Importance: Normal X-Archive-Number: 200107/393 X-Sequence-Number: 4207 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