================ Deep Shallow 64-bit =========================================== Release notes for DeepShallow 64-bit package: the original DeepShallow source code 32-bit version (Manzini and Ferragina, 2002) was converted to a 64-bit version by Mirjana Domazet-Loso, 2008. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details (file COPYRIGHT.GPL.txt) As an alternative, you can use this software under the terms of the MOZILLA PUBLIC LICENSE Version 1.1 (see file COPYRIGHT.MPL.txt) -------------------------------------------------------------------------------- The source code in this archive is an implementation of the Deep-Shallow Suffix Sorting algorithm described in the paper: G. Manzini, P. Ferragina Engineering a Lightweight Suffix Array Construction Algorithm. Proc. 10th European Symposium on Algorithms (ESA '02). Springer Verlag Lecture Notes in Computer Science n. 2461, pp 698-710. http://www.mfn.unipmn.it/~manzini/lightweight To compile the files just give the command make (without any argument). The makefile creates the executable testLcp, and the archives bwtlcp.a and ds_ssort.a which provide a simplified access to the suffix sorting routines. The procedure bwt_file() in the file bwt.c shows how an external program can call the ds suffix sorting routine. Essentially you first need to call the init_ds_ssort() routine which does some initializations and returns an integer called the overshoot. Then you can call: ds_ssort(unsigned char *text, int *sa, int n) where n is the size of the input string, text[] is an array of length (n+overshoot) which in t[0..n-1] contains the input string. [overshoot is the value returned by init_ds_ssort()] sa[] is an array of length n, which at the end of the computation contains the suffix array. Note that you are responsible of allocating text[] and sa[] BEFORE calling ds_ssort()! When calling init_ds_ssort() you must specify two arguments; the first one is the parameter d (see section 3.3 in the above paper) and the second one is the parameter b=n/B (see section 3.1 in the paper). If in doubt use d=500 and b=2000. The space occupancy of the ds algorithm is at most 5n + (36n)/b + (6n)/d bytes. Don't forget to include the file ds_ssort.h before calling the procedures init_ds_ssort() and and ds_ssort(). The makefile also creates the executables bwt and unbwt. bwt compute the Burrows-Wheeler transform of infile and writes it to infile.bwt; unbwt does the reverse transformation. -------------------------------------------------------------------- NEW: Lightweight LCP array computation The makefile creates the executable testlcp which tests several algorithm for linear time computation of the LCP array given the text and the suffix array. These algorithm are described in the paper: G. Manzini Two Space Saving Tricks for Linear Time LCP Array Computation Proc. 9th Scandinavian Workshop on Algorithm Theory (SWAT '04), Springer Verlag LNCS n. 3111, pagg. 372-383 The source code of the LCP algorithms can be found in the files lcp_aux.c, lcp5_aux.c and bwt_aux.c. ---------------------------------------------------------------------