Re^4: Fuzzy Searching:Alg.Sel. (Why tries won't work for this application.)

Since all that a DFA has to keep track of is the position within the test string and the number of fuzzy matches made so far, it would need no more than (number of characters in the test string)*(number of fuzzies allowed + 1) states. That is only 75 states for a string of length 25 with two errors allowed.

I haven't coded the DFA yet, but here is looping code that illustrates the idea.

use strict;
use warnings;

my $test = "abcdefghijklmnopqrstuvwxy";
my @test = split //,$test;
my $dict = "qqqabcdefghijklmnopqrstuvwxyqqq";
my @dict = split //,$dict;

my $dict_pos = 0;  # where in the dictionary word
my $at_pos = 0;    # where in the test word
my $fuzzies = 2;   # unused fuzzies remaining
my $testlen = length($test);
my $len = length($dict) - $testlen - 1;

# This loop illustrates the states a finite state machine would
# require.  The states would be numbered 3*$at_pos + $fuzzies,
# that is, 75 states in this case.
while (1) {
   if ($fuzzies > 0) {
      if ($dict[$dict_pos + $at_pos] ne $test[$at_pos]) {
         --$fuzzies;
      }
      ++$at_pos;
      if ($at_pos >= $testlen) {
         print "Found at $dict_pos with $fuzzies remaining\n";
         last;
      }
   } else {
      # Out of fuzzies.  Rest of match must be exact, or start over
      # in the next position.
      my $s1 = substr($dict, $dict_pos + $at_pos, $testlen - $at_pos);
      my $s2 = substr($test, $at_pos);
      if ($s1 ne $s2) {
         last if (++$dict_pos > $len);
         $fuzzies = 2;
         $at_pos = 0;
      } else {
         print "Found at $dict_pos with $fuzzies remaining\n";
         last;
      }
   }
}
[download]

Comment on Re^4: Fuzzy Searching:Alg.Sel. (Why tries won't work for this application.) Download Code

Replies are listed 'Best First'.
Re^5: Fuzzy Searching:Alg.Sel. (Why tries won't work for this application.) by BrowserUk (Patriarch) on Nov 14, 2004 at 23:29 UTC
That is only 75 states for a string of length 25 with two errors allowed. That is for one search key. There are 100,000 to process. Against 30,000 x 1000-char strings. The "... the complexity of this problem." I spoke of with respect to a DFA, is the idea that you could combine all 100,000 keys into a single, huge DFA. If you applied your code above--or any pure perl implementation of a DFA--against each of the 30,000 strings, for each of the 100,000 keys, would it out-perform Perl's regex engine? Even if you coded seperate, 75-state DFA using C for each of the 100,000 keys, and then applied them to the 30,000 sequences, would it out perform Perl's regex engine? Do you fancy the task of hand coding 100,000 75-state DFAs in C? And then doing it again next week for another 100,000 keys?. Obviously, you wouldn't hand-code all the DFAs individually. You would write a DFA generator and let the computer do the work. Writing DFA generators is non-trivial, Even once you have it working, you still have to apply 100,000 DFAs to each of the 30,000 sequences. So, rather than generate individual DFAs, you write your generator to build one, humungous DFA that encapsulates the state of all, 75 states of all 100,000 keys. Combining the DFA this way probably reduces the 7.5 million states to less that 10%? That's still an awefully complex DFA to generate, and an even more complex DFA generator to design, code, test, debug--in C. If you did do this, the advantage is that you only have one DFA to apply to the 30,000 sequences, which would almost certainly be the quickest of all the techniques described in this thread. It's just a case of doing the work. Does this sound familiar? If you carefully craft your regexes to avoid backtracking, you are using the regex engine to generate a fairly close approximation to a custom DFA for each regex. No, horribly compex, difficult to get right, C work to do. It's already available in Perl. Examine what is said, not who speaks. "Efficiency is intelligent laziness." -David Dunham "Think for yourself!" - Abigail "Time is a poor substitute for thought"--theorbtwo "Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon	[reply]

Replies are listed 'Best First'.

Re^5: Fuzzy Searching:Alg.Sel. (Why tries won't work for this application.)
by BrowserUk (Patriarch) on Nov 14, 2004 at 23:29 UTC

That is only 75 states for a string of length 25 with two errors allowed.

That is for one search key. There are 100,000 to process. Against 30,000 x 1000-char strings.

The "... the complexity of this problem." I spoke of with respect to a DFA, is the idea that you could combine all 100,000 keys into a single, huge DFA.

If you applied your code above--or any pure perl implementation of a DFA--against each of the 30,000 strings, for each of the 100,000 keys, would it out-perform Perl's regex engine?

Even if you coded seperate, 75-state DFA using C for each of the 100,000 keys, and then applied them to the 30,000 sequences, would it out perform Perl's regex engine?

Do you fancy the task of hand coding 100,000 75-state DFAs in C? And then doing it again next week for another 100,000 keys?.

Obviously, you wouldn't hand-code all the DFAs individually. You would write a DFA generator and let the computer do the work**. Writing DFA generators is non-trivial, Even once you have it working, you still have to apply 100,000 DFAs to each of the 30,000 sequences.

So, rather than generate individual DFAs, you write your generator to build one, humungous DFA that encapsulates the state of all, 75 states of all 100,000 keys. Combining the DFA this way probably reduces the 7.5 million states to less that 10%? That's still an awefully complex DFA to generate, and an even more complex DFA generator to design, code, test, debug--in C.

If you did do this, the advantage is that you only have one DFA to apply to the 30,000 sequences, which would almost certainly be the quickest of all the techniques described in this thread. It's just a case of doing the work.

**Does this sound familiar? If you carefully craft your regexes to avoid backtracking, you are using the regex engine to generate a fairly close approximation to a custom DFA for each regex. No, horribly compex, difficult to get right, C work to do. It's already available in Perl.

Examine what is said, not who speaks.

"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail "Time is a poor substitute for thought"--theorbtwo
"Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon

[reply]