Adaptive Dictionary Matching

Semiadaptive and fully adaptive dictionary matching algorithms are presented. In the fully adaptive algorithm, the dictionary is processed in time O( mod D mod log mod D mod ). Inserting a new pattern P/sub k+1/ into the dictionary can be done in time O mod P/sub K+1/ mod log mod D mod ). A dictionary pattern can be deleted in time O(log mod D mod ). Text scanning is accomplished in time O( mod T mod log mod D mod ). Also presented is a parallel version of the algorithm with optimal speedup for the dictionary construction and pattern addition phase and a logarithmic overhead in the text scan phase. The method used incorporates a new way of using suffix trees as well as a new data structure in which the suffix tree is embedded for the sequential algorithm. >

Authors

• Amihood Amir
• Martín Farach-Colton

Keywords

• Dictionaries
• Pattern matching
• Educational institutions
• Sequences
• Tree data structures
• Parallel algorithms
• Data structures
• Concurrent computing
• Computer science
• Hamming distance
• Dictionary Matching
• Data Structure
• Time Constant
• Operation Time
• Adaptive Algorithm
• Search String
• Tree Nodes
• Exact Match
• Linear Time
• Matching Algorithm
• General Scheme
• Value Of Node
• Occurrence Patterns
• Sequential Algorithm
• Binary Tree
• Substring
• Unique Elements
• Log Time
• Parallel Algorithm