首页所有驱动分类下载数据挖掘与人工智能搜索引擎与SEO技术备忘录站长随笔

用交集与并集的方法,计算字符串的相似度

2020-02-03 字符串相似度 浏览次数:123
 
使用场景:在一些特定环境下,要求保持语句里的文字顺序不变,计算语句之间的相似度。

原理:利用滑动的方式,选任意一个字符串作为固定方,另一个字符串作为滑动方,向某一方向滑动,以字节为单位(也可以根据实际需要,以词或字为单位),每滑动一个单位,就计算两个字符串的相似值(公式:相似值 = 交集 / 并集),得到的比例值就是相似度,然后选出最高的相似值的作为结果。

例子,要对下面两个字符串计算相似度,滑动单位是:字节。

字符串A的长度是15,扮演固定方:www.mypcrun.com
字符串B的长度是11,扮演滑动方:mypcrun.com

开始将字符串B向右滑动1位,没有交集,如下图:



将字符串B向右滑动2位,还是没有交集,如下图:



将字符串B向右滑动3位,仍然没有交集,如下图:



当字符串B不停的向右滑动时,将会得到跟下面一些图一样的情况,红色字体部分,就是在同一位置上相同的数据(字符),这就是交集:



上图有1个字符(交集),这时的并集为(15 + 11 – 1 = 25个字符),相似度为:1 / 25 = 0.04



上图一共有11个字符(交集),这时的并集为(15 + 11 – 11 = 15个字符),相似度为:11 / 15 = 0.73

经过多轮位移,最终得到多个结果,但是最高值为0.73,所以选择这个作为最终值,字符串A和字符串B的相似度就是73%

利用这种方法,可以将单词组或单个字看作一个单元,进行滑动对比,在一些特定的场合下,还是可以利用的。

不想写C代码了,用PHP写代码如下:

// 用交集和并集的比例,比较两个字符串的相似度
function CmpStrChar($str1,$str2)
{
$intResult=0;

$T=0;
while ($T < 2){

if ($T==1){
// 第二轮交换位置
$strTmp=$str1;
$str1=$str2;
$str2=$strTmp;
}

// 最大相同数
$SameCount=0;

$str1Len=strlen($str1);
$str2Len=strlen($str2);
$N=0;
while ($N < $str2Len){
$L=$str2Len-$N;
$strCmp=substr($str2,$N,$L);
$strCmpLen=strlen($strCmp);

// 本次相同数
$S=0;
$P=0;
while ( ($P < $strCmpLen) && ($P < $str1Len) ){
$sChar1=substr($str1,$P,1);
$sChar2=substr($strCmp,$P,1);
$dChar1=ord($sChar1);
$dChar2=ord($sChar2);

// 加这两句主要是为了不区分大小写
if ( ($dChar1 >= 97) && ($dChar1 <= 122) ) $dChar1=$dChar1 - 32;
if ( ($dChar2 >= 97) && ($dChar2 <= 122) ) $dChar2=$dChar2 - 32;

if ($dChar1===$dChar2) $S++;
$P++;
}

// 比例=交集 除以 并集
$U=$str1Len+$str2Len-$S;
$B=round($S/$U,2) * 100;
if ($B > $SameCount) $SameCount=$B;

$N++;
}

if ($SameCount > $intResult) $intResult=$SameCount;

$T++;
}

return $intResult;
}



// 以单词的形式来比较两个字符串的相似性,连续读取字符串,遇到空格,回车,换行,TAB键,即看作一个单词
function CmpStrWord($str1,$str2)
{
$intResult=0;

// 此函数默认区分大小写,但如果不想这个函数区分大小写,在处理字符串之前,统一变成小写

$T=0;
while ($T < 2){

if ($T==1){
// 第二轮交换位置
$strTmp=$str1;
$str1=$str2;
$str2=$strTmp;
}

$aryWord1=array();
$aryWord1Count=0;
$str1Len=strlen($str1);
$N=0;
$strWord='';
$strWordLen=0;
while ($N < $str1Len){
$sChar=substr($str1,$N,1);
$dChar=ord($sChar);
if ( ($dChar==9) || ($dChar==10) || ($dChar==13) || ($dChar==32) ){
if ($strWordLen > 0) $aryWord1[$aryWord1Count++]=$strWord;
$strWord='';
$strWordLen=0;
}
else{
$strWord.=$sChar;
$strWordLen++;
}
$N++;
}
if ($strWordLen > 0) $aryWord1[$aryWord1Count++]=$strWord;

$aryWord2=array();
$aryWord2Count=0;
$str2Len=strlen($str2);
$N=0;
$strWord='';
$strWordLen=0;
while ($N < $str2Len){
$sChar=substr($str2,$N,1);
$dChar=ord($sChar);
if ( ($dChar==9) || ($dChar==10) || ($dChar==13) || ($dChar==32) ){
if ($strWordLen > 0) $aryWord2[$aryWord2Count++]=$strWord;
$strWord='';
$strWordLen=0;
}
else{
$strWord.=$sChar;
$strWordLen++;
}
$N++;
}
if ($strWordLen > 0) $aryWord2[$aryWord2Count++]=$strWord;

// 最大相同数
$SameCount=0;
$N=0;
while ($N < $aryWord2Count){
$S=0;
$P1=0;
$P2=$N;
while ( ($P2 < $aryWord2Count) && ($P1 < $aryWord1Count) ){
$sChar1=$aryWord1[$P1];
$sChar2=$aryWord2[$P2];
$sChar1Len=strlen($sChar1);
$sChar2Len=strlen($sChar2);
if ($sChar1Len===$sChar2Len)
if (strncmp($sChar1,$sChar2,$sChar2Len) === 0) $S++;
$P1++;
$P2++;
}

// 比例=交集 除以 并集
$U=$aryWord1Count+$aryWord2Count-$S;
$B=round($S/$U,2) * 100;
if ($B > $SameCount) $SameCount=$B;

$N++;
}

if ($SameCount > $intResult) $intResult=$SameCount;

unset($aryWord2);
unset($aryWord1);

$T++;
}

return $intResult;
}
留言

有啥想说的就说吧,有啥想问的就问吧
Good good study, day day up!

名称

Email

内容

预览(只读), 点击返回编辑.

 
最新文章
 
留言
版权所有 © 2020 mypcrun.com.
桂ICP备19002156号桂公网安备 45070202000667号
这回把网站设计得那么漂亮,这下子不会被人笑了吧。