Reading the ADFA search algorithm

[stormbind]

In my random readings, I came across something by the name of "Acyclic Deterministic Finite Automaton" search algorithm which is apparently more scalable than BST.

But this is all I know

The most promising paper on the subject requires a subscription, so I am hoping someone here will have example code in Java.

--Glen

Memoria mihi benigna erit qui eam perscribam

 

[sedj]

Found these :

http://en.wikipedia.org/wiki/Trie

http://en.wikipedia.org/wiki/Acyclic_deterministic_finite_automata

http://en.wikipedia.org/wiki/Judy_array

http://en.wikipedia.org/wiki/Deterministic_finite_automata

http://www.cs.brown.edu/research/ai/dynamics/tutorial/Documents/FiniteAutomata.html

In fact, loads of stuff on DFA structures, and their associative search alogorithms :

http://www.google.co.uk/search?hl=e...tic+Finite+Automaton&btnG=Google+Search&meta=

From the little I've read, the [A]DFA is a data structure - so you would need to build that first, and then you have algorithms that search that data structure such as 'Trie' or Judy ....

--------------------------------------------------
Free Java/J2EE Database Connection Pooling Software

http://www.primrose.org.uk

 

[sedj]

oops, looks like a Trie is also a data structure itself, rather than a search alg

--------------------------------------------------
Free Java/J2EE Database Connection Pooling Software

http://www.primrose.org.uk

 

[sedj]

OK,
This has an article on how to implement Trie structures. You have to register, but its free :

http://www.ftponline.com/javapro/2003_08/magazine/columns/javatecture/

The OpenAnitVirus project (

http://www.openantivirus.org/

) seems to have implemented a Trie structure too - I geuss download their code and have a look at the package org.openantivirus.engine.censor.trie


Probably your two best bets for some actual code.

--------------------------------------------------
Free Java/J2EE Database Connection Pooling Software

http://www.primrose.org.uk

 

[stormbind]

Thanks man

(I think) I have written a Trie structure, but the ADFA is supposed to take up less space and I cannot fathom how.

Btw, I am fairly sure Judy is also a data structure, and I suspect it cannot be implemented in pure Java. The original was written in C and concerned mainly with efficient use of CPU cache - wouldn't JVM get in the way of such low-level data manipulations?

--Glen

Memoria mihi benigna erit qui eam perscribam

 

[sedj]

A Trie *is* a ADFA isn't it ?
As for how it takes up less space & stuff ... bit beyond me. I never was that good at maths and big brain stuff

--------------------------------------------------
Free Java/J2EE Database Connection Pooling Software

http://www.primrose.org.uk

 

[stormbind]

Well, I rarely mess with trees because RDMBS generally bundle competitive implementations

However, I have found that Java makes it easy to create new structures: things like BST and Trie seem straight forward.

wikipedia
If only the dictionary words need to be stored, however, without any additional information required to be stored along with each word, minimal acyclic deterministic finite automata are much more compact than tries.

This is why I want to understand the ADFA.

--Glen

Memoria mihi benigna erit qui eam perscribam