Date: Wed, 9 Oct 2002 19:47:30 -0700 From: "Michael C. Wu" <keichii@iteration.net> To: luigi@freebsd.org, darrenr@freebsd.org Cc: freebsd-net@freebsd.org Subject: DAWG for IPFW2/IPF Message-ID: <20021010024730.GA25358@nuit.iteration.net>
next in thread | raw e-mail | index | archive | help
Hi Luigi and Darren, Regarding IPFW2 and IPF, do you have plans on implementing a DAWG algorithm for the pattern matching? (Directed Acyclic Word Graphs) http://citeseer.nj.nec.com/crochemore99fast.html It is a new algorithm that does super fast multiple stream/pattern matching in a given n-length string within O(n) . The traditional fastest Knuth algorithm only does two streams, while DAWG's do multiple streams. We use it in Bioinformatics research to match DNA sequences. However, I know for a fact that applying DAWG's to router/firewall situations would be very appropriate. Forgive my not knowing about our regex(3) implementation, what algorithm exactly does our regex(3) do/use? I was thinking that we may possibly add kernel/userland libraries for a DAWG regex. And I am willing to do the work. What do you think? Does anyone else have thoughts about this? Thanks, Michael To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-net" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20021010024730.GA25358>