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
