Aho-Corasick ●Pro O searching time complexity is o(n)(independent from the pattern set size) ●Cons OWhen patern set size increase, the memory needed increase drastically O Cache and memory access time changing will compromise the time performance
Aho-Corasick ⚫Pro: searching time complexity is O(n) (independent from the pattern set size) ⚫Cons: When pattern set size increase, the memory needed increase drastically. Cache and memory access time changing will compromise the time performance
AC-Modified eAC-sparse and Ac-banded o Sparse vector storing method for transitions o State and path compression by tuck o Character index ac by jianming o Others
AC-Modified ⚫AC-sparse and AC-banded Sparse vector storing method for transitions ⚫State and Path compression by tuck ⚫Character index AC by Jianming ⚫Others……
Boyer-Moore o How to safely shifting the search window without missing possible match o Two major heuristics O Good Suffix two shift value: s1, S 2) O Bad Character (one shift value: S3) o In the searching stage, the shift value is calculated by max(min(s1, s2),$ 3)
Boyer-Moore ⚫How to safely shifting the search window without missing possible match ⚫Two major heuristics Good Suffix (two shift value: s1,s2) Bad Character (one shift value: s3) In the searching stage, the shift value is calculated by max(min(s1,s2),s3)
Good suffix heuristic SI 「a S2
Good suffix heuristic
Bad character heuristic s3[a「「 a不在这部分中出现 a不在这部分中出现
Bad Character heuristic