Hi,
Following patch implements configurable penalty costs for levenshtein
distance metric in fuzzystrmatch contrib module.
It doesn't introduce any compatibility issues. Just implements
levenshtein(text,text,int,int,int)
function on top of fuzzystrmatch.c:levenshtein_internal(). At the
same time, levenshtein(text,text) becomes just a wrapper for
levenshtein(text,text,1,1,1) call.
BTW, in current CVS tip
if (cols/rows == 0) ...
checks in fuzzyztrmatch.c:levenshtein() never fail because of
cols/rows = strlen(...) + 1;
FYI.
Regards.
? contrib/fuzzystrmatch/fuzzystrmatch.sql
? contrib/fuzzystrmatch/libfuzzystrmatch.so.0.0
Index: contrib/fuzzystrmatch/README.fuzzystrmatch
===================================================================
RCS file: /projects/cvsroot/pgsql/contrib/fuzzystrmatch/README.fuzzystrmatch,v
retrieving revision 1.10
diff -c -r1.10 README.fuzzystrmatch
*** contrib/fuzzystrmatch/README.fuzzystrmatch 5 Jan 2007 22:19:17 -0000 1.10
--- contrib/fuzzystrmatch/README.fuzzystrmatch 17 Oct 2007 13:58:09 -0000
***************
*** 14,19 ****
--- 14,20 ----
* found at http://www.merriampark.com/ld.htm
* Also looked at levenshtein.c in the PHP 4.0.6 distribution for
* inspiration.
+ * Configurable penalty costs extension is introduced by Volkan YAZICI.
*
* metaphone()
* -----------
***************
*** 116,121 ****
--- 117,158 ----
==================================================================
Name
+ levenshtein -- calculates levenshtein distance with respect
+ to specified costs.
+
+ Synopsis
+
+ levenshtein(text source, text target,
+ int insert_cost, int delete_cost, int substitution_cost)
+
+ Inputs
+
+ source
+ any text string, 255 characters max, NOT NULL
+
+ target
+ any text string, 255 characters max, NOT NULL
+
+ insert_cost
+ cost of extra inserted characters
+
+ delete_cost
+ cost of missing characters
+
+ substitution_cost
+ cost of character substitutions
+
+ Outputs
+
+ Returns int
+
+ Example usage
+
+ select levenshtein('GUMBO','GAMBOL', 1, 1, 3);
+
+ ==================================================================
+ Name
+
metaphone -- calculates the metaphone code of an input string
Synopsis
***************
*** 140,144 ****
select metaphone('GUMBO',4);
==================================================================
! -- Joe Conway
!
--- 177,180 ----
select metaphone('GUMBO',4);
==================================================================
! -- Joe Conway
\ No newline at end of file
Index: contrib/fuzzystrmatch/fuzzystrmatch.c
===================================================================
RCS file: /projects/cvsroot/pgsql/contrib/fuzzystrmatch/fuzzystrmatch.c,v
retrieving revision 1.24
diff -c -r1.24 fuzzystrmatch.c
*** contrib/fuzzystrmatch/fuzzystrmatch.c 13 Feb 2007 18:00:35 -0000 1.24
--- contrib/fuzzystrmatch/fuzzystrmatch.c 17 Oct 2007 13:58:09 -0000
***************
*** 15,20 ****
--- 15,21 ----
* found at http://www.merriampark.com/ld.htm
* Also looked at levenshtein.c in the PHP 4.0.6 distribution for
* inspiration.
+ * Configurable penalty consts extension is introduced by Volkan YAZICI.
*
* metaphone()
* -----------
***************
*** 47,201 ****
PG_MODULE_MAGIC;
/*
! * 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 calculations. 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))
ereport(ERROR,
(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
errmsg("argument exceeds the maximum length of %d bytes",
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 through 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 = (*str_s != *str_t);
! /*
! * 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
! */
! 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
! */
! 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
--- 48,178 ----
PG_MODULE_MAGIC;
+
/*
! * levenshtein_internal - Calculates Levenshtein distance metric
! * between supplied strings. Generally
! * (1, 1, 1) penalty costs suffices common
! * cases, but your mileage may vary.
*/
! static int
! levenshtein_internal(char *s, char *t, int ins_c, int del_c, int sub_c)
{
! int m, n;
! int *prev;
! int *curr;
! int i, j;
! char *x;
! char *y;
!
! m = strlen(s);
! n = strlen(t);
!
! if (!m)
! return n;
! if (!n)
! return m;
/*
! * For security concerns, restrict excessive CPU+RAM usage. (This
! * implementation uses O(m+n) memory and has O(mn) complexity.)
*/
! if ((m + n) > (2 * MAX_LEVENSHTEIN_STRLEN))
ereport(ERROR,
(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
errmsg("argument exceeds the maximum length of %d bytes",
MAX_LEVENSHTEIN_STRLEN)));
! /* One more cell for initial segments. */
! ++m;
! ++n;
/*
! * Instead of building an (m+1)x(n+1) array, we'll use two
! * different arrays of size m+1 and n+1 for storing accumulated
! * values in previous calls.
*/
! prev = palloc((m + n) * sizeof(char));
! curr = prev + (m * sizeof(char));
! for (i = 0; i < m; i++)
! prev[i] = i;
! for (y = t, j = 1; j < n; y++, j++)
{
+ int *temp;
+
/*
! * First cell must increment sequentially, as we're on the
! * j'th column of the (m+1)x(n+1) array.
*/
! curr[0] = j;
!
! for (x = s, i = 1; i < m; x++, i++)
{
! int ins;
! int del;
! int sub;
!
! /* Calculate costs for probable operations. */
! ins = prev[i] + ins_c; /* Insertion */
! del = curr[i-1] + del_c; /* Deletion */
! sub = prev[i-1] + ((*x == *y) ? 0 : sub_c); /* Substitution */
!
! /* Take the one with minimum cost. */
! curr[i] = ins < del ? ins : del;
! curr[i] = curr[i] < sub ? curr[i] : sub;
! }
! /* Swap current row with previous row. */
! temp = curr;
! curr = prev;
! prev = temp;
! }
! /*
! * Because the final value was swapped from the previous row to
! * the current row, that's where we'll find it.
! */
! return prev[m-1];
! }
! PG_FUNCTION_INFO_V1(levenshtein_with_costs);
! Datum
! levenshtein_with_costs(PG_FUNCTION_ARGS)
! {
! char *src;
! char *dst;
! int ins_c;
! int del_c;
! int sub_c;
!
! src = _textout(PG_GETARG_DATUM(0));
! dst = _textout(PG_GETARG_DATUM(1));
!
! ins_c = PG_GETARG_INT32(2);
! del_c = PG_GETARG_INT32(3);
! sub_c = PG_GETARG_INT32(4);
! PG_RETURN_INT32(levenshtein_internal(src, dst, ins_c, del_c, sub_c));
! }
! PG_FUNCTION_INFO_V1(levenshtein);
! Datum
! levenshtein(PG_FUNCTION_ARGS)
! {
! char *src;
! char *dst;
! src = _textout(PG_GETARG_DATUM(0));
! dst = _textout(PG_GETARG_DATUM(1));
! PG_RETURN_INT32(levenshtein_internal(src, dst, 1, 1, 1));
}
+
/*
* Calculates the metaphone of an input string.
* Returns number of characters requested
Index: contrib/fuzzystrmatch/fuzzystrmatch.h
===================================================================
RCS file: /projects/cvsroot/pgsql/contrib/fuzzystrmatch/fuzzystrmatch.h,v
retrieving revision 1.15
diff -c -r1.15 fuzzystrmatch.h
*** contrib/fuzzystrmatch/fuzzystrmatch.h 5 Jan 2007 22:19:18 -0000 1.15
--- contrib/fuzzystrmatch/fuzzystrmatch.h 17 Oct 2007 13:58:09 -0000
***************
*** 58,63 ****
--- 58,64 ----
/*
* External declarations
*/
+ extern Datum levenshtein_with_costs(PG_FUNCTION_ARGS);
extern Datum levenshtein(PG_FUNCTION_ARGS);
extern Datum metaphone(PG_FUNCTION_ARGS);
extern Datum soundex(PG_FUNCTION_ARGS);
***************
*** 82,87 ****
--- 83,89 ----
* Levenshtein
*/
#define MAX_LEVENSHTEIN_STRLEN 255
+ static int levenshtein_internal(char *s, char *t, int ins_c, int del_c, int sub_c);
/*
Index: contrib/fuzzystrmatch/fuzzystrmatch.sql.in
===================================================================
RCS file: /projects/cvsroot/pgsql/contrib/fuzzystrmatch/fuzzystrmatch.sql.in,v
retrieving revision 1.7
diff -c -r1.7 fuzzystrmatch.sql.in
*** contrib/fuzzystrmatch/fuzzystrmatch.sql.in 26 Jan 2005 08:04:04 -0000 1.7
--- contrib/fuzzystrmatch/fuzzystrmatch.sql.in 17 Oct 2007 13:58:09 -0000
***************
*** 1,6 ****
--- 1,10 ----
-- Adjust this setting to control where the objects get created.
SET search_path = public;
+ CREATE FUNCTION levenshtein (text,text,int,int,int) RETURNS int
+ AS 'MODULE_PATHNAME','levenshtein_with_costs'
+ LANGUAGE C IMMUTABLE STRICT;
+
CREATE FUNCTION levenshtein (text,text) RETURNS int
AS 'MODULE_PATHNAME','levenshtein'
LANGUAGE C IMMUTABLE STRICT;
