比较字符串相似度函数

比较字符串相似度函数
sub compare($$){
my ($src,$obj) = @_;
#某字符不同时 设定的权值
my $cost = $_[2] || 1;

my @src_arr = split //,$src;
my @obj_arr = split //,$obj;
@src_arr = ('0',@src_arr);
@obj_arr = ('0',@obj_arr);
my $src_len = $#src_arr;
my $obj_len = $#obj_arr;

my @matrix;
my $no = 0;
for (my $i = 0;$i <= $src_len ; $i++ ) {#第一横行赋值
$matrix[$i][0] = $no;
$no ++;
}
$no = 0;
for (my $i = 0;$i <= $obj_len ; $i++ ) {#第一竖行赋值
$matrix[0][$i] = $no;
$no ++;
}

for (my $p = 1;$p <= $obj_len; $p++) { #$p 竖 $h 横
for (my $h = 1;$h <= $src_len; $h++) {
my @value;
my $diff = 0;

if ($src_arr[$h] ne $obj_arr[$p]) {
$diff = $cost; #设定是否加值
}

if (defined $matrix[$h][$p-1]) {
push @value, $matrix[$h][$p-1] + $diff;
}
if (defined $matrix[$h-1][$p]) {
push @value, $matrix[$h-1][$p] + $diff;
}
if (defined $matrix[$h-1][$p-1]) {
push @value, $matrix[$h-1][$p-1] + $diff;
}

my @sort_value = sort { $b <=> $a } @value;
$matrix[$h][$p] = $sort_value[-1];
}
}


#打印矩阵结果
#for (my $i = 0;$i<= $obj_len ;$i++) {
# for (my $j = 0;$j<= $src_len ;$j++) {
# print $matrix[$j][$i]." ";
# }
# print "\n";
#}

return $matrix[$src_len][$obj_len];

}


运行:

my $a = &compare('lao','leo');
结果为1;
矩阵:
0 l a o
0 0 1 2 3
l 1 0 1 2
e 2 1 1 2
o 3 2 2 1(返回值)
算法: 矩阵中某点的正上方一格代表加一个字母的代价,正前方一格代表减一个字母的代价,左上方一格代表改一个字母的代价, 如果字母不一样则上述第2情况加上$cost($diff)权值.
算出这三种情况后，取最小值为此点的值，然后继续循环.
当$cost=1时 函数返回值=最少需要更改多少次后 两个字符串完全相同.
&compare('slekdfj','leoa');
0 1 2 3 4 5 6 7
1 1 1 2 3 4 5 6
2 2 2 1 2 3 4 5
3 3 3 2 2 3 4 5
4 4 4 3 3 3 4 5

学习ing..........-- 学习ing..........


-----------------------
亿客网络
http://www.icho.cn/
全球唯一能提供（非 CGI)
mod_python,
mod_php5,
mod_perl
主机提供商。 另开放免费商业主机申请，为开源作者免费服务