1228940Sdelphij# libdivsufsort 2284879Sdelphij 3228940Sdelphijlibdivsufsort is a software library that implements a lightweight suffix array construction algorithm. 4228940Sdelphij 5228940Sdelphij## News 6228940Sdelphij* 2015-03-21: The project has moved from [Google Code](http://code.google.com/p/libdivsufsort/) to [GitHub](https://github.com/y-256/libdivsufsort) 7228940Sdelphij 8228940Sdelphij## Introduction 9228940SdelphijThis 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. 10228940SdelphijThe 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 11228940Sdelphijthe string. 12228940Sdelphij 13228940Sdelphij## Build requirements 14228940Sdelphij* An ANSI C Compiler (e.g. GNU GCC) 15228940Sdelphij* [CMake](http://www.cmake.org/ "CMake") version 2.4.2 or newer 16228940Sdelphij* CMake-supported build tool 17228940Sdelphij 18228940Sdelphij## Building on GNU/Linux 19228940Sdelphij1. Get the source code from GitHub. You can either 20228940Sdelphij * use git to clone the repository 21228940Sdelphij ``` 22228940Sdelphij git clone https://github.com/y-256/libdivsufsort.git 23228940Sdelphij ``` 24228940Sdelphij * or download a [zip file](../../archive/master.zip) directly 25228940Sdelphij2. Create a `build` directory in the package source directory. 26228940Sdelphij```shell 27228940Sdelphij$ cd libdivsufsort 28228940Sdelphij$ mkdir build 29228940Sdelphij$ cd build 30228940Sdelphij``` 31228940Sdelphij3. Configure the package for your system. 32228940SdelphijIf you want to install to a different location, change the -DCMAKE_INSTALL_PREFIX option. 33228940Sdelphij```shell 34228940Sdelphij$ cmake -DCMAKE_BUILD_TYPE="Release" \ 35228940Sdelphij-DCMAKE_INSTALL_PREFIX="/usr/local" .. 36228940Sdelphij``` 37228940Sdelphij4. Compile the package. 38228940Sdelphij```shell 39228940Sdelphij$ make 40228940Sdelphij``` 41228940Sdelphij5. (Optional) Install the library and header files. 42228940Sdelphij```shell 43228940Sdelphij$ sudo make install 44228940Sdelphij``` 45228940Sdelphij 46228940Sdelphij## API 47228940Sdelphij```c 48228940Sdelphij/* Data types */ 49228940Sdelphijtypedef int32_t saint_t; 50228940Sdelphijtypedef int32_t saidx_t; 51228940Sdelphijtypedef uint8_t sauchar_t; 52228940Sdelphij 53228940Sdelphij/* 54228940Sdelphij * Constructs the suffix array of a given string. 55228940Sdelphij * @param T[0..n-1] The input string. 56228940Sdelphij * @param SA[0..n-1] The output array or suffixes. 57228940Sdelphij * @param n The length of the given string. 58228940Sdelphij * @return 0 if no error occurred, -1 or -2 otherwise. 59228940Sdelphij */ 60228940Sdelphijsaint_t 61228940Sdelphijdivsufsort(const sauchar_t *T, saidx_t *SA, saidx_t n); 62228940Sdelphij 63228940Sdelphij/* 64228940Sdelphij * Constructs the burrows-wheeler transformed string of a given string. 65228940Sdelphij * @param T[0..n-1] The input string. 66228940Sdelphij * @param U[0..n-1] The output string. (can be T) 67228940Sdelphij * @param A[0..n-1] The temporary array. (can be NULL) 68228940Sdelphij * @param n The length of the given string. 69228940Sdelphij * @return The primary index if no error occurred, -1 or -2 otherwise. 70228940Sdelphij */ 71228940Sdelphijsaidx_t 72228940Sdelphijdivbwt(const sauchar_t *T, sauchar_t *U, saidx_t *A, saidx_t n); 73228940Sdelphij``` 74228940Sdelphij 75228940Sdelphij## Example Usage 76228940Sdelphij```c 77228940Sdelphij#include <stdio.h> 78228940Sdelphij#include <stdlib.h> 79228940Sdelphij#include <string.h> 80228940Sdelphij 81228940Sdelphij#include <divsufsort.h> 82228940Sdelphij 83228940Sdelphijint main() { 84228940Sdelphij // intput data 85228940Sdelphij char *Text = "abracadabra"; 86228940Sdelphij int n = strlen(Text); 87228940Sdelphij int i, j; 88228940Sdelphij 89228940Sdelphij // allocate 90228940Sdelphij int *SA = (int *)malloc(n * sizeof(int)); 91228940Sdelphij 92228940Sdelphij // sort 93228940Sdelphij divsufsort((unsigned char *)Text, SA, n); 94228940Sdelphij 95228940Sdelphij // output 96228940Sdelphij for(i = 0; i < n; ++i) { 97228940Sdelphij printf("SA[%2d] = %2d: ", i, SA[i]); 98228940Sdelphij for(j = SA[i]; j < n; ++j) { 99228940Sdelphij printf("%c", Text[j]); 100228940Sdelphij } 101228940Sdelphij printf("$\n"); 102228940Sdelphij } 103228940Sdelphij 104228940Sdelphij // deallocate 105228940Sdelphij free(SA); 106228940Sdelphij 107228940Sdelphij return 0; 108228940Sdelphij} 109228940Sdelphij``` 110228940SdelphijSee the [examples](examples) directory for a few other examples. 111228940Sdelphij 112228940Sdelphij## Benchmarks 113228940SdelphijSee [Benchmarks](https://github.com/y-256/libdivsufsort/blob/wiki/SACA_Benchmarks.md) page for details. 114228940Sdelphij 115228940Sdelphij## License 116228940Sdelphijlibdivsufsort is released under the [MIT license](LICENSE "MIT license"). 117228940Sdelphij> The MIT License (MIT) 118228940Sdelphij> 119228940Sdelphij> Copyright (c) 2003 Yuta Mori All rights reserved. 120228940Sdelphij> 121228940Sdelphij> Permission is hereby granted, free of charge, to any person obtaining a copy 122228940Sdelphij> of this software and associated documentation files (the "Software"), to deal 123228940Sdelphij> in the Software without restriction, including without limitation the rights 124228940Sdelphij> to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 125228940Sdelphij> copies of the Software, and to permit persons to whom the Software is 126228940Sdelphij> furnished to do so, subject to the following conditions: 127228940Sdelphij> 128228940Sdelphij> The above copyright notice and this permission notice shall be included in all 129228940Sdelphij> copies or substantial portions of the Software. 130228940Sdelphij> 131228940Sdelphij> THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 132228940Sdelphij> IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 133228940Sdelphij> FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 134228940Sdelphij> AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 135228940Sdelphij> LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 136228940Sdelphij> OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 137228940Sdelphij> SOFTWARE. 138228940Sdelphij 139228940Sdelphij## Author 140228940Sdelphij* Yuta Mori 141228940Sdelphij