• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Fuzzy Systems and Knowledge Discovery(FSKD 2005) pt.1; 20050827-29; Changsha(CN) >Time and Space Efficient Search for Small Alphabets with Suffix Arrays
【24h】

Time and Space Efficient Search for Small Alphabets with Suffix Arrays

机译：时空高效搜索带有后缀数组的小字母

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

摘要

To search a pattern P in a text, index data structures such as suffix trees and suffix arrays are widely used. It is known that searching with suffix trees is faster than with suffix arrays in the aspect of time complexity. But recently, a few linear-time search algorithms for constant-size alphabet in suffix arrays have been suggested. One of such algorithms proposed by Sim et al. uses Burrows-Wheeler transform and takes O(|P| log |∑|) time. But this algorithm needs too much space compared to Abouelhoda et al.'s algorithm to search a pattern. In this paper we present an improved version for Sim et al.'s algorithm. It needs only 2n bytes at most if a given alphabet is sufficiently small.
机译：为了在文本中搜索模式P，广泛使用诸如后缀树和后缀阵列的索引数据结构。众所周知，在时间复杂度方面，使用后缀树进行搜索比使用后缀数组进行搜索要快。但是最近，提出了一些针对后缀数组中恒定大小的字母的线性时间搜索算法。 Sim等人提出的这种算法之一。使用Burrows-Wheeler变换并花费O（| P | log | ∑ |）时间。但是，与Abouelhoda等人的算法相比，该算法需要太多空间来搜索模式。在本文中，我们提出了Sim等人算法的改进版本。如果给定的字母足够小，则最多仅需要2n个字节。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号