• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on String Processing and Information Retrieval(SPIRE 2004); 20041005-08; Padova(IT) >Simple Implementation of String B-Trees
【24h】

Simple Implementation of String B-Trees

机译：字符串B树的简单实现

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

摘要

The String B-tree due to Ferragina and Grossi is a well-known external-memory index data structure which handles arbitrarily long strings and performs search efficiently. It is essentially a combination of B~+-trees and Patricia tries. Prom a high-level point of view, the String B-tree of a string T of length N is a B~+-tree, where the keys are pointers to the suffixes of string T, and they are sorted in lexicographically increasing order of the suffixes. A Patricia trie is used for each node of the String B-tree. By plugging in Patricia tries at nodes, the branch/search/update operations can be carried out efficiently. Due to Patricia tries, however, the String B-tree is rather heavy and complex. In this paper we propose a new implementation of the String B-tree, which is simpler and easier to implement than the original String B-tree, and that supports as efficient search as the original String B-tree. Instead of a Patricia trie, each node contains an array, lcp_i, of integers and an array, lnc_i, of characters. Once the number of keys in a node is given, arrays lcp_i and lnc_i occupy a fixed space, while the space required for a Patricia trie can vary within a constant factor. Because arrays are simple and occupy a fixed space, they are easy to handle and suitable for external-memory data structure.
机译：归因于Ferragina和Grossi的String B树是一种众所周知的外部存储器索引数据结构，它可以处理任意长的字符串并有效地执行搜索。它本质上是B〜+树和Patricia try的组合。从高级的角度来看，长度为N的字符串T的字符串B树是B〜+树，其中的键是指向字符串T后缀的指针，并且按字母顺序从大到小排序。后缀。 Patricia trie用于字符串B树的每个节点。通过在节点上插入Patricia try，可以有效地执行分支/搜索/更新操作。然而，由于帕特里夏（Patricia）的尝试，字符串B树非常繁重且复杂。在本文中，我们提出了一种新的String B树实现，它比原始String B树更容易实现，并且支持与原始String B树一样高效的搜索。每个节点都包含一个整数数组lcp_i和一个字符数组lnc_i，而不是Patricia trie。一旦给出了节点中的键数，数组lcp_i和lnc_i将占据固定的空间，而Patricia trie所需的空间可以在恒定因子内变化。因为数组很简单并且占据固定的空间，所以它们易于处理并且适合于外部内存数据结构。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号