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.
In reply to Re: Re: Re: 3 Examples of Multiple-Word Search n Replace
by demerphq
in thread 3 Examples of Multiple-Word Search n Replace
by chunlou
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |