pg.ddx.io pgsql-sql@postgresql.org mailing list archive
help / color / mirror / Atom feedFuzzy matching?
26+ messages / 10 participants
[nested] [flat]
* Fuzzy matching?
@ 2001-07-31 16:05 Josh Berkus <josh@agliodbs.com>
2001-07-31 17:07 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
2001-07-31 17:07 ` RE: Fuzzy matching? Robby Slaughter <webmaster@robbyslaughter.com>
2001-07-31 17:44 ` Re: Fuzzy matching? Tom Lane <tgl@sss.pgh.pa.us>
2001-08-01 02:27 ` Re: Fuzzy matching? Timothy H. Keitt <tklistaddr@keittlab.bio.sunysb.edu>
2001-08-05 21:47 ` Re: Fuzzy matching? Peter Eisentraut <peter_e@gmx.net>
0 siblings, 5 replies; 26+ messages in thread
From: Josh Berkus @ 2001-07-31 16:05 UTC (permalink / raw)
To: pgsql-sql
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
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Fuzzy matching?
2001-07-31 16:05 Fuzzy matching? Josh Berkus <josh@agliodbs.com>
@ 2001-07-31 17:07 ` Joe Conway <joseph.conway@home.com>
2001-07-31 17:53 ` Re: Fuzzy matching? Bruce Momjian <pgman@candle.pha.pa.us>
4 siblings, 1 reply; 26+ messages in thread
From: Joe Conway @ 2001-07-31 17:07 UTC (permalink / raw)
To: Josh Berkus <josh@agliodbs.com>; pgsql-sql
> 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
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Fuzzy matching?
2001-07-31 16:05 Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 17:07 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
@ 2001-07-31 17:53 ` Bruce Momjian <pgman@candle.pha.pa.us>
2001-07-31 18:06 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
0 siblings, 1 reply; 26+ messages in thread
From: Bruce Momjian @ 2001-07-31 17:53 UTC (permalink / raw)
To: Joe Conway <joseph.conway@home.com>; +Cc: Josh Berkus <josh@agliodbs.com>; pgsql-sql
> 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
>
See /contrib/soundex.
--
Bruce Momjian | http://candle.pha.pa.us
pgman@candle.pha.pa.us | (610) 853-3000
+ If your life is a hard drive, | 830 Blythe Avenue
+ Christ can be your backup. | Drexel Hill, Pennsylvania 19026
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Fuzzy matching?
2001-07-31 16:05 Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 17:07 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
2001-07-31 17:53 ` Re: Fuzzy matching? Bruce Momjian <pgman@candle.pha.pa.us>
@ 2001-07-31 18:06 ` Joe Conway <joseph.conway@home.com>
2001-07-31 18:11 ` Re: Fuzzy matching? Bruce Momjian <pgman@candle.pha.pa.us>
2001-07-31 18:15 ` Re: Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 18:48 ` Re: Fuzzy matching? Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 3 replies; 26+ messages in thread
From: Joe Conway @ 2001-07-31 18:06 UTC (permalink / raw)
To: Bruce Momjian <pgman@candle.pha.pa.us>; +Cc: Josh Berkus <josh@agliodbs.com>; pgsql-sql
> > 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
> >
>
> See /contrib/soundex.
Sorry, missed that -- I only looked in the Documentation :(
I guess it's not there because it is a contrib. FWIW, both Oracle and MSSQL
have a built-in soundex function.
In any case, metaphone is reportedly more accurate (at least for English
words) than soundex, and levenshtein offers an entirely different and
interesting approach. Any interest in having all three of these in the
backend?
-- Joe
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Fuzzy matching?
2001-07-31 16:05 Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 17:07 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
2001-07-31 17:53 ` Re: Fuzzy matching? Bruce Momjian <pgman@candle.pha.pa.us>
2001-07-31 18:06 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
@ 2001-07-31 18:11 ` Bruce Momjian <pgman@candle.pha.pa.us>
2 siblings, 0 replies; 26+ messages in thread
From: Bruce Momjian @ 2001-07-31 18:11 UTC (permalink / raw)
To: Joe Conway <joseph.conway@home.com>; +Cc: Josh Berkus <josh@agliodbs.com>; pgsql-sql
> > See /contrib/soundex.
>
> Sorry, missed that -- I only looked in the Documentation :(
> I guess it's not there because it is a contrib. FWIW, both Oracle and MSSQL
> have a built-in soundex function.
>
> In any case, metaphone is reportedly more accurate (at least for English
> words) than soundex, and levenshtein offers an entirely different and
> interesting approach. Any interest in having all three of these in the
> backend?
Sure.
--
Bruce Momjian | http://candle.pha.pa.us
pgman@candle.pha.pa.us | (610) 853-3000
+ If your life is a hard drive, | 830 Blythe Avenue
+ Christ can be your backup. | Drexel Hill, Pennsylvania 19026
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Fuzzy matching?
2001-07-31 16:05 Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 17:07 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
2001-07-31 17:53 ` Re: Fuzzy matching? Bruce Momjian <pgman@candle.pha.pa.us>
2001-07-31 18:06 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
@ 2001-07-31 18:15 ` Josh Berkus <josh@agliodbs.com>
2001-07-31 20:09 ` Re: Fuzzy matching? Tom Lane <tgl@sss.pgh.pa.us>
2 siblings, 1 reply; 26+ messages in thread
From: Josh Berkus @ 2001-07-31 18:15 UTC (permalink / raw)
To: Joe Conway <joseph.conway@home.com>; Bruce Momjian <pgman@candle.pha.pa.us>; +Cc: Josh Berkus <josh@agliodbs.com>; pgsql-sql
Joe,
> In any case, metaphone is reportedly more accurate (at least for
> English
> words) than soundex, and levenshtein offers an entirely different and
> interesting approach. Any interest in having all three of these in
> the
> backend?
I'm quite interested, myself. How difficult is it for somebody that
doesn't program C to attach a function from the Contrib directory? If
it's not very difficult, then I'd recommend putting metaphone in
/contrib, and levenstein in the backend. My reasoning is that
levenstein is useful for all roman alphabets, but metaphone is not so
useful for non-english versions of postgres.
-Josh
______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
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Fuzzy matching?
2001-07-31 16:05 Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 17:07 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
2001-07-31 17:53 ` Re: Fuzzy matching? Bruce Momjian <pgman@candle.pha.pa.us>
2001-07-31 18:06 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
2001-07-31 18:15 ` Re: Fuzzy matching? Josh Berkus <josh@agliodbs.com>
@ 2001-07-31 20:09 ` Tom Lane <tgl@sss.pgh.pa.us>
2001-07-31 20:53 ` Re: Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-08-02 16:16 ` Re: Fuzzy matching? Oleg Bartunov <oleg@sai.msu.su>
0 siblings, 2 replies; 26+ messages in thread
From: Tom Lane @ 2001-07-31 20:09 UTC (permalink / raw)
To: Josh Berkus <josh@agliodbs.com>; +Cc: Joe Conway <joseph.conway@home.com>; Bruce Momjian <pgman@candle.pha.pa.us>; pgsql-sql
"Josh Berkus" <josh@agliodbs.com> writes:
> I'm quite interested, myself. How difficult is it for somebody that
> doesn't program C to attach a function from the Contrib directory?
Run the install script.
> If it's not very difficult, then I'd recommend putting metaphone in
> /contrib, and levenstein in the backend. My reasoning is that
> levenstein is useful for all roman alphabets, but metaphone is not so
> useful for non-english versions of postgres.
Our usual practice with stuff of uncertain usefulness has been to stick
it in contrib for awhile and see if anyone uses it. If there's
sufficient interest, we'll promote it to mainstream in a future release.
regards, tom lane
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Fuzzy matching?
2001-07-31 16:05 Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 17:07 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
2001-07-31 17:53 ` Re: Fuzzy matching? Bruce Momjian <pgman@candle.pha.pa.us>
2001-07-31 18:06 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
2001-07-31 18:15 ` Re: Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 20:09 ` Re: Fuzzy matching? Tom Lane <tgl@sss.pgh.pa.us>
@ 2001-07-31 20:53 ` Josh Berkus <josh@agliodbs.com>
2001-08-03 20:00 ` Re: Fuzzy matching Joe Conway <joseph.conway@home.com>
1 sibling, 1 reply; 26+ messages in thread
From: Josh Berkus @ 2001-07-31 20:53 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; Josh Berkus <josh@agliodbs.com>; +Cc: Joe Conway <joseph.conway@home.com>; Bruce Momjian <pgman@candle.pha.pa.us>; pgsql-sql
Tom, Joe,
> Our usual practice with stuff of uncertain usefulness has been to
> stick
> it in contrib for awhile and see if anyone uses it. If there's
> sufficient interest, we'll promote it to mainstream in a future
> release.
Makes sense to me. Go, Joe!
Since I can't help with the porting of metaphone or levenstein (but will
benefit immensely), I pledge to write a name-alike data checking
PL/pgSQL function which I will post to Roberto's library for public
consumption.
-Josh
______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
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Fuzzy matching
2001-07-31 16:05 Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 17:07 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
2001-07-31 17:53 ` Re: Fuzzy matching? Bruce Momjian <pgman@candle.pha.pa.us>
2001-07-31 18:06 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
2001-07-31 18:15 ` Re: Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 20:09 ` Re: Fuzzy matching? Tom Lane <tgl@sss.pgh.pa.us>
2001-07-31 20:53 ` Re: Fuzzy matching? Josh Berkus <josh@agliodbs.com>
@ 2001-08-03 20:00 ` Joe Conway <joseph.conway@home.com>
2001-08-03 21:08 ` Re: Re: Fuzzy matching Tom Lane <tgl@sss.pgh.pa.us>
2001-08-03 21:21 ` Re: Re: Fuzzy matching Bruce Momjian <pgman@candle.pha.pa.us>
2001-08-07 16:48 ` Re: Re: Fuzzy matching Bruce Momjian <pgman@candle.pha.pa.us>
0 siblings, 3 replies; 26+ messages in thread
From: Joe Conway @ 2001-08-03 20:00 UTC (permalink / raw)
To: pgsql-patches@postgresql.org
> > Our usual practice with stuff of uncertain usefulness has been to
> > stick
> > it in contrib for awhile and see if anyone uses it. If there's
> > sufficient interest, we'll promote it to mainstream in a future
> > release.
>
> Makes sense to me. Go, Joe!
>
Per this discussion, here's a patch to implement both levenshtein() and
metaphone() in a contrib. There seem to be a fair number of different
approaches to both of these algorithms. I used the simplest case for
levenshtein which has a cost of 1 for any character insertion, deletion, or
substitution. For metaphone, I adapted the same code from CPAN that the PHP
folks did.
A couple of questions:
1. Does it make sense to fold the soundex contrib together with this one?
2. I was debating trying to add multibyte support to levenshtein (it would
make no sense at all for metaphone), but a quick search through the contrib
directory found no hits on the word MULTIBYTE. Should worry about adding
multibyte support to levenshtein()?
Thanks,
Joe
Attachments:
fuzzystrmatch.diff (application/octet-stream, 26.4K) download
diff -Naur pgsql.alt/contrib/fuzzystrmatch/Makefile pgsql.dev/contrib/fuzzystrmatch/Makefile
--- pgsql.alt/contrib/fuzzystrmatch/Makefile Thu Jan 1 00:00:00 1970
+++ pgsql.dev/contrib/fuzzystrmatch/Makefile Tue Jul 31 16:08:46 2001
@@ -0,0 +1,41 @@
+subdir = contrib/fuzzystrmatch
+top_builddir = ../..
+include $(top_builddir)/src/Makefile.global
+
+# override libdir to install shlib in contrib not main directory
+libdir := $(libdir)/contrib
+
+# shared library parameters
+NAME= fuzzystrmatch
+SO_MAJOR_VERSION= 0
+SO_MINOR_VERSION= 1
+
+override CPPFLAGS := -I$(srcdir)/src/include $(CPPFLAGS)
+
+OBJS= fuzzystrmatch.o
+
+all: all-lib $(NAME).sql
+
+# Shared library stuff
+include $(top_srcdir)/src/Makefile.shlib
+
+
+$(NAME).sql: $(NAME).sql.in
+ sed -e 's:MODULE_PATHNAME:$(libdir)/$(shlib):g' < $< > $@
+
+install: all installdirs install-lib
+
+installdirs:
+ $(mkinstalldirs) $(DESTDIR)$(libdir)
+
+uninstall: uninstall-lib
+
+clean distclean maintainer-clean: clean-lib
+ rm -f $(OBJS) $(NAME).sql
+
+depend dep:
+ $(CC) -MM $(CFLAGS) *.c >depend
+
+ifeq (depend,$(wildcard depend))
+include depend
+endif
diff -Naur pgsql.alt/contrib/fuzzystrmatch/README.fuzzystrmatch pgsql.dev/contrib/fuzzystrmatch/README.fuzzystrmatch
--- pgsql.alt/contrib/fuzzystrmatch/README.fuzzystrmatch Thu Jan 1 00:00:00 1970
+++ pgsql.dev/contrib/fuzzystrmatch/README.fuzzystrmatch Fri Aug 3 12:42:22 2001
@@ -0,0 +1,121 @@
+/*
+ * fuzzystrmatch.c
+ *
+ * Functions for "fuzzy" comparison of strings
+ *
+ * Copyright (c) Joseph Conway <joseph.conway@home.com>, 2001;
+ *
+ * levenshtein()
+ * -------------
+ * Written based on a description of the algorithm by Michael Gilleland
+ * found at http://www.merriampark.com/ld.htm
+ * Also looked at levenshtein.c in the PHP 4.0.6 distribution for
+ * inspiration.
+ *
+ * metaphone()
+ * -----------
+ * Modified for PostgreSQL by Joe Conway.
+ * Based on CPAN's "Text-Metaphone-1.96" by Michael G Schwern <schwern@pobox.com>
+ * Code slightly modified for use as PostgreSQL function (palloc, elog, etc).
+ * Metaphone was originally created by Lawrence Philips and presented in article
+ * in "Computer Language" December 1990 issue.
+ *
+ * Permission to use, copy, modify, and distribute this software and its
+ * documentation for any purpose, without fee, and without a written agreement
+ * is hereby granted, provided that the above copyright notice and this
+ * paragraph and the following two paragraphs appear in all copies.
+ *
+ * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY PARTY FOR
+ * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING
+ * LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS
+ * DOCUMENTATION, EVEN IF THE AUTHOR OR DISTRIBUTORS HAVE BEEN ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
+ * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
+ * ON AN "AS IS" BASIS, AND THE AUTHOR AND DISTRIBUTORS HAS NO OBLIGATIONS TO
+ * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
+ *
+ */
+
+
+Version 0.1 (3 August, 2001):
+ Functions to calculate the degree to which two strings match in a "fuzzy" way
+ Tested under Linux (Red Hat 6.2 and 7.0) and PostgreSQL 7.2devel
+
+Release Notes:
+
+ Version 0.1
+ - initial release
+
+Installation:
+ Place these files in a directory called 'fuzzystrmatch' under 'contrib' in the PostgreSQL source tree. Then run:
+
+ make
+ make install
+
+ You can use fuzzystrmatch.sql to create the functions in your database of choice, e.g.
+
+ psql -U postgres template1 < fuzzystrmatch.sql
+
+ installs following functions into database template1:
+
+ levenshtein() - calculates the levenshtein distance between two strings
+ metaphone() - calculates the metaphone code of an input string
+
+Documentation
+==================================================================
+Name
+
+levenshtein -- calculates the levenshtein distance between two strings
+
+Synopsis
+
+levenshtein(text source, text target)
+
+Inputs
+
+ source
+ any text string, 255 characters max, NOT NULL
+
+ target
+ any text string, 255 characters max, NOT NULL
+
+Outputs
+
+ Returns int
+
+Example usage
+
+ select levenshtein('GUMBO','GAMBOL');
+
+==================================================================
+Name
+
+metaphone -- calculates the metaphone code of an input string
+
+Synopsis
+
+metaphone(text source, int max_output_length)
+
+Inputs
+
+ source
+ any text string, 255 characters max, NOT NULL
+
+ max_output_length
+ maximum length of the output metaphone code; if longer, the output
+ is truncated to this length
+
+Outputs
+
+ Returns text
+
+Example usage
+
+ select metaphone('GUMBO',4);
+
+==================================================================
+-- Joe Conway
+
diff -Naur pgsql.alt/contrib/fuzzystrmatch/fuzzystrmatch.c pgsql.dev/contrib/fuzzystrmatch/fuzzystrmatch.c
--- pgsql.alt/contrib/fuzzystrmatch/fuzzystrmatch.c Thu Jan 1 00:00:00 1970
+++ pgsql.dev/contrib/fuzzystrmatch/fuzzystrmatch.c Fri Aug 3 11:58:39 2001
@@ -0,0 +1,631 @@
+/*
+ * fuzzystrmatch.c
+ *
+ * Functions for "fuzzy" comparison of strings
+ *
+ * Copyright (c) Joseph Conway <joseph.conway@home.com>, 2001;
+ *
+ * levenshtein()
+ * -------------
+ * Written based on a description of the algorithm by Michael Gilleland
+ * found at http://www.merriampark.com/ld.htm
+ * Also looked at levenshtein.c in the PHP 4.0.6 distribution for
+ * inspiration.
+ *
+ * metaphone()
+ * -----------
+ * Modified for PostgreSQL by Joe Conway.
+ * Based on CPAN's "Text-Metaphone-1.96" by Michael G Schwern <schwern@pobox.com>
+ * Code slightly modified for use as PostgreSQL function (palloc, elog, etc).
+ * Metaphone was originally created by Lawrence Philips and presented in article
+ * in "Computer Language" December 1990 issue.
+ *
+ * Permission to use, copy, modify, and distribute this software and its
+ * documentation for any purpose, without fee, and without a written agreement
+ * is hereby granted, provided that the above copyright notice and this
+ * paragraph and the following two paragraphs appear in all copies.
+ *
+ * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY PARTY FOR
+ * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING
+ * LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS
+ * DOCUMENTATION, EVEN IF THE AUTHOR OR DISTRIBUTORS HAVE BEEN ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
+ * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
+ * ON AN "AS IS" BASIS, AND THE AUTHOR AND DISTRIBUTORS HAS NO OBLIGATIONS TO
+ * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
+ *
+ */
+
+#include "fuzzystrmatch.h"
+
+/*
+ * Calculates Levenshtein Distance between two strings.
+ * Uses simplest and fastest cost model only, i.e. assumes a cost of 1 for
+ * each deletion, substitution, or insertion.
+ */
+PG_FUNCTION_INFO_V1(levenshtein);
+Datum
+levenshtein(PG_FUNCTION_ARGS)
+{
+ char *str_s;
+ char *str_s0;
+ char *str_t;
+ int cols = 0;
+ int rows = 0;
+ int *u_cells;
+ int *l_cells;
+ int *tmp;
+ int i;
+ int j;
+
+ /*
+ * Fetch the arguments.
+ * str_s is referred to as the "source"
+ * cols = length of source + 1 to allow for the initialization column
+ * str_t is referred to as the "target", rows = length of target + 1
+ * rows = length of target + 1 to allow for the initialization row
+ */
+ str_s = DatumGetCString(DirectFunctionCall1(textout, PointerGetDatum(PG_GETARG_TEXT_P(0))));
+ str_t = DatumGetCString(DirectFunctionCall1(textout, PointerGetDatum(PG_GETARG_TEXT_P(1))));
+
+ cols = strlen(str_s) + 1;
+ rows = strlen(str_t) + 1;
+
+ /*
+ * Restrict the length of the strings being compared to something reasonable
+ * because we will have to perform rows * cols calcualtions. If longer strings need to be
+ * compared, increase MAX_LEVENSHTEIN_STRLEN to suit (but within your tolerance for
+ * speed and memory usage).
+ */
+ if ((cols > MAX_LEVENSHTEIN_STRLEN + 1) || (rows > MAX_LEVENSHTEIN_STRLEN + 1))
+ elog(ERROR, "levenshtein: Arguments may not exceed %d characters in length", MAX_LEVENSHTEIN_STRLEN);
+
+ /*
+ * If either rows or cols is 0, the answer is the other value.
+ * This makes sense since it would take that many insertions
+ * the build a matching string
+ */
+
+ if (cols == 0)
+ PG_RETURN_INT32(rows);
+
+ if (rows == 0)
+ PG_RETURN_INT32(cols);
+
+ /*
+ * Allocate two vectors of integers. One will be used for the "upper" row,
+ * the other for the "lower" row. Initialize the "upper" row to 0..cols
+ */
+ u_cells = palloc(sizeof(int) * cols);
+ for (i = 0; i < cols; i++)
+ u_cells[i] = i;
+
+ l_cells = palloc(sizeof(int) * cols);
+
+ /*
+ * Use str_s0 to "rewind" the pointer to str_s in the nested for loop below
+ */
+ str_s0 = str_s;
+
+ /*
+ * Loop throught the rows, starting at row 1. Row 0 is used for the initial
+ * "upper" row.
+ */
+ for (j = 1; j < rows; j++)
+ {
+ /*
+ * We'll always start with col 1,
+ * and initialize lower row col 0 to j
+ */
+ l_cells[0] = j;
+
+ for (i = 1; i < cols; i++)
+ {
+ int c = 0;
+ int c1 = 0;
+ int c2 = 0;
+ int c3 = 0;
+
+ /*
+ * The "cost" value is 0 if the character at the current col position
+ * in the source string, matches the character at the current row position
+ * in the target string; cost is 1 otherwise.
+ */
+ c = ((CHAREQ(str_s, str_t)) ? 0 : 1);
+
+ /*
+ * c1 is upper right cell plus 1
+ */
+ c1 = u_cells[i] + 1;
+
+ /*
+ * c2 is lower left cell plus 1
+ */
+ c2 = l_cells[i - 1] + 1;
+
+ /*
+ * c3 is cell diagonally above to the left plus "cost"
+ */
+ c3 = u_cells[i - 1] + c;
+
+ /*
+ * The lower right cell is set to the minimum
+ * of c1, c2, c3
+ */
+ l_cells[i] = (c1 < c2 ? c1 : c2) < c3 ? (c1 < c2 ? c1 : c2) : c3;
+
+ /*
+ * Increment the pointer to str_s
+ */
+ NextChar(str_s);
+ }
+
+ /*
+ * Lower row now becomes the upper row, and the upper row
+ * gets reused as the new lower row.
+ */
+ tmp = u_cells;
+ u_cells = l_cells;
+ l_cells = tmp;
+
+ /*
+ * Increment the pointer to str_t
+ */
+ NextChar(str_t);
+
+ /*
+ * Rewind the pointer to str_s
+ */
+ str_s = str_s0;
+ }
+
+ /*
+ * Because the final value (at position row, col) was swapped from
+ * the lower row to the upper row, that's where we'll find it.
+ */
+ PG_RETURN_INT32(u_cells[cols - 1]);
+}
+
+/*
+ * Calculates the metaphone of an input string.
+ * Returns number of characters requested
+ * (suggested value is 4)
+ */
+PG_FUNCTION_INFO_V1(metaphone);
+Datum
+metaphone(PG_FUNCTION_ARGS)
+{
+ int reqlen;
+ char *str_i;
+ size_t str_i_len;
+ char *metaph;
+ text *result_text;
+ int retval;
+
+ str_i = DatumGetCString(DirectFunctionCall1(textout, PointerGetDatum(PG_GETARG_TEXT_P(0))));
+ str_i_len = strlen(str_i);
+
+ if (str_i_len > MAX_METAPHONE_STRLEN)
+ elog(ERROR, "metaphone: Input string must not exceed %d characters", MAX_METAPHONE_STRLEN);
+ if (!(str_i_len > 0))
+ elog(ERROR, "metaphone: Input string length must be > 0");
+
+ reqlen = PG_GETARG_INT32(1);
+ if (reqlen > MAX_METAPHONE_STRLEN)
+ elog(ERROR, "metaphone: Requested Metaphone output length must not exceed %d characters", MAX_METAPHONE_STRLEN);
+ if (!(reqlen > 0))
+ elog(ERROR, "metaphone: Requested Metaphone output length must be > 0");
+
+ metaph = palloc(reqlen);
+ memset(metaph, '\0', reqlen);
+
+ retval = _metaphone(str_i, reqlen, &metaph);
+ if (retval == META_SUCCESS)
+ {
+ result_text = DatumGetTextP(DirectFunctionCall1(textin, CStringGetDatum(metaph)));
+ PG_RETURN_TEXT_P(result_text);
+ }
+ else
+ {
+ elog(ERROR, "metaphone: failure");
+
+ /*
+ * Keep the compiler quiet
+ */
+ PG_RETURN_NULL();
+ }
+}
+
+
+/*
+ * Original code by Michael G Schwern starts here.
+ * Code slightly modified for use as PostgreSQL
+ * function (palloc, etc). Original includes
+ * are rolled into fuzzystrmatch.h
+ *------------------------------------------------------------------*/
+
+/* I suppose I could have been using a character pointer instead of
+ * accesssing the array directly... */
+
+/* Look at the next letter in the word */
+#define Next_Letter (toupper(word[w_idx+1]))
+/* Look at the current letter in the word */
+#define Curr_Letter (toupper(word[w_idx]))
+/* Go N letters back. */
+#define Look_Back_Letter(n) (w_idx >= n ? toupper(word[w_idx-n]) : '\0')
+/* Previous letter. I dunno, should this return null on failure? */
+#define Prev_Letter (Look_Back_Letter(1))
+/* Look two letters down. It makes sure you don't walk off the string. */
+#define After_Next_Letter (Next_Letter != '\0' ? toupper(word[w_idx+2]) \
+ : '\0')
+#define Look_Ahead_Letter(n) (toupper(Lookahead(word+w_idx, n)))
+
+
+/* Allows us to safely look ahead an arbitrary # of letters */
+/* I probably could have just used strlen... */
+char Lookahead(char * word, int how_far) {
+ char letter_ahead = '\0'; /* null by default */
+ int idx;
+ for(idx = 0; word[idx] != '\0' && idx < how_far; idx++);
+ /* Edge forward in the string... */
+
+ letter_ahead = word[idx]; /* idx will be either == to how_far or
+ * at the end of the string
+ */
+ return letter_ahead;
+}
+
+
+/* phonize one letter */
+#define Phonize(c) {(*phoned_word)[p_idx++] = c;}
+/* Slap a null character on the end of the phoned word */
+#define End_Phoned_Word {(*phoned_word)[p_idx] = '\0';}
+/* How long is the phoned word? */
+#define Phone_Len (p_idx)
+
+/* Note is a letter is a 'break' in the word */
+#define Isbreak(c) (!isalpha(c))
+
+
+int _metaphone (
+ /* IN */
+ char * word,
+ int max_phonemes,
+ /* OUT */
+ char ** phoned_word
+) {
+ int w_idx = 0; /* point in the phonization we're at. */
+ int p_idx = 0; /* end of the phoned phrase */
+
+ /*-- Parameter checks --*/
+
+ /*
+ * Shouldn't be necessary, but left these here anyway
+ * jec Aug 3, 2001
+ */
+
+ /* Negative phoneme length is meaningless */
+ if (!(max_phonemes > 0))
+ elog(ERROR, "metaphone: Requested output length must be > 0");
+
+ /* Empty/null string is meaningless */
+ if ((word == NULL) || !(strlen(word) > 0))
+ elog(ERROR, "metaphone: Input string length must be > 0");
+
+ /*-- Allocate memory for our phoned_phrase --*/
+ if (max_phonemes == 0) { /* Assume largest possible */
+ *phoned_word = palloc(sizeof(char) * strlen(word) + 1);
+ if (!*phoned_word)
+ return META_ERROR;
+ } else {
+ *phoned_word = palloc(sizeof(char) * max_phonemes + 1);
+ if (!*phoned_word)
+ return META_ERROR;
+ }
+
+ /*-- The first phoneme has to be processed specially. --*/
+ /* Find our first letter */
+ for( ; !isalpha(Curr_Letter); w_idx++ ) {
+ /* On the off chance we were given nothing but crap... */
+ if( Curr_Letter == '\0' ) {
+ End_Phoned_Word
+ return META_SUCCESS; /* For testing */
+ }
+ }
+
+ switch (Curr_Letter) {
+ /* AE becomes E */
+ case 'A':
+ if( Next_Letter == 'E' ) {
+ Phonize('E');
+ w_idx+=2;
+ }
+ /* Remember, preserve vowels at the beginning */
+ else {
+ Phonize('A');
+ w_idx++;
+ }
+ break;
+ /* [GKP]N becomes N */
+ case 'G':
+ case 'K':
+ case 'P':
+ if( Next_Letter == 'N' ) {
+ Phonize('N');
+ w_idx+=2;
+ }
+ break;
+ /* WH becomes H,
+ WR becomes R
+ W if followed by a vowel */
+ case 'W':
+ if( Next_Letter == 'H' ||
+ Next_Letter == 'R' )
+ {
+ Phonize(Next_Letter);
+ w_idx+=2;
+ }
+ else if ( isvowel(Next_Letter) ) {
+ Phonize('W');
+ w_idx+=2;
+ }
+ /* else ignore */
+ break;
+ /* X becomes S */
+ case 'X':
+ Phonize('S');
+ w_idx++;
+ break;
+ /* Vowels are kept */
+ /* We did A already
+ case 'A':
+ case 'a':
+ */
+ case 'E':
+ case 'I':
+ case 'O':
+ case 'U':
+ Phonize(Curr_Letter);
+ w_idx++;
+ break;
+ default:
+ /* do nothing */
+ break;
+ }
+
+
+
+ /* On to the metaphoning */
+ for(; Curr_Letter != '\0' &&
+ (max_phonemes == 0 || Phone_Len < max_phonemes);
+ w_idx++) {
+ /* How many letters to skip because an eariler encoding handled
+ * multiple letters */
+ unsigned short int skip_letter = 0;
+
+
+ /* THOUGHT: It would be nice if, rather than having things like...
+ * well, SCI. For SCI you encode the S, then have to remember
+ * to skip the C. So the phonome SCI invades both S and C. It would
+ * be better, IMHO, to skip the C from the S part of the encoding.
+ * Hell, I'm trying it.
+ */
+
+ /* Ignore non-alphas */
+ if( !isalpha(Curr_Letter) )
+ continue;
+
+ /* Drop duplicates, except CC */
+ if( Curr_Letter == Prev_Letter &&
+ Curr_Letter != 'C' )
+ continue;
+
+ switch (Curr_Letter) {
+ /* B -> B unless in MB */
+ case 'B':
+ if( Prev_Letter != 'M' )
+ Phonize('B');
+ break;
+ /* 'sh' if -CIA- or -CH, but not SCH, except SCHW.
+ * (SCHW is handled in S)
+ * S if -CI-, -CE- or -CY-
+ * dropped if -SCI-, SCE-, -SCY- (handed in S)
+ * else K
+ */
+ case 'C':
+ if( MAKESOFT(Next_Letter) ) { /* C[IEY] */
+ if( After_Next_Letter == 'A' &&
+ Next_Letter == 'I' ) { /* CIA */
+ Phonize(SH);
+ }
+ /* SC[IEY] */
+ else if ( Prev_Letter == 'S' ) {
+ /* Dropped */
+ }
+ else {
+ Phonize('S');
+ }
+ }
+ else if ( Next_Letter == 'H' ) {
+#ifndef USE_TRADITIONAL_METAPHONE
+ if( After_Next_Letter == 'R' ||
+ Prev_Letter == 'S' ) { /* Christ, School */
+ Phonize('K');
+ }
+ else {
+ Phonize(SH);
+ }
+#else
+ Phonize(SH);
+#endif
+ skip_letter++;
+ }
+ else {
+ Phonize('K');
+ }
+ break;
+ /* J if in -DGE-, -DGI- or -DGY-
+ * else T
+ */
+ case 'D':
+ if( Next_Letter == 'G' &&
+ MAKESOFT(After_Next_Letter) ) {
+ Phonize('J');
+ skip_letter++;
+ }
+ else
+ Phonize('T');
+ break;
+ /* F if in -GH and not B--GH, D--GH, -H--GH, -H---GH
+ * else dropped if -GNED, -GN,
+ * else dropped if -DGE-, -DGI- or -DGY- (handled in D)
+ * else J if in -GE-, -GI, -GY and not GG
+ * else K
+ */
+ case 'G':
+ if( Next_Letter == 'H' ) {
+ if( !( NOGHTOF(Look_Back_Letter(3)) ||
+ Look_Back_Letter(4) == 'H' ) ) {
+ Phonize('F');
+ skip_letter++;
+ }
+ else {
+ /* silent */
+ }
+ }
+ else if( Next_Letter == 'N' ) {
+ if( Isbreak(After_Next_Letter) ||
+ ( After_Next_Letter == 'E' &&
+ Look_Ahead_Letter(3) == 'D' ) ) {
+ /* dropped */
+ }
+ else
+ Phonize('K');
+ }
+ else if( MAKESOFT(Next_Letter) &&
+ Prev_Letter != 'G' ) {
+ Phonize('J');
+ }
+ else {
+ Phonize('K');
+ }
+ break;
+ /* H if before a vowel and not after C,G,P,S,T */
+ case 'H':
+ if( isvowel(Next_Letter) &&
+ !AFFECTH(Prev_Letter) )
+ Phonize('H');
+ break;
+ /* dropped if after C
+ * else K
+ */
+ case 'K':
+ if( Prev_Letter != 'C' )
+ Phonize('K');
+ break;
+ /* F if before H
+ * else P
+ */
+ case 'P':
+ if( Next_Letter == 'H' ) {
+ Phonize('F');
+ }
+ else {
+ Phonize('P');
+ }
+ break;
+ /* K
+ */
+ case 'Q':
+ Phonize('K');
+ break;
+ /* 'sh' in -SH-, -SIO- or -SIA- or -SCHW-
+ * else S
+ */
+ case 'S':
+ if( Next_Letter == 'I' &&
+ ( After_Next_Letter == 'O' ||
+ After_Next_Letter == 'A' ) ) {
+ Phonize(SH);
+ }
+ else if ( Next_Letter == 'H' ) {
+ Phonize(SH);
+ skip_letter++;
+ }
+#ifndef USE_TRADITIONAL_METAPHONE
+ else if ( Next_Letter == 'C' &&
+ Look_Ahead_Letter(2) == 'H' &&
+ Look_Ahead_Letter(3) == 'W' ) {
+ Phonize(SH);
+ skip_letter += 2;
+ }
+#endif
+ else {
+ Phonize('S');
+ }
+ break;
+ /* 'sh' in -TIA- or -TIO-
+ * else 'th' before H
+ * else T
+ */
+ case 'T':
+ if( Next_Letter == 'I' &&
+ ( After_Next_Letter == 'O' ||
+ After_Next_Letter == 'A' ) ) {
+ Phonize(SH);
+ }
+ else if ( Next_Letter == 'H' ) {
+ Phonize(TH);
+ skip_letter++;
+ }
+ else {
+ Phonize('T');
+ }
+ break;
+ /* F */
+ case 'V':
+ Phonize('F');
+ break;
+ /* W before a vowel, else dropped */
+ case 'W':
+ if( isvowel(Next_Letter) )
+ Phonize('W');
+ break;
+ /* KS */
+ case 'X':
+ Phonize('K');
+ Phonize('S');
+ break;
+ /* Y if followed by a vowel */
+ case 'Y':
+ if( isvowel(Next_Letter) )
+ Phonize('Y');
+ break;
+ /* S */
+ case 'Z':
+ Phonize('S');
+ break;
+ /* No transformation */
+ case 'F':
+ case 'J':
+ case 'L':
+ case 'M':
+ case 'N':
+ case 'R':
+ Phonize(Curr_Letter);
+ break;
+ default:
+ /* nothing */
+ break;
+ } /* END SWITCH */
+
+ w_idx += skip_letter;
+ } /* END FOR */
+
+ End_Phoned_Word;
+
+ return(META_SUCCESS);
+} /* END metaphone */
diff -Naur pgsql.alt/contrib/fuzzystrmatch/fuzzystrmatch.h pgsql.dev/contrib/fuzzystrmatch/fuzzystrmatch.h
--- pgsql.alt/contrib/fuzzystrmatch/fuzzystrmatch.h Thu Jan 1 00:00:00 1970
+++ pgsql.dev/contrib/fuzzystrmatch/fuzzystrmatch.h Fri Aug 3 11:58:50 2001
@@ -0,0 +1,161 @@
+/*
+ * fuzzystrmatch.h
+ *
+ * Functions for "fuzzy" comparison of strings
+ *
+ * Copyright (c) Joseph Conway <joseph.conway@home.com>, 2001;
+ *
+ * levenshtein()
+ * -------------
+ * Written based on a description of the algorithm by Michael Gilleland
+ * found at http://www.merriampark.com/ld.htm
+ * Also looked at levenshtein.c in the PHP 4.0.6 distribution for
+ * inspiration.
+ *
+ * metaphone()
+ * -----------
+ * Modified for PostgreSQL by Joe Conway.
+ * Based on CPAN's "Text-Metaphone-1.96" by Michael G Schwern <schwern@pobox.com>
+ * Code slightly modified for use as PostgreSQL function (palloc, elog, etc).
+ * Metaphone was originally created by Lawrence Philips and presented in article
+ * in "Computer Language" December 1990 issue.
+ *
+ * Permission to use, copy, modify, and distribute this software and its
+ * documentation for any purpose, without fee, and without a written agreement
+ * is hereby granted, provided that the above copyright notice and this
+ * paragraph and the following two paragraphs appear in all copies.
+ *
+ * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY PARTY FOR
+ * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING
+ * LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS
+ * DOCUMENTATION, EVEN IF THE AUTHOR OR DISTRIBUTORS HAVE BEEN ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
+ * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
+ * ON AN "AS IS" BASIS, AND THE AUTHOR AND DISTRIBUTORS HAS NO OBLIGATIONS TO
+ * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
+ *
+ */
+
+#ifndef FUZZYSTRMATCH_H
+#define FUZZYSTRMATCH_H
+
+#include <stdio.h>
+#include <string.h>
+#include <ctype.h>
+
+#include "postgres.h"
+#include "fmgr.h"
+#include "utils/builtins.h"
+
+
+#define MAX_LEVENSHTEIN_STRLEN 255
+#define MAX_METAPHONE_STRLEN 255
+
+typedef struct dynmatrix
+{
+ int value;
+} dynmat;
+
+
+/*
+ * External declarations
+ */
+extern Datum levenshtein(PG_FUNCTION_ARGS);
+extern Datum metaphone(PG_FUNCTION_ARGS);
+
+/*
+ * Internal declarations
+ */
+
+
+
+#define STRLEN(p) strlen(p)
+#define CHAREQ(p1, p2) (*(p1) == *(p2))
+#define NextChar(p) ((p)++)
+
+
+/*
+ * Original code by Michael G Schwern starts here.
+ * Code slightly modified for use as PostgreSQL
+ * function (combined *.h into here).
+ *------------------------------------------------------------------*/
+
+/**************************************************************************
+ metaphone -- Breaks english phrases down into their phonemes.
+
+ Input
+ word -- An english word to be phonized
+ max_phonemes -- How many phonemes to calculate. If 0, then it
+ will phonize the entire phrase.
+ phoned_word -- The final phonized word. (We'll allocate the
+ memory.)
+ Output
+ error -- A simple error flag, returns TRUE or FALSE
+
+ NOTES: ALL non-alpha characters are ignored, this includes whitespace,
+ although non-alpha characters will break up phonemes.
+****************************************************************************/
+
+
+/**************************************************************************
+ my constants -- constants I like
+
+ Probably redundant.
+
+***************************************************************************/
+
+#define META_ERROR FALSE
+#define META_SUCCESS TRUE
+#define META_FAILURE FALSE
+
+
+/* I add modifications to the traditional metaphone algorithm that you
+ might find in books. Define this if you want metaphone to behave
+ traditionally */
+#undef USE_TRADITIONAL_METAPHONE
+
+/* Special encodings */
+#define SH 'X'
+#define TH '0'
+
+char Lookahead(char * word, int how_far);
+int _metaphone (
+ /* IN */
+ char * word,
+ int max_phonemes,
+ /* OUT */
+ char ** phoned_word
+);
+
+/* Metachar.h ... little bits about characters for metaphone */
+
+
+/*-- Character encoding array & accessing macros --*/
+/* Stolen directly out of the book... */
+char _codes[26] = {
+ 1,16,4,16,9,2,4,16,9,2,0,2,2,2,1,4,0,2,4,4,1,0,0,0,8,0
+/* a b c d e f g h i j k l m n o p q r s t u v w x y z */
+};
+
+
+#define ENCODE(c) (isalpha(c) ? _codes[((toupper(c)) - 'A')] : 0)
+
+#define isvowel(c) (ENCODE(c) & 1) /* AEIOU */
+
+/* These letters are passed through unchanged */
+#define NOCHANGE(c) (ENCODE(c) & 2) /* FJMNR */
+
+/* These form dipthongs when preceding H */
+#define AFFECTH(c) (ENCODE(c) & 4) /* CGPST */
+
+/* These make C and G soft */
+#define MAKESOFT(c) (ENCODE(c) & 8) /* EIY */
+
+/* These prevent GH from becoming F */
+#define NOGHTOF(c) (ENCODE(c) & 16) /* BDH */
+
+
+#endif /* FUZZYSTRMATCH_H */
diff -Naur pgsql.alt/contrib/fuzzystrmatch/fuzzystrmatch.sql.in pgsql.dev/contrib/fuzzystrmatch/fuzzystrmatch.sql.in
--- pgsql.alt/contrib/fuzzystrmatch/fuzzystrmatch.sql.in Thu Jan 1 00:00:00 1970
+++ pgsql.dev/contrib/fuzzystrmatch/fuzzystrmatch.sql.in Thu Aug 2 16:14:30 2001
@@ -0,0 +1,5 @@
+CREATE FUNCTION levenshtein (text,text) RETURNS int
+ AS 'MODULE_PATHNAME','levenshtein' LANGUAGE 'c' with (iscachable, isstrict);
+
+CREATE FUNCTION metaphone (text,int) RETURNS text
+ AS 'MODULE_PATHNAME','metaphone' LANGUAGE 'c' with (iscachable, isstrict);
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Re: Fuzzy matching
2001-07-31 16:05 Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 17:07 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
2001-07-31 17:53 ` Re: Fuzzy matching? Bruce Momjian <pgman@candle.pha.pa.us>
2001-07-31 18:06 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
2001-07-31 18:15 ` Re: Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 20:09 ` Re: Fuzzy matching? Tom Lane <tgl@sss.pgh.pa.us>
2001-07-31 20:53 ` Re: Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-08-03 20:00 ` Re: Fuzzy matching Joe Conway <joseph.conway@home.com>
@ 2001-08-03 21:08 ` Tom Lane <tgl@sss.pgh.pa.us>
2 siblings, 0 replies; 26+ messages in thread
From: Tom Lane @ 2001-08-03 21:08 UTC (permalink / raw)
To: Joe Conway <joseph.conway@home.com>; +Cc: pgsql-patches@postgresql.org
"Joe Conway" <joseph.conway@home.com> writes:
> 1. Does it make sense to fold the soundex contrib together with this one?
> 2. I was debating trying to add multibyte support to levenshtein (it would
> make no sense at all for metaphone), but a quick search through the contrib
> directory found no hits on the word MULTIBYTE. Should worry about adding
> multibyte support to levenshtein()?
Both of these seem like reasonable things to do, if you have the energy.
regards, tom lane
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Re: Fuzzy matching
2001-07-31 16:05 Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 17:07 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
2001-07-31 17:53 ` Re: Fuzzy matching? Bruce Momjian <pgman@candle.pha.pa.us>
2001-07-31 18:06 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
2001-07-31 18:15 ` Re: Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 20:09 ` Re: Fuzzy matching? Tom Lane <tgl@sss.pgh.pa.us>
2001-07-31 20:53 ` Re: Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-08-03 20:00 ` Re: Fuzzy matching Joe Conway <joseph.conway@home.com>
@ 2001-08-03 21:21 ` Bruce Momjian <pgman@candle.pha.pa.us>
2 siblings, 0 replies; 26+ messages in thread
From: Bruce Momjian @ 2001-08-03 21:21 UTC (permalink / raw)
To: Joe Conway <joseph.conway@home.com>; +Cc: pgsql-patches@postgresql.org
Your patch has been added to the PostgreSQL unapplied patches list at:
http://candle.pha.pa.us/cgi-bin/pgpatches
I will try to apply it within the next 48 hours.
> > > Our usual practice with stuff of uncertain usefulness has been to
> > > stick
> > > it in contrib for awhile and see if anyone uses it. If there's
> > > sufficient interest, we'll promote it to mainstream in a future
> > > release.
> >
> > Makes sense to me. Go, Joe!
> >
>
> Per this discussion, here's a patch to implement both levenshtein() and
> metaphone() in a contrib. There seem to be a fair number of different
> approaches to both of these algorithms. I used the simplest case for
> levenshtein which has a cost of 1 for any character insertion, deletion, or
> substitution. For metaphone, I adapted the same code from CPAN that the PHP
> folks did.
>
> A couple of questions:
> 1. Does it make sense to fold the soundex contrib together with this one?
>
> 2. I was debating trying to add multibyte support to levenshtein (it would
> make no sense at all for metaphone), but a quick search through the contrib
> directory found no hits on the word MULTIBYTE. Should worry about adding
> multibyte support to levenshtein()?
>
> Thanks,
>
> Joe
>
[ Attachment, skipping... ]
>
> ---------------------------(end of broadcast)---------------------------
> TIP 3: if posting/reading through Usenet, please send an appropriate
> subscribe-nomail command to majordomo@postgresql.org so that your
> message can get through to the mailing list cleanly
--
Bruce Momjian | http://candle.pha.pa.us
pgman@candle.pha.pa.us | (610) 853-3000
+ If your life is a hard drive, | 830 Blythe Avenue
+ Christ can be your backup. | Drexel Hill, Pennsylvania 19026
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Re: Fuzzy matching
2001-07-31 16:05 Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 17:07 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
2001-07-31 17:53 ` Re: Fuzzy matching? Bruce Momjian <pgman@candle.pha.pa.us>
2001-07-31 18:06 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
2001-07-31 18:15 ` Re: Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 20:09 ` Re: Fuzzy matching? Tom Lane <tgl@sss.pgh.pa.us>
2001-07-31 20:53 ` Re: Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-08-03 20:00 ` Re: Fuzzy matching Joe Conway <joseph.conway@home.com>
@ 2001-08-07 16:48 ` Bruce Momjian <pgman@candle.pha.pa.us>
2001-08-07 18:11 ` Re: Re: Fuzzy matching Joe Conway <joseph.conway@home.com>
2 siblings, 1 reply; 26+ messages in thread
From: Bruce Momjian @ 2001-08-07 16:48 UTC (permalink / raw)
To: Joe Conway <joseph.conway@home.com>; +Cc: pgsql-patches@postgresql.org
I have added this into /contrib under fuzzystrmatch. Not sure if we
want to merge soundex into that but it can be done later.
> > > Our usual practice with stuff of uncertain usefulness has been to
> > > stick
> > > it in contrib for awhile and see if anyone uses it. If there's
> > > sufficient interest, we'll promote it to mainstream in a future
> > > release.
> >
> > Makes sense to me. Go, Joe!
> >
>
> Per this discussion, here's a patch to implement both levenshtein() and
> metaphone() in a contrib. There seem to be a fair number of different
> approaches to both of these algorithms. I used the simplest case for
> levenshtein which has a cost of 1 for any character insertion, deletion, or
> substitution. For metaphone, I adapted the same code from CPAN that the PHP
> folks did.
>
> A couple of questions:
> 1. Does it make sense to fold the soundex contrib together with this one?
>
> 2. I was debating trying to add multibyte support to levenshtein (it would
> make no sense at all for metaphone), but a quick search through the contrib
> directory found no hits on the word MULTIBYTE. Should worry about adding
> multibyte support to levenshtein()?
>
> Thanks,
>
> Joe
>
[ Attachment, skipping... ]
>
> ---------------------------(end of broadcast)---------------------------
> TIP 3: if posting/reading through Usenet, please send an appropriate
> subscribe-nomail command to majordomo@postgresql.org so that your
> message can get through to the mailing list cleanly
--
Bruce Momjian | http://candle.pha.pa.us
pgman@candle.pha.pa.us | (610) 853-3000
+ If your life is a hard drive, | 830 Blythe Avenue
+ Christ can be your backup. | Drexel Hill, Pennsylvania 19026
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Re: Fuzzy matching
2001-07-31 16:05 Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 17:07 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
2001-07-31 17:53 ` Re: Fuzzy matching? Bruce Momjian <pgman@candle.pha.pa.us>
2001-07-31 18:06 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
2001-07-31 18:15 ` Re: Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 20:09 ` Re: Fuzzy matching? Tom Lane <tgl@sss.pgh.pa.us>
2001-07-31 20:53 ` Re: Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-08-03 20:00 ` Re: Fuzzy matching Joe Conway <joseph.conway@home.com>
2001-08-07 16:48 ` Re: Re: Fuzzy matching Bruce Momjian <pgman@candle.pha.pa.us>
@ 2001-08-07 18:11 ` Joe Conway <joseph.conway@home.com>
2001-08-07 18:16 ` Re: Re: Fuzzy matching Bruce Momjian <pgman@candle.pha.pa.us>
0 siblings, 1 reply; 26+ messages in thread
From: Joe Conway @ 2001-08-07 18:11 UTC (permalink / raw)
To: Bruce Momjian <pgman@candle.pha.pa.us>; +Cc: pgsql-patches@postgresql.org
>
> I have added this into /contrib under fuzzystrmatch. Not sure if we
> want to merge soundex into that but it can be done later.
>
>
Sorry - I should have gotten to this sooner. Here's a patch which you should
be able to apply against what you just committed. It rolls soundex into
fuzzystrmatch.
I'm don't think I will multibyte-enable levenshtein right now. If there is
some interest in it, I'll do that later.
Joe
Attachments:
fuzzystrmatch_r02.diff (application/octet-stream, 6.5K) download
diff -Naur pgsql.alt/contrib/fuzzystrmatch/README.fuzzystrmatch pgsql.dev/contrib/fuzzystrmatch/README.fuzzystrmatch
--- pgsql.alt/contrib/fuzzystrmatch/README.fuzzystrmatch Fri Aug 3 12:47:25 2001
+++ pgsql.dev/contrib/fuzzystrmatch/README.fuzzystrmatch Tue Aug 7 11:00:17 2001
@@ -20,6 +20,11 @@
* Metaphone was originally created by Lawrence Philips and presented in article
* in "Computer Language" December 1990 issue.
*
+ * soundex()
+ * -----------
+ * Folded existing soundex contrib into this one. Renamed text_soundex() (C function)
+ * to soundex() for consistency.
+ *
* Permission to use, copy, modify, and distribute this software and its
* documentation for any purpose, without fee, and without a written agreement
* is hereby granted, provided that the above copyright notice and this
@@ -40,11 +45,14 @@
*/
-Version 0.1 (3 August, 2001):
+Version 0.2 (7 August, 2001):
Functions to calculate the degree to which two strings match in a "fuzzy" way
Tested under Linux (Red Hat 6.2 and 7.0) and PostgreSQL 7.2devel
Release Notes:
+
+ Version 0.2
+ - folded soundex contrib into this one
Version 0.1
- initial release
diff -Naur pgsql.alt/contrib/fuzzystrmatch/README.soundex pgsql.dev/contrib/fuzzystrmatch/README.soundex
--- pgsql.alt/contrib/fuzzystrmatch/README.soundex Thu Jan 1 00:00:00 1970
+++ pgsql.dev/contrib/fuzzystrmatch/README.soundex Tue Aug 7 10:42:27 2001
@@ -0,0 +1,62 @@
+NOTE: Modified August 07, 2001 by Joe Conway. Updated for accuracy
+ after combining soundex code into the fuzzystrmatch contrib
+---------------------------------------------------------------------
+The Soundex system is a method of matching similar sounding names
+(or any words) to the same code. It was initially used by the
+United States Census in 1880, 1900, and 1910, but it has little use
+beyond English names (or the English pronunciation of names), and
+it is not a linguistic tool.
+
+The following are some usage examples:
+
+SELECT soundex('hello world!');
+
+CREATE TABLE s (nm text)\g
+
+insert into s values ('john')\g
+insert into s values ('joan')\g
+insert into s values ('wobbly')\g
+
+select * from s
+where soundex(nm) = soundex('john')\g
+
+select nm from s a, s b
+where soundex(a.nm) = soundex(b.nm)
+and a.oid <> b.oid\g
+
+CREATE FUNCTION text_sx_eq(text, text) RETURNS bool AS
+'select soundex($1) = soundex($2)'
+LANGUAGE 'sql'\g
+
+CREATE FUNCTION text_sx_lt(text,text) RETURNS bool AS
+'select soundex($1) < soundex($2)'
+LANGUAGE 'sql'\g
+
+CREATE FUNCTION text_sx_gt(text,text) RETURNS bool AS
+'select soundex($1) > soundex($2)'
+LANGUAGE 'sql';
+
+CREATE FUNCTION text_sx_le(text,text) RETURNS bool AS
+'select soundex($1) <= soundex($2)'
+LANGUAGE 'sql';
+
+CREATE FUNCTION text_sx_ge(text,text) RETURNS bool AS
+'select soundex($1) >= soundex($2)'
+LANGUAGE 'sql';
+
+CREATE FUNCTION text_sx_ne(text,text) RETURNS bool AS
+'select soundex($1) <> soundex($2)'
+LANGUAGE 'sql';
+
+DROP OPERATOR #= (text,text)\g
+
+CREATE OPERATOR #= (leftarg=text, rightarg=text, procedure=text_sx_eq,
+commutator=text_sx_eq)\g
+
+SELECT *
+FROM s
+WHERE text_sx_eq(nm,'john')\g
+
+SELECT *
+from s
+where s.nm #= 'john';
diff -Naur pgsql.alt/contrib/fuzzystrmatch/fuzzystrmatch.c pgsql.dev/contrib/fuzzystrmatch/fuzzystrmatch.c
--- pgsql.alt/contrib/fuzzystrmatch/fuzzystrmatch.c Fri Aug 3 12:47:25 2001
+++ pgsql.dev/contrib/fuzzystrmatch/fuzzystrmatch.c Tue Aug 7 10:52:40 2001
@@ -629,3 +629,71 @@
return(META_SUCCESS);
} /* END metaphone */
+
+
+/*
+ * SQL function: soundex(text) returns text
+ */
+PG_FUNCTION_INFO_V1(soundex);
+
+Datum
+soundex(PG_FUNCTION_ARGS)
+{
+ char outstr[SOUNDEX_LEN + 1];
+ char *arg;
+
+ arg = _textout(PG_GETARG_TEXT_P(0));
+
+ _soundex(arg, outstr);
+
+ PG_RETURN_TEXT_P(_textin(outstr));
+}
+
+static void
+_soundex(const char *instr, char *outstr)
+{
+ int count;
+
+ AssertArg(instr);
+ AssertArg(outstr);
+
+ outstr[SOUNDEX_LEN] = '\0';
+
+ /* Skip leading non-alphabetic characters */
+ while (!isalpha((unsigned char) instr[0]) && instr[0])
+ ++instr;
+
+ /* No string left */
+ if (!instr[0])
+ {
+ outstr[0] = (char) 0;
+ return;
+ }
+
+ /* Take the first letter as is */
+ *outstr++ = (char) toupper((unsigned char) *instr++);
+
+ count = 1;
+ while (*instr && count < SOUNDEX_LEN)
+ {
+ if (isalpha((unsigned char) *instr) &&
+ soundex_code(*instr) != soundex_code(*(instr - 1)))
+ {
+ *outstr = soundex_code(instr[0]);
+ if (*outstr != '0')
+ {
+ ++outstr;
+ ++count;
+ }
+ }
+ ++instr;
+ }
+
+ /* Fill with 0's */
+ while (count < SOUNDEX_LEN)
+ {
+ *outstr = '0';
+ ++outstr;
+ ++count;
+ }
+}
diff -Naur pgsql.alt/contrib/fuzzystrmatch/fuzzystrmatch.h pgsql.dev/contrib/fuzzystrmatch/fuzzystrmatch.h
--- pgsql.alt/contrib/fuzzystrmatch/fuzzystrmatch.h Fri Aug 3 12:47:25 2001
+++ pgsql.dev/contrib/fuzzystrmatch/fuzzystrmatch.h Tue Aug 7 10:38:46 2001
@@ -51,31 +51,42 @@
#include "utils/builtins.h"
-#define MAX_LEVENSHTEIN_STRLEN 255
-#define MAX_METAPHONE_STRLEN 255
-
-typedef struct dynmatrix
-{
- int value;
-} dynmat;
-
/*
* External declarations
*/
extern Datum levenshtein(PG_FUNCTION_ARGS);
extern Datum metaphone(PG_FUNCTION_ARGS);
+extern Datum soundex(PG_FUNCTION_ARGS);
/*
- * Internal declarations
+ * Soundex
*/
+static void _soundex(const char *instr, char *outstr);
+#define SOUNDEX_LEN 4
+#define _textin(str) DirectFunctionCall1(textin, CStringGetDatum(str))
+#define _textout(str) DatumGetPointer(DirectFunctionCall1(textout, PointerGetDatum(str)))
+/* ABCDEFGHIJKLMNOPQRSTUVWXYZ */
+static const char *soundex_table = "01230120022455012623010202";
+#define soundex_code(letter) soundex_table[toupper((unsigned char) (letter)) - 'A']
+
+
+/*
+ * Levenshtein
+ */
#define STRLEN(p) strlen(p)
#define CHAREQ(p1, p2) (*(p1) == *(p2))
#define NextChar(p) ((p)++)
+#define MAX_LEVENSHTEIN_STRLEN 255
+
+/*
+ * Metaphone
+ */
+#define MAX_METAPHONE_STRLEN 255
/*
* Original code by Michael G Schwern starts here.
diff -Naur pgsql.alt/contrib/fuzzystrmatch/fuzzystrmatch.sql.in pgsql.dev/contrib/fuzzystrmatch/fuzzystrmatch.sql.in
--- pgsql.alt/contrib/fuzzystrmatch/fuzzystrmatch.sql.in Fri Aug 3 12:47:25 2001
+++ pgsql.dev/contrib/fuzzystrmatch/fuzzystrmatch.sql.in Tue Aug 7 10:53:49 2001
@@ -3,3 +3,9 @@
CREATE FUNCTION metaphone (text,int) RETURNS text
AS 'MODULE_PATHNAME','metaphone' LANGUAGE 'c' with (iscachable, isstrict);
+
+CREATE FUNCTION soundex(text) RETURNS text
+ AS 'MODULE_PATHNAME', 'soundex' LANGUAGE 'c' with (iscachable, isstrict);
+
+CREATE FUNCTION text_soundex(text) RETURNS text
+ AS 'MODULE_PATHNAME', 'soundex' LANGUAGE 'c';
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Re: Fuzzy matching
2001-07-31 16:05 Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 17:07 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
2001-07-31 17:53 ` Re: Fuzzy matching? Bruce Momjian <pgman@candle.pha.pa.us>
2001-07-31 18:06 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
2001-07-31 18:15 ` Re: Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 20:09 ` Re: Fuzzy matching? Tom Lane <tgl@sss.pgh.pa.us>
2001-07-31 20:53 ` Re: Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-08-03 20:00 ` Re: Fuzzy matching Joe Conway <joseph.conway@home.com>
2001-08-07 16:48 ` Re: Re: Fuzzy matching Bruce Momjian <pgman@candle.pha.pa.us>
2001-08-07 18:11 ` Re: Re: Fuzzy matching Joe Conway <joseph.conway@home.com>
@ 2001-08-07 18:16 ` Bruce Momjian <pgman@candle.pha.pa.us>
0 siblings, 0 replies; 26+ messages in thread
From: Bruce Momjian @ 2001-08-07 18:16 UTC (permalink / raw)
To: Joe Conway <joseph.conway@home.com>; +Cc: pgsql-patches@postgresql.org
> >
> > I have added this into /contrib under fuzzystrmatch. Not sure if we
> > want to merge soundex into that but it can be done later.
> >
> >
>
> Sorry - I should have gotten to this sooner. Here's a patch which you should
> be able to apply against what you just committed. It rolls soundex into
> fuzzystrmatch.
>
> I'm don't think I will multibyte-enable levenshtein right now. If there is
> some interest in it, I'll do that later.
OK, I have removed /contrib/soundex and /contrib/metaphone and added
your patch so they are all in fuzzystrmatch.
--
Bruce Momjian | http://candle.pha.pa.us
pgman@candle.pha.pa.us | (610) 853-3000
+ If your life is a hard drive, | 830 Blythe Avenue
+ Christ can be your backup. | Drexel Hill, Pennsylvania 19026
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Fuzzy matching?
2001-07-31 16:05 Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 17:07 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
2001-07-31 17:53 ` Re: Fuzzy matching? Bruce Momjian <pgman@candle.pha.pa.us>
2001-07-31 18:06 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
2001-07-31 18:15 ` Re: Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 20:09 ` Re: Fuzzy matching? Tom Lane <tgl@sss.pgh.pa.us>
@ 2001-08-02 16:16 ` Oleg Bartunov <oleg@sai.msu.su>
1 sibling, 0 replies; 26+ messages in thread
From: Oleg Bartunov @ 2001-08-02 16:16 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Josh Berkus <josh@agliodbs.com>; Joe Conway <joseph.conway@home.com>; Bruce Momjian <pgman@candle.pha.pa.us>; pgsql-sql
I have C-codes which implement Levenstein Distance Algorithms
Here is a header for soe info:
// Levenstein Distance Algorithms Module
//
// Contains functions to do "Inexact Alphanumeric Comparisons". The original
// concept for this code came from "The C Users Journal", May 1991, starting
// on page 127. The author was Hans Z. Zwakenberg.
//
// These routines have been modified so they do not need to use double
// subscripted arrays in the CUJ code. An additional function was created to
// "look up" a word from a list, returning the most likely matches.
//
// Written initailly by R. Bruce Roberts, MCI Systems Engineering, 1/7/93
// Compiled with Borland C++, V3.1
//
It's compiled and works well. Don't know about license but it's published
and it's possible to ask author directly
zen:~/app/algo/dist/ldist$ ./test simple sample
Returns 'Levenstein Distance' of two strings on command line.
Determining Distance for simple and sample.
Length is limited to 40 characters.
Words are alike, L Distance is 1, Threshold was 3.
PLease let me know if you need it. I thought about implementing the
same feature as Google has into our OpenFTS search
Regards,
Oleg
On Tue, 31 Jul 2001, Tom Lane wrote:
> "Josh Berkus" <josh@agliodbs.com> writes:
> > I'm quite interested, myself. How difficult is it for somebody that
> > doesn't program C to attach a function from the Contrib directory?
>
> Run the install script.
>
> > If it's not very difficult, then I'd recommend putting metaphone in
> > /contrib, and levenstein in the backend. My reasoning is that
> > levenstein is useful for all roman alphabets, but metaphone is not so
> > useful for non-english versions of postgres.
>
> Our usual practice with stuff of uncertain usefulness has been to stick
> it in contrib for awhile and see if anyone uses it. If there's
> sufficient interest, we'll promote it to mainstream in a future release.
>
> regards, tom lane
>
> ---------------------------(end of broadcast)---------------------------
> TIP 6: Have you searched our list archives?
>
> http://www.postgresql.org/search.mpl
>
Regards,
Oleg
_____________________________________________________________
Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
Sternberg Astronomical Institute, Moscow University (Russia)
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(095)939-16-83, +007(095)939-23-83
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Fuzzy matching?
2001-07-31 16:05 Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 17:07 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
2001-07-31 17:53 ` Re: Fuzzy matching? Bruce Momjian <pgman@candle.pha.pa.us>
2001-07-31 18:06 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
@ 2001-07-31 18:48 ` Tom Lane <tgl@sss.pgh.pa.us>
2 siblings, 0 replies; 26+ messages in thread
From: Tom Lane @ 2001-07-31 18:48 UTC (permalink / raw)
To: Joe Conway <joseph.conway@home.com>; +Cc: Bruce Momjian <pgman@candle.pha.pa.us>; Josh Berkus <josh@agliodbs.com>; pgsql-sql
"Joe Conway" <joseph.conway@home.com> writes:
> In any case, metaphone is reportedly more accurate (at least for English
> words) than soundex, and levenshtein offers an entirely different and
> interesting approach. Any interest in having all three of these in the
> backend?
I'd certainly accept such functions as /contrib material, but probably
would want to wait to see if they get used much before putting them in
the standard backend ...
regards, tom lane
^ permalink raw reply [nested|flat] 26+ messages in thread
* RE: Fuzzy matching?
2001-07-31 16:05 Fuzzy matching? Josh Berkus <josh@agliodbs.com>
@ 2001-07-31 17:07 ` Robby Slaughter <webmaster@robbyslaughter.com>
4 siblings, 0 replies; 26+ messages in thread
From: Robby Slaughter @ 2001-07-31 17:07 UTC (permalink / raw)
To: Josh Berkus <josh@agliodbs.com>; pgsql-sql
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
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Fuzzy matching?
2001-07-31 16:05 Fuzzy matching? Josh Berkus <josh@agliodbs.com>
@ 2001-07-31 17:44 ` Tom Lane <tgl@sss.pgh.pa.us>
2001-07-31 21:31 ` Re: Fuzzy matching? Christopher Sawtell <csawtell@paradise.net.nz>
4 siblings, 1 reply; 26+ messages in thread
From: Tom Lane @ 2001-07-31 17:44 UTC (permalink / raw)
To: Josh Berkus <josh@agliodbs.com>; +Cc: pgsql-sql
"Josh Berkus" <josh@agliodbs.com> writes:
> 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;
Uh, have you looked at contrib/soundex? The Soundex code is kinda
specialized but might be just what you want...
regards, tom lane
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Fuzzy matching?
2001-07-31 16:05 Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 17:44 ` Re: Fuzzy matching? Tom Lane <tgl@sss.pgh.pa.us>
@ 2001-07-31 21:31 ` Christopher Sawtell <csawtell@paradise.net.nz>
0 siblings, 0 replies; 26+ messages in thread
From: Christopher Sawtell @ 2001-07-31 21:31 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; Josh Berkus <josh@agliodbs.com>; +Cc: pgsql-sql
On Wed, 01 Aug 2001 05:44, Tom Lane wrote:
> "Josh Berkus" <josh@agliodbs.com> writes:
> > 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;
>
> Uh, have you looked at contrib/soundex? The Soundex code is kinda
> specialized but might be just what you want...
Be aware that Soundex simply does not work at all well on names of Pacific
origin. Samoan in particular is a total no no.
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Fuzzy matching?
2001-07-31 16:05 Fuzzy matching? Josh Berkus <josh@agliodbs.com>
@ 2001-08-01 02:27 ` Timothy H. Keitt <tklistaddr@keittlab.bio.sunysb.edu>
2001-08-01 02:40 ` Re: Fuzzy matching? Timothy H. Keitt <tklistaddr@keittlab.bio.sunysb.edu>
4 siblings, 1 reply; 26+ messages in thread
From: Timothy H. Keitt @ 2001-08-01 02:27 UTC (permalink / raw)
To: Josh Berkus <josh@agliodbs.com>; +Cc: pgsql-sql
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
>
>
--
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/
Attachments:
levenshtein_distance.c (text/plain, 5.3K) download
/* 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<rows; ++j) {
for (i=1; i<columns; ++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<columns; ++i) dynamic_array[i] = i;
for (j=0; j<rows; ++j) dynamic_array[j*columns] = j;
for (j=1; j<rows; ++j) {
for (i=1; i<columns; ++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) */
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Fuzzy matching?
2001-07-31 16:05 Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-08-01 02:27 ` Re: Fuzzy matching? Timothy H. Keitt <tklistaddr@keittlab.bio.sunysb.edu>
@ 2001-08-01 02:40 ` Timothy H. Keitt <tklistaddr@keittlab.bio.sunysb.edu>
0 siblings, 0 replies; 26+ messages in thread
From: Timothy H. Keitt @ 2001-08-01 02:40 UTC (permalink / raw)
To: Timothy H. Keitt <tklistaddr@keittlab.bio.sunysb.edu>; +Cc: Josh Berkus <josh@agliodbs.com>; pgsql-sql
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<rows; ++j) {
> for (i=1; i<columns; ++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<columns; ++i) dynamic_array[i] = i;
> for (j=0; j<rows; ++j) dynamic_array[j*columns] = j;
>
> for (j=1; j<rows; ++j) {
> for (i=1; i<columns; ++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/
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Fuzzy matching?
2001-07-31 16:05 Fuzzy matching? Josh Berkus <josh@agliodbs.com>
@ 2001-08-05 21:47 ` Peter Eisentraut <peter_e@gmx.net>
2001-08-11 19:55 ` Re: Re: Fuzzy matching? Timothy H. Keitt <tklistaddr@keittlab.bio.sunysb.edu>
4 siblings, 1 reply; 26+ messages in thread
From: Peter Eisentraut @ 2001-08-05 21:47 UTC (permalink / raw)
To: Josh Berkus <josh@agliodbs.com>; +Cc: pgsql-sql
Josh Berkus writes:
> For many of my programs, it would be extremely useful to have some form
> of "fuzzy matching" for VARCHAR fields.
For lexical similarity, check out the agrep algorithm. Last I checked the
source code wasn't quite Free(tm), but the algorithm was published in an
academic work.
--
Peter Eisentraut peter_e@gmx.net http://funkturm.homeip.net/~peter
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Re: Fuzzy matching?
2001-07-31 16:05 Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-08-05 21:47 ` Re: Fuzzy matching? Peter Eisentraut <peter_e@gmx.net>
@ 2001-08-11 19:55 ` Timothy H. Keitt <tklistaddr@keittlab.bio.sunysb.edu>
0 siblings, 0 replies; 26+ messages in thread
From: Timothy H. Keitt @ 2001-08-11 19:55 UTC (permalink / raw)
To: Peter Eisentraut <peter_e@gmx.net>; +Cc: Josh Berkus <josh@agliodbs.com>; pgsql-sql
The Levenshtein-distance code I posted uses the agrep algorithm.
Tim
Peter Eisentraut wrote:
>Josh Berkus writes:
>
>>For many of my programs, it would be extremely useful to have some form
>>of "fuzzy matching" for VARCHAR fields.
>>
>
>For lexical similarity, check out the agrep algorithm. Last I checked the
>source code wasn't quite Free(tm), but the algorithm was published in an
>academic work.
>
--
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/
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Fuzzy matching?
@ 2001-07-31 17:34 Josh Berkus <josh@agliodbs.com>
2001-07-31 17:41 ` Re: Fuzzy matching? Joe Conway <joseph.conway@home.com>
0 siblings, 1 reply; 26+ messages in thread
From: Josh Berkus @ 2001-07-31 17:34 UTC (permalink / raw)
To: Joe Conway <joseph.conway@home.com>; +Cc: pgsql-sql
Joe,
> > 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.
> >
>
> Actually, this may even be closer to what you want:
> http://www.php.net/manual/en/function.levenshtein.php
Hey, that's terrific! I didn't know that those programs existed
outside fo expensive proprietary software.
Now, who can I talk into porting them (metaphone, levenstein) to
Postgres? Hey, GreatBridge folks? (this would be a significant value
enhancement for Postgres)
-Josh
______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
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Fuzzy matching?
2001-07-31 17:34 Re: Fuzzy matching? Josh Berkus <josh@agliodbs.com>
@ 2001-07-31 17:41 ` Joe Conway <joseph.conway@home.com>
0 siblings, 0 replies; 26+ messages in thread
From: Joe Conway @ 2001-07-31 17:41 UTC (permalink / raw)
To: Josh Berkus <josh@agliodbs.com>; +Cc: pgsql-sql
> >
> > Actually, this may even be closer to what you want:
> > http://www.php.net/manual/en/function.levenshtein.php
>
> Hey, that's terrific! I didn't know that those programs existed
> outside fo expensive proprietary software.
>
> Now, who can I talk into porting them (metaphone, levenstein) to
> Postgres? Hey, GreatBridge folks? (this would be a significant value
> enhancement for Postgres)
>
> -Josh
I wouldn't mind doing it if the core team agrees. It will probably be a
couple of weeks before I can get to it though -- not sure if that's soon
enough to make it into 7.2. Should it be a contrib, or in the backend?
-- Joe
^ permalink raw reply [nested|flat] 26+ messages in thread
* RE: Fuzzy matching?
@ 2001-07-31 20:23 Jeff Eckermann <jeckermann@verio.net>
0 siblings, 0 replies; 26+ messages in thread
From: Jeff Eckermann @ 2001-07-31 20:23 UTC (permalink / raw)
To: 'Josh Berkus' <josh@agliodbs.com>; Joe Conway <joseph.conway@home.com>; Bruce Momjian <pgman@candle.pha.pa.us>; +Cc: pgsql-sql
With version 7.2 we will have pl/perlu (untrusted), which will allow use of
the various Perl modules which do this sort of thing.
> -----Original Message-----
> From: Josh Berkus [SMTP:josh@agliodbs.com]
> Sent: Tuesday, July 31, 2001 1:16 PM
> To: Joe Conway; Bruce Momjian
> Cc: Josh Berkus; pgsql-sql@postgresql.org
> Subject: Re: Fuzzy matching?
>
> Joe,
>
> > In any case, metaphone is reportedly more accurate (at least for
> > English
> > words) than soundex, and levenshtein offers an entirely different and
> > interesting approach. Any interest in having all three of these in
> > the
> > backend?
>
> I'm quite interested, myself. How difficult is it for somebody that
> doesn't program C to attach a function from the Contrib directory? If
> it's not very difficult, then I'd recommend putting metaphone in
> /contrib, and levenstein in the backend. My reasoning is that
> levenstein is useful for all roman alphabets, but metaphone is not so
> useful for non-english versions of postgres.
>
> -Josh
>
> ______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 5: Have you checked our extensive FAQ?
>
> http://www.postgresql.org/users-lounge/docs/faq.html
^ permalink raw reply [nested|flat] 26+ messages in thread
end of thread, other threads:[~2001-08-11 19:55 UTC | newest]
Thread overview: 26+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2001-07-31 16:05 Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 17:07 ` Joe Conway <joseph.conway@home.com>
2001-07-31 17:53 ` Bruce Momjian <pgman@candle.pha.pa.us>
2001-07-31 18:06 ` Joe Conway <joseph.conway@home.com>
2001-07-31 18:11 ` Bruce Momjian <pgman@candle.pha.pa.us>
2001-07-31 18:15 ` Josh Berkus <josh@agliodbs.com>
2001-07-31 20:09 ` Tom Lane <tgl@sss.pgh.pa.us>
2001-07-31 20:53 ` Josh Berkus <josh@agliodbs.com>
2001-08-03 20:00 ` Re: Fuzzy matching Joe Conway <joseph.conway@home.com>
2001-08-03 21:08 ` Re: Re: Fuzzy matching Tom Lane <tgl@sss.pgh.pa.us>
2001-08-03 21:21 ` Re: Re: Fuzzy matching Bruce Momjian <pgman@candle.pha.pa.us>
2001-08-07 16:48 ` Re: Re: Fuzzy matching Bruce Momjian <pgman@candle.pha.pa.us>
2001-08-07 18:11 ` Re: Re: Fuzzy matching Joe Conway <joseph.conway@home.com>
2001-08-07 18:16 ` Re: Re: Fuzzy matching Bruce Momjian <pgman@candle.pha.pa.us>
2001-08-02 16:16 ` Oleg Bartunov <oleg@sai.msu.su>
2001-07-31 18:48 ` Tom Lane <tgl@sss.pgh.pa.us>
2001-07-31 17:07 ` Robby Slaughter <webmaster@robbyslaughter.com>
2001-07-31 17:44 ` Tom Lane <tgl@sss.pgh.pa.us>
2001-07-31 21:31 ` Christopher Sawtell <csawtell@paradise.net.nz>
2001-08-01 02:27 ` Timothy H. Keitt <tklistaddr@keittlab.bio.sunysb.edu>
2001-08-01 02:40 ` Timothy H. Keitt <tklistaddr@keittlab.bio.sunysb.edu>
2001-08-05 21:47 ` Peter Eisentraut <peter_e@gmx.net>
2001-08-11 19:55 ` Timothy H. Keitt <tklistaddr@keittlab.bio.sunysb.edu>
2001-07-31 17:34 Re: Fuzzy matching? Josh Berkus <josh@agliodbs.com>
2001-07-31 17:41 ` Joe Conway <joseph.conway@home.com>
2001-07-31 20:23 RE: Fuzzy matching? Jeff Eckermann <jeckermann@verio.net>
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