I've reworked patch with your suggestion. In this version I found a little
slowdown in comparison with previous version:
SELECT * FROM words WHERE levenshtein_less_equal(a, 'extensize', 2) <= 2;
48,069 ms => 57,875 ms
SELECT * FROM words2 WHERE levenshtein_less_equal(a, 'клубничный', 3) <= 2;
100,073 ms => 113,975 ms
select * from phrases where levenshtein_less_equal('kkkknucklehead
courtliest sapphires be coniferous emolument antarctic Laocoon''s deadens
unseemly', a, 10) <= 10;
22,876 ms => 24,721 ms
test=# select * from phrases2 where levenshtein_less_equal('таяй
раскупорившийся передислоцируется юлианович праздничный лачужка присыхать
опппливший ффехтовальный уууудобряющий', a, 10) <= 10;
55,405 ms => 57,760 ms
I think it is caused by multiplication operation for each bound
movement. Probably,
this slowdown is ignorable or there is some way to achieve the same
performance.
----
With best regards,
Alexander Korotkov.
diff --git a/contrib/fuzzystrmatch/fuzzystrmatch.c b/contrib/fuzzystrmatch/fuzzystrmatch.c
index fe5fa88..7739431 100644
--- a/contrib/fuzzystrmatch/fuzzystrmatch.c
+++ b/contrib/fuzzystrmatch/fuzzystrmatch.c
@@ -5,7 +5,7 @@
*
* Joe Conway <[email protected]>
*
- * $PostgreSQL$
+ * contrib/fuzzystrmatch/fuzzystrmatch.c
* Copyright (c) 2001-2010, PostgreSQL Global Development Group
* ALL RIGHTS RESERVED;
*
@@ -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 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,6 +249,20 @@ levenshtein_internal(text *s, text *t,
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,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
@@ -277,92 +317,209 @@ levenshtein_internal(text *s, text *t,
++n;
/*
- * Instead of building an (m+1)x(n+1) array, we'll use two different
- * arrays of size m+1 for storing accumulated values. At each step one
- * represents the "previous" row and one is the "current" row of the
- * notional large array.
+ * One way to compute Levenshtein distance is to incrementally construct
+ * an (m+1)x(n+1) matrix where cell (i, j) represents the minimum number
+ * of operations required to transform the first i characters of s into
+ * the first j characters of t. The last column of the final row is the
+ * answer.
+ *
+ * We use that algorithm here with some modification. In lieu of holding
+ * the entire array in memory at once, we'll just use two arrays of size
+ * m+1 for storing accumulated values. At each step one array represents
+ * the "previous" row and one is the "current" row of the notional large
+ * array.
*/
prev = (int *) palloc(2 * m * sizeof(int));
curr = prev + m;
- /* Initialize the "previous" row to 0..cols */
+ /*
+ * 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 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;
- 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.
+ * To transform the first 0 characters of s into the first j
+ * characters of t, we must perform j insertions.
*/
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;
+
+ /*
+ * 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--;
}
}
@@ -376,6 +533,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 && 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.
*/
@@ -393,7 +557,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));
}
@@ -404,7 +568,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;
<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,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.
+ <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,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)
</screen>
</sect2>
--
Sent via pgsql-hackers mailing list ([email protected])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
