More efficient Tries/DAWGs - Githubissues

almondtools / stringsearchalgorithms

String matching algorithms for searching a single or multiple strings in large texts

http://stringsearchalgorithms.amygdalum.net/

GNU Lesser General Public License v3.0

44 stars 4 forks source link

More efficient Tries/DAWGs #7

Open almondtools opened 5 years ago

almondtools commented 5 years ago

The current trie actually is a directed acyclic word graph (DAWG), yet we have algorithms that do not depend on this:

Set-Horspool and Wu-Manber need simple tries (can be implemented more efficiently as double array)
Aho-Corasick needs a trie with support links (can also be implemented as double array, but needs additional structure for support links
(Set) Backward Oracle Matching uses a factor oracle base on a DAWG, so we will need this implementation at least here

Consequently each algorithm should use the best optimized variant instead of all depending on a DAWG (which is currently labeled trie).