首页> 外文期刊>Algorithmica >Compressed Indexes for Approximate String Matching
【24h】

Compressed Indexes for Approximate String Matching

机译:用于近似字符串匹配的压缩索引

获取原文
获取原文并翻译 | 示例
       

摘要

We revisit the problem of indexing a string S[1..n] to support finding all substrings in S that match a given pattern P[1..m] with at most k errors. Previous solutions either require an index of size exponential in k or need Ω(m k ) time for searching. Motivated by the indexing of DNA, we investigate space efficient indexes that occupy only O(n) space. For k=1, we give an index to support matching in O(m+occ+log nlog log n) time. The previously best solution achieving this time complexity requires an index of O(nlog n) space. This new index can also be used to improve existing indexes for k≥2 errors. Among others, it can support 2-error matching in O(mlog nlog log n+occ) time, and k-error matching, for any k>2, in O(m k−1log nlog log n+occ) time.
机译:我们将重新讨论索引字符串S [1..n]的问题,以支持查找S中与给定模式P [1..m]匹配的所有子字符串,最多不超过k个错误。以前的解决方案要么需要以k为单位的大小指数索引,要么需要Ω(m k )时间进行搜索。受DNA标引的影响,我们研究了仅占用O(n)空间的空间有效指标。对于k = 1,我们给出一个索引来支持O(m + occ + log nlog log n)时间的匹配。实现此时间复杂度的先前最佳解决方案需要O(nlog n)空间的索引。此新索引还可以用于改善k≥2错误的现有索引。其中,它可以支持在O(mlog nlog log n + occ)时间中进行2次错误匹配,并且在O(m k-1 log nlog中对任意k> 2进行k错误匹配。 log n + occ)时间。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号