摘要：我是在洗澡的间隙，坐在马桶上写这篇博客的。因此，凌乱、间断、错漏肯定是有的，只是我怕思路断了会忘记，所以还是记录下来先。前些时候写过一个利用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.\n";
	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[-1], 0, $flag2 );
 
	my @tmp_arr = split( /&/, $tmp1 );
	for( my $i = 0; $i < @tmp_arr; $i ++ )
	{
		$tmp_arr[$i] =~ s/=.*//g;
	}
	$array1[-1] = $array1[-1]. '?'. join( '&', sort @tmp_arr );
}
 
if( $flag2 != -1 )
{
	my @tmp_arr = split( /&/, $tmp2 );
	for( my $i = 0; $i < @tmp_arr; $i ++ )
	{
		$tmp_arr[$i] =~ s/=.*//g;
	}
	$array2[-1] = $array2[-1]. '?'. join( '&', sort @tmp_arr );
}
my $result1 = join( '/', @array1 );
my $result2 = join( '/', @array2 );
 
print $url1, "\n\t==>\n\t    ", $result1, "\n\n";
print $url2, "\n\t==>\n\t    ", $result2, "\n";
 
if( $result1 eq $result2 )
{
	print "\nthey are the similar url\n";
}
else
{
	print "\nnot\n";
}
脚本非常的乱，不过只是为了验证想法而已，没有关系。