The string B-tree: A new data structure for string search in external memory and its applications
The string B-tree: A new data structure for string search in external memory and its applications
复制标题
DOI：
10.1145/301970.301973
复制
发表时间：
1999-03-01
影响因子：
2.5
通讯作者：
Grossi, R
中科院分区：
文献类型：
--
作者：
Ferragina, P;Grossi, R
我们介绍了一个新的文本索引数据结构，即字符串B-Tree，可以看作是一些传统的外部记忆和字符串匹配数据结构之间的链接。简而言之，它是B-Trees和Patricia尝试的内部节点指数的组合，通过添加额外的指针来加快搜索和更新操作，可以更有效。因此，字符串B-Tree克服了倒文件，B-Trees，前缀B-Trees，后缀阵列，紧凑的尝试和后缀树的理论局限性。 String b-Trees的性能与B-Trees具有最差的性能，但是它们管理无界长的字符串并执行更强大的搜索操作，例如后缀树支持的搜索操作。字符串B树在主内存（RAM模型）中也很有效，因为它们可以在动态的字符串上改善在线后缀树搜索。它们还可以成功应用于数据库索引和软件重复。
We introduce a new text-indexing data structure, the String B-Tree, that can be seen as a link between some traditional external-memory and string-matching data structures. In a short phrase, it is a combination of B-trees and Patricia tries for internal-node indices that is made more effective by adding extra pointers to speed up search and update operations. Consequently, the String B-Tree overcomes the theoretical limitations of inverted files, B-trees, prefix B-trees, suffix arrays, compacted tries and suffix trees. String B-trees have the same worst-case performance as B-trees but they manage unbounded-length strings and perform much more powerful search operations such as the ones supported by suffix trees. String B-trees are also effective in main memory (RAM model) because they improve the online suffix tree search on a dynamic set of strings. They also can be successfully applied to database indexing and software duplication.