levenshtein() fixes and regression test

1 files changed, 99 insertions, 211 deletions

diff --git a/ext/standard/levenshtein.c b/ext/standard/levenshtein.c
index d157cf7fab..6887946da2 100644
--- a/ext/standard/levenshtein.c
+++ b/ext/standard/levenshtein.c
@@ -23,168 +23,53 @@
 #include <ctype.h>
 #include "php_string.h"
 
-/* faster, but obfuscated, all operations have a cost of 1 */
-static int fastest_levdist(const char *s1, const char *s2) 
+/* reference implementation, only optimized for memory usage, not speed */
+static int reference_levdist(const char *s1, int l1, 
+                             const char *s2, int l2, 
+                             int cost_ins, int cost_rep, int cost_del )
 {
-	register char *p1,*p2; 
-	register int i,j,n;
-	int l1=0,l2=0;
-	char r[512];
-	const char *tmp;
-
-	/* skip equal start sequence, if any */
-	while(*s1==*s2) {
-		if(!*s1) break;
-		s1++; s2++;
-	}
-	
-	/* if we already used up one string, then
-      the result is the length of the other */
-	if(*s1=='\0') return strlen(s2);
-	if(*s2=='\0') return strlen(s1);
-
-	/* length count */
-	while(*s1++) l1++;
-	while(*s2++) l2++;
-	
-	/* cut of equal tail sequence, if any */
-	while(*--s1 == *--s2) {
-		l1--; l2--;		
-	}
-	
-
-	/* reset pointers, adjust length */
-	s1-=l1++;
-	s2-=l2++;
-	
-
-	/* possible dist to great? */
- 	if(abs(l1-l2)>=255) return -1;
-
-	/* swap if l2 longer than l1 */
-	if(l1<l2) {
-		tmp=s1; s1=s2; s2=tmp;
-		l1 ^= l2; l2 ^= l1; l1 ^= l2;
-	}
-
-	
-	/* fill initial row */
-	n=1;
-	for(i=0,p1=r;i<l1;i++,*p1++=n++,p1++) {/*empty*/}
-	
-	/* calc. rowwise */
-	for(j=1;j<l2;j++) {
-		/* init pointers and col#0 */
-		p1 = r + !(j&1);
-		p2 = r + (j&1);
-		n=*p1+1;
-		*p2++=n;p2++;
-		s2++;
-		
-		/* foreach column */
-		for(i=1;i<l1;i++) {
-			if(*p1<n) n=*p1+(*(s1+i)!=*(s2)); /* replace cheaper than delete? */
-			p1++;
-			if(*++p1<n) n=*p1+1; /* insert cheaper then replace ? */
-			*p2++=n++; /* update field and cost for next col's delete */
-			p2++;
-		}	
-	}
-
-	/* return result */
-	return n-1;
+  int *p1,*p2,*tmp;
+  int i1,i2,c0,c1,c2;
+  
+  if(l1==0) return l2*cost_ins;
+  if(l2==0) return l1*cost_del;
+
+  p1=malloc(l2*sizeof(int));
+  p2=malloc(l2*sizeof(int));
+
+  p1[0]=(s1[0]==s2[0])?0:cost_rep;
+
+  for(i2=1;i2<l2;i2++)
+    p1[i2]=i2*cost_ins;
+
+  for(i1=1;i1<l1;i1++)
+    {
+      p2[0]=i1*cost_del;
+      for(i2=1;i2<l2;i2++)
+        {
+          c0=p1[i2-1]+((s1[i1]==s2[i2])?0:cost_rep);
+          c1=p1[i2]+cost_del; if(c1<c0) c0=c1;
+          c2=p2[i2-1]+cost_ins; if(c2<c0) c0=c2;        
+          p2[i2]=c0;
+        }
+      tmp=p1; p1=p2; p2=tmp;
+    }
+
+  c0=p1[l2-1];
+
+  free(p1);
+  free(p2);
+
+  return c0;
 }
 
 
-static int weighted_levdist( const char *s1
-														 , const char *s2
-														 , const int cost_ins
-														 , const int cost_rep
-														 , const int cost_del
-														 ) 
-{
-	register int *p1,*p2; 
-	register int i,j,n,c;
-	int l1=0,l2=0;
-	int r[512];
-	const char *tmp;
-
-	/* skip equal start sequence, if any */
-	while(*s1==*s2) {
-		if(!*s1) break;
-		s1++; s2++;
-	}
-	
-	/* if we already used up one string, then
-      the result is the length of the other */
-	if(*s1=='\0') return strlen(s2);
-	if(*s2=='\0') return strlen(s1);
-
-	/* length count */
-	while(*s1++) l1++;
-	while(*s2++) l2++;
-	
-	/* cut of equal tail sequence, if any */
-	while(*--s1 == *--s2) {
-		l1--; l2--;		
-	}
-	
-
-	/* reset pointers, adjust length */
-	s1-=l1++;
-	s2-=l2++;
-	
-
-	/* possible dist to great? */
- 	if(abs(l1-l2)>=255) return -1;
-
-	/* swap if l2 longer than l1 */
-	if(l1<l2) {
-		tmp=s1; s1=s2; s2=tmp;
-		l1 ^= l2; l2 ^= l1; l1 ^= l2;
-	}
-
-	if((l1==1)&&(l2==1)) {
-		n= cost_del+cost_ins;
-		return n<cost_rep?n:cost_rep;
-	}
-
-	/* fill initial row */
-	n=cost_ins;
-	for(i=0,p1=r;i<l1;i++,*p1++=n,p1++) {n+=cost_ins;}
-	
-	/* calc. rowwise */
-	for(j=1;j<l2;j++) {
-		/* init pointers and col#0 */
-		p1 = r + !(j&1);
-		p2 = r + (j&1);
-		n=*p1+cost_del;
-		*p2++=n;p2++;
-		s2++;
-		
-		/* foreach column */
-		for(i=1;i<l1;i++) {
-			c = *p1; if(*(s1+i)!=*(s2)) c+=cost_rep;
-			if(c<n) n=c; /* replace cheaper than delete? */
-			p1++;
-			c= *++p1+cost_ins;
-			if(c<n) n=c; /* insert cheaper then replace ? */
-			*p2++=n; /* update field and cost for next col's delete */
-			n+=cost_del; /* update field and cost for next col's delete */
-			p2++;
-		}	
-	}
-
-	/* return result */
-	return n-=cost_del;
-}
-
 static int custom_levdist(char *str1,char *str2,char *callback_name) 
 {
-		php_error(E_WARNING,"the general Levenshtein support is not there yet");
-		/* not there yet */
+    php_error(E_WARNING,"the general Levenshtein support is not there yet");
+    /* not there yet */
 
-		return -1;
+    return -1;
 }
 
 
@@ -192,61 +77,64 @@ static int custom_levdist(char *str1,char *str2,char *callback_name)
    Calculate Levenshtein distance between two strings */
 PHP_FUNCTION(levenshtein)
 {
-	zval **str1, **str2, **cost_ins, **cost_rep, **cost_del,**callback_name;
-	int distance=-1;
-
-	switch(ZEND_NUM_ARGS()) {
-	case 2: /* just two string: use maximum performance version  */
-		if (zend_get_parameters_ex(2, &str1, &str2) == FAILURE) {
-			WRONG_PARAM_COUNT;
-		}
-		convert_to_string_ex(str1);
-		convert_to_string_ex(str2);
-		
-		distance = fastest_levdist((*str1)->value.str.val, (*str2)->value.str.val);
-		break;
-
-	case 5: /* more general version: calc cost by ins/rep/del weights */
-		if (zend_get_parameters_ex(5, &str1, &str2, &cost_ins, &cost_rep, &cost_del) == FAILURE) {
-			WRONG_PARAM_COUNT;
-		}
-		convert_to_string_ex(str1);
-		convert_to_string_ex(str2);
-		convert_to_long_ex(cost_ins);
-		convert_to_long_ex(cost_rep);
-		convert_to_long_ex(cost_del);
-		
-		distance = weighted_levdist((*str1)->value.str.val
-																, (*str2)->value.str.val
-																, (*cost_ins)->value.lval
-																, (*cost_rep)->value.lval
-																, (*cost_del)->value.lval
-																);
-		
-		break;
-
-	case 3: /* most general version: calc cost by user-supplied function */
-		if (zend_get_parameters_ex(3, &str1, &str2, &callback_name) == FAILURE) {
-			WRONG_PARAM_COUNT;
-		}
-		convert_to_string_ex(str1);
-		convert_to_string_ex(str2);
-		convert_to_string_ex(callback_name);
-
-		distance = custom_levdist((*str1)->value.str.val
-																, (*str2)->value.str.val
-																, (*callback_name)->value.str.val
-																);
-		break;
-
-	default: 
-		WRONG_PARAM_COUNT;
-	}	
-
-	if(distance<0) {
-		php_error(E_WARNING,"levenshtein(): argument string(s) too long");
-	}
-	
-	RETURN_LONG(distance);
+  zval **str1, **str2, **cost_ins, **cost_rep, **cost_del,**callback_name;
+  int distance=-1;
+
+  switch(ZEND_NUM_ARGS()) {
+  case 2: /* just two string: use maximum performance version  */
+    if (zend_get_parameters_ex(2, &str1, &str2) == FAILURE) {
+      WRONG_PARAM_COUNT;
+    }
+    convert_to_string_ex(str1);
+    convert_to_string_ex(str2);
+
+    distance = reference_levdist((*str1)->value.str.val,(*str1)->value.str.len, 
+                                 (*str2)->value.str.val,(*str2)->value.str.len,
+                                 1,1,1);
+
+    break;
+
+  case 5: /* more general version: calc cost by ins/rep/del weights */
+    if (zend_get_parameters_ex(5, &str1, &str2, &cost_ins, &cost_rep, &cost_del) == FAILURE) {
+      WRONG_PARAM_COUNT;
+    }
+    convert_to_string_ex(str1);
+    convert_to_string_ex(str2);
+    convert_to_long_ex(cost_ins);
+    convert_to_long_ex(cost_rep);
+    convert_to_long_ex(cost_del);
+    
+    distance = reference_levdist((*str1)->value.str.val,(*str1)->value.str.len, 
+                                 (*str2)->value.str.val,(*str2)->value.str.len,
+                                 (*cost_ins)->value.lval,
+                                 (*cost_rep)->value.lval,
+                                 (*cost_del)->value.lval
+                                );
+    
+    break;
+
+  case 3: /* most general version: calc cost by user-supplied function */
+    if (zend_get_parameters_ex(3, &str1, &str2, &callback_name) == FAILURE) {
+      WRONG_PARAM_COUNT;
+    }
+    convert_to_string_ex(str1);
+    convert_to_string_ex(str2);
+    convert_to_string_ex(callback_name);
+
+    distance = custom_levdist((*str1)->value.str.val
+                                , (*str2)->value.str.val
+                                , (*callback_name)->value.str.val
+                                );
+    break;
+
+  default: 
+    WRONG_PARAM_COUNT;
+  }  
+
+  if(distance<0) {
+    php_error(E_WARNING,"levenshtein(): argument string(s) too long");
+  }
+  
+  RETURN_LONG(distance);
 }
 /* }}} */