[ Източник: xxsds-dynamic ]
Пакет: libxxsds-dynamic-dev (1.0~alpha.1+git20210426.548c6f7-2)
Връзки за libxxsds-dynamic-dev
Ресурси за Debian:
- Доклади за грешки
- Developer Information
- Журнал на промените в Debian
- Авторски права
- Управление на кръпките в Debian
Изтегляне на пакет-източник xxsds-dynamic.
- [xxsds-dynamic_1.0~alpha.1+git20210426.548c6f7-2.dsc]
- [xxsds-dynamic_1.0~alpha.1+git20210426.548c6f7.orig.tar.xz]
- [xxsds-dynamic_1.0~alpha.1+git20210426.548c6f7-2.debian.tar.xz]
Отговорници:
Външни препратки:
- Начална страница [github.com]
Подобни пакети:
succinct and compressed fully-dynamic data structures library
This library offers space- and time-efficient implementations of some basic succinct/compressed dynamic data structures. It only ships header files, i.e. is inclusion only.
DYNAMIC features:
* A succinct Searchable Partial Sums with Indels (SPSI) structure representing a list of integers s_1, s_2, ..., s_m. Space: about 1.2 * m * ( log(M/m) + log log m ) bits, where M = m + s_1 + s_2 + ... + s_m. The structure supports also update operations (i.e. s_i = s_i + delta). * A Succinct dynamic bitvector supporting rank/select/access/Indel (RSAI) operations. Space: about 1.2 * n bits. * A gap-compressed dynamic bitvector supporting rank/select/access/Indel operations. Space: about 1.2 * b * ( log(n/b) + log log b ) bits, b being the number of bits set and n being the bitvector length. All operations take log(b) time. * A dynamic sparse vector (of integers) with access/Indel operations. * A dynamic string supporting rank/select/access/Indel operations. The user can choose at construction time between fixed-length/gamma/Huffman encoding of the alphabet. All operations take log(n) * log(sigma) time (or log(n) * H0 with Huffman encoding). * A run-length encoded dynamic string supporting rank/select/access/insert operations (removes are not yet implemented). Space: approximately R*(1.2 * log(sigma) + 2.4 * (log(n/R)+log log R) ) bits, where R is the number of runs in the string. All operations take log(R) time. * A dynamic (left-extend only) entropy/run-length compressed BWT * A dynamic (left-extend only) entropy/run-length compressed FM-index. This structure consists in the above BWT + a dynamic suffix array sampling
Algorithms
* Two algorithms to build LZ77 in repetition-aware RAM working space. Both algorithms use a run-length encoded BWT with sparse Suffix array sampling. The first algorithm stores 2 SA samples per BWT run. The second algorithm (much more space efficient) stores 1 SA sample per LZ factor. From the papers "Computing LZ77 in Run-Compressed Space", Alberto Policriti and Nicola Prezza, DCC2016 and " LZ77 Computation Based on the Run-Length Encoded BWT", Alberto Policriti and Nicola Prezza (Algorithmica) * An algorithm to build the BWT in run-compressed space * An algorithm to build LZ77 in nH0(2+o(1)) space and n * log n * H0 time. From the paper "Fast Online Lempel-Ziv Factorization in Compressed Space", Alberto Policriti and Nicola Prezza, SPIRE2015 * An algorithm to build the BWT in high-order compressed space. The algorithm runs in O(n * H_k * log log n) average-case time (e.g. good for DNA) and O(n * H_k * log n) worst-case time. From the paper "Average linear time and compressed space construction of the Burrows-Wheeler transform" Policriti A., Gigante N. and Prezza N., LATA 2015 (the paper discusses a theoretically faster variant)
The SPSI structure is the building block on which all other structures are based. This structure is implemented with cache-efficient B-trees.
Изтегляне на libxxsds-dynamic-dev
Архитектура | Големина на пакета | Големина след инсталиране | Файлове |
---|---|---|---|
all | 57,2 кБ | 345,0 кБ | [списък на файловете] |