标签归档：PHP源码

PHP的相似度计算函数：levenshtein

发表回复

在之前的文章 << PHP中计算字符串相似度的函数 >>中我们介绍了similar_text函数的使用及实现过程。similar_text() 函数主要是用来计算两个字符串的匹配字符的数目，也可以计算两个字符串的相似度（以百分比计）。与 similar_text() 函数相比，我们今天要介绍的 levenshtein() 函数更快。不过，similar_text() 函数能通过更少的必需修改次数提供更精确的结果。在追求速度而少精确度，并且字符串长度有限时可以考虑使用 levenshtein() 函数。

使用说明

先看手册上 levenshtein() 函数的说明：

levenshtein() 函数返回两个字符串之间的 Levenshtein 距离。

Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

例如把 kitten 转换为 sitting：

sitten （k→s）
sittin （e→i）
sitting （→g）

levenshtein() 函数给每个操作（替换、插入和删除）相同的权重。不过，您可以通过设置可选的 insert、replace、delete 参数，来定义每个操作的代价。

语法：

levenshtein(string1,string2,insert,replace,delete)

参数 描述

  • string1 必需。要对比的第一个字符串。
  • string2 必需。要对比的第二个字符串。
  • insert 可选。插入一个字符的代价。默认是 1。
  • replace 可选。替换一个字符的代价。默认是 1。
  • delete 可选。删除一个字符的代价。默认是 1。

提示和注释

  • 如果其中一个字符串超过 255 个字符，levenshtein() 函数返回 -1。
  • levenshtein() 函数对大小写不敏感。
  • levenshtein() 函数比 similar_text() 函数更快。不过，similar_text() 函数提供需要更少修改的更精确的结果。

例子

<?php
    echo levenshtein("Hello World","ello World");
    echo "<br />";
    echo levenshtein("Hello World","ello World",10,20,30);
    ?>

输出： 1 30

源码分析

levenshtein() 属于标准函数，在/ext/standard/目录下有专门针对此函数实现的文件：levenshtein.c。

levenshtein()会根据参数个数选择实现方式，针对参数为2和参数为5的情况，都会调用 reference_levdist() 函数计算距离。其不同在于对后三个参数，参数为2时，使用默认值1。

并且在实现源码中我们发现了一个在文档中没有说明的情况： levenshtein() 函数还可以传递三个参数，其最终会调用 custom_levdist() 函数。它将第三个参数作为自定义函数的实现，其调用示例如下：

 echo levenshtein("Hello World","ello World", 'strsub');

执行会报Warning： The general Levenshtein support is not there yet。这是因为现在这个方法还没有实现，仅仅是放了一个坑在那。

reference_levdist() 函数的实现算法是一个经典的DP问题。

给定两个字符串x和y，求最少的修改次数将x变成y。修改的规则只能是如下三种之一：删除、插入、改变。
用a[i][j]表示把x的前i个字符变成y的前j个字符所需的最少操作次数，则状态转移方程为：

当x[i]==y[j]时：a[i][j]  = min(a[i-1][j-1], a[i-1][j]+1, a[i][j-1]+1);
当x[i]!=y[j]时：a[i][j] =  min(a[i-1][j-1], a[i-1][j], a[i][j-1])+1;

在用状态转移方程前，我们需要初始化(n+1)(m+1)的矩阵d，并让第一行和列的值从0开始增长。 扫描两字符串（nm级的），对比字符，使用状态转移方程，最终$a[$l1][$l2]为其结果。

简单实现过程如下：

<?PHP
    $s1 = "abcdd";
    $l1 = strlen($s1);
    $s2 = "aabbd";
    $l2 = strlen($s2);
 
 
    for ($i = 0; $i < $l1; $i++) {
        $a[0][$i + 1] = $i + 1;
    }
    for ($i = 0; $i < $l2; $i++) {
        $a[$i + 1][0] = $i + 1;
    }
 
    for ($i = 0; $i < $l2; $i++) {
        for ($j = 0; $j < $l1; $j++) {
            if ($s2[$i] == $s1[$j]) {
                $a[$i + 1][$j + 1] = min($a[$i][$j], $a[$i][$j + 1] + 1, $a[$i + 1][$j] + 1);
            }else{
                $a[$i + 1][$j + 1] = min($a[$i][$j], $a[$i][$j + 1], $a[$i + 1][$j]) + 1;
            }
        }
    }
 
    echo $a[$l1][$l2];
    echo "\n";
    echo levenshtein($s1, $s2);

在PHP的实现中，实现者在注释中很清楚的标明：此函数仅优化了内存使用，而没有考虑速度，从其实现算法看，时间复杂度为O(m×n)。其优化点在于将上面的状态转移方程中的二维数组变成了两个一组数组。简单实现如下：

<?PHP
    $s1 = "abcjfdkslfdd";
    $l1 = strlen($s1);
    $s2 = "aab84093840932bd";
    $l2 = strlen($s2);
 
    $dis = 0;
    for ($i = 0; $i <= $l2; $i++){
        $p1[$i] = $i;
    }
 
    for ($i = 0; $i < $l1; $i++){
        $p2[0] = $p1[0] + 1;
 
        for ($j = 0; $j < $l2; $j++){
            if ($s1[$i] == $s2[$j]){
                $dis = min($p1[$j], $p1[$j + 1] + 1, $p2[$j] + 1);
            }else{
                $dis = min($p1[$j] + 1, $p1[$j + 1] + 1, $p2[$j] + 1);  // 注意这里最后一个参数为$p2  
            }
            $p2[$j + 1] = $dis;
        }
        $tmp = $p1;
        $p1 = $p2;
        $p2 = $tmp;  
    }
 
    echo "\n";
    echo $p1[$l2];
    echo "\n";
    echo levenshtein($s1, $s2);

如上为PHP内核开发者对前面经典DP的优化，其优化点在于不停的复用两个一维数组，一个记录上次的结果，一个记录这一次的结果。如果按照PHP的参数，分别给三个操作赋值不同的值，在上面的算法中将对应的1变成操作对应的值就可以了。 min函数的第一个参数对应的是修改，第二个参数对应的是删除，第三个参数对应的是添加。

Levenshtein distance说明

Levenshtein distance最先是由俄国科学家Vladimir Levenshtein在1965年发明，用他的名字命名。不会拼读，可以叫它edit distance（编辑距离）。Levenshtein distance可以用来：

  • Spell checking(拼写检查)
  • Speech recognition(语句识别)
  • DNA analysis(DNA分析)
  • Plagiarism detection(抄袭检测) LD用mn的矩阵存储距离值。

PHP内核中的异常基类

4条回复

PHP内核中的异常基类

在<<思考PHP语言三：异常处理>>中有说到异常的定义：异常处理是指在语言中能够使程序按照一种标准的方法对于某些运行时错误和其他程序所检测到的异常事件做出反应。异常发生的时间是不可以确定的，如果一种语言不包括异常处理机制，这就会给语言带来额外的复杂性。对于异常的处理有三种方案，而PHP5使用的是将一个异常处理独立出来，作为专门的子程序或类存在。

Exception是PHP中所有异常的基类，自从PHP5.1.0开始引入，自此，我们可以以面向对象的方式处理错误。 Exception类的声明如下：

 
 Exception {
        /* 属性 */
        protected string $message ;
        protected int $code ;
        protected string $file ;
        protected int $line ;
 
        /* 方法 */
        public __construct ([ string $message = "" [, int $code = 0 [, Exception $previous = NULL ]]] )
        final public string getMessage ( void )
        final public Exception getPrevious ( void )
        final public int getCode ( void )
        final public string getFile ( void )
        final public int getLine ( void )
        final public array getTrace ( void )
        final public string getTraceAsString ( void )
        public string __toString ( void )
        final private void __clone ( void )
    }

其中message表示异常消息内容，code表示异常代码，file表示抛出异常的文件名，line表示抛出异常在该文件中的行号。下面从 PHP内核的角度说明这些属性及对应的方法。

message表示异常的消息内容，其对应getMessage方法。message是自定义的异常消息，默认为空字符串。对于PHP内核来说，创建Exception对象时，有无message参数会影响 getMessage方法的返回值，以及显示异常时是否有with message %s等字样。message成员变量的作用是为了让用户更好的定义说明异常类。

code表示异常代码，其对应getCode方法。和meesage成员变量一样，code也是用户自定义的内容，默认为0。

file表示抛出异常的文件名，其对应getFile方法，返回值为执行文件的文件名，在PHP内核中存储此文件名的字段为 EG(active_op_array)->filename 此字段的值在生成一个opcode列表时，PHP的内核会将此前正在编译文件的文件名赋值给opcode的filename属性，如生成一个函数的op_array，在初始化op_array时，会执行上面所说的赋值操作，这里的赋值是通过编译的全局变量来传递的。当代码执行时，EG(active_op_array)表示正在执行的opcode列表。

line表示抛出异常在该文件中的行号，其对应getLine方法，返回整数，即EG(opline_ptr)->lineno。对于每条PHP脚本生成的opcode，在编译时都会执行一次初始化操作，在这次初始化操作中，PHP内核会将当前正在编译的行号赋值给opcode的lineno属性。 EG(opline_ptr)是PHP内核执行的当前opcode，抛出异常时对应的行号即为此对象的lineno属性。

除了上面四个属性，异常类还包括一个非常重要的内容：异常的追踪信息。在异常类中，通过getTrace方法可以获取这些信息。此方法的作用相当于PHP的内置函数debug_backtrace。在代码实现层面他们最终都是调用zend_fetch_debug_backtrace函数。在此函数中通过回溯PHP的调用栈，返回代码追踪信息。与getTrace方法对应还有一个返回被串化值的方法getTraceAsString，以字符串替代数组返回异常追踪信息。

在构造函数中，从PHP5.3.0增加$previous参数，表示异常链中的前一个异常。在catch块中可以抛出一个新的异常，并引用原始的异常，为调试提供更多的信息。

PHP脚本运行超时管理机制

2条回复

PHP脚本运行超时管理机制

在我们平常的开发中，也许曾经都遇到过PHP脚本运行超时的情况，此时PHP会显示错误说： “Fatal error: Maximum execution time of XXX seconds exceeded in XXX”，并终止脚本的运行。当遇到这种情况我们经常会通过使用 set_time_limit（非安全模式），或修改配置文件并重启服务器，或者修改程序减少程序的执行时间，使其在允许的范围之内，以解决此问题。但是，这些都是在应用层上我们可以看到的的表象，在PHP内核中有一套这样的机制支撑这样一个表象。

这是PHP为防止某些业务脚本长时间执行而阻塞其它脚本的处理或耗尽服务器资源，从而实现的脚本运行的超时管理机制。其本质上是PHP通过针对不同的平台实现定时器，依赖运行时的超时全局变量（EG(timeout_seconds)）管理并控制定时器的运行。所有对脚本运行时长的管理，包括接口函数和配置文件对于最大运行时长的配置，最终都是通过管理超时全局变量并重启定时器来实现的。

初始化和超时配置项

在PHP内核的核心层文件/main/main.c文件中，定义了PHP的核心配置项以及每个配置项对应的on_modify方法。在模块初始化（php_module_startup）时，PHP内核会调用ini配置的注册函数，将定义的核心配置项添加到ini配置的指令集中，并且会调用每个配置项对应的on_modify方法。

用于定义脚本运行最长时间的max_execution_time配置项也是这些核心配置项的一员，它的默认值为30秒，对应的on_modify方法是OnUpdateTimeout。当注册这些核心配置项时，max_execution_time的on_modify方法将被调用，此时配置项的值将传递给超时全局变量:EG(timeout_seconds)，并通过zend_set_timeout方法启动定时器。

针对WIN平台和类unix平台，PHP内核实现了不同的定时器。 Win32平台的定时器是在WM_TIME的基础上封装了一个计时器。通过创建一个独立线程控制计时器，并创建一个消息环，WaitForSingleObject用来阻塞zend_init_timeout_thread 返回。当接收到WM_REGISTER_ZEND_TIMEOUT时开始计时，实际上此时计时的任务是SetTimer(timeout_window, wParam, lParam*1000, NULL); 系统会在 seconds *　1000 后发个 WM_TIMER，这个时候就结束计时，中间可以被 WM_UNREGISTER_ZEND_TIMEOUT 打断。

类unix平台使用Linux的API函数setitimer，指定SIGPROF信号为超时处理信号，对应超时处理函数zend_timeout，当发生超时时，会发送此信号并触发函数zend_timeout显示错误信息并中止程序。

如果需要取消定时器，Win平台通过PostThreadMessage发送WM_UNREGISTER_ZEND_TIMEOUT给线程即可，类unix平台会重置定时器的时长为0。

超时管理

超时机制的管理非常灵活，有三种修改运行时长的方法。

1、 修改配置项。默认情况下PHP脚本的最长运行时长为30s。如果需要调整此项，可以通过修改php.ini文件中的max_execution_time项并重启动服务器达到修改最长运行时长的目的。此种方法适用于最开始的默认配置修改，或在其它方法无效的情况下使用。

2、 使用set_time_limit接口函数。此函数的作用是设置脚本最大执行时间。当此函数被调用时，set_time_limit()会从零开始重新启动超时计数器。比如，每一次设置是5秒，待脚本运行4秒后，脚本中又设置了5秒，那么，脚本在超时之前可运行总共时间为10秒。如下脚本示例：

    <?php
    set_time_limit(5);
    for ($i = 0; $i < 4; $i++) {
        sleep(1);
        echo $i, "<br />";
    }
 
    set_time_limit(5);
 
    for ($i = 0; $i < 4; $i++) {
        sleep(1);
        echo $i, "<br />";
    }

如上的代码，程序会执行完两个循环，都输出0,1,2,3。如果我们注释掉中间的set_time_limit(5)，程序再运行一次，此时就会在第二个循环输出0后报错。

在安全模式下，无法通过set_time_limit和ini_set重新设置max_execution_time，只有关闭安全模式或改变php.ini中的时间限制才能达到修改此参数的目的。

3、 通过ini_set修改max_execution_time参数。

以上的三种方法，其实现过程基本类似，前一种是在初始化时调用on_modify指针函数。后两种在处理了参数后，调用zend_alter_ini_entry_ex函数，触发on_modify函数。于是，管理超时机制的所有操作最终都汇集到OnUpdateTimeout函数。在此函数中，通过zend_set_timeout重新设置脚本的超时时间。