commit 82d0eea7825062ed60ec1912a6ce3409419058bf Author: Robert Haas Date: Fri Sep 24 14:51:13 2010 -0400 levenshtein_less_equal-0.1 diff --git a/contrib/fuzzystrmatch/fuzzystrmatch.c b/contrib/fuzzystrmatch/fuzzystrmatch.c index 01084da..9a1c1ac 100644 --- a/contrib/fuzzystrmatch/fuzzystrmatch.c +++ b/contrib/fuzzystrmatch/fuzzystrmatch.c @@ -61,6 +61,8 @@ PG_MODULE_MAGIC; */ 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,7 +94,7 @@ 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); + int ins_c, int del_c, int sub_c, int max_d); /* @@ -202,10 +204,14 @@ 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. + * 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 ins_c, int del_c, int sub_c, int max_d) { int m, n, @@ -219,6 +225,9 @@ levenshtein_internal(text *s, text *t, 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,6 +247,20 @@ levenshtein_internal(text *s, text *t, 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,6 +274,23 @@ levenshtein_internal(text *s, text *t, 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 @@ -296,14 +336,50 @@ levenshtein_internal(text *s, text *t, * To transform the first i characters of s into the first 0 characters * of t, we must perform i deletions. */ - for (i = 0; i < m; i++) - prev[i] = i * del_c; + 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; - const char *x = s_data; int y_char_len = n != t_bytes + 1 ? pg_mblen(y) : 1; /* @@ -313,67 +389,175 @@ levenshtein_internal(text *s, text *t, curr[0] = j * ins_c; /* - * This inner loop is critical to performance, so we include a + * 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 (s_char_len != NULL) + if (max_d < 0) { - for (i = 1; i < m; i++) - { - int ins; - int del; - int sub; - int x_char_len = s_char_len[i - 1]; + 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; - /* - * 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; + 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); + /* 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; + /* Point to next character. */ + x += x_char_len; + } } - } - else - { - for (i = 1; i < m; i++) + else { - int ins; - int del; - int sub; + 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); + /* 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); + /* Take the one with minimum cost. */ + curr[i] = Min(ins, del); + curr[i] = Min(curr[i], sub); - /* Point to next character. */ - x++; + /* 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. */ @@ -386,6 +570,13 @@ levenshtein_internal(text *s, text *t, } /* + * 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. */ @@ -403,7 +594,7 @@ 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)); + PG_RETURN_INT32(levenshtein_internal(src, dst, ins_c, del_c, sub_c, -1)); } @@ -414,7 +605,34 @@ 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)); + 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)); } diff --git a/contrib/fuzzystrmatch/fuzzystrmatch.sql.in b/contrib/fuzzystrmatch/fuzzystrmatch.sql.in index 05a347d..0e75491 100644 --- a/contrib/fuzzystrmatch/fuzzystrmatch.sql.in +++ b/contrib/fuzzystrmatch/fuzzystrmatch.sql.in @@ -11,6 +11,14 @@ CREATE OR REPLACE FUNCTION levenshtein (text,text,int,int,int) RETURNS int 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; diff --git a/doc/src/sgml/fuzzystrmatch.sgml b/doc/src/sgml/fuzzystrmatch.sgml index 69777e4..83a39d4 100644 --- a/doc/src/sgml/fuzzystrmatch.sgml +++ b/doc/src/sgml/fuzzystrmatch.sgml @@ -84,6 +84,8 @@ SELECT * FROM s WHERE difference(s.nm, 'john') > 2; 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 @@ -92,6 +94,11 @@ levenshtein(text source, text target) returns int 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. + levenshtein_less_equal is accelerated version of + levenshtein functon for low values of distance. If actual distance + is less or equal then max_d, then levenshtein_less_equal + returns accurate value of it. Otherwise this function returns value + which is greater than max_d. @@ -110,6 +117,18 @@ test=# SELECT levenshtein('GUMBO', 'GAMBOL', 2,1,1); ------------- 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)