Knuth-Morris-Pratt a□ o preprocessing phase in o(m)space and time complexity o searching phase in O(n+m) time complexity (independent from the alphabet size)
Knuth-Morris-Pratt ⚫ preprocessing phase in O(m) space and time complexity ⚫ searching phase in O(n+m) time complexity (independent from the alphabet size)
Aho-Corasick ● Automata( Finite) Oa finite set of states Q, among which one is Initial. and some are terminal Transitions between states are labeled by elements of characters orE, which is decided by a transition function f O(S, Q, I,T, F) A+-③--③、T ona DFA
Aho-Corasick ⚫Automata (Finite) a finite set of States Q, among which one is Initial, and some are Terminal transitions between states are labeled by elements of characters orε, which is decided by a transition function F (S,Q,I,T,F) NFA & DFA
Aho-Corasick NFa ③-(---- →(0 ③一0→① o AC automata(above pattern setATATATA, TATAT, ACGATAT) O Extend the concept of Border in KMP to search pattern set O NFA o Three main function O Goto function (real transition) O Failure function(dashed transition) O Output function(double circle state
Aho-Corasick: NFA ⚫ AC automata (above pattern set {ATATATA, TATAT, ACGATAT}) Extend the concept of Border in KMP to search pattern set NFA ⚫ Three main function Goto function (real transition) Failure function (dashed transition) Output function (double circle state)
Aho-Corasick: NFA o Search stage is simple o Start from state o O Read the character one after another e If current state has Goto transition for the reading character, current Goto(current) If current state has Failure transition for the reading character then While(current has relevent Goto transition current Failure(current) current+ Goto(current) o Check if current state has Output function and report
Aho-Corasick: NFA ⚫Search stage is simple Start from state 0 Read the character one after another ⚫If current state has Goto transition for the reading character, current Goto (current) ⚫If current state has Failure transition for the reading character, then While (current has relevent Goto transition) current Failure (current) current Goto (current) Check if current state has Output function and report
Aho-Corasick: DFA ● Preprocess: Conversion from nfa to dfa OTraverse the NFa and previously calculate all failure ath oa o Each reading character can find goto transition Search WIthout travel back the failure path Trade-off between storage and search speed
Aho-Corasick: DFA ⚫Preprocess: Conversion from NFA to DFA Traverse the NFA and previously calculate all failure path Each reading character can find Goto transition ⚫Search Without travel back the failure path Trade-off between storage and search speed