#!/usr/local/bin/perl -w
#
# rank.pl Version 0.5
#
# Program to calculate the rank correlation coefficient between the rankings
# generated by two different statistical measures on the same
# bigram-frequency (as output by count.pl).
#
# Copyright (C) 2000-2001,
# Satanjeev Banerjee, University of Minnesota, Duluth
# bane0025@d.umn.edu
# Ted Pedersen, University of Minnesota, Duluth
# tpederse@d.umn.edu
#
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation; either version 2
# of the License, or (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
#
#-----------------------------------------------------------------------------
#                                 Start of Program!
#-----------------------------------------------------------------------------

# we have to use commandline options, so use the necessary package!
use Getopt::Long;

# first check if no commandline options have been provided... in which case
# print out the usage notes!
if ( $#ARGV == -1 )
{
    minimalUsageNotes();
    askHelp();
    exit;
}

# now get the options!
GetOptions("version", "help", "precision=i");

# if help has been requested, print out help and exit
if (defined $opt_help)
{
    $opt_help = 1;
    showHelp();
    exit;
}

# if version has been requested, print out the version number and exit
if (defined $opt_version)
{
    $opt_version = 1;
    showVersion();
    exit;
}

# get the first file.
$firstFile = shift;
open(SRC, $firstFile) || die("Couldn't open $firstFile\n");
while(<SRC>)
{
    next unless(/^((\S+<>)+)(\d+)\s/);
    $list1{$1} = $3;
}
close(SRC);

# get from the second file only those ngrams that are in the first
# file. Also continuously "rerank".
$secondFile = shift;
if (!defined $secondFile) 
{ 
    print STDERR "Second file not provided.\n"; 
    askHelp(); 
    exit; 
}

open(SRC, $secondFile) || die("Couldn't open $secondFile\n");
$lastRankSeen = 0;
$lastRankUsed = 0;
$tiesAtLastRank = 0;
while(<SRC>)
{
    next unless(/^((\S+<>)+)(\d+)\s/);
    my $ngram = $1;
    my $rank = $3;

    # ignore ngrams not on first list
    next unless(defined $list1{$ngram});

    # save ngram in second list, but after adjusting rank
    if ($rank == $lastRankSeen)
    {
	$list2{$ngram} = $lastRankUsed;
	$tiesAtLastRank++;
    }
    else
    {
	$list2{$ngram} = $lastRankUsed + $tiesAtLastRank + 1;
	$lastRankUsed  = $lastRankUsed + $tiesAtLastRank + 1;
	$lastRankSeen = $rank;
	$tiesAtLastRank = 0;
    }
}
close(SRC);

# now remove those ngrams in list1 that dont exist in list2, and rerank
$lastRankSeen = 0;
$lastRankUsed = 0;
$tiesAtLastRank = 0;
foreach (sort {$list1{$a} <=> $list1{$b}} keys %list1)
{
    # remove ngrams not on second list
    next unless (defined $list2{$_});

    # Adjust rank
    if ($list1{$_} == $lastRankSeen)
    {
	$adjustedList1{$_} = $lastRankUsed;
	$tiesAtLastRank++;
    }
    else
    {
	$adjustedList1{$_} = $lastRankUsed + $tiesAtLastRank + 1;
	$lastRankUsed  = $lastRankUsed + $tiesAtLastRank + 1;
	$lastRankSeen = $list1{$_};
	$tiesAtLastRank = 0;
    }
}

%list1 = %adjustedList1;

# compute the coeff and count the number of bigrams being used
$bigramsUsed = 0;
$coeff = 0;
foreach (sort {$list1{$b} <=> $list1{$a}} keys %list1)
{
    $bigramsUsed++;
    $diff = $list1{$_} - $list2{$_};
    $coeff += $diff * $diff;
}

if ($bigramsUsed == 0)
{
    print STDERR "No bigrams to calculate rank correlation coefficient for.\n";
    exit;
}

$coeff *= 6;
$coeff /= $bigramsUsed * ( $bigramsUsed * $bigramsUsed - 1 );
$coeff = 1 - $coeff;

$precision = (defined $opt_precision) ? $opt_precision : 4;
$floatFormat = "%.${precision}f";
printf("Rank correlation coefficient = $floatFormat\n", $coeff);
    
# function to output a minimal usage note when the user has not provided any
# commandline options
sub minimalUsageNotes
{
    print "Usage: rank.pl [OPTIONS] SOURCE_FILE1 SOURCE_FILE2\n";
}

# function to output help messages for this program
sub showHelp
{
    print "Usage: rank.pl [OPTIONS] SOURCE_FILE1 SOURCE_FILE2\n\n";

    print "To compute the Spearman rank correlation coefficient between two lists\n";
    print "of ngrams produced by program statistic.pl using two (probably different)\n";
    print "statistical measures. SOURCE_FILE1 and SOURCE_FILE2 should contain the two\n";
    print "lists respectively. Ngrams occurring in both source files are chosen,\n";
    print "their ranks are adjusted and then these ranks are used to compute the\n";
    print "correlation coefficient.\n\n";

    print "OPTIONS:\n\n";

    print "   --precision N   Rounds coefficient to N places of decimal. N = 4 by\n";
    print "                   default.\n\n";

    print "   --version       Prints the version number.\n\n";

    print "   --help          Prints this help message.\n\n";

}


# function to show the version number
sub showVersion
{
    print "rank.pl         -       version 0.5\n";
    print "A component of the NSP, version 0.5\n";
    print "Copyright (C) 2000-2003, Ted Pedersen & Satanjeev Banerjee\n";
}

# function to output "ask for help" message when the user's goofed up!
sub askHelp
{
    print STDERR "Type rank.pl --help for help.\n";
}
