๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Reducing the space requirement of suffix trees

โœ Scribed by Stefan Kurtz

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
202 KB
Volume
29
Category
Article
ISSN
0038-0644

No coin nor oath required. For personal study only.

โœฆ Synopsis

We show that suffix trees store various kinds of redundant information. We exploit these redundancies to obtain more space efficient representations. The most space efficient of our representations requires 20 bytes per input character in the worst case, and 10.1 bytes per input character on average for a collection of 42 files of different type. This is an advantage of more than 8 bytes per input character over previous work. Our representations can be constructed without extra space, and as fast as previous representations. The asymptotic running times of suffix tree applications are retained.

๐Ÿ“œ SIMILAR VOLUMES

Geometry of the Space of Phylogenetic Tr
Geometry of the Space of Phylogenetic Trees
โœ Louis J. Billera; Susan P. Holmes; Karen Vogtmann ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 693 KB

We consider a continuous space which models the set of all phylogenetic trees having a fixed set of leaves. This space has a natural metric of nonpositive curvature, giving a way of measuring distance between phylogenetic trees and providing some procedures for averaging or combining several trees w

Reducing the computational requirements
Reducing the computational requirements of the differential quadrature method
โœ Wen Chen; Yongxi Yu; Xinwei Wang ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 603 KB

This article shows that the weighting coefficient matrices of the differential quadrature method (DQM) are centrosymmetric or skew-centrosymmetric, if the grid spacings are symmetric irrespective of whether they are equal or unequal. A new skew centrosymmetric matrix is also discussed. The applicati