xref: /PHP-8.2/ext/standard/levenshtein.c (revision 01b3fc03)
1 /*
2    +----------------------------------------------------------------------+
3    | Copyright (c) The PHP Group                                          |
4    +----------------------------------------------------------------------+
5    | This source file is subject to version 3.01 of the PHP license,      |
6    | that is bundled with this package in the file LICENSE, and is        |
7    | available through the world-wide-web at the following url:           |
8    | https://www.php.net/license/3_01.txt                                 |
9    | If you did not receive a copy of the PHP license and are unable to   |
10    | obtain it through the world-wide-web, please send a note to          |
11    | license@php.net so we can mail you a copy immediately.               |
12    +----------------------------------------------------------------------+
13    | Author: Hartmut Holzgraefe <hholzgra@php.net>                        |
14    +----------------------------------------------------------------------+
15  */
16 
17 #include "php.h"
18 #include "php_string.h"
19 
20 /* {{{ reference_levdist
21  * reference implementation, only optimized for memory usage, not speed */
reference_levdist(const zend_string * string1,const zend_string * string2,zend_long cost_ins,zend_long cost_rep,zend_long cost_del)22 static zend_long reference_levdist(const zend_string *string1, const zend_string *string2, zend_long cost_ins, zend_long cost_rep, zend_long cost_del )
23 {
24 	zend_long *p1, *p2, *tmp;
25 	zend_long c0, c1, c2;
26 	size_t i1, i2;
27 
28 	if (ZSTR_LEN(string1) == 0) {
29 		return ZSTR_LEN(string2) * cost_ins;
30 	}
31 	if (ZSTR_LEN(string2) == 0) {
32 		return ZSTR_LEN(string1) * cost_del;
33 	}
34 
35 	p1 = safe_emalloc((ZSTR_LEN(string2) + 1), sizeof(zend_long), 0);
36 	p2 = safe_emalloc((ZSTR_LEN(string2) + 1), sizeof(zend_long), 0);
37 
38 	for (i2 = 0; i2 <= ZSTR_LEN(string2); i2++) {
39 		p1[i2] = i2 * cost_ins;
40 	}
41 	for (i1 = 0; i1 < ZSTR_LEN(string1) ; i1++) {
42 		p2[0] = p1[0] + cost_del;
43 
44 		for (i2 = 0; i2 < ZSTR_LEN(string2); i2++) {
45 			c0 = p1[i2] + ((ZSTR_VAL(string1)[i1] == ZSTR_VAL(string2)[i2]) ? 0 : cost_rep);
46 			c1 = p1[i2 + 1] + cost_del;
47 			if (c1 < c0) {
48 				c0 = c1;
49 			}
50 			c2 = p2[i2] + cost_ins;
51 			if (c2 < c0) {
52 				c0 = c2;
53 			}
54 			p2[i2 + 1] = c0;
55 		}
56 		tmp = p1;
57 		p1 = p2;
58 		p2 = tmp;
59 	}
60 	c0 = p1[ZSTR_LEN(string2)];
61 
62 	efree(p1);
63 	efree(p2);
64 
65 	return c0;
66 }
67 /* }}} */
68 
69 /* {{{ Calculate Levenshtein distance between two strings */
PHP_FUNCTION(levenshtein)70 PHP_FUNCTION(levenshtein)
71 {
72 	zend_string *string1, *string2;
73 	zend_long cost_ins = 1;
74 	zend_long cost_rep = 1;
75 	zend_long cost_del = 1;
76 
77 	if (zend_parse_parameters(ZEND_NUM_ARGS(), "SS|lll", &string1, &string2, &cost_ins, &cost_rep, &cost_del) == FAILURE) {
78 		RETURN_THROWS();
79 	}
80 
81 
82 	RETURN_LONG(reference_levdist(string1, string2, cost_ins, cost_rep, cost_del));
83 }
84 /* }}} */
85