1 : /*
2 : +----------------------------------------------------------------------+
3 : | PHP Version 6 |
4 : +----------------------------------------------------------------------+
5 : | Copyright (c) 1997-2009 The PHP Group |
6 : +----------------------------------------------------------------------+
7 : | This source file is subject to version 3.01 of the PHP license, |
8 : | that is bundled with this package in the file LICENSE, and is |
9 : | available through the world-wide-web at the following url: |
10 : | http://www.php.net/license/3_01.txt |
11 : | If you did not receive a copy of the PHP license and are unable to |
12 : | obtain it through the world-wide-web, please send a note to |
13 : | license@php.net so we can mail you a copy immediately. |
14 : +----------------------------------------------------------------------+
15 : | Author: Hartmut Holzgraefe <hholzgra@php.net> |
16 : +----------------------------------------------------------------------+
17 : */
18 : /* $Id: levenshtein.c 276986 2009-03-10 23:40:06Z helly $ */
19 :
20 : #include "php.h"
21 : #include <stdlib.h>
22 : #include <errno.h>
23 : #include <ctype.h>
24 : #include "php_string.h"
25 :
26 : #define LEVENSHTEIN_MAX_LENGTH 255
27 :
28 : /* {{{ reference_levdist
29 : * reference implementation, only optimized for memory usage, not speed */
30 : static int reference_levdist(void *s1, int l1, void *s2, int l2, zend_uchar str_type, int cost_ins, int cost_rep, int cost_del )
31 50 : {
32 : int *p1, *p2, *tmp;
33 : int32_t i1, i2, j1, j2, cp1, cp2;
34 : int32_t c0, c1, c2;
35 : UChar32 ch1, ch2;
36 :
37 50 : if (str_type == IS_UNICODE) {
38 50 : cp1 = u_countChar32((UChar *)s1, l1);
39 50 : cp2 = u_countChar32((UChar *)s2, l2);
40 :
41 50 : if (cp1 == 0) {
42 6 : return cp2 * cost_ins;
43 : }
44 44 : if (cp2 == 0) {
45 2 : return cp1 * cost_del;
46 : }
47 42 : if ((cp1 > LEVENSHTEIN_MAX_LENGTH) || (cp2 > LEVENSHTEIN_MAX_LENGTH)) {
48 2 : return -1;
49 : }
50 :
51 40 : p1 = safe_emalloc((cp2 + 1), sizeof(int), 0);
52 40 : p2 = safe_emalloc((cp2 + 1), sizeof(int), 0);
53 : } else {
54 0 : if (l1 == 0) {
55 0 : return l2 * cost_ins;
56 : }
57 0 : if (l2 == 0) {
58 0 : return l1 * cost_del;
59 : }
60 0 : if ((l1 > LEVENSHTEIN_MAX_LENGTH) || (l2 > LEVENSHTEIN_MAX_LENGTH)) {
61 0 : return -1;
62 : }
63 :
64 0 : p1 = safe_emalloc((l2 + 1), sizeof(int), 0);
65 0 : p2 = safe_emalloc((l2 + 1), sizeof(int), 0);
66 : }
67 :
68 476 : for (i2 = 0; i2 <= l2; i2++) {
69 436 : p1[i2] = i2 * cost_ins;
70 : }
71 438 : for (i1 = 0, j1 = 0; i1 < l1; i1++) {
72 398 : p2[0] = p1[0] + cost_del;
73 398 : if (str_type == IS_UNICODE) {
74 398 : U16_NEXT((UChar *)s1, j1, l1, ch1);
75 : }
76 1536 : for (i2 = 0, j2 = 0; i2 < l2; i2++) {
77 1138 : if (str_type == IS_UNICODE) {
78 1138 : U16_NEXT((UChar *)s2, j2, l2, ch2);
79 1138 : c0 = p1[i2] + ((ch1 == ch2) ? 0 : cost_rep);
80 : } else {
81 0 : c0 = p1[i2] + ((*((char *)s1 + i1) == *((char *)s2 + i2)) ? 0 : cost_rep);
82 : }
83 1138 : c1 = p1[i2 + 1] + cost_del;
84 1138 : if (c1 < c0) {
85 439 : c0 = c1;
86 : }
87 1138 : c2 = p2[i2] + cost_ins;
88 1138 : if (c2 < c0) {
89 405 : c0 = c2;
90 : }
91 1138 : p2[i2 + 1] = c0;
92 : }
93 398 : tmp = p1;
94 398 : p1 = p2;
95 398 : p2 = tmp;
96 : }
97 40 : c0 = p1[l2];
98 :
99 40 : efree(p1);
100 40 : efree(p2);
101 :
102 40 : return c0;
103 : }
104 : /* }}} */
105 :
106 : /* {{{ custom_levdist
107 : */
108 : static int custom_levdist(void *str1, void *str2, char *callback_name TSRMLS_DC)
109 1 : {
110 1 : php_error_docref(NULL TSRMLS_CC, E_WARNING, "The general Levenshtein support is not there yet");
111 : /* not there yet */
112 :
113 1 : return -1;
114 : }
115 : /* }}} */
116 :
117 : /* {{{ proto int levenshtein(string str1, string str2[, int cost_ins, int cost_rep, int cost_del]) U
118 : Calculate Levenshtein distance between two strings */
119 : PHP_FUNCTION(levenshtein)
120 53 : {
121 53 : int argc = ZEND_NUM_ARGS();
122 : void *str1, *str2;
123 : char *callback_name;
124 : int str1_len, str2_len, callback_len;
125 : zend_uchar str1_type, str2_type;
126 : long cost_ins, cost_rep, cost_del;
127 53 : int distance = -1;
128 :
129 53 : switch (argc) {
130 : case 2: /* just two strings: use maximum performance version */
131 37 : if (zend_parse_parameters(2 TSRMLS_CC, "TT", &str1, &str1_len, &str1_type, &str2, &str2_len, &str2_type) == FAILURE) {
132 1 : return;
133 : }
134 36 : distance = reference_levdist(str1, str1_len, str2, str2_len, str1_type, 1, 1, 1);
135 36 : break;
136 :
137 : case 5: /* more general version: calc cost by ins/rep/del weights */
138 14 : if (zend_parse_parameters(5 TSRMLS_CC, "TTlll", &str1, &str1_len, &str1_type, &str2, &str2_len, &str2_type, &cost_ins, &cost_rep, &cost_del) == FAILURE) {
139 0 : return;
140 : }
141 14 : distance = reference_levdist(str1, str1_len, str2, str2_len, str1_type, cost_ins, cost_rep, cost_del);
142 14 : break;
143 :
144 : case 3: /* most general version: calc cost by user-supplied function */
145 1 : if (zend_parse_parameters(3 TSRMLS_CC, "TTs", &str1, &str1_len, &str1_type, &str2, &str2_len, &str2_type, &callback_name, &callback_len) == FAILURE) {
146 0 : return;
147 : }
148 1 : distance = custom_levdist(str1, str2, callback_name TSRMLS_CC);
149 1 : break;
150 :
151 : default:
152 1 : WRONG_PARAM_COUNT;
153 : }
154 :
155 51 : if (distance < 0 && /* TODO */ ZEND_NUM_ARGS() != 3) {
156 2 : php_error_docref(NULL TSRMLS_CC, E_WARNING, "Argument string(s) too long");
157 : }
158 :
159 51 : RETURN_LONG(distance);
160 : }
161 : /* }}} */
162 :
163 : /*
164 : * Local variables:
165 : * tab-width: 4
166 : * c-basic-offset: 4
167 : * End:
168 : * vim600: sw=4 ts=4 fdm=marker
169 : * vim<600: sw=4 ts=4
170 : */
|
