document-array

This repository contains the implementation of algorithm [1] that computes the document-array (DA) for a string collection in linear time using constant additional space.

Introduction

Our algorithm receives the suffix array (SA) of the concatenated string [2] and reuses its space to store the LF-array. Then SA is reconstructed during the computation of DA.

Build requirements

An ANSI C Compiler (e.g. GNU GCC)

API

/** @brief computes the document array of string s[0, n-1] given its SA * * @param T input concatenated string, using separators s[i]=1 and with s[n-1]=0 * @param SA Suffix array  * @param DA Document array * @param n string length * @param d number of documents * @return -1 if an error occured, otherwise returns 0 */intdocument_array_9n(unsigned char*T, int_t*SA, int_da*DA, uint_tn, uint_td);

Example

Compilation:

make

Available options:

-d D	use the first D documents of the INPUT
-v	verbose output
-o	output computed arrays to disk (INPUT.da and INPUT.sa)
-c	check output (for debug)
-p P	print the output arrays LA[1,P] and SA[1,P] (for debug)
-h	this help message

Notes:

• Supported extensions are .txt, .fasta and .fastq.

Run a test:

/maindataset/input.txt-p10-c

Output:

d=3N=32bytessizeof(int) =4bytesTOTAL:
CLOCK=0.000059TIME=0.0000000.000059SA: isSorted!!
DA: isDA!!
########
i) DASAsuffixes0) 331	#
1) 06$abacabad$...
2) 115$banaanana...
3) 230$#
4) 05a$abacabad...
5) 229a$#
6) 224aanana$#
7) 219aananaanan...
8) 17abacabad$b...
9) 111abad$banaa...
########
malloc_count ### exiting, total: 25,032, peak: 21,512, current: 1,024

References

[1] Louza, F. A., A Simple Algorithm for Computing the Document Array. CoRR abs/1812.09094 (2018)

[2] Louza, F. A., Gog, S., Telles, G. P., Inducing enhanced suffix arrays for string collections. Theor. Comput. Sci., vol. 678, pp. 22-39, 2017, Elsevier.

Thanks

Thanks to Giovanni Manzini, Travis Gagie and Nicola Prezza for helpful discussions