Update: realized this is the same idea as tachyon's
Re: Fuzzy Searching: Optimizing Algorithm Selection
How about something simple minded: for each substring of the target, compute the difference with the search string, if the diff is less than 3, accept it. This will only find out matches that have at most two letter difference (but not missing):
use strict;
my $search = "apple";
my $length = 5; #length of the target
my $FUZZY = 2; #
my $BIG = 10;
while(my $a = <DATA>){
chomp $a;
my $score = $BIG;
for(my $i = 0; $i + $length < length($a); $i++){
$score = diff_score($search, substr($a,,$i,$length));
if($score <= $FUZZY){
print "$score: $a\n";
last;
}
}
if($score > $FUZZY){
print "-1:$a\n";
}
}
# return the number of different letters.
sub diff_score{
my ($first, $second)= @_;
return $BIG unless length($first) == length($second);
my $score = 0;
for(my $i = 0; $i < length($first); ++$i){
++$score if substr($first,$i,1) ne substr($second,$i,1
+);
}
return $score;
}
__DATA__
This is an apple
An arple is here
What bpple is that
What is that
What bple is that
aplle is not a word
Output as follows, diffs are in front, -1 show not matching fuzzily.
__OUTPUT__
0: This is an apple
1: An arple is here
1: What bpple is that
-1:What is that
2: What bple is that
1: aplle is not a word
-
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.