php中怎么比较两段话、两个文本、两篇文章的相似性或相关性

php中怎么比较两段话、两个文本、两篇文章的相似性或相关性

给定两个字符串如何判断它们的相似程度？常用的有两种方法：
编辑距离（edit distance）
最长公共子序列（LCS，longest common sequence）
解释两个概念：
编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括：(1)将一个字符替换成另一个字符，(2)插入一个字符，(3)删除一个字符。
相似度，等于“编辑距离+1”的倒数。

最长公共子序列 一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。

一开始，我看到编辑距离的代码时，差点以为就是最长公共子序列。后来才发现两者不太一样。
下面就递推公式进行解释，f[i][j]表示a[0:i]和b[0:j]两个串进行比较所得的结果。

最长公共子序列
a[i]==b[j]时，f[i][j]=f[i-1][j-1]+1
a[i]!=b[j]时，f[i][j]=max(f[i-1][j],f[i][j-1])

编辑距离
a[i]==b[j]时，f[i][j]=f[i-1][j-1]
意思是，当a[i]==b[j]时，无需进行编辑操作
a[i]!=b[j]时，需要进行编辑操作，这是编辑可以从三种操作中进行选择：插入、删除、修改
细分之，又可得到6种操作：
在a[i]前面插入b[j]，f[i][j]=f[i-1][j]+1
在b[j]前面插入a[i]，f[i][j]=f[i][j-1]+1
删除a[i]，f[i][j]=f[i-1][j]+1
删除b[j]，f[i][j]=f[i][j-1]+1
修改a[i],使之等于b[j]，f[i][j]=f[i-1][j-1]+1
修改b[j]，使之等于a[i]，f[i][j]=f[i-1][j-1]+1
显然,操作虽然是6种，但是结果却只有三种。
如果选择插入操作，在a[i]前面插入一个字符b[j]。那么a[0:i-1]和b[0:j]字符都相同需要的编辑次数为f[i-1][j]，所以f[i][j]=f[i-1][j]+1
如果选择删除操作，把a[i]这个字符删除，这样一来b[j]就不用跟a[i]进行比较了。那么a[0:i]和b[0:j-1]字符都相同，需要的编辑次数是f[i][j-1]，所以f[i][j]=f[i][j-1]+1
如果选择修改操作，把a[i]改成b[j]，那么a[0:i-1]和b[0:j-1]部分比较次数为f[i-1][j-1]，所以f[i][j]=f[i-1][j-1]+1
因为需要编辑次数尽量少，所以f[i][j]会从以上三种可行操作中选择一种花费最少的。
也就是说，f[i][j]=min(f[i-1][j],f[i][j-1],f[i-1][j-1])+1
显然，把上述在a中插入改为在b中插入、在a中删除改为在b中删除，所得到的递推式是一样的。

php中有个函数是比较文本相似性的，叫similar_text

<?php
similar_text("php防范sql攻击","php防止sql攻击", $percent);
echo $percent;

网上有个大牛写了个lcs的相关性检测，还不错

<?php 
class LCS {
    var $str1;
    var $str2;
    var $c = array();
    /*返回串一和串二的最长公共子序列
*/
    function getLCS($str1, $str2, $len1 = 0, $len2 = 0) {
        $this->str1 = $str1;
        $this->str2 = $str2;
        if ($len1 == 0) $len1 = strlen($str1);
        if ($len2 == 0) $len2 = strlen($str2);
        $this->initC($len1, $len2);
        return $this->printLCS($this->c, $len1 - 1, $len2 - 1);
    }
    /*返回两个串的相似度
*/
    function getSimilar($str1, $str2) {
        $len1 = strlen($str1);
        $len2 = strlen($str2);
        $len = strlen($this->getLCS($str1, $str2, $len1, $len2));
        return $len * 2 / ($len1 + $len2);
    }
    function initC($len1, $len2) {
        for ($i = 0; $i < $len1; $i++) $this->c[$i][0] = 0;
        for ($j = 0; $j < $len2; $j++) $this->c[0][$j] = 0;
        for ($i = 1; $i < $len1; $i++) {
            for ($j = 1; $j < $len2; $j++) {
                if ($this->str1[$i] == $this->str2[$j]) {
                    $this->c[$i][$j] = $this->c[$i - 1][$j - 1] + 1;
                } else if ($this->c[$i - 1][$j] >= $this->c[$i][$j - 1]) {
                    $this->c[$i][$j] = $this->c[$i - 1][$j];
                } else {
                    $this->c[$i][$j] = $this->c[$i][$j - 1];
                }
            }
        }
    }
    function printLCS($c, $i, $j) {
        if ($i == 0 || $j == 0) {
            if ($this->str1[$i] == $this->str2[$j]) return $this->str2[$j];
            else return "";
        }
        if ($this->str1[$i] == $this->str2[$j]) {
            return $this->printLCS($this->c, $i - 1, $j - 1).$this->str2[$j];
        } else if ($this->c[$i - 1][$j] >= $this->c[$i][$j - 1]) {
            return $this->printLCS($this->c, $i - 1, $j);
        } else {
            return $this->printLCS($this->c, $i, $j - 1);
        }
    }
} 

$lcs = new LCS();
//返回最长公共子序列
$lcs->getLCS("hello word","hello china");
//返回相似度
echo $lcs->getSimilar("php 防范sql攻击","php 防止sql攻击与注入");