Pattern matching is a fundamental process in almost every scientific domain. The problem involves finding the positions of a given pattern (usually of short length) in a reference stream of data (usually of large length). The matching can be as an exact or as an approximate (inexact) matching. Exact matching is to search for the pattern without allowing for mismatches (or insertions and deletions) of one or more characters in the pattern), while approximate matching is the opposite. For exact matching, several data structures that can be built in linear time and space are used and in practice nowadays. For approximate matching, the solutions proposed to solve this matching are non-linear and currently impractical. In this paper, we designed and implemented a structure that can be built in linear time and space and solve the approximate matching problem in ($O(m + \frac {log_\Sigma ^kn}{k!} + occ$) search costs, where $m$ is the length of the pattern, $n$ is the length of the reference, and $k$ is the number of tolerated mismatches (and insertion and deletions).


翻译:几乎每个科学领域都存在模式匹配的基本过程。 问题在于找到数据参考流中特定模式( 通常是短长度的) 的位置( 通常是长长的 ) 。 匹配可以是精确的, 也可以是近似( 不精确的) 匹配 。 精确匹配是寻找模式, 不允许一个或一个以上字符在模式中出现不匹配( 插入和删除 ), 而近似匹配是相反的 。 对于精确匹配, 使用几个可以以线性时间和空间构建的数据结构, 并在目前实际操作中使用。 对于近似匹配, 为解决这一匹配而提出的解决方案是非线性且目前不切实际的 。 在本文中, 我们设计和实施了一个可以在线性时间和空间中构建的结构, 并解决在( $( m) +\ frac { {log\ SIgma {kn}} + occ$ 搜索成本, 其中, 美元是模式的长度, $n is the long of the refirn, 而 $ 是可容忍的错配配配( 和删除) ) 。

0
下载
关闭预览

相关内容

Python编程基础,121页ppt
专知会员服务
48+阅读 · 2021年1月1日
【干货书】真实机器学习,264页pdf,Real-World Machine Learning
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【泡泡汇总】CVPR2019 SLAM Paperlist
泡泡机器人SLAM
14+阅读 · 2019年6月12日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
人工智能 | 国际会议信息6条
Call4Papers
4+阅读 · 2019年1月4日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【推荐】(Keras)LSTM多元时序预测教程
机器学习研究会
24+阅读 · 2017年8月14日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
6+阅读 · 2021年6月4日
Arxiv
3+阅读 · 2018年10月18日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关资讯
【泡泡汇总】CVPR2019 SLAM Paperlist
泡泡机器人SLAM
14+阅读 · 2019年6月12日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
人工智能 | 国际会议信息6条
Call4Papers
4+阅读 · 2019年1月4日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【推荐】(Keras)LSTM多元时序预测教程
机器学习研究会
24+阅读 · 2017年8月14日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员