cvs: php3 / Makefile.in /functions/ basic_functions.c levenshtein.c php3_string.h

hholzgra Tue May 23 21:34:48 2000 EDT Added files: /php3/functions levenshtein.c Modified files: /php3 Makefile.in /php3/functions php3_string.h basic_functions.c Log: new function levenshtein(), same as in PHP4 Index: php3/Makefile.in diff -u php3/Makefile.in:1.360 php3/Makefile.in:1.361 --- php3/Makefile.in:1.360 Thu Mar 30 06:14:21 2000 +++ php3/Makefile.in Tue May 23 21:34:47 2000 @@ -24,7 +24,7 @@ # +----------------------------------------------------------------------+ # -# $Id: Makefile.in,v 1.360 2000/03/30 04:14:21 sas Exp $ +# $Id: Makefile.in,v 1.361 2000/05/23 19:34:47 hholzgra Exp $ # prefix = @prefix@ @@ -99,7 +99,7 @@ functions/dba_dbm.c functions/dba_ndbm.c functions/dba_cdb.c \ functions/mcrypt.c functions/dba_db2.c functions/mhash.c \ functions/pcre.c functions/posix.c functions/parsedate.c \ - functions/lcg.c functions/recode.c + functions/lcg.c functions/recode.c functions/levenshtein.c FUNCTIONS = $(FUNCTIONS_SOURCE:.c=.o) Index: php3/functions/php3_string.h diff -u php3/functions/php3_string.h:1.47 php3/functions/php3_string.h:1.48 --- php3/functions/php3_string.h:1.47 Sat Jan 1 05:44:09 2000 +++ php3/functions/php3_string.h Tue May 23 21:34:47 2000 @@ -29,7 +29,7 @@ */ -/* $Id: php3_string.h,v 1.47 2000/01/01 04:44:09 sas Exp $ */ +/* $Id: php3_string.h,v 1.48 2000/05/23 19:34:47 hholzgra Exp $ */ #ifndef _PHPSTRING_H #define _PHPSTRING_H @@ -49,6 +49,7 @@ extern void php3_ltrim(INTERNAL_FUNCTION_PARAMETERS); extern void php3_similar_text(INTERNAL_FUNCTION_PARAMETERS); extern void soundex(INTERNAL_FUNCTION_PARAMETERS); +extern void php3_levenshtein(INTERNAL_FUNCTION_PARAMETERS); extern void php3_explode(INTERNAL_FUNCTION_PARAMETERS); extern void php3_implode(INTERNAL_FUNCTION_PARAMETERS); Index: php3/functions/basic_functions.c diff -u php3/functions/basic_functions.c:1.287 php3/functions/basic_functions.c:1.288 --- php3/functions/basic_functions.c:1.287 Mon Apr 10 21:29:37 2000 +++ php3/functions/basic_functions.c Tue May 23 21:34:47 2000 @@ -28,7 +28,7 @@ +----------------------------------------------------------------------+ */ -/* $Id: basic_functions.c,v 1.287 2000/04/10 19:29:37 andi Exp $ */ +/* $Id: basic_functions.c,v 1.288 2000/05/23 19:34:47 hholzgra Exp $ */ #include "php.h" #include "modules.h" #include "internal_functions.h" @@ -226,6 +226,7 @@ {"passthru", php3_passthru, second_arg_force_ref}, {"soundex", soundex, NULL}, + {"levenshtein", php3_levenshtein, NULL}, {"rand", php3_rand, NULL}, {"srand", php3_srand, NULL}, Index: php3/functions/levenshtein.c +++ php3/functions/levenshtein.c /* +----------------------------------------------------------------------+ | Php HTML Embedded Scripting Language Version 3.0 | +----------------------------------------------------------------------+ | Copyright (c) 1997-2000 PHP Development Team (See Credits file) | +----------------------------------------------------------------------+ | This program is free software; you can redistribute it and/or modify | | it under the terms of one of the following licenses: | | | | A) the GNU General Public License as published by the Free Software | | Foundation; either version 2 of the License, or (at your option) | | any later version. | | | | B) the PHP License as published by the PHP Development Team and | | included in the distribution in the file: LICENSE | | | | This program is distributed in the hope that it will be useful, | | but WITHOUT ANY WARRANTY; without even the implied warranty of | | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | | GNU General Public License for more details. | | | | You should have received a copy of both licenses referred to here. | | If you did not, or have any questions about PHP licensing, please | | contact core@php.net. | +----------------------------------------------------------------------+ | Authors: Rasmus Lerdorf <rasmus@lerdorf.on.ca> | | Stig Sæther Bakken <ssb@fast.no> | | Zeev Suraski <bourbon@nevision.net.il> | +----------------------------------------------------------------------+ */ /* $Id: levenshtein.c,v 1.1 2000/05/23 19:34:47 hholzgra Exp $ */ #include <stdio.h> #include "php.h" #include "internal_functions.h" #include "reg.h" #include "post.h" #include "php3_string.h" int calc_levdist(const char *s1, const char *s2) /* faster, but obfuscated */ { register char *p1,*p2; register int i,j,n; int l1=0,l2=0; char r[512]; /* 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) { (long)s1 ^= (long)s2; (long)s2 ^= (long)s1; (long)s1 ^= (long)s2; l1 ^= l2; l2 ^= l1; l1 ^= l2; } /* fill initial row */ n=(*s1!=*s2); 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 insert ? */ *p2++=n++; /* update field and cost for next col's delete */ p2++; } } /* return result */ return n-1; } /* {{{ proto int levenshtein(string str1, string str2) Calculate Levenshtein distance between two strings */ void php3_levenshtein(INTERNAL_FUNCTION_PARAMETERS) { pval *str1, *str2; int l; if (ARG_COUNT(ht) != 2 || getParameters(ht, 2, &str1, &str2) == FAILURE) { WRONG_PARAM_COUNT; } convert_to_string(str1); convert_to_string(str2); l = calc_levdist(str1->value.str.val, str2->value.str.val); if(l<0) { php3_error(E_WARNING,"levenshtein(): argument string(s) too long"); } RETURN_LONG(l); } /* }}} */