Re: [gnugo-devel] more on dfa

[Dave Denholm]

Dave Denholm <address@hidden> writes:

> Tanguy URVOY <address@hidden> writes:
> 
> > Arend Bayer wrote:

> > > 
> > > There is a clean way to solve this problem: Instead of having attributes
> > > for all states, we could only have attributes for those states that have
> > > a transition into the error state. I.e., only at the very end of the DFA
> > > spiral we generate a list of all patterns that got matched.
> > 
> > This is a good optimization of the DFA
> > to put the attributes only in the states with
> > an output transition to the error state.
> > 
> 
> 
> Agreed - I had been wondering how to change things to make a tight inner loop
> while there are no attributes.
> 
> 
> > > 
> > > These attributes could be handled by a separate list, that would be much
> > > smaller because most states do _not_ have a transition to the error
> > > state.
> > 

I'm not sure that's true : for many states, a board value of OFFBOARD
(or whatever it is) will be a transition to the error state.


> > I would be happy to know the amount of states without 
> > out-transitions.
> > If you are right this may be a good compression of the DFA.
> > Can you explain how this list works ?
> > Will you use a hash table ?
> > 
> > 



Fortunately, we don't have to duplicate the pattern list too much for
all these terminal states. An early transition to error can share the
pattern list of a later node, by pointing into it.



> > > I am writing this because:
> > > 1. This could be implemented independently of the incremental matcher
> > > (and would be a step towards it).
> > 
> > agreed.
> > 
> > > 2. It would immediately have two benefits: Save some memory, make the
> > > inner-most loop of the DFA simpler (because there is no longer a need to
> > > check for the attribute), and it should have good cache benefits (there 
> > > will
> > > be four instead of five (short-)ints per dfa state, so more dfa states
> > > fit into a cache line, and we get good alignment for free).
> > 

Also, scaling by 8 or 16 is much easier (on x86) than by 10 or 20



> > Still i dont know how we will seek for the attributes.
> > 
> 
> 
> A picture that sprang into my mind when I read this was to use
> the adjacent entry in the dfa.
> 
> 
> So if a node has any transition to an error state, then the next
> node actually contains a representation of the pattern list.
> 
> 
> eg   42 :   44  47  0  99
>      43 :    0   0 77   0
>      44 :   <etc>
> 
> 
> So node (ie dfa state) 42 says to go to state 44 if board is 0, 47 if 1, 99 
> if 3.
> 2 is a terminal node.
> 
> So "state" 43 is not actually a state, but contains the pattern list (77 in 
> this case)
> 


Hmm - that's not much good, since most nodes contain at least one error
transition (edge of board).

An alternative is to use +ve numbers for a valid transition, or a -ve number
to indicate a terminal state, with the -ve number representing the
pattern list.

eg   42 :   43  47 -77  99
     43 :   44 -76 -76 -76

So from node 42, a board value of 2 is a terminal node, and points
at index 77 into some big list of patterns. From node 43, there are
some more terminal nodes. But they have matched one more
pattern, they point one slot earlier into the pattern list. We don't
have to duplicate the entire pattern list for each terminal node, of
which there are (probably) many.




> 
> 
> The main dfa loop is something along the lines of
> 
>  while ( (next = dfa[state].states[board[spiral[k]]) != 0)
>     state = next;
> 
>  /* get here => terminal node, and the the pattern list is
>   * dfa[state+1].states[board[spiral[k]]]
>   */
> 
> 


Only change is the test becomes > 0  rather than != 0


> 
> 
> Using relative rather than absolute offsets might reduce
> some work in the inner loop.
> 
> Eg if dfa could be a pointer to the current node, then
> 
> 
>  while ( (delta = dfa->states[board[spiral[k]]) != 0)
>     dfa += delta;
> 
> 
> with delta of 0 indicating illegal transition.
> 
> 

If we sort the nodes so that all valid transitions are forwards, then
a -ve number could still represent the pattern list.  Or potentially
save an instruction by storing the -ve of the transition, and doing

  dfa -= delta

while delta < 0. The index into the pattern (attribute) list is now >= 0.

(Pretty minor tweak, though)


dd
-- 
address@hidden          http://www.insignia.com