Re: Looking for a DFA implementation (please help)

mike wrote:


> I'm working on an AI project and one part of it requires an
> implementation of fast string matching.
> Specifically I need a DFA (or an analog) that can match a string against
> a set of others and give a
> different output depending on which string it matched (not just that a
> match was found)
> for example, i have a set of strings
> xoo?.?$ (1)
> ?$?x.? (2)
> o$?.. (3)
> (where ? [xo.] and $ is [xo])
> and I need to if another string C, for example 'xxo?' matches anything
> in the set, and if so, what is the number of the string that it matches


[snip]


If correctly understand the above, what do you need is a table of
topics, which can be matched against a string to find the longest
topic in the table that matches a string prefix. If so there is a
GMGPL-ed software for this (in Ada 95):


www.dmitry-kazakov.de/ada/tables.htm


In worst case matching time is linear. However, usually it is logarithmic.


Alternatively, if topics are not strings, but patterns then you need a
sort of pattern matching and little could be said about speed. There
is a GMGPL-ed pattern matching software (in C, C++):


www.dmitry-kazakov.de/match/match.htm


It supports SNOBOL-like immediate assignment, i.e. setting/resetting
variables during matching process. This can be used to note which part of
the pattern (=topic) was actually matched.


--
Regards,
Dmitry A. Kazakov
www.dmitry-kazakov.de

Return to the comp.compilers page.
Search the comp.compilers archives again.