相似URL的判定


云舒
摘要：我是在洗澡的间隙，坐在马桶上写这篇博客的。因此，凌乱、间断、错漏肯定是有的，只是我怕思路断了会忘记，所以还是记录下来先。前些时候写过一个html" target=_blank>利用Bloom Filter消除重复URL的文章，今天想了下相似URL判定的方法。URL相似度的判定，在WEB黑盒扫描工具中是很有用的。
最开始想到的是URL也是一个特殊的字符串，那么URL的相似度判定就转化成了字符串相似度判定了。这个问题已经有了很多算法，比较著名的有易做图人的Edit Distance。但是仔细思考后，这个算法做普通字符串相似度比较是可以的，但是作为URL这种特殊的内容来比较则会有很多问题。举例来说，http://www.xxx.com/123.html到http://www.xxx.com/456.html的距离（相似度）与到http://www.xxx.com/abc.html的距离是一样的，但是对于URL来说前面两个是相似的URL，第一个与第三个则不是，这属于特殊条件下的误判。
于是我想到，URL是有结构的，也许我们可以利用这种结构来做判定。对于人来说，一眼就能看出http://video.sina.com.cn/ent/s/h/2010-01-10/163961994.shtml和http://video.sina.com.cn/ent/s/h/2010-01-10/163961890.shtml是相似的URL。但是与http://video.sina.com.cn/ent/m/c/2010-01-10/164661995.shtml呢？则未必，这取决于你如何看待目录本身，可以认为是相似的，也可以认为不是。基于结构来判断URL相似度，我的想法是去掉数字这种东西本身，最终只保留一个结构。字符串是否也需要去掉自身只保留结构，或者保留存在长度的结构，可以根据情况来灵活取舍。
随手写了一段脚本印证想法，这里我没有去掉字符串，仅仅将数字转变成结构了。URL中的参数，我去掉了值，其实这里的值也可以保留结构本身的。冷……不写了。
#!/usr/bin/perl
use strict;
use warnings;
 
my $url1 = http://video.sina.com.cn/ent/s/h/2010-01-10/163961994.shtml?a=1&b=10;
my $url2 = http://video.sina.com.cn/ent/m/c/2010-01-10/164661995.shtml?b=2&a=5;
 
my @array1 = split( ///, $url1 );
my @array2 = split( ///, $url2 );
 
if( @array1 != @array2 )
{
 print "they are not the similar url.
";
 return;
}
 
for( my $i = 3; $i < @array1; $i ++ )
{
 $array1[$i] =~ s/d+/d/g;
 $array2[$i] =~ s/d+/d/g;
 
 #we should compare char sometimes.
 #$array1[$i] =~ s/[a-zA-Z]/c/g;
 #$array2[$i] =~ s/[a-zA-Z]/c/g;
}
 
my $flag1 = index( $array1[-1], ? );
my $flag2 = index( $array2[-1], ? );
my $tmp1 = substr( $array1[-1], $flag1 + 1 );
my $tmp2 = substr( $array2[-1], $flag2 + 1 );
 
if( $flag1 != -1 )
{
 $array1[-1] = substr( $array1[-1], 0, $flag1 );
 $array2[-1] = substr( $array2[
补充：综合编程 , 安全编程 ,