burrows-wheeler-transform.jsx

Synopsis

Burrows Wheeler transform library for JS/JSX/AMD/CommonJS

Motivation

This code is a part of Oktavia. To create FM-index index files takes much time to create suffix array. This module uses O(n) induced sorting algorithm. It can use to create suffix arraies from more than 10MB source text.

Code Example

Use from JSX

import "burrows-wheeler-transform.jsx";
import "console.jsx";

class _Main {
    static function main(argv : string[]) : void
    {
        // Simple version
        var result = BurrowsWheelerTransform.bwt('abracadabra', '$');
        // -> 'ard$rcaaaabb'

        // Detail version
        var bwt = new BurrowsWheelerTransform('abracadabra');
        console.log(bwt.get('$')); // -> 'ard$rcaaaabb'
        console.log(bwt.size());   // -> 12
        console.log(bwt.head());   // -> 3
    }
}

Use from node.js

var BWT = require('burrows-wheeler-transform.common.js').BurrowsWheelerTransform;

Use from require.js

// use burrows-wheeler-transform.amd.js
define(['burrows-wheeler-transform.js'], function (BWT) {

    var bwt = new BWT.BurrowsWheelerTransform('text');
    // Write simple usage here!
});

Use via standard JSX function

<script src="burrows-wheeler-transform.js" type="text/javascript"></script>
<script type="text/javascript">
window.onload = function () {
    var BWT = JSX.require("src/burrows-wheeler-transform.js").BurrowsWheelerTransform;
    var bwt = new BWT('text');
});
</script>

Use via global variables

<script src="burrows-wheeler-transform.global.js" type="text/javascript"></script>
<script type="text/javascript">
window.onload = function () {
    var obj = new BurrowsWheelerTransform();
});
</script>

Installation

$ npm install burrows-wheeler-transform.jsx

API Reference

static BurrowsWheelerTransform.bwt(text : string, endMarker : string = default) : string

It is a shortcut method to get converted string.

class BurrowsWheelerTransform(text : string)

This constructer Converts input text and stores results in BWT transform.

BurrowsWheelerTransform.size() : int

Input text size + sentinel(size 1).

BurrowsWheelerTransform.get(endMarker : string = default) : string

Get converted text with specified or default endMarker.

BurrowsWheelerTransform.head() : int

Head index in translated string.

Development

JSX

Don't be afraid JSX! If you have an experience of JavaScript, you can learn JSX quickly.

• Static type system and unified class syntax.
• All variables and methods belong to class.
• JSX includes optimizer. You don't have to write tricky unreadalbe code for speed.
• You can use almost all JavaScript API as you know. Some functions become static class functions. See reference.

Setup

To create development environment, call following command:

$ npm install

Repository

• Repository: git:/github.com/shibukawa/burrows-wheeler-transform.jsx.git
• Issues: https://github.com/shibukawa/burrows-wheeler-transform.jsx/issues

Run Test

$ grunt test

Build

$ grunt build

Generate API reference

$ grunt doc

Author

• shibukawa / [email protected]

License

MIT

Complete license is written in LICENSE.md.

Reference

• BWT paper: M Burrows, DJ Wheeler. A Block-sorting Lossless Data Compression Algorithm. Digital Equipment, 1994
• Induced Sort: http://www.cs.sysu.edu.cn/nong/index.files/Two%20Efficient%20Algorithms%20for%20Linear%20Suffix%20Array%20Construction.pdf