libdivsufsort 简介

libdivsufsort

libdivsufsort 是一个轻量级的后缀数组排序软件算法库。

简介

该库提供了一个简单而有效的C API，用于从恒定大小的字母上的给定字符串构造后缀数组和Burrows-Wheeler转换的字符串。该算法仅使用5n + O（1）个字节的内存空间在O（n log n）最坏情况下运行，其中n是字符串的长度。

构建依赖环境

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

在 GNU/Linux构建

从 GitHub上获取源码.
- 使用git克隆仓库
```
git clone https://github.com/y-256/libdivsufsort.git
```
- 也可以直接下载zip压缩文件
在源码包的目录里面创建一个build目录

$ cd libdivsufsort
$ mkdir build
$ cd build

为你的系统配置编译参数. 如果你想安装到本地, 请修改参数 -DCMAKE_INSTALL_PREFIX.

$ cmake -DCMAKE_BUILD_TYPE="Release" -DCMAKE_INSTALL_PREFIX="/usr/local" ..

编译源码.

$ make

安装库和头文件.

$ 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("$
");
    }

    // 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