• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on String Processing and Information Retrieval(SPIRE 2004); 20041005-08; Padova(IT) >Bit-Parallel Branch and Bound Algorithm for Transposition Invariant LCS
【24h】

Bit-Parallel Branch and Bound Algorithm for Transposition Invariant LCS

机译：换位不变LCS的位并行分支定界算法

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

摘要

Main Results. We consider the problem of longest common subsequence (LCS) of two given strings in the case where the first may be shifted by some constant (i.e. transposed) to match the second. For this longest common transposition invariant subsequence (LCTS) problem, that has applications for instance in music comparison, we develop a branch and bound algorithm with best case time O((m~2 + log log σ) log σ) and worst case time O((m~2 + log σ)σ), where m and σ are the length of the strings and the number of possible transpositions, respectively. This compares favorably against the O(σm~2) naive algorithm in most cases and, for large m, against the O(m~2 log log m) time algorithm of [2].
机译：主要结果。我们考虑两个给定字符串的最长公共子序列（LCS）最长的问题，其中第一个可以移位某个常数（即转置）以匹配第二个。针对这个最长的普通换位不变子序列（LCTS）问题（例如在音乐比较中的应用），我们开发了一种分支定界算法，其最佳情况时间为O（（m〜2 + log logσ）logσ）和最坏情况时间O（（m〜2 + logσ）σ），其中m和σ分别是字符串的长度和可能的换位次数。在大多数情况下，这与O（σm〜2）天真的算法相比是有利的，而对于较大的m，则与[2]的O（m〜2 log log m）时间算法相比。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号