xref: /freebsd/contrib/libdivsufsort/README.md (revision 5dae51da3da0cc94d17bd67b308fad304ebec7e0) 
1# libdivsufsort
2
3libdivsufsort is a software library that implements a lightweight suffix array construction algorithm.
4
5## News
6* 2015-03-21: The project has moved from [Google Code](http://code.google.com/p/libdivsufsort/) to [GitHub](https://github.com/y-256/libdivsufsort)
7
8## Introduction
9This library provides a simple and an efficient C API to construct a suffix array and a Burrows-Wheeler transformed string from a given string over a constant-size alphabet.
10The algorithm runs in O(n log n) worst-case time using only 5n+O(1) bytes of memory space, where n is the length of
11the string.
12
13## Build requirements
14* An ANSI C Compiler (e.g. GNU GCC)
15* [CMake](http://www.cmake.org/ "CMake") version 2.4.2 or newer
16* CMake-supported build tool
17
18## Building on GNU/Linux
191. Get the source code from GitHub. You can either
20    * use git to clone the repository
21    ```
22    git clone https://github.com/y-256/libdivsufsort.git
23    ```
24    * or download a [zip file](../../archive/master.zip) directly
252. Create a `build` directory in the package source directory.
26```shell
27$ cd libdivsufsort
28$ mkdir build
29$ cd build
30```
313. Configure the package for your system.
32If you want to install to a different location,  change the -DCMAKE_INSTALL_PREFIX option.
33```shell
34$ cmake -DCMAKE_BUILD_TYPE="Release" \
35-DCMAKE_INSTALL_PREFIX="/usr/local" ..
36```
374. Compile the package.
38```shell
39$ make
40```
415. (Optional) Install the library and header files.
42```shell
43$ sudo make install
44```
45
46## API
47```c
48/* Data types */
49typedef int32_t saint_t;
50typedef int32_t saidx_t;
51typedef uint8_t sauchar_t;
52
53/*
54 * Constructs the suffix array of a given string.
55 * @param T[0..n-1] The input string.
56 * @param SA[0..n-1] The output array or suffixes.
57 * @param n The length of the given string.
58 * @return 0 if no error occurred, -1 or -2 otherwise.
59 */
60saint_t
61divsufsort(const sauchar_t *T, saidx_t *SA, saidx_t n);
62
63/*
64 * Constructs the burrows-wheeler transformed string of a given string.
65 * @param T[0..n-1] The input string.
66 * @param U[0..n-1] The output string. (can be T)
67 * @param A[0..n-1] The temporary array. (can be NULL)
68 * @param n The length of the given string.
69 * @return The primary index if no error occurred, -1 or -2 otherwise.
70 */
71saidx_t
72divbwt(const sauchar_t *T, sauchar_t *U, saidx_t *A, saidx_t n);
73```
74
75## Example Usage
76```c
77#include <stdio.h>
78#include <stdlib.h>
79#include <string.h>
80
81#include <divsufsort.h>
82
83int main() {
84    // intput data
85    char *Text = "abracadabra";
86    int n = strlen(Text);
87    int i, j;
88
89    // allocate
90    int *SA = (int *)malloc(n * sizeof(int));
91
92    // sort
93    divsufsort((unsigned char *)Text, SA, n);
94
95    // output
96    for(i = 0; i < n; ++i) {
97        printf("SA[%2d] = %2d: ", i, SA[i]);
98        for(j = SA[i]; j < n; ++j) {
99            printf("%c", Text[j]);
100        }
101        printf("$\n");
102    }
103
104    // deallocate
105    free(SA);
106
107    return 0;
108}
109```
110See the [examples](examples) directory for a few other examples.
111
112## Benchmarks
113See [Benchmarks](https://github.com/y-256/libdivsufsort/blob/wiki/SACA_Benchmarks.md) page for details.
114
115## License
116libdivsufsort is released under the [MIT license](LICENSE "MIT license").
117> The MIT License (MIT)
118>
119> Copyright (c) 2003 Yuta Mori All rights reserved.
120>
121> Permission is hereby granted, free of charge, to any person obtaining a copy
122> of this software and associated documentation files (the "Software"), to deal
123> in the Software without restriction, including without limitation the rights
124> to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
125> copies of the Software, and to permit persons to whom the Software is
126> furnished to do so, subject to the following conditions:
127>
128> The above copyright notice and this permission notice shall be included in all
129> copies or substantial portions of the Software.
130>
131> THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
132> IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
133> FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
134> AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
135> LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
136> OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
137> SOFTWARE.
138
139## Author
140* Yuta Mori
141