计算字符串相似度及寻找最相似字符串的代码

灰太狼 2022-10-02 15:56 243阅读 0赞

计算两个字符串的差异距离函数

///  <summary>   
 ///  计算两个字符串的差异距离  
 ///  </summary>   
 ///  <param name="source"> 来源字符串 </param>   
 ///  <param name="target"> 目标字符串 </param>   
 ///  <returns> 字符串差距 </returns>    
  public  int  CalcDistance( string  source,  string  target)  
\{  
 int  n  =  source.Length;  
 int  m  =  target.Length;  
 if  (m  ==  0 )  return  n;  
 if  (n  ==  0 )  return  m;  
var matrix  =  new  int \[n  \+  1 , m  \+  1 \];  
 for  ( int  i  =  1 ; i  <=  n; i \++ )  
\{  
matrix\[i,  0 \]  =  i;  
\}  
 for  ( int  i  =  1 ; i  <=  m; i \++ )  
\{  
matrix\[ 0 , i\]  =  i;  
\}  
  
 for  ( int  i  =  1 ; i  <=  n; i \++ )  
\{  
var si  =  source\[i  \-  1 \];  
 for  ( int  j  =  1 ; j  <=  m; j \++ )  
\{  
var tj  =  target\[j  \-  1 \];  
  
 int  cost;  
 if  (si  ==  tj)  
cost  =  0 ;  
 else   
cost  =  1 ;  
  
 int  above  =  matrix\[i  \-  1 , j\]  \+  1 ;  
 int  left  =  matrix\[i, j  \-  1 \]  \+  1 ;  
 int  diag  =  matrix\[i  \-  1 , j  \-  1 \]  \+  cost;  
matrix\[i, j\]  =  Math.Min(above, Math.Min(left, diag));  
\}  
\}  
 return  matrix\[n, m\];  
\}

计算两个字符串的相似度

///  <summary>   
 ///  计算两个字符串的相似度  
 ///  </summary>   
 ///  <param name="source"> 来源字符串 </param>   
 ///  <param name="target"> 目标字符串 </param>   
 ///  <returns> 相似度 </returns>    
  public  double  CalcSimilarity( string  source,  string  target)  
\{  
 int  n  =  source.Length;  
 int  m  =  target.Length;  
 if  (n  ==  0  ||  m  ==  0 )  
 return  0 ;  
 int  distance  =  CalcDistance(source, target);  
 int  max  =  Math.Max(n, m);  
 return  1.0  \*  (max  \-  distance)  /  max;  
\}

demo:

List < string >  lvArea  =  new  List < string > ();  
lvArea.Add( " 北京电信一区 " );  
lvArea.Add( " 广东一区 " );  
lvArea.Add( " 北京网通二区 " );  
lvArea.Add( " 北京网通一区 " );  
  
 decimal  lvSmall  =  100 ;  
 string  lvRes  =  "" ;  
 foreach  ( string  item  in  lvArea)  
\{  
 decimal  lvTemp  =  CalcDistance( " 北京网通二区 " , item);  
 if  (lvTemp  <  lvSmall)  
\{  
lvSmall  =  lvTemp;  
lvRes  =  item;  
\}  
  
\}  
MessageBox.Show(lvRes);

转载于:https://www.cnblogs.com/phcis/archive/2011/06/30/2094111.html