1WagnerFischer(3)      User Contributed Perl Documentation     WagnerFischer(3)
2
3
4

NAME

6       Text::WagnerFischer - An implementation of the Wagner-Fischer edit
7       distance
8

SYNOPSIS

10        use Text::WagnerFischer qw(distance);
11
12        print distance("foo","four");# prints "2"
13
14        print distance([0,1,2],"foo","four");# prints "3"
15
16
17        my @words=("four","foo","bar");
18
19        my @distances=distance("foo",@words);
20        print "@distances"; # prints "2 0 3"
21
22        @distances=distance([0,2,1],"foo",@words);
23        print "@distances"; # prints "3 0 3"
24

DESCRIPTION

26       This module implements the Wagner-Fischer dynamic programming
27       technique, used here to calculate the edit distance of two strings.
28       The edit distance is a measure of the degree of proximity between two
29       strings, based on "edits": the operations of substitutions, deletions
30       or insertions needed to transform the string into the other one (and
31       vice versa).  A cost (weight) is needed for every of the operation
32       defined above:
33
34                   / a if x=y (cost for letter match)
35        w(x,y) =  |  b if x=- or y=- (cost for insertion/deletion operation)
36                   \ c if x!=y (cost for letter mismatch)
37
38       These costs are given through an array reference as first argument of
39       the distance subroutine: [a,b,c].  If the costs are not given, a
40       default array cost is used: [0,1,1] that is the case of the Levenshtein
41       edit distance:
42
43                   / 0 if x=y (cost for letter match)
44        w(x,y) =  |  1 if x=- or y=- (cost for insertion/deletion operation)
45                   \ 1 if x!=y (cost for letter mismatch)
46
47       This particular distance is the exact number of edit needed to
48       transform the string into the other one (and vice versa).  When two
49       strings have distance 0, they are the same.  Note that the distance is
50       calculated to reach the _minimum_ cost, i.e.  choosing the most
51       economic operation for each edit.
52

EXTENDING (by Daniel Yacob)

54       New modules may build upon Text::WagnerFischer as a base class.  This
55       is practical when you would like to apply the algorithm to non-Roman
56       character sets or would like to change some part of the algorithm but
57       not another.
58
59       The following example demonstrates how to use the WagnerFisher distance
60       algorithm but apply your own weight function in a new package:
61
62         package Text::WagnerFischer::MyModule;
63         use base qw( Text::WagnerFischer );
64
65         #
66         # Link to the WagnerFisher "distance" function so that the
67         # new module may also export it:
68         #
69         use vars qw(@EXPORT_OK);
70
71         @EXPORT_OK = qw(&distance);
72
73         *distance = \&Text::WagnerFischer::distance;
74
75         #
76         # "override" the _weight function with the a one:
77         #
78         *Text::WagnerFischer::_weight = \&_my_weight;
79
80         #
81         # "override" the default WagnerFischer "costs" table:
82         #
83         $Text::WagnerFischer::REFC = [0,2,3,1,1];
84
85         sub _my_weight {
86           :
87           :
88           :
89         }
90

AUTHOR

92       Copyright 2002,2003 Dree Mistrut <dree@friul.it>
93
94       This package is free software and is provided "as is" without express
95       or implied warranty. You can redistribute it and/or modify it under the
96       same terms as Perl itself.
97

SEE ALSO

99       "Text::Levenshtein", "Text::PhraseDistance"
100
101
102
103perl v5.38.0                      2023-07-21                  WagnerFischer(3)
Impressum