String Matching algorithm Overview& Analysis By cyclone@ NSlab, RIIT Sep.62008
String Matching Algorithm Overview & Analysis By cyclone @ NSlab, RIIT Sep. 6 2008
Structure ● Algorithm overview o Performance experiments o Solution and future work o Bibliography and resources
Structure ⚫Algorithm overview ⚫Performance experiments ⚫Solution and future work ⚫Bibliography and resources
Algorithm Overview
Algorithm Overview
Definition o Given an alphabet bet S, a pattern P of length m and a text T of length n, find if P is in Tor the position( s)p matches a substring of T, where usually m<<n o Considering the pattern P Ostring exact string matching O string with errors approximate string matching O regular expression regular expression matching
Definition ⚫ Given an alphabet bet S, a pattern P of length m and a text T of length n, find if P is in T or the position (s) P matches a substring of T, where usually m<<n ⚫ Considering the pattern P string exact string matching string with errors approximate string matching regular expression regular expression matching
Categories ● Category1 O Single string matching algorithms O Multiple string matching algorithms o Category 2 O Prefix based algorithms O Suffix based Algorithms O Factor based Algorithms o Category 3 O Automaton based algorithms O Trie based algorithms O Table based algorithms
Categories ⚫ Category 1 Single string matching Algorithms Multiple string matching Algorithms ⚫ Category 2 Prefix based Algorithms Suffix based Algorithms Factor based Algorithms ⚫ Category 3 Automaton based Algorithms Trie based Algorithms Table based Algorithms ⚫ ……