PHP字符串处理函数中有一个similar_text用于计算两个字符串的相似程度。今天来看看similar_text如何实现的。
similar_text — 计算两个字符串的相似度,返回两个字符串中匹配字符的数目
两个字符串的相似程度。注意该实现没有使用 Oliver 虚拟码中的堆栈,但是却进行了递归调用,这个做法可能会导致整个过程变慢或变快。也请注意,该算法的复杂度是 O(N**3),N 是最长字符串的长度。
上面的文档说明还是很绕。
源码中similar_text函数在内部调用了php_similar_char进行处理。ac是参数的个数。函数返回的是两个字符串中匹配字符的数目。如果想要获取相似的百分比,则需要传递一个引用参数获取。
在php_similar_char中有调用了php_similar_str,在看php_similar_char前,先看看php_similar_str的功能。
php_similar_str内部跑了三个嵌套的循环,这就难怪文档中描述的,时间复杂度是O(N**3)。在最里面的循环中,检查两个字符串连续一致的个数。最里层循环结束之后,判断是否大于已经获取到的最大相似数目。并记录最大相似情况下两个字符串相似处开始的位置。
在php_similar_char,通过php_similar_str拿到最大相似数目,以及两个字符串起始位置。在底下,则把text1,text2分为最大相似字符串前的字符,最大相似字符串,最大相似字符串后面字符串三个部分,分别在递归调用计算两个字符串中相似字符串前后两个部分对应的相似长度。直到字符串长度为0.
看到这,similar_text只能大概计算相似程度。其中有几个小问题。
1、两个空字符串的相似度是0。
2、假设两个字符串'abcdefg','qabdefgabc',直观上这两个字符串中“匹配字符”的数目有a,b,c,d,e,f,g 但是当你执行similar_text拿到的结果确是6。
看看整个执行过程:
a、获取最常匹配串的长度'defg',长度4,pos1=3,pos2=3
b、获取abc,qab相似长度度2
c、获取空字符串和abc相似度0
所以上述计算结果,相似字符串长度为6.
3、顺序敏感 顺序敏感其实也是由于拆分的问题导致的。比如字符串"PHP IS GREAT" 和字符串"WITH MYSQL" 不同的顺序得到的结果分别是2,3。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 意想不到的MySQL复制延迟原因
- Kubernetes VS Docker意想不到的结局
- 网络安全无小事:那些意想不到的黑客攻击方式
- 放弃 OpenStack?恐怕还不到时候
- 盘点一下不到100行的给力代码
- Xcode 静态链接库找不到的问题
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
架构真经
马丁L. 阿伯特(Martin L. Abbott)、迈克尔T.费舍尔(Michael T. Fisher) / 机械工业出版社 / 2017-4 / 79
前言 感谢你对本书第2版感兴趣!作为一本入门、进修和轻量级的参考手册,本书旨在帮助工程师、架构师和管理者研发及维护可扩展的互联网产品。本书给出了一系列规则,每个规则围绕着不同的主题展开讨论。大部分的规则聚焦在技术上,少数规则涉及一些关键的思维或流程问题,每个规则对构建可扩展的产品都是至关重要的。这些规则在深度和焦点上都有所不同。有些规则是高级的,例如定义一个可以应用于几乎任何可扩展性问题的模......一起来看看 《架构真经》 这本书的介绍吧!
在线进制转换器
各进制数互转换器
UNIX 时间戳转换
UNIX 时间戳转换