levenshtein_less_equal-0.2.patch

commit 82d0eea7825062ed60ec1912a6ce3409419058bf
Author: Robert Haas <rhaas@postgresql.org>
Date:   Fri Sep 24 14:51:13 2010 -0400

    levenshtein_less_equal-0.1

diff --git a/contrib/fuzzystrmatch/fuzzystrmatch.c b/contrib/fuzzystrmatch/fuzzystrmatch.c
index 01084da..9a1c1ac 100644
--- a/contrib/fuzzystrmatch/fuzzystrmatch.c
+++ b/contrib/fuzzystrmatch/fuzzystrmatch.c
@@ -61,6 +61,8 @@ PG_MODULE_MAGIC;
  */
 extern Datum levenshtein_with_costs(PG_FUNCTION_ARGS);
 extern Datum levenshtein(PG_FUNCTION_ARGS);
+extern Datum levenshtein_less_equal_with_costs(PG_FUNCTION_ARGS);
+extern Datum levenshtein_less_equal(PG_FUNCTION_ARGS);
 extern Datum metaphone(PG_FUNCTION_ARGS);
 extern Datum soundex(PG_FUNCTION_ARGS);
 extern Datum difference(PG_FUNCTION_ARGS);
@@ -92,7 +94,7 @@ soundex_code(char letter)
 #define MAX_LEVENSHTEIN_STRLEN		255
 
 static int levenshtein_internal(text *s, text *t,
-					 int ins_c, int del_c, int sub_c);
+					 int ins_c, int del_c, int sub_c, int max_d);
 
 
 /*
@@ -202,10 +204,14 @@ rest_of_char_same(const char *s1, const char *s2, int len)
  *						  between supplied strings. Generally
  *						  (1, 1, 1) penalty costs suffices common
  *						  cases, but your mileage may vary.
+ *						  Returns accurate value if max_d < 0 or
+ *						  actual distance is less or equal than
+ *						  max_d, otherwise returns value greater
+ *						  than max_d.
  */
 static int
 levenshtein_internal(text *s, text *t,
-					 int ins_c, int del_c, int sub_c)
+					 int ins_c, int del_c, int sub_c, int max_d)
 {
 	int			m,
 				n,
@@ -219,6 +225,9 @@ levenshtein_internal(text *s, text *t,
 	const char *s_data;
 	const char *t_data;
 	const char *y;
+	const char *prev_x = NULL;
+	int        curr_left = 0, curr_right = 0, prev_left, prev_right, d;
+	int        delta = 0, min_d = 0, theor_max_d;
 
 	/* Extract a pointer to the actual character data. */
 	s_data = VARDATA_ANY(s);
@@ -238,6 +247,20 @@ levenshtein_internal(text *s, text *t,
 		return n * ins_c;
 	if (!n)
 		return m * del_c;
+	
+	/*
+	 * There is theoretical maximum distance based of string lengths. It
+	 * represents the case, when no characters are matching. If max_d
+	 * reaches this value than we can use accurate calculation of distance
+	 * which is faster in this case.
+	 */
+	if (max_d >= 0)
+	{
+		theor_max_d = Min(m*del_c + n*ins_c, (m > n) ?
+			(n * sub_c + (m - n) * del_c):(m * sub_c + (n - m) * ins_c)) - 1;
+		if (max_d >= theor_max_d)
+			max_d = -1;
+	}
 
 	/*
 	 * For security concerns, restrict excessive CPU+RAM usage. (This
@@ -251,6 +274,23 @@ levenshtein_internal(text *s, text *t,
 						MAX_LEVENSHTEIN_STRLEN)));
 
 	/*
+	 * We can find the minimal distance by the difference of string lengths.
+	 */
+	if (max_d >= 0)
+	{
+		delta = m - n;
+		if (delta > 0)
+			min_d = delta * del_c;
+		else if (delta < 0)
+			min_d = - delta * ins_c;
+		else
+			min_d = 0;
+
+		if (min_d > max_d)
+			return max_d + 1;
+	}
+
+	/*
 	 * In order to avoid calling pg_mblen() repeatedly on each character in s,
 	 * we cache all the lengths before starting the main loop -- but if all the
 	 * characters in both strings are single byte, then we skip this and use
@@ -296,14 +336,50 @@ levenshtein_internal(text *s, text *t,
 	 * To transform the first i characters of s into the first 0 characters
 	 * of t, we must perform i deletions.
 	 */
-	for (i = 0; i < m; i++)
-		prev[i] = i * del_c;
+	if (max_d < 0)
+	{
+		for (i = 0; i < m; i++)
+			prev[i] = i * del_c;
+	}else{
+		/*
+		 * In case of max_d limitation we fill first cell of the matrix with
+		 * minimal possible value of distance produced by difference of lengths.
+		 * We would maintain the minimal possible distance value, which
+		 * representing the case whan all non-compared characters of string 
+		 * match, in cells of the matrix. When current cell is not on the
+		 * diagonal, which contains last cell, we anyway will have a penalty
+		 * of ins_c or del_c when returning to this diagonal. That's why in the
+		 * case of movement towards diagonal, which contain last cell, value
+		 * should be increased by ins_c + del_c. In the case of movement
+		 * backwards this diagonal cell value should not be increased. Also
+		 * we store the bounds of cells inside row where was less or equal than
+		 * max_d in order to avoid filling of cells which are knowingly greater
+		 * than max_d.
+		 */
+		curr_left = 1;
+		d = min_d;
+		for (i = 0; i < delta; i++)
+		{
+			prev[i] = d;
+		}
+		curr_right = m;
+		for (; i < m; i++)
+		{
+			prev[i] = d;
+			d += (ins_c + del_c);
+			if (d > max_d)
+			{
+				curr_right = i;
+				break;
+			}
+		}
+		prev_x = s_data;
+	}
 
 	/* Loop through rows of the notional array */
 	for (y = t_data, j = 1; j < n; j++)
 	{
 		int		   *temp;
-		const char *x = s_data;
 		int			y_char_len = n != t_bytes + 1 ? pg_mblen(y) : 1;
 
 		/*
@@ -313,67 +389,175 @@ levenshtein_internal(text *s, text *t,
 		curr[0] = j * ins_c;
 
 		/*
-		 * This inner loop is critical to performance, so we include a
+		 * This inner loop is critical to performance, that's why we
+		 * handle case without max_d limitation separatetly. Also we include a
 		 * fast-path to handle the (fairly common) case where no multibyte
 		 * characters are in the mix.  The fast-path is entitled to assume
 		 * that if s_char_len is not initialized then BOTH strings contain
 		 * only single-byte characters.
 		 */
-		if (s_char_len != NULL)
+		if (max_d < 0)
 		{
-			for (i = 1; i < m; i++)
-			{
-				int			ins;
-				int			del;
-				int			sub;
-				int			x_char_len = s_char_len[i - 1];
+			const char *x = s_data;
+			/*
+			 * First cell must increment sequentially, as we're on the j'th row of
+			 * the (m+1)x(n+1) array.
+			 */
+			curr[0] = j * ins_c;
 
-				/*
-				 * Calculate costs for insertion, deletion, and substitution.
-				 *
-				 * When calculating cost for substitution, we compare the last
-				 * character of each possibly-multibyte character first,
-				 * because that's enough to rule out most mis-matches.  If we
-				 * get past that test, then we compare the lengths and the
-				 * remaining bytes.
-				 */
-				ins = prev[i] + ins_c;
-				del = curr[i - 1] + del_c;
-				if (x[x_char_len-1] == y[y_char_len-1]
-					&& x_char_len == y_char_len &&
-					(x_char_len == 1 || rest_of_char_same(x, y, x_char_len)))
-					sub = prev[i - 1];
-				else
-					sub = prev[i - 1] + sub_c;
+			if (s_char_len != NULL)
+			{
+				for (i = 1; i < m; i++)
+				{
+					int			ins;
+					int			del;
+					int			sub;
+					int			x_char_len = s_char_len[i - 1];
+
+					/*
+					 * Calculate costs for insertion, deletion, and substitution.
+					 *
+					 * When calculating cost for substitution, we compare the last
+					 * character of each possibly-multibyte character first,
+					 * because that's enough to rule out most mis-matches.  If we
+					 * get past that test, then we compare the lengths and the
+					 * remaining bytes.
+					 */
+					ins = prev[i] + ins_c;
+					del = curr[i - 1] + del_c;
+					if (x[x_char_len-1] == y[y_char_len-1]
+						&& x_char_len == y_char_len &&
+						(x_char_len == 1 || rest_of_char_same(x, y, x_char_len)))
+						sub = prev[i - 1];
+					else
+						sub = prev[i - 1] + sub_c;
 
-				/* Take the one with minimum cost. */
-				curr[i] = Min(ins, del);
-				curr[i] = Min(curr[i], sub);
+					/* Take the one with minimum cost. */
+					curr[i] = Min(ins, del);
+					curr[i] = Min(curr[i], sub);
 
-				/* Point to next character. */
-				x += x_char_len;
+					/* Point to next character. */
+					x += x_char_len;
+				}
 			}
-		}
-		else
-		{
-			for (i = 1; i < m; i++)
+			else
 			{
-				int			ins;
-				int			del;
-				int			sub;
+				for (i = 1; i < m; i++)
+				{
+					int			ins;
+					int			del;
+					int			sub;
 
-				/* Calculate costs for insertion, deletion, and substitution. */
-				ins = prev[i] + ins_c;
-				del = curr[i - 1] + del_c;
-				sub = prev[i - 1] + ((*x == *y) ? 0 : sub_c);
+					/* Calculate costs for insertion, deletion, and substitution. */
+					ins = prev[i] + ins_c;
+					del = curr[i - 1] + del_c;
+					sub = prev[i - 1] + ((*x == *y) ? 0 : sub_c);
 
-				/* Take the one with minimum cost. */
-				curr[i] = Min(ins, del);
-				curr[i] = Min(curr[i], sub);
+					/* Take the one with minimum cost. */
+					curr[i] = Min(ins, del);
+					curr[i] = Min(curr[i], sub);
 
-				/* Point to next character. */
-				x++;
+					/* Point to next character. */
+					x++;
+				}
 			}
+		}else{
+			const char *x = prev_x;
+
+			/*
+			 * Memorize the bounds of previos row where values was less or
+			 * equal than max_d.
+			 */
+			prev_left = curr_left;
+			prev_right = curr_right;
+			curr_left = -1;
+
+			/*
+			 * Fill the first cell of the row taking care about it's position
+			 * relatively last cell's diagnal.
+			 */
+			if (delta >= 0)
+				curr[0] = min_d + j * (ins_c + del_c);
+			else
+			{
+				if (j <= - delta)
+					curr[0] = min_d;
+				else
+					curr[0] = min_d + (j + delta) * (ins_c + del_c);
+			}
+			if (curr[0] <= max_d) curr_left = 1;
+
+			if (s_char_len != NULL)
+			{
+				for (i = prev_left; i < m && i < prev_right + 2; i++)
+				{
+					int	x_char_len = s_char_len[i - 1];
+					d = max_d + 1;
+					/*
+					 * Take minimum costs for insertion, deletion, and
+					 * substitution when corresponding previous cell doesn't
+					 * exceed bounds where value was less or equal than max_d.
+					 */
+					if (i <= prev_right)
+						d = Min(prev[i] + ((j + delta > i) ? (ins_c + del_c):0), d);
+					if (i == 1 || i > prev_left)
+					{
+						d = Min(curr[i - 1] +
+							((i - delta > j) ? (ins_c + del_c) : 0), d);
+						d = Min(prev[i - 1] + ((x[x_char_len-1] == y[y_char_len-1]
+							&& x_char_len == y_char_len
+							&& (x_char_len == 1 || rest_of_char_same(x, y, x_char_len)))
+							? 0 : sub_c), d);
+					}
+					curr[i] = d;
+					if (d <= max_d)
+					{
+						if (curr_left == -1)
+						{
+							curr_left = i;
+							/*
+							 * Save previos position in the string x in order
+							 * to avoid pg_mblen calls.
+							 */
+							prev_x = x;
+						}
+						curr_right = i;
+					}
+					x += x_char_len;
+				}
+			}
+			else
+			{
+				for (i = prev_left; i < m && i < prev_right + 2; i++)
+				{
+					/*
+					 * Take minimum costs for insertion, deletion, and
+					 * substitution when corresponding previous cell doesn't
+					 * exceed bounds where value was less or equal than max_d.
+					 */
+					d = max_d + 1;
+					if (i <= prev_right)
+						d = Min(prev[i] + ((j + delta > i)?(ins_c + del_c):0), d);
+					if (i == 1 || i > prev_left)
+					{
+						d = Min(curr[i - 1] + ((i - delta > j)?(ins_c + del_c):0), d);
+						d = Min(prev[i - 1] + (*x == *y ? 0 : sub_c), d);
+					}
+					curr[i] = d;
+					if (d <= max_d)
+					{
+						if (curr_left == -1)
+						{
+							curr_left = i;
+							prev_x = x;
+						}
+						curr_right = i;
+					}
+					x++;
+				}
+			}
+			if (curr_left == -1)
+				break;
 		}
 
 		/* Swap current row with previous row. */
@@ -386,6 +570,13 @@ levenshtein_internal(text *s, text *t,
 	}
 
 	/*
+	 * If we have limitation of max_d and haven't less or equal, than max_d
+	 * value in the last row than we should return max_d + 1.
+	 */
+	if (max_d >= 0 && (curr_left == -1 || curr_right < m - 1))
+		return max_d + 1;
+
+	/*
 	 * Because the final value was swapped from the previous row to the
 	 * current row, that's where we'll find it.
 	 */
@@ -403,7 +594,7 @@ levenshtein_with_costs(PG_FUNCTION_ARGS)
 	int			del_c = PG_GETARG_INT32(3);
 	int			sub_c = PG_GETARG_INT32(4);
 
-	PG_RETURN_INT32(levenshtein_internal(src, dst, ins_c, del_c, sub_c));
+	PG_RETURN_INT32(levenshtein_internal(src, dst, ins_c, del_c, sub_c, -1));
 }
 
 
@@ -414,7 +605,34 @@ levenshtein(PG_FUNCTION_ARGS)
 	text	   *src = PG_GETARG_TEXT_PP(0);
 	text	   *dst = PG_GETARG_TEXT_PP(1);
 
-	PG_RETURN_INT32(levenshtein_internal(src, dst, 1, 1, 1));
+	PG_RETURN_INT32(levenshtein_internal(src, dst, 1, 1, 1, -1));
+}
+
+
+PG_FUNCTION_INFO_V1(levenshtein_less_equal_with_costs);
+Datum
+levenshtein_less_equal_with_costs(PG_FUNCTION_ARGS)
+{
+	text	   *src = PG_GETARG_TEXT_PP(0);
+	text	   *dst = PG_GETARG_TEXT_PP(1);
+	int			ins_c = PG_GETARG_INT32(2);
+	int			del_c = PG_GETARG_INT32(3);
+	int			sub_c = PG_GETARG_INT32(4);
+	int			max_d = PG_GETARG_INT32(5);
+
+	PG_RETURN_INT32(levenshtein_internal(src, dst, ins_c, del_c, sub_c, max_d));
+}
+
+
+PG_FUNCTION_INFO_V1(levenshtein_less_equal);
+Datum
+levenshtein_less_equal(PG_FUNCTION_ARGS)
+{
+	text	   *src = PG_GETARG_TEXT_PP(0);
+	text	   *dst = PG_GETARG_TEXT_PP(1);
+	int			max_d = PG_GETARG_INT32(2);
+
+	PG_RETURN_INT32(levenshtein_internal(src, dst, 1, 1, 1, max_d));
 }
 
 
diff --git a/contrib/fuzzystrmatch/fuzzystrmatch.sql.in b/contrib/fuzzystrmatch/fuzzystrmatch.sql.in
index 05a347d..0e75491 100644
--- a/contrib/fuzzystrmatch/fuzzystrmatch.sql.in
+++ b/contrib/fuzzystrmatch/fuzzystrmatch.sql.in
@@ -11,6 +11,14 @@ CREATE OR REPLACE FUNCTION levenshtein (text,text,int,int,int) RETURNS int
 AS 'MODULE_PATHNAME','levenshtein_with_costs'
 LANGUAGE C IMMUTABLE STRICT;
 
+CREATE OR REPLACE FUNCTION levenshtein_less_equal (text,text,int) RETURNS int
+AS 'MODULE_PATHNAME','levenshtein_less_equal'
+LANGUAGE C IMMUTABLE STRICT;
+
+CREATE OR REPLACE FUNCTION levenshtein_less_equal (text,text,int,int,int,int) RETURNS int
+AS 'MODULE_PATHNAME','levenshtein_less_equal_with_costs'
+LANGUAGE C IMMUTABLE STRICT;
+
 CREATE OR REPLACE FUNCTION metaphone (text,int) RETURNS text
 AS 'MODULE_PATHNAME','metaphone'
 LANGUAGE C IMMUTABLE STRICT;
diff --git a/doc/src/sgml/fuzzystrmatch.sgml b/doc/src/sgml/fuzzystrmatch.sgml
index 69777e4..83a39d4 100644
--- a/doc/src/sgml/fuzzystrmatch.sgml
+++ b/doc/src/sgml/fuzzystrmatch.sgml
@@ -84,6 +84,8 @@ SELECT * FROM s WHERE difference(s.nm, 'john') &gt; 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>