similar_text 有哪些意想不到的惊喜(PHP)

栏目: PHP · 发布时间: 5年前

PHP字符串处理函数中有一个similar_text用于计算两个字符串的相似程度。今天来看看similar_text如何实现的。

similar_text — 计算两个字符串的相似度,返回两个字符串中匹配字符的数目

两个字符串的相似程度。注意该实现没有使用 Oliver 虚拟码中的堆栈,但是却进行了递归调用,这个做法可能会导致整个过程变慢或变快。也请注意,该算法的复杂度是 O(N**3),N 是最长字符串的长度。

similar_text 有哪些意想不到的惊喜(PHP)

上面的文档说明还是很绕。

源码中similar_text函数在内部调用了php_similar_char进行处理。ac是参数的个数。函数返回的是两个字符串中匹配字符的数目。如果想要获取相似的百分比,则需要传递一个引用参数获取。

在php_similar_char中有调用了php_similar_str,在看php_similar_char前,先看看php_similar_str的功能。

similar_text 有哪些意想不到的惊喜(PHP)

php_similar_str内部跑了三个嵌套的循环,这就难怪文档中描述的,时间复杂度是O(N**3)。在最里面的循环中,检查两个字符串连续一致的个数。最里层循环结束之后,判断是否大于已经获取到的最大相似数目。并记录最大相似情况下两个字符串相似处开始的位置。

在php_similar_char,通过php_similar_str拿到最大相似数目,以及两个字符串起始位置。在底下,则把text1,text2分为最大相似字符串前的字符,最大相似字符串,最大相似字符串后面字符串三个部分,分别在递归调用计算两个字符串中相似字符串前后两个部分对应的相似长度。直到字符串长度为0.

similar_text 有哪些意想不到的惊喜(PHP)

看到这,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。


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

JavaScript凌厉开发

JavaScript凌厉开发

张鑫 黄灯桥、杨彦强 / 清华大学出版社 / 2010 年4月 / 49.00元

本书详细介绍Ext JS框架体系结构,以及利用HTML/CSS/JavaScript进行前端设计的方法和技巧。作者为Ext中文站站长领衔的三个国内Ext JS先锋,在开发思维和开发经验上有着无可争议的功力。 本书包含的内容有Ext.Element.*、事件Observable、Ext组件+MVC原理、Grid/Form/Tree/ComboBox、Ajax缓存Store等,并照顾JavaSc......一起来看看 《JavaScript凌厉开发》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

URL 编码/解码
URL 编码/解码

URL 编码/解码

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具