Given a set of $k$ strings $I$, their longest common subsequence (LCS) is the string with the maximum length that is a subset of all the strings in $I$. A data-structure for this problem preprocesses $I$ into a data-structure such that the LCS of a set of query strings $Q$ with the strings of $I$ can be computed faster. Since the problem is NP-hard for arbitrary $k$, we allow an error that allows some characters to be replaced by other characters. We define the approximation version of the problem with an extra input $m$, which is the length of the regular expression (regex) that describes the input, and the approximation factor is the logarithm of the number of possibilities in the regex returned by the algorithm, divided by the logarithm regex with the minimum number of possibilities. Then, we use a tree data-structure to achieve sublinear-time LCS queries. We also explain how the idea can be extended to the longest increasing subsequence (LIS) problem.


翻译:根据一套美元字符串的一套美元字符串,他们最长的共同子序列(LCS)是最大长度的字符串,这是所有字符串的一个子集,以美元计。这个问题的数据结构预处理美元进入一个数据结构,这样可以更快地计算出一组查询字符串的LCS$Q美元,而字符串为美元。由于问题在于任意的美元,因此我们允许一个错误,允许一些字符被其他字符取代。我们用一个额外的输入美元来定义问题的近似版本,即描述输入的正则表达式(regex)的长度,而近似系数是算法返回的regex中的可能性的对数,除以对数正数正数正数正数和最小的可能性。然后,我们使用树数据结构来达到亚线性时间LCS查询。我们还解释了如何将这一想法扩展至最长的子序列问题。

0
下载
关闭预览

相关内容

正则表达式(Regular Expression,一般简写为RegEx或者RegExp),也译为正规表示法、常规表示法,台湾译「规则运算式」,在计算机科学中,是指一个用来描述或者匹配一系列符合某个句法规则的字符串的单个字符串。
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
学术报告|港科大助理教授宋阳秋博士
科技创新与创业
7+阅读 · 2019年7月19日
【泡泡汇总】CVPR2019 SLAM Paperlist
泡泡机器人SLAM
14+阅读 · 2019年6月12日
revelation of MONet
CreateAMind
5+阅读 · 2019年6月8日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
时序数据异常检测工具/数据集大列表
极市平台
65+阅读 · 2019年2月23日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年1月21日
Arxiv
0+阅读 · 2021年1月20日
Arxiv
3+阅读 · 2018年2月24日
Arxiv
4+阅读 · 2018年1月15日
VIP会员
相关资讯
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
学术报告|港科大助理教授宋阳秋博士
科技创新与创业
7+阅读 · 2019年7月19日
【泡泡汇总】CVPR2019 SLAM Paperlist
泡泡机器人SLAM
14+阅读 · 2019年6月12日
revelation of MONet
CreateAMind
5+阅读 · 2019年6月8日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
时序数据异常检测工具/数据集大列表
极市平台
65+阅读 · 2019年2月23日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员