更多内容查看公众号:写PHP的老王

PCA主成分分析

21 Feb 2019 Category: 算法

主成分分析(Principal components analysis,PCA) 是数据降维最重要的方法之一。主要通过找出数据的主要成分，替代原有数据。减少后续数据处理的维度。

PCA 主成分分析主要是找到一个超平面，使得原数据距离超平面尽可能的进，数据在超平面上的投影尽可能的远。如果找到这么一个超平面，则是有这个超平面坐标系表示原有数据。（变换后的维度一般提前给定，小于原有数据维度）

查看更多

SVD分解算法

20 Feb 2019 Category: 算法

奇异值分解(Singular Value Decomposition，以下简称SVD)之前接触还是在老师的课本里…。最近在看nlp相关概念知识，里面有写算法是基于svd分解的。因此重新查找资料学习svd分解。它不光可以用于降维算法中的特征分解，还可以用于推荐系统，以及自然语言处理等领域。是很多机器学习算法的基石。

特征值分解

如果 $A_{n \times n}x_{n \times 1}=\lambda x_{n \times 1}$ 则称 $\lambda$ 是矩阵 $A$的特征值，向量$x$叫做特征向量。

我们求出了矩阵A的n个特征值λ1≤λ2≤…≤λn,以及这n个特征值所对应的特征向量{w1,w2,…wn}，，如果这n个特征向量线性无关，那么矩阵A就可以用下式的特征分解表示：

其中W是这n个特征向量所张成的n×n维矩阵，而Σ为这n个特征值为主对角线的n×n维矩阵

般我们会把W的这n个特征向量标准化，即满足$\parallel w_i \parallel_2=1$, 或者说$w_i^T w_i=1$，此时W的n个特征向量为标准正交基，满足$W^T W = I $，即$W^T=W^-1$, 也就是说$W$为酉矩阵。

特征值分解只能对方阵进行分解。那么对于非方阵则需要进行SVD分解。

svd分解

对于矩阵$A_{m \times n}$ ，则它的SVD分解定义为:

其中$U$是一个$m \times m$的矩阵，$\Sigma$是一个$m \times m$的矩阵，除了主对角线上的元素以外全为0，主对角线上的每个元素都称为奇异值，$V$是一个$n\times n$的矩阵。$U$和$V$都是酉矩阵，即满足$U^T U=I$,$V^T V=I$

所以$V$是$A_{m \times n}^T A_{m \times n}$的特征值分解矩阵

同理有$U$是$A_{m \times n} A_{m \times n}^T$的特征值分解矩阵

由于$\Sigma$只有主对角线非0，所以主对角线上的元素$\delta_i=\sqrt{\lambda_i}$ 其中$\lambda_i$是$A_{m \times n}^T A_{m \times n}$的特征值。

查看更多

PHP 字符串填充str_pad函数有什么不知道的

20 Feb 2019 Category: php

str_pad — 使用另一个字符串填充字符串为指定长度


str_pad ( string $input , int $pad_length [, string $pad_string = " " [, int $pad_type = STR_PAD_RIGHT ]] ) : string

该函数返回 input 被从左端、右端或者同时两端被填充到制定长度后的结果。

如果可选的 pad_string 参数没有被指定，input 将被空格字符填充，否则它将被 pad_string 填充到指定长度。

可选的 pad_type 参数的可能值为 STR_PAD_RIGHT，STR_PAD_LEFT 或 STR_PAD_BOTH。如果没有指定 pad_type，则假定它是 STR_PAD_RIGHT。

以上是文档上的说明。

那么对于以下这些情况，内部怎么处理，会得到什么样的结果呢？

1、input长度比pad_length长度大

2、pad_length给负数的时候,给0的时候呢

3、pad_string给空字符串的时候呢

4、可以填充的最大长度是什么，有没有限制

5、两边填充，给定pad_length，左边填充多少，右边填充多少

查看更多

PHP 字符串分割成数组函数explode,str_split 内部实现

15 Feb 2019 Category: php

将一个字符串分割成数组在日常开发中的应用应该是很多的。如果指定分割符，可以使用explode，如果没有分割符，可以使用split实现。 那么两个函数内部如何实现，有什么不同呢？

查看更多

PHP内部如何实现打乱字符串顺序函数str_shuffle

12 Feb 2019 Category: php

2019年春节已过，今天是上班第一天，还得翻一翻之前没有看完的PHP源码。

今天聊的是字符串顺序打乱函数str_shuffle。这个函数本身使用频率并不高。但是，其内部实现还是非常有趣的。

查看更多

简单聊聊字符串的翻转问题

29 Jan 2019 Category: php

字符串的翻转在日常开发使用程度比较少，但是面试过程中却是常有的。最近看php 源码中strrev，因此写一篇文记录对字符串翻转问题的一些学习。

查看更多

用php实现大小写转换功能

29 Jan 2019 Category: php

字符串的大小写转换功能在日常中经常使用。那么如何实现一个简单的大小写转换功能呢?

在php中，最终使用的是c语言的toupper,tolower函数将字符进行大小写转换。因此需要定义一个字符大小写转换的函数。

//字符转大写
protected function toupper($c){
 $ord = ord($c);
 return $ord>=97 && $ord<=122 ?chr($ord-32):$c;
}
//字符转小写
protected function tolower($c){
 $ord = ord($c);
 return $ord>=65 && $ord<=90 ?chr($ord+32):$c;
}

字符的大小写转换就是进行ascii码的转换。A-Z的ASCII码在65-90之间。a-z的ASCII码在97-122之间。对于不在转换区间的字符，应该原样返回

php中字符串大小写转换有下面几个函数strtolower,strtoupper, lcfirst,ucfirst,ucwords,lcfirst, 这几个函数都是成对的，因此仅以大写转小写为例说明如何实现这几个函数

strtoupper实现字符串从大写转小写。无非是遍历字符串的每个字符，将大写字符转换成小写。

public function strtolower($str){
 if($this->checkempty($str))
 {
  return "";
 }
 $len = strlen($str);
 for($i=0;$i<$len;$i++){
  $str[$i] = $this->tolower($str[$i]);
 }
 return $str;
}

php字符串可以像数组一样用下标获取每个字符。因此对字符串每个字符遍历，转换成小写字符即可

lcfirst实现首字母大写的功能，因此比strtolower还要简单

public function ucfirst($str){
 if($this->checkempty($str))
 {
  return "";
 }
 $str[0] = $this->toupper($str[0]);
 return $str;
}

lcwords 实现单词首字母转小写。说单词，其实是空格后面第一个字符。因此只需要在遍历到空格字符后面第一个非空字符串转换成小写即可。

public function lcwords($str){
 if($this->checkempty($str))
 {
  return "";
 }
 $splitchar = [' ',"\n","\r","\f","\v"];
 $len = strlen($str);
 for($i=0;$i<$len;$i++){
  if(in_array($str[$i], $splitchar))
  {
   $i++;
   if($i>=$len)
   {
    break;
   }
   $str[$i] = $this->tolower($str[$i]);
  }
 }
 return $str;
}

主要要小心越界的问题。如果最后一个字符串是空字符。

至于为什么单词分割字符是代码中的那几项，主要是php源码就是根据那几项实现的。php源码中ucwords实现方式如下:

PHP_FUNCTION(ucwords)
{
 zend_string *str;
 char *delims = " \t\r\n\f\v";
 register char *r, *r_end;
 size_t delims_len = 6;
 char mask[256];

 ZEND_PARSE_PARAMETERS_START(1, 2)
  Z_PARAM_STR(str)
  Z_PARAM_OPTIONAL
  Z_PARAM_STRING(delims, delims_len)
 ZEND_PARSE_PARAMETERS_END();

 if (!ZSTR_LEN(str)) {
  RETURN_EMPTY_STRING();
 }
 php_charmask((unsigned char *)delims, delims_len, mask);

 ZVAL_STRINGL(return_value, ZSTR_VAL(str), ZSTR_LEN(str));
 r = Z_STRVAL_P(return_value);

 *r = toupper((unsigned char) *r);
 for (r_end = r + Z_STRLEN_P(return_value) - 1; r < r_end; ) {
  if (mask[(unsigned char)*r++]) {
   *r = toupper((unsigned char) *r);
  }
 }
}

将分割的字符串放入一个mask中，在遍历字符串的过程中判断是否是mask的字符。如果是则对后面一位字符进行大写转换操作。

代码地址https://github.com/froyot/froyot.github.io/blob/master/code/php_stringchange.php

查看更多

php 中的similar_text如何实现的

25 Jan 2019 Category: php

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

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

两个字符串的相似程度计算依据 Programming Classics: Implementing the World’s Best Algorithms by Oliver (ISBN 0-131-00413-1) 的描述进行。注意该实现没有使用 Oliver 虚拟码中的堆栈，但是却进行了递归调用，这个做法可能会导致整个过程变慢或变快。也请注意，该算法的复杂度是 O(N**3)，N 是最长字符串的长度。

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

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


sim = php_similar_char(ZSTR_VAL(t1), ZSTR_LEN(t1), ZSTR_VAL(t2), ZSTR_LEN(t2));

if (ac > 2) {
  Z_DVAL_P(percent) = sim * 200.0 / (ZSTR_LEN(t1) + ZSTR_LEN(t2));
}
RETURN_LONG(sim);

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


static void php_similar_str(const char *txt1, size_t len1, const char *txt2, size_t len2, size_t *pos1, size_t *pos2, size_t *max)
{
  char *p, *q;
  char *end1 = (char *) txt1 + len1;
  char *end2 = (char *) txt2 + len2;
  size_t 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内部跑了三个嵌套的循环，这就难怪文档中描述的，时间复杂度是O(N**3)。在最里面的循环中，检查两个字符串连续一致的个数。最里层循环结束之后，判断是否大于已经获取到的最大相似数目。并记录最大相似情况下两个字符串相似处开始的位置。

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

static size_t php_similar_char(const char *txt1, size_t len1, const char *txt2, size_t len2)
{
  size_t sum;
  size_t pos1 = 0, pos2 = 0, 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;
}

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

查看更多