blib/lib/Uplug/StrSim.pm untested

filter: Statementstmt 0.0% 0 / 363 Branchbran 0.0% 0 / 126 Conditioncond 0.0% 0 / 54 MC/DCmcdc 0.0% 0 / 36 Subroutinesub 0.0% 0 / 20 Podpod 0.0% 0 / 19 totaltotal 0.0% 0 / 618 CC 64 SCAR 41.8
CC
64
Cov
0%
LCS
182.0
similar
110.0
CombScore
72.0
CRAP 65.2
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