Any automata extension?
Georgios Petasis
Are there any tcl extensions that support the creation & optimisation of
NFA/DFA?
I know about tcllib's grammar::fa, but the automata that I want to
optimise take a few hours with grammar::fa. Any ideas?
I have ~100.000 phrases that must be matched in a string, so I want to
somehow optimise my lists before I turn them into regular expressions...
George
Neil Madden
What sort of matching do you need to do? Exact? Prefix? Glob? Full
regexp? If prefix then maybe a trie?
-- Neil
Georgios Petasis
I have a large list (~250.000) of strings, that I want to convert into a
regular expression.
I think that I want to convert the list into a minimal acyclic directed
graph...
George
Alexandre Ferrieux
wrote:
> O/H Neil Madden Ýãñáøå:
You still didn't answer Neil's question: what kind of match ?
- exact --> ^(foo|bar)$
- prefix --> ^(foo|bar)
- other ?
The reason it matters is that if it's 'exact' then a hashtable (array
or dict) might be simpler, faster, and more compact in memory.
Also, the expected gain of the minimization could be clarified. A
simple PTA regexp implements only the left-minimization, but the extra
space you can squeeze out by right-minimization can be disappointing
(and the speed gain is close to zero, only cache effects).
-Alex
Neil Madden
I'm not getting what the immediate connection is between "I have
~100.000 phrases that must be matched in a string" and the need to turn
them into a regular expression. Are the phrases themselves REs that you
want to combine and optimise, or are they just strings? Are you trying
to match a disjunction of all the phrases (A or B or C ...) or the
conjunction? Do the patterns contain wildcards or anchors? Converting a
list of strings into an RE (or a DAG) is an underspecified task.
To answer your immediate question -- no, I'm not aware of any finite
automata or DAG package for Tcl that supports this sort of optimisation
out of the box. There are a number of packages that might get you part
of the way, such as grammar_fa, the tcllib graph package, or
http://wiki.tcl.tk/18129, but I'm still not 100% clear what you are
trying to achieve.
-- Neil
Georgios Petasis
The "other" case. Something like regexp -all {A|B|C} string.
Like locating in a text all occurances of location names, from a list of
a few thousands location names.
George
Georgios Petasis
I do want to allow flexibility the strings to be also regular
expressions. I am after the disjunction of all phrases with no anchors.
I have used the grammar_fa (nice package btw), it does what I want to
do, but it is slow for the task. (I think that minimising a DFA is of
exponential complexity though).
I am looking for something that would accept (aaa|aba) and would output
(a(a|b)a).
George
Neil Madden
OK. That's more difficult then. In general, I believe this conversion is
PSPACE-complete, so unlikely to be a fast general solution. You may be
able to get decent performance for specific examples though. You will
probably have to code this yourself though, or look for a C library that
does it.
-- Neil
Alexandre Ferrieux
Not anchored, but possibly delimited, ain't it ?
For example, you'd like to find "Chicago" in " foo Chicago, bar", but
not in "zzChicagoes" ?
If that's so, tokenize-and-hash will probably win the race...
(of course that's for fixed strings, not regexps. But city names are
not regexps, provided you take care of upper/lowercase, hyphens, etc.,
by preprocessing (regsub))
-Alex
Georgios Petasis
Dear Alex,
This is what I am currently exploring...
The only puzzling issue is that some strings have 13 words in them,
which suggests that I have to do 13 checks per word position.
George
Georgios Petasis
Finally, it worked, and it was fast enough... Unexpected :D
George
Aric Bills
I wonder if SFST could do this: http://www.ims.uni-stuttgart.de/projekte/gramotron/SOFTWARE/SFST.html
It's not a Tcl extension (yet) and I haven't ever used it, but it's
high on my list of things to try.
Les Cargill
I am not at all sure I understand your problem. That being said,
suppose the pattern database is:
set delist { { now is the time} { see the monkey } { go man go } }
which can algorithmically be rendered (rather, generated) as ( bear with
me):
array set FSM {
0,now 1
1,is 2
3,the 4
4,time TERMINAL
0,see 5
5,the 6
6,monkey TERMINAL
0,go 7
7,man 8
8,go TERMINAL
}
# -1 = partial match
# 0 = no match
# 1 = exact match
proc match { phrase } {
variable FSM
set state 0
foreach tok $phrase {
if {[catch { set state $FSM($state,$tok) } {
#puts "no match"
return 0
}
if {$state == TERMINAL} {
#puts "matched"
return 1
}
}
return -1
}
might seem silly, but I use this exact technique all
the time with datasets of bewildering size, and it
just works. Indeed, you can do protocols like this
pretty easily.
The only downside is any hash complexity ( in the O(n)
sense ) as the dataset gets large.
Having large regexp sets may or may not be good, and I'm
not sure how one would do that.
--
Les Cargill
Donal K. Fellows
> if {$state == TERMINAL} {
Syntax correction:
if {$state eq "TERMINAL"} {
Donal.