On Wed, Nov 12, 2014 at 4:54 PM, Peter Geoghegan <p...@heroku.com> wrote: > Attached patch moves the Levenshtein distance implementation into core.
Oops. Somehow managed to send a *.patch.swp file. :-) Here is the actual patch. -- Peter Geoghegan
From b7df918f1a52107637600f3b22d1cff18bd07ae1 Mon Sep 17 00:00:00 2001 From: Peter Geoghegan <p...@heroku.com> Date: Sat, 30 Nov 2013 23:15:00 -0800 Subject: [PATCH 1/2] Move Levenshtein distance implementation into core The fuzzystmatch Levenshtein distance implementation is moved from /contrib to core. However, the related SQL-callable functions may still only be used with the fuzzystmatch extension installed -- the fuzzystmatch definitions become simple forwarding stubs. It is not anticipated that the user-facing SQL functions will be moved into core in the future, due to the MAX_LEVENSHTEIN_STRLEN restriction. An in-core Levenshtein distance implementation is only anticipated to be helpful in building diagnostic messages. --- contrib/fuzzystrmatch/Makefile | 3 - contrib/fuzzystrmatch/fuzzystrmatch.c | 81 ++++--- contrib/fuzzystrmatch/levenshtein.c | 403 ---------------------------------- src/backend/utils/adt/Makefile | 2 + src/backend/utils/adt/levenshtein.c | 394 +++++++++++++++++++++++++++++++++ src/backend/utils/adt/varlena.c | 24 ++ src/include/utils/builtins.h | 5 + 7 files changed, 481 insertions(+), 431 deletions(-) delete mode 100644 contrib/fuzzystrmatch/levenshtein.c create mode 100644 src/backend/utils/adt/levenshtein.c diff --git a/contrib/fuzzystrmatch/Makefile b/contrib/fuzzystrmatch/Makefile index 024265d..0327d95 100644 --- a/contrib/fuzzystrmatch/Makefile +++ b/contrib/fuzzystrmatch/Makefile @@ -17,6 +17,3 @@ top_builddir = ../.. include $(top_builddir)/src/Makefile.global include $(top_srcdir)/contrib/contrib-global.mk endif - -# levenshtein.c is #included by fuzzystrmatch.c -fuzzystrmatch.o: fuzzystrmatch.c levenshtein.c diff --git a/contrib/fuzzystrmatch/fuzzystrmatch.c b/contrib/fuzzystrmatch/fuzzystrmatch.c index 7a53d8a..62e650f 100644 --- a/contrib/fuzzystrmatch/fuzzystrmatch.c +++ b/contrib/fuzzystrmatch/fuzzystrmatch.c @@ -154,23 +154,6 @@ getcode(char c) /* These prevent GH from becoming F */ #define NOGHTOF(c) (getcode(c) & 16) /* BDH */ -/* Faster than memcmp(), for this use case. */ -static inline bool -rest_of_char_same(const char *s1, const char *s2, int len) -{ - while (len > 0) - { - len--; - if (s1[len] != s2[len]) - return false; - } - return true; -} - -#include "levenshtein.c" -#define LEVENSHTEIN_LESS_EQUAL -#include "levenshtein.c" - PG_FUNCTION_INFO_V1(levenshtein_with_costs); Datum levenshtein_with_costs(PG_FUNCTION_ARGS) @@ -180,8 +163,20 @@ levenshtein_with_costs(PG_FUNCTION_ARGS) int ins_c = PG_GETARG_INT32(2); 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)); + const char *s_data; + const char *t_data; + int s_bytes, + t_bytes; + + /* Extract a pointer to the actual character data */ + s_data = VARDATA_ANY(src); + t_data = VARDATA_ANY(dst); + /* Determine length of each string in bytes and characters */ + s_bytes = VARSIZE_ANY_EXHDR(src); + t_bytes = VARSIZE_ANY_EXHDR(dst); + + PG_RETURN_INT32(varstr_leven(s_data, s_bytes, t_data, t_bytes, ins_c, + del_c, sub_c)); } @@ -191,8 +186,20 @@ 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)); + const char *s_data; + const char *t_data; + int s_bytes, + t_bytes; + + /* Extract a pointer to the actual character data */ + s_data = VARDATA_ANY(src); + t_data = VARDATA_ANY(dst); + /* Determine length of each string in bytes and characters */ + s_bytes = VARSIZE_ANY_EXHDR(src); + t_bytes = VARSIZE_ANY_EXHDR(dst); + + PG_RETURN_INT32(varstr_leven(s_data, s_bytes, t_data, t_bytes, 1, 1, + 1)); } @@ -206,8 +213,20 @@ levenshtein_less_equal_with_costs(PG_FUNCTION_ARGS) 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_less_equal_internal(src, dst, ins_c, del_c, sub_c, max_d)); + const char *s_data; + const char *t_data; + int s_bytes, + t_bytes; + + /* Extract a pointer to the actual character data */ + s_data = VARDATA_ANY(src); + t_data = VARDATA_ANY(dst); + /* Determine length of each string in bytes and characters */ + s_bytes = VARSIZE_ANY_EXHDR(src); + t_bytes = VARSIZE_ANY_EXHDR(dst); + + PG_RETURN_INT32(varstr_leven_less_equal(s_data, s_bytes, t_data, t_bytes, + ins_c, del_c, sub_c, max_d)); } @@ -218,8 +237,20 @@ 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_less_equal_internal(src, dst, 1, 1, 1, max_d)); + const char *s_data; + const char *t_data; + int s_bytes, + t_bytes; + + /* Extract a pointer to the actual character data */ + s_data = VARDATA_ANY(src); + t_data = VARDATA_ANY(dst); + /* Determine length of each string in bytes and characters */ + s_bytes = VARSIZE_ANY_EXHDR(src); + t_bytes = VARSIZE_ANY_EXHDR(dst); + + PG_RETURN_INT32(varstr_leven_less_equal(s_data, s_bytes, t_data, t_bytes, + 1, 1, 1, max_d)); } diff --git a/contrib/fuzzystrmatch/levenshtein.c b/contrib/fuzzystrmatch/levenshtein.c deleted file mode 100644 index 4f37a54..0000000 --- a/contrib/fuzzystrmatch/levenshtein.c +++ /dev/null @@ -1,403 +0,0 @@ -/* - * levenshtein.c - * - * Functions for "fuzzy" comparison of strings - * - * Joe Conway <m...@joeconway.com> - * - * Copyright (c) 2001-2014, PostgreSQL Global Development Group - * ALL RIGHTS RESERVED; - * - * levenshtein() - * ------------- - * Written based on a description of the algorithm by Michael Gilleland - * 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 <volkan.yaz...@gmail.com>. - */ - -/* - * External declarations for exported functions - */ -#ifdef LEVENSHTEIN_LESS_EQUAL -static int levenshtein_less_equal_internal(text *s, text *t, - int ins_c, int del_c, int sub_c, int max_d); -#else -static int levenshtein_internal(text *s, text *t, - int ins_c, int del_c, int sub_c); -#endif - -#define MAX_LEVENSHTEIN_STRLEN 255 - - -/* - * Calculates Levenshtein distance metric between supplied strings. Generally - * (1, 1, 1) penalty costs suffices for common cases, but your mileage may - * vary. - * - * 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. - * - * If max_d >= 0, we only need to provide an accurate answer when that answer - * is less than or equal to the bound. From any cell in the matrix, there is - * theoretical "minimum residual distance" from that cell to the last column - * of the final row. This minimum residual distance is zero when the - * untransformed portions of the strings are of equal length (because we might - * get lucky and find all the remaining characters matching) and is otherwise - * based on the minimum number of insertions or deletions needed to make them - * equal length. The residual distance grows as we move toward the upper - * right or lower left corners of the matrix. When the max_d bound is - * usefully tight, we can use this property to avoid computing the entirety - * of each row; instead, we maintain a start_column and stop_column that - * identify the portion of the matrix close to the diagonal which can still - * affect the final answer. - */ -static int -#ifdef LEVENSHTEIN_LESS_EQUAL -levenshtein_less_equal_internal(text *s, text *t, - int ins_c, int del_c, int sub_c, int max_d) -#else -levenshtein_internal(text *s, text *t, - int ins_c, int del_c, int sub_c) -#endif -{ - int m, - n, - s_bytes, - t_bytes; - int *prev; - int *curr; - int *s_char_len = NULL; - int i, - j; - const char *s_data; - const char *t_data; - const char *y; - - /* - * For levenshtein_less_equal_internal, we have real variables called - * start_column and stop_column; otherwise it's just short-hand for 0 and - * m. - */ -#ifdef LEVENSHTEIN_LESS_EQUAL - int start_column, - stop_column; - -#undef START_COLUMN -#undef STOP_COLUMN -#define START_COLUMN start_column -#define STOP_COLUMN stop_column -#else -#undef START_COLUMN -#undef STOP_COLUMN -#define START_COLUMN 0 -#define STOP_COLUMN m -#endif - - /* Extract a pointer to the actual character data. */ - s_data = VARDATA_ANY(s); - t_data = VARDATA_ANY(t); - - /* Determine length of each string in bytes and characters. */ - s_bytes = VARSIZE_ANY_EXHDR(s); - t_bytes = VARSIZE_ANY_EXHDR(t); - m = pg_mbstrlen_with_len(s_data, s_bytes); - n = pg_mbstrlen_with_len(t_data, t_bytes); - - /* - * We can transform an empty s into t with n insertions, or a non-empty t - * into an empty s with m deletions. - */ - if (!m) - return n * ins_c; - if (!n) - return m * del_c; - - /* - * For security concerns, restrict excessive CPU+RAM usage. (This - * implementation uses O(m) memory and has O(mn) complexity.) - */ - if (m > MAX_LEVENSHTEIN_STRLEN || - n > MAX_LEVENSHTEIN_STRLEN) - ereport(ERROR, - (errcode(ERRCODE_INVALID_PARAMETER_VALUE), - errmsg("argument exceeds the maximum length of %d bytes", - MAX_LEVENSHTEIN_STRLEN))); - -#ifdef LEVENSHTEIN_LESS_EQUAL - /* Initialize start and stop columns. */ - start_column = 0; - stop_column = m + 1; - - /* - * If max_d >= 0, determine whether the bound is impossibly tight. If so, - * return max_d + 1 immediately. Otherwise, determine whether it's tight - * enough to limit the computation we must perform. If so, figure out - * initial stop column. - */ - if (max_d >= 0) - { - int min_theo_d; /* Theoretical minimum distance. */ - int max_theo_d; /* Theoretical maximum distance. */ - int net_inserts = n - m; - - min_theo_d = net_inserts < 0 ? - -net_inserts * del_c : net_inserts * ins_c; - if (min_theo_d > max_d) - return max_d + 1; - if (ins_c + del_c < sub_c) - sub_c = ins_c + del_c; - max_theo_d = min_theo_d + sub_c * Min(m, n); - if (max_d >= max_theo_d) - max_d = -1; - else if (ins_c + del_c > 0) - { - /* - * Figure out how much of the first row of the notional matrix we - * need to fill in. If the string is growing, the theoretical - * minimum distance already incorporates the cost of deleting the - * number of characters necessary to make the two strings equal in - * length. Each additional deletion forces another insertion, so - * the best-case total cost increases by ins_c + del_c. If the - * string is shrinking, the minimum theoretical cost assumes no - * excess deletions; that is, we're starting no further right than - * column n - m. If we do start further right, the best-case - * total cost increases by ins_c + del_c for each move right. - */ - int slack_d = max_d - min_theo_d; - int best_column = net_inserts < 0 ? -net_inserts : 0; - - stop_column = best_column + (slack_d / (ins_c + del_c)) + 1; - if (stop_column > m) - stop_column = m + 1; - } - } -#endif - - /* - * 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 a fast-path in the main loop. If only one string contains - * multi-byte characters, we still build the array, so that the fast-path - * needn't deal with the case where the array hasn't been initialized. - */ - if (m != s_bytes || n != t_bytes) - { - int i; - const char *cp = s_data; - - s_char_len = (int *) palloc((m + 1) * sizeof(int)); - for (i = 0; i < m; ++i) - { - s_char_len[i] = pg_mblen(cp); - cp += s_char_len[i]; - } - s_char_len[i] = 0; - } - - /* One more cell for initialization column and row. */ - ++m; - ++n; - - /* Previous and current rows of notional array. */ - prev = (int *) palloc(2 * m * sizeof(int)); - curr = prev + m; - - /* - * To transform the first i characters of s into the first 0 characters of - * t, we must perform i deletions. - */ - for (i = START_COLUMN; i < STOP_COLUMN; 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; - -#ifdef LEVENSHTEIN_LESS_EQUAL - - /* - * In the best case, values percolate down the diagonal unchanged, so - * we must increment stop_column unless it's already on the right end - * of the array. The inner loop will read prev[stop_column], so we - * have to initialize it even though it shouldn't affect the result. - */ - if (stop_column < m) - { - prev[stop_column] = max_d + 1; - ++stop_column; - } - - /* - * The main loop fills in curr, but curr[0] needs a special case: to - * transform the first 0 characters of s into the first j characters - * of t, we must perform j insertions. However, if start_column > 0, - * this special case does not apply. - */ - if (start_column == 0) - { - curr[0] = j * ins_c; - i = 1; - } - else - i = start_column; -#else - curr[0] = j * ins_c; - i = 1; -#endif - - /* - * 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 < STOP_COLUMN; 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 < STOP_COLUMN; 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. */ - temp = curr; - curr = prev; - prev = temp; - - /* Point to next character. */ - y += y_char_len; - -#ifdef LEVENSHTEIN_LESS_EQUAL - - /* - * This chunk of code represents a significant performance hit if used - * in the case where there is no max_d bound. This is probably not - * because the max_d >= 0 test itself is expensive, but rather because - * the possibility of needing to execute this code prevents tight - * optimization of the loop as a whole. - */ - if (max_d >= 0) - { - /* - * The "zero point" is the column of the current row where the - * remaining portions of the strings are of equal length. There - * are (n - 1) characters in the target string, of which j have - * been transformed. There are (m - 1) characters in the source - * string, so we want to find the value for zp where (n - 1) - j = - * (m - 1) - zp. - */ - int zp = j - (n - m); - - /* Check whether the stop column can slide left. */ - while (stop_column > 0) - { - int ii = stop_column - 1; - int net_inserts = ii - zp; - - if (prev[ii] + (net_inserts > 0 ? net_inserts * ins_c : - -net_inserts * del_c) <= max_d) - break; - stop_column--; - } - - /* Check whether the start column can slide right. */ - while (start_column < stop_column) - { - int net_inserts = start_column - zp; - - if (prev[start_column] + - (net_inserts > 0 ? net_inserts * ins_c : - -net_inserts * del_c) <= max_d) - break; - - /* - * We'll never again update these values, so we must make sure - * there's nothing here that could confuse any future - * iteration of the outer loop. - */ - prev[start_column] = max_d + 1; - curr[start_column] = max_d + 1; - if (start_column != 0) - s_data += (s_char_len != NULL) ? s_char_len[start_column - 1] : 1; - start_column++; - } - - /* If they cross, we're going to exceed the bound. */ - if (start_column >= stop_column) - return max_d + 1; - } -#endif - } - - /* - * 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]; -} diff --git a/src/backend/utils/adt/Makefile b/src/backend/utils/adt/Makefile index 7b4391b..3ea9bf4 100644 --- a/src/backend/utils/adt/Makefile +++ b/src/backend/utils/adt/Makefile @@ -38,4 +38,6 @@ OBJS = acl.o arrayfuncs.o array_selfuncs.o array_typanalyze.o \ like.o: like.c like_match.c +varlena.o: varlena.c levenshtein.c + include $(top_srcdir)/src/backend/common.mk diff --git a/src/backend/utils/adt/levenshtein.c b/src/backend/utils/adt/levenshtein.c new file mode 100644 index 0000000..bf4f1dd --- /dev/null +++ b/src/backend/utils/adt/levenshtein.c @@ -0,0 +1,394 @@ +/*------------------------------------------------------------------------- + * + * levenshtein.c + * Levenshtein distance implementation. + * + * Original author: Joe Conway <m...@joeconway.com> + * + * This file is included by varlena.c twice, to provide matching code for (1) + * Levenshtein distance with custom costings, and (2) Levenshtein distance with + * custom costings and a "max" value above which exact distances are not + * interesting. Before the inclusion, we rely on the presence of the inline + * function rest_of_char_same(). + * + * Written based on a description of the algorithm by Michael Gilleland 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 <volkan.yaz...@gmail.com. + * + * Copyright (c) 2001-2014, PostgreSQL Global Development Group + * + * IDENTIFICATION + * src/backend/utils/adt/levenshtein.c + * + *------------------------------------------------------------------------- + */ +#define MAX_LEVENSHTEIN_STRLEN 255 + +/* + * Calculates Levenshtein distance metric between supplied csrings, which are + * not necessarily null-terminated. Generally (1, 1, 1) penalty costs suffices + * for common cases, but your mileage may vary. + * + * 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. + * + * If max_d >= 0, we only need to provide an accurate answer when that answer + * is less than or equal to the bound. From any cell in the matrix, there is + * theoretical "minimum residual distance" from that cell to the last column + * of the final row. This minimum residual distance is zero when the + * untransformed portions of the strings are of equal length (because we might + * get lucky and find all the remaining characters matching) and is otherwise + * based on the minimum number of insertions or deletions needed to make them + * equal length. The residual distance grows as we move toward the upper + * right or lower left corners of the matrix. When the max_d bound is + * usefully tight, we can use this property to avoid computing the entirety + * of each row; instead, we maintain a start_column and stop_column that + * identify the portion of the matrix close to the diagonal which can still + * affect the final answer. + */ +int +#ifdef LEVENSHTEIN_LESS_EQUAL +varstr_leven_less_equal(const char *source, int slen, const char *target, + int tlen, int ins_c, int del_c, int sub_c, int max_d) +#else +varstr_leven(const char *source, int slen, const char *target, int tlen, + int ins_c, int del_c, int sub_c) +#endif +{ + int m, + n; + int *prev; + int *curr; + int *s_char_len = NULL; + int i, + j; + const char *y; + + /* + * For varstr_levenshtein_less_equal, we have real variables called + * start_column and stop_column; otherwise it's just short-hand for 0 and + * m. + */ +#ifdef LEVENSHTEIN_LESS_EQUAL + int start_column, + stop_column; + +#undef START_COLUMN +#undef STOP_COLUMN +#define START_COLUMN start_column +#define STOP_COLUMN stop_column +#else +#undef START_COLUMN +#undef STOP_COLUMN +#define START_COLUMN 0 +#define STOP_COLUMN m +#endif + + /* + * A common use for Levenshtein distance is to match attributes when + * building diagnostic, user-visible messages. Restrict the size of + * MAX_LEVENSHTEIN_STRLEN at compile time such that this is guaranteed to + * work. + */ + StaticAssertStmt(NAMEDATALEN <= MAX_LEVENSHTEIN_STRLEN, + "Levenshtein hinting mechanism restricts NAMEDATALEN"); + + m = pg_mbstrlen_with_len(source, slen); + n = pg_mbstrlen_with_len(target, tlen); + + /* + * We can transform an empty s into t with n insertions, or a non-empty t + * into an empty s with m deletions. + */ + if (!m) + return n * ins_c; + if (!n) + return m * del_c; + + /* + * For security concerns, restrict excessive CPU+RAM usage. (This + * implementation uses O(m) memory and has O(mn) complexity.) + */ + if (m > MAX_LEVENSHTEIN_STRLEN || + n > MAX_LEVENSHTEIN_STRLEN) + ereport(ERROR, + (errcode(ERRCODE_INVALID_PARAMETER_VALUE), + errmsg("argument exceeds the maximum length of %d bytes", + MAX_LEVENSHTEIN_STRLEN))); + +#ifdef LEVENSHTEIN_LESS_EQUAL + /* Initialize start and stop columns. */ + start_column = 0; + stop_column = m + 1; + + /* + * If max_d >= 0, determine whether the bound is impossibly tight. If so, + * return max_d + 1 immediately. Otherwise, determine whether it's tight + * enough to limit the computation we must perform. If so, figure out + * initial stop column. + */ + if (max_d >= 0) + { + int min_theo_d; /* Theoretical minimum distance. */ + int max_theo_d; /* Theoretical maximum distance. */ + int net_inserts = n - m; + + min_theo_d = net_inserts < 0 ? + -net_inserts * del_c : net_inserts * ins_c; + if (min_theo_d > max_d) + return max_d + 1; + if (ins_c + del_c < sub_c) + sub_c = ins_c + del_c; + max_theo_d = min_theo_d + sub_c * Min(m, n); + if (max_d >= max_theo_d) + max_d = -1; + else if (ins_c + del_c > 0) + { + /* + * Figure out how much of the first row of the notional matrix we + * need to fill in. If the string is growing, the theoretical + * minimum distance already incorporates the cost of deleting the + * number of characters necessary to make the two strings equal in + * length. Each additional deletion forces another insertion, so + * the best-case total cost increases by ins_c + del_c. If the + * string is shrinking, the minimum theoretical cost assumes no + * excess deletions; that is, we're starting no further right than + * column n - m. If we do start further right, the best-case + * total cost increases by ins_c + del_c for each move right. + */ + int slack_d = max_d - min_theo_d; + int best_column = net_inserts < 0 ? -net_inserts : 0; + + stop_column = best_column + (slack_d / (ins_c + del_c)) + 1; + if (stop_column > m) + stop_column = m + 1; + } + } +#endif + + /* + * 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 a fast-path in the main loop. If only one string contains + * multi-byte characters, we still build the array, so that the fast-path + * needn't deal with the case where the array hasn't been initialized. + */ + if (m != slen || n != tlen) + { + int i; + const char *cp = source; + + s_char_len = (int *) palloc((m + 1) * sizeof(int)); + for (i = 0; i < m; ++i) + { + s_char_len[i] = pg_mblen(cp); + cp += s_char_len[i]; + } + s_char_len[i] = 0; + } + + /* One more cell for initialization column and row. */ + ++m; + ++n; + + /* Previous and current rows of notional array. */ + prev = (int *) palloc(2 * m * sizeof(int)); + curr = prev + m; + + /* + * To transform the first i characters of s into the first 0 characters of + * t, we must perform i deletions. + */ + for (i = START_COLUMN; i < STOP_COLUMN; i++) + prev[i] = i * del_c; + + /* Loop through rows of the notional array */ + for (y = target, j = 1; j < n; j++) + { + int *temp; + const char *x = source; + int y_char_len = n != tlen + 1 ? pg_mblen(y) : 1; + +#ifdef LEVENSHTEIN_LESS_EQUAL + + /* + * In the best case, values percolate down the diagonal unchanged, so + * we must increment stop_column unless it's already on the right end + * of the array. The inner loop will read prev[stop_column], so we + * have to initialize it even though it shouldn't affect the result. + */ + if (stop_column < m) + { + prev[stop_column] = max_d + 1; + ++stop_column; + } + + /* + * The main loop fills in curr, but curr[0] needs a special case: to + * transform the first 0 characters of s into the first j characters + * of t, we must perform j insertions. However, if start_column > 0, + * this special case does not apply. + */ + if (start_column == 0) + { + curr[0] = j * ins_c; + i = 1; + } + else + i = start_column; +#else + curr[0] = j * ins_c; + i = 1; +#endif + + /* + * 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 < STOP_COLUMN; 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 < STOP_COLUMN; 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. */ + temp = curr; + curr = prev; + prev = temp; + + /* Point to next character. */ + y += y_char_len; + +#ifdef LEVENSHTEIN_LESS_EQUAL + + /* + * This chunk of code represents a significant performance hit if used + * in the case where there is no max_d bound. This is probably not + * because the max_d >= 0 test itself is expensive, but rather because + * the possibility of needing to execute this code prevents tight + * optimization of the loop as a whole. + */ + if (max_d >= 0) + { + /* + * The "zero point" is the column of the current row where the + * remaining portions of the strings are of equal length. There + * are (n - 1) characters in the target string, of which j have + * been transformed. There are (m - 1) characters in the source + * string, so we want to find the value for zp where (n - 1) - j = + * (m - 1) - zp. + */ + int zp = j - (n - m); + + /* Check whether the stop column can slide left. */ + while (stop_column > 0) + { + int ii = stop_column - 1; + int net_inserts = ii - zp; + + if (prev[ii] + (net_inserts > 0 ? net_inserts * ins_c : + -net_inserts * del_c) <= max_d) + break; + stop_column--; + } + + /* Check whether the start column can slide right. */ + while (start_column < stop_column) + { + int net_inserts = start_column - zp; + + if (prev[start_column] + + (net_inserts > 0 ? net_inserts * ins_c : + -net_inserts * del_c) <= max_d) + break; + + /* + * We'll never again update these values, so we must make sure + * there's nothing here that could confuse any future + * iteration of the outer loop. + */ + prev[start_column] = max_d + 1; + curr[start_column] = max_d + 1; + if (start_column != 0) + source += (s_char_len != NULL) ? s_char_len[start_column - 1] : 1; + start_column++; + } + + /* If they cross, we're going to exceed the bound. */ + if (start_column >= stop_column) + return max_d + 1; + } +#endif + } + + /* + * 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]; +} diff --git a/src/backend/utils/adt/varlena.c b/src/backend/utils/adt/varlena.c index c3171b5..48afc61 100644 --- a/src/backend/utils/adt/varlena.c +++ b/src/backend/utils/adt/varlena.c @@ -1546,6 +1546,30 @@ varstr_cmp(char *arg1, int len1, char *arg2, int len2, Oid collid) return result; } +/* + * varstr_leven() + * varstr_leven_less_equal() + * Levenshtein distance functions. All arguments should be strlen(s) <= 255. + * Guaranteed to work with Name datatype's cstrings. + * For full details see levenshtein.c. + * + * Helper function. Faster than memcmp(), for this use case. + */ +static inline bool +rest_of_char_same(const char *s1, const char *s2, int len) +{ + while (len > 0) + { + len--; + if (s1[len] != s2[len]) + return false; + } + return true; +} +/* Expand each Levenshtein distance variant */ +#include "levenshtein.c" +#define LEVENSHTEIN_LESS_EQUAL +#include "levenshtein.c" /* text_cmp() * Internal comparison function for text strings. diff --git a/src/include/utils/builtins.h b/src/include/utils/builtins.h index 3ba34f8..7298c93 100644 --- a/src/include/utils/builtins.h +++ b/src/include/utils/builtins.h @@ -786,6 +786,11 @@ extern Datum textoverlay_no_len(PG_FUNCTION_ARGS); extern Datum name_text(PG_FUNCTION_ARGS); extern Datum text_name(PG_FUNCTION_ARGS); extern int varstr_cmp(char *arg1, int len1, char *arg2, int len2, Oid collid); +extern int varstr_leven(const char *source, int slen, const char *target, + int tlen, int ins_c, int del_c, int sub_c); +extern int varstr_leven_less_equal(const char *source, int slen, + const char *target, int tlen, int ins_c, + int del_c, int sub_c, int max_d); extern List *textToQualifiedNameList(text *textval); extern bool SplitIdentifierString(char *rawstring, char separator, List **namelist); -- 1.9.1
-- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers