================ 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. 

--------------------------------------------------------------------- 
