切,一个字符串有什么好研究的。别这么说,看过《平凡的世界》么,平凡的字符串也可以有不平凡的故事。试看:(1)在C语言中,strlen计算字 符串的时间复杂度是?PHP中呢?(2)在PHP中,怎样处理多字节字符串?PHP对unicode的支持如何?同样是字符串,为什么c 语言与C++/PHP/Java的均不相同?数据结构决定算法,这句话一点不假。那么我们今天就来掰一掰,PHP中的字符串结构,以及相关 字符串函数的实现。一、字符串基础字符串可以说是PHP中遇到最多的数据结构之一了(另外一个比较常用的是数组,见http://ww w.cnblogs.com/ohmygirl/p/internal-4.htmlPHP内核探索之变量(4)-数组操作)。而由于P HP语言的特性和应用场景,使得我们日常的很多工作,实际上都是在处理字符串。也正是这个原因,PHP为开发者提供了丰富的字符串操作函数 (初步统计约有100个,这个数量相当可观)。那么,在PHP中,字符串是怎样实现的呢?与C语言又有什么区别呢?1.PHP中字符串 的表现形式在PHP中使用字符串有四种常见的形式:(1)双引号这种形式比较常见:$str=”thisis\0astrin g”;而且以双引号包含的字符串中可以包含变量、控制字符等:$str="thisis$name,aha.\n";(2)单 引号单引号包含的字符都被认为是raw的,因此不会解析单引号中的变量,控制字符等:123$string?=?"test";$st r?=?''thisis$string,aha\n'';echo?$str;(3)????HeredocHeredoc比较 适合较长的字符串表示,且对于多行的字符串表示更加灵活多样。与双引号表示形式类似,heredoc中也可以包含变量。常见的形式是:12 34567$string?="teststring";$str?=<<stringis?$stringSTR;?echo?$str;(4)????nowdoc(5.3+支持)nowdoc和h eredoc是如此的类似,以至于我们可以把它们当做是一对儿亲兄弟。nowdoc的起始标志符是用单引号括起来的,与单引号相似,它不会 解析其中的变量,格式控制符等:123456$s?=<<<''EOT''thisis?$strthisis\ttest;EO T;?echo?$s;2.??????PHP中字符串的结构?之前提到过,PHP中变量是用Zval(http://www.cn blogs.com/ohmygirl/p/internal-variable-1.htmlPHP内核探索之变量(1)Zval)这样 一个结构体来存储的。Zval的结构是:struct_zval_struct{zvalue_valuevalue;/va lue/zend_uintrefcount__gc;/variablerefcount/zend_uchar type;/activetype/zend_ucharis_ref__gc;/ifitisarefv ariable/};而变量的值是zvalue_value这样一个共用体:typedefunion_zvalue_valu e{longlval;doubledval;struct{/string/charval;intl en;}str;HashTableht;zend_object_valueobj;}zvalue_value;我们 从中抽取出字符串的结构:struct{charval;intlen;}str;现在比较清楚了,PHP中字符串在底层实 际上是一个结构体,该结构体包含了指向字符串的指针和该字符串的长度。那么为什么这么做呢?换句话说,这样做有什么好处呢?我们接下来,将 PHP的字符串与C语言的字符串做一个对比,以解释采用这样一种结构来存储字符串的优势。3.与c语言字符串的比较我们知道,在c语言 中,一个字符串可以用两种常见的形式存储,一种是使用指针方式,另一种是使用字符数组。我们接下来的说明,都以c语言的字符数组的方式来存 储字符串。(1)??PHP字符串是二进制安全的,而C字符串不是。我们经常会提到”二进制安全”这一术语,那么二进制安全究竟是什么意 思呢?wikipedia中对二进制安全(BinarySafe)的定义是:Binary-safeisacomputerp rogrammingtermmainlyusedinconnectionwithstringmanipulatin gfunctions.Abinary-safefunctionisessentiallyonethattreat sitsinputasarawstreamofdatawithoutanyspecificformat. Itshouldthusworkwithall256possiblevaluesthatacharacter cantake(assuming8-bitcharacters).翻译过来就是:二进制安全是计算机编程的术语,主要用 于字符串操作函数。一个二进制安全的函数,本质上是指它将输入看做是原始的数据流(raw)而不包含任何特殊的格式。那么为什么C字符串 不是二进制安全的?我们知道,在C语言中,以字符数组表示的字符串总是以\0结尾的,这个\0便是C字符串的specificforma t,用于标识字符串的结束。更近一步说,如果一个字符串中本身包含了\0且并不是该字符串的结尾,那么在C中,\0后面的所有数据都会被 忽略(感觉就像是字符串被莫名其妙的截断了)。这也意味着,C字符串只合适保存简单的文本,而不能用于保存图片、视频、其他文件等二进制 数据。而在PHP中,我们可以使用$str=file_get_contents(“filename”);保存图片、视频等二进制数 据。(2)??效率对比。由于C字符串中使用\0来标志字符串的结束,因此,对于strlen函数而言,获取字符串长度的操作需要顺序遍 历字符串,直到遇到\0为止,因此strlen函数的时间复杂度是O(n)。而在PHP中,字符串是以:struct{charva l;intlen;}str;?这样一种结构体来表示的,因而获取字符串的长度只需要通过常量的时间便可以完成:#defineZ _STRLEN(zval)(zval).value.str.len当然,仅仅是strlen函数的性能,无法支持 “PHP中string比c字符串的效率更高”的结论(一个很明显的原因是PHP是构建在C语言之上的高级语言),而仅仅说明,在时间复杂 度上,PHP字符串比C字符串更加高效。(3)很多C字符串函数存在缓冲区溢出的漏洞缓存区溢出是C语言中常见的漏洞,这种安全隐患经常 是致命的。一个典型的缓存区溢出的例子如下:voidstr2Buf(charstr){charbuffer[16];s trcpy(buffer,str);}?这个函数将str的内容copy到buffer数组中,而buffer数组的大小是16,因此如 果str的长度大于16,便会发生缓冲区溢出的问题。除了strcpy,还有gets,strcat,fprintf等字符串函数也会 有缓冲区溢出的问题。PHP中并没有strcpy与strcat之类的函数,实际上由于PHP语言的简洁性,并不需要提供strcpy和s trcat之类的函数。例如我们要复制一个字符串,直接使用=即可:$str="thisisastring";$str_co py=$str;由于PHP中变量共享zval的特性,并不会有空间浪费.而简单的.连接符可以轻松实现字符串连接:$str= "thisis";$str.="teststring";echo$str;关于字符串连接符过程中的内存分配和管理,可以 查看zend引擎部分的实现,这里暂时忽略。二、字符串操作相关函数(部分)毫无疑问,研究字符串的目的并不只是为了知道它的结构和特 性,而是为了更好的使用它。我们日常的工作中,恐怕有一般以上的工作都是在与字符串打交道:如处理一个日期串、加密一个密码、获取用户信息 、正则表达式匹配替换、字符串替换、格式化一个串等等。可以说,在PHP开发中,你无法避免与字符串的直接或者间接接触(就像无法摆脱呼吸 )。正因为如此,PHP为开发者提供了大量的、丰富的字符串操作函数(http://cn2.php.net/manual/en/re f.strings.php),这对于90%以上的字符串操作,已经基本足够。由于字符串函数众多,不可能一一说明。这里只挑选几个比较 典型的字符串操作函数来做简单的说明(我相信80%以上的PHPer对于字符串的操作函数掌握的非常的好)。在开始说明之前,有必要强调 一下字符串函数的使用原则,理解和掌握这些原则对于高效、熟练使用字符串函数非常关键,这些原则包括(不仅限于):(1)如果你的操作既 可以使用正则表达式,也可以使用字符串。那么优先考虑字符串操作。正则表达式是处理文本的绝好工具,尤其对于模式查找、模式替换这一类应 用,正则可以说是无往不利。正因为如此,正则表达式在很多场合都被滥用。如果对于你的字符串操作,既可以使用字符串函数完成,也可以使用正 则表达式完成,那么,请优先选择字符串操作函数,因为正则表达式在一定场合下会有严重的性能问题。(2)注意false与0PHP是 弱变量类型,相信不少phper开始都深受其害var_dump(0==false);//bool(true)var_dump( 0===false);//bool(false)等等,这与字符串操作函数有什么关系?在PHP中,有一类函数用于查找(如s trpos,stripos),这类查找函数在查找成功时,返回的是子串在原串中的index,如strpos:var_dump(st rpos("thisisabc","abc"));而在查找不成功时,返回的是false:var_dump(strpos(" thisisabc","angle"));//false这里便有一个坑:字符串的索引也是以0开始的!如果子串刚好在源串的起 始位置出现,那么,简单的==比较便无法区分究竟strpos是不是成功:var_dump(strpos("thisisabc", "this"));因此我们一定是要用===来比较的:if((strpos("thisisabc","this"))== =false){//notfound}(3)多看手册,避免重复造轮子。相信不少PHPer面试都碰到过这样的问题:如何 翻转一个字符串?由于题目中只提及“如何“,而并没有限制”不使用PHP内置函数“。那么对于本题,最简洁的方法自然是使用strrev函 数。另一个说明不应该重复造轮子的函数是levenshtein函数,这个函数如同其名字一样,返回的是两个字符串的编辑距离。作为动态规 划(DP)的典型代表案例之一,我想编辑距离很多人都不陌生。碰到这类问题,你还准备DP搞起吗?一个函数搞定它:$str1="th isistest";$str2="hisistes";echolevenshtein($str1,$str2);在 某些情况下,我们都应该尽可能的“懒“,不是吗。以下是字符串操作函数节选(对于最常见的操作,请直接参考手册)1.strlen此标题 一出,我猜想大多数人的表情是这样的:或者是这样的:?我要说的,并不是这个函数本身,而是这个函数的返回值。12int?strlen (?string?$string)Returnsthelengthofthegiven?string.虽然手册上明 确指出“strlen函数返回给定字符串的长度”,但是,并没有对长度单位做任何说明,长度究竟是指”字符的个数“还是说”字符的字节数“ 。而我们要做的,并不是臆想,而是测试:在GBK编码格式下:echostrlen(“这是中文”);//8说明strlen函数返回的 是字符串的字节数。那么又有问题了,如果是utf-8编码,由于中文在utf8编码的情况下,每个中文使用3个byte,因而,我们期望的 结果应该是12:echostrlen(“这是中文”);//12这说明:strlen计算字符串的长度依赖于当前的编码格式,其值并不 是唯一的!这在某些情况下,自然是无法满足要求的。这时,多字节扩展mbstring便有它的发挥余地了:echomb_strlen( "这是中文","GB2312");//4关于这点,在多字节处理中会有相应说明,这里略过。2.str_word_countstr _word_count是另一个比较强大的且容易忽略的字符串函数。mixedstr_word_count(string$st ring[,int$format=0[,string$charlist]])其中$format的不同值可以使s tr_word_count函数有不同的行为。现在,我们手头有这样的文本:WhenIamdownand,ohmyso ul,sowearyWhentroublescomeandmyheartburdenedbeThen,Iam stillandwaithereinthesilenceUntilyoucomeandsitawhile withmeYouraisemeup,soIcanstandonmountainsYouraisemeu p,towalkonstormyseasIamstrong,whenIamonyourshoulders Youraisemeup…TomorethanIcanberYouraisemeup,soIcan standonmountainsYouraisemeup,towalkonstormyseasIamstr ong,whenIamonyourshouldersYouraisemeup,TomorethanIc anbe。那么:(1)$format=0$format=0,$format返回的是文本中的单词的个数:echostr_w ord_count(file_get_contents(“word”));//112(2)$format=1$format= 1时,返回的是文本中全部单词的数组:print_r(file_get_contents(“word”),1);Array([0 ]=>When[1]=>I[2]=>am[3]=>down[4]=>and[5]=>oh[6] =>my[7]=>soul[8]=>so[9]=>weary[10]=>When[11]=>tr oubles......)这一特性有什么作用呢?比如英文分词。还记得“单词统计”的问题么?str_word_count可以轻松完成 单词统计TopK的问题:$s=file_get_contents("./word");$a=array_count_val ues(str_word_count($s,1));arsort($a);print_r($a);/Array([ I]=>10[me]=>7[raise]=>6[up]=>6[You]=>6[am]=>6[o n]=>6[can]=>4[and]=>4[be]=>3[so]=>3……);/(3)$forma t=2$format=2时,返回的是一个关联数组:$a=str_word_count($s,2);print_r($a) ;/Array([0]=>When[5]=>I[7]=>am[10]=>down[15]=>and [20]=>oh[23]=>my[26]=>soul[32]=>so[35]=>weary[41] =>When[46]=>troubles[55]=>come...)/配合其他数组函数,可以实现更加多样化的功 能.例如,配合array_flip,可以计算某个单词最后一次出现的位置:$t=array_flip(str_word_coun t($s,2));print_r($t);而如果配合了array_unique之后再array_flip,则可以计算某个单词第一 次出现的位置:$t=array_flip(array_unique(str_word_count($s,2)));pri nt_r($t);Array([When]=>0[I]=>5[am]=>7[down]=>10[and] =>15[oh]=>20[my]=>23[soul]=>26[so]=>32[weary]=>3 5[troubles]=>46[come]=>55[heart]=>67...)3.?similar_tex t这是除了levenshtein()函数之外另一个计算两个字符串相似度的函数:intsimilar_text(string $first,string$second[,float&$percent])$t1="Youraiseme up,soIcanstandonmountains";$t2="Youraisemeup,towalk onstormyseas";$percent=0;echosimilar_text($t1,$t2,$percen t).PHP_EOL;//26echo$percent;//62.650602409639撇开具体的使用不谈,我很好奇底层对于 字符串的相似度是如何定义的。Similar_text函数实现位于?ext/standard/string.c?中,摘取其关键代码: ?1234567891011121314151617181920212223242526272829303132333435PHP _FUNCTION(similar_text){?chart1,t2;?zvalpercent=NULL;?in tac=ZEND_NUM_ARGS();?intsim;?intt1_len,t2_len;???/参数解析/ ?if(zend_parse_parameters(ZEND_NUM_ARGS(‘www.mntuku.cn’)TSRMLS_ CC,?"ss|Z",&t1,&t1_len,&t2,&t2_len,&percent)==FAILURE){? return;?}???/setpercenttodoubletype/?if(ac>2){?conver t_to_double_ex(percent);?}??/t1_len==0&&t2_len==0/?if( t1_len+t2_len==0){?if(ac>2){?Z_DVAL_PP(percent)=0;?}?R ETURN_LONG(0);?}???/计算字符串相同个数/?sim=php_similar_char(t1,t1_ len,t2,t2_len);???/相似百分比/?if(ac>2){?Z_DVAL_PP(percent) =sim200.0/(t1_len+t2_len);?}???RETURN_LONG(sim);}??可以看出,字 符串相似个数是通过?php_similar_char?函数实现的,而相似百分比则是通过公式:percent=sim200 /(t1串长度+t2串长度)来定义的。php_similar_char的具体实现:?1234567891011121314 15161718staticintphp_similar_char(constchartxt1,?intlen1,?c onst?chartxt2,?intlen2){?intsum;?intpos1=0,pos2=0,max ;??php_similar_str(txt1,len1,txt2,len2,&pos1,&pos2,&max);?i f((sum=max)){?if(pos1&&pos2){?sum+=php_similar_char(txt 1,pos1,txt2,pos2);?}??if((pos1+maxlen2)){?sum+=php_similar_char(txt1+pos1+max,len1-pos1- max,txt2+pos2+max,len2-pos2-max);?}?}??returnsum;}这个函数 通过调用php_similar_str来完成字符串相似个数的统计,而php_similar_str返回字符串s1与字符串s2的最长 相同字符串长度:1234567891011121314151617181920staticvoidphp_similar_st r(constchartxt1,?intlen1,?const?chartxt2,?intlen2,?int? pos1,?intpos2,?intmax){?charp,q;?charend1=(char)tx t1+len1;?charend2=(char)txt2+len2;?intl;?max=0;??? /查找最长串/?for(p=(char?)txt1;phar?)txt2;qlmax){?max=l;?po s1=p-txt1;?pos2=q-txt2;?}?}?}}?php_similar_str匹配完成之后,原始 的串被划分为三个部分:第一部分是最长串的左边部分,这一部分含有相似串,但是却不是最长的;第二部分是最长相似串部分;第三部分是最长串 的右边部分,与第一部分相似,这一部分含有相似串,但是也不是最长的。因而要递归对第一部分和第三部分求相似串的长度:?12345678 9/最长的串左边部分相似串/if?(pos1&&pos2){?sum+=php_similar_char(tx t1,pos1,txt2,pos2);}?/右半部分相似串/if?((pos1+maxpos2+maxlen1-pos1-max,txt2+pos2+max,len2-pos2-max);}匹配的过程如下 图所示:?对于字符串函数的更多解释,可以参考PHP的在线手册,这里不再一一列举。三、多字节字符串迄今为止,我们讨论的所有的字符串 和相关操作函数都是单字节的。然而这个世界是如此的丰富多彩,就好比有红瓤的西瓜也有黄瓤的西瓜一样,字符串也不例外。如我们常用的中文汉 字在GBK编码的情况下,实际上是使用两个字节来编码的。多字节字符串不仅仅局限于中文汉字,还包括日文,韩文等等多个国家的文字。正因为 如此,对于多字节字符串的处理显得异常重要。字符和字符集是编程过程中不可避免总是要遇到的术语。如果有童鞋对于这一块的内容并不是特别 清晰,建议移步《编码大事1字符编码基础-字符和字符集,》由于我们日常中使用较多的是中文,因而我们以中文字符串截取为例,重点研究 中文字符串的问题。中文字符串的截取中文字符串截取一直是个相对来说比较麻烦的问题,原因在于:(1)PHP原生的substr函数 只支持单字节字符串的截取,对于多字节的字符串略显无力(2)PHP的扩展mbstring需要服务器的支持,事实上,很多开发环境中并 没有开启mbstring扩展,对于习惯使用mbstring扩展的童鞋非常遗憾。(3)一个更为复杂的问题是,在UTF-8编码的情况 下,虽然中文是3个字节的,但是中文的某些特殊字符(如脱字符·)实际上是双字节编码的。这无疑加大了中文字符串截取的难度(毕竟,中文字 符串中不可能完全不包含特殊字符)。头疼之余,还是要自己撸一个中文的字符串截取的库,这个字符串截取函数应该与substr有相似的函 数参数列表,而且要支持中文GBK编码和UTF-8编码情况下的截取,为了效率起见,如果服务器已经开启了mbstring扩展,那么就应 该直接使用mbstring的字符串截取。API:StringcnSubstr(string$str,int$start, int$len,[$encode=’GBK’]);//注意参数中$start,$len都是字符数而不是字节数。我们以UTF- 8编码为例,来说明UTF8编码下中文的截取思路。(1)编码范围:UTF-8的编码范围(utf-8使用1-6个字节编码字符,实际上只 使用了1-4字节):1个字节:00——7F2个字节:C080——DFBF3个字符:E08080——EFBFBF4个字符:F0808 080——F7BFBFBF据此,可以根据第一个字节的范围确定该字符所占的字节数:$ord=ord($str{$i});$or d<192单字节和控制字符192<=$ord<224双字节224<=$ord<240三字节中文并没有四个字 节的字符(2)$start为负的情况1234567if(?$start<0){?$start+=cnStrlen_utf 8(?$str);???if(?$start<0){?$start=0;?}}网上大多数字符串截取版本都没有处理$st art<0的情况,按照PHPsubstr的API设计,在$start<0时,应该加上字符串的长度(多字节指字符数)。其中c nStrlen_utf8用于获取字符串在utf8编码下的字符数:12345678910111213141516171819func tion?cnStrlen_utf8(?$str?){?$len=0;?$i=0;?$slen=?strlen(?$ str);??while(?$i$slen){?$ord=ord(?$str{$i});?if(?$ord<1 27){?$i++;?}elseif(?$ord<224){?$i+=2;?}else{?$i+=3;?}?$l en++;?}???return$len;}因此UTF-8的截取算法为:123456789101112131415161718 19202122232425262728293031323334353637383940414243444546474849505 152535455565758function?cnSubstr_utf8(?$str,?$start,?$len){?if( ?$start<0){?$start+=cnStrlen_utf8(?$str);???if(?$start<0 ){?$start=0;?}?}???$slen=?strlen(?$str);???if(?$len<0){?$l en+=?$slen?-?$start;???if($len<0){?$len=0;?}?}??$i=0;?$co unt=0;???/获取开始位置/?while(?$i$slen&&?$count?$start){?$ ord=ord(?$str{$i});???if(?$ord<127){?$i++;?}elseif(?$ord< 224){?$i+=2;?}else{?$i+=3;?}?$count++;?}???$count=0;?$su bstr=?'''';???/截取$len个字符/?while(?$i$slen&&?$count?$len) {?$ord=ord(?$str{$i});???if(?$ord<127){?$substr.=?$str{$i}; ?$i++;?}elseif(?$ord<224){?$substr.=?$str{$i}.?$str{$i+1}; ?$i+=2;?}else{?$substr.=?$str{$i}.?$str{$i+1}.?$str{$i+2};?$ i+=3;?}?$count++;?}???return$substr;}而最终的cnSubstr()可以设计如下(程序还 有很多优化的余地):123456789101112131415161718192021function?cnSubstr(?$s tr,?$start,?$len,?$encode=?''gbk''){?if(?extension_loaded("mbst ring")){?//echo"usembstring";?//returnmb_substr($str,$start ,$len,$encode);?}??$enc=?strtolower(?$encode);?switch($enc){ ?case''gbk'':?case''gb2312'':?returncnSubstr_gbk($str,?$start,?$le n);?break;?case''utf-8'':?case''utf8'':?returncnSubstr_utf8($str,? $start,?$len);?break;?default:?//dosomewarningortriggererror ;?}?}简单的测试一下:$str="这是中文的字符串string,还有abs·";for($i=0;$i<10;$i++){echocnSubstr($str,$i,3,''utf8'').PHP_EOL;}最后贴一下ThinkPHPextend中提供的msubstr函数(这是用正则表达式做的substr):123456789101112131415161718function?msubstr($str,?$start=0,?$length,?$charset="utf-8",?$suffix=true){?if(function_exists("mb_substr"))?$slice=mb_substr($str,?$start,?$length,?$charset);?elseif(function_exists(''iconv_substr'')){?$slice=iconv_substr($str,$start,$length,$charset);?if(false===?$slice){?$slice=?'''';?}?}else{?$re[''utf-8'']??=?"/[\x01-\x7f]|[\xc2-\xdf][\x80-\xbf]|[\xe0-\xef][\x80-\xbf]{2}|[\xf0-\xff][\x80-\xbf]{3}/";?$re[''gb2312'']=?"/[\x01-\x7f]|[\xb0-\xf7][\xa0-\xfe]/";?$re[''gbk'']???=?"/[\x01-\x7f]|[\x81-\xfe][\x40-\xfe]/";?$re[''big5'']??=?"/[\x01-\x7f]|[\x81-\xfe]([\x40-\x7e]|\xa1-\xfe])/";?preg_match_all($re[$charset],?$str,?$match);?$slice=join("",array_slice($match[0],?$start,?$length));?}?return$suffix??$slice.''...'':?$slice;}由于文章篇幅问题,更多的问题,这里不再细说。还是那句话,有任何问题,欢迎指出。 |
|