Clone this repo:
  1. 90d90b2 Build libdivsufsort for the target. am: 2ba0b76 am: de0b898 by Sen Jiang · 12 months ago master sdk-release android-n-mr1-preview-1 android-n-mr1-preview-2 android-n-mr2-preview-1
  2. de0b898 Build libdivsufsort for the target. am: 2ba0b76 by Sen Jiang · 12 months ago
  3. 2ba0b76 Build libdivsufsort for the target. by Sen Jiang · 12 months ago n-iot-preview-2 nougat-mr1-wear-release android-n-iot-preview-2 android-n-preview-2 android-n-preview-3 android-n-preview-4 android-n-preview-5 android-wear-7.1.1_r1 android-wear-n-preview-1 android-wear-n-preview-2
  4. ae4cb13 Merge "Add License files." by Alex Deymo · 1 year, 6 months ago brillo-m10-dev brillo-m10-release brillo-m7-dev brillo-m7-mr-dev brillo-m7-release brillo-m8-dev brillo-m8-release brillo-m9-dev brillo-m9-release nougat-cts-release nougat-dev nougat-dr1-release nougat-mr0.5-release nougat-mr1-cts-release nougat-mr1-dev nougat-mr1-release nougat-mr1.1-release nougat-mr1.2-release nougat-mr1.3-release nougat-mr1.4-release nougat-mr1.5-release nougat-release android-7.0.0_r1 android-7.0.0_r12 android-7.0.0_r13 android-7.0.0_r14 android-7.0.0_r15 android-7.0.0_r17 android-7.0.0_r19 android-7.0.0_r21 android-7.0.0_r24 android-7.0.0_r27 android-7.0.0_r28 android-7.0.0_r29 android-7.0.0_r3 android-7.0.0_r30 android-7.0.0_r31 android-7.0.0_r4 android-7.0.0_r5 android-7.0.0_r6 android-7.0.0_r7 android-7.1.0_r1 android-7.1.0_r2 android-7.1.0_r3 android-7.1.0_r4 android-7.1.0_r5 android-7.1.0_r6 android-7.1.0_r7 android-7.1.1_r1 android-7.1.1_r10 android-7.1.1_r11 android-7.1.1_r12 android-7.1.1_r13 android-7.1.1_r14 android-7.1.1_r15 android-7.1.1_r16 android-7.1.1_r17 android-7.1.1_r2 android-7.1.1_r20 android-7.1.1_r21 android-7.1.1_r22 android-7.1.1_r23 android-7.1.1_r24 android-7.1.1_r25 android-7.1.1_r26 android-7.1.1_r27 android-7.1.1_r28 android-7.1.1_r3 android-7.1.1_r4 android-7.1.1_r6 android-7.1.1_r7 android-7.1.1_r8 android-7.1.1_r9 android-cts-7.0_r1 android-cts-7.0_r2 android-cts-7.0_r3 android-cts-7.0_r4 android-cts-7.0_r5 android-cts-7.0_r6 android-cts-7.0_r7 android-cts-7.1_r1 android-cts-7.1_r2 android-cts-7.1_r3 android-n-preview-1
  5. efb03ae Add Android.mk with host targets. by Alex Deymo · 1 year, 6 months ago

libdivsufsort

libdivsufsort is a software library that implements a lightweight suffix array construction algorithm.

News

Introduction

This 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. The 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 the string.

Build requirements

  • An ANSI C Compiler (e.g. GNU GCC)
  • CMake version 2.4.2 or newer
  • CMake-supported build tool

Building on GNU/Linux

  1. Get the source code from GitHub. You can either
    • use git to clone the repository
    git clone https://github.com/y-256/libdivsufsort.git
    
  2. Create a build directory in the package source directory.
$ cd libdivsufsort
$ mkdir build
$ cd build
  1. Configure the package for your system. If you want to install to a different location, change the -DCMAKE_INSTALL_PREFIX option.
$ cmake -DCMAKE_BUILD_TYPE="Release" \
-DCMAKE_INSTALL_PREFIX="/usr/local" ..
  1. Compile the package.
$ make
  1. (Optional) Install the library and header files.
$ sudo make install

API

/* Data types */
typedef int32_t saint_t;
typedef int32_t saidx_t;
typedef uint8_t sauchar_t;

/*
 * Constructs the suffix array of a given string.
 * @param T[0..n-1] The input string.
 * @param SA[0..n-1] The output array or suffixes.
 * @param n The length of the given string.
 * @return 0 if no error occurred, -1 or -2 otherwise.
 */
saint_t
divsufsort(const sauchar_t *T, saidx_t *SA, saidx_t n);

/*
 * Constructs the burrows-wheeler transformed string of a given string.
 * @param T[0..n-1] The input string.
 * @param U[0..n-1] The output string. (can be T)
 * @param A[0..n-1] The temporary array. (can be NULL)
 * @param n The length of the given string.
 * @return The primary index if no error occurred, -1 or -2 otherwise.
 */
saidx_t
divbwt(const sauchar_t *T, sauchar_t *U, saidx_t *A, saidx_t n);

Example Usage

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <divsufsort.h>

int main() {
    // intput data
    char *Text = "abracadabra";
    int n = strlen(Text);
    int i, j;

    // allocate
    int *SA = (int *)malloc(n * sizeof(int));

    // sort
    divsufsort((unsigned char *)Text, SA, n);

    // output
    for(i = 0; i < n; ++i) {
        printf("SA[%2d] = %2d: ", i, SA[i]);
        for(j = SA[i]; j < n; ++j) {
            printf("%c", Text[j]);
        }
        printf("$\n");
    }

    // deallocate
    free(SA);

    return 0;
}

See the examples directory for a few other examples.

Benchmarks

See Benchmarks page for details.

License

libdivsufsort is released under the MIT license.

The MIT License (MIT)

Copyright (c) 2003 Yuta Mori All rights reserved.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the “Software”), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Author

  • Yuta Mori