Received: from keittlab.bio.sunysb.edu (keittlab.bio.sunysb.edu [129.49.19.70]) by postgresql.org (8.11.3/8.11.1) with ESMTP id f712euf23362 for ; Tue, 31 Jul 2001 22:40:56 -0400 (EDT) (envelope-from tklistaddr@keittlab.bio.sunysb.edu) Received: from keittlab-6.keittlab.bio.sunysb.edu ([192.168.1.6] helo=keittlab.bio.sunysb.edu ident=tkeitt) by keittlab.bio.sunysb.edu with esmtp (Exim 3.22 #1 (Debian)) id 15RlwJ-0003du-00; Tue, 31 Jul 2001 22:40:51 -0400 Message-ID: <3B676C33.10805@keittlab.bio.sunysb.edu> Date: Tue, 31 Jul 2001 22:40:51 -0400 From: "Timothy H. Keitt" Organization: State University of New York at Stony Brook User-Agent: Mozilla/5.0 (X11; U; Linux 2.2.19-smp i686; en-US; rv:0.9.1) Gecko/20010615 X-Accept-Language: en-us MIME-Version: 1.0 To: "Timothy H. Keitt" CC: Josh Berkus , pgsql-sql@postgresql.org Subject: Re: Fuzzy matching? References: <3B676905.90208@keittlab.bio.sunysb.edu> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Archive-Number: 200107/402 X-Sequence-Number: 4221 Oh and despite the copyright notice, I'm happy to put it in the public domain, so feel free to incorporate into postgresql. Tim Timothy H. Keitt wrote: > I posted this many moons ago to pgsql-hackers. 'Guess nobody noticed. > > Tim > > Josh Berkus wrote: > >> 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 >> >> >> ------------------------------------------------------------------------ >> >> >> >> ------------------------------------------------------------------------ >> >> >> >> ------------------------------------------------------------------------ >> >> >> >> ------------------------------------------------------------------------ >> >> >> ---------------------------(end of broadcast)--------------------------- >> TIP 2: you can get off all lists at once with the unregister command >> (send "unregister YourEmailAddressHere" to majordomo@postgresql.org) >> >> Part 1.2 >> >> Content-Type: >> >> text/plain >> Content-Encoding: >> >> base64 >> >> >> ------------------------------------------------------------------------ >> Part 1.3 >> >> Content-Type: >> >> text/plain >> Content-Encoding: >> >> base64 >> >> >> ------------------------------------------------------------------------ >> Part 1.4 >> >> Content-Type: >> >> text/plain >> Content-Encoding: >> >> base64 >> >> >> ------------------------------------------------------------------------ >> Part 1.5 >> >> Content-Type: >> >> text/plain >> Content-Encoding: >> >> binary >> >> > > >------------------------------------------------------------------------ > >/* Copyright (c) 2000 Timothy H. Keitt */ >/* Licence: GPL version 2 or higher (see http://www.gnu.org/) */ > >#include "postgres.h" > >#define STATIC_SIZE 32 > >/* This must be changed if STATIC_SIZE is changed */ >static int4 static_array[STATIC_SIZE][STATIC_SIZE] = { > {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, > 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31}, > {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {13, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {17, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {18, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {19, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {21, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {22, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {23, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {24, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {25, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {26, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {27, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {29, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {30, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, > {31, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, > 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}; > >/* Fast version for strings up to STATIC_SIZE characters */ >int4 >levenshtein_distance(text *s1, text *s2) { > register int i, j, l, m, n, add, rows, columns; > > columns = VARSIZE(s1) - VARHDRSZ + 1; > rows = VARSIZE(s2) - VARHDRSZ + 1; > > /* Use slower dynamically allocated version for larger strings */ > if (columns > STATIC_SIZE || rows > STATIC_SIZE) > return levenshtein_distance_dynamic(s1, s2); > > for (j=1; j for (i=1; i > if (VARDATA(s1)[i-1] == VARDATA(s2)[j-1]) add=0; else add=1; > > m = 1 + static_array[j-1][i]; > l = 1 + static_array[j][i-1]; > n = add + static_array[j-1][i-1]; > > static_array[j][i] = (m < l ? (m < n ? m : n): (l < n ? l : n)); > > } /* next column (i) */ > } /* next row (j) */ > > return static_array[rows-1][columns-1]; > >} /* end levenshtein_distance(text *s1, text *s2) */ > >int4 >levenshtein_distance_dynamic(text *s1, text *s2) { > register int i, j, l, m, n, add, rows, columns, out; > int4 *dynamic_array; > > columns = VARSIZE(s1) - VARHDRSZ + 1; > rows = VARSIZE(s2) - VARHDRSZ + 1; > > dynamic_array = (int4 *) palloc(rows * columns * sizeof(int4)); > if (dynamic_array == NULL) return -1; > > for (i=0; i for (j=0; j > for (j=1; j for (i=1; i > if (VARDATA(s1)[i-1] == VARDATA(s2)[j-1]) add=0; else add=1; > > m = 1 + dynamic_array[(j-1)*columns+i]; > l = 1 + dynamic_array[j*columns+i-1]; > n = add + dynamic_array[(j-1)*columns+i-1]; > > dynamic_array[j*columns+i] = > (m < l ? (m < n ? m : n): (l < n ? l : n)); > > } /* next column (i) */ > } /* next row (j) */ > > out = dynamic_array[(rows-1)*columns+columns-1]; > > pfree(dynamic_array); > > return out; > >} /* end levenshtein_distance_dynamic(text *s1, text *s2) */ > > > >------------------------------------------------------------------------ > > >---------------------------(end of broadcast)--------------------------- >TIP 4: Don't 'kill -9' the postmaster > > levenshtein_distance.c > > Content-Type: > > text/plain > Content-Encoding: > > 7bit > > > ------------------------------------------------------------------------ > Part 1.3 > > Content-Type: > > text/plain > Content-Encoding: > > binary > > -- Timothy H. Keitt Department of Ecology and Evolution State University of New York at Stony Brook Stony Brook, New York 11794 USA Phone: 631-632-1101, FAX: 631-632-7626 http://life.bio.sunysb.edu/ee/keitt/