| 1 | #-*-perl-*- | ||
| 2 | ##################################################################### | ||
| 3 | # Copyright (C) 2004 Jörg Tiedemann <joerg@stp.ling.uu.se> | ||
| 4 | # | ||
| 5 | # This program is free software; you can redistribute it and/or modify | ||
| 6 | # it under the terms of the GNU General Public License as published by | ||
| 7 | # the Free Software Foundation; either version 2 of the License, or | ||
| 8 | # (at your option) any later version. | ||
| 9 | # | ||
| 10 | # This program is distributed in the hope that it will be useful, | ||
| 11 | # but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
| 12 | # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | ||
| 13 | # GNU General Public License for more details. | ||
| 14 | # | ||
| 15 | # You should have received a copy of the GNU General Public License | ||
| 16 | # along with this program; if not, write to the Free Software | ||
| 17 | # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | ||
| 18 | # | ||
| 19 | ##################################################################### | ||
| 20 | # string similarity measures | ||
| 21 | ##################################################################### | ||
| 22 | |||
| 23 | |||
| 24 | package Uplug::StrSim; | ||
| 25 | |||
| 26 | use vars qw(@ISA @EXPORT); | ||
| 27 | @ISA = qw( Exporter); | ||
| 28 | @EXPORT = qw( &similar ); | ||
| 29 | |||
| 30 | ##################################################################### | ||
| 31 | # GetNrSims | ||
| 32 | ##################################################################### | ||
| 33 | |||
| 34 | |||
| 35 | sub GetNrSims | ||
| 36 | { | ||
| 37 | return 4; | ||
| 38 | } | ||
| 39 | |||
| 40 | ##################################################################### | ||
| 41 | # similar($src,$trg,$meth[,\%weights[,$splitpattern]]) | ||
| 42 | ##################################################################### | ||
| 43 | # returns string similarity score for ($src,$trg) | ||
| 44 | # $meth specifies similarity metric | ||
| 45 | # $norm specifies normalization of scores | ||
| 46 | # 0 -> no normalization | ||
| 47 | # 1 -> normalization by length of longer string | ||
| 48 | # 2 -> normalization by length of shorter string | ||
| 49 | |||
| 50 | sub similar | ||
| 51 | { | ||
| 52 | my ($src,$trg, # source and target string | ||
| 53 | $meth, # similarity measure | ||
| 54 | $norm, # normalization | ||
| 55 | $W, # weight function | ||
| 56 | $pattern)=@_; # pattern for splitting into char's | ||
| 57 | |||
| 58 | my ($score,$first,$last)=(0,0,0); | ||
| 59 | # $src=&my_lc($src); # make lower case versions | ||
| 60 | # $trg=&my_lc($trg); # of source and target strings | ||
| 61 | if (length($src)>length($trg)){ # source string should be the shorter | ||
| 62 | ($src,$trg)=($trg,$src); # one -> swap if necessary | ||
| 63 | } | ||
| 64 | |||
| 65 | #--------------------------------------------------------------------------- | ||
| 66 | # now, call the sub-function for string similarity score calculation | ||
| 67 | #--------------------------------------------------------------------------- | ||
| 68 | |||
| 69 | if (($meth==2) or ($meth eq 'ord')) { | ||
| 70 | ($score,$first,$last)= | ||
| 71 | &LCIFS($src,$trg,$W,$pattern); | ||
| 72 | } | ||
| 73 | elsif (($meth==4) or ($meth eq 'pos')) { | ||
| 74 | ($score,$first,$last)= | ||
| 75 | &LNCCRP($src,$trg,$W,$pattern); | ||
| 76 | } | ||
| 77 | elsif (($meth==6) or ($meth eq 'best')) { | ||
| 78 | ($score,$first,$last)= | ||
| 79 | &BestSimilar($src,$trg,$W,$pattern); | ||
| 80 | } | ||
| 81 | else { | ||
| 82 | ($score,$first,$last)= # LCSR is the default metric | ||
| 83 | &LCS($src,$trg,$W,$pattern); | ||
| 84 | } | ||
| 85 | |||
| 86 | #--------------------------------------------------------------------------- | ||
| 87 | # score normalization | ||
| 88 | #--------------------------------------------------------------------------- | ||
| 89 | |||
| 90 | if ($norm==1) { | ||
| 91 | if (length($trg)>0) {$score/=(length($trg));} | ||
| 92 | } | ||
| 93 | if ($norm==2) { | ||
| 94 | if (length($src)>0) {$score/=(length($src));} | ||
| 95 | } | ||
| 96 | if ((defined $first) and (defined $last)){ | ||
| 97 | return ($score,$first,$last); | ||
| 98 | } | ||
| 99 | return $score; | ||
| 100 | } | ||
| 101 | |||
| 102 | |||
| 103 | ########################################################################### | ||
| 104 | # LCSR($src,$trg,[\%weights[,$SplitPattern[,\%trace[,$PrintMatrix]]]]) | ||
| 105 | #-------------------------------------------------------------------------- | ||
| 106 | # longest common sub-sequence ratio | ||
| 107 | #-------------------------------------------------------------------------- | ||
| 108 | # $src - source string | ||
| 109 | # $trg - target string | ||
| 110 | # %weights - weights for character pairs | ||
| 111 | # $SplitPattern - pattern for splitting strings into characters | ||
| 112 | # %trace - trace of character matches | ||
| 113 | # $PrintMatrix - ==1 -> print the LSCR matrix | ||
| 114 | ########################################################################### | ||
| 115 | |||
| 116 | sub LCSR { | ||
| 117 | |||
| 118 | my ($src,$trg,$W,$pattern,$trace,$printMatrix)=@_; | ||
| 119 | my $score=&LCS($src,$trg,$W,$pattern,$trace,$printMatrix); | ||
| 120 | if (length($src)>length($trg)){ | ||
| 121 | return $score/length($src); | ||
| 122 | } | ||
| 123 | if (length($trg)>0){ | ||
| 124 | return $score/length($trg); | ||
| 125 | } | ||
| 126 | return 0; | ||
| 127 | } | ||
| 128 | |||
| 129 | ########################################################################### | ||
| 130 | # LCS($src,$trg,[\%weights[,$SplitPattern[,\%trace[,$PrintMatrix]]]]) | ||
| 131 | #-------------------------------------------------------------------------- | ||
| 132 | # longest common sub-sequence | ||
| 133 | ########################################################################### | ||
| 134 | |||
| 135 | sub LCS { | ||
| 136 | |||
| 137 | my ($src,$trg,$W,$pattern,$trace,$printMatrix)=@_; | ||
| 138 | my (@l,$i,$j); | ||
| 139 | my @src_let=split(/$pattern/,$src); # split string into char | ||
| 140 | my @trg_let=split(/$pattern/,$trg); | ||
| 141 | unshift (@src_let,''); | ||
| 142 | unshift (@trg_let,''); | ||
| 143 | for ($i=0;$i<=$#src_let;$i++){ # initialize the matrix | ||
| 144 | $l[$i][0]=0; | ||
| 145 | } | ||
| 146 | for ($i=0;$i<=$#trg_let;$i++){ | ||
| 147 | $l[0][$i]=0; | ||
| 148 | } # weight function is | ||
| 149 | if (defined $W){ # defined: | ||
| 150 | for $i (1..$#src_let){ # if the pair | ||
| 151 | for $j (1..$#trg_let){ # ['.','.'] is | ||
| 152 | if (($$W{'.'}{'.'}) and # defined in %W: | ||
| 153 | (not $$W{$src_let[$i]}{$trg_let[$j]})){ # -> count all | ||
| 154 | if ($src_let[$i] eq $trg_let[$j]){ # identical | ||
| 155 | $$W{$src_let[$i]}{$trg_let[$j]}=1; # matches with | ||
| 156 | } # score=1 if the | ||
| 157 | } # pair is not | ||
| 158 | my $best; # included in %W | ||
| 159 | if ($$W{$src_let[$i]}{$trg_let[$j]}){ | ||
| 160 | $best=$l[$i-1][$j-1]+$$W{$src_let[$i]}{$trg_let[$j]}; | ||
| 161 | } | ||
| 162 | if ($l[$i][$j-1]>$best){ | ||
| 163 | $best=$l[$i][$j-1]; | ||
| 164 | } | ||
| 165 | if ($l[$i-1][$j]>$best){ | ||
| 166 | $best=$l[$i-1][$j]; | ||
| 167 | } | ||
| 168 | $l[$i][$j]=$best; | ||
| 169 | } | ||
| 170 | } | ||
| 171 | } | ||
| 172 | else{ | ||
| 173 | for $i (1..$#src_let){ | ||
| 174 | for $j (1..$#trg_let){ | ||
| 175 | if ($src_let[$i] eq $trg_let[$j]){ | ||
| 176 | $l[$i][$j]=$l[$i-1][$j-1]+1; | ||
| 177 | } | ||
| 178 | else{ | ||
| 179 | if ($l[$i][$j-1]>$l[$i-1][$j]){ | ||
| 180 | $l[$i][$j]=$l[$i][$j-1]; | ||
| 181 | } | ||
| 182 | else{ | ||
| 183 | $l[$i][$j]=$l[$i-1][$j]; | ||
| 184 | } | ||
| 185 | } | ||
| 186 | } | ||
| 187 | } | ||
| 188 | } | ||
| 189 | if (defined $trace){ # save the trace of character | ||
| 190 | $i=$#l; # matches if %trace is defined | ||
| 191 | $j=$#{$l[0]}; | ||
| 192 | while (($i>0) and ($j>0)){ | ||
| 193 | if ($l[$i][$j]==$l[$i-1][$j]){ | ||
| 194 | $$trace{$i}{$j}=$l[$i][$j]-$l[$i-1][$j]; | ||
| 195 | $i-=1; | ||
| 196 | } | ||
| 197 | elsif($l[$i][$j]==$l[$i][$j-1]){ | ||
| 198 | $$trace{$i}{$j}=$l[$i][$j]-$l[$i][$j-1]; | ||
| 199 | $j-=1; | ||
| 200 | } | ||
| 201 | else{ | ||
| 202 | $$trace{$i}{$j}=$l[$i][$j]-$l[$i-1][$j-1]; | ||
| 203 | $i-=1; | ||
| 204 | $j-=1; | ||
| 205 | } | ||
| 206 | } | ||
| 207 | } | ||
| 208 | |||
| 209 | if ($printMatrix){ | ||
| 210 | print ' '; | ||
| 211 | foreach (0..$#src_let){ | ||
| 212 | printf "%4s ", $src_let[$_]; | ||
| 213 | } | ||
| 214 | print "\n"; | ||
| 215 | |||
| 216 | foreach (0..$#trg_let){ | ||
| 217 | my $i; | ||
| 218 | printf "%3s ", $trg_let[$_]; | ||
| 219 | foreach $i (0..$#src_let){ | ||
| 220 | printf "%1.2f",$l[$i][$_]; | ||
| 221 | print " "; | ||
| 222 | } | ||
| 223 | print "\n"; | ||
| 224 | } | ||
| 225 | } | ||
| 226 | |||
| 227 | return $l[$#src_let][$#trg_let]; | ||
| 228 | } | ||
| 229 | |||
| 230 | |||
| 231 | |||
| 232 | ##################################################################### | ||
| 233 | # GetNonMatches($src,$trg,\%NonMatchPairs)' | ||
| 234 | #-------------------------------------------------------------------- | ||
| 235 | # get all non-matching pairs from two strings | ||
| 236 | ##################################################################### | ||
| 237 | |||
| 238 | sub GetNonMatches{ | ||
| 239 | |||
| 240 | my ($src,$trg,$res)=@_; | ||
| 241 | |||
| 242 | my %trace; | ||
| 243 | my $score=&LCS($src,$trg,undef,'',\%trace); | ||
| 244 | |||
| 245 | my @SRC=split(//,$src); | ||
| 246 | my @TRG=split(//,$trg); | ||
| 247 | |||
| 248 | my $i=1; | ||
| 249 | my $j=1; | ||
| 250 | |||
| 251 | my $x=1; | ||
| 252 | my $y=1; | ||
| 253 | my ($srcnot,$trgnot)=('',''); | ||
| 254 | |||
| 255 | my $matches=''; | ||
| 256 | my $nonmatches=''; | ||
| 257 | my $SrcNonMatch=''; | ||
| 258 | my $TrgNonMatch=''; | ||
| 259 | |||
| 260 | foreach $i (sort {$a <=> $b} keys %trace){ | ||
| 261 | foreach $j (sort {$a <=> $b} keys %{$trace{$i}}){ | ||
| 262 | if ($trace{$i}{$j}){ | ||
| 263 | $matches.=$SRC[$i-1]; | ||
| 264 | while ($x<$i){ | ||
| 265 | $srcnot.=$SRC[$x-1]; | ||
| 266 | $x++; | ||
| 267 | } | ||
| 268 | while ($y<$j){ | ||
| 269 | $trgnot.=$TRG[$y-1]; | ||
| 270 | $y++; | ||
| 271 | } | ||
| 272 | $x++; | ||
| 273 | $y++; | ||
| 274 | if ($srcnot or $trgnot){ | ||
| 275 | $$res{$srcnot}{$trgnot}++; | ||
| 276 | $SrcNonMatch.=$srcnot.'*'; | ||
| 277 | $TrgNonMatch.=$trgnot.'*'; | ||
| 278 | $nonmatches.='('.$srcnot.'|'.$trgnot.').*'; | ||
| 279 | } | ||
| 280 | else{ | ||
| 281 | if (not $nonmatches){ | ||
| 282 | $nonmatches='.*'; | ||
| 283 | $SrcNonMatch.='*'; | ||
| 284 | $TrgNonMatch.='*'; | ||
| 285 | } | ||
| 286 | } | ||
| 287 | ($srcnot,$trgnot)=('',''); | ||
| 288 | } | ||
| 289 | else{ | ||
| 290 | if ($matches!~/\*$/){ | ||
| 291 | $matches.='*'; | ||
| 292 | } | ||
| 293 | } | ||
| 294 | } | ||
| 295 | } | ||
| 296 | while ($x<=@SRC){ | ||
| 297 | $srcnot.=$SRC[$x-1]; | ||
| 298 | $x++; | ||
| 299 | } | ||
| 300 | while ($y<=@TRG){ | ||
| 301 | $trgnot.=$TRG[$y-1]; | ||
| 302 | $y++; | ||
| 303 | } | ||
| 304 | if ($srcnot or $trgnot){ | ||
| 305 | $$res{$srcnot}{$trgnot}++; | ||
| 306 | # $nonmatches.="\{'".$srcnot."' \=\> '".$trgnot."'\}\*"; | ||
| 307 | $nonmatches.='('.$srcnot.'|'.$trgnot.')'; | ||
| 308 | $SrcNonMatch.=$srcnot; | ||
| 309 | $TrgNonMatch.=$trgnot; | ||
| 310 | } | ||
| 311 | return ($score,$nonmatches,$matches, | ||
| 312 | $SrcNonMatch,$TrgNonMatch); | ||
| 313 | } | ||
| 314 | |||
| 315 | |||
| 316 | ##################################################################### | ||
| 317 | # GetNonMatches($src,$trg,\%NonMatchPairs)' | ||
| 318 | #-------------------------------------------------------------------- | ||
| 319 | # get all non-matching pairs from two strings | ||
| 320 | ##################################################################### | ||
| 321 | |||
| 322 | sub GetNonMatchesOld{ | ||
| 323 | |||
| 324 | my ($src,$trg,$res)=@_; | ||
| 325 | |||
| 326 | my %trace; | ||
| 327 | my $score=&LCS($src,$trg,undef,'',\%trace); | ||
| 328 | |||
| 329 | my @SRC=split(//,$src); | ||
| 330 | my @TRG=split(//,$trg); | ||
| 331 | |||
| 332 | my $i=1; | ||
| 333 | my $j=1; | ||
| 334 | |||
| 335 | my $x=1; | ||
| 336 | my $y=1; | ||
| 337 | my ($srcnot,$trgnot)=('',''); | ||
| 338 | |||
| 339 | my $matches=''; | ||
| 340 | my $nonmatches=''; | ||
| 341 | |||
| 342 | foreach $i (sort {$a <=> $b} keys %trace){ | ||
| 343 | foreach $j (sort {$a <=> $b} keys %{$trace{$i}}){ | ||
| 344 | if ($trace{$i}{$j}){ | ||
| 345 | $matches.=$SRC[$i]; | ||
| 346 | while ($x<$i){ | ||
| 347 | $srcnot.=$SRC[$x-1]; | ||
| 348 | $x++; | ||
| 349 | } | ||
| 350 | while ($y<$j){ | ||
| 351 | $trgnot.=$TRG[$y-1]; | ||
| 352 | $y++; | ||
| 353 | } | ||
| 354 | $x++; | ||
| 355 | $y++; | ||
| 356 | if ($srcnot or $trgnot){ | ||
| 357 | $$res{$srcnot}{$trgnot}++; | ||
| 358 | $nonmatches.='('.$srcnot.'|'.$trgnot.').*'; | ||
| 359 | } | ||
| 360 | else{ | ||
| 361 | if (not $nonmatches){ | ||
| 362 | $nonmatches='.*'; | ||
| 363 | } | ||
| 364 | } | ||
| 365 | ($srcnot,$trgnot)=('',''); | ||
| 366 | } | ||
| 367 | else{ | ||
| 368 | if ($matches!~/\*$/){ | ||
| 369 | $matches.='*'; | ||
| 370 | } | ||
| 371 | } | ||
| 372 | } | ||
| 373 | } | ||
| 374 | while ($x<=@SRC){ | ||
| 375 | $srcnot.=$SRC[$x-1]; | ||
| 376 | $x++; | ||
| 377 | } | ||
| 378 | while ($y<=@TRG){ | ||
| 379 | $trgnot.=$TRG[$y-1]; | ||
| 380 | $y++; | ||
| 381 | } | ||
| 382 | if ($srcnot or $trgnot){ | ||
| 383 | $$res{$srcnot}{$trgnot}++; | ||
| 384 | # $nonmatches.="\{'".$srcnot."' \=\> '".$trgnot."'\}\*"; | ||
| 385 | $nonmatches.='('.$srcnot.'|'.$trgnot.')'; | ||
| 386 | } | ||
| 387 | return ($score,$nonmatches,$matches); | ||
| 388 | } | ||
| 389 | |||
| 390 | |||
| 391 | ##################################################################### | ||
| 392 | # LCIS($src,$trg) | ||
| 393 | ##################################################################### | ||
| 394 | # longest common initial subsequence | ||
| 395 | |||
| 396 | sub LCIS | ||
| 397 | { | ||
| 398 | my ($src,$trg,$W,$pattern)=@_; | ||
| 399 | my ($i,$j,$score,$first,$last)=(0,0,0,0,0); | ||
| 400 | if (length($src)>length($trg)) {($src,$trg)=($trg,$src);} | ||
| 401 | @src_let=split(/$pattern/,$src); # split words into single | ||
| 402 | @trg_let=split(/$pattern/,$trg); # letters | ||
| 403 | while ($i<@src_let) # until last letter is reached | ||
| 404 | { | ||
| 405 | if ($src_let[$i] eq $trg_let[$j]) # if same letters at | ||
| 406 | { # current positions | ||
| 407 | $score++; # -> increment score and | ||
| 408 | $i++; # the position in the smaller word | ||
| 409 | if (not $first) {$first=$j+1;} # remember postition of the first | ||
| 410 | $last=$j+1; # and the last match | ||
| 411 | } | ||
| 412 | if ($j<@trg_let) {$j++;} # increment the position in the | ||
| 413 | else {last;} # longer word, if not endposition | ||
| 414 | } | ||
| 415 | return ($score,$first,$last); # return score, first and last | ||
| 416 | } | ||
| 417 | |||
| 418 | ##################################################################### | ||
| 419 | # LCIFS($src,$trg) | ||
| 420 | ##################################################################### | ||
| 421 | # max(longest common initial subsequence, | ||
| 422 | # longest common final subsequence) | ||
| 423 | |||
| 424 | sub LCIFS | ||
| 425 | { | ||
| 426 | my ($src,$trg,$W,$pattern)=@_; | ||
| 427 | my ($i,$j,$score1,$first1,$last1)=(0,0,0,0,0); | ||
| 428 | my ($score2,$first2,$last2)=(0,0,0); | ||
| 429 | if (length($src)>length($trg)) {($src,$trg)=($trg,$src);} | ||
| 430 | |||
| 431 | ($score1,$first1,$last1)=&LCIS($src,$trg); | ||
| 432 | |||
| 433 | @src_let=split(/$pattern/,$src); # split words into single | ||
| 434 | @trg_let=split(/$pattern/,$trg); # letters | ||
| 435 | ($i,$j)=(@src_let-1,@trg_let-1); # and now from the last character | ||
| 436 | while ($i>=0) | ||
| 437 | { | ||
| 438 | if ($src_let[$i] eq $trg_let[$j]) # same as above | ||
| 439 | { | ||
| 440 | $score2++; | ||
| 441 | $i--; # but decrement positions | ||
| 442 | if (not $last2) {$last2=$j+1;} # remember postition of the last | ||
| 443 | $first2=$j+1; # and the first match | ||
| 444 | } | ||
| 445 | if ($j>0) {$j--;} | ||
| 446 | else {last;}; | ||
| 447 | } | ||
| 448 | |||
| 449 | if ($score1>=$score2){return ($score1,$first1,$last1);} | ||
| 450 | return ($score2,$first2,$last2); | ||
| 451 | } | ||
| 452 | |||
| 453 | ##################################################################### | ||
| 454 | # LNCCP($src,$trg) | ||
| 455 | ##################################################################### | ||
| 456 | # largest number of common characters at same positions | ||
| 457 | |||
| 458 | sub LNCCP | ||
| 459 | { | ||
| 460 | my ($src,$trg,$W,$pattern)=@_; | ||
| 461 | my ($i,$score,$first,$last)=(0,0,0); | ||
| 462 | if (length($src)>length($trg)) {($src,$trg)=($trg,$src);} | ||
| 463 | @src_let=split(/$pattern/,$src); # split words into single | ||
| 464 | @trg_let=split(/$pattern/,$trg); # letters | ||
| 465 | for ($i=0;$i<@src_let;$i++) # for every letter of the | ||
| 466 | { # string | ||
| 467 | if ($src_let[$i] eq $trg_let[$i]) # if letters equal | ||
| 468 | { # at same positions | ||
| 469 | $score++; # -> increment score | ||
| 470 | if (not $first) {$first=$i+1;} | ||
| 471 | $last=$i+1; | ||
| 472 | } | ||
| 473 | } | ||
| 474 | return ($score,$first,$last); # and return | ||
| 475 | } | ||
| 476 | |||
| 477 | ##################################################################### | ||
| 478 | # LNCCRP($src,$trg) | ||
| 479 | ##################################################################### | ||
| 480 | # largest number of common characters at same relativ positions | ||
| 481 | |||
| 482 | sub LNCCRP | ||
| 483 | { | ||
| 484 | my ($src,$trg,$W,$pattern)=@_; | ||
| 485 | |||
| 486 | my ($j,$i,$best,$score,$first,$last,$first_tmp,$last_tmp)=(0,0,0,0,0,0,0,0); | ||
| 487 | if (length($src)>length($trg)) {($src,$trg)=($trg,$src);} | ||
| 488 | |||
| 489 | @src_let=split(/$pattern/,$src); | ||
| 490 | @trg_let=split(/$pattern/,$trg); | ||
| 491 | for ($j=0-@src_let;$j<@trg_let;$j++){ | ||
| 492 | $score=0; | ||
| 493 | $first_tmp=0; | ||
| 494 | for ($i=0;$i<@src_let;$i++) | ||
| 495 | { | ||
| 496 | if (($i+$j>=0) and ($i+$j<@trg_let)){ | ||
| 497 | if ($src_let[$i] eq $trg_let[$i+$j]) | ||
| 498 | { | ||
| 499 | $score++; | ||
| 500 | $last_tmp=$j+$i+1; | ||
| 501 | if (not $first_tmp){$first_tmp=$j+$i+1;} | ||
| 502 | } | ||
| 503 | } | ||
| 504 | } | ||
| 505 | if ($score>$best) | ||
| 506 | { | ||
| 507 | $best=$score; | ||
| 508 | $first=$first_tmp; | ||
| 509 | $last=$last_tmp; | ||
| 510 | } | ||
| 511 | } | ||
| 512 | return ($best,$first,$last); | ||
| 513 | } | ||
| 514 | |||
| 515 | |||
| 516 | ##################################################################### | ||
| 517 | # BestSimilar($src,$trg) # | ||
| 518 | ##################################################################### | ||
| 519 | # calculate similarity scores with all available measures and | ||
| 520 | # return the highest for the current string pair | ||
| 521 | |||
| 522 | sub BestSimilar | ||
| 523 | { | ||
| 524 | my ($src,$trg)=@_; | ||
| 525 | my $sims=&GetNrSims; | ||
| 526 | my ($i,$bestscore,$bestlast,$bestfirst)=(0,0,0,0); | ||
| 527 | my ($score,$first,$last); | ||
| 528 | for $i (0..$sims-2){ # don't do BestSimilar again ... | ||
| 529 | ($score,$first,$last)=similar($src,$trg,$i); | ||
| 530 | if ($score>$bestscore){ | ||
| 531 | $bestscore=$score; | ||
| 532 | $bestfirst=$first; | ||
| 533 | $bestlast=$last; | ||
| 534 | } | ||
| 535 | } | ||
| 536 | return ($bestscore,$bestfirst,$bestlast); | ||
| 537 | } | ||
| 538 | |||
| 539 | ##################################################################### | ||
| 540 | # CombScore(\@ScoreMatrix,\@ScoreComb,$meth) | ||
| 541 | ##################################################################### | ||
| 542 | # scores[source][target]: score matrix | ||
| 543 | # $meth specifies algorithm | ||
| 544 | # @comb contains resulting score matrix | ||
| 545 | |||
| 546 | sub CombScore | ||
| 547 | { | ||
| 548 | local (*scores,*comb,$meth)=@_; | ||
| 549 | if (($meth==0)or($meth eq 'sub_s')) {&CombScore1(\@scores,\@comb);} | ||
| 550 | if (($meth==1)or($meth eq 'sub_t')) {&CombScore2(\@scores,\@comb);} | ||
| 551 | if (($meth==2)or($meth eq 'sub_l')) {&CombScore3(\@scores,\@comb);} | ||
| 552 | if (($meth==3)or($meth eq 'sub_b')) {&CombScore4(\@scores,\@comb);} | ||
| 553 | if (($meth==4)or($meth eq 'sub_s_sub_b')) {&CombScore5(\@scores,\@comb);} | ||
| 554 | if (($meth==5)or($meth eq 'sub_t_sub_b')) {&CombScore6(\@scores,\@comb);} | ||
| 555 | if (($meth==6)or($meth eq 'sub_l_sub_b')) {&CombScore7(\@scores,\@comb);} | ||
| 556 | } | ||
| 557 | |||
| 558 | ##################################################################### | ||
| 559 | # score combination 1 (score-s) # | ||
| 560 | ##################################################################### | ||
| 561 | |||
| 562 | sub CombScore1{ | ||
| 563 | |||
| 564 | local (*scores,*comb)=@_; | ||
| 565 | for $i (0..$#scores){ | ||
| 566 | for $j (0..$#{$scores[$i]}){ | ||
| 567 | for $k (0..$#scores){ | ||
| 568 | if ($k==$i) {$comb[$i][$j]+=$scores[$k][$j];} | ||
| 569 | else {$comb[$i][$j]-=$scores[$k][$j];} | ||
| 570 | |||
| 571 | } | ||
| 572 | } | ||
| 573 | } | ||
| 574 | } | ||
| 575 | |||
| 576 | ##################################################################### | ||
| 577 | # score combination 2 (score-t) # | ||
| 578 | ##################################################################### | ||
| 579 | |||
| 580 | sub CombScore2{ | ||
| 581 | |||
| 582 | local (*scores,*comb)=@_; | ||
| 583 | for $i (0..$#scores){ | ||
| 584 | for $j (0..$#{$scores[$i]}){ | ||
| 585 | for $k (0..$#{$scores[$i]}){ | ||
| 586 | if ($k==$j) {$comb[$i][$j]+=$scores[$i][$k];} | ||
| 587 | else {$comb[$i][$j]-=$scores[$i][$k];} | ||
| 588 | |||
| 589 | } | ||
| 590 | } | ||
| 591 | } | ||
| 592 | } | ||
| 593 | |||
| 594 | ##################################################################### | ||
| 595 | # score combination 3 (score-l) # | ||
| 596 | ##################################################################### | ||
| 597 | |||
| 598 | sub CombScore3{ | ||
| 599 | local (*scores,*comb)=@_; | ||
| 600 | if ($#scores>$#{$scores[0]}){CombScore2(\@scores,\@comb);} | ||
| 601 | else{CombScore1(\@scores,\@comb);} | ||
| 602 | } | ||
| 603 | |||
| 604 | |||
| 605 | ##################################################################### | ||
| 606 | # score combination 4 (lead_avr) # | ||
| 607 | ##################################################################### | ||
| 608 | |||
| 609 | sub CombScore4{ | ||
| 610 | |||
| 611 | local (*scores,*comb)=@_; | ||
| 612 | for $i (0..$#scores){ | ||
| 613 | for $j (0..$#{$scores[$i]}){ | ||
| 614 | my $best=-99999999; | ||
| 615 | my $bestpos=0; | ||
| 616 | for $k (0..$#scores){ | ||
| 617 | if ($k!=$i) { | ||
| 618 | if ($scores[$k][$j]>$best){ | ||
| 619 | $best=$scores[$k][$j]; | ||
| 620 | $bestpos=$k; | ||
| 621 | } | ||
| 622 | } | ||
| 623 | } | ||
| 624 | $comb[$i][$j]=$scores[$i][$j]-$scores[$bestpos][$j]; | ||
| 625 | } | ||
| 626 | } | ||
| 627 | } | ||
| 628 | |||
| 629 | |||
| 630 | ##################################################################### | ||
| 631 | # score combination lead_avr-s # | ||
| 632 | ##################################################################### | ||
| 633 | |||
| 634 | sub CombScore5{ | ||
| 635 | local (*scores,*comb)=@_; | ||
| 636 | my @tmparr; | ||
| 637 | &CombScore1(\@scores,\@comb); | ||
| 638 | &CombScore4(\@comb,\@tmparr); | ||
| 639 | @comb=@tmparr; | ||
| 640 | } | ||
| 641 | |||
| 642 | ##################################################################### | ||
| 643 | # score combination lead_avr-t # | ||
| 644 | ##################################################################### | ||
| 645 | |||
| 646 | sub CombScore6{ | ||
| 647 | local (*scores,*comb)=@_; | ||
| 648 | my @tmparr; | ||
| 649 | &CombScore2(\@scores,\@comb); | ||
| 650 | &CombScore4(\@comb,\@tmparr); | ||
| 651 | @comb=@tmparr; | ||
| 652 | } | ||
| 653 | |||
| 654 | ##################################################################### | ||
| 655 | # score combination lead_avr-l # | ||
| 656 | ##################################################################### | ||
| 657 | |||
| 658 | sub CombScore7{ | ||
| 659 | local (*scores,*comb)=@_; | ||
| 660 | my @tmparr; | ||
| 661 | &CombScore3(\@scores,\@comb); | ||
| 662 | &CombScore4(\@comb,\@tmparr); | ||
| 663 | @comb=@tmparr; | ||
| 664 | } | ||
| 665 | |||
| 666 | |||
| 667 | |||
| 668 | |||
| 669 | |||
| 670 | |||
| 671 | |||
| 672 | |||
| 673 | |||
| 674 | |||
| 675 | |||
| 676 | 1; | ||
| 677 |