WagnerFischer(3pm)

💖 NAME 💖

Text::WagnerFischer — bestie, this is a whole implementation of the Wagner-Fischer edit distance and it's iconic, no cap. (You'll also see it filed under WagnerFischer(3pm) in the User Contributed Perl Documentation corner of the manual, iykyk.)

---

✨ SYNOPSIS ✨

use Text::WagnerFischer qw(distance);

print distance("foo","four");# prints "2"

print distance([0,1,2],"foo","four");# prints "3"

my @words=("four","foo","bar");

my @distances=distance("foo",@words);
print "@distances"; # prints "2 0 3"

@distances=distance([0,2,1],"foo",@words);
print "@distances"; # prints "3 0 3"

---

🦋 DESCRIPTION 🦋

Okay so. This module is doing the Wagner-Fischer dynamic programming technique, and it's using it to compute the edit distance of two strings. And what even is edit distance, you ask? It's literally a measure of how close two strings are to each other, and it's based on "edits" — the operations of substitutions, deletions, or insertions you'd need to transform one string into the other one (and vice versa, obviously, she's symmetric 💅). Every one of those operations needs a cost (aka a weight), and here's the whole vibe:

            / a if x=y (cost for letter match)
 w(x,y) =  |  b if x=- or y=- (cost for insertion/deletion operation)
            \ c if x!=y (cost for letter mismatch)

You hand these costs over as an array reference, and it goes in as the first argument of the distance subroutine: [a,b,c]. If you don't give any costs at all? No stress, a default cost array gets used: [0,1,1] — which is exactly the Levenshtein edit distance situation:

            / 0 if x=y (cost for letter match)
 w(x,y) =  |  1 if x=- or y=- (cost for insertion/deletion operation)
            \ 1 if x!=y (cost for letter mismatch)

This particular distance is the exact number of edits needed to transform one string into the other one (and vice versa, again 💖). And when two strings have distance 0? They're the same, periodt. Just know that the distance is always calculated to reach the _minimum_ cost, i.e. it's picking the most economic operation for each and every edit. Frugal queen. 👑

---

🌸 EXTENDING 🌸 (by Daniel Yacob)

New modules can totally build on top of Text::WagnerFischer as a base class, and honestly? Slay. This is highkey practical when you want to apply the algorithm to non-Roman character sets, or when you want to change one part of the algorithm but not another. Very mix-and-match, very customizable.

The following example shows you how to use the WagnerFisher distance algorithm while applying your own weight function in a new package:

package Text::WagnerFischer::MyModule;
use base qw( Text::WagnerFischer );

#
# Link to the WagnerFisher "distance" function so that the
# new module may also export it:
#
use vars qw(@EXPORT_OK);

@EXPORT_OK = qw(&distance);

*distance = \&Text::WagnerFischer::distance;

#
# "override" the _weight function with the a one:
#
*Text::WagnerFischer::_weight = \&_my_weight;

#
# "override" the default WagnerFischer "costs" table:
#
$Text::WagnerFischer::REFC = [0,2,3,1,1];

sub _my_weight {
  :
  :
  :
}

---

🎀 AUTHOR 🎀

Copyright 2002,2003 Dree Mistrut <dree@friul.it> 🫶

This package is free software and it's provided "as is" without express or implied warranty. You can redistribute it and/or modify it under the same terms as Perl itself. (Yes bestie, same terms as Perl itself, that's the whole deal.)

---

👑 SEE ALSO 👑

• "Text::Levenshtein"
• "Text::PhraseDistance"

---

Ok that's the whole page, mwah 💜 Go forth and compute some distances, you absolute main character.

perl v5.32.0 · 2021-01-01 · User Contributed Perl Documentation — that's the version, the date and the source, babes, and that's a wrap on WagnerFischer(3pm) ✨💅🎀