blib/lib/Uplug/Align/Word/Clue.pm untested

filter: Statementstmt 0.0% 0 / 973 Branchbran 0.0% 0 / 298 Conditioncond 0.0% 0 / 81 MC/DCmcdc 0.0% 0 / 52 Subroutinesub 0.0% 0 / 51 Podpod 0.0% 0 / 44 totaltotal 0.0% 0 / 1499 CC 150 SCAR 49.4
CC
150
Cov
0%
getLinkScores
756.0
add2LinkCluster
156.0
findAlignment
110.0
CRAP 139.1
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 # Uplug::Align::Word::Clue
21 #
22 #
23 #
24 ###########################################################################
25  
26  
27 package Uplug::Align::Word::Clue;
28  
29 use strict;
30 # use Time::HiRes qw(time);
31  
32  
33 use vars qw(@ISA $DEBUG);
34 use vars qw($INPHRASESONLY $ADJACENTONLY $ADJACENTSCORE $FILLPHRASES);
35 use vars qw($ALLOWMULTIOVERLAP $PRINTHTML);
36 # use utf8;
37 use Uplug::Data;
38 use Uplug::Align::Word;
39 use Data::Dumper;
40 $Data::Dumper::Indent=1;
41 $Data::Dumper::Terse=1;
42 $Data::Dumper::Purity=1;
43  
44 @ISA = qw( Uplug::Align::Word );
45  
46 $DEBUG = 0;
47  
48 #---------------------------------
49 # parameters for add2LinkCluster
50  
51 $INPHRASESONLY = 0; # if = 1 --> no links outside of chunks
52 $ADJACENTONLY = 0; # if = 1 --> allow only adjacent links
53 $ADJACENTSCORE = 0; # if > 0 --> $score >= $neighbor * $ADJACENTSCORE
54 # $ALLOWMULTIOVERLAP = 0; # allow overlap with more than 1 link cluster!
55 # $ADJACENTSCORE = 0.4;
56 $ADJACENTSCORE = 0;
57  
58 $FILLPHRASES = 0; # ... doesn't work ....
59  
60  
61  
62 sub new{
63 my $class=shift;
64 my $self=$class->SUPER::new(@_);
65 if (not defined $self->parameter('adjacent_only')){
66 $self->setParameter('adjacent_only',$ADJACENTONLY);
67 }
68 if (not defined $self->parameter('adjacent_score')){
69 $self->setParameter('adjacent_score',$ADJACENTSCORE);
70 }
71 if (not defined $self->parameter('in_phrases_only')){
72 $self->setParameter('in_phrases_only',$INPHRASESONLY);
73 }
74 if (not defined $self->parameter('fill_phrase')){
75 $self->setParameter('fill_phrases',$FILLPHRASES);
76 }
77 if (not defined $self->parameter('allow_multiple_overalps')){
78 $self->setParameter('allow_multiple_overlaps',$ALLOWMULTIOVERLAP);
79 }
80 if (not defined $self->parameter('verbose')){
81 $self->setParameter('verbose',$DEBUG);
82 }
83 else{$DEBUG=$self->parameter('verbose');}
84  
85 return $self;
86 }
87  
88 sub DESTROY {
89 my $self = shift;
90 }
91  
92  
93  
94 #===========================================================================
95 #
96 # get all link scores and fill the clue matrix
97 #
98 #===========================================================================
99  
100 sub getLinkScores{
101 my $self=shift;
102  
103 $self->{matrix}=[];
104 $self->{links}={};
105 my $LinkProb=$self->{matrix};
106 my $links=$self->{linkStreams};
107 my $SrcTok=$self->{srcToken};
108 my $TrgTok=$self->{trgToken};
109 my $Param=$self->{param};
110 my $data=$self->{data};
111  
112 ## prepare clue param hash (reduce checks in the loop below)
113 my %ClueParam=%{$Param};
114 if (exists $ClueParam{general}){delete $ClueParam{general};}
115 if (exists $ClueParam{original}){delete $ClueParam{original};}
116 foreach (keys %ClueParam){
117 if (ref($ClueParam{$_}) ne 'HASH'){$ClueParam{$_}={};}
118 if (not defined $ClueParam{$_}{'score weight'}){
119 $ClueParam{$_}{'score weight'}=$self->defaultClueWeight();
120 }
121 }
122  
123 ## define some variables used in the loop
124 my $weight; # clue combination weight
125 my ($src,$trg); # source and target language tokens
126 my $score; # clue score found for the current pair
127 my $time; # time (for debugging)
128 my %search; # hash of patterns for searching clues
129 my $found=Uplug::Data->new; # clues found
130 my @SrcTok; # positions of the current source
131 my @TrgTok; # and target tokens in the sentence
132 my ($s,$t,$x,$y,$p); # variables for iteration
133 my $ScoreComb=$self->parameter('score combination');
134 if (not $ScoreComb){$ScoreComb='probabilistic';}
135  
136 if ($self->parameter('verbose')){
137 print STDERR "\n=====================================================\n";
138 print STDERR "matching clue scores";
139 print STDERR "\n=====================================================\n";
140 }
141  
142  
143 ## the following loop takes most of the time!
144  
145 foreach $s (sort {$a <=> $b} keys %{$SrcTok}){
146 foreach $t (keys %{$TrgTok}){
147  
148 $time=time();
149  
150 ($src,$trg)=($$SrcTok{$s}{general},$$TrgTok{$t}{general});
151 $self->alignIdentical($src,$trg,$s,$t,$LinkProb);
152  
153 ### DEBUG: store search time
154 $self->{identical_score_time}+=time()-$time if ($DEBUG);
155  
156 foreach (keys %ClueParam){
157  
158 $time=time();
159  
160 $weight=$ClueParam{$_}{'score weight'};
161 if ($ClueParam{$_}{'relative position'}){
162 ($src,$trg)=$self->makeRelPosFeature($$SrcTok{$s}{$_},
163 $$TrgTok{$t}{$_});
164 }
165 else{($src,$trg)=($$SrcTok{$s}{$_},$$TrgTok{$t}{$_});}
166  
167 ### DEBUG: store search time
168 $self->{before_score_time}+=time()-$time if ($DEBUG);
169  
170 $score=0;
171  
172 #---------------------------------------
173 # length difference as scores ...
174 #---------------------------------------
175  
176 if ($ClueParam{$_}{'string length difference'}){
177 $score=$data->lengthQuotient($src,$trg);
178 }
179  
180 #---------------------------------------
181 # otherwise: search scores in link-DB
182 #---------------------------------------
183  
184 else{
185 if (not defined $links->{$_}){next;}
186 if (defined($src) and defined($trg)){
187 %search=('source' => $src,
188 'target' => $trg);
189 $time=time();
190 if ($links->{$_}->select($found,\%search)){
191 $score=$found->attribute('score');
192 }
193 ### DEBUG: store search time
194 $self->{search_score_time}+=time()-$time if ($DEBUG);
195 }
196 }
197  
198 $time=time();
199  
200 #---------------------------------------
201 # set weighted score in score matrix
202 #---------------------------------------
203  
204 if (not $score){next;}
205 if (not $data->checkPairParameter($src,$trg,$ClueParam{$_})){
206 ### DEBUG: store search time
207 $self->{after_score_time}+=time()-$time if ($DEBUG);
208 next;
209 }
210  
211 if (exists $ClueParam{$_}{'minimal score'}){
212 if ($score<$ClueParam{$_}{'minimal score'}){
213 ### DEBUG: store search time
214 $self->{after_score_time}+=time()-$time if ($DEBUG);
215 next;
216 }
217 }
218  
219 $score*=$weight;
220  
221 # shouldn't be >1, but in case ...
222 #--------------------------------
223 if ($score>=1){$score=0.999999999999;}
224 #--------------------------------
225  
226 if ($self->parameter('verbose')){
227 # printf STDERR "%20s [ %s %s ] %15s - %-15s %s\n",
228 printf STDERR "$_\t$s\t$t\t$src\t$trg\t$score\n";
229 }
230  
231 @SrcTok=split(/:/,$s);
232 @TrgTok=split(/:/,$t);
233  
234 foreach $x (@SrcTok){
235 foreach $y (@TrgTok){
236  
237 # if ($self->parameter('verbose')){
238 # printf STDERR "%20s [%d %d] %15s - %-15s %s\n",
239 # $_,$x,$y,$src,$trg,$score;
240 # }
241  
242 if ($ScoreComb eq 'addition'){
243 $$LinkProb[$x][$y]+=$score;
244 }
245 #
246 # log-linear and multiplication are useless!
247 # * there's not always a positive score for each possible pair!
248 # --> multiplications with one factor = 0 --> score = 0
249 # --> leaving out zero-factors -> implicit penalty for pairs with multiple
250 # clue scores
251 #
252 # elsif ($ScoreComb eq 'log-linear'){
253 # $$LinkProb[$x][$y]+=log($score);
254 # }
255 # elsif ($ScoreComb eq 'multiplication'){
256 # $$LinkProb[$x][$y]+=log($score);
257 # }
258 else{
259 $p=$$LinkProb[$x][$y];
260 $$LinkProb[$x][$y]=$p+$score-$p*$score;
261 }
262 }
263 }
264  
265 ### DEBUG: store search time
266 $self->{after_score_time}+=time()-$time if ($DEBUG);
267  
268 }
269 }
270 }
271  
272 $time=time();
273 $self->align1x($LinkProb);
274  
275 # if ($ScoreComb eq 'log-linear'){ # special for log-linear:
276 # foreach $x (0..$#{$LinkProb}){ # reverse log (make positiv
277 # foreach $y (0..$#{$$LinkProb[$x]}){ # score values)
278 # $$LinkProb[$x][$y]=exp($$LinkProb[$x][$y]);
279 # }
280 # }
281 # }
282  
283 if ($self->parameter('verbose')){
284 $self->printClueMatrix($self->{token}->{source},
285 $self->{token}->{target},
286 $self->{matrix});
287  
288 $self->printBitextTokensWithID();
289  
290 # $self->printBitextToken($self->{token}->{source},
291 # $self->{token}->{target});
292  
293 }
294 ### DEBUG: store search time
295 $self->{'1x_score_time'}+=time()-$time if ($DEBUG);
296 }
297  
298  
299 #===========================================================================
300 #
301 # search for the best alignment using the clue matrix scores
302 #
303 # topLinkSearch ........ iteratively add top links to link clusters
304 # nextBestSearch ....... score = distance to next best link (+topLinkSearch)
305 # oneOneFirstSearch .... non-overlapping first, overlapping then
306 # competitiveSearch .... competitive linking (1:1 links only!)
307 # bidirectionalRefineSearch intersection of directional links + overlapping
308 # directionalSrcSearch ..... best alignment source --> target
309 # directionalTrgSearch ..... best alignment target --> source
310 # bidirectionalUnion ....... union of directionalSrc & directionalTrg
311 # bidirectionalIntersection intersection of directionalSrc & directionalTrg
312 #
313 # parameter search: nextbest ........ nextBestSearch
314 # oneone....... ... oneOneFirstSearch
315 # competitive ..... competitiveSearch
316 # myrefined ....... bidirectionalRefinedSearch
317 # och ............. bidirectionalRefinedSearchOch
318 # src ............. directionalSrcSearch
319 # trg ............. directionalTrgSearch
320 # union ........... bidirectionalUnion
321 # intersection .... bidirectionalIntersection
322 # <default> ....... topLinkSearch
323 #
324 #===========================================================================
325  
326  
327 sub findAlignment{
328 my $self=shift;
329 $self->{links}={};
330 my $minScore=$self->scoreThreshold();
331 my $method=$self->parameter('search');
332  
333 if ($method=~/nextbest/){
334 return $self->nextBestSearch($self->{links},$minScore);}
335 elsif ($method=~/competitive/){
336 return $self->competitiveSearch($self->{links},$minScore);}
337 elsif ($method=~/oneone/){
338 return $self->oneOneFirstSearch($self->{links},$minScore);}
339 elsif ($method=~/myrefined/){
340 return $self->bidirectionalRefinedSearch($self->{links},$minScore);}
341 elsif ($method=~/(och|refined)/){
342 return $self->bidirectionalRefinedSearchOch($self->{links},$minScore);}
343 elsif ($method=~/src/){
344 return $self->directionalSrcSearch($self->{links},$minScore);}
345 elsif ($method=~/trg/){
346 return $self->directionalTrgSearch($self->{links},$minScore);}
347 elsif ($method=~/union/){
348 return $self->bidirectionalUnion($self->{links},$minScore);}
349 elsif ($method=~/intersection/){
350 return $self->bidirectionalIntersection($self->{links},$minScore);}
351 else{
352 return $self->topLinkSearch($self->{links},$minScore);}
353 }
354  
355  
356  
357  
358  
359 #===========================================================================
360 # add scores to the clue matrix for
361 # sentence alignments with only 1 word in either source or target
362 #===========================================================================
363  
364  
365 sub align1x{
366 my $self=shift;
367 my ($LinkProb)=@_;
368 my $Align11=$self->parameter('align 1:1');
369 my $Align1x=$self->parameter('align 1:x');
370 if ($Align11 and ($#{$LinkProb}==0)){
371 if ($#{$$LinkProb[0]}==0){
372 my $p=$$LinkProb[0][0];
373 $$LinkProb[0][0]=$p+$Align11-$p*$Align11;
374 return;
375 }
376 }
377 if ($Align1x and ($#{$LinkProb}==0)){
378 foreach (0..$#{$$LinkProb[0]}){
379 my $p=$$LinkProb[0][$_];
380 $$LinkProb[0][$_]=$p+$Align1x-$p*$Align1x;
381 }
382 return;
383 }
384 if ($Align1x){
385 my $ok=1;
386 foreach (0..$#{$LinkProb}){
387 if ($#{$$LinkProb[$_]}!=0){$ok=0;}
388 }
389 if ($ok){
390 foreach (0..$#{$LinkProb}){
391 my $p=$$LinkProb[$_][0];
392 $$LinkProb[$_][0]=$p+$Align1x-$p*$Align1x;
393 }
394 }
395 }
396 }
397  
398 #===========================================================================
399 # add scores to the clue matrix for
400 # pairs of identical tokens with at least one non-alphabetical character
401 # (hard-coded as /[^A-Za-z]/ !!!!!!)
402 #===========================================================================
403  
404 sub alignIdentical{
405 my $self=shift;
406 my $AlignIdentical=$self->parameter('align identical');
407 if (not $AlignIdentical){return;}
408 my ($src,$trg,$s,$t,$LinkProb)=@_;
409 if ($src=~/[^A-Za-z]/){
410 if ($src eq $trg){
411 my @SrcTok=split(/:/,$s);
412 my @TrgTok=split(/:/,$t);
413 foreach my $x (@SrcTok){
414 foreach my $y (@TrgTok){
415 my $p=$$LinkProb[$x][$y];
416 $$LinkProb[$x][$y]=$p+$AlignIdentical-$p*$AlignIdentical;
417 }
418 }
419 }
420 }
421 }
422  
423  
424  
425  
426 #===========================================================================
427 #
428 # topLinkSearch:
429 # 1) search best link in the matrix
430 # 2) add link to link clusters
431 # 3) continue with 1) until finished
432 #
433 #===========================================================================
434  
435 sub topLinkSearch{
436 my $self=shift;
437 my $Links=shift;
438 my $MinScore=shift;
439  
440 my $LinkProb=$self->{matrix};
441 my $Token=$self->{token};
442 my $TokenAttr=$self->{tokenAttr};
443  
444 my @SrcLinks;
445 my @TrgLinks;
446 my $NrSrc=$#{$$Token{source}};
447 my $NrTrg=$#{$$Token{target}};
448  
449 my @LinkMatrix;
450 my @LinkCluster;
451 my ($x,$y);
452  
453  
454 # ----------------------------
455  
456 # print STDERR "---------new sentence-------$MinScore-------\n";
457 undef $self->{SORTEDLINKS};
458  
459 $self->cloneLinkMatrix($LinkProb,\@LinkMatrix); # clone the matrix
460  
461 while (($x,$y)=$self->getTopLink(\@LinkMatrix,$MinScore)){
462 # print STDERR "$x:$y:$LinkMatrix[$x][$y]\n";
463 if ($MinScore=~/\%/){
464 $MinScore=$LinkMatrix[$x][$y]*$MinScore/100;
465 # print STDERR "## minscore == $MinScore\n";
466 }
467 if (not defined($LinkMatrix[$x][$y])){last;}
468 if ($LinkMatrix[$x][$y]<$MinScore){last;}
469  
470 if ($self->add2LinkCluster($x,$y,\@LinkCluster)){
471 $LinkMatrix[$x][$y]=0;
472 }
473 }
474  
475  
476 # ----------------------------
477 # get the links from the set of link clusters
478  
479 $self->getClusterLinks(\@LinkCluster,$Links); # get links
480 }
481  
482  
483  
484  
485 #===========================================================================
486 #
487 # nextBestSearch:
488 # 1) find score distance to "next best link" for each word pair
489 # 2) call topLinkSearch
490 #
491 #===========================================================================
492  
493  
494  
495 sub nextBestSearch{
496 my $self=shift;
497 my $LinkProb=$self->{matrix};
498 $self->nextBestMatrix($LinkProb);
499 return $self->topLinkSearch(@_);
500 }
501  
502  
503 sub nextBestMatrix{
504 my $self=shift;
505 my ($LinkProb)=@_;
506  
507 my @SortedColumns=();
508 my @SortedRows=();
509  
510 my $sizeX=$#{$LinkProb};
511 my $sizeY=$#{$$LinkProb[0]};
512  
513 foreach my $x (0..$sizeX){
514 @{$SortedColumns[$x]}=
515 sort {$$LinkProb[$x][$b] <=> $$LinkProb[$x][$a]} (0..$sizeY);
516 }
517 foreach my $y (0..$sizeY){
518 @{$SortedRows[$y]}=
519 sort {$$LinkProb[$b][$y] <=> $$LinkProb[$a][$y]} (0..$sizeX);
520 }
521  
522 my @LinkMatrix=();
523 $self->cloneLinkMatrix($LinkProb,\@LinkMatrix);
524  
525 my $lowest=0;
526  
527 foreach my $x (0..$sizeX){
528 foreach my $y (0..$sizeY){
529 my $NextBestY=$SortedColumns[$x][0];
530 if ($NextBestY==$y){$NextBestY=$SortedColumns[$x][1];}
531 my $NextBestX=$SortedRows[$y][0];
532 if ($NextBestX==$x){$NextBestX=$SortedRows[$y][1];}
533 my $NextBest=$LinkMatrix[$NextBestX][$y];
534 if ($LinkMatrix[$x][$NextBestY]>$NextBest){
535 $NextBest=$LinkMatrix[$x][$NextBestY];
536 }
537 $$LinkProb[$x][$y]-=$NextBest;
538 if ($$LinkProb[$x][$y]<$lowest){
539 $lowest=$$LinkProb[$x][$y];
540 }
541 }
542 }
543 foreach my $x (0..$sizeX){ # normalize!
544 foreach my $y (0..$sizeY){ # no negative values
545 $$LinkProb[$x][$y]-=$lowest; # in the matrix!
546 }
547 }
548 if ($self->parameter('verbose')){
549 $self->printClueMatrix($self->{token}->{source},
550 $self->{token}->{target},
551 $LinkProb);
552 }
553 }
554  
555  
556  
557 #===========================================================================
558 #
559 # oneOneFirstSearch:
560 # 1) find all one-to-one word links first (non-overlapping links)
561 # 2) add iteratively overlapping links
562 #
563 #===========================================================================
564  
565 sub oneOneFirstSearch{
566 my $self=shift;
567 my $Links=shift;
568 my $MinScore=shift;
569  
570 my $LinkProb=$self->{matrix};
571 my $Token=$self->{token};
572 my $TokenAttr=$self->{tokenAttr};
573  
574 my @SrcLinks;
575 my @TrgLinks;
576 my $NrSrc=$#{$$Token{source}};
577 my $NrTrg=$#{$$Token{target}};
578  
579 my @LinkMatrix;
580 my @LinkCluster;
581 my ($x,$y);
582  
583  
584 # ----------------------------
585 # 1) get all word-to-word links without any overlaps
586  
587 $self->cloneLinkMatrix($LinkProb,\@LinkMatrix); # clone the matrix
588  
589 while (($x,$y)=$self->getTopLink(\@LinkMatrix,$MinScore)){
590 if ($MinScore=~/\%/){
591 $MinScore=$LinkMatrix[$x][$y]*$MinScore/100;
592 print STDERR "## minscore == $MinScore\n";
593 }
594 if ($LinkMatrix[$x][$y]<$MinScore){last;}
595 my @overlap=$self->findClusterOverlap($x,$y,\@LinkCluster);
596  
597 if (not @overlap){
598 $LinkCluster[$#LinkCluster+1]={};
599 $LinkCluster[-1]{src}{$x}=1;
600 $LinkCluster[-1]{trg}{$y}=1;
601 }
602 $LinkMatrix[$x][$y]=0;
603 }
604  
605 # ----------------------------
606 # 2) do it again --> find overlapping links!
607  
608 $self->cloneLinkMatrix($LinkProb,\@LinkMatrix); # clone the matrix
609  
610 while (($x,$y)=$self->getTopLink(\@LinkMatrix,$MinScore)){
611 if ($LinkMatrix[$x][$y]<$MinScore){last;}
612 $self->add2LinkCluster($x,$y,\@LinkCluster);
613 $LinkMatrix[$x][$y]=0;
614 }
615  
616  
617 # ----------------------------
618 # get the links from the set of link clusters
619  
620 $self->getClusterLinks(\@LinkCluster,$Links); # get links
621 }
622  
623  
624  
625  
626 #===========================================================================
627 # ------------------ directional alignment (source to target) ----------------
628 #===========================================================================
629  
630 sub directionalSrcSearch{
631 my $self=shift;
632 my $Links=shift;
633 my $MinScore=shift;
634 my $competitive=shift;
635  
636 my @LinkCluster;
637 my ($x,$y);
638  
639 my @SrcLinks=$self->bestSrcLinks($MinScore,$competitive);
640  
641 foreach (0..$#SrcLinks){
642 if ((defined $SrcLinks[$_]) and
643 ($SrcLinks[$_] > 0)){
644 $self->add2LinkCluster($_,$SrcLinks[$_],\@LinkCluster);
645 }
646 }
647  
648 $self->getClusterLinks(\@LinkCluster,$Links);
649 }
650  
651 #===========================================================================
652 # ------------------ directional alignment (target to source ) ---------------
653 #===========================================================================
654  
655 sub directionalTrgSearch{
656 my $self=shift;
657 my $Links=shift;
658 my $MinScore=shift;
659 my $competitive=shift;
660  
661 my @LinkCluster;
662 my ($x,$y);
663  
664 my @TrgLinks=$self->bestTrgLinks($MinScore,$competitive);
665 foreach (0..$#TrgLinks){
666 if ((defined $TrgLinks[$_]) and
667 ($TrgLinks[$_] > 0)){
668 $self->add2LinkCluster($TrgLinks[$_],$_,\@LinkCluster);
669 }
670 }
671  
672 $self->getClusterLinks(\@LinkCluster,$Links);
673 }
674  
675  
676 #===========================================================================
677 # competitive linking
678 # 1) get best word-to-word link (s,t)
679 # 2) remove alternative links for (s) and for (t)
680 # 3) go to 1) until finished
681 #===========================================================================
682  
683 sub competitiveSearch{
684 my $self=shift;
685 my $Links=shift;
686 my $MinScore=shift;
687 if (not defined $MinScore){
688 $MinScore=0.00000000000001;
689 }
690  
691 my $Token=$self->{token};
692 my $NrSrc=$#{$$Token{source}};
693 my $NrTrg=$#{$$Token{target}};
694  
695 my @WordLinks=();
696 if ($NrTrg>$NrSrc){
697 return $self->directionalTrgSearch($Links,$MinScore,1);
698 }
699 return $self->directionalSrcSearch($Links,$MinScore,1);
700 }
701  
702 #===========================================================================
703 # refined symmetric link search a la Och&Ney
704 #
705 #===========================================================================
706  
707 sub bidirectionalRefinedSearchOch{
708 my $self=shift;
709 my $Links=shift;
710 my $MinScore=shift;
711 my $competitive=shift;
712 if (not defined $MinScore){
713 $MinScore=0.00000000000001;
714 }
715  
716 my $LinkProb=$self->{matrix};
717 my @LinkCluster;
718 my %WordLinks=();
719 my %InvWordLinks=();
720 my ($x,$y);
721  
722 #-----------------------------------
723 # 1) get directional links
724  
725 my @SrcLinks=$self->bestSrcLinks($MinScore,$competitive);
726 my @TrgLinks=$self->bestTrgLinks($MinScore,$competitive);
727  
728 #-----------------------------------
729 # 2) intersection of directional links
730  
731 foreach (0..$#SrcLinks){
732 if ((defined $SrcLinks[$_]) and
733 ($TrgLinks[$SrcLinks[$_]] eq $_)){
734 $WordLinks{$_}{$SrcLinks[$_]}=1;
735 $InvWordLinks{$SrcLinks[$_]}{$_}=1;
736 # print STDERR "$_ --> $SrcLinks[$_]\n";
737 }
738 }
739  
740  
741 #-----------------------------------
742 # 3) add overlapping links
743 # * sort all scores in the matrix
744 # * run through possible links starting with the highest score
745 # * repeat until no more links can be added
746 #
747 # links (s,t) are added if
748 # * there is no other link for both, s AND t
749 # * or ..the new link is adjacent to another link in source OR target
750 # and thew new link does not create links which have neighbors
751 # in both directions
752  
753 my %scores=();
754 foreach my $s (0..$#{$LinkProb}){
755 foreach my $t (0..$#{$$LinkProb[$s]}){ # put all scores
756 $scores{"$s:$t"}=$$LinkProb[$s][$t]; # in a long list
757 }
758 }
759  
760 my $added=0;
761 do{
762 $added=0;
763 foreach my $pair (sort {$scores{$b} <=> $scores{$a} } keys %scores){
764 if ($scores{$pair}<$MinScore){last;}
765 my ($s,$t)=split(/\:/,$pair);
766  
767 if (((not defined $WordLinks{$s}) or # if no other links
768 (not keys %{$WordLinks{$s}})) and # are defined for both,
769 ((not defined $InvWordLinks{$t}) or # source AND target
770 (not keys %{$InvWordLinks{$t}}))){ # word:
771 $added++;
772 $scores{$pair}=0; # add the link
773 $WordLinks{$s}{$t}=1;
774 $InvWordLinks{$t}{$s}=1;
775 # print STDERR "add $s --> $t (new)\n";
776 }
777 elsif ((($s>0) and
778 (defined $WordLinks{$s-1}{$t})) or # the link has a
779 (defined $WordLinks{$s+1}{$t}) or # vertical neighbor
780 (($t>0) and
781 (defined $WordLinks{$s}{$t-1})) or # or a
782 (defined $WordLinks{$s}{$t+1})){ # horizontal neighbor
783  
784 $InvWordLinks{$t}{$s}=1;
785 $WordLinks{$s}{$t}=1; # if there are
786 if (&CheckWordLinks(\%WordLinks, # no links with
787 \%InvWordLinks)){ # neighbors in both
788 $added++; # dimensions! -->
789 $scores{$pair}=0; # add the new link
790 # print STDERR "add $s --> $t (adj)\n";
791 }
792 else{ # else:
793 delete $WordLinks{$s}{$t}; # delete the link
794 delete $InvWordLinks{$t}{$s};
795 # print STDERR "reject $s --> $t\n";
796 }
797 }
798 }
799 }
800 until (not $added); # repeat as long as links are added!
801  
802 $self->setParameter('adjacent_only',0);
803 $self->setParameter('adjacent_score',0);
804  
805 foreach my $s (keys %WordLinks){ # put word-to-word
806 foreach my $t (keys %{$WordLinks{$s}}){ # links together
807 $self->add2LinkCluster($s,$t,\@LinkCluster); # (link clusters)
808 }
809 }
810  
811  
812 #-----------------------------------
813 # 4) convert link cluster to word/phrase links
814  
815 $self->getClusterLinks(\@LinkCluster,$Links);
816 }
817  
818 #-------------------------------------------------------------------------
819 # check if there are alignments containing horicontal AND vertical links
820 # (---> return 0 if there are such links!)
821  
822 sub CheckWordLinks{
823 my $srclinks=shift;
824 my $trglinks=shift;
825  
826 foreach my $s (keys %{$srclinks}){
827 foreach my $t (keys %{$$srclinks{$s}}){
828 if (keys %{$$srclinks{$s}} > 1){
829 if (keys %{$$trglinks{$t}} > 1){
830 return 0;
831 }
832 }
833 }
834 }
835 return 1;
836 }
837  
838  
839 #===========================================================================
840 # symmetric alignment (bi-directional)
841 # 1) get links in both directions
842 # 2) get intersection of links
843 # 3) iteratively add new links to existing link clusters
844 #===========================================================================
845  
846  
847 sub bidirectionalRefinedSearch{
848 my $self=shift;
849 my $Links=shift;
850 my $MinScore=shift;
851 my $competitive=shift;
852 if (not defined $MinScore){
853 $MinScore=0.00000000000001;
854 }
855  
856 my $LinkProb=$self->{matrix};
857 my @LinkCluster;
858 my ($x,$y);
859  
860 #-----------------------------------
861 # 1) get directional links
862  
863 my @SrcLinks=$self->bestSrcLinks($MinScore,$competitive);
864 my @TrgLinks=$self->bestTrgLinks($MinScore,$competitive);
865  
866 #-----------------------------------
867 # 2) intersection of directional links
868  
869 foreach (0..$#SrcLinks){
870 if ((defined $SrcLinks[$_]) and
871 ($TrgLinks[$SrcLinks[$_]] eq $_)){
872 $self->add2LinkCluster($_,$SrcLinks[$_],
873 \@LinkCluster); # (link clusters)
874 }
875 }
876  
877  
878 #-----------------------------------
879 # 3) add overlapping links
880 # * sort all scores in the matrix
881 # * run through possible links starting with the highest score
882 # * repeat until no more links can be added
883 #
884 # links (s,t) are added if
885 # * there is no other link for both, s AND t
886 # * or ..the new link is adjacent to another link in source OR target
887 # and thew new link does not create links which have neighbors
888 # in both directions
889  
890 my %scores=();
891 foreach my $s (0..$#{$LinkProb}){
892 foreach my $t (0..$#{$$LinkProb[$s]}){ # put all scores
893 $scores{"$s:$t"}=$$LinkProb[$s][$t]; # in a long list
894 }
895 }
896  
897 my $added=0;
898 do{
899 $added=0;
900 foreach my $pair (sort {$scores{$b} <=> $scores{$a} } keys %scores){
901 if ($scores{$pair}<$MinScore){last;}
902 my ($s,$t)=split(/\:/,$pair);
903  
904 if ($self->add2LinkCluster($s,$t,\@LinkCluster)){
905 $added++;
906 delete $scores{$pair};
907 }
908 }
909 }
910 until (not $added); # repeat as long as links are added!
911  
912 #-----------------------------------
913 # 4) convert link cluster to word/phrase links
914  
915 $self->getClusterLinks(\@LinkCluster,$Links);
916 }
917  
918  
919  
920  
921 # ------------------ bi-directional alignment (union) ------------------
922 #
923 # union of links in both diretions
924 #
925  
926 sub bidirectionalUnion{
927 my $self=shift;
928 my $Links=shift;
929 my $MinScore=shift;
930 my $competitive=shift;
931  
932 my @LinkCluster;
933 my ($x,$y);
934  
935 my @SrcLinks=$self->bestSrcLinks($MinScore,$competitive);
936 foreach (0..$#SrcLinks){
937 if (defined $SrcLinks[$_]){
938 $self->add2LinkCluster($_,$SrcLinks[$_],\@LinkCluster);
939 }
940 }
941 my @TrgLinks=$self->bestTrgLinks($MinScore,$competitive);
942 foreach (0..$#TrgLinks){
943 if (defined $TrgLinks[$_]){
944 $self->add2LinkCluster($TrgLinks[$_],$_,\@LinkCluster);
945 }
946 }
947  
948 $self->getClusterLinks(\@LinkCluster,$Links);
949 }
950  
951  
952 # ------------------ bi-directional alignment (intersection) -------------
953 #
954 # intersection of links in both directions
955 #
956  
957 sub bidirectionalIntersection{
958 my $self=shift;
959 my $Links=shift;
960 my $MinScore=shift;
961 my $competitive=shift;
962  
963 my @LinkCluster;
964 my ($x,$y);
965  
966 my @SrcLinks=$self->bestSrcLinks($MinScore,$competitive);
967 my @TrgLinks=$self->bestTrgLinks($MinScore,$competitive);
968  
969 foreach (0..$#SrcLinks){
970 if ((defined $SrcLinks[$_]) and
971 ($TrgLinks[$SrcLinks[$_]] eq $_)){
972 $self->add2LinkCluster($_,$SrcLinks[$_],\@LinkCluster);
973 $SrcLinks[$_]=undef;
974 $TrgLinks[$SrcLinks[$_]]=undef;
975 }
976 }
977  
978 $self->getClusterLinks(\@LinkCluster,$Links);
979 }
980  
981  
982  
983  
984  
985  
986  
987  
988  
989  
990  
991 # ------------------------------------
992 # get best links from source to target words
993  
994 sub bestSrcLinks{
995 my $self=shift;
996 my $MinScore=shift; # score threshold
997 my $competitive=shift; # enable/disable competive linking
998  
999 if ($competitive){
1000 return $self->competitiveSrcLinks($MinScore,@_);
1001 }
1002  
1003 my $LinkProb=$self->{matrix};
1004 my $Token=$self->{token};
1005 my $NrSrc=$#{$$Token{source}};
1006 my $NrTrg=$#{$$Token{target}};
1007  
1008 my @Links=();
1009  
1010 # ----------------------------
1011 my @LinkMatrix=();
1012 $self->cloneLinkMatrix($LinkProb,\@LinkMatrix);
1013 # ----------------------------
1014  
1015 foreach my $s (0..$NrSrc){
1016 my $bestLink=0;
1017 my $bestScore=$LinkMatrix[$s][$bestLink];
1018 foreach my $t (1..$NrTrg){
1019 if ($LinkMatrix[$s][$t]>$bestScore){
1020 $bestLink=$t;
1021 $bestScore=$LinkMatrix[$s][$bestLink];
1022 }
1023 }
1024 if ($LinkMatrix[$s][$bestLink]<$MinScore){next;}
1025 # if ($LinkMatrix[$s][$bestLink]<$MinScore){last;}
1026 $Links[$s]=$bestLink;
1027 }
1028  
1029 return @Links;
1030 }
1031  
1032 # ------------------------------------
1033 # get best links from target to source words
1034  
1035 sub bestTrgLinks{
1036 my $self=shift;
1037 my $MinScore=shift; # score threshold
1038 my $competitive=shift; # enable/disable competive linking
1039  
1040 if ($competitive){
1041 return $self->competitiveTrgLinks($MinScore,@_);
1042 }
1043  
1044 my $LinkProb=$self->{matrix};
1045 my $Token=$self->{token};
1046 my $NrSrc=$#{$$Token{source}};
1047 my $NrTrg=$#{$$Token{target}};
1048  
1049 my @Links=();
1050  
1051 # ----------------------------
1052 my @LinkMatrix=();
1053 $self->cloneLinkMatrix($LinkProb,\@LinkMatrix);
1054 # ----------------------------
1055  
1056 foreach my $t (0..$NrTrg){
1057 my $bestLink=0;
1058 my $bestScore=$LinkMatrix[$bestLink][$t];
1059 foreach my $s (1..$NrSrc){
1060 if ($LinkMatrix[$s][$t]>$bestScore){
1061 $bestLink=$s;
1062 $bestScore=$LinkMatrix[$bestLink][$t];
1063 }
1064 }
1065 if ($LinkMatrix[$bestLink][$t]<$MinScore){next;}
1066 # if ($LinkMatrix[$bestLink][$t]<$MinScore){last;}
1067 $Links[$t]=$bestLink;
1068 }
1069 return @Links;
1070 }
1071  
1072  
1073 # ------------------------------------
1074 # competitive linking from source to target
1075  
1076  
1077 sub competitiveSrcLinks{
1078 my $self=shift;
1079 my $MinScore=shift; # score threshold
1080  
1081 my $LinkProb=$self->{matrix};
1082 my $Token=$self->{token};
1083 my $NrSrc=$#{$$Token{source}};
1084 my $NrTrg=$#{$$Token{target}};
1085 my @Links=();
1086  
1087 # ----------------------------
1088 my @LinkMatrix=();
1089 $self->cloneLinkMatrix($LinkProb,\@LinkMatrix);
1090 # ----------------------------
1091  
1092 my ($s,$t);
1093 while (($s,$t)=$self->getTopLink(\@LinkMatrix,$MinScore)){
1094 if ($LinkMatrix[$s][$t]<$MinScore){next;}
1095 $LinkMatrix[$s][$t]=0;
1096  
1097 $Links[$s]=$t;
1098  
1099 foreach my $x (0..$NrSrc){$LinkMatrix[$x][$t]=0;}
1100 foreach my $x (0..$NrTrg){$LinkMatrix[$s][$x]=0;}
1101 }
1102 return @Links;
1103 }
1104  
1105 # ------------------------------------
1106 # competitive linking from target to source
1107  
1108 sub competitiveTrgLinks{
1109 my $self=shift;
1110 my $MinScore=shift; # score threshold
1111  
1112 my $LinkProb=$self->{matrix};
1113 my $Token=$self->{token};
1114 my $NrSrc=$#{$$Token{source}};
1115 my $NrTrg=$#{$$Token{target}};
1116 my @Links=();
1117  
1118 # ----------------------------
1119 my @LinkMatrix=();
1120 $self->cloneLinkMatrix($LinkProb,\@LinkMatrix);
1121 # ----------------------------
1122  
1123 my ($s,$t);
1124 while (($s,$t)=$self->getTopLink(\@LinkMatrix,$MinScore)){
1125 if ($LinkMatrix[$s][$t]<$MinScore){next;}
1126 $LinkMatrix[$s][$t]=0;
1127  
1128 $Links[$t]=$s;
1129  
1130 foreach my $x (0..$NrSrc){$LinkMatrix[$x][$t]=0;}
1131 foreach my $x (0..$NrTrg){$LinkMatrix[$s][$x]=0;}
1132 }
1133 return @Links;
1134 }
1135  
1136  
1137 #==========================================================================
1138 #
1139 # get the word-to-word link with the highest score from the clue matrix
1140 #
1141 #==========================================================================
1142  
1143 sub getTopLink{
1144 my $self=shift;
1145 my $LinkProb=shift;
1146 my $MinScore=shift;
1147  
1148 my $bestX=undef;
1149 my $bestY=undef;
1150 my $bestVal;
1151  
1152 if (not ref($self->{SORTEDLINKS})){
1153 $self->sortLinks($LinkProb,$MinScore);
1154 }
1155 my $top=shift @{$self->{SORTEDLINKS}};
1156 if (not defined $top){
1157 delete $self->{SORTEDLINKS};
1158 }
1159 my @link=split (':',$top);
1160 return @link;
1161 }
1162  
1163 sub sortLinks{
1164 my $self=shift;
1165 my $LinkProb=shift;
1166 my $MinScore=shift;
1167 $self->{ALLLINKS}={};
1168 foreach my $x (0..$#{$LinkProb}){
1169 foreach my $y (0..$#{$$LinkProb[$x]}){
1170 if ($$LinkProb[$x][$y]<$MinScore){next;}
1171 if ($$LinkProb[$x][$y]<=0){next;}
1172 $self->{ALLLINKS}->{"$x:$y"}=$$LinkProb[$x][$y];
1173 }
1174 }
1175 @{$self->{SORTEDLINKS}}=
1176 sort {$self->{ALLLINKS}->{$b} <=> $self->{ALLLINKS}->{$a}}
1177 keys %{$self->{ALLLINKS}};
1178 }
1179  
1180 sub getTopLinkOld{
1181 my $self=shift;
1182 my $LinkProb=shift;
1183  
1184 my $bestX=undef;
1185 my $bestY=undef;
1186 my $bestVal;
1187  
1188 foreach my $x (0..$#{$LinkProb}){
1189 my @sort = sort {$$LinkProb[$x][$b] <=> $$LinkProb[$x][$a]}
1190 (0..$#{$$LinkProb[$x]});
1191 if ($$LinkProb[$x][$sort[0]]>$bestVal){
1192 $bestVal=$$LinkProb[$x][$sort[0]];
1193 $bestX="$x";
1194 $bestY="$sort[0]";
1195 }
1196 }
1197 if ((defined $bestX) and (defined $bestY)){
1198 return ($bestX,$bestY);
1199 }
1200 else{
1201 return ();
1202 }
1203 }
1204  
1205 #==========================================================================
1206 #
1207 # getClusterLinks:
1208 # make word/phrase links out of link clusters
1209 # (add all necessary information for storing links,
1210 # e.g. token pairs, id's, byte spans)
1211 #
1212 #==========================================================================
1213  
1214  
1215 sub getClusterLinks{
1216 my $self=shift;
1217 my $LinkCluster=shift;
1218 my $Links=shift;
1219  
1220 my $LinkProb=$self->{matrix};
1221 my $TokenAttr=$self->{tokenAttr};
1222  
1223 if (ref($Links) ne 'HASH'){$Links={};}
1224  
1225 foreach (0..$#{$LinkCluster}){
1226 if (keys %{$$LinkCluster[$_]{src}}){
1227 if (keys %{$$LinkCluster[$_]{trg}}){
1228 my $src=join ':',sort {$a<=>$b} keys %{$$LinkCluster[$_]{src}};
1229 my $trg=join ':',sort {$a<=>$b} keys %{$$LinkCluster[$_]{trg}};
1230 my $score=$self->getMatrixScore($LinkProb,
1231 $$LinkCluster[$_]{src},
1232 $$LinkCluster[$_]{trg});
1233 my $link=$self->getLinkString($TokenAttr,$src,$trg);
1234  
1235 $$Links{$src}{link}=$link;
1236 $$Links{$src}{source}=
1237 $self->ngramIDs($src,$TokenAttr,'source');
1238 $$Links{$src}{target}=
1239 $self->ngramIDs($trg,$TokenAttr,'target');
1240 # my $span=$self->ngramSpans($src,$TokenAttr,'source');
1241 # if ($span){$$Links{$src}{src}=$span;}
1242 # $span=$self->ngramSpans($trg,$TokenAttr,'target');
1243 # if ($span){$$Links{$src}{trg}=$span;}
1244 $$Links{$src}{score}=$score;
1245 }
1246 }
1247 }
1248 return $Links;
1249 }
1250  
1251  
1252 sub getMatrixScore{
1253 my $self=shift;
1254 my ($matrix,$src,$trg)=@_;
1255 my $score=0;
1256 my $count;
1257 foreach my $s (keys %{$src}){
1258 foreach my $t (keys %{$trg}){
1259 if ($$matrix[$s][$t]>0){
1260 $score+=log($$matrix[$s][$t]);
1261 $count++;
1262 }
1263 }
1264 }
1265 if ($count){
1266 $score/=$count;
1267 }
1268 return exp($score);
1269 }
1270  
1271  
1272 #==========================================================================
1273 #
1274 # add links to link clusters
1275 #
1276 #==========================================================================
1277  
1278 sub add2LinkCluster{
1279 my $self=shift;
1280 my ($x,$y,$cluster)=@_;
1281 my @overlap=$self->findClusterOverlap($x,$y,$cluster);
1282 if ((not $self->parameter('allow_multiple_overlaps')) and (@overlap>1)){
1283 # print STDERR "disregard $x - $y (multi-overlap)!\n";
1284 return 0;
1285 }
1286 elsif (@overlap){
1287 if ($self->parameter('in_phrases_only')){
1288 if ($self->parameter('fill_phrases')){
1289 if (not $self->fillPhrases($x,$y,$cluster,$overlap[0])){
1290 # print STDERR "disregard $x - $y (fill phrase)!\n";
1291 return 0;
1292 }
1293 }
1294 if (not $self->isInPhrase($x,$y,$$cluster[$overlap[0]])){
1295 # print STDERR "disregard $x - $y (not in phrase)!\n";
1296 return 0;
1297 }
1298 }
1299 if ($self->parameter('adjacent_only')){
1300 if (not $self->isAdjacent($x,$y,$$cluster[$overlap[0]])){
1301 # print STDERR "disregard $x - $y (not adjacent)!\n";
1302 return 0;
1303 }
1304 }
1305 if ($self->parameter('adjacent_score')){
1306 if (not $self->isAdjacentScore($x,$y,$$cluster[$overlap[0]],
1307 $self->parameter('adjacent_score'))){
1308 #s print STDERR "disregard $x - $y (score difference to adjacent too big)!\n";
1309 return 0;
1310 }
1311 }
1312 $$cluster[$overlap[0]]{src}{$x}=1;
1313 $$cluster[$overlap[0]]{trg}{$y}=1;
1314 if (@overlap>1){ # join all overlapping
1315 foreach my $o (1..$#overlap){ # link clusters!
1316 foreach (keys %{$$cluster[$overlap[$o]]{src}}){
1317 delete $$cluster[$overlap[$o]]{src}{$_};
1318 $$cluster[$overlap[0]]{src}{$_}=1;
1319 }
1320 foreach (keys %{$$cluster[$overlap[$o]]{trg}}){
1321 delete $$cluster[$overlap[$o]]{trg}{$_};
1322 $$cluster[$overlap[0]]{trg}{$_}=1;
1323 }
1324 }
1325 }
1326 }
1327 else{
1328 $$cluster[$#{$cluster}+1]={};
1329 $$cluster[-1]{src}{$x}=1;
1330 $$cluster[-1]{trg}{$y}=1;
1331 }
1332 return 1;
1333 }
1334  
1335  
1336 sub isInPhrase{
1337 my $self=shift;
1338 my ($newX,$newY,$cluster)=@_;
1339 my @srcAccepted=keys %{$self->{srcToken}};
1340 my @trgAccepted=keys %{$self->{trgToken}};
1341  
1342 my %src=%{$cluster->{src}};
1343 my %trg=%{$cluster->{trg}};
1344 $src{$newX}=1;
1345 $trg{$newY}=1;
1346  
1347 # my $srcPhr=join ':',sort {$a <=> $b} keys %src;
1348 # my $trgPhr=join ':',sort {$a <=> $b} keys %trg;
1349  
1350 my $srcPhr=join '(:[0-9]+)?:',sort {$a <=> $b} keys %src;
1351 my $trgPhr=join '(:[0-9]+)?:',sort {$a <=> $b} keys %trg;
1352  
1353 if (grep(/$srcPhr/,@srcAccepted)){
1354 if (grep(/$trgPhr/,@trgAccepted)){
1355 # my @missing=$self->getMissingTokens(\%src,\%trg);
1356 return 1;
1357 }
1358 }
1359 return 0;
1360 }
1361  
1362 sub fillPhrases{
1363 my $self=shift;
1364 my ($newX,$newY,$cluster,$nr)=@_;
1365  
1366 my %link=();
1367 %{$link{src}}=%{$cluster->[$nr]->{src}};
1368 %{$link{trg}}=%{$cluster->[$nr]->{trg}};
1369 $link{src}{$newX}=1;
1370 $link{trg}{$newY}=1;
1371  
1372 my @missing=$self->getMissingTokens($link{src},$link{trg});
1373 if (not @missing){
1374 return 0;
1375 }
1376 my @missSrc=split(/:/,$missing[0]);
1377 my @missTrg=split(/:/,$missing[1]);
1378 my %overlap=();
1379 foreach my $s (@missSrc){
1380 $self->findSrcOverlap($s,$cluster,\%overlap);
1381 $link{src}{$s}=1;
1382 }
1383 foreach my $t (@missTrg){
1384 $self->findTrgOverlap($t,$cluster,\%overlap);
1385 $link{trg}{$t}=1;
1386 }
1387 foreach (keys %overlap){
1388 if (not $self->isIncluded($cluster->[$_],\%link)){
1389 foreach (@missSrc){delete $link{src}{$_};}
1390 foreach (@missTrg){delete $link{trg}{$_};}
1391 return 0;
1392 }
1393  
1394 ############# !!!!!!!!!!!!!! change this:
1395 print STDERR "delete cluster $_!\n";
1396 $cluster->[$_]->{src}=();
1397 $cluster->[$_]->{trg}=();
1398 ############# !!!!!!!!!!!!!! change this:
1399  
1400 }
1401  
1402 if (@missSrc or @missTrg){ # ... just for information
1403 print STDERR "fill cluster $nr with missing tokens!\n";
1404 }
1405  
1406 foreach (keys %{$link{src}}){
1407 $cluster->[$nr]->{src}->{$_}=1;
1408 }
1409 foreach (keys %{$link{trg}}){
1410 $cluster->[$nr]->{trg}->{$_}=1;
1411 }
1412 return 1;
1413 }
1414  
1415  
1416 #sub removeClusterInclusions{
1417 # my $self=shift;
1418 # my $cluster=shift;
1419 # foreach my $c (@{$cluster}){
1420 # my $src=join '(:[0-9]+)?:',sort {$a <=> $b} keys %{$$cluster[$c]{src}};
1421 # my $trg=join '(:[0-9]+)?:',sort {$a <=> $b} keys %{$$cluster[$c]{trg}};
1422 # }
1423 #}
1424  
1425  
1426 sub isIncluded{
1427 my $self=shift;
1428 my ($cluster1,$cluster2)=@_;
1429 foreach (keys %{$cluster1->{src}}){
1430 if (not defined $cluster2->{src}->{$_}){return 0;}
1431 }
1432 foreach (keys %{$cluster1->{trg}}){
1433 if (not defined $cluster2->{trg}->{$_}){return 0;}
1434 }
1435 return 1;
1436 }
1437  
1438 sub findSrcOverlap{
1439 my $self=shift;
1440 return $self->findOverlap('src',@_);
1441 }
1442 sub findTrgOverlap{
1443 my $self=shift;
1444 return $self->findOverlap('trg',@_);
1445 }
1446  
1447 sub findOverlap{
1448 my $self=shift;
1449 my ($lang,$token,$cluster,$overlap)=@_;
1450 my @c=grep (defined $$cluster[$_]{$lang}{$token},0..$#{$cluster});
1451 foreach (@c){
1452 $$overlap{$_}=1;
1453 }
1454 }
1455  
1456 sub getMissingTokens{
1457 my $self=shift;
1458 my ($src,$trg)=@_;
1459 my @srcAccepted=keys %{$self->{srcToken}};
1460 my @trgAccepted=keys %{$self->{trgToken}};
1461  
1462 my $srcPhr=join '(:[0-9]+)?:',sort {$a <=> $b} keys %{$src};
1463 my $trgPhr=join '(:[0-9]+)?:',sort {$a <=> $b} keys %{$trg};
1464  
1465 my $missingSrc=undef;
1466 my $missingTrg=undef;
1467  
1468 my @match;
1469  
1470 if (@match=grep(/$srcPhr/,@srcAccepted)){
1471  
1472 @match=sort {length($a) <=> length($b)} @match;
1473 if ($match[0]=~/^(.*)$srcPhr(.*)$/){
1474 $missingSrc="$1$2$3$4$5$6$7$8$9";
1475 }
1476  
1477 if (@match=grep(/$trgPhr/,@trgAccepted)){
1478  
1479 @match=sort {length($a) <=> length($b)} @match;
1480 if ($match[0]=~/^(.*)$trgPhr(.*)$/){
1481 $missingTrg="$1$2$3$4$5$6$7$8$9";
1482 }
1483 $missingSrc=~s/^://;$missingSrc=~s/:$//;
1484 $missingTrg=~s/^://;$missingTrg=~s/:$//;
1485 return ($missingSrc,$missingTrg);
1486 }
1487 }
1488  
1489 return ();
1490 }
1491  
1492  
1493 sub isAdjacent{
1494 my $self=shift;
1495 my ($x,$y,$cluster)=@_;
1496 if ((defined $$cluster{src}{$x}) and
1497 ((defined $$cluster{trg}{$y-1}) or
1498 ((defined $$cluster{trg}{$y+1})))){
1499 return 1;
1500 }
1501 if ((defined $$cluster{trg}{$y}) and
1502 ((defined $$cluster{src}{$x-1}) or
1503 ((defined $$cluster{src}{$x+1})))){
1504 return 1;
1505 }
1506 return 0;
1507 }
1508  
1509 sub isAdjacentScore{
1510 my $self=shift;
1511 my ($x,$y,$cluster,$p)=@_;
1512  
1513 if ((defined $$cluster{src}{$x}) and
1514 (defined $$cluster{trg}{$y-1})){
1515 if ($self->{matrix}->[$x]->[$y]>=$self->{matrix}->[$x]->[$y-1]*$p){
1516 return 1;
1517 }
1518 return 0;
1519 }
1520 if ((defined $$cluster{src}{$x}) and
1521 (defined $$cluster{trg}{$y+1})){
1522 if ($self->{matrix}->[$x]->[$y]>=$self->{matrix}->[$x]->[$y+1]*$p){
1523 return 1;
1524 }
1525 return 0;
1526 }
1527 if ((defined $$cluster{src}{$x-1}) and
1528 (defined $$cluster{trg}{$y})){
1529 if ($self->{matrix}->[$x]->[$y]>=$self->{matrix}->[$x-1]->[$y]*$p){
1530 return 1;
1531 }
1532 return 0;
1533 }
1534 if ((defined $$cluster{src}{$x+1}) and
1535 (defined $$cluster{trg}{$y})){
1536 if ($self->{matrix}->[$x]->[$y]>=$self->{matrix}->[$x+1]->[$y]*$p){
1537 return 1;
1538 }
1539 return 0;
1540 }
1541 return 0;
1542 }
1543  
1544  
1545 sub findClusterOverlap{
1546 my $self=shift;
1547 my ($x,$y,$cluster)=@_;
1548 my @overlap=();
1549 foreach (0..$#{$cluster}){
1550 if (defined $$cluster[$_]{src}{$x}){
1551 push(@overlap,$_);
1552 }
1553 elsif (defined $$cluster[$_]{trg}{$y}){
1554 push(@overlap,$_);
1555 }
1556 }
1557 return @overlap;
1558 }
1559  
1560  
1561  
1562 #========================================================================
1563  
1564 sub cloneLinkMatrix{
1565 my $self=shift;
1566 my $matrix=shift;
1567 my $clone=shift;
1568  
1569 if (ref($matrix) ne 'ARRAY'){return ();}
1570 if (ref($clone) ne 'ARRAY'){$clone=[];}
1571  
1572 foreach my $x (0..$#{$matrix}){
1573 foreach my $y (0..$#{$$matrix[$x]}){
1574 $$clone[$x][$y]=$$matrix[$x][$y];
1575 }
1576 }
1577 return $clone;
1578 }
1579  
1580  
1581  
1582  
1583 #==========================================================================
1584 #
1585 #
1586 #
1587 #==========================================================================
1588  
1589  
1590  
1591 sub clueMatrixToHtml{
1592 my $self=shift;
1593  
1594 my $Matrix=$self->{matrix};
1595 my $Token=$self->{token};
1596 my $SrcTok=$$Token{source};
1597 my $TrgTok=$$Token{target};
1598 my $nrSrc=$#{$$Token{source}};
1599 my $nrTrg=$#{$$Token{target}};
1600  
1601 my $max;
1602 foreach my $s (0..$nrSrc){
1603 foreach my $t (0..$nrTrg){
1604 if ($Matrix->[$s]->[$t]>$max){$max=$Matrix->[$s]->[$t];}
1605 }
1606 }
1607 if (not $max){$max=1;}
1608  
1609 my $html="<p>\n";
1610 $html.="<table border=\"0\" cellpadding=\"0\" cellspacing=\"0\">\n";
1611 $html.="<tr><th></th>\n";
1612  
1613 foreach my $t (0..$nrTrg){
1614 my $str=$TrgTok->[$t];
1615 $html.="<th>$str</th>\n";
1616 }
1617  
1618 foreach my $s (0..$nrSrc){
1619 $html.="</tr><tr>\n";
1620 my $str=$SrcTok->[$s];
1621 $html.="<th>$str</th>\n";
1622 foreach my $t (0..$nrTrg){
1623 my $score=0;
1624 if ($Matrix->[$s]){
1625 if ($Matrix->[$s]->[$t]){
1626 $score=$Matrix->[$s]->[$t];
1627 }
1628 }
1629 my $color=255-$score*256/$max;
1630 if ($color==-1){$color=0;}
1631 my $hex=sprintf("%X",$color);
1632 if (length($hex)<2){$hex="0$hex";}
1633 my $val=int(100*$score);
1634 if ($color<128){
1635 $html.="<td bgcolor=\"#$hex$hex$hex\">";
1636 $html.='<font color="#ffffff">';
1637 $html.="$val</font></td>\n";
1638 }
1639 else{
1640 $html.="<td bgcolor=\"#$hex$hex$hex\">";
1641 $html.="$val</td>\n";
1642 }
1643 }
1644 }
1645 $html.="</tr></table><hr>\n";
1646 return $html;
1647 }
1648  
1649  
1650  
1651 sub printHtmlClueMatrix{
1652 my $self=shift;
1653 print STDERR $self->clueMatrixToHtml();
1654 }
1655  
1656  
1657  
1658 sub printClueMatrix{
1659 my $self=shift;
1660  
1661 my ($SrcTok,$TrgTok,$Matrix)=@_;
1662  
1663 my $nrSrc=$#{$SrcTok};
1664 my $nrTrg=$#{$TrgTok};
1665  
1666  
1667 print STDERR "\n=====================================================\n";
1668 print STDERR "final clue matrix scores";
1669 print STDERR "\n=====================================================\n";
1670  
1671 foreach my $s (0..$nrSrc){
1672 foreach my $t (0..$nrTrg){
1673 my $score=$Matrix->[$s]->[$t];
1674 if ($score>0){
1675 # printf STDERR "[%2d-%-2d] %15s - %-15s: %s\n",
1676 printf STDERR "[%d %d] %20s - %-20s %s\n",
1677 $s,$t,$$SrcTok[$s],$$TrgTok[$t],$score;
1678 }
1679 }
1680 }
1681 print STDERR "\n=====================================================\n";
1682 print STDERR "clue matrix $nrSrc x $nrTrg";
1683 print STDERR "\n=====================================================\n";
1684  
1685 my @char=();
1686 &MakeCharArr($TrgTok,\@char);
1687 foreach my $c (0..$#char){
1688 printf STDERR "\n%10s",' ';
1689 foreach (@{$char[$c]}){
1690 printf STDERR "%4s",$_;
1691 }
1692 }
1693  
1694 print STDERR "\n";
1695  
1696 foreach my $s (0..$nrSrc){
1697 my $str=substr($SrcTok->[$s],0,10);
1698 $str=&Uplug::Encoding::convert($str,'utf-8','iso-8859-1');
1699  
1700 printf STDERR "%10s",$str;
1701 foreach my $t (0..$nrTrg){
1702 my $score=0;
1703 if ($Matrix->[$s]){
1704 if ($Matrix->[$s]->[$t]){
1705 $score=$Matrix->[$s]->[$t];
1706 }
1707 }
1708 printf STDERR " %3d",$score*100;
1709 }
1710 print STDERR "\n";
1711 }
1712 }
1713  
1714  
1715 sub MakeCharArr{
1716 my ($tok,$char)=@_;
1717  
1718 my @lat1=@{$tok};
1719  
1720 # my @lat1=();
1721 # foreach (0..$#{$tok}){
1722 # $lat1[$_]=&Uplug::Data::encode($tok->[$_],'utf-8','iso-8859-1');
1723 # }
1724  
1725 map ($lat1[$_]=&Uplug::Encoding::convert($lat1[$_],'utf-8','iso-8859-1'),
1726 (0..$#lat1));
1727  
1728 my $max=&MaxLength(\@lat1);
1729 foreach my $t (0..$#{$tok}){
1730 my @c=split(//,$lat1[$t]);
1731 foreach (1..$max){
1732 if (@c){
1733 $char->[$max-$_]->[$t]=pop(@c);
1734 # $char->[$max-$_]->[$t]=shift(@c);
1735 }
1736 else{$char->[$max-$_]->[$t]=' ';}
1737 }
1738 }
1739 }
1740  
1741 sub MaxLength{
1742 my ($tok)=@_;
1743 my $max=0;
1744 foreach (@{$tok}){
1745 if (length($_)>$max){$max=length($_);}
1746 }
1747 return $max;
1748 }
1749  
1750  
1751  
1752  
1753  
1754 ######### return a true value
1755  
1756 1;
1757