CVS log for pgsql/contrib/fuzzystrmatch/fuzzystrmatch.c

Up to [PostgreSQL CVS Repository] / pgsql / contrib / fuzzystrmatch

Request diff between arbitrary revisions - Display revisions graphically

Keyword substitution: kv
Default branch: MAIN

Teach levenshtein() about multi-byte characters.

Based on a patch by, and further ideas from, Alexander Korotkov.

Avoid using text_to_cstring() in levenshtein functions.

Operating directly on the underlying varlena saves palloc and memcpy
overhead, which testing shows to be significant.

Extracted from a larger patch by Alexander Korotkov.

Update copyright for the year 2010.

Fix levenshtein with costs.  The previous code multiplied by the cost in only
3 of the 7 relevant locations.

Marcin Mank, slightly adjusted by me.

Fix levenshtein with costs.  The previous code multiplied by the cost in only
3 of the 7 relevant locations.

Marcin Mank, slightly adjusted by me.

8.4 pgindent run, with new combined Linux/FreeBSD/MinGW typedef list
provided by Andrew.

Defend against non-ASCII letters in fuzzystrmatch code.  The functions
still don't behave very sanely for multibyte encodings, but at least
they won't be indexing off the ends of static arrays.

Update copyright for 2009.

Add a variant of the Levenshtein string-distance function that lets the user
specify the cost values to use, instead of always using 1's.
Volkan Yazici

In passing, remove fuzzystrmatch.h, which contained a bunch of stuff that had
no business being in a .h file; fold it into its only user, fuzzystrmatch.c.

Simplify and standardize conversions between TEXT datums and ordinary C
strings.  This patch introduces four support functions cstring_to_text,
cstring_to_text_with_len, text_to_cstring, and text_to_cstring_buffer, and
two macros CStringGetTextDatum and TextDatumGetCString.  A number of
existing macros that provided variants on these themes were removed.

Most of the places that need to make such conversions now require just one
function or macro call, in place of the multiple notational layers that used
to be needed.  There are no longer any direct calls of textout or textin,
and we got most of the places that were using handmade conversions via
memcpy (there may be a few still lurking, though).

This commit doesn't make any serious effort to eliminate transient memory
leaks caused by detoasting toasted text objects before they reach
text_to_cstring.  We changed PG_GETARG_TEXT_P to PG_GETARG_TEXT_PP in a few
places where it was easy, but much more could be done.

Brendan Jurd and Tom Lane

Update copyrights in source tree to 2008.

Update /contrib/fuzzystrmatch error message to mention bytes, not just
'length', which can be characters.

Update CVS HEAD for 2007 copyright.  Back branches are typically not
back-stamped for this.

Remove a few baby-C macros in fuzzystrmatch.  Add a few missing includes.

Magic blocks don't do us any good unless we use 'em ... so install one
in every shared library.

Fix a few places that were checking for the return value of palloc() to be
non-NULL: palloc() ereports on OOM, so we can safely assume it returns a
valid pointer.

Add CVS tag lines to files that were lacking them.

Update copyright for 2006.  Update scripts.

Standard pgindent run for 8.1.

One of the web pages mentioned in dmetaphone.c has moved.  Also fix
a few typos in comments.

The dictionaries I checked list "altho" as a variant of "although,"
but I didn't find any other instances of the former in the source
tree so I changed it.

Michael Fuhr

The attached patch implements the soundex difference function which
compares two strings' soundex values for similarity, from Kris Jurka.
Also mark the text_soundex() function as STRICT, to avoid crashing
on NULL input.

Update copyrights that were missed.

Update copyright to 2004.

Add double metaphone code from Andrew Dunstan. Also change metaphone so that
an empty input string causes an empty output string to be returned, instead of
throwing an ERROR -- per complaint from Aaron Hillegass, and consistent with
double metaphone. Fix examples in README.soundex pointed out by James Robinson.

Fix some copyright notices that weren't updated.  Improve copyright tool
so it won't miss 'em again.

pgindent run.

Error message editing in contrib (mostly by Joe Conway --- thanks Joe!)

Jim C. Nasby wrote:
> Second argument to metaphone is suposed to set the limit on the
> number of characters to return, but it breaks on some phrases:
>
> usps=# select metaphone(a,3),metaphone(a,4),metaphone(a,20) from
> (select 'Hello world'::varchar AS a) a;
> HLW       | HLWR      | HLWRLT
>
> usps=# select metaphone(a,3),metaphone(a,4),metaphone(a,20) from
> (select 'A A COMEAUX MEMORIAL'::varchar AS a) a;
  > AKM       | AKMKS     | AKMKSMMRL
>
> In every case I've found that does this, the 4th and 5th letters are
> always 'KS'.

Nice catch.

There was a bug in the original metaphone algorithm from CPAN. Patch
attached (while I was at it I updated my email address, changed the
copyright to PGDG, and removed an unnecessary palloc). Here's how it
looks now:

regression=# select metaphone(a,4) from (select 'A A COMEAUX
MEMORIAL'::varchar AS a) a;
   metaphone
-----------
   AKMK
(1 row)

regression=# select metaphone(a,5) from (select 'A A COMEAUX
MEMORIAL'::varchar AS a) a;
   metaphone
-----------
   AKMKS
(1 row)

Joe Conway

This patch fixes a bunch of spelling mistakes in comments throughout the
PostgreSQL source code.

Neil Conway

Make sure that all <ctype.h> routines are called with unsigned char
values; it's not portable to call them with signed chars.  I recall doing
this for the last release, but a few more uncasted calls have snuck in.

Add trailing semicolon for Joe Conway

pgindent run on all C files.  Java run to follow.  initdb/regression
tests pass.

Add do { ... } while (0) to more bad macros.

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.

Remove soundex/metaphone and merge into fuzzystrmatch.

Joe Conway

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()?

Joe Conway