请选择 进入手机版 | 继续访问电脑版
设为首页收藏本站

一起开发

 找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索

PHP函数similar_text()对比两个字符串的相似度原理解析

发表于 2013-5-22 21:49 作者:phper
php结合memcache实现访问统计文章点击的计数
随着访问量的增大,点击数直接更新数据库已经不太可能了,数据库中点击的更新 ...
Web开发利器,简版开发手册助您快速开发(图
web开发,帮助手册是我们经常查询的,查函数、查属性等等,下面图片里综合了各开发手册 ...
        在seo中我们经常用到伪原创、原创文章,那么你知道你修改过的内容和之前的内容有多大的相似度吗,下面我们介绍一下php中的函数similar_text()便可以轻松的获取两个字符串的相似度值。
         PHP计算两个字符串相似度的函数similar_text(),可以得出一个百分比来表示两个字符串的相似程度。效果如下:
  1. similar_text('http://www.17kaifa.com', 'http://www.17kaifa.com', $percent);
  2. var_dump($percent);
  3. //float(100)
  4. similar_text('<a href="http://www.17kaifa.com">一起开发网</a>', http://www.17kaifa.com', $percent);
  5. var_dump($percent);
  6. //float(66.666666666667)
  7. similar_text('abcdef一起开发 -  web开发社区', 'aabcdefg一起开发 -  web开发社区', $percent);
  8. var_dump($percent);
  9. //float(85.714285714286)
复制代码
利用这个函数,可以用来做模糊搜索的功能,或者其他需要模糊匹配的功能。最近我在验证码识别研究中的特征匹配一步上涉及到了这个函数。
但这个函数具体使用了怎样的算法呢?我研究了他的底层实现,总结为三步:
(1)找出两个字符串中相同部分最长的一段;
(2)再用同样的方法在剩下的两段中分别找出相同部分最长的一段,以此类推,直到没有任何相同部分;
(3)相似度 = 所有相同部分的长度之和 * 2 / 两个字符串的长度之和;

我研究的源代码版本是PHP 5.4.6,相关的代码位于文件php-5.4.6/ext/standard/string.c的第2951~3031行。以下是我加过注释后源代码。
  1. //找出两个字符串中相同部分最长的一段
  2. static void php_similar_str(const char *txt1, int len1, const char *txt2, int len2, int *pos1, int *pos2, int *max)
  3. {
  4.         char *p, *q;
  5.         char *end1 = (char *) txt1 + len1;
  6.         char *end2 = (char *) txt2 + len2;
  7.         int l;

  8.         *max = 0;
  9.         //以第一个字符串为基准开始遍历
  10.         for (p = (char *) txt1; p < end1; p++) {
  11.                 //遍历第二个字符串
  12.                 for (q = (char *) txt2; q < end2; q++) {
  13.                         //发现有字符相同,继续循环找,l为相同部分的长度
  14.                         for (l = 0; (p + l < end1) && (q + l < end2) && (p[l] == q[l]); l++);
  15.                         //冒泡方法找出最长的一个l,并记住相同部分的开始位置
  16.                         if (l > *max) {
  17.                                 *max = l;
  18.                                 *pos1 = p - txt1;
  19.                                 *pos2 = q - txt2;
  20.                         }
  21.                 }
  22.         }
  23. }

  24. //计算两个字符串的相同部分的总长度
  25. static int php_similar_char(const char *txt1, int len1, const char *txt2, int len2)
  26. {
  27.         int sum;
  28.         int pos1, pos2, max;

  29.         //找出两个字符串相同部分最长的一段
  30.         php_similar_str(txt1, len1, txt2, len2, &pos1, &pos2, &max);
  31.         //这里是对sum的初始赋值,也是对max值的判断
  32.         //如果max为零,表示两个字符串没有任何相同的字符,也就会跳出if
  33.         if ((sum = max)) {
  34.                 //对前半段递归,相同段长度累加
  35.                 if (pos1 && pos2) {
  36.                         sum += php_similar_char(txt1, pos1,
  37.                                                                         txt2, pos2);
  38.                 }
  39.                 //对后半段递归,相同段长度累加
  40.                 if ((pos1 + max < len1) && (pos2 + max < len2)) {
  41.                         sum += php_similar_char(txt1 + pos1 + max, len1 - pos1 - max,
  42.                                                                         txt2 + pos2 + max, len2 - pos2 - max);
  43.                 }
  44.         }

  45.         return sum;
  46. }

  47. //PHP函数定义
  48. PHP_FUNCTION(similar_text)
  49. {
  50.         char *t1, *t2;
  51.         zval **percent = NULL;
  52.         int ac = ZEND_NUM_ARGS();
  53.         int sim;
  54.         int t1_len, t2_len;

  55.         //检查参数合法性
  56.         if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "ss|Z", &t1, &t1_len, &t2, &t2_len, &percent) == FAILURE) {
  57.                 return;
  58.         }

  59.         //如果有第三个参数
  60.         if (ac > 2) {
  61.                 convert_to_double_ex(percent);
  62.         }

  63.         //如果两个字符串长度都为0,返回0
  64.         if (t1_len + t2_len == 0) {
  65.                 if (ac > 2) {
  66.                         Z_DVAL_PP(percent) = 0;
  67.                 }

  68.                 RETURN_LONG(0);
  69.         }

  70.         //调用上面的函数,计算两个字符串的相似度
  71.         sim = php_similar_char(t1, t1_len, t2, t2_len);

  72.         //可以看到percent的计算公式
  73.         if (ac > 2) {
  74.                 Z_DVAL_PP(percent) = sim * 200.0 / (t1_len + t2_len);
  75.         }

  76.         RETURN_LONG(sim);
  77. }
复制代码
此外,PHP还提供了另外一个计算字符串相似度的函数levenshtein(),通过计算两个字符串的编辑距离来表示字符串相似度,这也是一种很常见的算法。levenshtein()的性能相比similar_text()要好一些,因为通过前面的代码分析可以看到,similar_text()的复杂度是O(n^3),n表示最长字符串的长度,而levenshtein()的复杂度为O(m*n),m与n分别为两个字符串的长度。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

Archiver|手机版|一起开发   

GMT+8, 2017-9-23 20:45 , Processed in 0.120637 second(s), 26 queries .

Powered by Discuz! X2.5 Licensed

© 2001-2012 Comsenz Inc.

回顶部