Efficient Approximate and Dynamic Matching of Patterns Using a Labeling Paradigm (extended abstract)

A key approach in string processing algorithmics has been the labeling paradigm which is based on assigning labels to some of the substrings of a given string. If these labels are chosen consistently, they can enable fast comparisons of substrings. Until the first optimal parallel algorithm for suffix tree construction was given by the authors in 1994 the labeling paradigm was considered not to be competitive with other approaches. They show that this general method is also useful for several central problems in the area of string processing: approximate string matching, dynamic dictionary matching, and dynamic text indexing. The approximate string matching problem deals with finding all substrings of a text which match a pattern "approximately", i. e. , with at most m differences. The differences can be in the form of inserted, deleted, or replaced characters. The text indexing problem deals with finding all occurrences of a pattern in a text, after the text is preprocessed. In the dynamic text indexing problem, updates to the text in the form of insertions and deletions of substrings are permitted. The dictionary matching problem deals with finding all occurrences of each pattern set of a set of patterns in a text, after the pattern set is preprocessed. In the dynamic dictionary matching problem, insertions and deletions of patterns to the pattern set are permitted.

Authors

• Süleyman Cenk Sahinalp
• Uzi Vishkin

Keywords

• Pattern matching
• Labeling
• Dictionaries
• Indexing
• Educational institutions
• Parallel algorithms
• Heuristic algorithms
• Tree data structures
• Approximate Matching
• Dynamic Matching
• Labeling Paradigm
• Search String
• Dynamic Problem
• Dynamic Index
• Matching Problem
• Parallel Algorithm
• Difference In The Number
• Data Structure
• Dynamic Programming
• Root Node
• Patterns Of Groups
• Smallest Number
• Exact Match
• Linear Time
• Matching Algorithm
• Algorithm For Problem
• Core Dimensions
• Linear Algorithm
• Deletion Formation
• Main Core
• Compact Representation
• End Of Block
• Identity Labels