Generalized Dictionary Matching Under Substring Consistent Equivalence Relations
Generalized Dictionary Matching Under Substring Consistent Equivalence Relations
复制标题
子串一致等价关系下的广义字典匹配
DOI：
10.1007/978-3-030-39881-1_11
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Hendrian Diptarama
中科院分区：
文献类型：
--
作者：
Johannes Fischer;Tomohiro I;Dominik Koeppl;Hendrian Diptarama
给定一组称为字典和文本的模式，字典匹配问题是找到文本中所有模式的所有出现位置的任务。使用Aho-Corasick算法可以有效地解决字典匹配问题。最近，松冈等人。 [TCS，2016]提出了子串一致等价关系下模式匹配问题的推广，并提出了解决该问题的 Knuth-Morris-Pratt 算法的推广。如果对于两个字符串 X、Y、隐含且对于所有，则等价关系是子串一致等价关系 (SCER)。在本文中，我们提出了字典匹配问题的推广，并提出了 SCER 下字典匹配的 Aho-Corasick 算法的推广。我们提出了一种构建 SCER 自动机的算法和一种使用自动机在 SCER 下执行字典匹配的算法。此外，我们还展示了算法相对于输入字符串大小的时间和空间复杂度。
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 relationis a substring consistent equivalence relation (SCER) if for two stringsX,Y,impliesandfor all. 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.