PHP函數similar

 　　PHP有個計算兩個字符串相似度的函數similar_text()，可以得出一個百分比來表示兩個字符串的相似程度。效果如下：

　　similar_text('aaaa', 'aaaa', $percent);

　　var_dump($percent);

　　//float(100)

　　similar_text('aaaa', 'aaaabbbb', $percent);

　　var_dump($percent);

　　//float(66.666666666667)

　　similar_text('abcdef', 'aabcdefg', $percent);

　　var_dump($percent);

　　//float(85.714285714286)

　　利用這個函數，可以用來做模糊搜索的功能，或者其他需要模糊匹配的功能。最近我在驗證碼識別研究中的特征匹配一步上涉及到了這個函數。

　　但這個函數具體使用了怎樣的算法呢?我研究了他的底層實現，總結為三步：

　　(1)找出兩個字符串中相同部分最長的一段;

　　(2)再用同樣的方法在剩下的兩段中分別找出相同部分最長的一段，以此類推，直到沒有任何相同部分;

　　(3)相似度 = 所有相同部分的長度之和 * 2 / 兩個字符串的長度之和;

　　我研究的源代碼版本是PHP 5.4.6，相關的代碼位於文件php-5.4.6/ext/standard/string.c的第2951~3031行。以下是我加過注釋後源代碼。

　　//找出兩個字符串中相同部分最長的一段

　　static void php_similar_str(const char *txt1, int len1, const char *txt2, int len2, int *pos1, int *pos2, int *max)

　　{

　　char *p, *q;

　　char *end1 = (char *) txt1 + len1;

　　char *end2 = (char *) txt2 + len2;

　　int l;

　　*max = 0;

　　//以第一個字符串為基准開始遍歷

　　for (p = (char *) txt1; p < end1; p++) {

　　//遍歷第二個字符串

　　for (q = (char *) txt2; q < end2; q++) {

　　//發現有字符相同，繼續循環找，l為相同部分的長度

　　for (l = 0; (p + l < end1) && (q + l < end2) && (p[l] == q[l]); l++);

　　//冒泡方法找出最長的一個l，並記住相同部分的開始位置

　　if (l > *max) {

　　*max = l;

　　*pos1 = p - txt1;

　　*pos2 = q - txt2;

　　}

　　}

　　}

　　}

　　//計算兩個字符串的相同部分的總長度

　　static int php_similar_char(const char *txt1, int len1, const char *txt2, int len2)

　　{

　　int sum;

　　int pos1, pos2, max;

　　//找出兩個字符串相同部分最長的一段

　　php_similar_str(txt1, len1, txt2, len2, &pos1, &pos2, &max);

　　//這裡是對sum的初始賦值，也是對max值的判斷

　　//如果max為零，表示兩個字符串沒有任何相同的字符，也就會跳出if

　　if ((sum = max)) {

　　//對前半段遞歸，相同段長度累加

　　if (pos1 && pos2) {

　　sum += php_similar_char(txt1, pos1,

　　txt2, pos2);

　　}

　　//對後半段遞歸，相同段長度累加

　　if ((pos1 + max < len1) && (pos2 + max < len2)) {

　　sum += php_similar_char(txt1 + pos1 + max, len1 - pos1 - max,

　　txt2 + pos2 + max, len2 - pos2 - max);

　　}

　　}

　　return sum;

　　}

　　//PHP函數定義

　　PHP_FUNCTION(similar_text)

　　{

　　char *t1, *t2;

　　zval **percent = NULL;

　　int ac = ZEND_NUM_ARGS();

　　int sim;

　　int t1_len, t2_len;

　　//檢查參數合法性

　　if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "ss|Z", &t1, &t1_len, &t2, &t2_len, &percent) == FAILURE) {

　　return;

　　}

　　//如果有第三個參數

　　if (ac > 2) {

　　convert_to_double_ex(percent);

　　}

　　//如果兩個字符串長度都為0，返回0

　　if (t1_len + t2_len == 0) {

　　if (ac > 2) {

　　Z_DVAL_PP(percent) = 0;

　　}

　　RETURN_LONG(0);

　　}

　　//調用上面的函數，計算兩個字符串的相似庫

　　sim = php_similar_char(t1, t1_len, t2, t2_len);

　　//可以看第三個參數percent的計算公式

　　if (ac > 2) {

　　Z_DVAL_PP(percent) = sim * 200.0 / (t1_len + t2_len);

　　}

　　RETURN_LONG(sim);

　　}

　　另外，PHP還提供了另外一個計算字符串相似度的函數levenshtein()，通過計算兩個字符串的編輯距離來表示字符串相似度，這也是一種很常見的算法。levenshtein()的性能相比similar_text()要好一些，因為通過前面的代碼分析可以看到，similar_text()的復雜度是O(n^3)，n表示最長字符串的長度，而levenshtein()的復雜度為O(m*n)，m與n分別為兩個字符串的長度。