Levenshtein距離って長さの影響受けすぎてかわいそうな気がする

Levenshtein距離を測る時に、単語長が長くなると、場合によっては文字列長い方が不利じゃない？ってことで、id:naoyaさんのプログラムを拝借して文字の長さの影響を軽減させてみた。

あ、ただ単純に単語1と単語2の長さのルートをとってかけたものでLevenshtein距離を割っているだけです。

これが妥当かどうかは・・どうなんだろう・・ちょっと比較してみる必要があるかもしれないですね・・。

あと、日本語の場合lengthがbyte計算になっていることにも注意。。

#!/hogehoge/perl -w

use strict;
use List::Util qw/min/;
use Params::Validate qw/validate_pos/;

open(IN,'./mogo.tsv');

while(){
    my($name1,$name2) = split('\t',$_);
    my $distance = &levenshtein($name1,$name2);
    my $l1 = length($name1);
    my $l2 = length($name2);
    my $sim = $distance/(sqrt($name1)*sqrt($name2));
    print $name1."\t".$name2."\t".$sim."\n";
}

sub levenshtein{
    my ($s1, $s2) = validate_pos(@_, 1, 1);
    my $m = [];
    
    my @s1 = split(//, $s1);
    my @s2 = split(//, $s2);

    for(my $i = 0; $i <= @s1; $i++){
         $m->[$i]->[0] = $i;
    }

    for(my $j = 0; $j <= @s2; $j++){
         $m->[0]->[$j] = $j;
    }

    for(my $i = 1; $i <= @s1; $i++){
         for(my $j = 1; $j <= @s2; $j++){
              my $diff = ($s1[$i-1] eq $s2[$j-1]) ? 0:1;
              
              #置換、挿入、削除のうち、一番低コストで一致可能なものを選択
　　　　　　　　$m->[$i]->[$j] = min(
                    $m->[$i-1]->[$j-1] + $diff,    #置換
                    $m->[$i-1]->[$j] + 1,          #挿入
                    $m->[$i]->[$j-1] + 1           #削除
                   );
         }
    }

    return $m->[-1]->[-1];
}