String Matching with Wildcards in the Massively Parallel Computation Model
String Matching with Wildcards in the Massively Parallel Computation Model
复制标题
大规模并行计算模型中通配符的字符串匹配
DOI：
10.1145/3409964.3461793
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Hajiaghayi, Mohammad
中科院分区：
文献类型：
--
作者：
Hajiaghayi, Mohammad
我们研究存在通配符的字符串匹配问题的分布式算法。给定一个字符串 T（文本），我们查找另一个字符串 P（模式）的所有出现作为字符串 T 的子字符串。模式中的每个通配符根据其类型匹配特定类别的字符串。字符串匹配是计算机科学中最基本的问题之一，尤其是在生物信息学和机器学习领域。自20世纪60年代以来，经过不懈的努力，针对该问题出现了多种算法。随着大数据的兴起以及解决海量数据集问题的必然需求，人们进行了许多尝试，将经典算法融入MPC框架中以获得进一步的效率。 MPC 是一种最新的大数据并行计算框架，旨在捕获类似 MapReduce 的算法。在本文中，我们研究了MPC模型中的字符串匹配问题，并考虑了三种类型的通配符：'?'通配符：在此设置中，模式允许包含特殊的“？”字符或不关心与文本的任何字符匹配。不关心的字符串匹配可以通过快速卷积来解决，并且我们给出了一个恒定轮MPC算法，通过显示FFT可以在恒定数量的MPC轮中实现。'+'通配符：'+'通配符是一个特殊字符，允许任意重复字符。当模式包含“+”通配符时，我们的算法通过减少子集匹配问题以恒定数量的 MPC 轮数运行。“*”通配符：“*”是与文本的任何子字符串匹配的特殊字符。当模式中允许使用“*”时，我们以对数轮次解决问题的两种特殊情况。
We study distributed algorithms for string matching problem in presence of wildcard characters. Given a string T (a text), we look for all occurrences of another string P (a pattern) as a substring of string T. Each wildcard character in the pattern matches a specific class of strings based on its type. String matching is one of the most fundamental problems in computer science, especially in the fields of bioinformatics and machine learning. Persistent effort has led to a variety of algorithms for the problem since 1960s.With rise of big data and the inevitable demand to solve problems on huge data sets, there have been many attempts to adapt classic algorithms into the MPC framework to obtain further efficiency. MPC is a recent framework for parallel computation of big data, which is designed to capture the MapReduce-like algorithms. In this paper, we study the string matching problem in the MPC model and consider three types of wildcards:'?' wildcard: In this setting, the pattern is allowed to contain special '?' characters or don't cares that match any character of the text. String matching with don't cares could be solved by fast convolutions, and we give a constant round MPC algorithm for which by showing FFT could be implemented in a constant number of MPC rounds.'+' wildcard: '+' wildcard is a special character that allows for arbitrary repetitions of a character. When the pattern contains '+' wildcard characters, our algorithm runs in a constant number of MPC rounds by a reduction from subset matching problem.'*' wildcard: '*' is a special character that matches with any substring of the text. When '*' is allowed in the pattern, we solve two special cases of the problem in logarithmic rounds.
登录
查看更多内容
量子模式匹配平均速度快
影响因子：
1.1
作者：
A. Montanaro
通讯作者：
A. Montanaro
Õ(sqrt(n)+sqrt(m)) 量子时间内的字符串匹配
DOI：
--
发表时间：
2000
期刊：
J. Discrete Algorithms
影响因子：
--
作者：
Ramesh Hariharan;V. Vinay
通讯作者：
V. Vinay
使用有限自动机的分布式模式匹配
DOI：
--
发表时间：
2001
期刊：
J. Autom. Lang. Comb.
影响因子：
--
作者：
J. Holub;C. Iliopoulos;B. Melichar;L. Mouchard
通讯作者：
L. Mouchard
DOI：
10.1007/s00453-012-9734-3
发表时间：
2006-01-01
期刊：
ALGORITHMS - ESA 2006, PROCEEDINGS
影响因子：
--
作者：
Bremner, David;Chan, Timothy M.;Taslakian, Perouz
通讯作者：
Taslakian, Perouz
实际傅立叶分析的一些改进及其在液体 X 射线散射中的应用
DOI：
10.1016/s0016-0032(42)90767-1
发表时间：
1942
影响因子：
4.1
作者：
G. C. Danielson;C. Lanczos
通讯作者：
C. Lanczos