Here is the patch which adds levenshtein_less_equal function. I'm going to
add it to current commitfest.
----
With best regards,
Alexander Korotkov.
On Tue, Aug 3, 2010 at 3:23 AM, Robert Haas <robertmh...@gmail.com> wrote:
> On Mon, Aug 2, 2010 at 5:07 PM, Alexander Korotkov <aekorot...@gmail.com>
> wrote:
> > Now I think patch is as good as can be. :)
>
> OK, committed.
>
> > I'm going to prepare less-or-equal function in same manner as this patch.
>
> Sounds good. Since we're now more than half-way through this
> CommitFest and this patch has undergone quite a bit of change from
> what we started out with, I'd like to ask that you submit the new
> patch for the next CommitFest, to begin September 15th.
>
> https://commitfest.postgresql.org/action/commitfest_view/open
>
> --
> Robert Haas
> EnterpriseDB: http://www.enterprisedb.com
> The Enterprise Postgres Company
>
*** a/contrib/fuzzystrmatch/fuzzystrmatch.c
--- b/contrib/fuzzystrmatch/fuzzystrmatch.c
***************
*** 61,66 **** PG_MODULE_MAGIC;
--- 61,68 ----
*/
extern Datum levenshtein_with_costs(PG_FUNCTION_ARGS);
extern Datum levenshtein(PG_FUNCTION_ARGS);
+ extern Datum levenshtein_less_equal_with_costs(PG_FUNCTION_ARGS);
+ extern Datum levenshtein_less_equal(PG_FUNCTION_ARGS);
extern Datum metaphone(PG_FUNCTION_ARGS);
extern Datum soundex(PG_FUNCTION_ARGS);
extern Datum difference(PG_FUNCTION_ARGS);
***************
*** 92,98 **** soundex_code(char letter)
#define MAX_LEVENSHTEIN_STRLEN 255
static int levenshtein_internal(text *s, text *t,
! int ins_c, int del_c, int sub_c);
/*
--- 94,100 ----
#define MAX_LEVENSHTEIN_STRLEN 255
static int levenshtein_internal(text *s, text *t,
! int ins_c, int del_c, int sub_c, int max_d);
/*
***************
*** 202,211 **** rest_of_char_same(const char *s1, const char *s2, int len)
* between supplied strings. Generally
* (1, 1, 1) penalty costs suffices common
* cases, but your mileage may vary.
*/
static int
levenshtein_internal(text *s, text *t,
! int ins_c, int del_c, int sub_c)
{
int m,
n,
--- 204,217 ----
* between supplied strings. Generally
* (1, 1, 1) penalty costs suffices common
* cases, but your mileage may vary.
+ * Returns accurate value if max_d < 0 or
+ * actual distance is less or equal than
+ * max_d, otherwise returns value greater
+ * than max_d.
*/
static int
levenshtein_internal(text *s, text *t,
! int ins_c, int del_c, int sub_c, int max_d)
{
int m,
n,
***************
*** 219,224 **** levenshtein_internal(text *s, text *t,
--- 225,233 ----
const char *s_data;
const char *t_data;
const char *y;
+ const char *prev_x = NULL;
+ int curr_left = 0, curr_right = 0, prev_left, prev_right, d;
+ int delta = 0, min_d = 0, theor_max_d;
/* Extract a pointer to the actual character data. */
s_data = VARDATA_ANY(s);
***************
*** 238,243 **** levenshtein_internal(text *s, text *t,
--- 247,266 ----
return n * ins_c;
if (!n)
return m * del_c;
+
+ /*
+ * There is theoretical maximum distance based of string lengths. It
+ * represents the case, when no characters are matching. If max_d
+ * reaches this value than we can use accurate calculation of distance
+ * which is faster in this case.
+ */
+ if (max_d >= 0)
+ {
+ theor_max_d = Min(m*del_c + n*ins_c, (m > n) ?
+ (n * sub_c + (m - n) * del_c):(m * sub_c + (n - m) * ins_c)) - 1;
+ if (max_d >= theor_max_d)
+ max_d = -1;
+ }
/*
* For security concerns, restrict excessive CPU+RAM usage. (This
***************
*** 251,256 **** levenshtein_internal(text *s, text *t,
--- 274,296 ----
MAX_LEVENSHTEIN_STRLEN)));
/*
+ * We can find the minimal distance by the difference of string lengths.
+ */
+ if (max_d >= 0)
+ {
+ delta = m - n;
+ if (delta > 0)
+ min_d = delta * del_c;
+ else if (delta < 0)
+ min_d = - delta * ins_c;
+ else
+ min_d = 0;
+
+ if (min_d > max_d)
+ return max_d + 1;
+ }
+
+ /*
* In order to avoid calling pg_mblen() repeatedly on each character in s,
* we cache all the lengths before starting the main loop -- but if all the
* characters in both strings are single byte, then we skip this and use
***************
*** 286,369 **** levenshtein_internal(text *s, text *t,
curr = prev + m;
/* Initialize the "previous" row to 0..cols */
! for (i = 0; i < m; i++)
! prev[i] = i * del_c;
/* Loop through rows of the notional array */
for (y = t_data, j = 1; j < n; j++)
{
int *temp;
- const char *x = s_data;
int y_char_len = n != t_bytes + 1 ? pg_mblen(y) : 1;
/*
! * First cell must increment sequentially, as we're on the j'th row of
! * the (m+1)x(n+1) array.
! */
! curr[0] = j * ins_c;
!
! /*
! * This inner loop is critical to performance, so we include a
* fast-path to handle the (fairly common) case where no multibyte
* characters are in the mix. The fast-path is entitled to assume
* that if s_char_len is not initialized then BOTH strings contain
* only single-byte characters.
*/
! if (s_char_len != NULL)
{
! for (i = 1; i < m; i++)
! {
! int ins;
! int del;
! int sub;
! int x_char_len = s_char_len[i - 1];
! /*
! * Calculate costs for insertion, deletion, and substitution.
! *
! * When calculating cost for substitution, we compare the last
! * character of each possibly-multibyte character first,
! * because that's enough to rule out most mis-matches. If we
! * get past that test, then we compare the lengths and the
! * remaining bytes.
! */
! ins = prev[i] + ins_c;
! del = curr[i - 1] + del_c;
! if (x[x_char_len-1] == y[y_char_len-1]
! && x_char_len == y_char_len &&
! (x_char_len == 1 || rest_of_char_same(x, y, x_char_len)))
! sub = prev[i - 1];
! else
! sub = prev[i - 1] + sub_c;
! /* Take the one with minimum cost. */
! curr[i] = Min(ins, del);
! curr[i] = Min(curr[i], sub);
! /* Point to next character. */
! x += x_char_len;
}
! }
! else
! {
! for (i = 1; i < m; i++)
{
! int ins;
! int del;
! int sub;
! /* Calculate costs for insertion, deletion, and substitution. */
! ins = prev[i] + ins_c;
! del = curr[i - 1] + del_c;
! sub = prev[i - 1] + ((*x == *y) ? 0 : sub_c);
! /* Take the one with minimum cost. */
! curr[i] = Min(ins, del);
! curr[i] = Min(curr[i], sub);
! /* Point to next character. */
! x++;
}
}
/* Swap current row with previous row. */
--- 326,547 ----
curr = prev + m;
/* Initialize the "previous" row to 0..cols */
! if (max_d < 0)
! {
! for (i = 0; i < m; i++)
! prev[i] = i * del_c;
! }else{
! /*
! * In case of max_d limitation we fill first cell of the matrix with
! * minimal possible value of distance produced by difference of lengths.
! * We would maintain the minimal possible distance value, which
! * representing the case whan all non-compared characters of string
! * match, in cells of the matrix. When current cell is not on the
! * diagonal, which contains last cell, we anyway will have a penalty
! * of ins_c or del_c when returning to this diagonal. That's why in the
! * case of movement towards diagonal, which contain last cell, value
! * should be increased by ins_c + del_c. In the case of movement
! * backwards this diagonal cell value should not be increased. Also
! * we store the bounds of cells inside row where was less or equal than
! * max_d in order to avoid filling of cells which are knowingly greater
! * than max_d.
! */
! curr_left = 1;
! d = min_d;
! for (i = 0; i < delta; i++)
! {
! prev[i] = d;
! }
! curr_right = m;
! for (; i < m; i++)
! {
! prev[i] = d;
! d += (ins_c + del_c);
! if (d > max_d)
! {
! curr_right = i;
! break;
! }
! }
! prev_x = s_data;
! }
/* Loop through rows of the notional array */
for (y = t_data, j = 1; j < n; j++)
{
int *temp;
int y_char_len = n != t_bytes + 1 ? pg_mblen(y) : 1;
/*
! * This inner loop is critical to performance, that's why we
! * handle case without max_d limitation separatetly. Also we include a
* fast-path to handle the (fairly common) case where no multibyte
* characters are in the mix. The fast-path is entitled to assume
* that if s_char_len is not initialized then BOTH strings contain
* only single-byte characters.
*/
! if (max_d < 0)
{
! const char *x = s_data;
! /*
! * First cell must increment sequentially, as we're on the j'th row of
! * the (m+1)x(n+1) array.
! */
! curr[0] = j * ins_c;
! if (s_char_len != NULL)
! {
! for (i = 1; i < m; i++)
! {
! int ins;
! int del;
! int sub;
! int x_char_len = s_char_len[i - 1];
!
! /*
! * Calculate costs for insertion, deletion, and substitution.
! *
! * When calculating cost for substitution, we compare the last
! * character of each possibly-multibyte character first,
! * because that's enough to rule out most mis-matches. If we
! * get past that test, then we compare the lengths and the
! * remaining bytes.
! */
! ins = prev[i] + ins_c;
! del = curr[i - 1] + del_c;
! if (x[x_char_len-1] == y[y_char_len-1]
! && x_char_len == y_char_len &&
! (x_char_len == 1 || rest_of_char_same(x, y, x_char_len)))
! sub = prev[i - 1];
! else
! sub = prev[i - 1] + sub_c;
! /* Take the one with minimum cost. */
! curr[i] = Min(ins, del);
! curr[i] = Min(curr[i], sub);
! /* Point to next character. */
! x += x_char_len;
! }
}
! else
{
! for (i = 1; i < m; i++)
! {
! int ins;
! int del;
! int sub;
!
! /* Calculate costs for insertion, deletion, and substitution. */
! ins = prev[i] + ins_c;
! del = curr[i - 1] + del_c;
! sub = prev[i - 1] + ((*x == *y) ? 0 : sub_c);
! /* Take the one with minimum cost. */
! curr[i] = Min(ins, del);
! curr[i] = Min(curr[i], sub);
!
! /* Point to next character. */
! x++;
! }
! }
! }else{
! const char *x = prev_x;
!
! /*
! * Memorize the bounds of previos row where values was less or
! * equal than max_d.
! */
! prev_left = curr_left;
! prev_right = curr_right;
! curr_left = -1;
! /*
! * Fill the first cell of the row taking care about it's position
! * relatively last cell's diagnal.
! */
! if (delta >= 0)
! curr[0] = min_d + j * (ins_c + del_c);
! else
! {
! if (j <= - delta)
! curr[0] = min_d;
! else
! curr[0] = min_d + (j + delta) * (ins_c + del_c);
! }
! if (curr[0] <= max_d) curr_left = 1;
! if (s_char_len != NULL)
! {
! for (i = prev_left; i < m && i < prev_right + 2; i++)
! {
! int x_char_len = s_char_len[i - 1];
! d = max_d + 1;
! /*
! * Take minimum costs for insertion, deletion, and
! * substitution when corresponding previous cell doesn't
! * exceed bounds where value was less or equal than max_d.
! */
! if (i <= prev_right)
! d = Min(prev[i] + ((j + delta > i) ? (ins_c + del_c):0), d);
! if (i == 1 || i > prev_left)
! {
! d = Min(curr[i - 1] +
! ((i - delta > j) ? (ins_c + del_c) : 0), d);
! d = Min(prev[i - 1] + ((x[x_char_len-1] == y[y_char_len-1]
! && x_char_len == y_char_len
! && (x_char_len == 1 || rest_of_char_same(x, y, x_char_len)))
! ? 0 : sub_c), d);
! }
! curr[i] = d;
! if (d <= max_d)
! {
! if (curr_left == -1)
! {
! curr_left = i;
! /*
! * Save previos position in the string x in order
! * to avoid pg_mblen calls.
! */
! prev_x = x;
! }
! curr_right = i;
! }
! x += x_char_len;
! }
! }
! else
! {
! for (i = prev_left; i < m && i < prev_right + 2; i++)
! {
! /*
! * Take minimum costs for insertion, deletion, and
! * substitution when corresponding previous cell doesn't
! * exceed bounds where value was less or equal than max_d.
! */
! d = max_d + 1;
! if (i <= prev_right)
! d = Min(prev[i] + ((j + delta > i)?(ins_c + del_c):0), d);
! if (i == 1 || i > prev_left)
! {
! d = Min(curr[i - 1] + ((i - delta > j)?(ins_c + del_c):0), d);
! d = Min(prev[i - 1] + (*x == *y ? 0 : sub_c), d);
! }
! curr[i] = d;
! if (d <= max_d)
! {
! if (curr_left == -1)
! {
! curr_left = i;
! prev_x = x;
! }
! curr_right = i;
! }
! x++;
! }
}
+ if (curr_left == -1)
+ break;
}
/* Swap current row with previous row. */
***************
*** 376,381 **** levenshtein_internal(text *s, text *t,
--- 554,566 ----
}
/*
+ * If we have limitation of max_d and haven't less or equal, than max_d
+ * value in the last row than we should return max_d + 1.
+ */
+ if (max_d >= 0 && (curr_left == -1 || curr_right < m - 1))
+ return max_d + 1;
+
+ /*
* Because the final value was swapped from the previous row to the
* current row, that's where we'll find it.
*/
***************
*** 393,399 **** levenshtein_with_costs(PG_FUNCTION_ARGS)
int del_c = PG_GETARG_INT32(3);
int sub_c = PG_GETARG_INT32(4);
! PG_RETURN_INT32(levenshtein_internal(src, dst, ins_c, del_c, sub_c));
}
--- 578,584 ----
int del_c = PG_GETARG_INT32(3);
int sub_c = PG_GETARG_INT32(4);
! PG_RETURN_INT32(levenshtein_internal(src, dst, ins_c, del_c, sub_c, -1));
}
***************
*** 404,410 **** levenshtein(PG_FUNCTION_ARGS)
text *src = PG_GETARG_TEXT_PP(0);
text *dst = PG_GETARG_TEXT_PP(1);
! PG_RETURN_INT32(levenshtein_internal(src, dst, 1, 1, 1));
}
--- 589,622 ----
text *src = PG_GETARG_TEXT_PP(0);
text *dst = PG_GETARG_TEXT_PP(1);
! PG_RETURN_INT32(levenshtein_internal(src, dst, 1, 1, 1, -1));
! }
!
!
! PG_FUNCTION_INFO_V1(levenshtein_less_equal_with_costs);
! Datum
! levenshtein_less_equal_with_costs(PG_FUNCTION_ARGS)
! {
! text *src = PG_GETARG_TEXT_PP(0);
! text *dst = PG_GETARG_TEXT_PP(1);
! int ins_c = PG_GETARG_INT32(2);
! int del_c = PG_GETARG_INT32(3);
! int sub_c = PG_GETARG_INT32(4);
! int max_d = PG_GETARG_INT32(5);
!
! PG_RETURN_INT32(levenshtein_internal(src, dst, ins_c, del_c, sub_c, max_d));
! }
!
!
! PG_FUNCTION_INFO_V1(levenshtein_less_equal);
! Datum
! levenshtein_less_equal(PG_FUNCTION_ARGS)
! {
! text *src = PG_GETARG_TEXT_PP(0);
! text *dst = PG_GETARG_TEXT_PP(1);
! int max_d = PG_GETARG_INT32(2);
!
! PG_RETURN_INT32(levenshtein_internal(src, dst, 1, 1, 1, max_d));
}
*** a/contrib/fuzzystrmatch/fuzzystrmatch.sql.in
--- b/contrib/fuzzystrmatch/fuzzystrmatch.sql.in
***************
*** 11,16 **** CREATE OR REPLACE FUNCTION levenshtein (text,text,int,int,int) RETURNS int
--- 11,24 ----
AS 'MODULE_PATHNAME','levenshtein_with_costs'
LANGUAGE C IMMUTABLE STRICT;
+ CREATE OR REPLACE FUNCTION levenshtein_less_equal (text,text,int) RETURNS int
+ AS 'MODULE_PATHNAME','levenshtein_less_equal'
+ LANGUAGE C IMMUTABLE STRICT;
+
+ CREATE OR REPLACE FUNCTION levenshtein_less_equal (text,text,int,int,int,int) RETURNS int
+ AS 'MODULE_PATHNAME','levenshtein_less_equal_with_costs'
+ LANGUAGE C IMMUTABLE STRICT;
+
CREATE OR REPLACE FUNCTION metaphone (text,int) RETURNS text
AS 'MODULE_PATHNAME','metaphone'
LANGUAGE C IMMUTABLE STRICT;
*** a/doc/src/sgml/fuzzystrmatch.sgml
--- b/doc/src/sgml/fuzzystrmatch.sgml
***************
*** 84,89 **** SELECT * FROM s WHERE difference(s.nm, 'john') > 2;
--- 84,91 ----
<synopsis>
levenshtein(text source, text target, int ins_cost, int del_cost, int sub_cost) returns int
levenshtein(text source, text target) returns int
+ levenshtein_less_equal(text source, text target, int ins_cost, int del_cost, int sub_cost, int max_d) returns int
+ levenshtein_less_equal(text source, text target, int max_d) returns int
</synopsis>
<para>
***************
*** 92,97 **** levenshtein(text source, text target) returns int
--- 94,104 ----
specify how much to charge for a character insertion, deletion, or
substitution, respectively. You can omit the cost parameters, as in
the second version of the function; in that case they all default to 1.
+ <literal>levenshtein_less_equal</literal> is accelerated version of
+ levenshtein functon for low values of distance. If actual distance
+ is less or equal then max_d, then <literal>levenshtein_less_equal</literal>
+ returns accurate value of it. Otherwise this function returns value
+ which is greater than max_d.
</para>
<para>
***************
*** 110,115 **** test=# SELECT levenshtein('GUMBO', 'GAMBOL', 2,1,1);
--- 117,134 ----
-------------
3
(1 row)
+
+ test=# SELECT levenshtein_less_equal('extensive', 'exhaustive',2);
+ levenshtein_less_equal
+ ------------------------
+ 3
+ (1 row)
+
+ test=# SELECT levenshtein_less_equal('extensive', 'exhaustive',4);
+ levenshtein_less_equal
+ ------------------------
+ 4
+ (1 row)
</screen>
</sect2>
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
