作者归档:admin

PHP中计算字符串相似度的函数

上次reeze提到similar_text函数,这个真心没用过。
在手册上查找其说明如下:
similar_text — 计算两个字符串的相似度
int similar_text ( string $first , string $second [, float &$percent ] )
$first 必需。规定要比较的第一个字符串。
$second 必需。规定要比较的第二个字符串。
$percent 可选。规定供存储百分比相似度的变量名。

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

比如我们想找字符串abcdefg和字符串aeg的相似度:

$first = "abcdefg";
$second = "aeg";
 
echo similar_text($first, $second);

结果输出3.如果想以百分比显示,则可使用它的第三个参数,如下:

$first = "abcdefg";
$second = "aeg";
 
similar_text($first, $second, $percent);
echo $percent;

这里的相似度的算法是什么呢?本来是想看看Oliver[1993]对于这个算法的具体描述,各种google后,只找到这是从Ian Oliver1993年出版的书《Programming classics: implementing the world’s best algorithms》中记载,没有找到这本书的电子版。

直接代码,在string.c文件中我们找到了similar_text的实现PHP_FUNCTION(similar_text),其最终调用php_similar_cha获取两个字符串的相似度,如下代码:

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);
    if ((sum = max)) {
        if (pos1 && pos2) {
            sum += php_similar_char(txt1, pos1, txt2, pos2);
        }
        if ((pos1 + max < len1) && (pos2 + max < len2)) { 
             sum += php_similar_char(txt1 + pos1 + max, len1 - pos1 - max, 
                                               txt2 + pos2 + max, len2 - pos2 - max);
        }
    }
 
    return sum;
}

首先我们看php_similar_str函数的作用,从函数名和参数名我们可以大致猜测它的作用是求两个字符串的相似子串,具体代码如下:

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 < end1; p++) {
        for (q = (char *) txt2; q < end2; q++) {
            for (l = 0; (p + l < end1) && (q + l < end2) && (p[l] == q[l]); l++); //我是分号
            if (l > *max) {
                *max = l;
                *pos1 = p - txt1;
                *pos2 = q - txt2;
            }
        }
    }
}

真心很直白的三重循环,求两个字符串的最大相似子串的长度,以及这两个子串相等的开始位置。

在了解了php_similar_str的作用后,回到php_similar_char函数。这是一个很直白的二分算法。以当前两个字符串的最大相似子串的位置为分隔,向两边二分查找相似子串,最终得到所有的相似子串长度的总和,这也就是我们这个函数的相似度算法:从最长子串开始,依次统计所有的子串长度。

那么这里的百分比是如何计算的呢?

在PHP_FUNCTION(similar_text)的函数体中,如下代码:

sim = php_similar_char(t1, t1_len, t2, t2_len);
 
if (ac > 2) {
    Z_DVAL_PP(percent) = sim * 200.0 / (t1_len + t2_len);
}

sim是相似度的值,百分比是直接 sim * 200 / 两个字符串的长度。

关于那本书:

名称 Programming classics: implementing the world’s best algorithms
作者 Ian Oliver
出版商 Prentice Hall, 1993
出处: 密歇根大学
数字化处理时间 2007年11月15日
ISBN 0131004131, 9780131004139
页数 386 页
这里也许可以下载到

http://filecom.net/8EMrrcoyc8/

http://ebooks-files.org/download/programming-classics-implementing-the-worlds-best-algorithms.html

再读《程序员修炼之道》总结

虽然这本书的中文译名很文艺,但是内容确实值得一看,又花了一个星期的早晨将这本《程序员修炼之道》看了一遍,这次对于每个小节都写了些笔记和摘抄,也许是错的,也许没有什么道理,只是当时的感触和想到的。内容整理如下:

1、我的源码让猫给吃了: 责任、风险、应急备案、不要找借口,真诚

2、软件的熵:破窗户理论、酒与污水理论

3、石头汤与煮青蛙: 好的愿景和目标、不谋全局者不足以谋一域

4、足够好的软件:细化非功能性需求、过早优化是万恶之源

5、你的知识资产:养成学习的习惯,知识上的投资总能得到最好的回报

6、交流: 准备好你的交流

7、 重复的危害:DRY原则

8、正交性:高内聚,低耦合;模块化,组件化

9、可撤销性:良好的抽象接口让我们更灵活

10、曳光弹:让程序先跑起来

11、原型与便笺:为了学习,可看不可用。

12、领域语言: 语言会影响你思考问题的方式,合适的才是好的。

13、估算:估算会加深对需求的理解,

14、纯文本的威力:自描述,可读

15、shell游戏:GUI局限了用户的思维,但也提供了一些方便

16、强力编辑:选你所爱的,爱你所选的

17、源码控制:记住过去,人生要是有版本控制会是一个怎样的结果?

18、调试:调试是为了解决问题,心态很重要, 反思BUG产生的原因

19、 文本操纵:懂一门脚本语言

20、代码生成器:参数化模板,预处理,关注变化的地方

21、按合约设计: DBC,鸭子类型?找出业务规则并封装规则的变化

22、死程序不说谎: switch语句中的default子句的存在是为了让我们发现何时发生了不可能的事情,暴露错误,早崩溃

23、断言式编程:有选择的使用和开启

24、何时使用异常:将异常用于异常的问题

25、怎样配平资源: 处理资源要有始有终,尽量在分配的地方释放

26、 解耦与得墨忒耳法则:最少知识原则,不要和陌生人说话,对象的任何方法都应该只调用它自身、传入此方法的参数、它创建的对象以及它直接持有的组件

27、源程序设计:配置,将变化量放到元数据

28、时间耦合:并发的本质问题之一是时间

29、它只是视图:MVC

30、黑板:mediator模式

31、靠巧合编程: 知道你在做什么,把代码写扎实

32、算法速率:随时记得优化代码,优化要把握度

33、重构:习惯重构,自动测试是比较理想的状况

34、易于测试的代码: 测试文化,你和用户,总有一个人测

35、邪恶的向导:弄清楚向导干了什么

36、需求之坑:将商业策略与实际的需求分开, 问下为什么!需求是需要

37、解开不可能解开的谜题: 确定真正的约束所在

38、等你准备好:构建原型

39、规范陷阱:需求和规范都要有一些抽象,留一些空间

40、圆圈与箭头:取众家之长,形成自己的工作习惯

41、注重实效的团队:个人的原则也适用于团队

42、无处不在的自动化:让计算机去重复,它会比我们做得更好

43、无情的测试:早测试,道是无情却有情

44、全都是写:文档和代码同样重要

45、极大的期望:步子别跨太大,否则会扯到

46、傲慢欲偏见:署名,打上你的标记,树立你的品牌。

PHP执行过程中的数据

PHP脚本在内核中一般会经过词法解析,语法解析、编译生成中间代码,执行中间代码这样四个大的步骤。其中,第四个步骤,执行中间代码PHP内核默认情况下是通过zend/zend_vm_execute.h文件中的execute函数调用执行完成,对于所有的中间代码,默认实现是以按顺序执行,当遇到函数等情况时跳出去执行,执行完后再回到跳出的位置继续执行。

与过程相比,过程中的数据会更加重要,那么在执行过程中的核心数据结构有哪些呢? 在Zend/zend_vm_execute.h文件中的execute函数实现中,zend_execute_data类型的execute_data变量贯穿整个中间代码的执行过程, 其在调用时并没有直接使用execute_data,而是使用EX宏代替,其定义在Zend/zend_compile.h文件中,如下:

#define EX(element) execute_data.element

因此我们在execute函数或在opcode的实现函数中会看到EX(fbc),EX(object)等宏调用, 它们是调用函数局部变量execute_data的元素:execute_data.fbc和execute_data.object。 execute_data不仅仅只有fbc、object等元素,它包含了执行过程中的中间代码,上一次执行的函数,函数执行的当前作用域,类等信息。 其结构如下:

typedef struct _zend_execute_data zend_execute_data;
 
struct _zend_execute_data {
    struct _zend_op *opline;
    zend_function_state function_state;
    zend_function *fbc; /* Function Being Called */
    zend_class_entry *called_scope; 
    zend_op_array *op_array;  /* 当前执行的中间代码 */
    zval *object;
    union _temp_variable *Ts;
    zval ***CVs;
    HashTable *symbol_table; /* 符号表 */
    struct _zend_execute_data *prev_execute_data;   /* 前一条中间代码执行的环境*/
    zval *old_error_reporting;
    zend_bool nested;
    zval **original_return_value; /* */
    zend_class_entry *current_scope;
    zend_class_entry *current_called_scope;
    zval *current_this;
    zval *current_object;
    struct _zend_op *call_opline;
};

在前面的中间代码执行过程中有介绍:中间代码的执行最终是通过EX(opline)->handler(execute_data TSRMLS_CC)来调用最终的中间代码程序。 在这里会将主管中间代码执行的execute函数中初始化好的execture_data传递给执行程序。

zend_execute_data结构体部分字段说明如下:

  • opline字段:struct _zend_op类型,当前执行的中间代码
  • op_array字段: zend_op_array类型,当前执行的中间代码队列
  • fbc字段:zend_function类型,已调用的函数
    called_scope字段:zend_class_entry类型,当前调用对象作用域,常用操作是EX(called_scope) = Z_OBJCE_P(EX(object)), 即将刚刚调用的对象赋值给它。
  • symbol_table字段: 符号表,存放局部变量,这在前面的<< 第六节 变量的生命周期 » 变量的作用域 >>有过说明。 在execute_data初始时,EX(symbol_table) = EG(active_symbol_table);
  • prev_execute_data字段:前一条中间代码执行的中间数据,用于函数调用等操作的运行环境恢复。
    在execute函数中初始化时,会调用zend_vm_stack_alloc函数分配内存。 这是一个栈的分配操作,对于一段PHP代码的上下文环境,它存在于这样一个分配的空间作放置中间数据用,并作为栈顶元素。 当有其它上下文环境的切换(如函数调用),此时会有一个新的元素生成,上一个上下文环境会被新的元素压下去, 新的上下文环境所在的元素作为栈顶元素存在。

在zend_vm_stack_alloc函数中我们可以看到一些PHP内核中的优化。 比如在分配时,这里会存在一个最小分配单元,在zend_vm_stack_extend函数中, 分配的最小单位是ZEND_VM_STACK_PAGE_SIZE((64 * 1024) – 64),这样可以在一定范围内控制内存碎片的大小。 又比如判断栈元素是否为空,在PHP5.3.1之前版本(如5.3.0)是通过第四个元素elelments与top的位置比较来实现, 而从PHP5.3.1版本开始,struct _zend_vm_stack结构就没有第四个元素,直接通过在当前地址上增加整个结构体的长度与top的地址比较实现。 两个版本结构代码及比较代码如下:

// PHP5.3.0
struct _zend_vm_stack {
    void **top;
    void **end;
    zend_vm_stack prev;
    void *elements[1];
};
 
if (UNEXPECTED(EG(argument_stack)->top == EG(argument_stack)->elements)) {
}
 
//  PHP5.3.1
struct _zend_vm_stack {
    void **top;
    void **end;
    zend_vm_stack prev;
};
 
if (UNEXPECTED(EG(argument_stack)->top == ZEND_VM_STACK_ELEMETS(EG(argument_stack)))) {
}
 
#define ZEND_VM_STACK_ELEMETS(stack) \
((void**)(((char*)(stack)) + ZEND_MM_ALIGNED_SIZE(sizeof(struct _zend_vm_stack))))

当一个上下文环境结束其生命周期后,如果回收这段内存呢? 还是以函数为例,我们在前面的函数章节中<< 函数的返回 >>中我们知道每个函数都会有一个函数返回, 即使没有在函数的实现中定义,也会默认返回一个NULL。以ZEND_RETURN_SPEC_CONST_HANDLER实现为例, 在函数的返回最后都会调用一个函数zend_leave_helper_SPEC。

在zend_leave_helper_SPEC函数中,对于执行过程中的函数处理有几个关键点:

  • 上下文环境的切换:这里的关键代码是:EG(current_execute_data) = EX(prev_execute_data);。 EX(prev_execute_data)用于保留当前函数调用前的上下文环境,从而达到恢复和切换的目的。
  • 当前上下文环境所占用内存空间的释放:这里的关键代码是:zend_vm_stack_free(execute_data TSRMLS_CC);。 zend_vm_stack_free函数的实现存在于Zend/zend_execute.h文件,它的作用就是释放栈元素所占用的内存。
  • 返回到之前的中间代码执行路径中:这里的关键代码是:ZEND_VM_LEAVE();。 我们从zend_vm_execute.h文件的开始部分就知道ZEND_VM_LEAVE宏的效果是返回3。 在执行中间代码的while循环当中,当ret=3时,这个执行过程就会恢复之前上下文环境,继续执行。

更多内容请请移步TIPI项目