• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>2013 Information Theory and Applications Workshop >Determining the unique decodability of a string in linear time
【24h】

Determining the unique decodability of a string in linear time

机译：确定线性时间中字符串的唯一可解码性

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Determining whether an unordered collection of overlapping substrings (called shingles) can be uniquely decoded into a consistent string is a problem common to a broad assortment of disciplines ranging from networking and information theory through cryptography and even genetic engineering and linguistics. We present three perspectives on this problem: a graph theoretic framework due to Pevzner, an automata theoretic approach from our previous work, and a new insight that yields an efficient streaming algorithm for determining whether a string of n characters over the alphabet Σ can be uniquely decoded from its two-character shingles; our online algorithm achieves an overall time complexity Θ(n + |Σ|) and space complexity O(|Σ|). As an application, we demonstrate how this algorithm can be adapted to larger, varying-size shingles for (empirically) efficient string reconciliation.
机译：确定是否可以将无序的重叠子字符串集合（称为带状疱疹）唯一解码为一致的字符串，这是从网络和信息理论到密码学乃至基因工程和语言学等广泛学科的共同问题。我们针对此问题提出三种观点：基于Pevzner的图形理论框架，我们先前工作中的自动机理论方法，以及新的见解，产生了一种有效的流算法，用于确定字母Σ上的n个字符的字符串是否可以唯一从其两个字符的瓦片解码；我们的在线算法实现了整体时间复杂度Θ（n + |Σ|）和空间复杂度O（|Σ|）。作为一个应用程序，我们演示了该算法如何适用于较大的，尺寸可变的带状疱疹，以（凭经验）有效地调节字符串。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号