Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??

As far as I can tell this code fails the "A" x 10/"A" x 11 test that you challenged my code with in a different thread. I was able to fix the bug by changing the if ($fuz <= $FUZZY) test to the following:

if( $fuz <= $FUZZY and $offset1+$offset2+$keyLen<=$seqLen) {

I have put together a test harness and framework for developing Fuzzy::Matcher implementations which I will post in a new thread (when i get sufficient time) as IMO this one has become too polluted with acrimony to be worth continuing. Your code as massaged to fit into this framework (along with the baseclass) is in the following readmore. Note that the test harness monitors memory utilization post-prepare() which is why the default prepare() is the way it is (to reduce memory overhead).

Fuzzy::Matcher::Xor2

package Fuzzy::Matcher::Xor2; use strict; use warnings; use Fuzzy::Matcher; use vars qw/$VERSION @ISA/; @ISA=qw(Fuzzy::Matcher); $VERSION=0.01; # Original implementation by [BrowserUk] # bugfixes and modified to fit Fuzzy::Matcher interface by [demerphq] sub fuzz_search { my ($self,$seq)=@_; use bytes; my $FUZZY = $self->{fuzz}; my $seqLen = length $seq; my $keyLen = $self->{strlen}; my ($masked,$pos); my @matches; for my $key ( @{$self->{str_array}} ) { my $mask = $key x ( int( $seqLen / $keyLen ) + 1 ); my $maskLen = length $mask; my $minZeros = chr( 0 ) x int( $keyLen / ( $FUZZY + 1 ) ); my $minZlen = length $minZeros; for my $offset1 ( 0 .. $keyLen-1 ) { $masked = $mask ^ substr( $seq, $offset1, $maskLen ); $pos = 0; while( $pos = 1+index $masked, $minZeros, $pos ) { $pos--; my $offset2 = $pos - ($pos % $keyLen ); my $fuz = $keyLen - ( substr( $masked, $offset2, $keyLen ) =~ tr[\0][\0] ); if( $fuz <= $FUZZY and $offset1+$offset2+$keyLen<=$seqLen) + { push @matches,$offset1 + $offset2,$fuz,$key; #printf "\tFuzzy matched key:'$key' -v- '%s' in line: +" # . "%2d @ %6d (%6d+%6d) with fuzziness: %d\n +", # substr( $seq, $offset1 + $offset2, $keyLen ), # $., , $offset1, $offset2, $fuz; } $pos = $offset2 + $keyLen; } } } return @matches; } 1;

Base Class for Fuzzy::Matcher

package Fuzzy::Matcher; use strict; use warnings; use Carp qw(croak confess); use vars qw/$VERSION/; $VERSION=0.01; # This is a base class for fuzzy matchers to inherit. # Its where stuff that will be common to all matchers # is located. It also defines the interface that all # matchers will have to follow. # # Usage Sample: # # my $matcher=$class->new(2,25); # $matcher->fuzz_store($_) for @words; # $matcher->prepare() # for my $strings (@strings) { # my @res=$matcher->fuzz_search($strings); # } # # ---------------------------------------------------- # Constructor CLASS->new($fuzz,$strlen) # # Takes the amount of fuzz to use for matching # and the length of the strings to be matched. # # Should not be overriden. # sub new { my $class = shift; my $fuzz = shift; my $strlen = shift; my $self=bless { fuzz => $fuzz||0, strlen => $strlen, },$class; croak "Failed build!" unless $self; $self->_init(@_); return $self; } # # $obj->_init() # # This is a hook for subclass to override without # having to override the default object creation # process. It is called in void context before the # object is returned to the user with any args # remaining after the default ($fuzz,$strlen) # # By default it is a No-Op. # sub _init { } # # $obj->fuzz_store($string) # # Store a string into the object for fuzzy matching # later. # # Default behaviour is to build a hash of stored strings # for dupe checking and a corresponding array of strings. # The array is named fuzz_strings and the hash is named # str_hash. # # sub fuzz_store { my ($self,$str)=@_; push @{$self->{str_array}},$str unless $self->{str_hash}{$str}++; } # # $obj->prepare($string) # # If necessary a subclass may define this sub so # that any actions that need to occur after # adding the words but before search starts. # # By default it deletes the str_hash entry from the object to # preserve memory. # sub prepare { my ($self,$str)=@_; delete $self->{str_hash}; } # # $obj->fuzz_search($string) # # Search a string for results and return # a list of matches. The list will be # of triples so that the first match returns: # my ($match_ofs,$chars_diff,$string_matched)= # $obj->fuzz_search($string) # # Must be overriden # sub fuzz_search { confess((caller(0))[3],"() method must be overriden in ". ref($_[0])); } 1;
---
demerphq


In reply to Re^3: Fuzzy Searching: Optimizing Algorithm ( A few improvements). by demerphq
in thread Fuzzy Searching: Optimizing Algorithm Selection by Itatsumaki

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others admiring the Monastery: (3)
As of 2024-03-29 06:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found