Reducing the space requirement of suffix trees
S Kurtz - Software: Practice and Experience, 1999 - Wiley Online Library
Software: Practice and Experience, 1999•Wiley Online Library
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 …
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 …
Abstract
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. Copyright © 1999 John Wiley & Sons, Ltd.
Wiley Online Library以上显示的是最相近的搜索结果。 查看全部搜索结果