Sorry, I'm pretty *unconversant in git. Now, it should be ok.*
----
With best regards,
Alexander Korotkov.
*** 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 min_i = 0, max_i = 0, d;
+ int delta = 0, min_d = 0, theor_max_d;
/* Extract a pointer to the actual character data. */
s_data = VARDATA_ANY(s);
***************
*** 240,245 **** levenshtein_internal(text *s, text *t,
--- 249,268 ----
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
* implementation uses O(m) memory and has O(mn) complexity.)
*/
***************
*** 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
***************
*** 298,309 **** levenshtein_internal(text *s, text *t,
*/
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;
/*
--- 338,372 ----
*/
for (i = 0; i < m; i++)
prev[i] = i * del_c;
+ /*
+ * If we have limitation of max_d, than we'll maintain [min_i; max_i]
+ * interval, which bound cells, where sum of cell value and smallest
+ * possible residual cost is less or equal to max_d (we don't include
+ * 0 index into this interval). Residual cost represent cost of insertions
+ * or deletions for moving to diagonal, which containing bottom right cell.
+ * The sum value saves important property of original matrix, that this
+ * sum for cell always greater or equal than such sums for cells, which are
+ * used for it's calculation. That's why this sum can be used for bound
+ * interval.
+ */
+ if (max_d >= 0)
+ {
+ min_i = 1;
+ max_i = 1;
+ while (max_i < m && prev[max_i] +
+ ((delta - max_i > 0) ? (delta - max_i) * del_c :
+ (-delta + max_i) * ins_c) <= max_d)
+ {
+ max_i++;
+ }
+ max_i--;
+ 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;
/*
***************
*** 313,378 **** levenshtein_internal(text *s, text *t,
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++;
}
}
--- 376,525 ----
curr[0] = j * ins_c;
/*
! * 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;
!
! /*
! * Fill the first cell of the row taking care about it's position
! * relatively last cell's diagnal.
! */
! curr[0] = j * ins_c;
!
! if (s_char_len != NULL)
! {
! for (i = min_i; i < m && i < max_i + 2; i++)
! {
! int x_char_len = s_char_len[i - 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.
! */
! d = max_d + 1;
! if (i <= max_i)
! d = Min(prev[i] + ins_c, d);
! if (i == 1 || i > min_i)
! {
! d = Min(curr[i - 1] + del_c, 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;
! x += x_char_len;
! }
! }
! else
! {
! for (i = min_i; i < m && i < max_i + 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 <= max_i)
! d = Min(prev[i] + ins_c, d);
! if (i == 1 || i > min_i)
! {
! d = Min(curr[i - 1] + del_c, d);
! d = Min(prev[i - 1] + (*x == *y ? 0 : sub_c), d);
! }
! curr[i] = d;
! x++;
! }
! }
! if (max_i < m)
! max_i++;
! while (min_i <= max_i && curr[min_i] + ((delta - min_i + j > 0) ?
! (delta - min_i + j) * del_c : (-delta + min_i - j) * ins_c) > max_d)
! {
! if (s_char_len != NULL)
! prev_x += s_char_len[min_i - 1];
! else
! prev_x++;
! min_i++;
! }
! if (min_i > max_i)
! break;
! while (curr[max_i] + ((delta - max_i + j > 0) ? (delta - max_i + j) * del_c :
! (-delta + max_i - j) * ins_c) > max_d)
! {
! max_i--;
}
}
***************
*** 386,391 **** levenshtein_internal(text *s, text *t,
--- 533,545 ----
}
/*
+ * 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 && min_i > max_i)
+ 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.
*/
***************
*** 403,409 **** 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));
}
--- 557,563 ----
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));
}
***************
*** 414,420 **** 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));
}
--- 568,601 ----
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
