view release on metacpan or  search on metacpan

lib/Lingua/Align/LinkSearch.pm  view on Meta::CPAN

#-*-perl-*-

package Lingua::Align::LinkSearch;

=head1 NAME

Lingua::Align::LinkSearch - Search algorithms for tree alignment

=head1 SYNOPSIS

    my $aligner = new Lingua::Align::LinkSearch(-link_search => $type);
    $aligner->search(\%links,\@scores,$min_score,\@src,\@trg)

=head1 DESCRIPTION

Class factory for searching the best tree alignment based on local
link scores Various strategies have been implemented. Use the argument
C<-link_search> in the constructor to choose from the following
search strategies:

 threshold .............. greedy search with score thresholds
 assignment ............. bipartite graph matching (assignment problem)
 greedy ................. greedy search
 greedyWellformed ....... greedy search with well-formedness constraints
 greedyFinal ............ add step to link unlinked nodes (if wellformed)
 greedyFinalAnd ......... add step to link still unlinked nodes
 src2trg ................ source-to-target alignment (one link / source)
 trg2src ................ target-to-source alignment (one link / target)
 src2trgWellFormed ...... src2trg with wellformedness constraints
 intersection ........... intersection between src2trg and trg2src
 NTfirst ................ align non-terminals nodes first
 NTonly ................. align only non-terminals
 Tonly .................. align only termnal nodes
 PaCoMT ................. used in PaCoMT project
 cascaded ............... conbine search strategies (sequentially)

=cut

use 5.005;
use strict;

use FileHandle;
use Lingua::Align::LinkSearch::Threshold;
use Lingua::Align::LinkSearch::Greedy;
use Lingua::Align::LinkSearch::GreedyWellFormed;
use Lingua::Align::LinkSearch::GreedyFinal;
use Lingua::Align::LinkSearch::GreedyFinalAnd;
use Lingua::Align::LinkSearch::Src2Trg;
use Lingua::Align::LinkSearch::Src2TrgWellFormed;
use Lingua::Align::LinkSearch::Trg2Src;
use Lingua::Align::LinkSearch::Intersection;
use Lingua::Align::LinkSearch::NTFirst;
use Lingua::Align::LinkSearch::NTonly;
use Lingua::Align::LinkSearch::Tonly;
use Lingua::Align::LinkSearch::Assignment;
use Lingua::Align::LinkSearch::PaCoMT;
use Lingua::Align::LinkSearch::Cascaded;
use Lingua::Align::LinkSearch::Viterbi;
use Lingua::Align::LinkSearch::AssignmentWellFormed;


sub new{
    my $class=shift;
    my %attr=@_;

#    my $type = $attr{-link_search} || 'greedy';
    my $type = $attr{-link_search} || 'threshold';

    if ($type=~/^cascaded/i){
	return new Lingua::Align::LinkSearch::Cascaded(%attr);
    }
    if ($type=~/^viterbi/i){
	return new Lingua::Align::LinkSearch::Viterbi(%attr);
    }
    if ($type=~/paco/i){
	return new Lingua::Align::LinkSearch::PaCoMT(%attr);
    }

    # NT nodes first using the search strategy specified thereafter
    if ($type=~/^nt.*first/i){
	return new Lingua::Align::LinkSearch::NTFirst(%attr);
    }
    if ($type=~/and/i){
	return new Lingua::Align::LinkSearch::GreedyFinalAnd(%attr);
    }
    if ($type=~/final/i){
	return new Lingua::Align::LinkSearch::GreedyFinal(%attr);
    }

    # NT nodes first but "final" and "and" are handled before
    if ($type=~/nt.*first/i){
	return new Lingua::Align::LinkSearch::NTFirst(%attr);
    }

    if ($type=~/ntonly/i){
	return new Lingua::Align::LinkSearch::NTonly(%attr);
    }
    if ($type=~/tonly/i){
	return new Lingua::Align::LinkSearch::Tonly(%attr);
    }
    if ($type=~/src2trg.*well.*form/i){
	return new Lingua::Align::LinkSearch::Src2TrgWellFormed(%attr);
    }
    if ($type=~/src2trg/i){
	return new Lingua::Align::LinkSearch::Src2Trg(%attr);
    }
    if ($type=~/trg2src/i){
	return new Lingua::Align::LinkSearch::Trg2Src(%attr);
    }
    if ($type=~/inter/i){
	return new Lingua::Align::LinkSearch::Intersection(%attr);
    }
    if ($type=~/(assign|munkres).*wellform/i){
	return new Lingua::Align::LinkSearch::AssignmentWellFormed(%attr);
    }
    if ($type=~/(assign|munkres)/i){
	return new Lingua::Align::LinkSearch::Assignment(%attr);
    }
    if ($type=~/well.*formed/i){
	return new Lingua::Align::LinkSearch::GreedyWellFormed(%attr);
    }
    if ($type=~/greedy/i){
	return new Lingua::Align::LinkSearch::Greedy(%attr);
    }
    return new Lingua::Align::LinkSearch::Threshold(%attr);
}


# virtual method for checking additional constraints such as wellformedness