File Coverage

blib/lib/WordNet/Similarity/path.pm

Criterion	Covered	Total	%
statement	4	6	66.6
branch			n/a
condition			n/a
subroutine	2	2	100.0
pod			n/a
total	6	8	75.0

# WordNet::Similarity::path.pm version 2.04
# (Last updated $Id: path.pm,v 1.19 2008/03/27 06:21:17 sidz1979 Exp $)
#
# N.B., this module was formerly named edge.pm
#
# Semantic Similarity Measure package implementing a simple
# path-length (node-counting) semantic relatedness measure.
#
# Copyright (c) 2005,
#
# Ted Pedersen, University of Minnesota Duluth
# tpederse at d.umn.edu
#
# Siddharth Patwardhan, University of Utah, Salt Lake City
# sidd at cs.utah.edu
#
# Jason Michelizzi, Univeristy of Minnesota Duluth
# mich0212 at 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.
#
# ------------------------------------------------------------------

package WordNet::Similarity::path;

=head1 NAME

WordNet::Similarity::path - Perl module for computing semantic relatedness
of word senses by counting nodes in the noun and verb WordNet 'is-a'
hierarchies.

=head1 SYNOPSIS

  use WordNet::Similarity::path;

  use WordNet::QueryData;

  my $wn = WordNet::QueryData->new();

  my $path = WordNet::Similarity::path->new($wn);

  my $value = $measure->getRelatedness("car#n#1", "bus#n#2");

  my ($error, $errorString) = $measure->getError();

  die "$errorString\n" if($error);

  print "car (sense 1) <-> bus (sense 2) = $value\n";

=head1 DESCRIPTION

This module computes the semantic relatedness of word senses by counting
the number of nodes along the shortest path between the senses in the
'is-a' hierarchies of WordNet.  The path lengths include the end nodes.
For example, the path between shrub#n#1 and tree#n#1 is
S.

Since a longer path length indicate less relatedness, the relatedness
value returned is the multiplicative inverse of the path length (distance)
between the two concepts: S.  If the two
concepts are identical, then the distance between them is one; therefore,
their relatedness is also 1.  If no path is found, then a large negative
number is returned and an error is generated (see C).

The following methods are defined:

=over

=cut

use strict;
use WordNet::Similarity::PathFinder;
use constant MAX_DIST => 100;

our @ISA = qw(WordNet::Similarity::PathFinder);

our $VERSION = '2.04';

=item $path->getRelatedness()

Computes the relatedness of two word senses using a node counting scheme.
The relatedness score is inversely proportional to the number of nodes
along the shortest path between the two word senses.

Parameters: two word senses in "word#pos#sense" format.

Returns: Unless a problem occurs, the return value is the relatedness
score, which belongs to the interval (0, 1].  If no path exists between
the two word senses, then a large negative number is returned.  If an
error occurs, then the error level is set to non-zero and an error string
is created (see the description of getError()).  Note: the error level
will also be set to 1 and an error string will be created if no path
exists between the words.

=cut

sub getRelatedness
{
  my $self = shift;
  my $wps1 = shift;
  my $wps2 = shift;
  my $wn = $self->{wn};
  my $class = ref $self || $self;

  # Initialize traces.
  $self->{traceString} = "" if($self->{'trace'});

  # JM 1-21-04
  # moved input validation code to WordNet::Similarity::parseInput()
  my $ret = $self->parseWps ($wps1, $wps2);
  ref $ret or return $ret;

  my ($word1, $pos1, $sense1, $offset1, $word2, $pos2, $sense2, $offset2)
    = @{$ret};

  $wps1 = "$word1#$pos1#$sense1";
  $wps2 = "$word2#$pos2#$sense2";

  # Now check if the similarity value for these two synsets is in
  # fact in the cache... if so return the cached value.
  my $relatedness =
    $self->{doCache} ? $self->fetchFromCache ($wps1, $wps2) : undef;
  defined $relatedness and return $relatedness;


  # JM 1/23/04
  # Most of the code that does the work of finding the LCS and
  # hypernym trees has been moved into LCSFinder and PathFinder

  #my ($dist, $pathref) = $self->getShortestPath ($offset1, $offset2,
  #	          				 $pos1, 'offset');

  # there can be multiple shortest paths (i.e., paths of the same length)
  my @paths = $self->getShortestPath ($offset1, $offset2, $pos1, 'offset');

  my $path = shift @paths;

  # $path will be undef if no path was found (error messages already generated)
  unless (defined $path) {
    return $self->UNRELATED;
  }

  my $dist = $path->[0];

  # JM 1-29-04
  # most of the code that does path-finding is now in PathFinder

  if ($dist > 0) {
    my $score = 1.0 / $dist;

    $self->{doCache} and $self->storeToCache ($wps1, $wps2, $score);

    return $score;
  }
  else {
    $self->{errorString} .= "\nWarning (${class}::getRelatedness()) - ";
    $self->{errorString} .= "Internal error while finding relatedness.";
    $self->{error} = ($self->{error} < 1) ? 1 : $self->{error};
    return undef;
  }
}

# JM
# Much of the code that was shared between measures has been relocated.
# WordNet::Similarity contains code common to (almost) all measures,
# WordNet::Similarity::PathFinder has code common among path finding
# measures.

1;

__END__