From 65b66309444767129c81c6aee8df33a214bcf4c5 Mon Sep 17 00:00:00 2001 From: Michael Paquier Date: Fri, 18 Jul 2014 16:44:28 +0900 Subject: [PATCH 1/2] Move Levenshtein functions to core All the functions, part of fuzzystrmatch, able to evaluate distances between strings are moved into core: - levenshtein - levenshtein_less_equal In order to unify the names of the functions in catalogs, the functions with costs are appended a prefix *_with_costs. Documentation, as well as regression tests are added. fuzzystrmatch is dumped to 1.1 at the same occasion. --- contrib/fuzzystrmatch/Makefile | 6 +- contrib/fuzzystrmatch/fuzzystrmatch--1.0--1.1.sql | 9 + contrib/fuzzystrmatch/fuzzystrmatch--1.0.sql | 44 -- contrib/fuzzystrmatch/fuzzystrmatch--1.1.sql | 28 ++ contrib/fuzzystrmatch/fuzzystrmatch.c | 69 --- contrib/fuzzystrmatch/fuzzystrmatch.control | 2 +- contrib/fuzzystrmatch/levenshtein.c | 403 --------------- doc/src/sgml/func.sgml | 68 +++ doc/src/sgml/fuzzystrmatch.sgml | 66 --- src/backend/utils/adt/Makefile | 4 +- src/backend/utils/adt/levenshtein.c | 565 ++++++++++++++++++++++ src/include/catalog/pg_proc.h | 10 + src/include/utils/builtins.h | 6 + src/include/utils/levenshtein.h | 27 ++ src/test/regress/expected/levenshtein.out | 27 ++ src/test/regress/parallel_schedule | 2 +- src/test/regress/serial_schedule | 1 + src/test/regress/sql/levenshtein.sql | 8 + 18 files changed, 755 insertions(+), 590 deletions(-) create mode 100644 contrib/fuzzystrmatch/fuzzystrmatch--1.0--1.1.sql delete mode 100644 contrib/fuzzystrmatch/fuzzystrmatch--1.0.sql create mode 100644 contrib/fuzzystrmatch/fuzzystrmatch--1.1.sql delete mode 100644 contrib/fuzzystrmatch/levenshtein.c create mode 100644 src/backend/utils/adt/levenshtein.c create mode 100644 src/include/utils/levenshtein.h create mode 100644 src/test/regress/expected/levenshtein.out create mode 100644 src/test/regress/sql/levenshtein.sql diff --git a/contrib/fuzzystrmatch/Makefile b/contrib/fuzzystrmatch/Makefile index 024265d..3d3c773 100644 --- a/contrib/fuzzystrmatch/Makefile +++ b/contrib/fuzzystrmatch/Makefile @@ -4,7 +4,8 @@ MODULE_big = fuzzystrmatch OBJS = fuzzystrmatch.o dmetaphone.o $(WIN32RES) EXTENSION = fuzzystrmatch -DATA = fuzzystrmatch--1.0.sql fuzzystrmatch--unpackaged--1.0.sql +DATA = fuzzystrmatch--1.0.sql fuzzystrmatch--unpackaged--1.0.sql \ + fuzzystrmatch--1.0--1.1.sql PGFILEDESC = "fuzzystrmatch - similarities and distance between strings" ifdef USE_PGXS @@ -17,6 +18,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--1.0--1.1.sql b/contrib/fuzzystrmatch/fuzzystrmatch--1.0--1.1.sql new file mode 100644 index 0000000..0fca2a6 --- /dev/null +++ b/contrib/fuzzystrmatch/fuzzystrmatch--1.0--1.1.sql @@ -0,0 +1,9 @@ +/* contrib/pageinspect/fuzzystrmatch--1.0--1.1.sql */ + +-- complain if script is sourced in psql, rather than via ALTER EXTENSION +\echo Use "ALTER EXTENSION fuzzystrmatch UPDATE TO 1.1" to load this file. \quit + +DROP FUNCTION levenshtein (text,text); +DROP FUNCTION levenshtein (text,text,int,int,int); +DROP FUNCTION levenshtein_less_equal (text,text,int); +DROP FUNCTION levenshtein_less_equal (text,text,int,int,int,int); diff --git a/contrib/fuzzystrmatch/fuzzystrmatch--1.0.sql b/contrib/fuzzystrmatch/fuzzystrmatch--1.0.sql deleted file mode 100644 index 1cf9b61..0000000 --- a/contrib/fuzzystrmatch/fuzzystrmatch--1.0.sql +++ /dev/null @@ -1,44 +0,0 @@ -/* contrib/fuzzystrmatch/fuzzystrmatch--1.0.sql */ - --- complain if script is sourced in psql, rather than via CREATE EXTENSION -\echo Use "CREATE EXTENSION fuzzystrmatch" to load this file. \quit - -CREATE FUNCTION levenshtein (text,text) RETURNS int -AS 'MODULE_PATHNAME','levenshtein' -LANGUAGE C IMMUTABLE STRICT; - -CREATE FUNCTION levenshtein (text,text,int,int,int) RETURNS int -AS 'MODULE_PATHNAME','levenshtein_with_costs' -LANGUAGE C IMMUTABLE STRICT; - -CREATE FUNCTION levenshtein_less_equal (text,text,int) RETURNS int -AS 'MODULE_PATHNAME','levenshtein_less_equal' -LANGUAGE C IMMUTABLE STRICT; - -CREATE 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 FUNCTION metaphone (text,int) RETURNS text -AS 'MODULE_PATHNAME','metaphone' -LANGUAGE C IMMUTABLE STRICT; - -CREATE FUNCTION soundex(text) RETURNS text -AS 'MODULE_PATHNAME', 'soundex' -LANGUAGE C IMMUTABLE STRICT; - -CREATE FUNCTION text_soundex(text) RETURNS text -AS 'MODULE_PATHNAME', 'soundex' -LANGUAGE C IMMUTABLE STRICT; - -CREATE FUNCTION difference(text,text) RETURNS int -AS 'MODULE_PATHNAME', 'difference' -LANGUAGE C IMMUTABLE STRICT; - -CREATE FUNCTION dmetaphone (text) RETURNS text -AS 'MODULE_PATHNAME', 'dmetaphone' -LANGUAGE C IMMUTABLE STRICT; - -CREATE FUNCTION dmetaphone_alt (text) RETURNS text -AS 'MODULE_PATHNAME', 'dmetaphone_alt' -LANGUAGE C IMMUTABLE STRICT; diff --git a/contrib/fuzzystrmatch/fuzzystrmatch--1.1.sql b/contrib/fuzzystrmatch/fuzzystrmatch--1.1.sql new file mode 100644 index 0000000..a4861ee --- /dev/null +++ b/contrib/fuzzystrmatch/fuzzystrmatch--1.1.sql @@ -0,0 +1,28 @@ +/* contrib/fuzzystrmatch/fuzzystrmatch--1.1.sql */ + +-- complain if script is sourced in psql, rather than via CREATE EXTENSION +\echo Use "CREATE EXTENSION fuzzystrmatch" to load this file. \quit + +CREATE FUNCTION metaphone (text,int) RETURNS text +AS 'MODULE_PATHNAME','metaphone' +LANGUAGE C IMMUTABLE STRICT; + +CREATE FUNCTION soundex(text) RETURNS text +AS 'MODULE_PATHNAME', 'soundex' +LANGUAGE C IMMUTABLE STRICT; + +CREATE FUNCTION text_soundex(text) RETURNS text +AS 'MODULE_PATHNAME', 'soundex' +LANGUAGE C IMMUTABLE STRICT; + +CREATE FUNCTION difference(text,text) RETURNS int +AS 'MODULE_PATHNAME', 'difference' +LANGUAGE C IMMUTABLE STRICT; + +CREATE FUNCTION dmetaphone (text) RETURNS text +AS 'MODULE_PATHNAME', 'dmetaphone' +LANGUAGE C IMMUTABLE STRICT; + +CREATE FUNCTION dmetaphone_alt (text) RETURNS text +AS 'MODULE_PATHNAME', 'dmetaphone_alt' +LANGUAGE C IMMUTABLE STRICT; diff --git a/contrib/fuzzystrmatch/fuzzystrmatch.c b/contrib/fuzzystrmatch/fuzzystrmatch.c index 7a53d8a..9923c17 100644 --- a/contrib/fuzzystrmatch/fuzzystrmatch.c +++ b/contrib/fuzzystrmatch/fuzzystrmatch.c @@ -40,7 +40,6 @@ #include -#include "mb/pg_wchar.h" #include "utils/builtins.h" PG_MODULE_MAGIC; @@ -154,74 +153,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) -{ - 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); - - PG_RETURN_INT32(levenshtein_internal(src, dst, ins_c, del_c, sub_c)); -} - - -PG_FUNCTION_INFO_V1(levenshtein); -Datum -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_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_less_equal_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_less_equal_internal(src, dst, 1, 1, 1, max_d)); -} - /* * Calculates the metaphone of an input string. diff --git a/contrib/fuzzystrmatch/fuzzystrmatch.control b/contrib/fuzzystrmatch/fuzzystrmatch.control index e257f09..6b2832a 100644 --- a/contrib/fuzzystrmatch/fuzzystrmatch.control +++ b/contrib/fuzzystrmatch/fuzzystrmatch.control @@ -1,5 +1,5 @@ # fuzzystrmatch extension comment = 'determine similarities and distance between strings' -default_version = '1.0' +default_version = '1.1' module_pathname = '$libdir/fuzzystrmatch' relocatable = true 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 - * - * 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 . - */ - -/* - * 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/doc/src/sgml/func.sgml b/doc/src/sgml/func.sgml index bf13140..84ae29c 100644 --- a/doc/src/sgml/func.sgml +++ b/doc/src/sgml/func.sgml @@ -7893,6 +7893,74 @@ CREATE TYPE rainbow AS ENUM ('red', 'orange', 'yellow', 'green', 'blue', 'purple + + Levenshtein functions + + + Levenshtein functions provide ways to calculate a distance between two + strings. + + + + Levenshtein Functions + + + + Function + Description + Example + Example Result + + + + + + + levenshtein + + levenshtein(text source, text target [, int ins_cost, int del_cost, int sub_cost]) + + + Returns the distance between the two given strings source + and target. + + levenshtein('GUMBO', 'GAMBOL') + 2 + + + + + levenshtein_less_equal + + levenshtein_less_equal(text source, text target [, int ins_cost, int del_cost, int sub_cost], int max_d) + + + Returns the less-equal distance between the two strings + source and target. + + levenshtein_less_equal('extensive', 'exhaustive', 2) + 3 + + + +
+ + + Both source and target can be any + non-null string, with a maximum of 255 bytes. The cost parameters + ins_cost, del_cost and sub_cost + 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 function 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. + + + Geometric Functions and Operators diff --git a/doc/src/sgml/fuzzystrmatch.sgml b/doc/src/sgml/fuzzystrmatch.sgml index f26bd90..f95d5aa 100644 --- a/doc/src/sgml/fuzzystrmatch.sgml +++ b/doc/src/sgml/fuzzystrmatch.sgml @@ -83,72 +83,6 @@ SELECT * FROM s WHERE difference(s.nm, 'john') > 2; - Levenshtein - - - This function calculates the Levenshtein distance between two strings: - - - - levenshtein - - - - levenshtein_less_equal - - - -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 - - - - Both source and target can be any - non-null string, with a maximum of 255 bytes. The cost parameters - 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 function 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. - - - - Examples: - - - -test=# SELECT levenshtein('GUMBO', 'GAMBOL'); - levenshtein -------------- - 2 -(1 row) - -test=# SELECT levenshtein('GUMBO', 'GAMBOL', 2,1,1); - levenshtein -------------- - 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) - - - - Metaphone diff --git a/src/backend/utils/adt/Makefile b/src/backend/utils/adt/Makefile index 7b4391b..7071afe 100644 --- a/src/backend/utils/adt/Makefile +++ b/src/backend/utils/adt/Makefile @@ -22,8 +22,8 @@ OBJS = acl.o arrayfuncs.o array_selfuncs.o array_typanalyze.o \ encode.o enum.o float.o format_type.o formatting.o genfile.o \ geo_ops.o geo_selfuncs.o inet_cidr_ntop.o inet_net_pton.o int.o \ int8.o json.o jsonb.o jsonb_gin.o jsonb_op.o jsonb_util.o \ - jsonfuncs.o like.o lockfuncs.o mac.o misc.o nabstime.o name.o \ - network.o network_gist.o network_selfuncs.o \ + jsonfuncs.o levenshtein.o like.o lockfuncs.o mac.o misc.o nabstime.o \ + name.o network.o network_gist.o network_selfuncs.o \ numeric.o numutils.o oid.o oracle_compat.o \ orderedsetaggs.o pg_lzcompress.o pg_locale.o pg_lsn.o \ pgstatfuncs.o pseudotypes.o quote.o rangetypes.o rangetypes_gist.o \ diff --git a/src/backend/utils/adt/levenshtein.c b/src/backend/utils/adt/levenshtein.c new file mode 100644 index 0000000..e405ad8 --- /dev/null +++ b/src/backend/utils/adt/levenshtein.c @@ -0,0 +1,565 @@ +/*------------------------------------------------------------------------- + * + * levenshtein.c + * Levenshtein distance implementation. + * + * Original author: Joe Conway + * + * 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 costsings 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(). + * + * All arguments should be strlen(s) <= MAX_LEVENSHTEIN_STRLEN. + * + * 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 0) + { + len--; + if (s1[len] != s2[len]) + return false; + } + return true; +} + +/* + * Calculates Levenshtein distance metric between supplied cstrings, 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. + */ + +/* + * levenshtein_common + * + * Common routine for all Levenstein functions. + */ +static int +levenshtein_common(const char *source, int slen, const char *target, + int tlen, int ins_c, int del_c, int sub_c, int max_d) +{ + int m, n; + int *prev; + int *curr; + int *s_char_len = NULL; + int i, + j; + const char *y; + int max_init; + int start_column, + stop_column; + int start_column_local, stop_column_local; + + /* Save value of max_d */ + max_init = max_d; + + 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; + + /* + * A common use for Levenshtein distance is to match column names. + * Therefore, restrict the size of MAX_LEVENSHTEIN_STRLEN such that this is + * guaranteed to work. + */ + StaticAssertStmt(NAMEDATALEN <= MAX_LEVENSHTEIN_STRLEN, + "Levenshtein hinting mechanism restricts NAMEDATALEN"); + + /* + * 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))); + + /* This optimization is done only for less-equal calculation */ + if (max_init >= 0) + { + /* 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; + } + } + } + else + { + /* + * Be sure to set if correctly stop and start columns in all cases. + */ + start_column = 0; + stop_column = m; + } + + /* + * 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. + */ + if (max_init >= 0) + stop_column_local = stop_column; + else + stop_column_local = m; + + for (i = 0; i < stop_column_local; 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; + + /* This optimization is done only for less-equal calculation */ + if (max_init >= 0) + { + /* + * 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; + } + + /* + * 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) + { + if (max_init < 0) + stop_column_local = m; + else + stop_column_local = stop_column; + + for (; i < stop_column_local; 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 + { + if (max_init < 0) + stop_column_local = m; + else + stop_column_local = stop_column; + + for (; i < stop_column_local; 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; + + /* + * 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_init >= 0 && 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; + } + } + + /* + * 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]; +} + +/* + * levenshtein_internal + * levenshtein_less_equal_internal + * + * Internal procedures for Levenshtein distance calculation. + */ +int +levenshtein_less_equal_internal(const char *source, int slen, const char *target, + int tlen, int ins_c, int del_c, int sub_c, int max_d) +{ + return levenshtein_common(source, slen, target, tlen, ins_c, + del_c, sub_c, max_d); +} + +int +levenshtein_internal(const char *source, int slen, const char *target, int tlen, + int ins_c, int del_c, int sub_c) +{ + return levenshtein_common(source, slen, target, tlen, ins_c, + del_c, sub_c, -1); +} + +/* + * levenshtein + * + * Calculate the Levenshtein distance of two strings. + */ +Datum +levenshtein(PG_FUNCTION_ARGS) +{ + text *src = PG_GETARG_TEXT_PP(0); + text *dst = PG_GETARG_TEXT_PP(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(levenshtein_internal(s_data, s_bytes, t_data, + t_bytes, 1, 1, 1)); +} + +/* + * levenshtein_with_costs + * + * Improved version of levenshtein with costs for character insertion, + * deletion and substitution. + */ +Datum +levenshtein_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); + 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(levenshtein_internal(s_data, s_bytes, t_data, + t_bytes, ins_c, del_c, sub_c)); +} + +/* + * levenshtein_less_equal + * + * Accelerated version of levenshtein for low distances. + */ +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); + 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(levenshtein_less_equal_internal(s_data, s_bytes, + t_data, t_bytes, 1, 1, 1, max_d)); +} + +/* + * levenshtein_less_equal_with_costs + * + * Accelerated version of levenshtein for low distances with costs for + * character insertion, deletion and substitution. + */ +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); + 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(levenshtein_less_equal_internal(s_data, s_bytes, + t_data, t_bytes, ins_c, del_c, sub_c, max_d)); +} diff --git a/src/include/catalog/pg_proc.h b/src/include/catalog/pg_proc.h index 0af1248..e7bd6ff 100644 --- a/src/include/catalog/pg_proc.h +++ b/src/include/catalog/pg_proc.h @@ -4973,6 +4973,16 @@ DESCR("peek at changes from replication slot"); DATA(insert OID = 3785 ( pg_logical_slot_peek_binary_changes PGNSP PGUID 12 1000 1000 25 0 f f f f f t v 4 0 2249 "19 3220 23 1009" "{19,3220,23,1009,3220,28,17}" "{i,i,i,v,o,o,o}" "{slot_name,upto_lsn,upto_nchanges,options,location,xid,data}" _null_ pg_logical_slot_peek_binary_changes _null_ _null_ _null_ )); DESCR("peek at binary changes from replication slot"); +/* levenshtein distance */ +DATA(insert OID = 3366 ( levenshtein PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 23 "25 25" _null_ _null_ _null_ _null_ levenshtein _null_ _null_ _null_)); +DESCR("Levenshtein distance between two strings"); +DATA(insert OID = 3367 ( levenshtein PGNSP PGUID 12 1 0 0 0 f f f f t f i 5 0 23 "25 25 23 23 23" _null_ _null_ _null_ _null_ levenshtein_with_costs _null_ _null_ _null_)); +DESCR("Levenshtein distance between two strings with costs"); +DATA(insert OID = 3368 ( levenshtein_less_equal PGNSP PGUID 12 1 0 0 0 f f f f t f i 3 0 23 "25 25 23" _null_ _null_ _null_ _null_ levenshtein_less_equal _null_ _null_ _null_)); +DESCR("Less-equal Levenshtein distance between two strings"); +DATA(insert OID = 3369 ( levenshtein_less_equal PGNSP PGUID 12 1 0 0 0 f f f f t f i 6 0 23 "25 25 23 23 23 23" _null_ _null_ _null_ _null_ levenshtein_less_equal_with_costs _null_ _null_ _null_)); +DESCR("Less-equal Levenshtein distance between two strings with costs"); + /* event triggers */ DATA(insert OID = 3566 ( pg_event_trigger_dropped_objects PGNSP PGUID 12 10 100 0 0 f f f f t t s 0 0 2249 "" "{26,26,23,25,25,25,25}" "{o,o,o,o,o,o,o}" "{classid, objid, objsubid, object_type, schema_name, object_name, object_identity}" _null_ pg_event_trigger_dropped_objects _null_ _null_ _null_ )); DESCR("list objects dropped by the current command"); diff --git a/src/include/utils/builtins.h b/src/include/utils/builtins.h index bbb5d39..b468c3c 100644 --- a/src/include/utils/builtins.h +++ b/src/include/utils/builtins.h @@ -851,6 +851,12 @@ extern Datum cidrecv(PG_FUNCTION_ARGS); extern Datum cidsend(PG_FUNCTION_ARGS); extern Datum cideq(PG_FUNCTION_ARGS); +/* levenshtein.c */ +extern Datum levenshtein(PG_FUNCTION_ARGS); +extern Datum levenshtein_with_costs(PG_FUNCTION_ARGS); +extern Datum levenshtein_less_equal(PG_FUNCTION_ARGS); +extern Datum levenshtein_less_equal_with_costs(PG_FUNCTION_ARGS); + /* like.c */ extern Datum namelike(PG_FUNCTION_ARGS); extern Datum namenlike(PG_FUNCTION_ARGS); diff --git a/src/include/utils/levenshtein.h b/src/include/utils/levenshtein.h new file mode 100644 index 0000000..6fa01d0 --- /dev/null +++ b/src/include/utils/levenshtein.h @@ -0,0 +1,27 @@ +/*------------------------------------------------------------------------- + * + * levenshtein.h + * Header file for the Levenshtein distance functions. + * + * Copyright (c) 2001-2014, PostgreSQL Global Development Group + * + * src/include/utils/levenshtein.h + * + *------------------------------------------------------------------------- + */ + +#ifndef LEVENSHTEIN_H +#define LEVENSHTEIN_H + +#include "postgres.h" + +/* Internal functions */ +extern int levenshtein_less_equal_internal(const char *source, int slen, + const char *target, int tlen, + int ins_c, int del_c, int sub_c, int max_d); + +extern int levenshtein_internal(const char *source, int slen, + const char *target, int tlen, + int ins_c, int del_c, int sub_c); + +#endif diff --git a/src/test/regress/expected/levenshtein.out b/src/test/regress/expected/levenshtein.out new file mode 100644 index 0000000..e5a77c3 --- /dev/null +++ b/src/test/regress/expected/levenshtein.out @@ -0,0 +1,27 @@ +-- +-- LEVENSHTEIN +-- +SELECT levenshtein('GUMBO', 'GAMBOL'); + levenshtein +------------- + 2 +(1 row) + +SELECT levenshtein('GUMBO', 'GAMBOL', 2, 1, 1); + levenshtein +------------- + 3 +(1 row) + +SELECT levenshtein_less_equal('extensive', 'exhaustive', 2); + levenshtein_less_equal +------------------------ + 3 +(1 row) + +SELECT levenshtein_less_equal('extensive', 'exhaustive', 1, 1, 1, 4); + levenshtein_less_equal +------------------------ + 4 +(1 row) + diff --git a/src/test/regress/parallel_schedule b/src/test/regress/parallel_schedule index c0416f4..5faf182 100644 --- a/src/test/regress/parallel_schedule +++ b/src/test/regress/parallel_schedule @@ -13,7 +13,7 @@ test: tablespace # ---------- # The first group of parallel tests # ---------- -test: boolean char name varchar text int2 int4 int8 oid float4 float8 bit numeric txid uuid enum money rangetypes pg_lsn regproc +test: boolean char name varchar text int2 int4 int8 oid float4 float8 bit numeric txid uuid enum money rangetypes pg_lsn regproc levenshtein # Depends on things setup during char, varchar and text test: strings diff --git a/src/test/regress/serial_schedule b/src/test/regress/serial_schedule index 16a1905..e980619 100644 --- a/src/test/regress/serial_schedule +++ b/src/test/regress/serial_schedule @@ -21,6 +21,7 @@ test: money test: rangetypes test: pg_lsn test: regproc +test: levenshtein test: strings test: numerology test: point diff --git a/src/test/regress/sql/levenshtein.sql b/src/test/regress/sql/levenshtein.sql new file mode 100644 index 0000000..7806bde --- /dev/null +++ b/src/test/regress/sql/levenshtein.sql @@ -0,0 +1,8 @@ +-- +-- LEVENSHTEIN +-- + +SELECT levenshtein('GUMBO', 'GAMBOL'); +SELECT levenshtein('GUMBO', 'GAMBOL', 2, 1, 1); +SELECT levenshtein_less_equal('extensive', 'exhaustive', 2); +SELECT levenshtein_less_equal('extensive', 'exhaustive', 1, 1, 1, 4); -- 2.0.1