Program suffsort version 0.1.6

Initial revision 2003-02-13; Last revision 2004-05-31

1  Download

Win9x-EXE (minGW cross-compiled): mingw/suffsort.zip [20 Kb ]

2  File readme

suffsort --- construction of suffix array for given file


SUPPORTED ENVIRONMENTS

http://www.gnu.org    GNU/Linux 
http://www.mingw.org  MinGW --- Minimalist GNU For Windows


COMPILATION

Enter make (or gmake) in the directory where sources reside


BRIEF INSTRUCTION

This program can be used for the construction of suffix array. If you
call

suffsort file.txt

then the suffix array will be kept in file.txt.ary, where it could be
further used by cross-entropy, for example.

License conditions are described in file LICENSE.txt

3  Usage and options summary

user@computer$ ./suffsort --help
Usage: suffsort [OPTION]... FILE
Output file: FILE.ary
  -n, --naive               naive sort
  -l, --larsson-sadakane    Larsson-Sadakane
  -r, --resilence-naive     resilence naive sort (default)

  -d, --digital             output suffix array as a digital number per line

  -q, --quiet               do not send any messages to stderr
  -h, --help                display this help and exit
  -m, --man                 display complete description
  -v, --version             display version and exit

4  Description

user@computer$ ./suffsort --man
<Usage information from the previous section is omitted>


We use Larsson-Sadakane sorting algorithm for suffix sort described in
"Faster Suffix Sorting" by N. Jesper Larsson (jesper@cs.lth.se) and
Kunihiko Sadakane (sada@is.s.u-tokyo.ac.jp). It requires 9*size(FILE)
memory. One can reduce memory requirements by switchers -n (or -r) for
naive (or resilence naive) suffix sort using system qsort function. In
the last case memory requirements decay to 5*size(FILE), at cost of
slowing by factor 4.  However, the system qsort may require a lot of
memory, in particular, in the stack which might lead to errors in
sorting

5  Project revision history

2003-02-13

2003-02-18

2003-02-19

2003-05-15

2003-05-16

2004-04-10

2004-05-31

6  License

Available at http://www.math.toronto.edu/dkhmelev/PROGS/tacu/

Author:

Dmitry V. Khmelev dkhmelev((at))math.toronto.edu [change ((at)) to @ in order to get proper address - antispam]

University of Toronto, Department of Mathematics, 100 St George Street, M5S 3G3 ON, Canada

LICENSING TERMS

This program is granted free of charge for research and education purposes. However you must obtain a license from the author to use it for commercial purposes.

Scientific results produced using the software provided shall acknowledge the use of suffsort. The proper reference is:

D. Khmelev, Text Analysis and Conversion Utilities http://www.math.toronto.edu/dkhmelev/PROGS/tacu/

Moreover shall the author of suffsort be informed about the publication.

The software must not be modified and distributed without prior permission of the author.

By using suffsort you agree to the licensing terms.

NO WARRANTY

BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM ÄS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION.

IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR REDISTRIBUTE THE PROGRAM, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.