Myluzh Blog

PHP比较两篇文章相似度的查重算法

发布时间: 2020-3-30 文章作者: myluzh 分类名称: PHP 朗读文章

可以计算两个字符串之间最长公共子序列或者相似度，但是比较吃内存。
复制代码
  1. <?php
  2. class LCS {
  3.     var $str1;
  4.     var $str2;
  5.     var $c = array();
  6.     /*返回串一和串二的最长公共子序列
  7. */
  8.     function getLCS($str1, $str2, $len1 = 0, $len2 = 0) {
  9.         $this->str1 = $str1;
  10.         $this->str2 = $str2;
  11.         if ($len1 == 0) $len1 = strlen($str1);
  12.         if ($len2 == 0) $len2 = strlen($str2);
  13.         $this->initC($len1, $len2);
  14.         return $this->printLCS($this->c, $len1 - 1, $len2 - 1);
  15.     }
  16.     /*返回两个串的相似度
  17. */
  18.     function getSimilar($str1, $str2) {
  19.         $len1 = strlen($str1);
  20.         $len2 = strlen($str2);
  21.         $len = strlen($this->getLCS($str1, $str2, $len1, $len2));
  22.         return $len * 2 / ($len1 + $len2);
  23.     }
  24.     function initC($len1, $len2) {
  25.         for ($i = 0; $i < $len1; $i++) $this->c[$i][0] = 0;
  26.         for ($j = 0; $j < $len2; $j++) $this->c[0][$j] = 0;
  27.         for ($i = 1; $i < $len1; $i++) {
  28.             for ($j = 1; $j < $len2; $j++) {
  29.                 if ($this->str1[$i] == $this->str2[$j]) {
  30.                     $this->c[$i][$j] = $this->c[$i - 1][$j - 1] + 1;
  31.                 } else if ($this->c[$i - 1][$j] >= $this->c[$i][$j - 1]) {
  32.                     $this->c[$i][$j] = $this->c[$i - 1][$j];
  33.                 } else {
  34.                     $this->c[$i][$j] = $this->c[$i][$j - 1];
  35.                 }
  36.             }
  37.         }
  38.     }
  39.     function printLCS($c, $i, $j) {
  40.         if ($i == 0 || $j == 0) {
  41.             if ($this->str1[$i] == $this->str2[$j]) return $this->str2[$j];
  42.             else return "";
  43.         }
  44.         if ($this->str1[$i] == $this->str2[$j]) {
  45.             return $this->printLCS($this->c, $i - 1, $j - 1).$this->str2[$j];
  46.         } else if ($this->c[$i - 1][$j] >= $this->c[$i][$j - 1]) {
  47.             return $this->printLCS($this->c, $i - 1, $j);
  48.         } else {
  49.             return $this->printLCS($this->c, $i, $j - 1);
  50.         }
  51.     }
  52. } 
  53. $lcs = new LCS();
  54.  
  55. //返回最长公共子序列
  56. //echo $lcs->getLCS("hello word","hello china");
  57.  
  58. //返回相似度
  59. //echo $lcs->getSimilar("hello word","hello china");

标签: php 算法

正文到此结束
版权声明：若无特殊注明，本文皆为 Myluzh Blog 原创，转载请保留文章出处。
文章内容：https://itho.cn/php/55.html
文章标题：《PHP比较两篇文章相似度的查重算法》
« PHP删除文件夹以及文件夹下的所有文件 | ThinkPHP 5.x (v5.0.23及v5.1.31以下版本) 远程命令执行漏洞利用»

发表评论