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 /* When all costs are equal, levenshtein fulfills the requirements of a metric, which means
36 * that the distance is symmetric. If string1 is shorter than string 2 we can save memory (and CPU time)
37 * by having shorter rows (p1 & p2). */
38 if (ZSTR_LEN(string1) < ZSTR_LEN(string2) && cost_ins == cost_rep && cost_rep == cost_del) {
39 const zend_string *tmp = string1;
40 string1 = string2;
41 string2 = tmp;
42 }
43
44 p1 = safe_emalloc((ZSTR_LEN(string2) + 1), sizeof(zend_long), 0);
45 p2 = safe_emalloc((ZSTR_LEN(string2) + 1), sizeof(zend_long), 0);
46
47 for (i2 = 0; i2 <= ZSTR_LEN(string2); i2++) {
48 p1[i2] = i2 * cost_ins;
49 }
50 for (i1 = 0; i1 < ZSTR_LEN(string1) ; i1++) {
51 p2[0] = p1[0] + cost_del;
52
53 for (i2 = 0; i2 < ZSTR_LEN(string2); i2++) {
54 c0 = p1[i2] + ((ZSTR_VAL(string1)[i1] == ZSTR_VAL(string2)[i2]) ? 0 : cost_rep);
55 c1 = p1[i2 + 1] + cost_del;
56 if (c1 < c0) {
57 c0 = c1;
58 }
59 c2 = p2[i2] + cost_ins;
60 if (c2 < c0) {
61 c0 = c2;
62 }
63 p2[i2 + 1] = c0;
64 }
65 tmp = p1;
66 p1 = p2;
67 p2 = tmp;
68 }
69 c0 = p1[ZSTR_LEN(string2)];
70
71 efree(p1);
72 efree(p2);
73
74 return c0;
75 }
76 /* }}} */
77
78 /* {{{ Calculate Levenshtein distance between two strings */
PHP_FUNCTION(levenshtein)79 PHP_FUNCTION(levenshtein)
80 {
81 zend_string *string1, *string2;
82 zend_long cost_ins = 1;
83 zend_long cost_rep = 1;
84 zend_long cost_del = 1;
85
86 if (zend_parse_parameters(ZEND_NUM_ARGS(), "SS|lll", &string1, &string2, &cost_ins, &cost_rep, &cost_del) == FAILURE) {
87 RETURN_THROWS();
88 }
89
90
91 RETURN_LONG(reference_levdist(string1, string2, cost_ins, cost_rep, cost_del));
92 }
93 /* }}} */
94
