C. Khancome and V. Boonjing (Thailand)
Multiple string matching, dictionary matching, inverted list, trie, pattern
This paper proposes a new solution to the problem of dynamic dictionary matching. It employs inverted lists as data structures accommodating string patterns. The new solution takes (1) O(|P|) time for preprocessing, where |P| is a sum of the length of all patterns in set of pattern P; (2) O(|p|) time for insertion or deletion, where |p| is the length of pattern to be inserted or deleted; and (3) a search O(|t|+locc) time, where |t| is the length of input text and locc is the number of occurrences of matching between a character in the input text and in the inverted list.
Important Links:
Go Back
