搜索
首页后端开发php教程PHP函数similar_text()的原理_PHP教程
PHP函数similar_text()的原理_PHP教程Jul 13, 2016 am 10:27 AM
phptext函数原理字符串每次相似计算

   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

  //遍历第二个字符串

  for (q = (char *) txt2; q

  //发现有字符相同,继续循环找,l为相同部分的长度

  for (l = 0; (p + 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

  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分别为两个字符串的长度。

www.bkjia.comtruehttp://www.bkjia.com/PHPjc/815793.htmlTechArticlePHP有个计算两个字符串相似度的函数similar_text(),可以得出一个百分比来表示两个字符串的相似程度。效果如下: similar_text('aaaa', 'aaaa', $...
声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
php怎么把负数转为正整数php怎么把负数转为正整数Apr 19, 2022 pm 08:59 PM

php把负数转为正整数的方法:1、使用abs()函数将负数转为正数,使用intval()函数对正数取整,转为正整数,语法“intval(abs($number))”;2、利用“~”位运算符将负数取反加一,语法“~$number + 1”。

php怎么实现几秒后执行一个函数php怎么实现几秒后执行一个函数Apr 24, 2022 pm 01:12 PM

实现方法:1、使用“sleep(延迟秒数)”语句,可延迟执行函数若干秒;2、使用“time_nanosleep(延迟秒数,延迟纳秒数)”语句,可延迟执行函数若干秒和纳秒;3、使用“time_sleep_until(time()+7)”语句。

php怎么除以100保留两位小数php怎么除以100保留两位小数Apr 22, 2022 pm 06:23 PM

php除以100保留两位小数的方法:1、利用“/”运算符进行除法运算,语法“数值 / 100”;2、使用“number_format(除法结果, 2)”或“sprintf("%.2f",除法结果)”语句进行四舍五入的处理值,并保留两位小数。

php怎么根据年月日判断是一年的第几天php怎么根据年月日判断是一年的第几天Apr 22, 2022 pm 05:02 PM

判断方法:1、使用“strtotime("年-月-日")”语句将给定的年月日转换为时间戳格式;2、用“date("z",时间戳)+1”语句计算指定时间戳是一年的第几天。date()返回的天数是从0开始计算的,因此真实天数需要在此基础上加1。

php怎么替换nbsp空格符php怎么替换nbsp空格符Apr 24, 2022 pm 02:55 PM

方法:1、用“str_replace(" ","其他字符",$str)”语句,可将nbsp符替换为其他字符;2、用“preg_replace("/(\s|\&nbsp\;||\xc2\xa0)/","其他字符",$str)”语句。

php怎么判断有没有小数点php怎么判断有没有小数点Apr 20, 2022 pm 08:12 PM

php判断有没有小数点的方法:1、使用“strpos(数字字符串,'.')”语法,如果返回小数点在字符串中第一次出现的位置,则有小数点;2、使用“strrpos(数字字符串,'.')”语句,如果返回小数点在字符串中最后一次出现的位置,则有。

php字符串有没有下标php字符串有没有下标Apr 24, 2022 am 11:49 AM

php字符串有下标。在PHP中,下标不仅可以应用于数组和对象,还可应用于字符串,利用字符串的下标和中括号“[]”可以访问指定索引位置的字符,并对该字符进行读写,语法“字符串名[下标值]”;字符串的下标值(索引值)只能是整数类型,起始值为0。

php怎么设置implode没有分隔符php怎么设置implode没有分隔符Apr 18, 2022 pm 05:39 PM

在PHP中,可以利用implode()函数的第一个参数来设置没有分隔符,该函数的第一个参数用于规定数组元素之间放置的内容,默认是空字符串,也可将第一个参数设置为空,语法为“implode(数组)”或者“implode("",数组)”。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前By尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
4 周前By尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
4 周前By尊渡假赌尊渡假赌尊渡假赌

热工具

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SecLists

SecLists

SecLists是最终安全测试人员的伙伴。它是一个包含各种类型列表的集合,这些列表在安全评估过程中经常使用,都在一个地方。SecLists通过方便地提供安全测试人员可能需要的所有列表,帮助提高安全测试的效率和生产力。列表类型包括用户名、密码、URL、模糊测试有效载荷、敏感数据模式、Web shell等等。测试人员只需将此存储库拉到新的测试机上,他就可以访问到所需的每种类型的列表。

螳螂BT

螳螂BT

Mantis是一个易于部署的基于Web的缺陷跟踪工具,用于帮助产品缺陷跟踪。它需要PHP、MySQL和一个Web服务器。请查看我们的演示和托管服务。

mPDF

mPDF

mPDF是一个PHP库,可以从UTF-8编码的HTML生成PDF文件。原作者Ian Back编写mPDF以从他的网站上“即时”输出PDF文件,并处理不同的语言。与原始脚本如HTML2FPDF相比,它的速度较慢,并且在使用Unicode字体时生成的文件较大,但支持CSS样式等,并进行了大量增强。支持几乎所有语言,包括RTL(阿拉伯语和希伯来语)和CJK(中日韩)。支持嵌套的块级元素(如P、DIV),

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

功能强大的PHP集成开发环境