nark-fsa-intro

This project is just the introduction of nark-fsa, nark-fsa is private on github, it has an official site(chinese).

nark-fsa is a Finite State Automata library which implemented:

• High compression dictionary with hierachical keys
• DAWG(Directed Acyclic Word Graph)
• DFA Regular Expression Engine
• Aho-Corasick automata
• Hocroft DFA minimization algorithm
• Offline Linear time Acyclic DFA minimization
• Online Linear time Acyclic DFA minimization
• Load DFA file through Memory Mapping

nark-fsa also has many Amazing features:

• Multiple Regex Matching
• Search DFA DataBase with DFA(regex)
• Regex Intersection and Difference
• To be continued...

High compression dictionary with hierachical keys

### Features 1. Fast 1. Small: much smaller than input data set (usually 3+ times smaller, maybe 30+ times smaller, depend on input data) 1. prefix search: search keys which is a prefix of input text 1. predictive search: search suffixies which prefixies matche input text 1. value search: value search is a kind of predictive search

DAWG(Directed Acyclic Word Graph)

To be done ...

DFA Regular Expression Engine

To be done ...

Aho-Corasick automata

There are two implementation of Aho-Corasick automata: Compact Dynamic DFA based and double array trie based.

To be done ...

Hocroft DFA minimization algorithm

To be done ...

Offline Linear time Acyclic DFA minimization

To be done ...

Online Linear time Acyclic DFA minimization

To be done ...

Load DFA file through Memory Mapping

To be done ...