GSP
Quick Navigator

Search Site

Unix VPS
A - Starter
B - Basic
C - Preferred
D - Commercial
MPS - Dedicated
Previous VPSs
* Sign Up! *

Support
Contact Us
Online Help
Handbooks
Domain Status
Man Pages

FAQ
Virtual Servers
Pricing
Billing
Technical

Network
Facilities
Connectivity
Topology Map

Miscellaneous
Server Agreement
Year 2038
Credits
 

USA Flag

 

 

Man Pages


Manual Reference Pages  -  TEXT::BREW (3)

.ds Aq ’

NAME

Text::Brew - An implementation of the Brew edit distance

CONTENTS

SYNOPSIS



 use Text::Brew qw(distance);

 my ($distance,$arrayref_edits)=distance("four","foo");
 my $sequence=join",",@$arrayref_edits;
 print "The Brew distance for (four,foo) is $distance\n";
 print "obtained with the edits: $sequence\n\n";



DESCRIPTION

This module implements the Brew edit distance that is very close to the dynamic programming technique used for the Wagner-Fischer (and so for the Levenshtein) edit distance. Please look at the module references below. For more information about the Brew edit distance see: <http://ling.ohio-state.edu/~cbrew/795M/string-distance.html>

The difference here is that you have separated costs for the DELetion and INSertion operations (but with the default to 1 for both, you obtain the Levenshtein edit distance). But the most interesting feature is that you can obtain the description of the edits needed to transform the first string into the second one (not vice versa: here DELetions are separated from INSertions). The difference from the original algorithm by Chris Brew is that I have added the SUBST operation, making it different from MATCH operation.

The symbols used here are:



 INITIAL that is the INITIAL operation (i.e. NO operation)
 MATCH   that is the MATCH operation (0 is the default cost)
 SUBST   that is the SUBSTitution operation (1 is the default cost)
 DEL     that is the DELetion operation (1 is the default cost)
 INS     that is the INSertion operation (1 is the default cost)



and you can change the default costs (see below).

You can make INS and DEL the same operation in a simple way:



 1) give both the same cost
 2) change the output string DEL to INS/DEL (o whatever)
 3) change the output string INS to INS/DEL (o whatever)



    USAGE



 use strict;
 use Text::Brew qw(distance);

 my ($distance,$arrayref_edits)=distance("four","foo");
 my $sequence=join",",@$arrayref_edits;
 print "The Brew distance for (four,foo) is $distance\n";
 print "obtained with the edits: $sequence\n\n";

 my $string1="foo";
 my @strings=("four","foo","bar");
 my (@dist,@edits);
 foreach my $string2 (@strings) {
        my ($dist,$edits)=distance($string1,$string2);
        push @dist,$dist;
        push @edits,(join ",",@$edits);
 }
 foreach my $i (0 .. $#strings) {

        print "The Brew distance for ($string1,$strings[$i]) is $dist[$i]\n";
        print "obtained with the edits: $edits[$i]\n\n";
 }



    OPTIONAL PARAMETERS



 distance($string1,$string2,{-cost=>[0,2,1,1],-output=>edits});

 -output
 accepted values are:  
        distance        means that the distance returns
                        only the numeric distance
                                       
        both    the distance returns both the
                numeric distance and the array of the edits

        edits   means that the distance returns only the
                array of the edits

 Default output is both.

 -cost
 accepted value is an array with 4 elements:
 1st is the cost for the MATCH
 2nd is the cost for the INS (INSertion)
 3rd is the cost for the DEL (DELetion)
 4th is the cost for the SUBST (SUBSTitution)

 Default array is [0,1,1,1] .

 Examples are:

 my $distance=distance("four","foo",{-output=>distance});
 print "The Brew distance for (four,foo) is $distance\n\n";


 my $arrayref_edits=distance("four","foo",{-output=>edits});
 my $sequence=join",",@$arrayref_edits;
 print "The Brew sequence for (four,foo) is $sequence\n\n";


 my ($distance,$arrayref_edits)=distance("four","foo",{-cost=>[0,2,1,1]});
 my $sequence=join",",@$arrayref_edits;
 print "The Brew distance for (four,foo) is $distance\n";
 print "obtained with the edits: $sequence\n\n";

 ($distance,$arrayref_edits)=distance("foo","four",{-cost=>[0,2,1,1]});
 $sequence=join",",@$arrayref_edits;
 print "The Brew distance for (foo,four) is $distance\n";
 print "obtained with the edits: $sequence\n\n";



CREDITS

All the credits goes to Chris Brew the author of the algorithm.

THANKS

Many thanks to Stefano L. Rodighiero <larsen at perlmonk.org> for the suggestions.

AUTHOR

Copyright 2003 Dree Mistrut <dree@friuli.to>

This package is free software and is provided as is without express or implied warranty. You can redistribute it and/or modify it under the same terms as Perl itself.

SEE ALSO

Text::Levenshtein, Text::WagnerFischer
Search for    or go to Top of page |  Section 3 |  Main Index


perl v5.20.3 TEXT::BREW (3) 2005-04-02

Powered by GSP Visit the GSP FreeBSD Man Page Interface.
Output converted with manServer 1.07.