Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

Re: Re: 3 Examples of Multiple-Word Search n Replace

by chunlou (Curate)
on Jun 28, 2003 at 19:40 UTC ( [id://269922] : note . print w/replies, xml ) Need Help??


in reply to Re: 3 Examples of Multiple-Word Search n Replace
in thread 3 Examples of Multiple-Word Search n Replace

Thought, might be helpful to have a quick reference for some other readers...

Patrica Tree/Trie = "Practical Algorithm to Retrieve Info Coded In Alphanumeric," where Trie came from reTRIEval (pronounced either "tree" or "try")

Suppose you have data: good gal bad gag

How it looks like in a noncompact tree:

	         ^    ____ $ ___(NULL)
	     /  / \ \
	    b  g  g  g
	   /  /   |   \
	  a  a    a    o
	 /   |    |     \
	d    g    l      o
	|    |    |       \
	$    $    $       d
	|    |    |       |
         (bad)(gag)(gal)     $
                             |
                          (good)


How it looks like in a Patrica Tree

	       ^    ____ $ ___(NULL)
	     /    \ 
	    b     g 
	   /    /   \
	  a    a     o
	 /    |  \    \
	d     g   l    o
	|     |   |     \
	$     $   $     d
	|     |   |     |
         (bad)(gag) (gal)  $
                           |
                        (good)

I suppose most people know in this context DFA and NFA stand for "Deterministic Finite Automaton" and "Nondeterministic Finite Automaton" respectively, not "Dairy Farmers of America" and "National Farmers Association."

  • Comment on Re: Re: 3 Examples of Multiple-Word Search n Replace

Replies are listed 'Best First'.
Re: Re: Re: 3 Examples of Multiple-Word Search n Replace
by demerphq (Chancellor) on Jun 28, 2003 at 21:38 UTC

    And as can be seen from the bottom tree if we walk the tree from the root outward trying to match character by character and ever fail, then we need only backtrack to position N+1 and restart the process.

    This can then be optimized further by adding extra data to each node: how many characters we can advance if we fail at that point. For instance in a tree that contained only 'behoove' and 'hold' we could precalculate that when the 'h' in behoove is our last accepting character we can advance two chars, likewise if we added 'oven' to the tree we could calculate that when we get to the first 'o' in 'behoove' we could advance three chars, and if we get to the second 'o' and fail that we can advance 6 chars, because if we fail at that point we _cant_ match 'oven'. We can also do things like calculate where in the tree we should be if we fail with a given character. All of this adds up to the possibility of matching constant strings in a single pass with no backtracking.

    This is essentially what a DFA regex engine does. Although usually the tree isn't directly represented as a tree, but rather as a massive state transition table. In this representation the tree is represented as a table, with each node represented as row, and each row being called a state. (state == node). Each row would have sufficient fields for all the possible inputs (ie 255 chars), and each field would contain the newstate, and some kind of action statement, probably something like reject, accept,reject-advance, and accept-advance.


    ---
    demerphq

    <Elian> And I do take a kind of perverse pleasure in having an OO assembly language...