Paper Info
Title
Generalized Dictionary Matching Under Substring Consistent Equivalence Relations
Abstract
Given a set of patterns called a dictionary and a text, the dictionary matching problem is a task to find all occurrence positions of all patterns in the text. The dictionary matching problem can be solved efficiently by using the Aho-Corasick algorithm. Recently, Matsuoka et al. [TCS, 2016] proposed a generalization of pattern matching problem under substring consistent equivalence relations and presented a generalization of the Knuth-Morris-Pratt algorithm to solve this problem. An equivalence relation approximate to is a substring consistent equivalence relation (SCER) if for two strings X, Y, X approximate to Y implies vertical bar X vertical bar = vertical bar Y vertical bar and X[i : j] approximate to Y [i : j] for all 1 <= i <= j <= vertical bar X vertical bar. In this paper, we propose a generalization of the dictionary matching problem and present a generalization of the Aho-Corasick algorithm for the dictionary matching under SCER. We present an algorithm that constructs SCER automata and an algorithm that performs dictionary matching under SCER by using the automata. Moreover, we show the time and space complexity of our algorithms with respect to the size of input strings.
Year
DOI
Venue
2020
10.1007/978-3-030-39881-1_11
WALCOM: ALGORITHMS AND COMPUTATION (WALCOM 2020)
Keywords
Field
DocType
Dictionary matching, Aho-Corasick algorithm, Substring consistent equivalence relation
Discrete mathematics,Combinatorics,Substring,Equivalence relation,Approx,Computer science,Automaton,Spacetime,Aho–Corasick string matching algorithm,Pattern matching
Conference
Volume
ISSN
Citations 
12049
0302-9743
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Diptarama Hendrian102.70